Линейное программирование

    Линейное программирование

 

Задача линейного программирования
Общая постановка ЗЛП: функция цели, система ограничений
Каноническая (основная) форма записи ЗЛП, симметричная (стандартная) форма ЗЛП
Допустимое решение (план) ЗЛП
Оптимальное решение ЗЛП
Правила приведения к канонической форме ЗЛП
Пример – приведение к канонической форме

 

                                               Пример – приведение к канонической форме

                                            Пример – приведение к канонической форме

 

Линейное программирование. Графический метод решения ЗЛП.

Графический метод решения ЗЛП 

 

Особый случай ЗЛП – нет решений (графический метод)

 

  Особый случай ЗЛП – нет решений (графический метод)

 

Особый случай ЗЛП – решение неограниченно (графический метод)

                        Особый случай ЗЛП – решение неограниченно (графический метод)

 

Особый случай ЗЛП – бесконечное множество решений

                   Особый случай ЗЛП – бесконечное множество решений

 

• 1. Множество М всех планов ЗЛП выпукло
• 2. Замкнутую многогранную область М порождает конечное число особых (крайних) точек – вершин полиэндра
• 3. Если существуют допустимые планы, то существуют базисные (опорные) планы – вершины области М
• 4. Оптимальное решение находится среди базисных (опорных) решений

Блок-схема алгоритма решения ЗЛП аналитическими методами

Блок-схема алгоритма решения ЗЛП аналитическими методами

 

Выбор начального базисного решения

 Выбор начального базисного решения

 

Пример выбора начального базисного решения

 

                                Пример выбора начального базисного решения

Пример решения ЗЛП симплекс-методом

Пример решения ЗЛП симплекс-методом

 

Алгоритм симплекс-метода

• I Перевод задачи ЛП в каноническую форму
• II Выбор начального базисного решения

Алгоритм симплекс-метода

• III Представление ЦФ в виде уравнения

III Представление ЦФ в виде уравнения

 

• IV Заполнение исходной симплекс-таблицы

Заполнение исходной симплекс-таблицы

 

• V Проверка условия оптимальности (невыполнение условия – переход к п. VI)

Проверка условия оптимальности (невыполнение условия – переход к п. VI)

 

• VI Улучшение допустимого базисного решения

Улучшение допустимого базисного решения

 

• VII Преобразование симплекс-таблицы методом Гаусса-Жордана

Преобразование симплекс-таблицы методом Гаусса-Жордана

 

Получение нового базисного решения – переход к п. V