Метод потенциалов

35 35

5

35 35

50

40 20

15 55

20

15 55

50

40 10

(2,1) 3 + (2,2) 4 –

Рис. 2.3.1

Для циклов в транспортной задаче характерны следующие особенности:

а) цикл является замкнутым многоугольником;

б) вершинами цикла являются клетки таблицы, причем одна из вершин – пустая клетка, а все остальные – клетки с поставками базисного плана (с выделенными числами);

в) все углы цикла прямые и каждый отрезок цикла, ограниченный двумя вершинами, целиком принадлежит к одному столбцу или к одной строке таблицы;

г) в цикле четное число вершин;

д) отрезки цикла могут проходить заполненные поставками клетки, не являющиеся вершинами данного цикла;

е) в цикле одинаковое количество положительных и отрицательных вершин.

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

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

Рассмотрим табл. 2.3.5. Записав единичную поставку в клетку (2.1), мы увеличили целевую функцию на 3 (с₂₁=3). Уменьшив поставку в клетку (1,1) на единицу, мы уменьшили значение целевой функции на 2 (с₁₁=2). Увеличив поставку в клетку (1.2), мы увеличили целевую функцию на 1 (с₁₂=1). И, наконец, уменьшив поставку в клетку (2,2) на единицу, мы уменьшили значение целевой функции на 4 (с₂₂=4). В итоге целевая функция изменилась на 3–2+1–4= –2 (т.е. уменьшилась на 2). Эту величину и будем называть оценкой пустой клетки (i,j) и обозначать е_ij. Отметим, что оценка может быть как отрицательная, так и положительная.

Только что мы вычислили е ₂₁ = –2. Значит каждая единичная поставка в клетку (2,1) будет уменьшать значение целевой функции на 2. Чем больше будет величина поставки в клетку (2,1), тем лучше будет план поставок. Очевидно, наибольшее значение поставки в клетке (2,1) будет равно величине меньшей из поставок в отрицательных вершинах цикла. В противном случае в одной из этих вершин появится отрицательная поставка, что противоречит условиям задачи.

Наибольшее значение х ₂₁ в данном случае равно 40 (перепоставка из отрицательной вершины (1,1)). Принимая х ₂₁ = 40, для сохранения баланса по строкам и столбцам корректируем на эту величину поставки в остальных вершинах цикла:

х ₁₁ = 0, х ₁₂ = 50, х ₂₂ = 20.

Получим новый базисный план.

Транспортные издержки этого плана (см. табл. 2.3.6) изменились на е ₂₁ х ₂₁ = –2´40 = –80, т.е. уменьшились на 80.

Суммарные транспортные затраты для данного распределения можно посчитать и по общей формуле:

F = 1´50 + 3´40 +4´20 + 6´15 + 6´55=670.

Мы видим, что и по общей формуле расчета суммарные транспортные затраты уменьшились на 750 – 670 = 80 единиц.

Таблица 2.3.6

	2	1	5
	3	4
	4	15	6

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

1. Находим исходный базисный план.

2. Для пустых клеток определяем оценки е _ij, пока не найдем клетку с отрицательной оценкой.

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

4. Для нового базисного плана выполняем опять процедуру 2.

Если все оценки е_ij ³ 0, то план поставок улучшить невозможно (суммарные транспортные издержки не уменьшаются), значит, полученный на последнем шаге план поставок оптимальный.

Если существует хотя бы одна клетка с отрицательной оценкой – переходим к процедуре 3. Будем придерживаться этого общего алгоритма решения для улучшения нашего нового базисного плана.

Определим оценку клетки (1,3) с помощью цикла (рис. 2.3.2).

(1,2) 1 – (1,3) 5 +

е ₁₃ =5 –1 + 6 – 6 = +4

(3,2) 6 + (3,3) 6 –

Рис. 2.3.2

Значит, давать поставку в клетку (1,3) невыгодно – приращение целевой функции положительное, т.е. это приведет к удорожанию плана перевозок. Определим оценку следующей пустой клетки (2,3) с помощью цикла (рис. 2.3.3).

