Как привести каноническую задачу линейного программирования к стандартной форме

Пример №1. Привести следующую КЗЛП к задаче в стандартной форме:
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. Дана основная задача линейного программирования. При помощи элементарных преобразований матрицы коэффициентов системы ограничений, привести задачу стандартному виду и решить ее геометрическим методом. Методом искусственного базиса получить каноническую задачу (или доказать несовместимость этой системы). Решить полученную модель с помощью симплекс-таблиц (или доказать, что она не имеет оптимального плана).
Решение.
Расширенная матрица системы ограничений-равенств данной задачи:

3-11114
11-62-104
4-5-30-1-8

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

2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-21/3.
Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-21/3
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

1-(0 • -1/3):-21/3-1/3-(-21/3-1/3):-21/31/3-(-12/3-1/3):-21/31/3-(-42/3-1/3):-21/31/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 04/7 16/7 26/7
0 15/7 2 14/7 44/7
0 0 -15/7 6 33/7 33/7

3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=-15/7.
Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-15/7
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

1-(0 • 4/7):-15/7 0-(0 • 4/7):-15/74/7-(-15/74/7):-15/7 1-(6 • 4/7):-15/76/7-(33/74/7):-15/7 26/7-(33/74/7):-15/7
0-(0 • 5/7):-15/7 1-(0 • 5/7):-15/75/7-(-15/75/7):-15/7 2-(6 • 5/7):-15/7 14/7-(33/75/7):-15/7 44/7-(33/75/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

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (1, 2, 3).
Соответствующие уравнения имеют вид:
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
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1110012
2-10108
-2200110

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

2. В качестве базовой переменной можно выбрать x4.
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
загрузка...