Метод потенциалов
Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов. Этот способ имеет свои разновидности. Мы рассмотрим одну из них, предложенную Дж.Данцигом в 1951 году и названную им методом МОДИ.
Следует отметить, что Л.В.Канторовичем еще в 1940 году был разработан метод, отличающийся от метода МОДИ лишь весьма несущественными деталями. Свой метод Л.В.Канторович назвал методом потенциалов. Мы так и будем его называть.
Идея метода заключается в том, что для определения оценок пустых клеток предварительно находятся некоторые числа (потенциалы). Потенциалы ставятся в соответствие каждой строке и каждому столбцу. Потенциал i-й строки обозначим ui, а потенциал j-го столбца vj. Потенциалы определяются исходя из требования: для каждой занятой клетки (i,j) алгебраическая сумма потенциалов i-й строки и j-го столбца должна быть равна транспортным издержкам сij:
сij = ui+ vj, ui= сij – vj , vj= сij – ui . (2.3.6)
Затем оценки каждой пустой клетки определяются по формуле:
еij =сij – (ui+ vj). (2.3.7)
Как же определяются потенциалы?
Можно начать с любого столбца или строки и назначить в качестве их потенциала произвольное число. Произвольно назначается только этот первый потенциал, все остальные рассчитываются по формулам (2.3.6).
Проиллюстрируем это на примере, условия которого приведены в табл. 2.3.10 с базисным планом, полученным методом северо-западного угла.
Примем произвольно, например, для 2-й строки потенциал u2=10.
Тогда по формулам (2.3.6) можно вычислить потенциалы 2-го и 3-го столбца, а именно:
v2= с22 – u2 = 5 – 10 = –5,
v3= с23 – u2 = 7 – 10 = –3.
Таблица 2.3.10
| АiВj | ui | |||||
| 55 | 25 | |||||
| 65 | 10 | |||||
| 30 | 15 | |||||
| 15 | 20 | |||||
| vj | –4 | –5 | –3 | –2 | –1 |
Теперь, используя уже вычисленные потенциалы v2и v3,находим потенциалы 1-й и 3-й строки:
u1= с12 – v2 = 4 – (–5) = 9,
u3= с33 – v3 = 3 – (–3) = 6.
А теперь, используя уже вычисленные потенциалы u1и u3,находим потенциалы 1-го и 4-го столбца:
v1= с11 – u1 = 5 – 9 = –4,
v4= с34 – u3 = 4 – 6 = –2.
Нам осталось вычислить потенциалы 4-й строки и 5-го столбца:
u4= с44 – v4 = 5 – (–2) = 7,
v5= с45 – u4 = 6 – 7 = –1.
Зная потенциалы всех столбцов и строк по формуле (2.3.7) вычисляем оценки любой пустой клетки. В данном примере
е13 = с13 – (u1+ v3) =3 – (9 –3) = –3,
е14 = с14 – (u1+ v4) =2 – (9 –2) = –5,
е15 = с15 – (u1+ v5) =1 – (9 –1) = –7,
е21 = с21 – (u2+ v1) =3 – (10–4) = –3,
е24 = с24 – (u2+ v4) = 5 – (10–2) = –3,
е25 = с25 – (u2+ v5) = 3 – (10–1) = –6,
е31 = с31 – (u3+ v1) = 5 – (6–4) =3,
е32 = с32 – (u3+ v2) = 4 – (6–5) =3,
е35 = с35 – (u3+ v5) = 5 – (6–1) =0,
е41 = с41 – (u4+ v1) = 2 – (7–4) = –1,
е42 = с42 – (u4+ v2) = 3 – (7–5) =1,
е43 =с43 – (u4+ v3) = 4 – (7–3) =0.
Найдя отрицательную оценку, перемещаем в соответствующую клетку поставку по циклу, как и в распределительном методе.
Можно найти сначала все отрицательные оценки, а затем выбрать клетку, перемещение поставки в которую даст наибольший эффект, т.е. наибольшую величину уменьшения целевой функции. Заметим, что эта величина зависит как от значения оценки, так и от максимально допустимой поставки, которую можно дать в данную клетку. Студентам предоставляется право самостоятельно довести решение до конца. Оптимальное решение приведено в табл. 2.3.11.
Таблица 2.3.11