Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов. Этот способ имеет свои разновидности. Мы рассмотрим одну из них, предложенную Дж.Данцигом в 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) Как же определяются потенциалы?
133 Можно начать с любого столбца или строки и назначить в качестве их потенциала произвольное число. Произвольно назначается только этот первый потенциал, все остальные рассчитываются по формулам (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 55 90 40 30 20 u i 80 5
55 4
25 3 2 1 9 75 3 5
65 7
10 5 3 10 45 5 4 3
30 4
15 5 6 35 2 3 4 5
15 6
20 7 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) вычисляем оценки любой пустой клетки. В данном примере
е 43 = с43 – (u4+ v3) = 4 – (7–3) =0. Найдя отрицательную оценку, перемещаем в соответствующую клетку поставку по циклу, как и в распределительном методе. Можно найти сначала все отрицательные оценки, а затем выбрать клетку, перемещение поставки в которую даст наибольший эффект, т.е. наибольшую величину уменьшения целевой функции. Заметим, что эта величина зависит как от значения оценки, так и от максимально допустимой поставки, которую можно дать в данную клетку. Студентам предоставляется право самостоятельно довести решение до конца. Оптимальное решение приведено в табл. 2.3.11. Таблица 2.3.11 Аi Вj 55 90 40 30 20 80 5
4
50 3 2
30 1 75 3
55 5
0 7
5 3
20 45 5 4
5 3
40 4
5 35 2 3
35 4 5
6
2.3.5. Вырожденные случаи. Открытая транспортная задача. Некоторые замечания по частным случаям, которые могут встретиться при решении. 1. Если на некотором шаге построения базисного плана из рассмотрения выпадают одновременно и строка и столбец (случай вырождения ), можно использовать следующий прием: дать нулевую (фиктивную) поставку в произвольную еще не занятую клетку данной строки или столбца. (Тем самым сохраняется число занятых клеток m+n–1 для базисного распределения поставок). 2. Если в отрицательных вершинах цикла, по которому перераспределяется поставка, две или более минимальных поставок, то все они при перераспределении обратятся в нуль. Так как на каждом шаге число занятых клеток сохраняется в количестве m+n–1, то из этих
135 “нулевых” клеток образуется только одна пустая клетка, а остальные считаются заполненными поставкой равной 0. 3. Если мы нашли клетку с отрицательной оценкой и построили соответствующий цикл перераспределения, в одной из отрицательных вершин которого находится нулевая поставка, то следует переместить эту нулевую поставку (значение целевой функции при этом не изменится), а затем вновь определять оценки пустых клеток в полученном базисном плане. Рассмотрим некоторые моменты, имеющие практическое значение, но усложняющие постановку транспортной задачи: 1. Обязательные поставки. Независимо от оптимальных расчетов некоторому поставщику вменяется определенный объем поставки некоторому потребителю (например, определенная марка бетона производится только на таком- то заводе, а некоторому потребителю необходимо определенное количество данной марки). В этом случае на величину обязательных поставок корректируются мощности и потребности, и после этого решается задача. 2. Ограничения пропускной способности. Ранее мы исходили из того, что от любого поставщика любому потребителю можно перевозить любое количество продукта (в пределах мощности и спроса). В реальных задачах часто приходится учитывать пропускную способность коммуникаций (особенно железных дорог). Самый простой способ учитывать пропускную способность состоит в следующем: Пусть поставка в клетку (i,j) ограничена числом, строго меньшим Вj. Столбец j, соответствующий потребителю с ограниченной пропускной способностью, разбивается на два столбца, в одном спрос принимается равным ограничению, а в другом – остатку. Показатели транспортных затрат одинаковы для этих двух столбцов за исключением клетки (i,j) в столбце, где спрос равен разности (остатку). Здесь сij принимается очень большим, блокирующим какую-либо поставку в эту клетку. До сих пор мы рассматривали закрытую транспортную задачу, т.е. при условии баланса спроса и объемов производства (мощностей). В практических задачах это условие далеко не всегда выполняется. При нарушении баланса возникает открытая транспортная задача, которая решается сведением ее к закрытой транспортной задаче. При превышении суммарной мощности над суммарным спросом на величину Δ вводится дополнительный столбец так называемого
136 фиктивного потребителя со спросом равным Δ. Показатели сin+1 (i=1,2,…,m) в этом столбце выбираются произвольно, но с одним условием, что все они равны между собой. Удобнее всего принимать их равными 0. Далее задача решается как закрытая. Аналогично, при превышении суммарного спроса над суммарной мощностью на величину Δ вводится дополнительная строка так называемого фиктивного поставщика с мощностью равной Δ и с нулевыми транспортными издержками.
Ви переглядаєте статтю (реферат): «Метод потенциалов» з дисципліни «Математична економіка»
