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

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

или                                                   (15)

,                                             (16)

то модель задачи называется открытой. Для того чтобы решить транспортную задачу с открытой моделью, надо преобразовать ее в закрытую. Если дано условие (7.1), то необходимо ввести фиктивный (n + 1) пункт назначения В_n+1, т. е в матрице задачи вводится дополнительный столбец. Спрос фиктивного потребителя полага-ют равным не балансу, т. е. b_n+1 = , а все тарифы равными 0, т. е. С_i,n+1 = 0 ().

Аналогично, если дано в задаче условие (16): вводится фиктив-ный поставщик А_m+1, запас груза которого равен А_m+1=  - , а тарифы распределительной таблицы равны 0, то есть С_m+1,j = 0            (j = ).

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

6.3. Построение исходного опорного плана

Построение опорных планов, а также из преобразование будем производить в распределитель­ной таблице. Если переменная , то это число записываем в клетку (i, k) и считаем ее занятой (базисной), если же , то клетку (i, k) оставляем свободной.

Число занятых опорным планом клеток должно быть равно  (m + n - 1).

1. Метод северо-западного угла

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

Рассмотрим это правило на примере: составить план перевозок зерна из районов А₁, А₂, А₃, А₄ республики, в которых запасы составляют 800, 700, 1000, 500 тыс. ц. на три элеватора В₁, В₂, В₃ мощностью 1000, 1100 и 900 тыс. ц. Затраты на перевозку 1 ц зерна из районов на элеваторы приведены в табл. 30:

Таблица 30

Районы	Элеваторы			Запасы аi, (ц)
	В1	В2	В3
	Затраты на перевозку 1 ц зерна
А1	3	5	6	800
А2	7	2	4	700
А3	4	3	5	1000
А4	6	4	7	500
Мощность bj элеватора	1000	1100	900	3000

Установим характер задачи. Сравнивая:

 и , заключаем, что данная транспортная

задача обладает закрытой моделью, поэтому она имеет опорные планы.

Не учитывая стоимости перевозки единицы груза, начинаем удов­летворение потребностей первого потребителя (элеватора В₁ за счет района А₁), предварительно составив распределительную табл. 31.

Таблица 31

	В1	В2	В3	ai
А1	3 800	5     –	6    –	800
А2	7 200	2    500	4    –	700
А3	4 –	3    600	5   400	1000
А4	6 –	4      –	7   500	500
bj	1000	1100	900

Для этого сравниваем а₁ и b₁ (800 < 1000  а₁ < b₁) и записываем в клетку (1; 1) меньшее число 800; запасы района А₁ исчерпаны, поэтому остальные клетки 1-й строки прочеркиваем. Потребности элеватора В₁ остались неудовлетворенными на 1000 – 800 = 200 тыс. ц. Сравниваем этот остаток с запасами района А₂: так как 200 < 700, то помещаем 200 тыс. ц в клетку (2; 1), чем полностью удовлетворяем потребности элеватора В₁, а оставшиеся клетки в первом столбце прочеркиваем.

В районе А₂ осталось 700 – 200 = 500 тыс. ц, удовлетворяем элеватор В₂ за счет района А_2, для этого сравниваем этот остаток с потребностями элеватора В₂: 500 < 1100, записываем 500 тыс. ц. в клетку (2; 2), так как запасы района израсходованы полностью, то далее в строке ставим прочерки.

Потребности элеватора остались неудовлетворенными, удовлетворяем их за счет района А₃: 1100 – 500 = 600 – помещаем в клетку (3; 2), а далее в столбце прочерк.

В районе А₃ осталось 1000 – 600 = 400 тыс. ц. зерна, его отправляем на элеватор В₃, помещаем в клетку (3; 3). Мощность элеватора В₃ (900 – 400 = 500 тыс. ц. зерна) догружаем за счет района А₄, в котором имеется 500 тыс. ц. зерна, помещаем это число в клетку (4; 3).

Получили план перевозок Х₀, по которому на элеватор В₁ следует поставить 800 тыс. ц зерна из района А₁ и 200 тыс. ц зерна из района А₂.

На В₂ – 500 тыс. ц из А₂ и 600 тыс. ц из А₃.

На В₃ – 400 тыс. ц из А₃ и 500 тыс. ц из А₄.

