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

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

Вернемся к нашему примеру и возьмем базисный план, построенный методом северо-западного угла (табл. 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 +

20

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

5

е₂₂= +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 циклов. В некоторых случаях циклы имеют множество вершин и довольно сложную конфигурацию.