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

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

Пример 7.9. Найти оптимальное распределение поставок для транспортной задачи (табл. 7.17).

Таблица 7.17

Решение. В данном случае суммарная мощность потребителей больше, чем суммарная мощность поставщиков (45+35+55+65=200>40+60+90 = 190). Введем "фиктивного поставщика" и в таблице поставок добавим дополнительную строку (табл. 7.18) так, чтобы задача стала закрытой. Для этого мощность фиктивного поставщика следует принять равной 10 = 200 - 190. Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например, нулю, как в табл. 7.18). Согласно теореме 7.3, конкретное значение этого числа не влияет на оптимальное распределение поставок.

Таблица 7.18

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

Таблица 7.19

0 1 0 2

Установим, оптимально ли это распределение — найдем для него матрицу оценок (табл. 7.19).

(7.19)

Так как среди оценок свободных клеток есть отрицательные, то найденное распределение не оптимально. Переведем поставку в одну из клеток с наименьшей отрицательной оценкой, например, в клетку (4,3). Цикл для этой клетки изображен на рис. 7.7. Поставка, передаваемая по циклу, равна x ₄₃ ⁼ min{50,35,10} = 10.

+

-

(2,1) (2,3)

-

+

(3,1) (3,4)

	(4,4)

-

+

(4,3)

Рис. 7.7

Передвигая по циклу поставку, равную 10 единицам, приходим к следующему распределению поставок (табл. 7.20).

Таблица 7.20

Найдем оценки свободных клеток данного распределения (см. матрицу оценок 7.20). Так как оценки всех свободных клеток неотрицательны, то распределение поставок табл. 7.20 оптимально.

(7.20)

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