- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
3.12. Градиентные методы
Градиентным методом можно решать любую нелинейную задачу. При этом находится локальный экстремум. Целесообразнее же этот метод используют при решении задач выпуклого программирования.
Будем рассматривать задачу максимизации нелинейной дифференцируемой функции . Суть градиентного поиска точки максимума:
Возьмем произвольную точку из области допустимых значений.C помощью градиента функции в точке(Определим направление, в которомвозрастает с наибольшей скоростью. Затем сделав небольшой шаг в найденном направлении, перейдем в новую точку. Далее снова определяем наилучшее направление для перехода в очередную точкуи т.д.
Поисковая траектория представляет собой ломаную . Таким образом, надо построить последовательностьтак, чтобы она сходилась к точке максимума. Для точек последовательности выполняются условия
Градиентные методы, как правило, позволяют найти точные решения за бесконечное число шагов и лишь в некоторых случаях за конечное. В связи с этим градиентные методы относят к приближенным методам решения.
Блок 4
4.1. Методы штрафных и барьерных функций
Определение: Методы решения задач нелинейного (в частности выпуклого) программирования, при использовании которых данную задачу минимизации можно свести к задаче минимизации некоторой специальной функции, представляющую собой сумму данной минимизируемой функции и некоторой другой функции (называемой штрафной), сформированной из ограничений данной задачи, называют методами штрафных функций.
Общая идея методов штрафных и барьерных функций заключается в следующем: исследуется на экстремум не сама функция, а новая функция, построенная из исходной функции и штрафной. Значения полученной и исходной функции в области допустимых значений совпадают, а при приближении к границе, а тем более при выходе за ее пределы резко возрастают за счет добавленной функции. В зависимости от способа формирования штрафных функций различают метод штрафных и метод барьерных функций..
Рассмотрим метод штрафных функций.
Пусть требуется минимизировать функцию при ограничениях(). Предполагаем, что условия неотрицательности включены в систему ограничений задачи. Тогда обобщенная функция будет иметь вид:
,
где Н – штрафная функция, удовлетворяющая следующим условиям: для всех точек области допустимых значений Н=0 и Н>0 для всех остальных точек. Штрафную функцию можно построить различными способами. Для выпуклого программирования наиболее часто она имеет вид:
,
где
–некоторые постоянные числа, представляющие собой весовые коэффициенты.
Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. При этом координаты последующей точки находят по формуле:
Из последнего соотношения следует, что если предыдущая точка находится в области допустимых решений исходной задачи, то второе слагаемое в квадратных скобках равно 0 и переход к последующей точке определяется только градиентом целевой функции. Если же указанная точка не принадлежит области допустимых решений, то за счет данного слагаемого на последующих итерациях достигается возвращение в область допустимых решений. При этом чем меньше , тем быстрее находится приемлемое решение, однако точность определения его снижается. Поэтому итерационный процесс обычно начинают при сравнительно малых значенияхи, продолжая его, эти значения постепенно увеличивают.
Рассмотрим теперь метод барьерных функций. Если ограничения исходной задачи имеют вид строгих неравенств, то для формирования обобщенной функции используются так называемые барьерные функции, значения которых неограниченно возрастают при приближении к границе допустимой области. Обобщенная функция имеет такой же вид как для метода штрафных функций и за границы области допустимых значений она не выходит. В качестве барьерной чаще всего берут логарифмическую функцию.