Распределительный метод решения транспортной задачи.
Рассмотрим сейчас так называемый распределительный метод решения транспортной задачи. Этот метод довольно сложен и неудобен для решения практических задач, однако мы его подробно рассмотрим, т.к. этот метод позволяет понять основные идеи, лежащие в основе решения задач линейного программирования и, в частности, транспортных задач.
Вернемся к нашему примеру и возьмем базисный план, построенный методом северо-западного угла (табл. 2.3.3). Соответствующие данному плану суммарные транспортные затраты (значение целевой функции)F=750. Чтобы определить, является ли полученный план оптимальным, необходимо «оценить» различные варианты, связанные с неиспользованием клеток, в которых нет поставок (выделенных чисел). Таких клеток в нашем примере четыре. Посмотрим, что произойдет с таблицей, если дать единичную поставку в одну из пустых клеток, например в (2,1).
Чтобы не нарушался баланс по строкам и столбцам необходимо уменьшить на единицу поставку в клетки (2,2) и (1,1). Уменьшив поставку в (1,1) мы должны увеличить на единицу поставку в клетку (1,2). Заметим, что последнее изменение восстановило баланс по столбцу 2, нарушенный уменьшением поставки в клетку (2,2). Мы получили новый допустимый план поставок (см. табл. 2.3.5).
2 | 1 | 5 | |
3 | 4 | ||
4 | 15 | 6 |
Таблица 2.3.5
Заметим, что число ненулевых поставок (выделенных чисел) здесь превышает m+n–1, т.е. этот допустимый план не является базисным.
Перераспределяя поставки мы прошли по четырем клеткам. Путь нашего движения образовал так называемый цикл (цепь, контур). Представим этот цикл на рис. 2.3.1. На нем изображены клетки, в которых будем менять поставки (слева от каждой клетки написан в скобках ее номер).
При этом знаком “+” помечены те клетки, поставка в которых увеличится (положительные вершины). Знаком “–“ отмечены клетки, в которых поставка уменьшится (отрицательные вершины).
(1,1) 2 – (1,2) 1 +
40 10
(2,1) 3 + (2,2) 4 –
Рис. 2.3.1
Для циклов в транспортной задаче характерны следующие особенности:
а) цикл является замкнутым многоугольником;
б) вершинами цикла являются клетки таблицы, причем одна из вершин – пустая клетка, а все остальные – клетки с поставками базисного плана (с выделенными числами);
в) все углы цикла прямые и каждый отрезок цикла, ограниченный двумя вершинами, целиком принадлежит к одному столбцу или к одной строке таблицы;
г) в цикле четное число вершин;
д) отрезки цикла могут проходить заполненные поставками клетки, не являющиеся вершинами данного цикла;
е) в цикле одинаковое количество положительных и отрицательных вершин.
Цикл, сохраняя все перечисленные свойства, может иметь самую различную форму, но всегда для любой пустой клетки цикл пересчета существует, причем единственный (доказательство этого утверждения опускаем).
Введем теперь понятие оценки пустой клетки. Так же как и в общей задаче линейного программирования поставим вопрос следующим образом: на сколько изменится значение целевой функции, после совершения единичной поставки в рассматриваемую пустую клетку?
Рассмотрим табл. 2.3.5. Записав единичную поставку в клетку (2.1), мы увеличили целевую функцию на 3 (с21=3). Уменьшив поставку в клетку (1,1) на единицу, мы уменьшили значение целевой функции на 2 (с11=2). Увеличив поставку в клетку (1.2), мы увеличили целевую функцию на 1 (с12=1). И, наконец, уменьшив поставку в клетку (2,2) на единицу, мы уменьшили значение целевой функции на 4 (с22=4). В итоге целевая функция изменилась на 3–2+1–4= –2 (т.е. уменьшилась на 2). Эту величину и будем называть оценкой пустой клетки (i,j) и обозначать еij. Отметим, что оценка может быть как отрицательная, так и положительная.
Только что мы вычислили е21 = –2. Значит каждая единичная поставка в клетку (2,1) будет уменьшать значение целевой функции на 2. Чем больше будет величина поставки в клетку (2,1), тем лучше будет план поставок. Очевидно, наибольшее значение поставки в клетке (2,1) будет равно величине меньшей из поставок в отрицательных вершинах цикла. В противном случае в одной из этих вершин появится отрицательная поставка, что противоречит условиям задачи.
Наибольшее значение х21 в данном случае равно 40 (перепоставка из отрицательной вершины (1,1)). Принимая х21 = 40, для сохранения баланса по строкам и столбцам корректируем на эту величину поставки в остальных вершинах цикла:
х11 = 0, х12 = 50, х22 = 20.
Получим новый базисный план.
Транспортные издержки этого плана (см. табл. 2.3.6) изменились на е21х21= –2´40 = –80, т.е. уменьшились на 80.
Суммарные транспортные затраты для данного распределения можно посчитать и по общей формуле:
F = 1´50 +3´40 +4´20 +6´15 +6´55=670.
Мы видим, что и по общей формуле расчета суммарные транспортные затраты уменьшились на 750 – 670 = 80 единиц.
Таблица 2.3.6
2 | 1 | 5 | |
3 | 4 | ||
4 | 15 | 6 |
Итак, базисный план находить мы умеем (метод северо-западного угла или метод наименьших затрат). Научились определять оценки пустых клеток с помощью циклов и перераспределять по цепи поставки. Этого достаточно, чтобы решить транспортную задачу. Общий ход решения таков:
1. Находим исходный базисный план.
2. Для пустых клеток определяем оценкиеij, пока не найдем клетку с отрицательной оценкой.
3. В эту клетку записываем максимально возможную поставку, производя необходимую корректировку поставок в вершинах соответствующего цикла. В результате получаем новый базисный план, лучший, чем предыдущий.
4. Для нового базисного плана выполняем опять процедуру 2.
Если все оценки еij ³ 0, то план поставок улучшить невозможно (суммарные транспортные издержки не уменьшаются), значит, полученный на последнем шаге план поставок оптимальный.
Если существует хотя бы одна клетка с отрицательной оценкой – переходим к процедуре 3. Будем придерживаться этого общего алгоритма решения для улучшения нашего нового базисного плана.
Определим оценку клетки (1,3) с помощью цикла (рис. 2.3.2).
(1,2) 1 – (1,3) 5 +
50
е13 =5 –1 + 6 – 6 = +4
(3,2) 6 + (3,3) 6 –
15 55
Рис. 2.3.2
Значит, давать поставку в клетку (1,3) невыгодно – приращение целевой функции положительное, т.е. это приведет к удорожанию плана перевозок. Определим оценку следующей пустой клетки (2,3) с помощью цикла (рис. 2.3.3).
(2,2) 4 – (2,3) 3 +
20
е23 =3 – 4 + 6 – 6 = –1
(3,2) 6 + (3,3) 6 –
15 55
Рис. 2.3.3
Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать поставку (максимально возможную) в клетку (2,3). Очевидно, максимально возможная величина поставки х23 = 20, что изменит значение целевой функции на –1´20 = –20. Скорректировав соответственно поставки х22=0, х32 =35, х33 =35,получаем новый базисный план (табл. 2.3.7).
Таблица 2.3.7
2 | 1 | 5 | |
3 | 4 | ||
4 | 35 | 6 |
Суммарные транспортные затраты для данного распределения:
F = 1´50 +3´40 +3´20 +6´35 +6´35=650.
Проверим этот план на оптимальность. Для этого нужно узнать, нет ли отрицательных оценок пустых клеток.
Рассмотрим клетку (3,1). Цикл для нее изображен на рис. 2.3.4. Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать максимально возможную поставку в эту клетку х31= 35. Целевая функция должна уменьшиться на 2´35 = 70.
(2,1) 3 – (2,3) 3 +
40 20
е31 =4 –3 +3 – 6 = –2
(3,1) 4 + (3,3) 6 –
Рис. 2.3.4
Скорректировав соответственно в вершинах цикла поставки х21=5, х23 =55, х33 =0,получаем новый базисный план (табл. 2.3.8).
Таблица 2.3.8
2 | 1 | 5 | |
3 | 4 | ||
4 | 35 | 6 |
Суммарные транспортные затраты для данного распределения:
F = 1´50 +3´5 +3´55 +4´35 +6´35=580,
т.е., как мы и предполагали, уменьшились на 650 – 580 = 70.
Проверим теперь этот план на оптимальность. Для этого опять вычисляем оценки пустых клеток. Рассмотрим клетку (1,1). Цикл для нее изображен на рис. 2.3.5.
(1,1) 2 + (1,2) 1 –
50
е11 = +2 –1 +6 –4=+3
(3,1) 4 – (3,2) 6 +
35 35
Рис. 2.3.5
Рассмотрим клетку (2,2). Цикл для нее изображен на рис. 2.3.6.
(2,1) 3 – (2,2) 4 +
5
е22= +4 –6 +4 –3= –1
(3,1) 4 + (3,2) 6 –
35 35
Рис. 2.3.6
Значит, и этот план не оптимальный. Его можно улучшить, если дать максимально возможную поставку в эту клетку: х22 = 5. Целевая функция уменьшается на 1´5 = 5. Скорректировав соответственно в вершинах цикла поставки х21 =0, х31 =40, х32 =30,получаем новый базисный план (табл. 2.3.9).
Суммарные транспортные затраты составят:
F = 1´50 + 4´5 +3´55 +4´40 +6´30=575,
что как раз на 5 единиц меньше предыдущего значения целевой функции. Этот план оптимальный, оценки всех пустых клеток (е11,е13,е21,е32) неотрицательны!
Таблица 2.3.9
2 | 1 | 5 | |
3 | 4 | ||
4 | 30 | 6 |
Студентам предоставляется возможность самим убедиться, что этот план оптимальный.
Основным недостатком распределительного метода является необходимость построения циклов с целью определения оценок клеток. Так, при таблице 25 строк на 25 столбцов на каждом шаге для проверки оптимальности плана надо строить m´n – (m+n–1) = 25´25 – (25+25–1) = 576 циклов. В некоторых случаях циклы имеют множество вершин и довольно сложную конфигурацию.
Метод потенциалов.
Рассмотрим модифицированный способ, позволяющий определять оценки клеток без построения циклов. Этот способ имеет свои разновидности. Мы рассмотрим одну из них, предложенную Дж.Данцигом в 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
АiВj | |||||
50 | 30 | ||||
55 | 0 | 20 | |||
5 | 40 | ||||
35 |
Дата добавления: 2020-10-25; просмотров: 447;