5.6 Определение оптимального плана транспортных задач, имеющих некоторые усложения в их постановке.

При нахождении решения ряда конкретных транспортных задач часто бывает не­обходимо учитывать дополнительные ограничения, которые не встречались выше при рассмотрении простых вариантов данных задач. Остановимся подробнее на некоторых возможных услож­нениях в постановках транспортных задач.

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

2. В отдельных транспортных задачах дополнительным усло­вием является обеспечение перевозки по соответствующим мар­шрутам определенного количества груза. Пусть, например, из пункта отправления , в пункт назначения требуется обяза­тельно перевести единиц груза. Тогда в клетку таблицы дан­ных транспортной задачи, находящуюся на пересечении строки и столбца записывают указанное число и в дальнейшем эту клетку считают свободной со сколь угодно большим тарифом перевозок М. Для полученной таким образом новой транспорт­ной задачи находят оптимальный план, который определяет опти­мальный план исходной задачи.

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

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

(1)

Сформулированную задачу можно решить так. В таблице исход­ных данных задачи для каждого -го ограничения (1) преду­сматривают дополнительный столбец, т. е. вводят дополнитель­ный пункт назначения. В данном столбце записывают те же тари­фы, что и в столбце , за исключением тарифа, находящегося в -й строке. В дополнительном столбце в этой строке тариф счита­ют равным некоторому сколь угодно большому числу . При этом потребности пункта считают равными „ а потребности вновь введенного пункта назначения полагают равными . Решение полученной транспортной задачи может быть найдено методом потенциалов, и тем самым будет определен оптимальный план или установлена неразрешимость исходной задачи. Заме­тим, что исходная транспортная задача разрешима лишь в том случае, когда для нее существует хотя бы один опорный план.

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

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

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