Решение однопродуктовой многоэтапной модели задачи методом фиктивной диагонали.

Для решения такого рода задач используются специальные способы построения матриц. Матрица 3-х этапной задачи выглядит следующим образом (см. таблицу 4.12).

Матрица состоит из четырех блоков.

В I блоке (левый верхний блок) отражаются связи между предприятиями 1 и 2 этапа, т.е. пунктами поставок сырья и предприятиями − производителями готовой продукции. В клетках блока указываются реальные показатели удельных транспортных затрат.

Во II блоке (правый верхний блок) описываются связи поставщиков сырья и потребителей готовой продукции, если такие связи имеются. Если такие связи запрещены, все показатели транспортных затрат обозначены «х» (запретительный тариф).

III блок (левый нижний блок) отображает связи пунктов производства продукции с пунктами производства продукции. Поскольку по условию задачи перевозки готовой продукции от производителей к производителям не допускаются, во всех клетках этого блока (за исключением главной диагонали) проставлен запретительный тариф (х).

Матрица трехэтапной модели задачи РРП Таблица 4.12

Каждая клетка главной диагонали описывает связь каждого предприятия, производящего продукцию, с самим собой. В этих клетках производственно-транспортные затраты принимаются равными нулю. Если в результате решения задачи клетка главной диагонали оказывается заполненной, то число в ней будет показывать недоиспользованную мощность предприятия. Главная диагональ нижнего левого блока называется фиктивной диагональю, поэтому и метод решения многоэтапной задачи размещения производства называется методом фиктивной диагонали.

В IV блоке (правом нижнем блоке) описываются связи пунктов производства продукции с пунктами потребления, в клетках этого блока указываются реальные производственно-транспорные затраты.

Решение задачи включает все 4 блока и производится с помощью любого алгоритма транспортной задачи. Процесс решения начинается с заполнения блочной матрицы так, как это было описано выше. Поскольку целью задачи является полное удовлетворение спроса конечных потребителей, решается транспортная задача по данным IV блока, находятся маршруты и объемы распределения поставок от предприятий к потребителям. Далее осуществляется переход к III блоку. По результатам распределения поставок между предприятиями и потребителями заполняются диагональные клетки третьего блока для тех предприятий, производственная мощность которых недоиспользуется, в соответствующих диагональных клетках проставляется недоиспользуемая мощность таких предприятий.

Далее осуществляется переход к I блоку. Мощность предприятий ­ производителей продукции корректируется по результатам работы с третьим блоком: величина мощности предприятия определяется как разность между исходящей и мощностью, отражённой по диагонали в III блоке. При определении оптимальных связей в I блоке каждое предприятие получает сырья столько, сколько это необходимо для функционирования с скорректированной мощностью. Нераспределённое сырьё прикрепляется к фиктивным предприятиям.

Проверка на оптимальность производится методом потенциалов (метод дается в курсе «Экономико-математические методы»).

Пример 4.5. Исходная информация представлена в таблицах 4.13 ÷ 4.14.

Таблица 4.13

Таблица 4.14

В правом нижнем углу каждой клетки таблиц проставлены удельные производственно-транспортные расходы (в тыс.руб/тонну). Норма расхода сырья λ=1. Определить оптимальную мощность перерабатывающих предприятий и найти рациональную схему распределения поставок между предприятиями на всех этапах так, чтобы совокупные затраты были минимальными.

Заполнение блочной матрицы и результаты распределения поставок сырья и готовой продукции, обоснованные размеры мощностей перерабатывающих предприятий показаны в табл. 4.15 .

Таблица 4.15

Данное распределение является оптимальным (можно проверить методом потенциалов). По результатам решения задачи можно сделать следующие выводы. Для удовлетворения спроса потребителей требуется построить два перерабатывающих предприятия: в пункте А1 мощностью 100 тонн, в пункте А2 мощностью 50 тонн. С целью полной загрузки перерабатывающих предприятий необходимы поставки сырья из пункта Q1 в объеме 100 тонн и из пункта Q4 в объеме 50 тонн (в поставках сырья из пунктов Q2, Q3 необходимости нет).

Суммарные производственно-транспортные расходы составят 410 тыс.руб: Z_min=(1∙100+1∙50)+(1∙50+2∙50+3∙10+2∙40)=410 тыс.руб.