Алгоритм перехода к канонической форме ЗЛП

1. Если требуется найти минимум , то заменяя на , переходят к задаче максимизации, так как .

2. Если ограничение содержит неравенство со знаком , то от него переходят к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную.

3. Если ограничение содержит неравенство со знаком , то от него переходят к равенству, вычитая из левой части дополнительную неотрицательную переменную.

1. Если в задаче какая-либо из переменных произвольна, то от нее избавляются, заменяя разностью двух других неотрицательных переменных. Например, для произвольной переменной полагают , где .

ПРИМЕР

Записать в канонической форме задачу

Решение

1.

2.

3.

4. - произвольная переменная

ОЗЛП не всегда имеет решение:

· уравнения могут оказаться несовместными;

· уравнения могут оказаться совместными, но не в области неотрицательных решений;

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

Симплекс-метод является методом направленного перебора решений системы. Каждое следующее решение улучшает значение целевой функции.

· Определение начального решения, удовлетворяющего ограничениям ОЗЛП

· Последовательное улучшение начального решения и получение оптимального решения задачи.