Дополнительное задание
Решить прямую задачу аналитически симплекс-методом с учетом дополнительных ограничений:
2
х1
+ х2 ≤ 2,
х1 + 3х2 ≤ 3,
х1 ≥ 0.5 или -х1 ≤ -0.5,
х2 ≥ 0.5 или -х2 ≤ -0.5.
F(х1, x2) = 2х1 + 3х2 → max.
Запишем задачу в каноническом виде:
2
х1
+ х2 + х3 = 2,
х1 + 3х2 + х4 = 3,
-х1 + х5 = -1/2,
-х2 + х6 = -1/2.
F(х1, x2) = 2х1 + 3х2 → max
Из данных задачи составляем исходную симплекс-таблицу:
|
|
|
|
|
|
|
|
1 |
2 |
0 |
γ |
|
0 |
2 |
3 |
0 |
1 |
|
3 |
2 |
1 |
2 |
|
|
4 |
1 |
3 |
3 |
|
|
5 |
-1 |
0 |
-1/2 |
|
|
6 |
0 |
-1 |
-1/2 |
|
Первая итерация (k = 1). Вычислим текущее допустимое решение: x1 = x2 = 0, x3 = 2, x4 = 3, x5 = x6 = 1/2, F = 0.
|
|
|
е |
|
|
|
|
1 |
2 |
0 |
γ |
|
0 |
2 |
3 |
0 |
1 |
|
3 |
2 |
1 |
2 |
2/1 = 2 |
|
4 |
1 |
3 |
3 |
3/3 = 1 |
|
5 |
-1 |
0 |
-1/2 |
-1/2 ÷ 0 = -∞ |
s |
6 |
0 |
-1 |
-1/2 |
-1/2 ÷ (-1) = 1/2 - min |
|
|
|
|
|
|
|
|
1 |
6 |
0 |
γ |
|
0 |
2 – 0 * 3 = 2 |
3 |
0 – 1/2 * 3 = -3/2 |
2 |
|
3 |
2 – 0 * 1 = 2 |
1 |
2 – 1/2 * 1 = 3/2 |
|
|
4 |
1 – 0 * 3 = 1 |
3 |
3 – 1/2 * 3 = 3/2 |
|
|
5 |
-1 – 0 * 0 = -1 |
0 |
-1/2 – 1/2 * 0 = -1/2 |
|
|
2 |
0 |
-1 |
1/2 |
|
Вторая итерация (k = 2). Вычислим текущее допустимое решение: x1 = x6 = 0, x3 = х4 = 3/2, x5 = -1/2, х2 = 1/2, F = |-3/2|.
|
|
|
e |
|
|
|
|
1 |
6 |
0 |
γ |
|
0 |
2 |
3 |
-3/2 |
2 |
|
3 |
2 |
1 |
3/2 |
3/2 ÷ 1 = 3/2 |
s |
4 |
1 |
3 |
3/2 |
3/2 ÷ 3 = 1/2 - min |
|
5 |
-1 |
0 |
-1/2 |
-1/2 ÷ 0 = -∞ |
|
2 |
0 |
-1 |
1/2 |
1/2 ÷ (-1) = -1/2 |
|
|
|
|
|
|
|
|
1 |
4 |
0 |
γ |
|
0 |
2 – 1/3 * 3 = 1 |
-1 |
-3/2 – 1/2 * 3 = -3 |
3 |
|
3 |
2 – 1/3 * 1 = 5/3 |
-1/3 |
3/2 – 1/2 * 1 = 1 |
|
|
6 |
1/3 |
1/3 |
1/2 |
|
|
5 |
-1 – 1/3 * 0 = -1 |
0 |
-1/2 – 1/2 * 0 = -1/2 |
|
|
2 |
0 – 1/3 * (-1) = 1/3 |
1/3 |
1/2 – 1/2 * (-1) = 1 |
|
Третья итерация (k = 3). Вычислим текущее допустимое решение: x1 = x4 = 0, x2 = х3 = 1, x6 = 1/2, х5 = -1/2, F = |-3|.
|
|
e |
|
|
|
|
|
1 |
4 |
0 |
γ |
|
0 |
1 |
-1 |
-3 |
3 |
|
3 |
5/3 |
-1/3 |
1 |
1 ÷ 5/3 = 3/5 |
|
6 |
1/3 |
1/3 |
1/2 |
1/2 ÷ 1/3 = 3/2 |
s |
5 |
-1 |
0 |
-1/2 |
-1/2 ÷ (-1) = 1/2 - min |
|
2 |
1/3 |
1/3 |
1 |
1 ÷ 1/3 = 3 |
|
|
|
|
|
|
|
|
5 |
4 |
0 |
γ |
|
0 |
1 |
-1 – 0 * 1 = -1 |
-3 – 1/2 * 1 = -7/2 |
4 |
|
3 |
5/3 |
-1/3 – 0 * 5/3 = -1/3 |
1 – 1/2 * 5/3 = 1/6 |
|
|
6 |
1/3 |
1/3 – 0 * 1/3 = 1/3 |
1/2 – 1/2 * 1/3 = 1/3 |
|
|
1 |
-1 |
0 |
1/2 |
|
|
2 |
1/3 |
1/3 – 0 * 1/3 = 1/3 |
1 – 1/2 * 1/3 = 5/6 |
|
Четвертая итерация (k = 4). Вычислим текущее допустимое решение: x5 = x4 = 0, x3 = 1/6, x6 = 1/3, х1 = 1/2, х2 = 5/6, F = |-7/2|.
|
|
e |
|
|
|
|
|
5 |
4 |
0 |
γ |
|
0 |
1 |
-1 |
-7/2 |
4 |
s |
3 |
5/3 |
-1/3 |
1/6 |
1/6 ÷ 5/3 = 1/10 - min |
|
6 |
1/3 |
1/3 |
1/3 |
1/3 ÷ 1/3 = 1 |
|
1 |
-1 |
0 |
1/2 |
1/2 ÷ (-1) = -1/2 |
|
2 |
1/3 |
1/3 |
5/6 |
5/6 ÷ 1/3 = 5/2 |
|
|
|
|
|
|
|
|
3 |
4 |
0 |
γ |
|
0 |
-3/5 |
-1 – (-1/5) * 1 = -4/5 |
-7/2 – 1/10 * 1 = -18/5 |
5 |
|
5 |
3/5 |
-1/5 |
1/10 |
|
|
6 |
-1/5 |
1/3 – (-1/5) * 1/3 = 2/5 |
1/3 – 1/10 * 1/3 = 3/10 |
|
|
1 |
3/5 |
0 – (-1/5) * (-1) = -1/5 |
1/2 - 1/10 * (-1) = 3/5 |
|
|
2 |
-1/5 |
1/3 – (-1/5) * 1/3 = 2/5 |
5/6 – 1/10 * 1/3 = 4/5 |
|
Пятая итерация (k = 5). Вычислим текущее допустимое решение: x3 = x4 = 0, x5 = 1/10, x6 = 3/10, х1 = 3/5, х2 = 4/5, F = |-18/5|.
Так все коэффициенты при свободных переменных отрицательны, то найденное решение является единственным оптимальным решением данной задачи. Улучшить найденное решение не возможно.
Значит, Fmах = F(0.6, 0.8) = 3.6. Получили тот же ответ.