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