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

 

             

 

 

      

 

 

 

 

 

Суммарные затраты на перевозку согласно этого распределения поставок в денежных единицах составляют:

Fmin = 1*10 +2*10 +5*40+1*10 +2*110 + 3*100 = 760.

 

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

Замечание 1. Поставка, передаваемая по циклу, не может быть ни меньше, ни больше минимума поставок клеток цикла со знаком " - ". Действительно, в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а потому общее число заполненных клеток таблицы будет равно и, следовательно, распределение не будет базисным. Во втором случае уходим в область недопустимых решений.

Замечание 2. Оптимальное распределение поставок, найденное в задаче 7 (табл.13), не единственное, так как среди оценок свободных клеток есть нулевые, например клетка (2,3) в матрице (11).

Замечание 3. В некоторых случаях требуется определить изменение затрат на перевозку (экономию затрат) для некоторого i-го шага решения (или для каждого из шагов) транспортной задачи.

Из экономического смысла оценки свободной клетки следует, что экономия затрат , достигнутая на некотором i-м шаге, равна произведению оценки клетки, в которую передается поставка, на передаваемую поставку. Например, при переходе от исходного распределения поставок (табл. 11) к распределению поставок по табл. 12 поставка в 40 единиц передается в клетку, оценка которой равна -1. Тогда экономия затрат на первом шаге задачи 7 составит

.

 

Последовательность действий по решению произвольной закрытой транспортной задачи теперь может быть изложена в виде следующего алгоритма.

1. Для данного базисного распределения поставок подбираем потенциалы строк и столбцов таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю. Составляем матрицу оценок.
2. Если оценки всех свободных клеток неотрицательны, то найденное распределение оптимально — решение закончено. Если среди оценок свободных клеток есть отрицательные, то выбираем одну из них для передачи в нее поставки (для определенности можно брать, например, одну из клеток с наименьшей оценкой).
3. Для избранной свободной. клетки строится означенный цикл пересчета. Поставка z, передаваемая по циклу, определяется как минимум среди поставок в клетках со знаком " - ". Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на z, а в клетках со знаком " - " уменьшается на z. Клетка, поставка в которой при этом станет равной нулю, будет считаться свободной (далее рассмотрен случай, когда таких клеток несколько), остальные клетки цикла — заполненными. Таким образом, получено новое базисное распределение поставок.
4. Переходим к п. 1 алгоритма.

 

 

 

 

 

 

 

 

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

1. В некоторых случаях поставка, переводимая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка цикла со знаком "-" содержала нулевую поставку. В этом случае по циклу передается нулевая поставка. В результате та свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой — свободной.
2. Если при переводе поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной из них следует считать только одну (любую), остальные клетки, поставка в которых стала равной нулю, следует считать заполненными нулевой поставкой. Разберем перечисленные особые случаи на примере.

Пример 8. Завершить решение транспортной задачи из примера 4.

 

Решение. Установим сначала, оптимально ли распределение поставок, полученное в указанном примере методом "северо-западного" угла (табл. 8). Подберем потенциалы строк и столбцов этой таблицы поставок так, чтобы коэффициенты затрат  заполненных клеток стали равны нулю (табл. 14).

 

     Табл. 14

1               20	3                  10	3
3	3                    0	2               30
4	1	2               10

0

 

0 

 

0

 

    -1       -3       -2

 

Это приводит к матрице оценок (12). Так как среди свободных клеток таблицы есть клетка (3,2) с отрицательной оценкой, то данное базисное распределение поставок не оптимально. Переведем поставку в клетку (3,2) с отрицательной оценкой. Строя для клетки (3,2) означенный цикл пересчета (рис. 5), находим, что объем передаваемой поставки в данном случае равен х32 =min{0,10}= 0. Передавая по построенному циклу нулевую поставку, приходим к новому базисному распределению (табл. 15).

 

Рис. 5

 

 

     Табл. 15

1               20	3                  10	3
3	3                    0	2               30
4	1                    0	2               10

