Лекция. Решение транспортной задачи (закрытая модель) (1). Решение транспортной задачи

• Название: Решение транспортной задачи
• Дата: 21.12.2021
• Размер: 50.07 Kb.
• Имя файла: Лекция. Решение транспортной задачи (закрытая модель) (1).docx
• Тип: Решение; #312468

Решение транспортной задачи.

1. 
   Составление распределительной таблицы. Проверка модели на закрытость.
   
2. 
   Составление начального опорного плана
   

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

	В1	В2	В3	ai
А1	3 800	5 -	6 -	800
А2	7 200	2 500	4 -	700
А3	4 -	3 600	5 400	1000
А4	6 -	4 -	7 500	500
bj	1000	1100	900	3000

Z=800*3+200*7+500*2+600*3+400*5+500*7=12100

2. 
   Метод минимального элемента (метод минимальных затрат)-
   

	В1	В2	В3	ai	ui
А1	3 800	5 -	6 -	800	0
А2	7 -	2 700	4 -	700
А3	4 200	3 400	5 400	1000
А4	6 -	4 -	7 500	500
bj	1000	1100	900
vj

Z=800*3+200*4+700*2+400*3+400*5+500*7=11300

3. 
   Проверка выполнения необходимого условия оптимальности:
   

Количество заполненных ячеек (нагруженных – ячейки с 2-мя числами)= m + n -1
Кол-во заполненных ячеек= 4+3-1=6 –верно.Следовательно, необходимое условие выполняется

4. 
   Достаточное условие оптимальности (метод потенциалов)
   

1. 
   

   	В1	В2	В3	ai	ui
   А1	3 800	5 -	6 -	800	0
   А2	7 -	2 700	4 -	700	0
   А3	4 200	3 400	5 400	1000	1
   А4	6 -	4 -	7 500	500	3
   bj	1000	1100	900
   vj	3	2	4

   В правую верхнюю ячейку u1 ставим 0 всегда.
   
2. 
   работаем с тарифами-верхние правые числа в заполненных ячейках
   
3. 
   s12=5-(2+0)>0
   

s13=6-(4+0)>0

s21=7-(0+3)>0

s23=4-(0+4)=0!!!!

S41=6-(3+3)=0

S42=4-(2+3)=-1 нарушено условие оптимальности (выбираем минимальное отрицательное число). Будем перегружать ячейку (4;2)

Если все sij>=0 то получен оптимальный план.

-

+

+

-

	В1	В2	В3	ai	ui
А1	3 800	5 -	6 -	800	0
А2	7 -	2 700	4 -	700	1
А3	4 200	3 -	5 800	1000	1
А4	6 -	4 400	7 100	500	3
bj	1000	1100	900
vj	3	1	4

Ячейки с минусами: выбираем минимальное нагруженное число (то, которое ставили влево вниз) min{400, 500}=400 – это число ставим в клетку (4; 2)-розовая. Остальные клетки, входящие в контур очищаем. Затем начинаем клетки, входящие в контур заполнять по правилу: сумма значений в ячейках по столбцам и строкам должна сохранять исходные значения.

Переходим к пункту 3.

S12= 5-(0+1)>0

S13=6-(0+4)>0

S21=7-(3+1)>0

S23=4-(4+1)=-1 . Следовательно перегружаем ячейку (2; 3)

S32=3-(1+1)>0

S41=6-(3+3)=0

-

+

+

-

	В1	В2	В3	ai	ui
А1	3 800	5 -	6 -	800	0
А2	7 -	2 600	4 100	700	0
А3	4 200	3 -	5 800	1000	1
А4	6 -	4 500	7 -	500	2
bj	1000	1100	900
vj	3	2	4

Выбираем минимальное из «-« ячеек: min{100, 700}=100

S12=5-(2+0)>0

S13=6-(0+4)>0

S21=7-(3+0)>0

S32=3-(2+1)=0

S41=6-(3+2)>0

S43=7-(2+4)>0

Так как все sij>=0, то получен оптимальный план
Ответ: Z_min=800*3+600*2+100*4+200*4+800*5+500*4=10800 у.е.
-матрица перевозок