III. Целочисленное линейное программирование (ЦЛП)

Введение

Предмет методов оптимизации. Задачи оптимизации, их классификация.

I. Линейное программирование (ЛП)

1. Примеры содержательных задач, приводящих к задачам ЛП.
2. Общая, каноническая, симметричная задачи ЛП. Теоремы эквивалентности.
3. Базисные решения. Теорема о конечности множества базисных решений.
4. Базисные решения. Теорема о существовании оптимального базисного решения.
5. Критерии разрешимости канонической и общей задач ЛП.
6. Приведенная задача ЛП. Симплекс-метод. Условие оптимальности базисного решения. Условие неразрешимости задачи ЛП.
7. Приведенная задача ЛП. Симплекс-метод. Правило выбора ведущей строки. Теорема об улучшении базисного решения.
8. О конечности симплекс-метода. Лексикографический прямой симплекс-метод, его конечность.
9. Каноническая задача ЛП. Метод искусственного базиса. Критерий существования допустимых решений канонической задачи ЛП.
10. Метод искусственного базиса. Теорема о преобразовании канонической задачи ЛП в эквивалентную ей приведенную задачу ЛП.

II. Двойственность в линейном программировании

1. Правила построения двойственной задачи для общей задачи ЛП. Симметричные двойственные задачи, основное неравенство двойственности.
2. Теоремы двойственности. I и II критерий оптимальности.
3. Малая теорема двойственности. Теорема о причинах неразрешимости двойственных задач ЛП. Классификация пар двойственных задач.
4. Экономическая интерпретация пары двойственных задач, первой и второй теорем двойственности.
5. Лемма о планах одинаковой структуры. Третья теорема двойственности.
6. Двойственный симплекс-метод. Его обоснование. Построение начального двойственно допустимого решения.
7. Лексикографический двойственный симплекс-метод.

III. Целочисленное линейное программирование (ЦЛП)

1. Задача ЦЛП. Идея метода отсечений. Правильное отсечение. Отсечение Данцига.
2. Теорема об отсечении Гомори. Первый алгоритм Гомори.
3. Теорема о конечности первого алгоритма Гомори.
4. Идея метода ветвей и границ. Алгоритм Лэнд и Дойга для решения задачи ЦЛП.