II. Нахождение оптимального плана транспортной задачи методом потенциалов.

За основу берем построенный ранее методом минимальных тарифов опорный план транспортной задачи (см. табл. №9). Воспроизведем ее еще раз.

Таблица № 10

Поставщики	Потребители										Запасы
	В1 1		В2 2		В3 3		В4 4		В5 5
А1 1		4		11		6		5		15	200
	70		0		20		110		0
А2 2		8		7		9		13		10	200
	0		0		130		0		70
А3 3		10		5		12		7		20	100
	0		80		0		0		20
Потребность	70		80		150		110		90

1. Определим потенциалы каждого поставщика А_i и каждого потребителя В_j. Для этого поставим в соответствие:

поставщику А₁, т.е. первой строке, потенциал ₁,

поставщику А₂, т.е. второй строке, потенциал ₂,

поставщику А₃, т.е. третьей строке, потенциал ₃,

потребителю B₁, т.е. первому столбцу, потенциал ₁,

потребителю B₂, т.е. второму столбцу, потенциал ₂,

потребителю B₃, т.е. третьему столбцу, потенциал ₃,

потребителю B₄, т.е. четвертому столбцу, потенциал ₄,

потребителюB₅, т.е. пятому столбцу, потенциал ₅.

2. Для нахождения потенциалов составляем для каждой ненулевой клетки соотношения _i + _j = с_ij :

1 + 1 = с11 = 4;	1 + 1 = 4;
1 + 3 = с13 = 6;	1 + 3 = 6;
1 + 4 = с14 = 5;	1 + 4 = 5;
2 + 3 = с23 = 9;	2 + 3 = 9;
2 + 5 = с25 = 10;	2 + 5 = 10;
3 + 2 = с32 = 5;	3 + 2 = 5;
3 + 5 = с35 = 20;	3 + 5 = 20;

Для решения системы полагаем ₁=0. Тогда из первого уравнения получаем ₁ = 4; из второго 0 +₃ = 6  ₃ = 6; из третьего 0 +₄, = 5,  ₄ = 5.

Подставляем найденное значение ₃ = 6 в четвертое уравнение системы ₂ + ₃ = 9, тогда ₂ + 6 = 9, т.е. ₂ = 3.

Далее подставляем значение ₂ = 3 в пятое уравнение системы

₂ + ₅ = 10, отсюда 3+₅ = 10, или ₅ =7.

Следующее уравнение системы пропускаем, т.к. в нем обе переменные неизвестные.

А в последнее уравнение ₃ + ₅ = 20 подставляем найденное значение ₅ =7, получим:, ₃ + 7 = 20, т.e. ₃ = 13.

Возвращаемся к шестому уравнению: ₃ + ₂ = 5, подставляем ₃ = 13, получаем 13 + ₂ = 5 или ₂ = - 8.

Выпишем найденные значения потенциалов:

1 = 0	1 = 4	4 = 5
2 = 3	2 = -8	5 = 7
3 = 13	3 = 6

Занесем их в таблицу №10. В результате получим таблицу № 11.

Таблица № 11

Поставщики	Потребители										Запасы
	В1 1=4		В2 2=-8		В3 3=6		В4 4=5		В5 5=7
А1 1=0		4		11		6		5		15	200
	70		0		20		110		0
А2 2=3		8		7		9		13		10	200
	0		0		130		0		70
А3 3=13		10		5		12		7		20	100
	0		80		0		0		20
Потребность	70		80		150		110		90

3. Определим косвенные тарифы с_ij^* для каждой незаполненной клетки таблицы №11.

Косвенным тарифом с_ij для клетки с номером (i,j) таблицы перевозок называется алгебраическая сумма потенциалов i-той строки и j-ого столбца, на пересечении которых находится эта клетка, то есть с_ij* = _i + _j.

Отсюда следует, что для всех заполненных (базисных) клеток косвенный тариф равен истинному, т.е. с_ij* = с_ij .

Для свободных клеток в общем случае с_ij*  с_ij.

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

для клетки с номером (1, 2): с₁₂*= ₁ + ₂ = 0 - 8 = -8,

для клетки с номером (1, 5): с₁₅* = ₁ + ₅ =0 + 7 = 7,

для клетки с номером (2, 1): с₂₁* = ₂ + ₁ = 3 + 4 = 7,

