Понятие о параметрическом и стохастическом программировании

Задача выпуклого программирования

Пусть дана система неравенств следующего вида и функция Z

, (4.3)

, (4.4)

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

Множество точек называется выпуклым, если оно вместе с любыми своими двумя точками содержит и весь отрезок, соединяющий эти точки. Если — отрезок на числовой прямой и , то , или

, , , . (4.5)

Нетрудно видеть и обратное: если выполняется (4.5), то . Таким образом, отрезок можно определить как множество всех точек , удовлетворяющих условию (4.5). Тогда выпуклое множество — это множество, которое вместе с любой парой своих точек , содержит и все точки , для которых выполняется (4.5). Эти определения отрезка и выпуклого множества сохраняются для случая, когда , , — точки n-мерного пространства (где операции в равенстве (4.5) выполняются покоординатно).

Исходя из равенства (4.5), по индукции можно показать, что если — выпуклое пространство, то длялюбых точек и любых действительных чисел , удовлетворяющих условию .

Функция , определенная на выпуклом множестве п-мерного пространства, называется выпуклойна этом множестве, если

(4.6)

для любых точек и любого числа .

Если в условии (4.5) изменить знак неравенства на , то получим определение вогнутой функции. Если же в условии (4.6) неравенство выполняется как строгое, то функция называется строго выпуклой(или строго вогнутой).

На рис. 4.3 изображен график функции одной переменной, выпуклой на всей числовой прямой.

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

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

Решение. Строим область допустимых решений данной задачи:

а) — окружность с центром в начале координат и радиусом R = 2. (рис. 11.3). Область решений неравенства состоит из точек, лежащих внутри этой окружности и на ней самой;

б) — прямая, которую можно построить, например, по точкам и . Область решений неравенства - полуплоскость, лежащая над этой прямой, включая и саму прямую;

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

Теперь построим линию уровня функции и определим направление убывания . Все линии уровня имеют равнение , т.е.. При получаем линию уровня - это окружность с центром в точке и радиусом . Ясно, что в любой точке этой линии уровня при перемещении от

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

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

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

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

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

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

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

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