Ответить на вопросы.
1. Какие вы знаете методы нахождения опорных планов?
2. Расскажите об алгоритме метода искусственного базиса.
3. Для каких ЗЛП используется метод искусственного базиса?
4. Когда задача не имеет решения?
5. Сформулируйте правило перехода от одного опорного плана к другому.
6. Что делать, когда из базиса не выводятся все искусственные переменные?
7. Какие задачи линейного программирования называются двойственными?
8. Сформулируйте правила построения двойственных задач.
9. Как вид ограничений двойственной задачи связан с ограничениями
неотъемлемости соответствующей переменной в исходной задаче?
10. Какие бывают формы двойственных задач?
11. Сформулируйте первую теорему двойственности.
12. Сформулируйте вторую теорему двойственности.
13. Дайте экономическую интерпретацию двойственной задачи.
14. Какой план называется псевдопланом?
15. В чем состоят особенности двойственного симплекс-метода?
16. Как по решению прямой (двойственной) задачи найти решение двойственной
(прямой) задачи?
17. Когда задача не имеет решения?
18. Опишите алгоритм двойственного симплекс-метода.
Ответы
Ответ:
1Один из методов нахождения опорных планов - это метод искусственного базиса.
2Метод искусственного базиса используется для нахождения начального опорного плана в симплекс-методе. Суть метода заключается в добавлении к системе ограничений искусственных переменных, которые обеспечивают наличие единичной матрицы в левой части расширенной матрицы системы ограничений. Затем решается вспомогательная задача линейного программирования с целевой функцией, равной сумме искусственных переменных. Если оптимальное значение этой функции равно нулю, то соответствующий опорный план является допустимым для исходной задачи.
3Метод искусственного базиса используется для задач линейного программирования, в которых нет очевидного начального опорного плана.
4Задача не имеет решения, если она является недопустимой (нет ни одного допустимого плана, удовлетворяющего всем ограничениям) или неограниченной (целевая функция может принимать бесконечно большие или малые значения).
5Правило перехода от одного опорного плана к другому основано на выборе разрешающего элемента в симплекс-таблице и проведении операций над строками для получения новой единичной матрицы в левой части таблицы.
6Если после решения вспомогательной задачи в методе искусственного базиса из базиса не выводятся все искусственные переменные, то это означает, что исходная задача является недопустимой.
7Двойственными называются пары задач линейного программирования, связанные определенными отношениями между коэффициентами целевых функций и правых частей ограничений.
8-
9Если переменная в прямой задаче имеет ограничение неотъемлемости (неотрицательность или неопределенность), то соответствующее ограничение в двойственной задаче имеет противоположный знак: ограничение типа “больше или равно” для неотрицательных переменных и ограничение типа “меньше или равно” для неопределенных переменных.
10Двойственные задачи могут быть как в канонической форме (с ограничениями типа “равенство” и переменными, ограниченными снизу), так и в стандартной форме (с ограничениями типа “меньше или равно” и переменными, ограниченными снизу).
11Первая теорема двойственности утверждает, что если прямая задача имеет оптимальное решение, то двойственная задача также имеет оптимальное решение, причем значения их целевых функций совпадают.
12Вторая теорема двойственности утверждает, что если прямая задача является неограниченной (целевая функция может принимать бесконечно большие значения), то двойственная задача является недопустимой (не имеет допустимых решений).
13Экономическая интерпретация двойственной задачи заключается в том, что она представляет собой задачу определения оптимальных цен на ресурсы, используемые в прямой задаче.
14Псевдопланом называется план, который является допустимым для прямой задачи, но не является допустимым для двойственной задачи.
15Особенностью двойственного симплекс-метода является то, что он используется для решения двойственных задач линейного программирования. В отличие от обычного симплекс-метода, который начинает работу с допустимого базисного решения и на каждом шаге улучшает значение целевой функции, двойственный симплекс-метод начинает работу с оптимального базисного решения и на каждом шаге улучшает допустимость решения.
16По решению прямой (двойственной) задачи можно найти решение двойственной (прямой) задачи, используя соотношения между переменными и двойственными оценками. Если x - оптимальное решение прямой задачи, а y - оптимальное решение двойственной задачи, то соответствующие элементы векторов x и y удовлетворяют условиям дополняющей нежесткости: x[i] * y[i] = 0 для всех i.
17Задача не имеет решения, если она является недопустимой (нет ни одного допустимого плана, удовлетворяющего всем ограничениям) или неограниченной (целевая функция может принимать бесконечно большие или малые значения).
18
1Найти оптимальное базисное решение для двойственной задачи. Это может быть сделано, например, с помощью метода искусственного базиса.
2Проверить допустимость текущего решения. Если все переменные удовлетворяют ограничениям неотъемлемости (неотрицательность или неопределенность), то текущее решение является оптимальным, и алгоритм завершается.
3Выбрать переменную, которая нарушает ограничения неотъемлемости (например, отрицательную переменную в задаче с ограничениями типа “больше или равно”). Эта переменная становится разрешающей.
4Найти строку, которая будет исключена из базиса. Для этого необходимо выбрать строку, для которой отношение правой части ограничения к соответствующему элементу в столбце разрешающей переменной является минимальным среди всех положительных элементов этого столбца.
5Провести операции над строками симплекс-таблицы, чтобы получить новую единичную матрицу в левой части таблицы.
6Повторить шаги 2-5 до тех пор, пока не будет найдено оптимальное решение или пока не будет установлено, что задача является недопустимой или неограниченной.
Объяснение:
.