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

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

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

Задача линейного программирования

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

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

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

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

 

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

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

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

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

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

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

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

Основные положения теории линейного программирования

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

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

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

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

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

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

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

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

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

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

  • I Перевод задачи ЛП в каноническую форму
  • II Выбор начального базисного решения
Алгоритм симплекс-метода
Алгоритм симплекс-метода
  • III Представление ЦФ в виде уравнения
III Представление ЦФ в виде уравнения
III Представление ЦФ в виде уравнения
  • IV Заполнение исходной симплекс-таблицы
Заполнение исходной симплекс-таблицы
Заполнение исходной симплекс-таблицы
  • V Проверка условия оптимальности (невыполнение условия – переход к п. VI)
Проверка условия оптимальности (невыполнение условия – переход к п. VI)
Проверка условия оптимальности (невыполнение условия – переход к п. VI)
  • VI Улучшение допустимого базисного решения
Улучшение допустимого базисного решения
Улучшение допустимого базисного решения
  • VII Преобразование симплекс-таблицы методом Гаусса-Жордана
Преобразование симплекс-таблицы методом Гаусса-Жордана
Преобразование симплекс-таблицы методом Гаусса-Жордана

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

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