| Задача 1
Решить графическим методом задачу линейного программирования
А) найти область допустимых значений многоугольник решений
Б) найти оптимумы целевой функции
F=2x1
+ x2
max min
2X1 + X2 ≥ 4
2X1 - X2 ≤ 0
0 ≤ X1 < 2
0 ≤ X2 < 8
Решение:
1) 2X1 + X2 ≥ 4
(0; 4) и (1; 2) - решения системы
(2; 2) – контрольная точка
2) 2X1 - X2 ≤ 0
(2; 4) и (1; 2) - решения системы
(0; 1) – контрольная точка
3) Линия уровня 2x1
+ x2
= 0 (0; 0) и (2; - 4)
4) Дельта = (2;1)
5) Min (B) = 2 * 0 + 4 = 4 B (0; 4)
6) Max (D) = 2 * 2 + 8 = 12 D (2; 8)
Ответ: Min f(x) = 4
Max f(x) = 12
Задача 2
Решить задачу линейного программирования симплекс методом с искусственным базисом
max f
(X
) = (x
1
- 24x
2
+ 12x
3
)
-x
1
- 3x
2
+ 2x
3
≤ 1
-x
1
+ 4x
2
– x
3
≤2
x
1,2,3
≥ 0
Решение:
После приведения к канонической форме получим
max f(X) = 1 * x1
– 24 * x2
+ 12 * x3
+ 0 * x4
+ 0 * x5
Ограничения приобрели следующую форму:
- 1 *x1
– 3 * x2
+ 2 * x3
+ 1 * x4
– 0 * x5
+ 0 * p1
= 1
- 1 * x1
+ 4 * x2
– 1 * x3
+ 0 * x4
– 1 * x5
+ 1 * p1
= 2
X1,2,3,4
> 0; j = 1,4
В результате получим следующую симплекс-таблицу:
| Базис
|
B
|
Ci/Cj
|
А1
|
А2
|
А3
|
А4
|
А5
|
P1
|
Q
|
| А4
|
1
|
0
|
-1
|
-3
|
2
|
1
|
0
|
0
|
-0,333333333333333
|
| P1
|
2
|
-m
|
-1
|
4
|
-1
|
0
|
-1
|
1
|
0,5
|
| |
|
дельта
|
m-1
|
-4m+24
|
m-12
|
0
|
m
|
0
|
|
| А4
|
2,5
|
0
|
-1,75
|
0
|
1,25
|
1
|
-0,75
|
0
|
2
|
| А2
|
0,5
|
-24
|
-0,25
|
1
|
-0,25
|
0
|
-0,25
|
0
|
-2
|
| |
|
дельта
|
5
|
0
|
-6
|
0
|
6
|
0
|
|
| А3
|
2
|
12
|
-1,39999
|
0
|
1
|
0,8
|
-0,59999
|
0
|
-1,42857142857143
|
| А2
|
1
|
-24
|
-0,59999
|
1
|
0
|
0,2
|
-0,4
|
0
|
-1,66666666666667
|
| |
|
|
-3,4
|
0
|
0
|
4,8
|
2,4
|
0
|
|
Ответ: решения нет, так как Q < 0
|
