Метод потенциалов. Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов

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