Открытая и закрытая модели транспортной задачи

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

Критерий разрешимости для закрытой модели

(5)

(6)

Легко убедиться, что рассмотренный выше пример (задача о холодильных установках) представляет собой открытую модель, и так как 120 + 40 + 90 150 + 90 (250 240), она разрешима. Если поставить эту модель, как закрытую, она станет неразрешимой, так как невозможно без излишков поставить 250 холодильных установок в центры сбыта, которые нуждаются всего лишь в 240 установках.

Любую открытую модель можно преобразовать в закрытую.

Если общие запасы превышают потребности (), то в модель вводят еще одного потребителя, (m+1)-го по счету. Его принято называть дополнительным или фиктивным. На самом деле его нет, но условно можно считать, что именно к нему свозят все излишки. Соответственно, его «потребность» в продукции b_m₊₁ примем равной . Одновременно в модель вводятся n новых переменных x_im₊₁, . Каждая из этих переменных по экономическому смыслу представляет собой излишек продукции у i-го поставщика (столько продукции «везут» от i-го поставщика фиктивному потребителю). При этом все новые переменные в целевую функцию не входят (т.е. входят с нулевыми коэффициентами
c_im₊₁ = 0), поскольку на самом деле перевозки этой продукции не осуществляются. Излишек продукции остается у поставщиков, следовательно, и платить за его перевозку не надо.

Тогда транспортная задача примет вид:

(6)

При этом целевая функция в модели (6) может также иметь вид (отброшенные слагаемые все равно нулевые).

Собственно, в зависимости от экономической интерпретации открытой модели критерий ее разрешимости можно и вообще снять. А именно, если общий объем потребностей превышает объем запасов (), можно аналогично ввести дополнительного (фиктивного) поставщика, (n+1)-го по счету. Условно будем считать, что именно у этого поставщика находится вся недостающая продукция, поэтому его запасы
а_n+1 = . При этом также придется ввести m новых переменных x_n₊₁_j, - это дефицит продукции у j-го потребителя (т.е. та продукция, которую ему «везут» от несуществующего поставщика; этому потребителю ее не хватит). Разумеется, за перевозки несуществующей продукции не платят, поэтому все c_n₊₁_j = 0.

Тогда модель примет вид:

или

(7)

Итак, если в транспортной модели допускается дефицит, то она всегда будет разрешима после преобразования открытой модели в закрытую.

Чтобы преобразовать задачу о холодильных установках в закрытую, необходимо ввести дополнительный (третий) центр сбыта, потребность которого в холодильных установках будет равняться 10 (b₃ = 250 - 240 = 10). Одновременно в модель будут введены три новые переменные: x₁₃, х₂₃ и х₃₃ – число установок, не вывезенных соответственно из Стокгольма, Триеста и Руана. В целевую функцию они не войдут (войдут с нулевыми коэффициентами с₁₃= с₂₃ = с₃₃ = 0) – в самом деле, если установки остаются в центрах производства, затраты на их перевозку не осуществляются. Тогда задача примет вид:

min (25x₁₁ + 14x₁₂ + 18x₂₁ + 8x₂₂ + 12x₃₁ + 6x₃₂)

x₁₁ + x₁₂ + x₁₃ = 120