Глава 2 Транспортная задача

Упражнение 1.Получите опорный план транспортной задачи (таб. 24) тремя методами. Оптимизируйте план, полученный методом наименьших затрат.

Таблица 24

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1
А2
А3
Спрос на товар, bj

Решение.

,

.

Так как , то имеем закрытую транспортную задачу, n = 3, m = 5.

1 метод. Метод «северо-западного угла»

Таблица 25 заполняется, начиная с «северо-западного» угла, то есть с левой верхней клетки.

Дадим переменной x11 максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1; 1) – «северо-западный» угол таблицы поставок: x11 = min{200, 120} = 120. После этого спрос первого потребителя полностью удовлетворён, в результате чего первый столбец таблицы поставок исключается из дальнейшего рассмотрения (до тех пор, пока опорный план не будет составлен полностью). Заполненные клетки будем перечёркивать по диагонали сплошной линией, а исключённые из дальнейшего рассмотрения – пунктирной линией; при этом предложение первого поставщика уменьшается на 120 ед. и составит 80 ед.

Таблица 25

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           200/ 80
                 
А2          
                   
А3          
                   
Спрос на товар, bj 120/ –

Теперь в таблице поставок 26 находим новый «северо-западный» угол – клетку (1; 2) и отправляем в неё максимально возможную поставку x12 = min{80, 110} = 80 и клетка (1; 2) перечёркивается сплошной линией. После этого мощность первого поставщика полностью использована, то есть клетки (1; 3), (1; 4) и (1; 5) исключаются из рассмотрения и перечёркиваются пунктиром. В оставшейся таблице вновь находим «северо-западный» угол и отправляем туда максимально возможную поставку. И так далее.

В результате получаем опорный план, в котором заполненными (базисными) являются n + m – 1 = 5 + 3 – 1 = 7 клеток.

Таблица 26

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           200/ 80/ –
               
А2           300/ 270/ 190/ –
             
А3           200/ 190/ –
               
Спрос на товар, bj 120/ – 110/ 30/ – 80/ – 200/ 10/ – 190/ –

Этому плану соответствует значение целевой функции Fсз = 18·120+ +26·80+12·30+19·80+23·190+19·10+14·190 = 13340.

2 метод. Метод наименьших затрат

Согласно этому методу на каждом шаге заполняется клетка с минимальным коэффициентом затрат.

В таблице поставок 27 находим клетку с наименьшим коэффициентом затрат. Это клетка (2; 1) с коэффициентом затрат, равным 7 (если таких клеток несколько, то выбираем ту, в которую возможна максимальная поставка), причём x21 = min{300, 120} = 120.

Таблица 27

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1          
                   
А2           300/ 180
                 
А3          
                   
Спрос на товар, bj 120/ –

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

Таблица 28

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1          
                   
А2           300/ 180
                 
А3           200/ 90
                 
Спрос на товар, bj 120/ – 110/ –

В оставшейся таблице 28 наименьший коэффициент затрат равен 8 и находится в клетке (3; 2), x32 = min{200, 110} = 110. При этом из рассмотрения выбывает второй столбец.

Продолжая заполнение таблицы шаг за шагом (табл. 29), получаем x15 = min{200, 190} = 190, x13 = min{10, 80} = 10, x33 = min{90, 70} = 70, x34 = min{20, 180} = 20, x24 = 180. В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Таблица 29

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           200/ 10/ –
               
А2           300/ 180/ –
               
А3           200/ 90/ 20
             
Спрос на товар, bj 120/ – 110/ – 80/ 70/ – 200/ 180/ – 190/ –

Соответствующее значение целевой функции равно Fнз = 16·10+9·190+ +7·120+23·180+8·110+17·70+19·20 = 9300.

3 метод. Метод аппроксимации Фогеля

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

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

Таблица 30

  Пункты назначения ai Разности по строкам
ПО В1 В2 В3 В4 В5 I II III IV V
А1                    
                   
А2                    
                   
А3                    
                   
bj          
Разности по столбцам                      
                     
                     
                     
                     

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

Таблица 31

  Пункты назначения ai Разности по строкам
ПО В1 В2 В3 В4 В5 I II III IV V
А1           200/ 10        
                 
А2                  
                   
А3                  
                   
bj 190/ –          
Разности по столбцам            
                     
                     
                     
                     

В строке А1 минимальный коэффициент затрат равен 9, а следующий за ним равен 16, разность между ними 16 – 9 = 7. В строке А2 разность равна 12 – 7 = 5, и так далее. Вычислив все разности, видим, что наибольшая из них соответствует строке А1. В этой строке минимальный коэффициент затрат находится в клетке (1; 5) и равен 9. Отправим в эту клетку максимально возможную поставку x15 = min{200, 190} = 190. При этом потребности пятого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А1 равны 200 – 190 = 10.

Второй этап. Снова вычисляем разности между минимальными коэффициентами затрат (табл. 32) и видим, что наибольшая из них соответствует строке А2. В этой строке минимальный коэффициент затрат находится в клетке (2; 1) и равен 7. Отправим в эту клетку максимально возможную поставку x21 = min{300, 120} = 120. При этом потребности первого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А2 равны 300 – 120 = 180.

