Решение задачи ЛП графическим способом при большом количестве переменных

Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП.
F(X) = 3x1 - 2x2 + 5x3 - 4x5 → max при ограничениях:
x1 + x2 + x3=12
2x1 - x2 + x4=8
- 2x1 + 2x2 + x5=10
F(X) = 3x1 - 2x2 + 5x3 - 4x5
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
1110012
2-10108
-2200110

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x1 + x2 + x3 = 12
2x1 - x2 + x4 = 8
- 2x1 + 2x2 + x5 = 10
Выразим базисные переменные через остальные:
x3 = - x1 - x2+12
x4 = - 2x1 + x2+8
x5 = 2x1 - 2x2+10
Подставим их в целевую функцию:
F(X) = 3x1 - 2x2 + 5(- x1 - x2+12) - 4(2x1 - 2x2+10)
или
F(X) = - 10x1 + x2+20 → max
Система неравенств:
- x1 - x2+12 ≥ 0
- 2x1 + x2+8 ≥ 0
2x1 - 2x2+10 ≥ 0
Приводим систему неравенств к следующему виду:
x1 + x2 ≤ 12
2x1 - x2 ≤ 8
- 2x1 + 2x2 ≤ 10
F(X) = - 10x1 + x2+20 → max

Далее решаем задачу геометрическим методом.

загрузка...