Методы штрафных и барьерных функций

 

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

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

Рассмотрим метод штрафных функций.

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

,

где Н – штрафная функция, удовлетворяющая следующим условиям: для всех точек области допустимых значений Н=0 и Н>0 для всех остальных точек. Штрафную функцию можно построить различными способами. Для выпуклого программирования наиболее часто она имеет вид:

,

где

– некоторые постоянные числа, представляющие собой весовые коэффициенты.

Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. При этом координаты последующей точки находят по формуле:

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

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

 

Динамическое программирование. Основные понятия. Сущность методов решения

 

Динамическое программирование – это метод нахождение оптимальных решений в задачах с многошаговой структурой. Многие экономические процессы разделяются на шаги естественным образом: это все процессы планирования и управления, развивающиеся во времени. Естественным шагом в них могут быть год, неделя, декада и т.д. Однако метод динамического программирования может использоваться при решении задач, где время вообще не фигурирует. Разделение на шаги в таких задачах вводится искусственно.

Особенности задач динамического программирования:

1.Рассматривается система, состояние которой на каждом шаге определяется вектором .Дальнейшие изменения ее состояния зависят только от данного состояния и не зависят от того, каким путем система пришла в него. Такие процессы называют процессами без последствий.

2.На каждом шаге выбирается одно решение , под действием которого система переходит из предыдущего состояния в новое . Это новое состояние является функцией состояния на начало интервала и принятого вначале интервала решения ,т.е.

.

3.Действие на каждом шаге связано с определенным выигрышем (доходом прибыли) или потерей (издержками), которые зависят от состояния на начало шага и принятого решения.

4.На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений.

5.Требуется найти такое допустимое управление для каждого шага t, чтобы получить экстремальное значение функции цели за все T шагов.

Определение: Любую допустимую последовательность действий для каждого шага, приводящую систему из начального состояния в конечное, называют стратегией управления.

Определение: Допустимая стратегия управления, доставляющая функции цели экстремальное значение, называется оптимальной.

Определение: Управление – это воздействие, переводящее систему из начального состояния в конечное.

Любую многошаговую задачу можно решать по-разному. Во-первых, можно считать неизвестными величинами и находить экстремум целевой функции одним из существующих методов оптимизации, т.е. искать сразу все элементы решения на всех шагах сразу. Этот путь не всегда приводит к результату, особенно если целевая функция задана таблично или число переменных велико. Второй путь основан на проведении поэтапной оптимизации. Поэтапность отнюдь не означает изолированность этап, наоборот, управление на каждом последующем этапе осуществляется с учетом результатов предыдущего. Чаще всего этот метод проще, чем решение всей задачи сразу. Идея постепенной пошаговой оптимизации составляет суть метода динамического программирования. Из качественного анализа идеи поэтапной оптимизации можно сформулировать следующие принципы, лежащие в основе динамического программирования: принцип оптимальности и принцип погружения.

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

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

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

 

Стохастическое программирование. Основные понятия

 

Определение: Оптимизационные задачи и их модели, в которых вся исходная информация задана строго однозначно, называются детерминированными.

В действительности детерминированные модели часто оказываются неадекватными реальным процессам экономики. Это объясняется неполнотой, неточностью данных, на основе которых формируется модель. В одних случаях некоторые параметры носят вероятностный характер. Тогда говорят о ситуациях, связанных с риском. В других случаях имеющаяся информация не позволяет составить представление о характере изменения параметров, описываемых случайный процесс. Такие ситуации называются неопределенными.

Определение: Оптимизационные задачи, при постановке которых нет исчерпывающих данных об их условиях, называются стохастическими.

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

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

Различают пассивное и активное стохастическое программирование.

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

Определение: Активное стохастическое программирование – это совокупность приемов, позволяющих развивать методы выбора решений в условиях риска и неопределенности.

В стохастическом программировании исследуются одно-, двух-, многоэтапные задачи.

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

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

На практике чаще всего встречаются двухэтапные стохастические задачи. Подобные задачи возникают при планировании выпуска продукции в случае, когда отсутствуют данные о спросе, о ней. В такой ситуации сначала принимается предварительное решение об объеме выпуска на основе имеющейся информации (1 этап), затем после установления спроса принимается корректирующее решение (2 этап). При этом предварительное решение не должно исключать коррекции на втором этапе. Кроме того, предварительный и корректирующие планы согласовываются так, чтобы обеспечивались минимальные средние затраты за оба этапа.

Для ряда конкретных постановок двухэтапных стохастических задач Разработаны достаточно надежные методы решения.

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