При помощи элементарных преобразований матрицы коэффициентов системы ограничений привести задачу к стандартному виду и решить ее геометрическим методом

Задача 1
Исходные данные:
Дана основная задача линейного программирования. При помощи элементарных преобразований матрицы коэффициентов системы ограничений привести задачу к стандартному виду и решить ее геометрическим методом или доказать, что она не имеет оптимального плана.

Решение

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
Разрешающий элемент РЭ=-3. Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (-3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
5 : -3 -33 : -3 -3 : -3 -5 : -3 -1 : -3 -142 : -3
-12-(5 • -1):-3 -1-(-33 • -1):-3 -1-(-3 • -1):-3 1-(-5 • -1):-3 0-(-1 • -1):-3 -34-(-142 • -1):-3
4-(5 • 0):-3 -6-(-33 • 0):-3 0-(-3 • 0):-3 -1-(-5 • 0):-3 1-(-1 • 0):-3 -14-(-142 • 0):-3
Получаем новую матрицу:
-5/3 11 1 5/3 1/3 142/3
-41/3 10 0 8/3 1/3 40/3
4 -6 0 -1 1 -14
2. В качестве базовой переменной можно выбрать x5.
Разрешающий элемент РЭ=1. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x5 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
-12/3-(4 • 1/3):1 11-(-6 • 1/3):1 1-(0 • 1/3):1 12/3-(-1 • 1/3):1 1/3-(1 • 1/3):1 471/3-(-14 • 1/3):1
-132/3-(4 • 1/3):1 10-(-6 • 1/3):1 0-(0 • 1/3):1 22/3-(-1 • 1/3):1 1/3-(1 • 1/3):1 131/3-(-14 • 1/3):1
4 : 1 -6 : 1 0 : 1 -1 : 1 1 : 1 -14 : 1
Получаем новую матрицу:
-3 13 1 2 0 52
-15 12 0 3 0 18
4 -6 0 -1 1 -14
3. В качестве базовой переменной можно выбрать x4.
Разрешающий элемент РЭ=3. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x4 на разрешающий элемент РЭ=3. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
-3-(-15 • 2):3 13-(12 • 2):3 1-(0 • 2):3 2-(3 • 2):3 0-(0 • 2):3 52-(18 • 2):3
-15 : 3 12 : 3 0 : 3 3 : 3 0 : 3 18 : 3
4-(-15 • -1):3 -6-(12 • -1):3 0-(0 • -1):3 -1-(3 • -1):3 1-(0 • -1):3 -14-(18 • -1):3
Получаем новую матрицу:
7 5 1 0 0 40
-5 4 0 1 0 6
-1 -2 0 0 1 -8
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
7x1+5x2+x3 = 40
-5x1+4x2+x4 = 6
-x1-2x2+x5 = -8
Выразим базисные переменные через остальные:
x3 = -7x1-5x2+40
x4 = 5x1-4x2+6
x5 = x1+2x2-8
Подставим их в целевую функцию:
F(X) = 3x1+10x2+(-7x1-5x2+40)+(5x1-4x2+6)-46
или
F(X) = x1+x2 → min
Система неравенств:
-7x1-5x2+40 ≥ 0
5x1-4x2+6 ≥ 0
x1+2x2-8 ≥ 0