Транспортная задача

 

Пусть фиксировано некоторое базисное распределение поставок, при этом клетка - свободная (переменная - свободная), - оценка клетки . Найдем оценку свободной клетки,

 

Пример 5. Установить, является ли оптимальным базисное распределение поставок, найденное в табл. 5.

 

	20	110	40	110
60	1	2              60	5	3
120	1                    20	6	5	2                100
100	6	3               50	7              40	4                  10

 

 

Решение. Найдем, например, оценку свободной клетки (1,3). Для этого дадим в клетку (1,3) единичную поставку. При этом потребуется изменить поставки в заполненных клетках так, чтобы сохранился баланс по строкам и столбцам. (Будем полагать, что во   всех   свободных, клетках, отличных от клетки (1,3), поставка останется нулевой.).

 

Существенно, что найденный вариант перераспределения поставок, затрагивающий заполненные клетки и увеличивающий на 1 поставку клетки (1,3), единственный. Полученное распределение поставок представлено в табл. 10.

	20	110	40	110
60	1	2                 59	5              1	3
120	1                               20	6	5	2                100
100	6	3                        51	7                  39	4                       10

 

                                                  

 

 

 

 

 

 

 

 

 

 

 

                Табл. 9

        

 

 

       Найдем изменение суммарных затрат при указанном перераспределении поставок. Первоначально затраты на перевозку (табл. 9) составили:

 

FH = 2*60 + 1*20 + 5*0 + 3*50 + 7*40 + 2*100 + 4*10,

 

после перераспределения (табл. 10):

 

FПЕР = 2*59 + 1*20 + 5*1 + 3*51 + 7*39 + 2*100 + 4*10.

 

Определим  изменение затрат, связанных с введением единичной поставки в клетку (1,3)

 

.  (8)

 

Тогда - это относительная оценка свободной переменной , которую называют экономическим смыслом оценки свободной клетки.

Так как среди клеток табл. 9 есть клетка с отрицательной оценкой, то распределение поставок не оптимально.

Такой способ оценки оптимальности довольно громоздок (особенно учитывая, что часто в задачах приходится искать оценки всех свободных клеток заданного базисного распределения поставок). Проанализируем решение  табл.9, табл. 10 для упрощения вычислений.

При вычислении многие слагаемые из FH и FПЕР взаимно уничтожаются, не влияя на значение : существенны лишь коэффициенты затрат тех клеток, в которых поставка при рассматриваемом перераспределении изменится. При этом в выражение для некоторые из них входят со знаком "+", а некоторые - со знаком "-".

Можно сформулировать правило 1 нахождения оценки свободной клетки: для свободной клетки следует построить цикл пересчета, в вершинах этого цикла расставить последовательно чередующие знаки, начиная со знака "+" в свободной клетке, тогда значение оценки свободной клетки равно алгебраической сумме коэффициентов затрат клеток цикла, взятых с соответствующими знаками.

Ломаную, соединяющую клетки с изменяемой поставкой, будем называть означенным циклом пересчета (рис. 1).

 

Аналогично, составляя означенный цикл пересчета для каждой свободной клетки, можно найти ее оценку.

Например, означенный цикл пересчета для клетки (1,1), показанный на рис. 2, более сложный. Оценка клетки (1,1) в этом случае равна

=(1 + 3 + 2)-(2 + 1 + 4) = -1.

 

 

   Рис. 2

 

Замечание. Иногда для произвольного означенного цикла вводится понятие оценка цикла — алгебраическая сумма коэффициентов, стоящих в вершинах цикла, взятых с соответствующими знаками. Приведенные выше рассуждения показывают, что оценка цикла равна оценке той единственной свободной клетке, которая входит в данный цикл.

Для облегчения нахождения цикла пересчета в конкретных задачах дадим его точное определение.

Циклом в матрице будем называть ломаную с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющую условиям:

• ломаная должна быть связной, т.е. из любой ее вершины можно попасть в любую другую вершину по звеньям ломаной;
• в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, другое — по столбцу.

Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, остальные - в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки "+" и "-" так, что в свободной клетке стоит знак "+", а соседние вершины имеют противоположные знаки.

Для каждой свободной клетки базисного распределения поставок существует и притом единственный цикл пересчета, причем операция означивания цикла является корректной.

 

Нахождение оценок свободных клеток можно существенно упростить. Пусть коэффициенты затрат всех заполненных клеток равны нулю. Если теперь по рассмотренному правилу найти оценку свободных клеток, то окажется, что оценки свободных клеток равны их коэффициентам затрат, т.е. в этом случае значения оценок считываются с таблицы поставок и никаких циклов строить не надо.

С другой стороны, справедлива следующая теорема.

Метод потенциалов

Теорема 3. (о потенциалах). Оценка свободной клетки не изменится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число, прибавляемое к коэффициентам затрат выделенной строки (столбца), будем называть потенциалом данной строки (столбца).

Теорема 3 приводит к правилу 2 нахождения оценок свободных клеток:

