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

Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов. Этот способ имеет свои разновидности. Мы рассмотрим одну из них, предложенную Дж.Данцигом в 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