Переход к стандартной форме ЗЛП

СЗЛП - задача линейного программирования вида ax ≥ b или ax ≤ b. где a - матрица коэффициентов, b - вектор ограничений.
Математическая модель ЗЛП называется стандартной, если ограничения в ней представлены в виде линейных неравенств, а целевая функция минимизируется или максимизируется.

Назначение сервиса. Онлайн-калькулятор предназначен для приведения КЗЛП к СЗЛП путем преобразования матрицы a к единичной. При этом возможны две стандартных формы:

  1. Первая стандартная форма ax ≥ b, F(X) → min.
  2. Вторая стандартная форма ax ≤ b, F(X) → max.
Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word.
Количество переменных
Количество строк (количество ограничений)
Для всех переменных xi ≥ 0 .
Как привести каноническую задачу линейного программирования к стандартной форме
Привести к канонической форме

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

Расширенная матрица системы ограничений-равенств данной задачи:

16-1-1-12
5-12-120-4
3-1-20-1-7

Приведем систему к единичной матрице методом жордановских преобразований.
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

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-(-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

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

загрузка...