Поиск решения

Установить целевую ячейку: $F$5 ]4J Равной: йжгимальному значению <~ значению о~

минимальному значению

Изменяя ячейки:

$В$12:$Е$12 Ограничения:

Предположить

$В$12:$Е$12 = О $F$6 <= $Н$6 $F$7 = JH$7 $F$8 <= $н$е

Добавить

Изменить

Удалить

Вь ипшть ] Закрыть

Параметра

Восстановить

Справка

Рис. 21.6. Решение задачи стохастического программирования в Excel 2. Дана следующая задача стохастического программирования.

при ограничениях

Максимизировать z = х, + х\ + х3

Р{х2 + а2х\ + азл/х7 < 10} > 0,9,

хг, х2, х3 > 0.

Пусть параметры а2 и а3 - независимые нормально распределенные случайные величины с математическими ожиданиями 5 и 2 и дисперсиями 16 и 25 соответственно. Преобразуйте данную задачу в детерминированную задачу сепарабельного программирования.

21.2.5. Метод линейных комбинаций

Этот метод ориентирован на решение задач, в которых все ограничения являются линейными:

максимизировать z = f (X)

АХ<Ь,Х>0.

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

Пусть X* - допустимая точка, полученная на fe-й итерации. Разложим целевую функцию /(X) в окрестности точки X* в ряд Тейлора. В результате получим

/(X) /ХХ*) + V/(X*)(X - X*) = /(X*) - V/XX*)X* + V/XX*)X. Нам необходимо определить допустимую точку X = X , в которой достигается максимум функции /XX) при выполнении (линейных) ограничений задачи. Так как /XX ) - V/XX )Х - постоянное слагаемое, задача определения X сводится к решению следующей задачи линейного программирования:

максимизировать wk(X) = Vf(Xk)X

при ограничениях

АХ<Ь,Х>0.

Так как целевая функция wk определяется градиентом функции /XX) в точке X*, улучшение имеющегося решения может быть обеспечено лишь тогда, когда шДХ ) > шДХ*). Из разложения Тейлора следует, что выполнение этого условия не гарантирует, что /XX*) > /(X*), так как X* не обязательно находится в малой окрестности точки X*. Однако при выполнении условия шДХ ) > wk(X.k) на отрезке (X*, X ) должна существовать такая точка X**1, что /XX**1) > /XX*). Следовательно, задача сводится к определению такой точки X**1. Найдем эту точку следующим образом:

Xk = (1 - r)Xk + гХ* = Хк + г(Х* - Хк), 0 < г < 1.

Отсюда следует, что точка X**1 является линейной комбинацией точек X* и X*. Так как X* и X* - точки выпуклой области допустимых решений, точка X**1 также является допустимой. Если сравнить эту процедуру с методом наискорейшего подъема (подраздел 21.1.2), параметр г можно рассматривать как длину шага.

Точка X**1 определяется из условия максимума функции /XX). Так как X*41 зависит лишь от переменной г, то Х*и определяется путем максимизации функции

h(r) = f[Xk + r(X* - Xk)].

Процедура повторяется до тех пор, пока на fe-й итерации не будет выполнено условие м>Л(Х*) < шДХ*). В этой точке дальнейшее улучшение существующего решения невозможно, процесс вычислений завершается, точка X* считается наилучшим решением.

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

Пример 21.2.7

Рассмотрим задачу квадратичного программирования из примера 21.2.3.

Максимизировать z = 4х, + бх, - 2х] - 2х,х2 - 2х\

при ограничениях

х, + 2х, < 2,

х х2>0.

Пусть Х° = (1/2, 1/2) - начальная точка, которая является допустимой для рассматриваемой задачи. Имеем

УДХ) = (4 - 4х, - 2х2, 6 - 2х, - 4х2).

Итерация 1.

удх°) = (i,3).

Соответствующая задача линейного программирования сводится к максимизации функции и>, =х, + Зх2 с учетом ограничений исходной задачи. Ее оптимальным решением есть точка X* = (0, 1). Значения функции и>, в точках Х° и X* равны 2 и 3 соответственно. Следовательно, новая точка ищется в виде

х=!.- + г

Максимизация функции

2 2

*w-4 2 2

дает г = 1. Таким образом, X1 = (0, 1) и ДХ1) = 4. Итерация 2.

УДХ1) = (2, 2).

Целевой функцией новой задачи линейного программирования является w2 = 2xt + 2x2. Оптимальное решение этой задачи - X = (2, 0). Поскольку значения w2 в точках X1 и X* равны 2 и 4, следует найти новую точку. Рассматриваем точку

X2 = (0, 1) + г[(2, 0) - (0, 1)] = (2г, 1 - г).

Максимизация функции

А(г) =Д2г, 1 - г)

дает г = 1/6. Таким образом, X2 = (1/3, 5/6), при этом ДХ2) = 4,16. Итерация 3.

УДХ2) = (1,2).

Здесь целевая функция имеет вид w3 = х, + 2х2. Оптимальным решением задачи линейного программирования будут альтернативные точки X* = (0,1) и X* = (2, 0). Значение и>3 в обоих случаях совпадает со значением w3 в точке X2. Следовательно, улучшить имеющееся решение невозможно. Получено приближенное оптимальное решение задачи: X2 = (1/3, 5/6) сДХ2) = 4,16. В данном случае оно совпадает с точным оптимумом.