Переход к стандартной форме ЗЛП
СЗЛП - задача линейного программирования вида ax ≥ b или ax ≤ b. где a - матрица коэффициентов, b - вектор ограничений.Математическая модель ЗЛП называется стандартной, если ограничения в ней представлены в виде линейных неравенств, а целевая функция минимизируется или максимизируется.
Назначение сервиса. Онлайн-калькулятор предназначен для приведения КЗЛП к СЗЛП путем преобразования матрицы a к единичной. При этом возможны две стандартных формы:
- Первая стандартная форма ax ≥ b, F(X) → min.
- Вторая стандартная форма ax ≤ b, F(X) → max.
Пример. Дана основная задача линейного программирования. При помощи элементарных преобразований матрицы коэффициентов системы ограничений привести задачу к стандартному виду и решить ее геометрическим методом или доказать, что она не имеет оптимального плана.
Расширенная матрица системы ограничений-равенств данной задачи:
|
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной выбираем x1.
Разрешающий элемент РЭ=1.
Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x1 на разрешающий элемент РЭ=1
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x1 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
1 : 1 | 6 : 1 | -1 : 1 | -1 : 1 | -1 : 1 | 2 : 1 |
5-(1·5):1 | -12-(6·5):1 | -1-(-1·5):1 | 2-(-1·5):1 | 0-(-1·5):1 | -4-(2·5):1 |
3-(1·3):1 | -1-(6·3):1 | -2-(-1·3):1 | 0-(-1·3):1 | -1-(-1·3):1 | -7-(2·3):1 |
Разрешающий элемент РЭ=-42.
Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-42
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
1-(0·6):-42 | 6-(-42·6):-42 | -1-(4·6):-42 | -1-(7·6):-42 | -1-(5·6):-42 | 2-(-14·6):-42 |
0 : -42 | -42 : -42 | 4 : -42 | 7 : -42 | 5 : -42 | -14 : -42 |
0-(0·-19):-42 | -19-(-42·-19):-42 | 1-(4·-19):-42 | 3-(7·-19):-42 | 2-(5·-19):-42 | -13-(-14·-19):-42 |
Получаем новую матрицу:
1 | 0 | -3/7 | 0 | -2/7 | 0 |
0 | 1 | -2/21 | -1/6 | -5/42 | 1/3 |
0 | 0 | -17/21 | -1/6 | -11/42 | -20/3 |
3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=-17/21.
Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-17/21
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
1-(0·-3/7):-17/21 | 0-(0·-3/7):-17/21 | -3/7-(-17/21·-3/7):-17/21 | 0-(-1/6·-3/7):-17/21 | -2/7-(-11/42·-3/7):-17/21 | 0-(-62/3·-3/7):-17/21 |
0-(0·-2/21):-17/21 | 1-(0·-2/21):-17/21 | -2/21-(-17/21·-2/21):-17/21 | -1/6-(-1/6·-2/21):-17/21 | -5/42-(-11/42·-2/21):-17/21 | 1/3-(-62/3·-2/21):-17/21 |
0 : -17/21 | 0 : -17/21 | -17/21 : -17/21 | -1/6 : -17/21 | -11/42 : -17/21 | -62/3 : -17/21 |
Получаем новую матрицу:
1 | 0 | 0 | 3/34 | -5/34 | 60/17 |
0 | 1 | 0 | -5/34 | -3/34 | 19/17 |
0 | 0 | 1 | 7/34 | 11/34 | 140/17 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (1,2,3).
Соответствующие уравнения имеют вид:
x1 + 3/34x4 - 5/34x5 = 39/17
x2 - 5/34x4 - 3/34x5 = 12/17
x3 + 7/34x4 + 11/34x5 = 84/17
Выразим базисные переменные через остальные:
x1 = - 3/34x4 + 5/34x5+39/17
x2 = 5/34x4 + 3/34x5+12/17
x3 = - 7/34x4 - 11/34x5+84/17
Подставим их в целевую функцию:
F(X) = - 3(- 3/34x4 + 5/34x5+39/17) + 13( 5/34x4 + 3/34x5+12/17) + (- 7/34x4 - 11/34x5+84/17) - 2x4
или
F(X) = - 1/34x4 + 13/34x5+123/17 → max
Система неравенств:
- 3/34x4 + 5/34x5+39/17 ≥ 0
5/34x4 + 3/34x5+12/17 ≥ 0
- 7/34x4 - 11/34x5+84/17 ≥ 0
Приводим систему неравенств к следующему виду:
3/34x4 - 5/34x5 ≤ 39/17
- 5/34x4 - 3/34x5 ≤ 12/17
7/34x4 + 11/34x5 ≤ 84/17
F(X) = - 1/34x4 + 13/34x5+123/17 → max
Упростим систему.
3x1 - 5x2 ≤ 120
- 5x1 - 3x2 ≤ 38
7x1 + 11x2 ≤ 280
F(X) = - x1 + 13x2+414 → max
Далее систему можно решать геометрическим методом.
Пример №2. Привести следующую КЗЛП к задаче в стандартной форме:
F = x1 – 2x2 –x3 –x4 → max
при ограничениях:
2x1 + x3 –x4 +x5 = 2
4x1 + x2 +3x3 +x4+2x5 = 7
-x1 +x3 +2x4+x5 = 2
xi ≥0
2 | 0 | 1 | -1 | 1 | 2 |
4 | 1 | 3 | 1 | 2 | 7 |
-1 | 0 | 1 | 2 | 1 | 2 |
Методом Жордано-Гаусса приведем матрицу к единичной:
Последовательно будем выбирать разрешающий элемент РЭ, который лежит на главной диагонали матрицы.
Разрешающий элемент равен (2).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
РЭ - разрешающий элемент (2), А и В - элементы матрицы, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
x1 | x2 | x3 | x4 | x5 | B |
2 / 2 = 1 | 0 / 2 = 0 | 1 / 2 = 0.5 | -1 / 2 = -0.5 | 1 / 2 = 0.5 | 2 / 2 = 1 |
1 | 0 | 0.5 | -0.5 | 0.5 | 1 |
0 | 1 | 1 | 3 | 0 | 3 |
0 | 0 | 1.5 | 1.5 | 1.5 | 3 |
Разрешающий элемент равен (1).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Представим расчет каждого элемента в виде таблицы:
x1 | x2 | x3 | x4 | x5 | B |
0 / 1 = 0 | 1 / 1 = 1 | 1 / 1 = 1 | 3 / 1 = 3 | 0 / 1 = 0 | 3 / 1 = 3 |
1 | 0 | 0.5 | -0.5 | 0.5 | 1 |
0 | 1 | 1 | 3 | 0 | 3 |
0 | 0 | 1.5 | 1.5 | 1.5 | 3 |
Разрешающий элемент равен (1.5).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
1 | 0 | 0 | -1 | 0 | 0 |
0 | 1 | 0 | 2 | -1 | 1 |
0 | 0 | 1 | 1 | 1 | 2 |
Соответствующие уравнения имеют вид:
x1 – x4 = 0
x2 + 2x4 – x5= 1
x3 + x4 + x5= 2
Выразим x1, x2 и x3 через x4 и x5.
x1 = x4
x2 = -2x4 + x5 + 1
x3 = -x4 - x5 + 2
Получим новую целевую функцию F = - 4 + x4 – x5 → max
и систему неравенств
x4 ≥ 0
-2x4 + x5 + 1 ≥ 0
-x4 - x5 + 2≥ 0
x5 ≥ 0
Приводим второе и третье неравенство к следующему виду:
x4 ≥ 0
2x4 - x5 ≤ 1
x4 + x5 ≤ 2
x5 ≥ 0
F = - 4 + x4 – x5 → max
Таким образом, исходная КЗЛП сведена к СЗЛП.
Перейти к онлайн решению своей задачи
Пример №2. Дана основная задача линейного программирования. При помощи элементарных преобразований матрицы коэффициентов системы ограничений, привести задачу стандартному виду и решить ее геометрическим методом. Методом искусственного базиса получить каноническую задачу (или доказать несовместимость этой системы). Решить полученную модель с помощью симплекс-таблиц (или доказать, что она не имеет оптимального плана).
Решение.
Расширенная матрица системы ограничений-равенств данной задачи:
|
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной выбираем x1.
Разрешающий элемент РЭ=3.
Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x1 на разрешающий элемент РЭ=3
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x1 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
3 : 3 | -1 : 3 | 1 : 3 | 1 : 3 | 1 : 3 | 4 : 3 |
11-(3·11):3 | -6-(-1·11):3 | 2-(1·11):3 | -1-(1·11):3 | 0-(1·11):3 | 4-(4·11):3 |
4-(3·4):3 | -5-(-1·4):3 | -3-(1·4):3 | 0-(1·4):3 | -1-(1·4):3 | -8-(4·4):3 |
1 | -1/3 | 1/3 | 1/3 | 1/3 | 11/3 |
0 | -21/3 | -12/3 | -42/3 | -32/3 | -102/3 |
0 | -32/3 | -41/3 | -11/3 | -21/3 | -131/3 |
Разрешающий элемент РЭ=-21/3.
Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-21/3
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
1-(0·-1/3):-21/3 | -1/3-(-21/3·-1/3):-21/3 | 1/3-(-12/3·-1/3):-21/3 | 1/3-(-42/3·-1/3):-21/3 | 1/3-(-32/3·-1/3):-21/3 | 11/3-(-102/3·-1/3):-21/3 |
0 : -21/3 | -21/3 : -21/3 | -12/3 : -21/3 | -42/3 : -21/3 | -32/3 : -21/3 | -102/3 : -21/3 |
0-(0·-32/3):-21/3 | -32/3-(-21/3·-32/3):-21/3 | -41/3-(-12/3·-32/3):-21/3 | -11/3-(-42/3·-32/3):-21/3 | -21/3-(-32/3·-32/3):-21/3 | -131/3-(-102/3·-32/3):-21/3 |
1 | 0 | 4/7 | 1 | 6/7 | 26/7 |
0 | 1 | 5/7 | 2 | 14/7 | 44/7 |
0 | 0 | -15/7 | 6 | 33/7 | 33/7 |
Разрешающий элемент РЭ=-15/7.
Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-15/7
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
1-(0·4/7):-15/7 | 0-(0·4/7):-15/7 | 4/7-(-15/7·4/7):-15/7 | 1-(6·4/7):-15/7 | 6/7-(33/7·4/7):-15/7 | 26/7-(33/7·4/7):-15/7 |
0-(0·5/7):-15/7 | 1-(0·5/7):-15/7 | 5/7-(-15/7·5/7):-15/7 | 2-(6·5/7):-15/7 | 14/7-(33/7·5/7):-15/7 | 44/7-(33/7·5/7):-15/7 |
0 : -15/7 | 0 : -15/7 | -15/7 : -15/7 | 6 : -15/7 | 33/7 : -15/7 | 33/7 : -15/7 |
1 | 0 | 0 | 3 | 2 | 4 |
0 | 1 | 0 | 41/2 | 3 | 6 |
0 | 0 | 1 | -31/2 | -2 | -2 |
Соответствующие уравнения имеют вид:
x1 + 3x4 + 2x5 = 4
x2 + 41/2x4 + 3x5 = 6
x3 - 31/2x4 - 2x5 = -2
Выразим базисные переменные через остальные:
x1 = - 3x4 - 2x5+4
x2 = - 41/2x4 - 3x5+6
x3 = 31/2x4 + 2x5-2
Подставим их в целевую функцию:
F(X) = 4(- 3x4 - 2x5+4) + (- 41/2x4 - 3x5+6) + ( 31/2x4 + 2x5-2) + x4 + x5-4
или
F(X) = - 12x4 - 8x5+20 → max
Система неравенств:
- 3x4 - 2x5+4 ≥ 0
- 41/2x4 - 3x5+6 ≥ 0
31/2x4 + 2x5-2 ≥ 0
Приводим систему неравенств к следующему виду:
3x4 + 2x5<= 4
41/2x4 + 3x5<= 6
- 31/2x4 - 2x5<= -2
F(X) = - 12x4 - 8x5+20 → max
Упростим систему.
3x1 + 2x2<= 4
41/2x1 + 3x2<= 6
- 31/2x1 - 2x2<= -2
F(X) = - 12x1 - 8x2+20 → max
Пример №3. 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
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
|
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
Упростим систему.
x1 + x2 ≤ 12
2x1 - x2 ≤ 8
- 2x1 + 2x2 ≤ 10
F(X) = - 10x1 + x2+20 → max
Пример №4. Преобразовать задачу линейного программирования к стандартной форме:
z = -3x1 + 4x2 – 2x3 + 5x4 → max
4x1 - x2 + 2x3 - x4 = -2
x1 + x2 + 3x3 - x4 ≤ 14
-2x1 + 3x2 – x3 + 2x4 ≥ 2
x1≥ 0, x2 ≥ 0, x3 ≤ 0
Переменная x4 не ограничена по знаку.
Решение проводим с помощью калькулятора.
F(X) = - 3x1 + 4x2 - 2x3 + 5x4 → max при ограничениях:
4x1 - x2 + 2x3 - x4=-2
x1 + x2 + 3x3 - x4≤14
- 2x1 + 3x2 - x3 + 2x4≥2
x3≤0
Для приведения ЗЛП к канонической форме необходимо:
В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≥) вводим базисную переменную x6 со знаком минус. В 4-м неравенстве смысла (≤) вводим базисную переменную x7.
4x1-1x2 + 2x3-1x4 + 0x5 + 0x6 + 0x7 = -2
1x1 + 1x2 + 3x3-1x4 + 1x5 + 0x6 + 0x7 = 14
-2x1 + 3x2-1x3 + 2x4 + 0x5-1x6 + 0x7 = 2
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 0
3. Так как переменная x4, произвольного знака, то она заменяется разностями неотрицательных переменных.
4x1 - x2 + 2x3 - (x8 - x9) = -2
x1 + x2 + 3x3 - (x8 - x9) + x5 = 14
- 2x1 + 3x2 - x3 + 2(x8 - x9) - x6 = 2
x3 + x7 = 0
4. Соответствующая целевая функция примет вид:
F(X) = - 3x1 + 4x2 - 2x3 + 5(x8 - x9)
или
F(X) = - 3x1 + 4x2 - 2x3 + 5x8 - 5x9 → max при ограничениях:
4x1 - x2 + 2x3 - x8 + x9 = -2
x1 + x2 + 3x3 + x5 - x8 + x9 = 14
- 2x1 + 3x2 - x3 - x6 + 2x8 - 2x9 = 2
x3 + x7 = 0
Упростим задачу ЗЛП с заменой всех переменных (сократим их количество).
4x1 - x2 + 2x3 - x7 + x8 = -2
x1 + x2 + 3x3 + x4 - x7 + x8 = 14
- 2x1 + 3x2 - x3 - x5 + 2x7 - 2x8 = 2
x3 + x6 = 0
F(X) = - 3x1 + 4x2 - 2x3 + 5x7 - 5x8 → max
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
4 | -1 | 2 | 0 | 0 | 0 | -1 | 1 | -2 |
1 | 1 | 3 | 1 | 0 | 0 | -1 | 1 | 14 |
-2 | 3 | -1 | 0 | -1 | 0 | 2 | -2 | 2 |
0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
1. В качестве базовой переменной выбираем x1.
Разрешающий элемент РЭ=4.
Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x1 на разрешающий элемент РЭ=4
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x1 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
4 : 4 | -1 : 4 | 2 : 4 | 0 : 4 | 0 : 4 | 0 : 4 | -1 : 4 | 1 : 4 | -2 : 4 |
1-(4·1):4 | 1-(-1·1):4 | 3-(2·1):4 | 1-(0·1):4 | 0-(0·1):4 | 0-(0·1):4 | -1-(-1·1):4 | 1-(1·1):4 | 14-(-2·1):4 |
-2-(4·-2):4 | 3-(-1·-2):4 | -1-(2·-2):4 | 0-(0·-2):4 | -1-(0·-2):4 | 0-(0·-2):4 | 2-(-1·-2):4 | -2-(1·-2):4 | 2-(-2·-2):4 |
0-(4·0):4 | 0-(-1·0):4 | 1-(2·0):4 | 0-(0·0):4 | 0-(0·0):4 | 1-(0·0):4 | 0-(-1·0):4 | 0-(1·0):4 | 0-(-2·0):4 |
1 | -1/4 | 1/2 | 0 | 0 | 0 | -1/4 | 1/4 | -1/2 |
0 | 5/4 | 5/2 | 1 | 0 | 0 | -3/4 | 3/4 | 29/2 |
0 | 5/2 | 0 | 0 | -1 | 0 | 3/2 | -3/2 | 1 |
0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
3. В качестве базовой переменной можно выбрать x5.
4. В качестве базовой переменной можно выбрать x6.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (1,4,5,6).
Соответствующие уравнения имеют вид:
x1 - 1/4x2 + 1/2x3 - 1/4x7 + 1/4x8 = -1/2
11/4x2 + 21/2x3 + x4 - 3/4x7 + 3/4x8 = 141/2
- 21/2x2 + x5 - 11/2x7 + 11/2x8 = -1
x3 + x6 = 0
Выразим базисные переменные через остальные:
x1 = 1/4x2 - 1/2x3 + 1/4x7 - 1/4x8-1/2
x4 = - 11/4x2 - 21/2x3 + 3/4x7 - 3/4x8+141/2
x5 = 21/2x2 + 11/2x7 - 11/2x8-1
x6 = - x3
Подставим их в целевую функцию:
F(X) = - 3( 1/4x2 - 1/2x3 + 1/4x7 - 1/4x8-1/2) + 4x2 - 2x3 + 5x7 - 5x8
или
F(X) = 31/4x2 - 1/2x3 + 41/4x7 - 41/4x8+11/2 → max
Система неравенств:
1/4x2 - 1/2x3 + 1/4x7 - 1/4x8-1/2 ≥ 0
- 11/4x2 - 21/2x3 + 3/4x7 - 3/4x8+141/2 ≥ 0
21/2x2 + 11/2x7 - 11/2x8-1 ≥ 0
- x3 ≥ 0
Приводим систему неравенств к следующему виду:
- 1/4x2 + 1/2x3 - 1/4x7 + 1/4x8 ≤ -1/2
11/4x2 + 21/2x3 - 3/4x7 + 3/4x8 ≤ 141/2
- 21/2x2 - 11/2x7 + 11/2x8 ≤ -1
x3 ≤ 0
F(X) = 31/4x2 - 1/2x3 + 41/4x7 - 41/4x8+11/2 → max
Упростим систему.
- 1/2x1 + x2 - 1/2x3 + 1/2x4 ≤ -1
21/2x1 + 5x2 - 11/2x3 + 11/2x4 ≤ 29
- 5x1 - 3x3 + 3x4 ≤ -2
x2 ≤ 0
F(X) = 31/4x1 - 1/2x2 + 41/4x3 - 41/4x4+11/2 → max