Вырожденные случаи. Открытая транспортная задача

Некоторые замечания по частным случаям, которые могут встретиться при решении.

1. Если на некотором шаге построения базисного плана из рассмотрения выпадают одновременно и строка и столбец (случай вырождения), можно использовать следующий прием: дать нулевую (фиктивную) поставку в произвольную еще не занятую клетку данной строки или столбца. (Тем самым сохраняется число занятых клеток m+n–1 для базисного распределения поставок).

2. Если в отрицательных вершинах цикла, по которому перераспределяется поставка, две или более минимальных поставок, то все они при перераспределении обратятся в нуль. Так как на каждом шаге число занятых клеток сохраняется в количестве m+n–1, то из этих “нулевых” клеток образуется только одна пустая клетка, а остальные считаются заполненными поставкой равной 0.

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

Рассмотрим некоторые моменты, имеющие практическое значение, но усложняющие постановку транспортной задачи:

1. Обязательные поставки.

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

2. Ограничения пропускной способности.

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

Самый простой способ учитывать пропускную способность состоит в следующем:

Пусть поставка в клетку (i,j) ограничена числом, строго меньшим В_j. Столбец j, соответствующий потребителю с ограниченной пропускной способностью, разбивается на два столбца, в одном спрос принимается равным ограничению, а в другом – остатку. Показатели транспортных затрат одинаковы для этих двух столбцов за исключением клетки (i,j) в столбце, где спрос равен разности (остатку). Здесь с_ij принимается очень большим, блокирующим какую-либо поставку в эту клетку.

До сих пор мы рассматривали закрытую транспортную задачу, т.е. при условии баланса спроса и объемов производства (мощностей). В практических задачах это условие далеко не всегда выполняется. При нарушении баланса возникает открытая транспортная задача, которая решается сведением ее к закрытой транспортной задаче.

При превышении суммарной мощности над суммарным спросом на величину D вводится дополнительный столбец так называемого фиктивного потребителя со спросом равным D. Показатели с_in+1(i=1,2,…,m) в этом столбце выбираются произвольно, но с одним условием, что все они равны между собой. Удобнее всего принимать их равными 0. Далее задача решается как закрытая.

Аналогично, при превышении суммарного спроса над суммарной мощностью на величину D вводится дополнительная строка так называемого фиктивного поставщика с мощностью равной D и с нулевыми транспортными издержками.