14. В чем особенности симплекс метода?
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве.
15. Условие допустимости симплекс-метода.
Два правила выбора вводимых и исключающих переменных в симплекс-методе называются условием оптимальности и условием допустимости.
Условие оптимальности. Выбор переменной, вводимой в список базисных – просматривается последняя строка симплекс-таблицы, среди элементов этой строки выбирается максимальный по абсолютной величине отрицательный элемент. Столбец, в котором стоит этот элемент называется разрешающим.
Условие допустимости. Находят отношения элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент и 0 результат полагают равным +oo. Среди полученных отношений выбирают минимальное. Строка, соответствующая минимальному отношению называется разрешающей. Пусть это будет строка q. Базисная переменная xq соответствующая этой строке выводится из списка базисных.
16. Может ли в ограничениях присутствовать неравенства при решении задачи симплекс методом?
Нет, так как симплекс-метод работает только с задачей в каноническом виде, где в ограничениях могут быть только равенства.
17. Могут ли, при решении задачи симплекс методом, присутствовать отрицательные переменные?
Да, могут.
18. Частные случаи использования симплекс-метода.
Следующие особые случаи, встречающиеся при использовании симплекс-метода:
1) вырожденность
Если на следующей итерации одна из базисных переменных равна нулю, то новое решение называют вырожденным. Наличие вырожденного решения не свидетельствует о какой-либо «опасности» для исследователя и вызывает лишь некоторое неудобство в теоретическом отношении. С практической точки зрения специфика ситуации целиком объясняется наличием в модели, по крайней мере, одного избыточного ограничения.
2) альтернативные оптимальные решения;
3) неограниченные решения;
Когда график целевой функции параллелен одной из прямой ограничений. Тогда задача имеет бесконечное количество решений.
Или когда пространство решений по крайней мере в одном направлении не ограничено.
4) отсутствие допустимых решений.
19. Двойственная задача линейного программирования.
Любой задаче линейного программирования, называемой исходной или прямой, можно поставить в соответствие другую задачу, которая называется двойственной или сопряженной. Обе эти задачи образуют пару двойственных задач. Каждая из задач является двойственной к другой задаче рассматриваемой пары.
В теории двойственности используются четыре пары двойственных задач:
20. Соотношения между решениями исходной и двойственной задач.
Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач. Решив одну из пары двойственных задач, можно или найти оптимальное решение другой, не решая ее, или установив его отсутствие.
Теорема (первая теорема двойственности). Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение; причем значения целевых функций задач на своих оптимальных решениях совпадают.
Если одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.
Теорема (вторая теорема двойственности). Для оптимальных планов прямой и двойственной задачи в каждой паре двойственных условий только одно условие может быть неактивным (нежестким, свободным).
Вторая теорема двойственности иначе называется принципом дополняющей нежесткости. Для ее формулировки нам потребуется ввести классификацию ограничений.
Если взять конкретный план задачи линейного программирования и подставить его в некоторое ограничение, имеющее вид нестрогого неравенства, то оно будет выполняться либо как равенство, либо как строгое неравенство. В случае равенства ограничение для этого плана будет активным (в другой терминологии жестким, связанным), а при неравенстве неактивным (нежестким, свободным)