(2,2) 4 – (2,3) 3 +

е ₂₃ =3 – 4 + 6 – 6 = –1

(3,2) 6 + (3,3) 6 –

Рис. 2.3.3

Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать поставку (максимально возможную) в клетку (2,3). Очевидно, максимально возможная величина поставки х ₂₃ = 20, что изменит значение целевой функции на –1´20 = –20. Скорректировав соответственно поставки х ₂₂ = 0, х ₃₂ = 35, х ₃₃ = 35, получаем новый базисный план (табл. 2.3.7).

Таблица 2.3.7

	2	1	5
	3	4
	4	35	6

Суммарные транспортные затраты для данного распределения:

F = 1´50 + 3´40 +3´20 + 6´35 + 6´35=650.

Проверим этот план на оптимальность. Для этого нужно узнать, нет ли отрицательных оценок пустых клеток.

Рассмотрим клетку (3,1). Цикл для нее изображен на рис. 2.3.4. Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать максимально возможную поставку в эту клетку х ₃₁ = 35. Целевая функция должна уменьшиться на 2´35 = 70.

(2,1) 3 – (2,3) 3 +

е ₃₁ =4 –3 +3 – 6 = –2

(3,1) 4 + (3,3) 6 –

Рис. 2.3.4

Скорректировав соответственно в вершинах цикла поставки х ₂₁ = 5, х ₂₃ = 55, х ₃₃ = 0, получаем новый базисный план (табл. 2.3.8).

Таблица 2.3.8

	2	1	5
	3	4
	4	35	6

Суммарные транспортные затраты для данного распределения:

F = 1´50 + 3´5 +3´55 + 4´35 + 6´35=580,

т.е., как мы и предполагали, уменьшились на 650 – 580 = 70.

Проверим теперь этот план на оптимальность. Для этого опять вычисляем оценки пустых клеток. Рассмотрим клетку (1,1). Цикл для нее изображен на рис. 2.3.5.

(1,1) 2 + (1,2) 1 –

е ₁₁ = +2 –1 +6 –4=+3

(3,1) 4 – (3,2) 6 +

Рис. 2.3.5

Рассмотрим клетку (2,2). Цикл для нее изображен на рис. 2.3.6.

(2,1) 3 – (2,2) 4 +

е ₂₂= +4 –6 +4 –3= –1

(3,1) 4 + (3,2) 6 –

Рис. 2.3.6

Значит, и этот план не оптимальный. Его можно улучшить, если дать максимально возможную поставку в эту клетку: х ₂₂ = 5. Целевая функция уменьшается на 1´5 = 5. Скорректировав соответственно в вершинах цикла поставки х ₂₁ = 0, х ₃₁ = 40, х ₃₂ = 30, получаем новый базисный план (табл. 2.3.9).

Суммарные транспортные затраты составят:

F = 1´50 + 4´5 +3´55 + 4´40 + 6´30=575,

что как раз на 5 единиц меньше предыдущего значения целевой функции. Этот план оптимальный, оценки всех пустых клеток (е ₁₁, е ₁₃, е ₂₁,е₃₂) неотрицательны!

Таблица 2.3.9

	2	1	5
	3	4
	4	30	6

Студентам предоставляется возможность самим убедиться, что этот план оптимальный.

Основным недостатком распределительного метода является необходимость построения циклов с целью определения оценок клеток. Так, при таблице 25 строк на 25 столбцов на каждом шаге для проверки оптимальности плана надо строить m´n – (m+n–1) = 25´25 – (25+25–1) = 576 циклов. В некоторых случаях циклы имеют множество вершин и довольно сложную конфигурацию.

Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов. Этот способ имеет свои разновидности. Мы рассмотрим одну из них, предложенную Дж.Данцигом в 1951 году и названную им методом МОДИ.

Следует отметить, что Л.В.Канторовичем еще в 1940 году был разработан метод, отличающийся от метода МОДИ лишь весьма несущественными деталями. Свой метод Л.В.Канторович назвал методом потенциалов. Мы так и будем его называть.