Суммарные расходы на перевозку зерна составляют

Z(x₀) =  тыс. руб.

2. Метод «минимального элемента»

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

Рассмотрим тот же пример (табл. 32).

Таблица 32

	В1	В2	В3	ai
А1	3       800	5      –	6      –	800
А2	7     –	2    700	4      –	700
А3	4   200	3    400	5    400	1000
А4	6    –	4      –	7    500	500
bj	1000	1100	900

Просматриваем тарифы: min тариф в клетке (2; 2), поэтому в эту клетку помещаем х₂₂ = min (700; 1100) = 700; во 2-й строке ставим про­черки, так как запас зерна в районе А₂ израсходован. Просматриваем ос­тавшиеся клетки в таблице. Наименьшие тарифы имеют клетки (1; 1) и (3; 2) с₁₁ = с₃₂ = 3. В клетку (1; 1) помещаем х₁₁ = min (800; 1000) = 800, а в клетку (3; 2) – х₃₂ = min(1000; 1100 – 700) = 400. В первой строке и во 2-м столбце ставим прочерки.

Просматриваем тарифы в оставшихся клетках: наименьший тариф в клетке (3; 1). Загружаем ее х₃₁= min (1000 – 800; 1000 – 400) = 200. В первом столбце ставим прочерки, т. к. его мощность В₁  использована полностью. Смотрим тарифы далее. Наименьший в клетке (3; 3). Загружаем ее:

х₃₃ = min(1000 – 200 – 400; 900) = 400.

Загружаем клетку (4; 3): х₄₃ = min(900 – 400; 500) = 500. Получили план Х₀, для которого Z(Х₀) = 3 · 800 + 2 · 700 + 4 · 200 + 3 · 400 + 5 · 400 + 7 · 500 = 11300 тыс. руб.

6.4. Метод потенциалов решения транспортной задачи,        признак оптимальности опорных планов

1. Теорема о потенциалах: Если план Х^*=  транспортной задачи является оптимальным, то ему соответствует система из (m+n) чисел , удовлетворяющих условиям  для  и  для . Числа  называются потенциалами соответственно i-го поставщика и j-го потребителя.

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

1) каждой занятой клетке распределительной таблицы соответствует сумма потенциалов, равная тарифу этой клетки, то есть

;

2) каждой свободной клетке соответствует , то есть сумма потенциалов не превышающая тариф этой клетки.

Так как всех занятых клеток должно быть m + n – 1; то следует решить систему m + n – 1 уравнений  с (m+n) неизвестными. Система неопределенная и, чтобы найти частные решения, одному из потенциалов придаем определенной значение обычно равное 0.

Для исследования плана на оптимальность для каждой свободной клетки проверяется условие .

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

Пример 25. Пусть  для клеток (i; к) и (i; t) имеем оценки, S_ik =  = – 5; S_it= – 10.

Наиболее потенциальной является клетка (i, t).

Если для всех свободных клеток оценки S_it ≥ 0, то опорный план перевозок оптимален.

2. Если для опорного плана перевозок указанное условие оптимальности не выполняется, то за счет загрузки перспективной  свободной клетки строится замкнутый цикл с вершинами в загруженных клетках. Вершинам этого цикла условно приписываются знаки: свободной клетке «+», а следующей по часовой или против часовой стрелки «–», следующей «+» и так далее.

В клетках цикла с «отрицательными» вершинами выбирается наи­меньшее значение количество груза λ, которое и перемещается по клеткам этого цикла: прибавляется к поставкам в положительных вершинах и вычитается из поставок в отрицательных вершинах (в результате чего баланс цикла не нарушится).

Пример 26 (рис. 17).

λ = min xij = min (20, 60) = 20

             Рис. 17

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

Итак сформируем алгоритм решения транспортной задачи методом потенциалов:

1.  Построить опорный план по одному из правил: метод северо-западного угла, метод минимального элемента.

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

3. Вычислить оценки Sij для всех свободных клеток по формуле:

.

Если все S_ij ≥ 0, то полученный план – оптимальный, при этом если все S_ij > 0, то этот план единственный.

Если хотя бы одна оценка S_ij = 0, имеем бесчисленное множество оп­тимальных планов с одним и тем же значением целевой функции.