к коэффициентам затрат таблицы поставок в каждой строке и столбце надо прибавить такие числа (потенциалы), чтобы коэффициенты затрат в заполненных клетках стали равными нулю. Полученные при этом коэффициенты затрат свободных клеток равны относительным оценкам этих клеток.

Пример 6. Найти оценки свободных клеток базисного распределения поставок, найденного в задаче 3.

Решение. Найдем оценки свободных клеток, следуя изложенной выше последовательности действий.  Изменение  коэффициентов затрат можно начинать с любого столбца (строки). Потенциал столбца (строки), избранного для начала, может быть произвольным, но можно доказать, что после его фиксации потенциалы остальных столбцов и строк будут определены однозначно.

Начнем с первого столбца. Пусть потенциал этого столбца равен нулю (табл. 11). Рядом с потенциалом в скобках записываем номер шага (поставки опускаем).

       Табл. 11

1	2	5	3
1	6	5	2
6	3	7	4

 

-2(7) 

 

-1(2)             

 

-3(4)

 

   0(1)  0(6)    -4(5)    -1(3)

 

После прибавления этого потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (2,1) не изменится; чтобы полученный после сложения коэффициент стал равен нулю, потенциал второй строки табл. 11 должен быть равен -1; для обнуления коэффициента затрат клетки (2,4) потенциал четвертого столбца должен быть равен -1 и т. д.

 Измененные коэффициенты затрат удобно выписать в виде отдельной матрицы оценок. Элементы матрицы оценок, соответствующие свободным клеткам таблицы поставок, равны оценкам этих свободных клеток.

Из предыдущих рассуждений вытекает, что для фиксированного базисного распределения поставок можно подобрать различные наборы потенциалов, удовлетворяющих правилу 2, однако матрица оценок во всех таких случаях будет одинаковой.

 

 

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

 

Пример 7. Найти оптимальное распределение поставок в задаче 1.

Решение. Начнем с базисного распределения поставок, полученного в задаче 3. Как было установлено ранее (см. задачу 5), данное распределение не оптимально. Оценки свободных клеток приведены в (9).

Далее поступаем так, как поступили бы при решении задачи симплекс- методом: переменную , например, коэффициент при которой отрицателен, будем переводить в базисные (основные) переменные. Переменная начинает возрастать от нуля. Как было показано в примере 3, Перевод поставки в свободную клетку вызывает перераспределение поставок (передвижение поставки по циклу). Означенный Цикл пересчета для клетки (1,3) показан на рис. 3.

 

Рис. 3

 

Подобно тому, как это было в симплекс-методе, Увеличиваем поставку в клетке (1,3) до тех пор, пока поставка в одной заполненных клеток не станет равной нулю (дальнейшее увеличение приводит в область недопустимых решений). Эта клетка принадлежит, конечно, циклу, построенному на рис. 3 для клетки (1,3).

Найдем ее. Если в клетку (1,3) передать поставку, равную , то поставка в клетках цикла со знаком "+" увеличится на z, а в клетках со знаком "-" - уменьшится на z. Поэтому искомая клетка находится среди клеток цикла, имеющих знак « - » Более того, она имеет минимальную поставку среди таких клеток. Так как min{60,40} = 40 (рис. 3), то в нашем случае - это клетка (3,3), и для обнуления поставки в этой клетке по циклу следует передать 40 единиц груза. Таким образом, поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком «-». После этого клетка (1,3) считается заполненной, а клетка (3,3) — свободной.

В клетках со знаком "+" цикла поставка увеличивается на передаваемую поставку: поставка клетки (3,2) станет равной 90 единицам, поставка клетки (1,3) - 40 единицам. Аналогично в клетках со знаком " - " поставка уменьшится на передаваемую поставку, например, поставка клетки (1,2) станет равной 20 единицам, что видно из табл. 12. Нетрудно доказать, что вновь полученное распределение поставок - базисное.

Оптимальность базисного распределения поставок.

Найдем оценки свободных клеток (матрицу оценок) распределения поставок. Для этого, как и прежде, подберем потенциалы так, чтобы коэффициенты затрат заполненных клеток стали равными нулю (табл.12). Тогда матрица оценок примет вид (10).

 

 

Табл.12

1	2           20	5            40	3
1            20	6	5	2         100
6	3            90	7	4             10

-2

 

 

-1

 

            

 

-3

 

     

    0        0               -3            -1

 

Так как среди свободных клеток есть клетка (1,1) с отрицательной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для клетки (1,1) приведен на рис. 4. По правилу, сформулированному выше, поставка, передаваемая по циклу = {20, 20, 10}= = 10. Передвигая эту поставку по циклу (рис. 4), приходим к новому распределению поставок (табл. 13).

Найдя матрицу (11) оценок этого распределения, заключаем, что оно оптимально, так как среди оценок свободных клеток нет отрицательных.

 

 

Рис. 4

 

 

       Табл. 13

1                        10	2         10	5      40	3
1            10	6	5	2               110
6	3          100	7	4