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

Пример №1. Привести к канонической форме следующую ЗЛП.
F = 2x1 - x2 + 4x3 -2x4 → min
при ограничениях:
7x1 –x2 +5x3 + x4 = -10
3x1 +5x2 -9x3 + 2x4 = 6
x1 –x2 -2x3 + 6x4 ≥ 7
x1 +x2 -5x3 ≤ 11
7x1 –x2 -3x3 - x4 ≤ 9
x1 ≥0 , x2 ≥0 (обратите внимание, что переменные x3 и x4 имеют произвольный знак)

Решение находим с помощью калькулятора. Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции
- F = -2x1 + x2 - 4x3 +2x4 → max

2. В левые части трех последних неравенств внести дополнительные переменные x5, x6, x7 со знаком плюс или минус в зависимости от знака неравенства.
7x1 –x2 +5x3 + x4 = -10
3x1 +5x2 -9x3 + 2x4 = 6
x1 –x2 -2x3 + 6x4 –x5 = 7
x1 +x2 -5x3 +x6 = 11
7x1 –x2 -3x3 - x4 +x7 = 9
x1 ≥0 , x2 ≥0, x5 ≥0 , x6 ≥0, x7 ≥0

3. Так как переменные x3 и x4 произвольного знака, то они заменяются разностями неотрицательных переменных.
7x1 –x2 +5(x8 – x9) + (x10 – x11) = -10
3x1 +5x2 -9(x8 – x9) + 2(x10 – x11) = 6
x1 –x2 -2(x8 – x9) + 6(x10 – x11) –x5 = 7
x1 +x2 -5(x8 – x9) +x6 = 11
7x1 –x2 -3(x8 – x9) - (x10 – x11) +x7 = 9
x1 ≥0 , x2 ≥0, x5 ≥0 , x6 ≥0, x7 ≥0 , x8 ≥0, x9 ≥0 , x10 ≥0, x11 ≥0

4. Соответствующая целевая функция примет вид:
- F = -2x1 + x2 - 4(x8 – x9) +2(x10 – x11) → max

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

Перейти к онлайн решению своей задачи

Пример №2. Преобразовать следующие задачи ЛП к канонической форме и решить их симплекс-методом.

загрузка...