Для приведения ЗЛП к канонической форме необходимо:
0x1 + 0x2 + 1x3 + 1x4 + 0x5 = 3
0x1 + 2x2-1x3 + 0x4 + 0x5 = 4
0x1-1x2 + 3x3 + 0x4-1x5 = 3
F(X) = 4x1 + 2x2 + 5x3
Переход к СЗЛП.Расширенная матрица системы ограничений-равенств данной задачи:
0 | 0 | 1 | 1 | 0 | 3 |
0 | 2 | -1 | 0 | 0 | 4 |
0 | -1 | 3 | 0 | -1 | 3 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=2.
Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=2
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
0-(0 • 0):2 | 0-(2 • 0):2 | 1-(-1 • 0):2 | 1-(0 • 0):2 | 0-(0 • 0):2 | 3-(4 • 0):2 |
0 : 2 | 2 : 2 | -1 : 2 | 0 : 2 | 0 : 2 | 4 : 2 |
0-(0 • -1):2 | -1-(2 • -1):2 | 3-(-1 • -1):2 | 0-(0 • -1):2 | -1-(0 • -1):2 | 3-(4 • -1):2 |
Получаем новую матрицу:
0 | 0 | 1 | 1 | 0 | 3 |
0 | 1 | -1/2 | 0 | 0 | 2 |
0 | 0 | 21/2 | 0 | -1 | 5 |
3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=21/2.
Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=21/2
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
0-(0 • 1):21/2 | 0-(0 • 1):21/2 | 1-(21/2 • 1):21/2 | 1-(0 • 1):21/2 | 0-(-1 • 1):21/2 | 3-(5 • 1):21/2 |
0-(0 • -1/2):21/2 | 1-(0 • -1/2):21/2 | -1/2-(21/2 • -1/2):21/2 | 0-(0 • -1/2):21/2 | 0-(-1 • -1/2):21/2 | 2-(5 • -1/2):21/2 |
0 : 21/2 | 0 : 21/2 | 21/2 : 21/2 | 0 : 21/2 | -1 : 21/2 | 5 : 21/2 |
Получаем новую матрицу:
0 | 0 | 0 | 1 | 2/5 | 1 |
0 | 1 | 0 | 0 | -1/5 | 3 |
0 | 0 | 1 | 0 | -2/5 | 2 |
-----------------------------------------------------------------------------
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
x4 + 2/5 x5 = 1
x2 - 1/5 x5 = 3
x3 - 2/5 x5 = 2
Выразим базисные переменные через остальные:
x4 = - 2/5 x5+1
x2 = 1/5 x5+3
x3 = 2/5 x5+2
Подставим их в целевую функцию:
F(X) = 4x1 + 2( 1/5 x5+3) + 5( 2/5 x5+2)
или
F(X) = 4x1 + 22/5 x5+16 → max
Система неравенств:
- 2/5 x5+1 ≥ 0
1/5 x5+3 ≥ 0
2/5 x5+2 ≥ 0
Приводим систему неравенств к следующему виду:
2/5 x5 <= 1
- 1/5 x5 <= 3
- 2/5 x5 <= 2
F(X) = 4x1 + 22/5x5+16 → max
Упростим систему:
2/5 x2 <= 1
- 1/5 x2 <= 3
- 2/5 x2 <= 2
F(X) = 4x1 + 22/5 x2+16 → max
Как-то так=)