- 1
- 2
Транспортная задача
Вар 3 Никита Пазенко
15 | 15 | 16 | 15 | 15 | |
19 | 21 | 17 | 12 | 24 | 30 |
19 | 6 | 1 | 9 | 5 | 9 |
19 | 7 | 5 | 24 | 6 | 13 |
19 | 29 | 22 | 21 | 5 | 7 |
Потребителей 5, Поставщиков 4
Проверим ТЗ на замкнутость: .
, т.е. задача замкнутого типа.
Решением ТЗ будет служить минимальное значение целевой функции и значения xij
B1=15 | B2=15 | B3=16 | B4=15 | B5=15 | U | |
A1=19 | 21 15 | 17 - 4 | 12 + | 24 | 30 | U1=0 |
A2=19 | 6 | 1 + 11 | 9 - 8 | 5 | 9 | U2=-16 |
A3=19 | 7 | 5 | 24 8 | 6 11 | 13 | U3= -1 |
A4=19 | 29 | 22 | 21 | 5 4 | 7 15 | U4= -2 |
V | V1=21 | V2=17 | V3=25 | V4=7 | V5=9 |
1 = 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= 17= 21= 1= 14= 16= 27= - 11= 5= 1042= 7
S43= - 2
План не оптимален. Наиболее потенциальной является клетка (1,3). Для нее «невязка» равна -13. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (1,3), построим граф и запишем цикл. -23-22-12
+ - + -
Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В нашем случае это клетка (1, 2) с грузом 4.
Перемещаем по циклу груз величиной в 4 единицы, прибавляя её к грузу в клетках со знаком «+» и отнимая ее от груза в клетках со знаком «-». В результате перемещения по циклу получим новый план.
B1=15 | B2=15 | B3=16 | B4=15 | B5=15 | U | |
A1=19 | 21 - 15 | 17 | 12 + 4 | 24 | 30 | U1=0 |
A2=19 | 6 | 1 15 | 9 4 | 5 | 9 | U2=-3 |
A3=19 | 7 + | 5 | 24 - 8 | 6 11 | 13 | U3=12 |
A4=19 | 29 | 22 | 21 | 5 4 | 7 15 | 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= 30= 34= -12= 14= 16= - 27= - 11= 5= -342= 7
S43= -2
План не оптимален. Наиболее потенциальной является клетка (3,1). Для нее «невязка» равна -27. В клетку с наибольшей «невязкой» ввожv перевозку, выявляем цикл и пересчитываем клетки цикла.
Введем перевозку (3,1), построим граф и запишем цикл. -11-13-33
+ - + - Из клеток со знаком «-» выбираем клетку с наименьшей величиной груза. В
- 1
- 2
Похожие работы
Тема: Транспортная задача и задача об использовании сырья |
Предмет/Тип: Математика (Реферат) |
Тема: Транспортная задача и задача об использовании сырья |
Предмет/Тип: Финансовый менеджмент, финансовая математика (Реферат) |
Тема: Транспортная задача 2 |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Тема: Транспортная задача |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Тема: Транспортная задача 5 |
Предмет/Тип: Информатика, ВТ, телекоммуникации (Реферат) |
Интересная статья: Быстрое написание курсовой работы