86073 (Транспортная задача линейного программирования), страница 6
Описание файла
Документ из архива "Транспортная задача линейного программирования", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "математика" в общих файлах.
Онлайн просмотр документа "86073"
Текст 6 страницы из документа "86073"
Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,vj- потенциал Bj. Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.Положим u1=0,тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу:
Магазины Склад | B1 (b1=40) v1=1,7 | B2 (b2=50) v2=2 | B3 (b3=15) v3=2,3 | B4 (b4=75) v4=1,8 | B5 (b5=40) v5=2,8 | B6 (b6=5) v6=0,3 | |
А 0,7 1 (а1=50)U1=0 | 1 0 ,0 | 2 50 - 0,7 ,0 | 3 - 0,7 ,0 | 2 - 0,7 ,5 | 3 0,3 ,5 | 0 | |
3 0 2 - 2,3 1 20 3 0 0
- 1,5 А - 1 2(а2=20)U2=-1,3 - 1,5 ,4 ,0 ,0 ,0 ,0 | 0 | ||||||
1 0 0 ,8 ,5 | 0 | ||||||
А 0,2 4(а4=80)U4=-0,3 | 1 - 0,3 ,2 | 2 0 ,0 | 2 15 0 ,0 | 1 20 0 ,5 | 2 40 0 ,5 | 0 5 |
В верхнем левом углу здесь и далее записываем значение ui+vj-cij. Имеем: u1+v1--c11 =0,7>0, u1+v6-c16 =0,3>0, u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0,
u4+v1-c41 =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А1В1, сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу:
Магазины Склад | B1 (b1=40) v1=1 | B2 (b2=50) v2=2 | B3 (b3=15) v3=2,3 | B4 (b4=75) v4=1,8 | B5 (b5=40) v5=2,8 | B6 (b6=5) v6=0,3 | |
А 0 1 (а1=50)U1=0 | 1 0 ,0
20 | 2 30 - 0,7 ,0 | 3 - 0,7 ,0 | 2 - 0,7 ,5 | 3 0,3 ,5 | 0 | |
3 0 2 ,0 ,0 | 0 | ||||||
1 -0,7 0 0 ,8 ,5 | 0 | ||||||
А -0,5 4(а4=80)U4=-0,3 | 1 - 0,3 ,2 | 2 0 ,0 | 2 15 0 ,0 | 1 20 0 ,5 | 2 40 0 ,5 | 0 5 |
Стоимость 2-ого плана:
D2=1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.
Имеем:u1+v6-c16 =0,3>0, u2+v3-c23 =0,7>0, u3+v3-c33 =0,3>0, u3+v5-c35 =0,3>0. => По критерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7 => Поместим перевозку в клетку А2В3, сместив 15=min(20,30,55,15) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u2+v3=1, u4+v4=1,5, u4+v5=2,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=1,6, v5=2,8, v6=0,3. Составим таблицу:
Магазины Склад | B1 (b1=40) v1=1 | B2 (b2=50) v2=2 | B3 (b3=15) v3=1,6 | B4 (b4=75) v4=1,8 | B5 (b5=40) v5=2,8 | B6 (b6=5) v6=0,3 | |
А 0 1 (а1=50)U1=0 | 1 0 ,0
35 | 2 15 -1,4 ,0 | 3 - 0,7 ,0 | 2 - 0,7 ,5 | 3 0,3 ,5 | 0 | |
3 0 2 - 1,6 1
0 3 15 0
- 0,8 А - 0,3 2(а2=20)U2=-0,6 - 0,8 ,4 ,0 5 ,0 ,0 ,0 | 0 | ||||||
1
0 0
0 1 ,0 35 -0,4 ,8 -0,7 ,5 | 0 | ||||||
А -0,5 4(а4=80)U4=-0,3 | 1 - 0,3 ,2 | 2 -0,7 ,0 | 2 0 ,0 | 1 35 0 ,5 | 2 40 0 ,5 | 0 5 |
Стоимость 3-его плана:
D3=1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.
Имеем:u1+v6-c16 =0,3>0,u3+v5-c35 =0,3>0. => По критерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3. => Поместим перевозку в клетку А3В5, сместив 40=min(40,40) по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А4В5 нулевую перевозку. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u4+v5=2,5, u2+v3=1, u4+v4=1,5, u3+v5=1,5 , u4+v6=0. Положим u1=0,тогда v1=1,u2=-0,6,v2=2,v4=1,5, u3=-1,u4=0, v3=1,6, v5=2,5, v6=0. Составим таблицу:
Магазины Склад | B1 (b1=40) v1=1 | B2 (b2=50) v2=2 | B3 (b3=15) v3=1,6 | B4 (b4=75) v4=1,5 | B5 (b5=40) v5=2,5 | B6 (b6=5) v6=0 | |
А 0 1 (а1=50)U1=0 | 1 0 ,0
35 | 2 15 - 1,4 ,0 | 3 - 1 ,0 | 2 - 1 ,5 | 3 0 ,5 | 0 | |
3 0 2 - 1,6 1
0 3 15 0
- 1,1 А - 0,6 2(а2=20)U2=-0,6 - 1,1 ,4 ,0 5 ,0 ,0 ,0 | 0 | ||||||
1
0 0 -0,4 1 35 1
0 0 40 А - 1 3(а3=75)U3=-1 ,7 -0,3 ,0 ,0 ,8 -0,7 ,5 | 0 | ||||||
А -0,2 4(а4=80)U4=0 | 1 0 ,2 | 2 -0,4 ,0 | 2 0 ,0 | 1 75 0 ,5 | 2 0 0 ,5 | 0 5 |
Стоимость 4-ого плана: D4=1•35+2•15+0,4•5+1•15+1•35+1,5•40+1,5•75=289,5.
Для всех клеток последней таблицы выполнены условия оптимальности:
1)ui+vj-сij=0 для клеток, занятых перевозками;
2)ui+vj-сij ≤0 для свободных клеток.