Идея метода заключается в том, что для определения оценок пустых клеток предварительно находятся некоторые числа (потенциалы). Потенциалы ставятся в соответствие каждой строке и каждому столбцу. Потенциал i-й строки обозначим u_i, а потенциал j-го столбца v_j. Потенциалы определяются исходя из требования: для каждой занятой клетки (i,j) алгебраическая сумма потенциалов i-й строки и j-го столбца должна быть равна транспортным издержкам с _ij:

с _ij = u_i+ v_j, u_i = с _ij – v_j, v_j = с _ij – u_i. (2.3.6)

Затем оценки каждой пустой клетки определяются по формуле:

е _ij = с _ij – (u_i+ v_j). (2.3.7)

Как же определяются потенциалы?

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

Проиллюстрируем это на примере, условия которого приведены в табл. 2.3.10 с базисным планом, полученным методом северо-западного угла.

Примем произвольно, например, для 2-й строки потенциал u₂=10.

Тогда по формулам (2.3.6) можно вычислить потенциалы 2-го и 3-го столбца, а именно:

v₂ = с ₂₂ – u₂ = 5 – 10 = –5,

v₃ = с ₂₃ – u₂ = 7 – 10 = –3.

Таблица 2.3.10

Аi^Вj						ui
	55	25
		65	10
			30	15
				15	20
vj	–4	–5	–3	–2	–1

Теперь, используя уже вычисленные потенциалы v₂и v₃, находим потенциалы 1-й и 3-й строки:

u₁ = с ₁₂ – v₂ = 4 – (–5) = 9,

u₃ = с ₃₃ – v₃ = 3 – (–3) = 6.

А теперь, используя уже вычисленные потенциалы u₁и u₃, находим потенциалы 1-го и 4-го столбца:

v₁ = с ₁₁ – u₁ = 5 – 9 = –4,

v₄ = с ₃₄ – u₃ = 4 – 6 = –2.

Нам осталось вычислить потенциалы 4-й строки и 5-го столбца:

u₄ = с ₄₄ – v₄ = 5 – (–2) = 7,

v₅ = с ₄₅ – u₄ = 6 – 7 = –1.

Зная потенциалы всех столбцов и строк по формуле (2.3.7) вычисляем оценки любой пустой клетки. В данном примере

е ₁₃ = с₁₃ – (u₁+ v₃) =3 – (9 –3) = –3,

е ₁₄ = с₁₄ – (u₁+ v₄) =2 – (9 –2) = –5,

е ₁₅ = с₁₅ – (u₁+ v₅) =1 – (9 –1) = –7,

е ₂₁ = с₂₁ – (u₂+ v₁) =3 – (10–4) = –3,

е ₂₄ = с₂₄ – (u₂+ v₄) = 5 – (10–2) = –3,

е ₂₅ = с₂₅ – (u₂+ v₅) = 3 – (10–1) = –6,

е ₃₁ = с₃₁ – (u₃+ v₁) = 5 – (6–4) =3,

е ₃₂ = с₃₂ – (u₃+ v₂) = 4 – (6–5) =3,

е ₃₅ = с₃₅ – (u₃+ v₅) = 5 – (6–1) =0,

е ₄₁ = с₄₁ – (u₄+ v₁) = 2 – (7–4) = –1,

е ₄₂ = с₄₂ – (u₄+ v₂) = 3 – (7–5) =1,

е ₄₃ = с ₄₃ – (u₄+ v₃) = 4 – (7–3) =0.

Найдя отрицательную оценку, перемещаем в соответствующую клетку поставку по циклу, как и в распределительном методе.

Можно найти сначала все отрицательные оценки, а затем выбрать клетку, перемещение поставки в которую даст наибольший эффект, т.е. наибольшую величину уменьшения целевой функции. Заметим, что эта величина зависит как от значения оценки, так и от максимально допустимой поставки, которую можно дать в данную клетку. Студентам предоставляется право самостоятельно довести решение до конца. Оптимальное решение приведено в табл. 2.3.11.

Таблица 2.3.11

Аi^Вj
		50		30
	55	0			20
		5	40
		35

Дата добавления: 2015-04-24