Линейное программирование
Задача линейного программирования
- Общая постановка ЗЛП: функция цели, система ограничений
- Каноническая (основная) форма записи ЗЛП, симметричная (стандартная) форма ЗЛП
- Допустимое решение (план) ЗЛП
- Оптимальное решение ЗЛП
- Правила приведения к канонической форме ЗЛП
Пример – приведение к канонической форме
Линейное программирование. Графический метод решения ЗЛП.
Особый случай ЗЛП – нет решений (графический метод)
Особый случай ЗЛП – решение неограниченно (графический метод)
Особый случай ЗЛП – бесконечное множество решений
Основные положения теории линейного программирования
- 1. Множество М всех планов ЗЛП выпукло
- 2. Замкнутую многогранную область М порождает конечное число особых (крайних) точек – вершин полиэндра
- 3. Если существуют допустимые планы, то существуют базисные (опорные) планы – вершины области М
- 4. Оптимальное решение находится среди базисных (опорных) решений
Блок-схема алгоритма решения ЗЛП аналитическими методами
Выбор начального базисного решения
Пример выбора начального базисного решения
Пример решения ЗЛП симплекс-методом
Алгоритм симплекс-метода
- I Перевод задачи ЛП в каноническую форму
- II Выбор начального базисного решения
- III Представление ЦФ в виде уравнения
- IV Заполнение исходной симплекс-таблицы
- V Проверка условия оптимальности (невыполнение условия – переход к п. VI)
- VI Улучшение допустимого базисного решения
- VII Преобразование симплекс-таблицы методом Гаусса-Жордана
Получение нового базисного решения – переход к п. V
