- •Глава 1
- •Глава 2
- •2.3. Повысится ли эффективность метода поразрядного поиска, если шаг поиска ∆ последовательно уменьшать не в четыре, а в какое-либо другое количество раз?
- •2.4. Может ли применение методов исключения отрезков привести к неверному определению х*, если функция f(X) не унимодальная. Ответ пояснить рисунком.
- •2.5. Зависит ли точность определения х*, которую гарантируют методы дихотомии и золотого сечения в результате n вычислений f(X), от конкретной функции f(X)?
- •Глава 3
- •Глава 4
- •Что такое скорость сходимости минимизирующей последовательности? Какие скорости сходимости Вы знаете?
- •5.10. Какие направления дифференцируемой в точке xk функции f(X) называются направлениями убывания? Каков геометрический смысл направления убывания?
- •Глава 5
- •Привести пример минимизирующей последовательности, не сходящейся к точке минимума.
- •5.12. Когда говорят, что сильно выпуклая функция f(X) имеет овражный характер? Какие задачи минимизации называются хорошо обусловленными, а какие − плохо обусловленными?
- •5.17. Чем отличаются классический и обобщенный методы Ньютона для сильновыпуклой дважды дифференцируемой функции многих переменных?
- •5.18. Сформулировать общий принцип построения квазиньютоновских методов. Какую скорость сходимости следует ожидать от квазиньютоновских методов? Оценить их трудоемкость.
- •Глава 6
- •6.11. Как можно дополнительно повысить эффективность поиска точки минимума целевой функции, которая ищется методом циклического покоординатного спуска?
- •6.12 В чём состоит стратегия метода Хука-Дживса?
- •Глава 7
- •Глава 8
- •8.5. Какие задачи линейного программирования можно решить графически?
- •8.6. Описать алгоритм графического решения задачи линейного программирования.
- •8.7. Дать определение плана и оптимального плана задачи линейного программирования.
- •8.8. Какую задачу линейного программирования можно решить с помощью симплекс-метода?
- •8.18. Алгоритм решения злп методом искусственного базиса (м-методом)
8.18. Алгоритм решения злп методом искусственного базиса (м-методом)
В каждое i-ое ограничение вводим искусственную переменную Xn+i >0. Всего m новых искусственных переменных.
В целевую функцию F вводим m дополнительных отрицательных слагаемых вида : -M*Xn+1 -M*Xn+2 ...-M*Xn+m , где М - произвольная очень большая константа.
Получим новую ЗЛП вида : F(X) = c1Х1 + ... + сnXn -M*Xn+1 - ... -M*Xn+m => max ai,1X1+ ... + ai,nXn +Xn+i = bi , (i=1,m) Xj >0 , (j=1,n+m) Новая система ограничений характерна тем, что искусственные переменные сразу можно взять в качестве базисных: Xn+i = bi - ai,1X1 - ... - ai,nXn , (i=1,m)
Формируем начальное базисное решение новой М-задачи : X' = ( 0, ... 0, b1, ... bm )
Решаем М-задачу симплекс-методом
Анализируем решение М-задачи в соответствии со следующими правилами :
Если в оптимальном решении М-задачи: X" = ( X"1, ... X"n, X"n+1, ... X"n+m ) все искусственные переменные равны 0, то вектор X" = ( X"1, ... X"n ) является оптимальным решением исходной ЗЛП.
Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения в силу несовместимости ограничений.
Если М-задача не имеет решения , то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.