13. ТРАНСПОРТНАЯ ЗАДАЧА С НЕПРАВИЛЬНЫМ БАЛАНСОМ

До сих пор мы рассматривали только такую задачу о перевозках, в которой сумма запасов равна сумме заявок:

Это — классическая транспортная задача, иначе называемая «транспортной задачей с правильным балансом». Встречаются такие варианты ТЗ, где условие (13.1) нарушено. В этих случаях говорят о ТЗ с неправильным балансом. Баланс ТЗ может нарушаться в двух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок:

2. Сумма поданных заявок превышает наличные запасы:

Условимся первый случай называть «ТЗ с избытком запасов», а второй — «ТЗ с избытком заявок».

Рассмотрим последовательно эти два случая.

1. ТЗ с избытком запасов

В пунктах имеются запасы груза пункты подали заявки причем

Требуется найти такой план перевозок при котором все заявки будут выполнены, а общая стоимость перевозок минимальна;

Очевидно, при этой постановке задачи некоторые условия-равенства ТЗ превращаются в условия-неравенства, а некоторые — остаются равенствами:

Мы умеем решать задачу линейного программирования, В какой бы форме — равенств или неравенств — ни были заданы ее условия. Поставленная задача может быть решена, например, обычным симплекс-методом. Однако, задачу можно решить проще, если искусственным приемом свести ее к ранее рассмотренной ТЗ с правильным балансом.

Для этого, сверх имеющихся пунктов назначения введем еще один, фиктивный, пункт назначения которому припишем фиктивную заявку, равную избытку запасов над заявками:

и положим стоимости перевозок из всех ПО в фиктивный равными нулю:

Таким образом, отправление какого-то количества груза из пункта в пункт попросту будет означать, что в пункте остались неотправленными единиц груза.

Введением фиктивного ПН с его заявкой мы сравняли баланс ТЗ, и теперь ее можно решать как обычную ТЗ с правильным балансом.