Таблица 32

  Пункты назначения ai Разности по строкам
ПО В1 В2 В3 В4 В5 I II III IV V
А1           200/ 10      
                 
А2           300/ 180      
                 
А3                
                   
bj 190/ –          
Разности по столбцам            
           
                   
                   
                   

Продолжая итерационный процесс (табл. 33), последовательно заполняем клетки (3; 2), (1; 3), (3; 4), (2; 3), (2; 4) поставками x32 = min{200, 110} = 110, x13 = = min{10, 80} = 10, x34 = min{90, 200} = 90, x23 = min{110, 70} = 70, x24 = 110.

Отметим, что на этапе V появляются строка и столбец, у которых разности максимальны. Поэтому выбирает клетку с минимальным коэффициентом затрат. В данном случае таких клеток две – (2; 3) и (3; 4). Нас интересует та, в которую можно отправить максимально возможную поставку, то есть клетка (3; 4).

Таблица 33

  Пункты назначения ai Разности по строкам
ПО В1 В2 В3 В4 В5 I II III IV V
А1           200/ 10/ –
               
А2           300/180/ 110/ –
             
А3           200/ 90/ –
               
bj 110/ – 80/ 70/ – 200/ 110/– 190/ –          
Разности по столбцам            
           
           
           
           

В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Соответствующее значение целевой функции равно FФ = 7·120+8·110+ +16·10+19·70+23·110+19·90+9·190 = 9160.

Оптимизируем план, полученный методом наименьших затрат (табл. 29), используя метод потенциалов.

Методом наименьших затрат получен опорный план:

, Fo =9300 .

Согласно методу потенциалов каждой строке i и каждому столбцу j ставятся в соответствие числа ui, vj (потенциалы). Для каждой базисной переменной xij потенциалы ui, vj удовлетворяют уравнению:

cij + ui + vj = 0.

Так как базисных переменных n + m – 1 = 7, а потенциалов n+m = 8, то присвоим одному из потенциалов произвольное значение (например, u1 = 0) и вычислим значения остальных потенциалов:

Результаты вычислений занесём в таблицу 34.

Таблица 34

ПО ПН ui
В1 В2 В3 В4 В5
А1          
               
А2           –5
               
А3           –1
             
vj –2 –7 –16 –18 –9  

Далее, используя полученные значения потенциалов, для каждой свободной переменной вычисляем оценки dij по формуле:

dij = cij + ui + vj .

Результаты заносим в матрицу оценок (dij), проставив в клетках базисных переменных прочерки:

.

Так как в матрице оценок есть отрицательный элемент d23 = – 2, то опорный план неоптимальный. Для получения нового плана необходимо свободную переменную x23 перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (2;3) цикл пересчёта.

Цикл пересчёта – это ломаная линия, вершины которой расположены в занятых клетках таблицы поставок (кроме одной, предназначенной для заполнения), а звенья – вдоль строк и столбцов, причём в каждой вершине цикла встречается лишь два звена, одно из которых находится в строке, а другое – в столбце, и в каждых строке и столбце чётное число вершин. Перемещение по циклу производится по следующим правилам:

– каждой из вершин, связанной циклом с данной свободной клеткой, приписывают определённый знак, причём свободной клетке соответствует знак «+», а далее – поочерёдно то «–», то «+»;

– в данную свободную клетку переносится меньшее из значений xij, стоящих в клетках со знаком «–», а соответствующая переменная xij становится свободной. Одновременно это число добавляется ко всем значениям xij, стоящим в клетках со знаком «+», и вычитается из всех значений xij, стоящих в клетках со знаком «–».

В данном случае цикл пересчёта и перемещение по циклу представлены в таблице 35.

Таблица 35

ПО ПН
В1 В2 В3 В4 В5
А1 18          
               
А2          
      +      
А3          
      +    

Учитывая, что min{180, 70} = 70, в свободные переменные переходит x33. В результате получаем новый план, F1 = F0 + x’23 d23 = 9300 + 70·(–2) = = 9160 (см. табл. 36).

Таблица 36

ПО ПН ui
В1 В2 В3 В4 В5
А1          
               
А2           –3
             
А3          
               
vj –4 –9 –16 –20 –9  

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции F* = 9160.

Однако в матрице оценок присутствует элемент d22 = 0, что говорит о том, что оптимальный план не единственный. Для получения нового оптимального плана необходимо свободную переменную x22 перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (2;2) цикл пересчёта в таблице 37 по сформулированным выше правилам.

Таблица 37

ПО ПН
В1 В2 В3 В4 В5
А1 18          
               
А2          
  +        
А3          
        +    

Учитывая, что min{110, 110} = 110, в свободные переменные переходит любая из переменных x32 или x24, например, x24, при этом в клетку (3;2) отправляем фиктивную поставку (табл. 38), то есть x32 = 0 (если не сделать этого, число базисных переменных станет равным шести, а не семи, как должно быть в данной задаче). В результате получаем новый план, F2 = F1 + x’22 d22 = = 9300 + 110·0 = 9160.

