Задача 1. Решить задачу линейного программирования.
при условиях
.
Решение
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).
Определим максимальное значение целевой функции F(X) = x1 + 3x3 при следующих условиях-ограничений.
x1 + x2 + x3=11
2x1 - 3x2 - x4=1
x1 - x2 - x5=3
Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7; в 3-м равенстве вводим переменную x8;
1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 = 11
2x1-3x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 + 0x8 = 1
1x1-1x2 + 0x3 + 0x4-1x5 + 0x6 + 0x7 + 1x8 = 3
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = x1+3x3 - Mx6 - Mx7 - Mx8 → max
Из уравнений выражаем искусственные переменные:
x6 = 11-x1-x2-x3
x7 = 1-2x1+3x2+x4
x8 = 3-x1+x2+x5
которые подставим в целевую функцию:
F(X) = (1+4M)x1+(-3M)x2+(3+M)x3+(-M)x4+(-M)x5+(-15M) → max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
2 |
-3 |
0 |
-1 |
0 |
0 |
1 |
0 |
|
1 |
-1 |
0 |
0 |
-1 |
0 |
0 |
1 |
Решим систему уравнений относительно базисных переменных:
x6, x7, x8,