для клетки с номером (2, 2): с₂₂* = ₂ + ₂ = 3 - 8 = -5

для клетки с номером (2, 4): с₂₄* = ₂ + ₄ = 3 + 5 = 8,

для клетки с номером (3, 1): с₃₁* = ₃ + ₁ = 13 + 4 = 17,

для клетки с номером (3, 3): с₃₃* = ₃ + ₃ = 13 + 6 = 19,

для клетки с номером (3, 4): с₃₄* = ₃ + ₄ = 13 + 5 = 18.

4. Проверим полученный план перевозок на оптимальность. Сформируем сначала общие правила проведения такой проверки:

1) для всех незаполненных клеток вычисляем величину  , представляющую собой разницу между косвенным и истинным тарифом.

2) если для всех свободных клеток таблицы перевозок значение критерия оптимальности _ij ≤ 0, то этот план перевозок является оптимальным. Причем если для всех свободных клеток значение критерия оптимальности _ij<0, то этот оптимальный план перевозок является к тому же и единственным. Если же для некоторых свободных клеток значение критерия оптимальности _ij = 0, то этот оптимальный план перевозок не является единственным;

3) если имеются свободные клетки, для которых критерий оптимальности _ij  0, то полученный план перевозок не является оптимальным.

В соответствии с вышеизложенным записываем рядом косвенные и истинные тарифы, а также критерий оптимальности:

с₁₂* = -8 с₁₂ = 11 ₁₂ = -8 – 11 = -19  0

с₁₅* = 7 с₁₅ = 15 ₁₅ = 7 – 15 = -8  0

с₂₁* = 7 с₂₁ = 8 ₂₁ = 7 – 8 = -1  0

с₂₂* = -5 с₂₂ = 7 ₂₂ = -5 – 7 = -12  0

с₂₄* = 8 с₂₄ = 13 ₂₄ = 8 – 13 = -5  0

с₃₁* = 17 с₃₁ = 10 ₃₁ = 17 – 10 = 7 > 0

с₃₃* = 19, с₃₃ = 12 ₃₃ = 19 – 12 = 7 > 0

с₃₄* = 18, с₃₄ = 7 ₃₄ = 18 – 7 = 12 > 0.

Так как среди полученных оценок _ij есть положительные то, план перевозок не оптимален и его необходимо улучшить.

5. Для удобства изложения воспроизведем опорный план перевозок (таблица № 11) еще раз как таблицу № 12.

Таблица № 12

Поставщики	Потребители										Запасы
	В1 1=4		В2 2=-8		В3 3=6		В4 4=5		В5 5=7
А1 1=0		4		11		6		5		15	200
	70		0		20		110		0
А2 2=3		8		7		9		13		10	200
	0		0		130		0		70
А3 3=13		10		5		12		7		20	100
	0		80		0		0	+	20
Потребность	70		80		150		110		90

Для клеток (3,1), (3,3), (3,4) _ij > 0. Среди них выбираем клетку с максимальным значением _ij. Это клетка с номером (3, 4). Ставим в ней знак "+".

Для нее строим цикл, вычеркивая в таблице №12 те столбцы и строки, в которых есть только одна поставка, считая, что в клетке (3, 4) также есть поставка.

Вычеркнутыми будут первый и второй столбец, выделим их серым цветом. Все остальные заполненные клетки образуют цикл а) на рис 3.

Каждой вершине цикла будут соответствовать чередующиеся знаки "+" или "-", расставлять которые надо, начиная с "" в клетке (3, 4), для которой мы строим этот цикл.

Затем в тех вершинах, где стоит знак "-", находим наименьшую поставку min{ 130, 110, 20}. Это 20 в вершине (3, 5).

Обозначим эту величину Δ = 20, и теперь величину Δ вычитаем из поставок в вершинах со знаком "-" и прибавляем в те вершины, где стоит "+" (см. рис. 3б). Новый цикл, полученный после пересчета, представлен на рис.3в.

	+ -		20+20		110-20		40	90
(1,3) (2,3)	110 130	(1,4) + +	(2,5)		70+20			90
	- (3;4)	70 Δ = 20	(3,5)	130-20 +20		20-20	110 20
	+	-
	а)			б)			в)

Рис. 3. Цикл пересчёта для клетки (3, 4):

а) цикл в исходном плане; б) пересчёт по циклу; в) новый цикл.