Таблица 38

ПО ПН ui
В1 В2 В3 В4 В5
А1          
               
А2           –3
             
А3          
               
vj –4 –9 –16 –20 –9  

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции F* = 9160.

Однако, продолжив решение, получаем предыдущий план (предлагаем убедиться самостоятельно).

 

Ответ:

, ;

F* = 9160.

 

 

Упражнение 2. Получите опорный план транспортной задачи (табл. 39) тремя методами. Оптимизируйте план, полученный методом наименьших затрат.

Таблица 39

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1
А2
А3
Спрос на товар, bj  

Решение.

,

.

Так как , то имеем закрытую транспортную задачу, n = 3, m = 5.

1 метод. Метод «северо-западного угла»

Таблица 40

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           150/ 50
                 
А2          
                   
А3          
                   
Спрос на товар, bj 100/ –

Таблица 40 заполняется, начиная с левого верхнего угла. Дадим переменной x11 максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1;1) – «северо-западный» угол таблицы поставок: x11 = min{150, 100} = 100. После этого спрос первого потребителя полностью удовлетворён, в результате чего первый столбец таблицы поставок исключается из рассмотрения; при этом предложение первого поставщика уменьшается на 100 ед.

Теперь в таблице поставок (табл. 41) находим новый «северо-западный» угол – клетку (1;2) и отправляем в неё максимально возможную поставку x12 = min{50, 70} = 70 и так далее. На четвёртом шаге максимально возможную поставку нужно отправить в клетку (2;3), при этом удовлетворяются и спрос потребителя, и мощность поставщика. Поэтому необходимо отправить фиктивную поставку в одну из незачёркнутых клеток 2-ой строки или 3-го столбца, например, в клетку (3;3), то есть x33 = 0 (если не сделать этого число базисных переменных станет равным шести, а не семи как должно быть в данной задаче).

В результате получаем опорный план, в котором заполненными (базисными) являются n + m – 1 = 5 + 3 – 1 = 7 клеток.

Этому плану соответствует значение целевой функции Fсз = 20·100+ +3·50+10·20+12·130+16·0+16·110+48·90 = 9900.

Таблица 41

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           150/ 50/ –
               
А2           150/ 130/ –
               
А3             200/ 90/ –
             
Спрос на товар, bj 100/ – 70/ 20/ – 130/ – 110/ – 90/ –

2 метод. Метод наименьших затрат

В таблице поставок (табл. 42) находим клетки с наименьшим коэффициентом затрат. Это клетка (1;2) с коэффициентом затрат, равным 3, причём x12 = min{150, 70} = 70.

Таблица 42

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           150/ 80
                 
А2          
                   
А3          
                   
Спрос на товар, bj 70/ –

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

В оставшейся таблице 43 наименьший коэффициент затрат равен 9 и находится в клетке (1;3), x13 = min{80, 130} = 80. При этом из рассмотрения выбывает первая строка.

Таблица 43

Поставщики (пункты отправки) Потребители (пункты назначения) Запасы товара, ai
В1 В2 В3 В4 В5
А1           150/ 80/ –
               
А2           150/ 100/ –
               
А3           200/ 110/ –
             
Спрос на товар, bj 100/ – 70/ – 130/ 50/ – 110/ – 90/ –

Продолжая заполнение таблицы 43 шаг за шагом, получаем x23 = = min{150,50} = 50, x21 = min{100,100} = 100, x21 = 0 (фиктивная поставка), x34 = min{200,110} = 110, x35 = 90. В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Соответствующее значение целевой функции равно Fнз = 3·70+9·80+ +14·100+12·50+25·0+16·110+48·90 = 9010.

3 метод. Метод аппроксимации Фогеля

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

Вычислив все разности, видим, что наибольшая из них соответствует столбцу В1. В этой строке минимальный коэффициент затрат находится в клетке (1;5) и равен 35. Отправим в эту клетку максимально возможную поставку x13 = min{200,90} = 90. При этом потребности пятого потребителя полностью удовлетворены, и он исключается из рассмотрения, а запасы пункта А1 равны 150 – 90 = 60.

Таблица 44

  Пункты назначения ai Разности по строкам
ПО В1 В2 В3 В4 В5 I II III IV V
А1           150/ 60        
                 
А2                  
                   
А3                  
                   
bj          
Разности по столбцам            
                     
                     
                     
                     

Продолжая итерационный процесс, последовательно заполняем клетки (1;2), (2;1), (3;2), (2;3), (3;3), (3;4) таблицы 45 поставками x12 = min{60,70} = = 60, x21 = min{150, 100} = 100, x32 = min{200, 10} = 10, x23 = min{50, 130} = = 50, x33 = min{190, 80} = 80, x34 = 110.

В результате получаем опорный план, в котором заполненными (базисными) являются 7 клеток.

Соответствующее значение целевой функции равно FФ = 3·60+35·90+ +14·100+12·50+11·10+16·80+16·110 = 8480.

Таблица 45