Решение методом искусственного базиса
Ограничения – неравенства Ограничения – равенства
-3x1 - 5x2 + 25 0 x3 = -3x1 – 5x2 + 25
-2x1 + 2x2 + 6 0 x4 = - 2x1 + 2x2 + 6
x1 + 2x2 – 3 0 ξ1 = -x1 – 2x2 + x5 +3 x1 + x2 – 2 0 ξ2 = - x1 – x2 + x6 + 2
xi 0, xi 0, ξ1 0
F = - 2x1 + x2 min ʄ = - 2x1 – 3x2 + x5 + x6 + 5
Свободные х1, х2
Преобразуем систему для решения симплекс – методом
x3 = 25 - (3x1 + 5x2 )
x4 = 6 - ( 2x1 - 2x2 )
ξ1 = 3 - ( x1 + 2x2 - x5)
ξ2 = 2 - (x1 + x2 - x6 )
F=0 – ( 2x1 – x2) ʄ = 5 – ( 2x1 + 3x2 – x5 – x6)
|
β |
x1 |
x2 |
x5 |
x6 |
x3 |
25 -15/4 |
3 -5/4 |
5 -5/2 |
0 5/4 |
0 0 |
x4 |
6 3/2 |
2 1/2 |
-2 1 |
0 1/2 |
0 0 |
ξ1 |
3 3/2 |
1 1/2 |
2 1/2 |
-1 -1/2 |
0 0 |
ξ2 |
2 -3/4 |
1 -1/4 |
1 -1/2 |
0 1/4 |
-1 0 |
F |
0 3/4 |
2 1/4 |
-1 1/2 |
0 -1/4 |
0 0 |
ʄ |
5 -9/4 |
2 -3/4 |
3 -3/2 |
-1 3/4 |
-1 0 |
|
β |
x1 |
x5 |
x6 |
x3 |
85/4 |
7/4 |
5/4 |
0 |
x4 |
15/2 |
5/2 |
1/2 |
0 |
x2 |
3/2 |
3/2 |
-1/2 |
0 |
ξ2 |
5/4 |
3/4 |
1/4 |
-1 |
F |
3/4 |
9/4 |
-1/4 |
0 |
ʄ |
11/4 |
5/4 |
-1/4 |
-1 |
На данном этапе все свободные члены равны дробным числам, следовательно данный способ не может быть использован для решения данной задачи.
Вывод: задача линейного программирования решена графическим, алгебраическим методом, симплекс методом. Во всех случаях получены одинаковые решения, что говорит о корректности решения.
3.Решить зцлп
3.1Решение зцлп методом Гомори:
F = x1 + 2x2 max
5x1 + 7x2 ≤ 21
-x1 + 3x2 ≤ 8
x1,x2 ≥ 0
x1, x2 –целые
Приведём к канонической форме
-F = - x1 - 2x2 min
-
5x1
- 7x2
≥ -21
x1 - 3x2 ≥ - 8
Решим с помощью симплекс – метода
-
5x1
– 7x2 + 21 = x3
x1 – 3x2 + 8 = x4
x
3
= 21 – ( 5x1
+ 7x2
)
x4 = 8 – ( -x1 + 3x2 )
-F = 0 – ( x1 + 2x2 ) min
|
β |
x1 |
x |
x3
|
21
-56/3 |
5
7/3 |
7
-7/3 |
x4
|
8
8/3 |
-1
-1/3 |
3
1/3 |
-F
|
0
-16/3 |
1
2/3 |
2
-2/3 |
2
λ = 1/3
|
β |
x1 |
X4 |
x3
|
7/3
7/22 |
22/3
3/22 |
-7/3
-7/22 |
X2
|
8/3
7/66 |
-1/3
1/22 |
1/3
-7/66 |
-F
|
-16/3
-35/66 |
5/3
-5/22 |
-2/3
35/66 |
λ = 3/22
|
β |
X3 |
X4 |
X1
|
7/22
|
3/22
|
-7/22
|
X2
|
61/22
|
1/22
|
5/22
|
-F
|
-129/22
|
-5/22
|
-3/22
|
F опт = 129/22
XT ={ 7/22, 61/22 , 0 , 0 }
β1 = 7/22 – 0 = 7/22
α13 = 3/22 – 0 =3/22
α14 = 15/22 – 0 = 15/22
u1 = -7/22 – ( - 3/22 x3 – 15/22 x4 )
|
β |
X |
X4 |
X1
|
7/22
-7/22 |
3/22
1 |
-7/22
-15/22 |
X2
|
61/22
-7/66 |
1/22
1/3 |
5/22
-5/22 |
U1
|
-7/22
7/3 |
-3/22
-22/3 |
-15/22
5 |
-F
|
-129/22
35/66 |
-5/22
-5/3 |
-3/22
25/22 |
3
λ
= - 22/3
|
β |
U1 |
X4 |
X1
|
0
7/15 |
1
-22/15 |
-1
1/5 |
X2
|
8/3
0 |
1/3
0 |
0
0 |
X3
|
7/3
7/15 |
-22/3
-22/15 |
5
1/5 |
-F
|
-16/3
-7/15 |
-5/3
22/15 |
1
-1/5 |
λ = 1/5
|
β |
U1 |
X3 |
X1
|
7/15
|
-7/15
|
1/5
|
X2
|
8/3
|
1/3
|
0
|
X4
|
7/15
|
-22/15
|
1/5
|
-F
|
-29/5
|
-1/5
|
-1/5
|
Fопт = 29/5
XT ={ 7/15, 8/3 , 0 , 7/15 }
β2 = 8/3 – 2 = 2/3
α2u1 = 1/3 – 0 = 1/3
α23 = 0
u2 = -2/3 – ( - 1/3 u1 – 0 x3 )
|
β |
U1 |
X3 |
X1
|
7/15
14/5 |
-7/15
-7/5 |
1/5
0 |
X2
|
8/3
-2/3 |
1/3
1 |
0
0 |
X4
|
7/15 44/15 |
-22/15
-22/5 |
1/5
0 |
U |
-2/3
2 |
-1/3
-3 |
0
0 |
-F
|
-2 9/5
6/15 |
-1/5
-3/5 |
-1/5
0 |
2
λ = -3
|
β |
U2 |
X3 |
X1
|
7/5
|
-7/5
|
1/5
|
X2
|
2
|
1
|
0
|
X4
|
17/15
|
-22/5
|
1/5
|
U1 |
2
|
-3
|
0
|
-F
|
-2 7/5
|
-3/5
|
-1/5
|
Fопт = 27/5
XT ={ 7/5, 2 , 0 , 17/5 }
β1 = 7/5 – 1 = 2/5
α21u2 = 3/5 – 0 = 3/5
α13 = 1/5
u2 = -2/5 – ( - 3/5 u2 – 1/5 x3 )
|
β |
U2 |
X3 |
X1
|
7/5
-2/5 |
-7/5
-3/5 |
1/5
1 |
X2
|
2
0 |
1
0 |
0
0 |
X4
|
17/15
-2/5 |
-22/5
-3/5 |
1/5
1 |
U1 |
2
0 |
-3
0 |
0
0 |
U3
|
-2 /5
2 |
-3/5
3 |
-1/5
-5 |
-F
|
-2 7/5
2/5 |
-3/5
3/5 |
-1/5
-1 |
λ = -5
|
β |
U2 |
U3 |
X1
|
1
|
-2
|
1
|
X2
|
2
|
1
|
0
|
X4
|
3
|
-5
|
1
|
U1 |
2
|
-3
|
0
|
X3
|
2
|
3
|
-5
|
-F
|
-5
|
0
|
-1
|
F опт = 5
XT ={ 1, 2 , 2 , 3}