Задание ЭММ. Задание 2 ЛП МЛ-2021 (1). Задание Методы решения задач линейного и целочисленного программирования

Название	Задание Методы решения задач линейного и целочисленного программирования
Анкор	Задание ЭММ
Дата	01.12.2022
Размер	64.08 Kb.
Формат файла
Имя файла	Задание 2 ЛП МЛ-2021 (1).docx
Тип	Методические указания #823981

Задание № 2.

Методы решения задач линейного и целочисленного программирования.

Для предложенного варианта необходимо:
1. Привести математическую постановку задачи линейного программирования (ЛП).
2. Привести графическую интерпретацию задачи ЛП. Найти графическим способом решение задачи ЛП.
3. Записать задачу ЛП в двойственной формулировке.
4. Привести графическую интерпретацию двойственной задачи ЛП. Графическим способом найти решение двойственной задачи ЛП.
5. Решить задачу линейного программирования с помощью прямого и двойственного симплекс-методов. Сравнить полученные решения с графическими решениями (п.п. 2.1.2., 2.1.3.).
6. Привести математическую постановку задачи линейного целочисленного программирования (ЛЦП).
7. Привести графическую интерпретацию задачи ЛЦП. Выделить множество допустимых точек. Графическим способом найти решение задачи ЛЦП.
8. Найти решение задачи ЛЦП с помощью алгоритма Гомори. Сравнить полученное решение с графическим решением.
9. Найти решение задачи ЛЦП с помощью алгоритма ветвей и границ (алгоритм Ленг и Дойг).
Методические указания к выполнению задания №2.

2.3 Вопросы для самоконтроля.

Что называется допустимым базисным решением? Каким допустимым точкам эти решения соответствуют?
Как связаны между собой прямая и двойственная задачи ЛП? Сформулируйте основную теорему линейного программирования.
Какие переменные называются базисными? Какие свободными? Какая между ними связь?
Почему симплекс – таблица одновременно описывает прямую и двойственную задачи?
Каков геометрический смысл ведущего преобразования? Как выглядит схема ведущего преобразования?
Какова геометрическая идея симплекс – метода? Как эта идея реализуется?
Как выбирается ведущий элемент при получении базисного решения, при получении оптимального решения?
Как найти оптимальное решение двойственной задачи, решая соответствующую прямую задачу, и наоборот? В чем различие прямого и двойственного симплекс – метода?
В каком случае целесообразнее применять прямой симплекс – метод, а в каком - двойственный симплекс – метод?
Как выявить ситуации неразрешимости задачи ЛП при использовании симплекс – метода?
Когда возникает зацикливание симплекс – метода и как его устранить?
В чем состоит геометрический смысл метода Гомори решения задачи ЛЦП? Как эта идея реализуется?
Какова общая идея метода ветвей и границ? Как эта идея применяется к решению задачи ЛЦП?