Транспортная задача
План не оптимален. Наиболее потенциальной является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла. План не оптимален. Наиболее потенциальной является клетка (2,4). Для нее «невязка» равна -12. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла. План не оптимален… Читать ещё >
Транспортная задача (реферат, курсовая, диплом, контрольная)
Транспортная задача Вар 3
Никита Пазенко
Потребителей 5, Поставщиков 4
Проверим ТЗ на замкнутость: .
т. е. задача замкнутого типа.
Решением ТЗ будет служить минимальное значение целевой функции и значения xij
B1=15 | B2=15 | B3=16 | B4=15 | B5=15 | U | ||
A1=19 | 17 ; | 12 + | U1=0 | ||||
A2=19 | 1 + | 9 ; | U2=-16 | ||||
A3=19 | U3= -1 | ||||||
A4=19 | U4= -2 | ||||||
V | V1=21 | V2=17 | V3=25 | V4=7 | V5=9 | ||
L1 = 21*15+4*17+11+72+24*8+66+20+7*15=315+68+11++72+192+86+105=849
Итерация 1
u1= 0
v1= 21
v2= 17
v3=25
u2= - 16
v4= 7
u3= - 1
u4= - 2
Проверим план на оптимальность.
Признак оптимальности: sij= cij -(ui+vj)? 0 opt, для всех i, j.
Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:
S13= -13
S14= 17
S15= 21
S21= 1
S24= 14
S25= 16
S31= 27
S32= - 11
S35= 5
S41= 10
S42= 7
S43= - 2
План не оптимален. Наиболее потенциальной является клетка (1,3). Для нее «невязка» равна -13. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (1,3), построим граф и запишем цикл.
13−23−22−12
+ - + ;
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (1, 2) с грузом 4.
Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15 | B2=15 | B3=16 | B4=15 | B5=15 | U | ||
A1=19 | 21 ; | 12 + | U1=0 | ||||
A2=19 | U2=-3 | ||||||
A3=19 | 7 + | 24 ; | U3=12 | ||||
A4=19 | U4=11 | ||||||
V | V1=21 | V2=4 | V3=12 | V4= -6 | V5=-4 | ||
L2=315+48+15+36+192+66+20+105=797 | |||||||
Итерация 2
u1= 0
v1= 21
v2= 4
v3=12
u2= - 3
v4= - 6
u3= 12
u4= 11
Проверим план на оптимальность.
Признак оптимальности: sij= cij -(ui+vj)? 0 opt, для всех i, j.
Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:
S12= 13
S14= 30
S15= 34
S21= -12
S24= 14
S25= 16
S31= - 27
S32= - 11
S35= 5
S41= -3
S42= 7
S43= -2
План не оптимален. Наиболее потенциальной является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (3,1), построим граф и запишем цикл.
31−11−13−33
+ - + ;
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (3,3) с грузом 8.
Перемещаем по циклу груз величиной в 8 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15 | B2=15 | B3=16 | B4=15 | B5=15 | U | ||
A1=19 | 21 ; | 12+ | U1=0 | ||||
A2=19 | 9; | 5 + | U2= -3 | ||||
A3=19 | 7 + | 6 ; | U3=-14 | ||||
A4=19 | U4=- 15 | ||||||
V | V1=21 | V2=4 | V3=12 | V4= 20 | V5=22 | ||
L3=147+144+15+36+56+66+20+105=589
Итерация 3
u1= 0
v1= 21
v2= 4
v3=12
u2= -3
v4= 20
u3= - 14
u4= - 15
Проверим план на оптимальность.
Признак оптимальности: sij= cij -(ui+vj)? 0 opt, для всех i, j.
Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:
S12= 13
S14= 4
S15= 8
S21=- 12
S24= - 12
S25= - 10
S32= 15
S33= 26
S35=5
S41= 23
S42= 33
S43= 24
План не оптимален. Наиболее потенциальной является клетка (2,4). Для нее «невязка» равна -12. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (2,4), построим граф и запишем цикл.
24−34−31−11−13−23
+ - + - + ;
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (2,3) с грузом 4.
Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15 | B2=15 | B3=16 | B4=15 | B5=15 | U | ||
A1=19 | U1=0 | ||||||
A2=19 | U2= - 15 | ||||||
A3=19 | U3=- 14 | ||||||
A4=19 | U4=- 15 | ||||||
V | V1=21 | V2=16 | V3=12 | V4=20 | V5= 22 | ||
транспортный задача перевозка цикл
L4=63+192+15+20+84+42+20+105=541
Итерация 3
u1= 0
v1= 21
v2=16
v3=12
u2= - 15
v4= 20
u3= - 14
u4= - 15
v5= 22
Проверим план на оптимальность.
Признак оптимальности: sij= cij -(ui+vj)? 0 opt, для всех i, j.
Определим значения оценок sij= cij — (ui+vj)? 0 для всех свободных клеток:
S12= 1
S14= 4
S15= 8
S21= 0
S23= 12
S25= 2
S32= 3
S33= 26
S35= 5
S41=23
S42= 21
S43= 24
Ответ: L=541
X11=3
X13=16
X22=15
X24=4
X31=12
X34=7
X44=4
X45=15