Транспортные задачи с дополнительными ограничениями

Задачи с обязательными поставками

В качестве примера решения такой задачи рассмотрим исходные данные, приведенные в таблице 3.2.6.

Таблица 3.2.6 – Исходная транспортная таблица задачи с обязательными поставками

Запасы поставщиков	Потребности потребителей
B1 = 100	B2 = 200	B3 = 50	B4 = 250	B5 = 150
Распределение перевозок
A1 = 200
A2 = 150
A3 = 225
A4 = 175

Пусть в силу определенных обстоятельств (например, госзаказ) поставщик А₃, несмотря на фактические затраты, обязан поставить потребителю В₄ не менее 100 единиц продукции. Исключим эту обязательную поставку из транспортной задачи (таблица 3.2.7).

Таблица 3.2.7 – Транспортная таблица с исключенными обязательными поставками

Запасы поставщиков	Потребности потребителей
B1 = 100	B2 = 200	B3 = 50	B4 = 150	B5 = 150
Распределение перевозок
A1 = 200
A2 = 150
A3 = 125
A4 = 175

Затем решается обычная транспортная задача, но при определении суммарных затрат на перевозки необходимо учесть и затраты на обязательные поставки: 100 × 52 = 5200.

Задачи с запретами

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

Таблица 3.2.8 – Исходная транспортная таблица задачи с запретами, составленная методом наименьшего элемента

Запасы поставщиков	Потребности потребителей
B1 = 100	B2 = 200	B3 = 50	B4 = 252	B5 = 177
Распределение перевозок
A1 = 227
A2 = 152
A3 = 225
A4 = 175

Пусть в силу некоторых обстоятельств поставки по каналу А₁-В₂ невозможны. Поставим в соответствующую клетку транспортной таблицы вместо реальной стоимости перевозки М (сколь угодно большое число, большее любого наперед заданного числа). Решаем эту задачу методом потенциалов так, как это было показано в разделе 3.2.3.2 (таблица 3.2.9).

Таблица 3.2.9 – Решение транспортной задачи (первая итерация)

Наибольшая по модулю разность между стоимостью и псевдостоимостью (оценка цикла) соответствует клетке А₂-В₂, для которой и составляем цикл. После перестановки по этому циклу 75 единиц продукции (минимальное число, стоящее в отрицательной вершине) получается новый план, представленный в таблице 3.2.10.

Таблица 3.2.10 – Решение транспортной задачи (вторая итерация)

Как видно из таблицы, объем перевозок по каналу с запретом уменьшился. Повторяем процедуры метода потенциалов. В результате получаем новую таблицу 3.2.11.

Таблица 3.2.11 – Решение транспортной задачи (после второй итерации)

Запасы поставщиков	Потребности потребителей
B1 = 100	B2 = 200	B3 = 50	B4 = 252	B5 = 177
Распределение перевозок
A1 = 227		M
A2 = 152
A3 = 225
A4 = 175

В дальнейшем процесс решения происходит аналогично до тех пор, пока есть отрицательные оценки циклов.