-2

 

 0 

 

 0

 

   1      -1        -2

 

Подбирая потенциалы к строкам и столбцам табл. 15, находим матрицу (13) оценок данного распределения. Так как среди свободных клеток таблицы есть клетка (1,3) с отрицательной оценкой, то данное базисное распределение не оптимально. Найдем новое базисное распределение, передавая поставку в клетку (1,3) с отрицательной оценкой. Построим цикл для клетки (1,3), показанный на рис. 6.

Поставка, передаваемая в клетку (1,3): При передаче по циклу (рис. 6) 10 единиц груза станут равными нулю поставки в клетках (1,2) и (3,3). Полагаем, что только одна из них стала свободной, например клетка (3,3), а клетка (1,2) заполнена нулевой поставкой. Таким образом, будет получено базисное распределение поставок, представленное в табл. 16.

 

Рис. 6

 

 

     Табл. 16

1               20	3                  0	3               10
3	3                    0	2               30
4	1                  10	2               0

-1

 

0 

 

 1

 

   0      -2        -2

 

Определяя матрицу оценок (14), видим, что среди оценок свободных клеток найденного распределения нет отрицательных, т.е. найденное распределение (табл. 16) оптимально.

 

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

 

Открытая транспортная задача решается сведением ее к закрытой транспортной задаче.

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

    Табл. 17        Табл. 18

 

	45	35	55	65				45		35		55		65
40	4	1	2	5		40		4		1		2		5
60	3	2	3	7		60		3		2		3		7
90	4	4	5	2		90		4		4		5		2
							10		0		0		0		0

 

Решение. В данном случае суммарный спрос потребителей больше, чем суммарное предложение поставщиков (45+35+55+ +65 = 200 > 40+60+90 = 190). Введем "фиктивного поставщика" и в таблицу поставок добавим дополнительную строку (табл. 18) так, чтобы задача стала закрытой. Для этого мощность фиктивного поставщика следует принять равной 10 = 200—190. Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например, нулю, как в табл. 18). Согласно теореме 3, конкретное значение этого числа не влияет на оптимальное распределение поставок.

Первоначальное распределение поставок для сформулированной закрытой транспортной задачи найдем, например, по методу наименьших затрат. Для удобства укажем последовательность заполнения таблицы поставок: . В результате приходим к следующему базисному распределению поставок    (табл. 19).

   Табл.19

4	1                 35	2              5	5
3                10	2	3                 50	7
4              35	4	5	2              55
0	0	0	0                    10

-2

 

-3

 

-4

 

-2

 

         0        1    0  2 

 

Установим, оптимально ли это распределение - найдем для него матрицу оценок (15). Так как среди оценок свободных клеток есть отрицательные, то найденное распределение не оптимально. Переведем поставку в одну из клеток с наименьшей отрицательной оценкой, например в клетку (4,3). Цикл для этой клетки изображен на рис 7. Поставка, передаваемая по циклу, равна                  х43 = min {50, 35, 10} = 10. Передвигая по циклу поставку, равную 10 единицам, приходим к следующему распределению поставок (табл. 20).

Найдем оценки свободных клеток данного распределения (20). Так как оценки всех свободных клеток неотрицательны, то распределение поставок табл. 20 оптимальное.

 

Рис. 7  

 

 

 Табл. 20

4	1                 35	2                5	5
3                20	2	3                   40	7
4              25	4	5	2              65
0	0	0             10	0

 

 

 

 

 

 

 

 

         В случае, когда суммарная мощность поставщиков больше суммарной мощности потребителей, в рассмотрение вводится "фиктивный потребитель", а к таблице поставок присоединяется дополнительный столбец. Коэффициенты затрат этого добавленного столбца соответствуют затратам на хранение неотправленного груза (поставки последнего столбца – неотправленный груз для каждого из поставщиков). Если информация об этих затратах отсутствует, то их принимают равными какому-либо значению (например, нулю).