Открытые модели ТЗ и усложнения в ее постановке.

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

называется закрытой моделью; в противном случае – открытой. Для открытой модели может быть два случая:
а) суммарные запасы превышают суммарные потребности:

;
б) суммарные потребности превышают суммарные запасы:

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

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

, вводится фиктивный потребитель (столбец В_n+1), потребности которого

. В случае (б), когда суммарные потребности превышают суммарные запасы, т.е.

, вводится фиктивный поставщик (строка A_m+1), запасы которого

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

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

Замечание 2. При составлении первоначального опорного плана методом минимальной стоимости или двойного предпочтения необходимо наименьшую стоимость выбирать только среди стоимостей реальных поставщиков и потребителей, а запасы фиктивного поставщика (потребности фиктивного потребителя) распределять в последнюю очередь. Это позволит получить план, более близкий к оптимальному.
Отмеченное во втором замечании используют также при введении фиктивно запятых клеток.

Рекомендации приведения задачи к обычной ТЗ

При решении конкретных транспортных задач приходится часто учитывать некоторые дополнительные ограничения: невозможность (запрет) поставки груза из A_k в В_i (блокировка), обеспечение пункта В_j , заданным количеством a_ij единиц груза за счет пункта отправления A_i и т.п. В этих случаях поступают следующим образом:

Запрет перевозок груза из A_i в В_j осуществляется занесением в клетку A_i В_j числа c_ij = М > 0 (здесь и в последующем М - сколь угодно большое число). При оптимальном плане эта клетка будет блокирована.

По условию задачи требуется доставить из A_i в В_j α_ij единиц груза. Следует занести в начале заполнения таблицы в клетку A_i В_j число α_ij , считать ее в дальнейшем свободной (c_ij = М), а потребности b_j и запасы а_i уменьшить на α_ij. Найденный оптимальный план новой задачи будет оптимальным и для исходной (с добавлением x_ij = α_ij ).

Если требуется из A_i в В_j завести груз x_ij ≥ 0 - заданного числа, то уменьшают запасы а_i и потребности b_j на α_ij и находят оптимальный план новой задачи, по которому определяют и решение исходной задачи (x*_ij = α_ij + x_ij, где x_ij > 0 - компонента плана новой задачи).

Иногда требуется перевезти из A_i в В_j груза не более заданного объема x_ij < α_ij. Тогда, чаще всего, поступают следующим образом: в таблицу вводят дополнительный столбец В*_j с тарифами, равными тарифам столбца В_j , кроме клетки A_i В_j , где полагают c_ij = М. При этом потребности пункта В_j считаются равными α_ij , a В*_j - равными b_j - α_ij .

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

Тема 2.8. Открытые модели ТЗ и усложнения в ее постановке.