183619 (584739), страница 2
Текст из файла (страница 2)
На предприятии ОАО «Электросигнал» имеется 4 транзитных склада Аi, на которых хранятся сборочные узлы и 5 цехов Bj, занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.
Таблица 3. – Исходные данные по количеству сборочных узлов и стоимость перевозки
| Ц Склад | B1 (b1=40) | B2 (b2=50) | B3 (b3=15) | B4 (b4=75) | B5 (b5=40) |
| А1 (а1=50) | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 |
| А2(а2=20) | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 |
| А3(а3=75) | 0,7 | 1,0 | 1,0 | 0,8 | 1,5 |
| А4(а4=80) | 1,2 | 2,0 | 2,0 | 1,5 | 2,5 |
ехаВ данном случае Σai=225 >Σbj=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу 3. :
Таблица 3. -
| Ц Склад | B1 (b1=40) | B2 (b2=50) | B3 (b3=15) | B4 (b4=75) | B5 (b5=40) | B6 (b6=5) |
| А1 (а1=50) | 1,0 | 2,0 | 3,0 | 2,5 | 3,5 | 0 |
| А2(а2=20) | 0,4 | 3,0 | 1,0 | 2,0 | 3,0 | 0 |
| А3(а3=75) | 0,7 | 1,0 | 1,0 | 0,8 | 1,5 | 0 |
| А4(а4=80) | 1,2 | 2,0 | 2,0 | 1,5 | 2,5 | 0 |
ехаМатематическая модель: обозначим xij – количество товара, перевозимого из Аi в Bj. Тогда
x
11 x12 x13 x14 x15 x16
x21 x22 x23 x24 x25 x26
X = x31 x32 x33 x34 x35 x36 - матрица перевозок.
x41 x42 x43 x44 x45 x46
min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (3. )
x11+x12+x13+x14+x15+x16=50
x
21+x22+x23+x24+x25+x26=20
x31+x32+x33+x34+x35+x36=75
x41+x42+x43+x44+x45+x46=80
(3. )
x11+x21+x31+x41=40x12+x22+x32+x42=50
x13+x23+x33+x43=15
x14+x24+x34+x44=75
x15+x25+x35+x45=40
x16+x26+x36+x46=5
xij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3. )
Двойственная ЗЛП:
max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (3. )
u2+v1≤0,4
u2+v2≤3
u2+v3≤1
u2+v4≤2
u2+v5≤3
u2+v6≤0
u3+v1≤0,7
u3+v2≤1
u3+v3≤1
u3+v4≤0,8
u3+v5≤1,5
u3+v6≤0
u4+v1≤1,2
u4+v2≤2
u4+v3≤2
u4+v4≤1,5
u4+v5≤2,5
u4+v6≤0
u
1+v1≤1
u1+v2≤2
u1+v3≤3 (3. )
u1+v4≤2,5
u1+v5≤3,5
u1+v6≤0
ui,vj – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 )
Будем искать первоначальный план по методу наименьшей стоимости:
1) x21=20 и 2-ую строку исключаем;
2) x31=20 и 1-ый столбец исключаем;
3) x34=55 и 3-ю строку исключаем;
4) x44=20 и 4-ый столбец исключаем;
5) x12=50 и 1-ю строку и 2-ой столбец исключаем и x32=0;
6) x43=150 и 3-ий столбец исключаем;
7) x45=40 и 5-ый столбец исключаем и x46=5.
Составим таблицу 3. . Здесь и далее в нижнем правом углу записываем значение перевозки.
Таблица 3. – Проведение итераций
| Склад | B1 (b1=40) | B2 (b2=50) | B3 (b3=15) | B4 (b4=75) | B5 (b5=40) | B6 (b6=5) | |||||
| 2 50 А1 (а1=50) 1,0
| 3,0 | 2,5 | 3,5 | 0 | |||||||
|
20 А2(а2=20) 0 | 3,0 | 1,0 | 2,0 | 3,0 | 0 | ||||||
| 0 20 1 0
55 А3(а3=75) 0 ,0 1,0 ,8 | 1,5 | 0 | |||||||||
| 2 5 1 15 А
40 20 4(а4=80)1,2 2,0 2,0 ,5 ,5 | 0 | ||||||||||
Цеха
Стоимость 1-ого плана:
D1=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.
Будем улучшать этот план методом потенциалов: 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.Составим таблицу 3. :
Таблица 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 | |
| 3 | 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 | 0 | ||||||
| 0 0,2 2
0 1
15 2
20 2 0 1 40 А 5 4(а4=80)U4=-0,3 ,2 ,0 0 ,0 0 ,5 - 0,3 ,5 | |||||||
,5
,8В верхнем левом углу здесь и далее записываем значение 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. Составим таблицу 3. :
Таблица 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 | |
| 3 0 2 | 0 | ||||||
| 3 0 2 | 0 | ||||||
| 1 -0,7 0 | 0 | ||||||
| 0 -0,5 2
0 1 | |||||||
,5
,0
0Стоимость 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. Составим таблицу 3.:
Таблица 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 | |
| 3 0 2 0 3 35 2
15
- 0,7 1 - 0,7 А 0,3 1 (а1=50)U1=0 ,0-1,4 ,0 ,0 ,5 ,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   35 -0,4 ,8 -0,7 ,5 | 0 | ||||||
| 0 -0,5 2
- 0 1 | |||||||
Стоимость 3-его плана:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