6. Заменяя старый цикл в таблице № 12 на новый, получаем таблицу №13. Обратите внимание, что после пересчёта по циклу суммы поставок по строкам и столбцам не изменились и полученный план также невырожденный.

Таблица № 13

Поставщики	Потребители										Запасы
	В1 1		В2 2		В3 3		В4 4		В5 5
А1 1		4		11		6		5		15	200
	70		0		40		90		0
А2 2		8		7		9		13		10	200
	0		0		110		0		90
А3 3		10		5		12		7		20	100
	0		80		0		20		0
Потребность	70		80		150		110		90

7. Проверим его на оптимальность, пользуясь методом потенциалов.

Определяем потенциалы каждого поставщика А_i и каждого потребителя В_j. Для чего записываем для каждой заполненной клетки таблицы № 13 соотношения _i + _j = с_ij

Для клетки (1,I):	1 + 1 = 4;
для клетки (1,3):	1 + 3 = 6;
для клетки (1,4):	1 + 4 = 5;
для клетки (2,З):	2 + 3 = 9;
для клетки (2,5):	2 + 5 = 10;
для клетки (3,2):	3 + 2 = 5;
для клетки (3,4):	3 + 4 = 7.

Полагаем ₁ = 0 и решаем систему уравнений аналогично тому, как это было сделано в п.2. В результате получаем:

1 = 0	1 = 4	4 = 5
2 = 3	2 = 3	5 =7
3 = 2	3 = 6.

8. Определим косвенные тарифы с^*_ij для каждой незаполненной клетки таблицы №13:

для клетки с номером (1, 2): с₁₂* = ₁ + ₂ = 0 + 3 = 3,

для клетки с номером (1, 5): с₁₅* = ₁ + ₅ = 0 + 7 = 7,

для клетки с номером (2, 1): с₂₁* = ₂ + ₁ = 3 + 4 = 7,

для клетки с номером (2, 2): с₂₂* = ₂ + ₂ = 3 + 3 = 6,

для клетки с номером (2, 4): с₂₄* = ₂ + ₄ = 3 + 5 = 8,

для клетки с номером (3, 1): с₃₁* = ₃ + ₁ = 2 + 4 = 6,

для клетки с номером (3, 3): с₃₃* = ₃ + ₃ = 2 + 6 = 8,

для клетки с номером (3, 5): с₃₅* = ₃ + ₅ = 2 + 7 = 9.

9. Записываем рядом косвенные и истинные тарифы, а также критерий оптимальности:

с₁₂* = 3, с₁₂ = 11; ₁₂ = 3 – 11 = -8 < 0,

с₁₅* = 7, с₁₅ = 15; ₁₅ = 7 – 15 = -8 < 0,

с₂₁* = 7, с₂₁ = 8; ₂₁ = 7 – 8 = -1 < 0,

с₂₂* = 6, с₂₂ = 7; ₂₂ = 6 – 7 = -1 < 0,

с₂₄* = 8, с₂₄ = 13; ₂₄ = 8 – 13 = -5 < 0,

с₃₁* = 6, с₃₁ = 10; ₃₁ = 6 – 10 = -4 < 0,

с₃₃* = 8, с₃₃ = 12; ₃₃ = 8 – 12 = -4 < 0,

с₃₅* = 9, с₃₅ = 20; ₃₅ = 9 – 20 = -11 < 0.

Критерий оптимальности _ij  0 выполнен для всех клеток, кроме того, все значения _ij < 0. А это значит что полученный план перевозок оптимальный и единственный.

10. Вычисляем затраты на все планируемые перевозки:

11. Сравним найденное значение F_опт с затратами F, полученными при составлении первоначального опорного плана по методу наименьшей стоимости. Видим, что транспортные расходы уменьшились на величину:

F = F - F_опт = 3620 - 3400 = 220 (тыс. руб.).

Ответ: 1) Первоначальный опорный план перевозок, построенный по методу наименьшей стоимости, приведён в таблице № 9. При этом плане перевозок транспортные расходы составляют F=3620 тыс. руб.

2) Оптимальный план перевозок приведен в таблице № 13. При этом плане перевозок транспортные расходы составляют:F_опт=3400 тыс. руб. Экономия от улучшения этого опорного плана составляет F=F-F_опт=220тыс. руб.