Список предметов
Транспортная задача
117 / 152
Уважаемые коллеги!
 Целями данного урока является не изложение теории из курса матпрограммирования, а более простая цель - показать практическое применение знаний, которые Вы получаете в процессе изучения раздела "математическое программирование" в курсе высшей математики. Поэтому изложение будет максимально простым, но не совсем "каноническим".

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

В четырех пунктах отправления сосредоточен однородный груз в количествах A = (90;60;70;40), который необходимо доставить четырем потребителям со спросом B = (30;50;90;90), затраты на транспортировку единицы груза приведены в матрице тарифов С:
2,4,5,1
3,7,6,2
1,3,4,2
4,5,2,6
Найти оптимальное распределение поставок и минимальные транспортные затраты.

Решение.
Начальное условие сведем в таблицу:
Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
A1
90
2
 
4
 
5

1
 
A2
60
3
 
7
 
6

2

A3
70
1
 
3
 
4

2

A4
40
4
 
5
 
2

6


Для решения задачи, в отличие от универсального симплекс-метода, используем более простые, но наглядные методы решения. Первоначальный план перевозок получим методом Северо-Западного угла.  Удовлетворим потребителей, соблюдая очередность от левого верхнего угла.

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
A1
90
2
  30
4
  50
5
10
1
 
A2
60
3
 
7
 
6
60
2

A3
70
1
 
3
 
4
20
2
50
A4
40
4
 
5
 
2

6
40

Как  видно из первоначального плана, поставки равны потребностям, то есть задача является "закрытой" или сбалансированной. Оценим первоначальные затраты на перевозку:
2*30+4*50+5*10+6*60+4*20+2*50+6*40=1090

Оценим оптимальность выбранного плана с помощью метода потенциалов. Для этого введем две дополнительные колонки - alpha и beta. Принимаем первую строку равной нулю. Исходя из этого рассчитываем все остальные значения (см. таблицу).
Принцип расчета основывается на том, что beta[j] - alpha[i] = C[i,j] то есть разность значений дополнительных строки и колонки равна затратам (стоимости) перевозки. Поскольку строку 1 мы приняли равной нулю, то beta[j] - 2 = 0, откуда значение для первой колонки равно 2.

Поставщики и их ресурсы

Потребители и их спрос
 
B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2
       30
4
       50
5
       10
1
          
         0
A2
60
3
 
7
 
6
60
2

-1
A3
70
1
 
3
 
4
20
2
50
1
A4
40
4
 
5
 
2

6
40
-3
beta2453

Теперь определим потенциал каждой клетки, которая не участвовала в первоначальном плане, используя ту же самую формулу beta[j] - alpha[i] = C[i,j]. Однако, получающееся число у нас будет равно "псевдостоимости" перевозки. Вычислим значение beta[j] - alpha[i] - C[i,j]. Разность занесем в нижний левый угол клетки. Получим следующую таблицу:

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2
  30
4          
  50
5
10
1  
2 
0
A2
60
3          
0 
7    
-2 
6         
 0     60
2         
2
-1
A3
70
1      
0 
3     
0 
4     
0      20
2    
0     50
1
A4
40
4   
1 
5         
2 
2          
6
6    
0     40
-3
beta2453

Теперь выбираем опорную клетку. Наименьшее значение имеет клетка (4;3) - разница потенциалов -6.. Мы включаем ее в новый план. Соответственно, необходимо провести корректировки по столбцу и строке с другими клетками, уже находящимися в плане. Естественно, корректировка должна сохранять баланс объемов перевозок - ресурсов по строке должно быть не больше, чем их есть на складе, а по столбцу не больше, чем их необходимо в пункте назначения.

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2
  30
4          
  50
5
10
1  
2 
0
A2
60
3          
0 
7    
-2 
6         
 0        60
2         
2
-1
A3
70
1      
0 
3     
0 
4     [-20]
0         20
2   [+20]
0       50
1
A4
40
4           
1 
5           
2   
2    [+20]
6
6    [-20]
0       40
-3
beta2453

Затраты на перевозку по данному плану составят 2*30+4*50+5*10+6*60+2*20+2*70+6*20= 970. Как видно, план стал более оптимальным, по сравнению с первоначальным. Применим метод потенциалов для нового плана. Получим таблицу:

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2
  30
4          
  50
5
10
1  
 
