11. Методы условной минимизации. Метод штрафных функций

Пусть дана задача:

(1)

Определение. Пусть дано некоторое . Тогда штрафной функцией этого множества называют функцию со следующими свойствами:

– некоторый неотрицательный скалярный параметр, с ростом которого неограниченно растёт функция .

Штрафную функцию можно интерпретировать как штраф за отклонение от , а характеризует относительную величину этого штрафа.

Пример 1. – множество планов задачи с ограничениями равенствами, то можно положить .

Пример 2. – множество планов задачи с неравенствами, тогда .

Существуют специальные способы подбора штрафных функций для различных типов множеств. Штрафные функции различаются по порядку роста. Существуют штрафные функции, которые имеют полиномиальный рост, экспоненциальный рост, логарифмический рост в зависимости от отклонения от X.

Пусть дана задача (1) и для построена штрафная функция, тогда метод штрафных функций заключается в решении вместо задачи (1), задачи на безусловный минимум

(7)

В задаче (7) возможны 2 подхода:

1 составляем для целевой функции условие стационарности

Находим стационарную точку , затем находим точку

(8)

Иногда, таким образом, удаётся построить в точности оптимальный план.

2 в других случаях задача (7) решается приближёнными методами.

13. Динамическое программирование . Задача распределения ресурса

Здесь рассматривается подход к решению специальных классов задач, которые имеют характер процессов многошаговых, многоэтапных, развивающихся во времени (динамических).

Задача распределения ресурса

Постановка задачи. Имеется некоторый однотипный ресурс (нефть, зерно) в объёме . Этот ресурс можно использовать в технологических процессах и причём известно, что если -му процессу выделить ресурс в объёме , то получим прибыль . Требуется распределить ресурс между процессами таким образом, чтобы суммарная прибыль была максимальной.

Математическая модель. Целевая функция (суммарная прибыль) будет

(1)

Ограничения:

(2)

(В (2) можно использовать и неравенство , однако, как правило, ресурс используется полностью.)

(3)

(2)-(3) – прямые ограничения. (1)-(3) – математическая модель задачи. Задача (1)-(3) относится к задачам сепарабельного программирования, так как и целевая функция и все ограничения в ней задаются с помощью сепарабельных функций.

Определение. Функция переменных называется сепарабельной, если она представима в виде линейной комбинации функций одной переменной.

К таким задачам, в частности, всегда применим метод динамического программирования. Общая схема метода динамического программирования

Метод, как правило, включает 3 этапа:

I этап: инвариантное погружение. На этом этапе исходная задача погружается в семейство подобных ей задач, зависящие от 2-х параметров, один из которых обычно динамический (время, этап). Оптимальное значение целевой функции отдельной задачи этого семейства (при фиксированных значениях параметров) называется функцией Беллмана.

II этап: строится уравнение Беллмана для этой функции. На этом этапе используется принцип оптимальности Беллмана, который формулируется следующим образом: любая часть оптимального решения (которая представляет из себя некоторую траекторию во времени или развивается поэтапно) начинающаяся с любого момента является сама оптимальной относительно достигнутого состояния.

Пример.

Пусть имеется оптимальная траектория , связывающая две точки , для – начальный момент, – конечный момент; – начальное состояние, – конечное состояние. Эта траектория оптимальная в связи с некоторой целевой функцией. Предположим, что в некоторый момент мы достигаем состояния и пытаемся из этого состояния и из этого момента достигнуть оптимальным образом. Тогда принцип оптимальности Беллмана утверждает, что решением этой задачи будет соответствующий (оставшийся) кусок траектории .

III этап: заключается в решении уравнения Беллмана (при всех значениях параметров определяется функцией Беллмана) и построению по этому решению оптимального плана исходной задачи.

Инвариантное погружение для задачи (1)-(3)

Рассмотрим в (1)-(3) первых технологических процесса и выделим для них ресурс в объёме и будем этот ресурс для этих процессов распределять оптимально, тогда приходим к задаче:

(4)

это и есть искомое семейство. Если в (4) положить , то придём к исходной задаче (1)-(3). То есть погружение осуществлено корректно. Оптимум целевой функции семейства (4) при фиксированных и , то есть максимальную прибыль, которую можно получить, если распределить среди первых процессов ресурс называется функцией Беллмана и обозначается .