Главная
Случайная страница
Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
III. Целочисленное линейное программирование (ЦЛП)
Введение
Предмет методов оптимизации. Задачи оптимизации, их классификация.
I. Линейное программирование (ЛП)
- Примеры содержательных задач, приводящих к задачам ЛП.
- Общая, каноническая, симметричная задачи ЛП. Теоремы эквивалентности.
- Базисные решения. Теорема о конечности множества базисных решений.
- Базисные решения. Теорема о существовании оптимального базисного решения.
- Критерии разрешимости канонической и общей задач ЛП.
- Приведенная задача ЛП. Симплекс-метод. Условие оптимальности базисного решения. Условие неразрешимости задачи ЛП.
- Приведенная задача ЛП. Симплекс-метод. Правило выбора ведущей строки. Теорема об улучшении базисного решения.
- О конечности симплекс-метода. Лексикографический прямой симплекс-метод, его конечность.
- Каноническая задача ЛП. Метод искусственного базиса. Критерий существования допустимых решений канонической задачи ЛП.
- Метод искусственного базиса. Теорема о преобразовании канонической задачи ЛП в эквивалентную ей приведенную задачу ЛП.
II. Двойственность в линейном программировании
- Правила построения двойственной задачи для общей задачи ЛП. Симметричные двойственные задачи, основное неравенство двойственности.
- Теоремы двойственности. I и II критерий оптимальности.
- Малая теорема двойственности. Теорема о причинах неразрешимости двойственных задач ЛП. Классификация пар двойственных задач.
- Экономическая интерпретация пары двойственных задач, первой и второй теорем двойственности.
- Лемма о планах одинаковой структуры. Третья теорема двойственности.
- Двойственный симплекс-метод. Его обоснование. Построение начального двойственно допустимого решения.
- Лексикографический двойственный симплекс-метод.
III. Целочисленное линейное программирование (ЦЛП)
- Задача ЦЛП. Идея метода отсечений. Правильное отсечение. Отсечение Данцига.
- Теорема об отсечении Гомори. Первый алгоритм Гомори.
- Теорема о конечности первого алгоритма Гомори.
- Идея метода ветвей и границ. Алгоритм Лэнд и Дойга для решения задачи ЦЛП.
|