Me-02_Gavrilyak (2)
.docГавриляк
Me-02
1. Решить М-симплекс-методом ЗЛП
,
f(x)=3x1-2x2+0*x3+0*x4+0*x5+0*x6-M*x7 ---> max |
|
2x1+x2+1*x3+0*x4+0*x5+0*x6=15 |
3x1+2x2+0*x3-1*x4+0*x5+0*x6+1*x7=6 |
4x1-2x2+0*x3+0*x4+1*x5+0*x6=18 |
5x1-5x2+0*x3+0*x4+0*x5+1*x6=16 |
№ итерации |
Базис |
Сi |
bi решение |
3 |
-2 |
0 |
0 |
0 |
0 |
(-M) |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
||||
0 |
x3 |
0 |
15 |
2 |
1 |
1 |
0 |
0 |
0 |
0 |
x7 |
(-M) |
6 |
3 |
2 |
0 |
-1 |
0 |
0 |
1 |
|
x5 |
0 |
18 |
4 |
-2 |
0 |
0 |
1 |
0 |
0 |
|
x6 |
0 |
16 |
5 |
-5 |
0 |
0 |
0 |
1 |
0 |
|
f |
Δj |
6M |
3+3M |
(-2+2M) |
0 |
(-M) |
0 |
0 |
0 |
|
f= - (-M*6)=6M |
|
|
7 1/2 |
|
|
|
|
|
|
|
Δ1=3-(-M*3)=3+3M |
|
|
2 |
|
|
|
|
|
|
|
Δ2= -2- (-M*2)= -2+2M |
|
|
4 1/2 |
|
|
|
|
|
|
|
Δ3=0-0=0 |
|
|
3 1/5 |
|
|
|
|
|
|
|
Δ4=0-(-M*(-1))=-M |
|
|
|
|
|
|
|
|
|
|
Δ5=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ6=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ7= -M-(-M*1)=0 |
|
|
|
|
|
|
|
|
|
|
№ итерации |
Базис |
Сi |
bi решение |
3 |
-2 |
0 |
0 |
0 |
0 |
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
|
||||
1 |
x3 |
0 |
11 |
0 |
- 1/3 |
1 |
2/3 |
0 |
0 |
-2 |
x1 |
3 |
2 |
1 |
2/3 |
0 |
- 1/3 |
0 |
0 |
|
|
x5 |
0 |
10 |
0 |
-4 2/3 |
0 |
1 1/3 |
1 |
0 |
-4 |
|
x6 |
0 |
6 |
0 |
-8 1/3 |
0 |
1 2/3 |
0 |
1 |
-5 |
|
f |
Δj |
-6 |
0 |
-4 |
0 |
1 |
0 |
0 |
|
|
f= - (3*2)= 6 |
|
|
16 1/2 |
|
|
|
|
|
|
|
Δ1=3-(3*1)=0 |
|
|
-6 |
|
|
|
|
|
|
|
Δ2= -2-(3*2/3)=-4 |
|
|
7 1/2 |
|
|
|
|
|
|
|
Δ3=0-0=0 |
|
|
3 3/5 |
|
|
|
|
|
|
|
Δ4=0-(3*(-1/3))=1 |
|
|
|
|
|
|
|
|
|
|
Δ5=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ6=0-0=0 |
|
|
|
|
|
|
|
|
|
|
№ итерации |
Базис |
Сi |
bi решение |
3 |
-2 |
0 |
0 |
0 |
0 |
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
|
||||
2 |
x3 |
0 |
8 3/5 |
0 |
3 |
1 |
0 |
0 |
- 2/5 |
- 2/3 |
x1 |
3 |
3 1/5 |
1 |
-1 |
0 |
0 |
0 |
1/5 |
1/3 |
|
x5 |
0 |
5 1/5 |
0 |
2 |
0 |
0 |
1 |
- 4/5 |
-1 1/3 |
|
x4 |
0 |
3 3/5 |
0 |
-5 |
0 |
1 |
0 |
3/5 |
|
|
f |
Δj |
-9 3/5 |
0 |
1 |
0 |
0 |
0 |
- 3/5 |
|
|
f= - (3*3 1/5)=- 9 3/5 |
|
|
2 7/8 |
|
|
|
|
|
|
|
Δ1=3-(3*1)= 0 |
|
|
-3 1/5 |
|
|
|
|
|
|
|
Δ2= -2-(3*(-1))=1 |
|
|
2 3/5 |
|
|
|
|
|
|
|
Δ3=0-0=0 |
|
|
- 5/7 |
|
|
|
|
|
|
|
Δ4=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ5=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ6=0-(3*1/5)=-3/5 |
|
|
|
|
|
|
|
|
|
|
№ итерации |
Базис |
Сi |
bi решение |
3 |
-2 |
0 |
0 |
0 |
0 |
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
|
||||
2 |
x3 |
0 |
4/5 |
0 |
0 |
1 |
0 |
-1 1/2 |
4/5 |
-3 |
x1 |
3 |
5 4/5 |
1 |
0 |
0 |
0 |
1/2 |
- 1/5 |
1 |
|
x2 |
-2 |
2 3/5 |
0 |
1 |
0 |
0 |
1/2 |
- 2/5 |
|
|
x4 |
0 |
16 3/5 |
0 |
0 |
0 |
1 |
2 1/2 |
-1 2/5 |
5 |
|
f |
Δj |
-12 1/5 |
0 |
0 |
0 |
0 |
- 1/2 |
- 1/5 |
|
|
f= - (3*5 4/5+(-2)*2 3/5)=- 12 1/5 |
|
|
|
|
|
|
|
|
|
|
Δ1=3-(3*1)= 0 |
|
|
|
|
|
|
|
|
|
|
Δ2= -2-(-2*1)=0 |
|
|
|
|
|
|
|
|
|
|
Δ3=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ4=0-0=0 |
|
|
|
|
|
|
|
|
|
|
Δ5=0-(3*1/2+(-2)*1/2)=-1/2 |
|
|
|
|
|
|
|
|
|
|
Δ6=0-(3*(-1/5)+(-2)*(-2/5)=-1/5 |
|
|
|
|
|
|
|
|
|
|
2. Для выпуска 4 видов товара нужно 3 вида сырья. Расход сырья на единицу каждого товара, запасы сырья и прибыль от продажи единицы товара - в таблице. Найти план выпуска товаров для максимизации прибыли, решая ЗЛП симплекс-методом. Решить двойственную к ней задачу. Если решение не целочисленно, найти целочисленное решение методом Гомори. |
Вариант задачи |
|||||
Вид сырья |
Товар |
Запас сырья |
||||
1 |
2 |
3 |
4 |
|||
1 |
5 |
4 |
6 |
7 |
275 |
|
2 |
2 |
0 |
4 |
2 |
100 |
|
3 |
3 |
2 |
0 |
1 |
85 |
|
Прибыль |
50 |
27 |
34 |
54 |
|
f(x)=50x1+27x2+34x3+54x4--->max |
f(x)=50x1+27x2+34x3+54x4+0*x5+0*x6+0*x7--->max |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5x1+4x2+6x3+7x4≤275 |
|
5x1+4x2+6x3+7x4+1*x5+0*x6+0*x7 = 275 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2x1+4x3+2x4≤100 |
|
|
2x1+4x3+2x4+0*x5+1*x6+0*x7=100 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3x1+2x2+x4≤85 |
|
|
3x1+2x2+x4+0*x5+0*x6+1*x7 = 85 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|