В. 10 Алгоритм приведения задач ЛП к каноническому виду

Любую задачу ЛП можно решить симплексным методом. Для начала её нужно привести к каноническому виду.

Правила:

1) если исходная задача на максимум, то коэффициенты целевой функции умножаем на «-1» и получаем задачу на минимум.

2x₁-x₂→max

-2x₁+x₂→min

2) если есть ограничения типа “≥”, то из левых частей каждого из таких ограничений вычитаем по одной дополнительной переменной и ставим знак “=”. Для каждого ограничения даётся своя новая переменная.

2x₁+x₂≥5

2x₁+x₂-x₃=5

3) если есть ограничения типа “≤”, то к левым частям каждого из таких ограничений прибавляем по одной дополнительной переменной и ставим знак “=”.

2x₁+x₂≤5

2x₁+x₂+x₃=5

4) если некоторые переменные x_j имеют значение “≤0”, то мы должны заменить их на “-x_j”, тогда ограничения станут правильными.

x_j ≤0

x_j’ = - x_j

x_j’≥0

5) если переменная x_j может иметь любой знак, то заменяем его на разность 2-х переменных, которые не отрицательны.

Например:

Пример в тетради!

Замечание: при приведении к каноническому виду количество ограничений не меняется, количество переменных может увеличиться.