- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Метод барьерных функций
В отличие от метода штрафных функций, данный метод применим к задачам с ограничениями только в виде неравенств.
С
Исходная задача на условный экстремум задается в виде
f(x) min; (8.70)
i(x) 0, . (8.71)
Она преобразуется в задачу безусловной минимизации вспомогательной функции
(x) = f(x) + B(x),
где B(x) – барьерная функция, - параметр барьера.
Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых i (x) < 0).
Барьерная функция строится так, чтобы она была неотрицательной и непрерывной на допустимом множестве и стремилась к бесконечности при приближении изнутри к границе:
Как и в случае штрафной функции, существует несколько конструкций B(x), удовлетворяющих этим условиям. Но в основном используется барьерная функция в виде
(8.72)
Понятно, что решение вспомогательной задачи зависит от значения параметра барьера. Покажем на задаче из примера 8.7 влияние на результат минимизации .
Пример 8.11. Исходная задача:
f(x) = x min;
(x)=3 – x 0.
Барьерную функцию строим согласно (8.72). Тогда вспомогательная функция имеет вид
Находим точку минимума :
Отсюда получаем
Следовательно, с уменьшением точки минимума вспомогательной функции приближаются к минимуму исходной задачи. Геометрическая иллюстрация решения приведена на рис. 8.47.
Как хорошо видно на рис. 8.47, при оптимуме исходной задачи на границе допустимого множества последовательность точек минимума с уменьшением приближается к оптимальному решению изнутри допустимой области. По этой причине метод барьеров называют еще методом внутренних штрафов.
В связи с возможными трудностями поиска при малых значениях решается не одна, а последовательность вспомогательных задач с уменьшающимися значениями параметра барьера.
А лгоритм.
1. Выбрать начальную точку x0 так, чтобы i(x0)<0; задать точность , начальное значение 0 и число (0, 1).
2. Минимизировать (x) одним из методов безусловной оптимизации, в результате чего определяется .
3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.
Положить , за начальную точку принять и вернуться на 2.▲
Значение 0 можно брать из интервала [2, 10]. Важное замечание касается п.2 алгоритма: в процессе поиска минимума вблизи границы из-за дискретности шагов возможен выход за допустимую область, где барьерная функция становится отрицательной, что повлечет расхождение поиска. Поэтому необходима явная проверка на допустимость точек на каждом шаге при минимизации .
Пример 8.10 (Базара, Шетти). Исходная задача:
f(x) = (x1-2)4+( x1-2x2)2 min;
(x)= x2 0.
Решение находим, используя соответствующую вспомогательную функцию
=(x1-2)4+(x1-2 x2)2 -
За начальную точку возьмем допустимую точку (0;1), значения и принимаем равными 10. Результаты поиска алгоритмом барьерных функций представлены в табл. 8.5 и на рис. 8.48.
Таблица 8.5
№ итерации |
|
x1 |
x2 |
f |
|
B |
1 |
10 |
0.7079 |
1.5315 |
8.3338 |
18.0388 |
9.705 |
2 |
1.0 |
0.8282 |
1.1098 |
3.8214 |
6.1805 |
2.3591 |
3 |
0.1 |
0.8989 |
0.9638 |
2.5282 |
3.1701 |
0.6419 |
4 |
0.01 |
0.9294 |
0.9162 |
2.1291 |
2.3199 |
0.1908 |
5 |
0.001 |
0.9403 |
0.9011 |
2.0039 |
2.0629 |
0.0590 |
6 |
0.0001 |
0.94389 |
0.89635 |
1.9645 |
1.9829 |
0.0184 |
К ак и следовало ожидать, с уменьшением значение B стремится к нулю.
Завершая рассмотрение методов штрафных и барьерных функций, отметим, что можно построить алгоритм, использующий как штрафы, так и барьеры. Для этого достаточно записать смешанную вспомогательную функцию в виде
(x) = f(x) + B(x) + г де барьерная функция B(x) применяется к неравенствам, а штрафная функция Н(х) – к ограничениям-равенствам. Последовательность задач минимизации решается с уменьшающимися значениями параметра .