0
A2
60
3          
 
7    
 
6         
 0        60
2         
 
-1
A3
70
1      
 
3     
 
4     
         
2   
       70
7
A4
40
4           
 
5           
   
2    
  20
6            
       20
3
beta2
4
5
9


Теперь снова определим потенциал каждой клетки, которая не участвовала в плане, используя формулу beta[j] - alpha[i] = C[i,j]. Вычислим значение beta[j] - alpha[i] - C[i,j]. Разность занесем в нижний левый угол клетки. Сразу же определяем опорную клетку. Получим следующую таблицу:

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2
  30
4          
  50
5     [-10]
10
1   [+10]
8 
0
A2
60
3          
0 
7    
-2 
6   
 0        60
2  
8 
-1
A3
70
1      
-6 
3     
-6 
4     
-6           
2   
0        70
7
A4
40
4           
-5 
5           
-4   
2    [+10]
0         20
6    [-10]
0        20
3
beta2
4
5
9


Затраты на перевозку по данному плану составят 2*30+4*50+6*60+2*30+1*10+2*70+6*10=890 . Как видно, план стал более оптимальным, по сравнению с первоначальным. Применим метод потенциалов для нового плана..
Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2
  30
4          
  50
5     
-8           
1   
          10
0
A2
60
3          
8 
7    
6 
6     [-10]
 0        60
2   [+10]
8 
-9
A3
70
1      
2 
3     
2 
4     
-6           
2   
0        70
-1
A4
40
4           
3 
5           
4   
2     [+10]
0         30
6    [-10]
0        10
 -5
beta2
4
-3
1


Затраты на перевозку по данному плану составят 2*30+4*50+6*50+2*40+1*10+2*10+2*70=810. Как видно, план стал более оптимальным, по сравнению с первоначальным. Применим метод потенциалов для нового плана.

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2    [-30]
0       30
4          
0       50
5     
0             
1   [+30]
          10
0
A2
60
3          
0
7    
-2
6    
 0        50
2  
          10
-1
A3
70
1   [+30]
2 
3     
2 
4     
2             
2    [-30]
0        70
 -1
A4
40
4           
-5 
5           
-4  
2     
0         40
6    
-8          
3
beta2
4
5
1


Затраты на перевозку по данному плану составят 1*30+4*50+6*50+2*40+1*40+2*10+2*40=750. Применим метод потенциалов для следующего плана.

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2   
-2            
4      [-40]
0         50
5     
0             
1    [+40]
0        40
0
A2
60
3          
-2 
7    
-2 
6    
 0        50
2  
0        10
-1
A3
70
1   
0        30
3     [+40]
2 
4     
2             
2     [-40]
0        40
-1
A4
40
4           
-7 
5           
-4  
2     
0         40
6    
-8          
3
beta0
4
5
1


Затраты на перевозку по данному плану составят 1*30+4*10+3*40+6*50+2*40+1*80+2*10=670. Применим метод потенциалов для следующего плана.

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2    [+10]
2            
4      [-10]
0         10
5     
0             
1    
0        80
0
A2
60
3          
0 
7    
-2
6    
 0        50
2  
0        10
-1
A3
70
1    [-10]
0        30
3     [+10]
0          40
4     
0             
2    
0            
1
A4
40
4           
-5
5           
-4  
2     
0         40
6    
-8          
3
beta2
4
5
1


Затраты на перевозку по данному плану составят 2*10+1*20+3*50+6*50+2*40+1*80+2*10=670. Применим метод потенциалов для следующего плана.

Поставщики и их ресурсы

Потребители и их спрос

B1
30
B2
50
B3
90
B4
90
alpha
A1
90
2    
0         10
4      
0              
5     
0             
1    
0        80
0
A2
60
3          
0 
7    
-2
6    
 0        50
2  
0        10
-1
A3
70
1   
0         20
3     
0          50
4     
0             
2    
-2           
1
A4
40
4           
-5 
5           
-4 
2     
0         40
6    
-8           
3
beta2
4
5
1


Поскольку все вычисленные относительные потенциалы больше нуля (разница потенциалов отрицательная), то план является оптимальным.
Ответ:
10,0,0,80
0,0,50,10
20,50,0,0
0,0,40,0.
Затраты на перевозки 670.
0  


 Математическое программирование | Описание курса | Оптимальный план производства (линейное программирование)