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

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