Переход к стандартной форме ЗЛП
СЗЛП — задача линейного программирования вида ax ≥ b или ax ≤ b . где a — матрица коэффициентов, b — вектор ограничений.
Математическая модель ЗЛП называется стандартной, если ограничения в ней представлены в виде линейных неравенств, а целевая функция минимизируется или максимизируется.
- Первая стандартная форма ax ≥ b , F(X) → min.
- Вторая стандартная форма ax ≤ b , F(X) → max.
- Шаг №1
- Шаг №2
- Видеоинструкция
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word . Этот же калькулятор можно использовать при методе перебора опорных решений.
Пример . Дана основная задача линейного программирования. При помощи элементарных преобразований матрицы коэффициентов системы ограничений привести задачу к стандартному виду и решить ее геометрическим методом или доказать, что она не имеет оптимального плана.
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-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-(-6 2 /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-(-6 2 /3· -2 /21): -17 /21 |
| 0 : -17 /21 | 0 : -17 /21 | -17 /21 : -17 /21 | -1 /6 : -17 /21 | -11 /42 : -17 /21 | -6 2 /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 = 3 9 /17
x2 — 5 /34x4 — 3 /34x5 = 1 2 /17
x3 + 7 /34x4 + 11 /34x5 = 8 4 /17
Выразим базисные переменные через остальные:
x1 = — 3 /34x4 + 5 /34x5+3 9 /17
x2 = 5 /34x4 + 3 /34x5+1 2 /17
x3 = — 7 /34x4 — 11 /34x5+8 4 /17
Подставим их в целевую функцию:
F(X) = — 3(- 3 /34x4 + 5 /34x5+3 9 /17) + 13( 5 /34x4 + 3 /34x5+1 2 /17) + (- 7 /34x4 — 11 /34x5+8 4 /17) — 2x4
или
F(X) = — 1 /34x4 + 13 /34x5+12 3 /17 → max
Система неравенств:
— 3 /34x4 + 5 /34x5+3 9 /17 ≥ 0
5 /34x4 + 3 /34x5+1 2 /17 ≥ 0
— 7 /34x4 — 11 /34x5+8 4 /17 ≥ 0
Приводим систему неравенств к следующему виду:
3 /34x4 — 5 /34x5 ≤ 3 9 /17
— 5 /34x4 — 3 /34x5 ≤ 1 2 /17
7 /34x4 + 11 /34x5 ≤ 8 4 /17
F(X) = — 1 /34x4 + 13 /34x5+12 3 /17 → max
Упростим систему.
3x1 — 5x2 ≤ 120
— 5x1 — 3x2 ≤ 38
7x1 + 11x2 ≤ 280
F(X) = — x1 + 13x2+414 → max
Далее систему можно решать геометрическим методом.
Расширенная матрица системы ограничений-равенств данной задачи:
| 2 | 0 | 1 | -1 | 1 | 2 |
| 4 | 1 | 3 | 1 | 2 | 7 |
| -1 | 0 | 1 | 2 | 1 | 2 |
Методом Жордано-Гаусса приведем матрицу к единичной:
Последовательно будем выбирать разрешающий элемент РЭ, который лежит на главной диагонали матрицы.
Разрешающий элемент равен (2).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ — (А*В)/РЭ
РЭ — разрешающий элемент (2), А и В — элементы матрицы, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| 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, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Представим расчет каждого элемента в виде таблицы:
| 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
Получаем новую матрицу:
| 1 | -1 /3 | 1 /3 | 1 /3 | 1 /3 | 1 1 /3 |
| 0 | -2 1 /3 | -1 2 /3 | -4 2 /3 | -3 2 /3 | -10 2 /3 |
| 0 | -3 2 /3 | -4 1 /3 | -1 1 /3 | -2 1 /3 | -13 1 /3 |
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-2 1 /3.
Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-2 1 /3
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
| 1-(0· -1 /3):-2 1 /3 | -1 /3-(-2 1 /3· -1 /3):-2 1 /3 | 1 /3-(-1 2 /3· -1 /3):-2 1 /3 | 1 /3-(-4 2 /3· -1 /3):-2 1 /3 | 1 /3-(-3 2 /3· -1 /3):-2 1 /3 | 1 1 /3-(-10 2 /3· -1 /3):-2 1 /3 |
| 0 : -2 1 /3 | -2 1 /3 : -2 1 /3 | -1 2 /3 : -2 1 /3 | -4 2 /3 : -2 1 /3 | -3 2 /3 : -2 1 /3 | -10 2 /3 : -2 1 /3 |
| 0-(0·-3 2 /3):-2 1 /3 | -3 2 /3-(-2 1 /3·-3 2 /3):-2 1 /3 | -4 1 /3-(-1 2 /3·-3 2 /3):-2 1 /3 | -1 1 /3-(-4 2 /3·-3 2 /3):-2 1 /3 | -2 1 /3-(-3 2 /3·-3 2 /3):-2 1 /3 | -13 1 /3-(-10 2 /3·-3 2 /3):-2 1 /3 |
Получаем новую матрицу:
| 1 | 0 | 4 /7 | 1 | 6 /7 | 2 6 /7 |
| 0 | 1 | 5 /7 | 2 | 1 4 /7 | 4 4 /7 |
| 0 | 0 | -1 5 /7 | 6 | 3 3 /7 | 3 3 /7 |
3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=-1 5 /7.
Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-1 5 /7
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
| 1-(0· 4 /7):-1 5 /7 | 0-(0· 4 /7):-1 5 /7 | 4 /7-(-1 5 /7· 4 /7):-1 5 /7 | 1-(6· 4 /7):-1 5 /7 | 6 /7-(3 3 /7· 4 /7):-1 5 /7 | 2 6 /7-(3 3 /7· 4 /7):-1 5 /7 |
| 0-(0· 5 /7):-1 5 /7 | 1-(0· 5 /7):-1 5 /7 | 5 /7-(-1 5 /7· 5 /7):-1 5 /7 | 2-(6· 5 /7):-1 5 /7 | 1 4 /7-(3 3 /7· 5 /7):-1 5 /7 | 4 4 /7-(3 3 /7· 5 /7):-1 5 /7 |
| 0 : -1 5 /7 | 0 : -1 5 /7 | -1 5 /7 : -1 5 /7 | 6 : -1 5 /7 | 3 3 /7 : -1 5 /7 | 3 3 /7 : -1 5 /7 |
Решение проводим с помощью калькулятора.
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 |
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
4. В качестве базовой переменной можно выбрать x6.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (1,4,5,6).
Соответствующие уравнения имеют вид:
x1 — 1 /4x2 + 1 /2x3 — 1 /4x7 + 1 /4x8 = -1 /2
1 1 /4x2 + 2 1 /2x3 + x4 — 3 /4x7 + 3 /4x8 = 14 1 /2
— 2 1 /2x2 + x5 — 1 1 /2x7 + 1 1 /2x8 = -1
x3 + x6 = 0
Выразим базисные переменные через остальные:
x1 = 1 /4x2 — 1 /2x3 + 1 /4x7 — 1 /4x8 -1 /2
x4 = — 1 1 /4x2 — 2 1 /2x3 + 3 /4x7 — 3 /4x8+14 1 /2
x5 = 2 1 /2x2 + 1 1 /2x7 — 1 1 /2x8-1
x6 = — x3
Подставим их в целевую функцию:
F(X) = — 3( 1 /4x2 — 1 /2x3 + 1 /4x7 — 1 /4x8 -1 /2) + 4x2 — 2x3 + 5x7 — 5x8
или
F(X) = 3 1 /4x2 — 1 /2x3 + 4 1 /4x7 — 4 1 /4x8+1 1 /2 → max
Система неравенств:
1 /4x2 — 1 /2x3 + 1 /4x7 — 1 /4x8 -1 /2 ≥ 0
— 1 1 /4x2 — 2 1 /2x3 + 3 /4x7 — 3 /4x8+14 1 /2 ≥ 0
2 1 /2x2 + 1 1 /2x7 — 1 1 /2x8-1 ≥ 0
— x3 ≥ 0
Приводим систему неравенств к следующему виду:
— 1 /4x2 + 1 /2x3 — 1 /4x7 + 1 /4x8 ≤ -1 /2
1 1 /4x2 + 2 1 /2x3 — 3 /4x7 + 3 /4x8 ≤ 14 1 /2
— 2 1 /2x2 — 1 1 /2x7 + 1 1 /2x8 ≤ -1
x3 ≤ 0
F(X) = 3 1 /4x2 — 1 /2x3 + 4 1 /4x7 — 4 1 /4x8+1 1 /2 → max
Упростим систему.
— 1 /2x1 + x2 — 1 /2x3 + 1 /2x4 ≤ -1
2 1 /2x1 + 5x2 — 1 1 /2x3 + 1 1 /2x4 ≤ 29
— 5x1 — 3x3 + 3x4 ≤ -2
x2 ≤ 0
F(X) = 3 1 /4x1 — 1 /2x2 + 4 1 /4x3 — 4 1 /4x4+1 1 /2 → max