Задача 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) = (x1 - 24x2 + 12x3)
-x1 - 3x2 + 2x3 ≤ 1
-x1 + 4x2 – x3 ≤2
x1,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