Линейное программирование. Лекция 2

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

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

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

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

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

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

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

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

1. Множество М всех планов ЗЛП выпукло
2.

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

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

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

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

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

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

Алгоритм симплекс-метода (продолжение)

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

Алгоритм симплекс-метода (продолжение)

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

Алгоритм симплекс-метода (продолжение)

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

Алгоритм симплекс-метода (продолжение)

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

Алгоритм симплекс-метода (продолжение)

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