Построить график функции Точки разрыва функции Построение графика методом дифференциального исчисления Упростить выражение
Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

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

СЗЛП - задача линейного программирования вида 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 : 16 : 1-1 : 1-1 : 1-1 : 12 : 1
5-(1·5):1-12-(6·5):1-1-(-1·5):12-(-1·5):10-(-1·5):1-4-(2·5):1
3-(1·3):1-1-(6·3):1-2-(-1·3):10-(-1·3):1-1-(-1·3):1-7-(2·3):1
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-42.
Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-42
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x2 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
1-(0·6):-426-(-42·6):-42-1-(4·6):-42-1-(7·6):-42-1-(5·6):-422-(-14·6):-42
0 : -42-42 : -424 : -427 : -425 : -42-14 : -42
0-(0·-19):-42-19-(-42·-19):-421-(4·-19):-423-(7·-19):-422-(5·-19):-42-13-(-14·-19):-42

Получаем новую матрицу:
10-3/70-2/70
01-2/21-1/6-5/421/3
00-17/21-1/6-11/42-20/3

3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=-17/21.
Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=-17/21
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x3 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
1-(0·-3/7):-17/210-(0·-3/7):-17/21-3/7-(-17/21·-3/7):-17/210-(-1/6·-3/7):-17/21-2/7-(-11/42·-3/7):-17/210-(-62/3·-3/7):-17/21
0-(0·-2/21):-17/211-(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/211/3-(-62/3·-2/21):-17/21
0 : -17/210 : -17/21-17/21 : -17/21-1/6 : -17/21-11/42 : -17/21-62/3 : -17/21

Получаем новую матрицу:
1003/34-5/3460/17
010-5/34-3/3419/17
0017/3411/34140/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. Дана основная задача линейного программирования. При помощи элементарных преобразований матрицы коэффициентов системы ограничений, привести задачу стандартному виду и решить ее геометрическим методом. Методом искусственного базиса получить каноническую задачу (или доказать несовместимость этой системы). Решить полученную модель с помощью симплекс-таблиц (или доказать, что она не имеет оптимального плана).
Решение.
Расширенная матрица системы ограничений-равенств данной задачи:

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/7·4/7):-15/7 1-(6·4/7):-15/76/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/75/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
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем 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-12000-11-2
113100-1114
-23-10-102-22
001001000
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной выбираем x1.
Разрешающий элемент РЭ=4.
Строка, соответствующая переменной x1, получена в результате деления всех элементов строки x1 на разрешающий элемент РЭ=4
На месте разрешающего элемента получаем 1.
В остальных клетках столбца x1 записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
4 : 4-1 : 42 : 40 : 40 : 40 : 4-1 : 41 : 4-2 : 4
1-(4·1):41-(-1·1):43-(2·1):41-(0·1):40-(0·1):40-(0·1):4-1-(-1·1):41-(1·1):414-(-2·1):4
-2-(4·-2):43-(-1·-2):4-1-(2·-2):40-(0·-2):4-1-(0·-2):40-(0·-2):42-(-1·-2):4-2-(1·-2):42-(-2·-2):4
0-(4·0):40-(-1·0):41-(2·0):40-(0·0):40-(0·0):41-(0·0):40-(-1·0):40-(1·0):40-(-2·0):4
Получаем новую матрицу:
1-1/41/2000-1/41/4-1/2
05/45/2100-3/43/429/2
05/200-103/2-3/21
001001000
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
Яндекс 360 для бизнеса
  • Бесконечный почтовый ящик;
  • Объем облачного хранилища от 100 Гб;
  • Загрузка больших файлов — от 1 ГБ
  • Поддержка файлов MS Office
  • Трансляции и их планирование в календаре
Подробнее
Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее
Курсовые на заказ