4. Если хотя бы одна оценка S_ij < 0, то план неоптимальный. Переходим к другому плану. Для этого выбираем  и эта соответствующая клетка будет перспективной. Строим для нее цикл. Получаем новый план. Для нового плана находим потенциалы и т. д. 

Пример 27. С трех складов А₁, А₂, А₃, необходимо доставить овощи в пять торговых точек В₁, В₂, В₃, В₄, В_5. Требуется закрепить склады за торговыми точками так, чтобы общая сумма затрат на перевозку была min. Числовые данные занесены в табл. 33.

Таблица 33

Склады	Торговые точки					Объем вывоза, т
	В1	В2	В3	В4	В5
	Стоимость перевозки 1 т груза в тыс. руб.
А1	7	3	5	4	2	40
А2	6	2	3	1	7	150
А3	3	5	2	6	4	100
Объем потребности, т	20	80	90	60	40	290     290

Решение:

Исходное опорное решение получим, например, по методу «минимального элемента» (табл. 34). Получен опорный вырожденный план, так как число занятых клеток должно быть m + n – 1 = 3 + 5 – 1 = 7, а у нас это число равно 6. В одну из свободных клеток помещаем 0, и считаем ее занятой. Поместим число 0, например, в клетку (1; 2) с наименьшим тарифом. План будет опорным, так как из занятых клеток не образуется циклов.

Таблица 34

	В1	В2	В3	В4	В5	а i	Ui
А1	7 –	3 0				40	0
А2	6        –   10	2     80	3   +   –			150	– 1
А3	3        +   10	5     –	3    –     10			100	– 4
bi	20		90	60	40
Vj	7		6	2	2

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

Замечание. Потенциалы можно считать и непосредственно по табл. 33, используя только заполненные клетки. Определим оценки свободных клеток:

S₁₁ = 7 – (0 + 7) = 0,              S₁₃ = 5 – (0 + 6) = –1 < 0,

S₁₄ = 4 – (0 + 2) = 2 > 0,          S₂₃ = 3 – (– 1 + 6) = – 2 < 0,

S₂₅ = 7 – (– 1 + 2) = 6 > 0,          S₃₂ = 5 – (– 4 + 3) = 6 > 0,

S₃₄ = 6 – (– 4 + 2) = 8 > 0,                S₃₅ = 4 – (– 4 + 2) = 6 > 0.

Перспективными являются клетки (1; 3) и (2; 3) с оценками S₁₃ = – 1 и S₂₃ = – 2, наиболее потенциальной является клетка (2; 3), так как – 2 < – 1. Строим для клетки (2; 3) цикл непосредственно в таблице. В цикл войдут клетки (2; 3), (2; 1), (3; 1), (3; 3).

Наименьшее количество груза, стоящее в вершинах цикла с отрица­тельным знаком λ = min (10; 90) = 10. В результате смещения λ по циклу получим новый план (табл. 35).

Таблица 35

	В1	В2	В3	В4	В5	а i	Ui
А1						40	0
А2						150	– 1
А3						100	– 2
bj	20	80	90	60	40
Vj	5	3	4	2	2

Для нового плана определяем новые потенциалы, используя только заполненные клетки и новые оценки свободных клеток:

S₁₁ = 7 – (5 + 0) = 2 > 0;

S₁₃ = 5 – (4 + 0) = 1 > 0;  S₁₄ = 4 – 2 = 2 > 0; S₂₅ = 7 – 1 = 6 > 0;

S₃₂ = 5 – 1 = 4 > 0;       S₃₄ = 6 – 0 = 6 > 0; S₃₅ = 4 – 0 = 4 > 0.

Оценки всех свободных клеток неотрицательны, значит план оптимальный. Так как все оценки S > 0, то он единственный.

Запишем оптимальный план:

Х^* = , т. е. со склада А₁ надо поставить 40 т овощей в магазин В₅, со склада А₂ – 80 т в магазин В₂, 10 т в магазин В₃, 60 т в магазин В₄ и со склада А₃ 20 т в магазин В₁, 80 т. в магазин В₃. При этом издержки перевозок:

min Z = Z(x^*) = 2 · 40 + 2 · 80 + 3 · 10 + 1 · 60 + 3 · 20 + 2 · 80 = = 520 тыс. руб.