Распределительный метод решения транспортной задачи.

<20 21 222324 25 26 >

Рассмотрим сейчас так называемый распределительный метод решения транспортной задачи. Этот метод довольно сложен и неудобен для решения практических задач, однако мы его подробно рассмотрим, т.к. этот метод позволяет понять основные идеи, лежащие в основе решения задач линейного программирования и, в частности, транспортных задач.

Вернемся к нашему примеру и возьмем базисный план, построенный методом северо-западного угла (табл. 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 (с₂₁=3). Уменьшив поставку в клетку (1,1) на единицу, мы уменьшили значение целевой функции на 2 (с₁₁=2). Увеличив поставку в клетку (1.2), мы увеличили целевую функцию на 1 (с₁₂=1). И, наконец, уменьшив поставку в клетку (2,2) на единицу, мы уменьшили значение целевой функции на 4 (с₂₂=4). В итоге целевая функция изменилась на 3–2+1–4= –2 (т.е. уменьшилась на 2). Эту величину и будем называть оценкой пустой клетки (i,j) и обозначать е_ij. Отметим, что оценка может быть как отрицательная, так и положительная.

Только что мы вычислили е₂₁ = –2. Значит каждая единичная поставка в клетку (2,1) будет уменьшать значение целевой функции на 2. Чем больше будет величина поставки в клетку (2,1), тем лучше будет план поставок. Очевидно, наибольшее значение поставки в клетке (2,1) будет равно величине меньшей из поставок в отрицательных вершинах цикла. В противном случае в одной из этих вершин появится отрицательная поставка, что противоречит условиям задачи.

Наибольшее значение х₂₁в данном случае равно 40 (перепоставка из отрицательной вершины (1,1)). Принимая х₂₁= 40, для сохранения баланса по строкам и столбцам корректируем на эту величину поставки в остальных вершинах цикла:

х₁₁ = 0, х₁₂ = 50, х₂₂= 20.

Получим новый базисный план.

Транспортные издержки этого плана (см. табл. 2.3.6) изменились на е₂₁х₂₁= –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

е₁₃ =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 +

е₂₃ =3 – 4 + 6 – 6 = –1

(3,2) 6 + (3,3) 6 –

15 55

Рис. 2.3.3

Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать поставку (максимально возможную) в клетку (2,3). Очевидно, максимально возможная величина поставки х₂₃= 20, что изменит значение целевой функции на –1´20 = –20. Скорректировав соответственно поставки х₂₂=0, х₃₂ =35, х₃₃=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. Следовательно, рассматриваемый план не оптимален и может быть улучшен, если дать максимально возможную поставку в эту клетку х₃₁= 35. Целевая функция должна уменьшиться на 2´35 = 70.

(2,1) 3 – (2,3) 3 +

40 20

е₃₁ =4 –3 +3 – 6 = –2

(3,1) 4 + (3,3) 6 –

Рис. 2.3.4

Скорректировав соответственно в вершинах цикла поставки х₂₁=5, х₂₃ =55, х₃₃=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

е₁₁= +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 +

е₂₂= +4 –6 +4 –3= –1

(3,1) 4 + (3,2) 6 –

35 35

Рис. 2.3.6

Значит, и этот план не оптимальный. Его можно улучшить, если дать максимально возможную поставку в эту клетку: х₂₂= 5. Целевая функция уменьшается на 1´5 = 5. Скорректировав соответственно в вершинах цикла поставки х₂₁=0, х₃₁ =40, х₃₂=30,получаем новый базисный план (табл. 2.3.9).

Суммарные транспортные затраты составят:

F = 1´50 + 4´5 +3´55 +4´40 +6´30=575,

что как раз на 5 единиц меньше предыдущего значения целевой функции. Этот план оптимальный, оценки всех пустых клеток (е₁₁,е₁₃,е₂₁,е₃₂) неотрицательны!

Таблица 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-й строки обозначим 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						u_i
	55	25
		65	10
			30	15
				15	20
v_j	–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