Постановка ЗЛП

В общем случае ЗЛП ставится следующим образом.

Максимизировать (минимизировать) функцию

(1)

при ограничениях

где - управляющие переменные или решения задачи (1)-(4), ;

- параметры, ;

- целевая функция или критерий эффективности задачи.

Функция (1) – линейная, ограничения (2)-(4) – линейные. Задача содержит переменных и ограничений.

Решить ЗЛП – значит найти значения управляющих переменных , , удовлетворяющих ограничениям (2)-(4), при которых целевая функция (1) принимает минимальное или максимальное значение.

Основные этапы построения математической модели

1. Определение цели

2. Определение параметров модели

3. Формирование управляющих переменных, изменение значения которых приближает к поставленной цели

4. Определение области допустимых решений – ограничений, которым должны удовлетворять управляющие переменные

5. Выявление неизвестных факторов – величин, которые могут изменяться случайным или неопределенным образом

6. Выражение цели через управляющие переменные, параметры и неизвестные факторы – формирование целевой функции.

Основная ЗЛП

Для переменных областью допустимых решений является многомерный многогранник, подобный симплексу. Оптимальное решение, как правило, это вершина (граничная точка) такого многогранника. Симплекс-метод заключается в последовательном целенаправленном обходе вершин симплекса. В каждой следующей граничной точке симплекса значение целевой функции, в общем случае, улучшается.

Для применения симплекс-метода ЗЛП следует записать в канонической форме.