Параметрические методы для решения оптимизационных задач в условиях неполной информации Канева Ольга Николаевна

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Канева Ольга Николаевна. Параметрические методы для решения оптимизационных задач в условиях неполной информации : диссертация ... кандидата физико-математических наук : 05.13.18.- Омск, 2005.- 125 с.: ил. РГБ ОД, 61 06-1/359

Содержание к диссертации

Введение

1. Двухэтапная задача стохастического программирования 28

1.1. Постановка задачи 28

1.2. Новая постановка задачи второго этапа 32

1.3. Условия разрешимости задачи второго этапа 35

1.4. Многокритериальность задачи второго этапа 38

1.5. Положительная диагональная матрица компенсаций . 43

1.6. Положительно определенная матрица компенсаций . 50

2. Методы решения двухэташюй задачи 55

2.1. Метод проектирования стохастических к вази градиентов 55

2.2. Алгоритм 1 57

2.3. Алгоритм 2 62

2.4. Нахождение решения задачи второго этапа. Алгоритм 3 . 64

3. Задача нечеткого программирования 68

3.1. Максимизирующее решение 69

3.2. Обобщенное решение 73

3.3. Алгоритм 4 75

4. Прикладные задачи 79

4.1. Система регулирования насосной станции 79

4.2. Портфель ценных бумаг 81

Заключение 87

Список литературы 89

Приложение А Численные эксперименты

Новая постановка задачи второго этапа
Метод проектирования стохастических к вази градиентов
Максимизирующее решение
Система регулирования насосной станции

Введение к работе

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

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

Рассмотрим задачи принятия решений при определенности. В этих задачах вся исходная информация определена однозначно. В качестве примера задачи принятия решений при определенности приведем задачу нелинейного программирования.

Общую задачу нелинейного программирования будем рассматривать в виде [2]: min/(:c) (0.1) при условиях

9і{х)<0, і = 1,...,т, (0.2) hi{x) = 0, і = 1,...,I, (0.3) хЄХ. (0.4)

Здесь /, f?b -.Qm-, h\,..., hi - определенные на Л" функции, X - множество из Rⁿ, х - вектор с компонентами х\,...,х_п.

Функцию / называют целевой функцией или критерием оптимальности. Каждое условие gi(x) < 0, і ~ 1,..., m, называют ограничением-неравенством, а условие вида 1ц{х) = 0, і = 1,. ..,1, — ограничением-равенством. Вектор х Є А', удовлетворяющий всем ограничениям, называют допустимым решением или допустимой точкой. Все допустимые точки образуют допустимую область.

Таким образом задача нелинейного программирования заключается в нахождении такой допустимой точки х = (x~i,... ,х_п), для которой /0^е) > /(#) !'Р^И ^всех допустимых решениях х — (х\,... ,х_п). Точка х называется оптимальным решением, или просто решением задачи.

Когда целевая функция f(x) линейна и все ограничения, включая соотношения, описывающие множество X, могут быть представлены в виде линейных равенств и(или) неравенств, задача (0.1)-(0.4) называется задачей линейного программирования [4, 14].

Если функции f(x),gi(x),...,g_m(x),hi{x),...,h[(x) - выпуклые функции, а X — выпуклое множество, то задачу нелинейного программирования (0.1)-(0.4) называют задачей выпуклого программирования

Теория нелинейного программирования строится в предположении, что функции f(x), gi(x),...,g_m(x), h\(x),... ,ki(x) — однозначные и имеется возможность вычислять точные значения этих функций, их производных, а также устанавливать принадлежность решения х множеству X. В этом случае для задачи нелинейного программирования можно построить некоторую другую задачу нелинейной оптимизации, называемую двойственной [2, 8, 15].

Для общей задачи нелинейного программирования (0.1)-(0.4), которая называется прямой задачей, двойственная по Лаграпжу задача (в дальнейшем будем называть се просто двойственной) имеет следующий вид [2]: max9(u,v) (0.5) при условии и > 0, (0.6) где 9{щ v) = inf[/(х) 4- щді{х) + Ь{Ы{х)\ х Є X]. ^Х 1=1 2=1

Функцию L(x, % v) = f(x) + ^Г щді(х) + 5^ «і/ц(ж) называют функцией Лагранжа, а функцию $(u,v) — двойственной функцией Лагранжа. Компоненты векторов и и v называют множителями Лагранжа. Важно отметить, что мпожителіі щ, соответствующие ограничениям-неравенствам (0.2), неотрицательны, а множители -и,-, отвечающие ограничениям-равенствам (0.3), могут иметь любой знак.

Прямая и двойственная задачи могут быть записаны в векторной форме. Пусть д : Rⁿ -> R^m — вектор-функция с компонентами #,-, a h : Rⁿ ~> R^l — вектор-функция с компонентами hi. Тогда задача (0.1)-(0.4) примет вид: min/(:r) (0.7) при условиях

9(х) < 0, (0.8) h{x) - 0, (0.9) х є X, (0.10) а двойственная функция Лагранжа запишется так: в(и, v) = \ni[f(x) + ид{х) + vh{x) \ х Є X].

Для каждой задачи нелинейного программирования можно строить двоііственньїе задачи и в другой форме [8, 15]. Все зависит от того, какие из ограничений рассматриваются в виде неравенств д(х) < 0 и равенств h(x) = 0, а какие отнесены к описанию множества X.

Связь задачи нелинейного программирования (0.1)-(0.4) (или (0.7)-(0.10)) и функции Лагранжа(а;,и,*;) задастся критерием оптимальности решений прямой и двойственной задач в терминах седловой точки функции Лагранжа. Этот критерий утверждает [2], что если X — непустое множество вй^и существуют х Є X и (u,v), такие, что й > 0 и выполняются неравенства L(x,u,v) < L(x,u,v) < L(x,u,v) для всох х Є X и всех (u,v), для которых и > 0, то тогда х и (й,у) являются соответственно решениями прямой задачи (0.1)-(0.4) и двойственной задачи (0.5), (0.6).

Обратное утверждение верно только лишь для задачи выпуклого программирования в предположении, что ограничения (0,2)-(0.4) удовлетворяют некоторому условию регулярности. Наиболее часто используемыми условиями являются так называемые условие регулярности Слейтера и условие линейной независимости [2].

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

Пусть F(xi,. ..,х_п) — непрерывно дифференцируемая функция, d = (di,..., d_n) — некоторое направление. Сдвинемся из точки х в направлении d с шагом р > 0, то есть рассмотрим точку х + pd. Тогда при малом р выполняется равенство F(x + pd) = F(x) +pY, F_Xj(x)dj + o(p), где F_Xj ~ ^-, а величина o(p) такова, что ^ —> 0. Следовательно, направление d, в котором функция F(x) убывает, должно удовлетворять условию J2F_Xi(x)dj<0_t а вектор d = —(F_Xl,... ,F_Xn) ~ ~F_x(x) всегда будет характеризовать направление убывания F(x), причем этот вектор направлен по внутренней нормали к единственной касательной гиперплоскости, которую можно провести к линии уровня {у : F(y) = F(x)} в точке х. Таким образом, чтобы из точки х сместиться в область меньших значений, достаточно найти вектор —F_x(x).

Вектор F_x(x) = (F_Xl,..., F_Xn) называется градиентом функции F(x), а вектор —F_x(x) — антиградиентом. Очевидно, если точка х — точка локального экстремума (локального минимума или максимума), то dF(x) F_x(x)^0, или ^к ^} = 0, t = 1,...,п. (0.11)

В соответствии с этим определяется градиентный метод поиска минимума: x^s+1 =x^s- p_slsF_x(x*),s = 0,1,..., (0.12) гдех = (аг,...,х) — произвольная начальная точка; X^s = (х\,..., ж*) — точка, полученная после s-ro шага (итерации); p_s — величина шага спуска (шаговый множитель), р_а > 0; 7s ~ нормирующий множитель. Если при этом удачно выбирается величина p_s, то с каждым шагом процесса (0.12) происходит уменьшение F(x) и в пределе точка X^s приближается к точке, в которой выполняются соотношения (0.11).

Весьма важными в прикладном отношении являются вопросы минимизации непрерывных, но негладких функций [12, 25]. Отсутствие непрерывных производных функций цели или ограничений для экстремальной задачи существенно усложняет поиск точек экстремума. Например, если функция F(x) недифференцирусмая. то классические уравнения (0.11) в точках локального экстремума уже не имеют места.

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

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

Численный метод обобщенного градиентного спуска минимизации выпуклой вниз негладкой функции предложен в 1964 году Н.З. Шором, а в работах [34], [53] были даны наиболее общие условия его сходимости.

Основная идея метода состоит в следующем. Если выпуклая вниз функция F(x) не имеет непрерывной производной, то ее линии уровня могут терпеть изломы в некоторых точках X^s. В этом случае в точке X^s нет единственной касательной гиперплоскости, а имеется целое семейство так называемых опорных гиперплоскостей, которые можно провести через точку X^я.

Оказывается, что подобно тому, как касательная гиперплоскость может быть охарактеризована градиентом, каждая опорная гиперплоскость характеризуется некоторым вектором, направленным по внешней нормали к гиперплоскости и получившим название вектора обобщенного градиента. Если функция F(x) выпуклая вниз (выпуклая), то вектором обобщенного градиента в точке х называется любой вектор F_x(x), удовлетворяющий неравенству F(z)-F(x)>(F_x(x),z~x) (0.13) для любых точек Z.

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

По аналогии с градиентным методом (0.12) рассмотрим поелсдова- телыюсть точек x^s, определенную соотношением х⁸⁺¹ = х³- p^A^lrS = 0,1,..., (0.14) где х — произвольное начальное приближение, p_s — величина шага, F_x{x^s) ~ один из обобщенных градиентов в точке x^s. 7s ~ нормирующий множитель. В отличие от метода (0.12) метод (0.14) не дает монотонного уменьшения функции цели с каждым шагом, и в этом его качественное отличие от обычного градиентного метода. Более того, в методе (0.12) изменение шага р_я легко поставить в зависимость от изменения функции цели (если функция цели не убывает, то шаг уменьшается, так как поиск происходит уже в окрестности точки минимума, соизмеримой с величиной шага). В процедуре (0.14) обратную связь при управлении величинами p_s ввести подобным образом невозможно, поэтому в работах [34], [53] для метода обобщенных градиентов (0.14) было предложено "программное" управление значением p_s : p_s >0, р_а -^-0,^2p_s = со, причем

7*>0, 7*||&(ж^в)|| < const

Эти условия являются естественными для сходимости последовательности X^s к точке минимума F(x). В частности, расходимость ряда / должна обеспечить достижение точки экстремума из произвольной точки х.

При минимизации выпуклой не обязательно гладкой функции F(x) при ІЕІ, где X — выпуклое множество, процедуру (0.14) несколько обобщают: х^ш = тс_х(х^а - Ps7sF_x(x^a))_iS = ОД,..., (0.15) где irx{^z) ~ операция, которую называют операцией проектирования точки z на множество X: ir_x{z) А', \\у - 7г_Л'(г)|| < \\у - z\\ 9 для любого у Є X.

В качестве тгх(г) для метода (0.15) можно принять решение следующей экстремальной задачи (при данном z): minlU — all² при условиях

Условия сходимости метода (0.15) приведены в [16].

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

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

Рассмотрим сначала ситуацию, когда в наличии имеются некоторые статистические данные или возможность их получения в результате каких-либо исследований процессов, определяющих изменение исходных данных. Предполагается, что по этой выборке статистических данных можно установить те или иные вероятностные характеристики параметров задачи. В этом случае говорят, что принятие решения происходит в условиях риска. Такие ситуации являются объектом исследования стохастического программирования. Этой тематике посвящено большое число монографий, к примеру [10, 16, 19, 21, 30]. Рассмотрим специфику этих задач.

Для задач стохастического программирования характерно то, что каждое действие может приводить к неоднозначному исходу и с каждым решением х можно связать числовые параметры f(u),x), ді(и,х), і ~ 1,..., m, зависящие как от решения %, так и от случайного параметра (состояния природы) ш.

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

Пусть Q — непустое множество элементов, которые будем называть элементарными событиями [5]. За J⁷ обозначим множество подмножеств F из Q,, которое содержит само множество Q и замкнуто относительно операций перехода к дополнению, счетного объединения и счетного пересечения, то есть F—- а-алгебра. Элементы F ст-алгебры ? будем называть случайными событиями, или просто событиями.

Каждому F Т приписывается неотрицательная вероятностная мера P{F) > 0, имеющая следующие свойства:

1)^(0) = 0, Р(П) = 1;

СО ОС со

2) если U *i = ft то P(U F_t) = Y, P(Fi).

Пара (1,^), состоящая из Сі и (Г-алгебры Т подмножеств П, называется измеримым пространством.

Тройка (fi,.F, Р), состоящая из непустого множества Q. сг-алгебры F подмножеств Q и вероятности Р на Т', называется вероятностным пространством.

На вероятностном пространстве (О., J⁷, Р) определяют случайные величины — функции элементарных событий. Функция (cj) называется действительной случайной величиной (^"-измеримой), если она принимает действительные значения и для каждого числа z неравенство (^w) < % определяет измеримое подмножество в Сі. то есть выполняется включение {wj (w) < z] Т.

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

Для случайных величин определяется понятие математического ожидания, или среднего значения. Интеграл Лебега f ^(uj)P(dQ), coil ли он существует, называется математическим ожиданием случайной величины и обозначается через М (либо М_ы).

Если для случайной величины (ш) известна функция F(x) = P({w\t(u,)

М= хЩх)йх. г -ос

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

1) линейности, так как для любых скалярных величин а, /3 выпол няется M(ai(w) + /%М) = аМЬ(и) + /ЗМ&(и);

2) ограниченности, так как для произвольного F Є Т справедливо равенство M_Xf = P(F).

Эти свойства определяют математическое ожидание как линейный функционал в пространстве случайных величин.

Величина D = Л/( — М)² называется дисперсией случайной вс-личины (если соответствующие интегралы существуют).

Широко используется понятие условного математического ожидания, которое определяется следующим образом.

Условным математическим ожиданием (w) относительно а-алгебры ^называется ^"-измеримая случайная величина, обозначаемая M(\F), такая, что для любого F F выполняется равенство

ЛГ(хД) = М(х,М(|Я)).

Для последовательности случайных величин определяются следующие понятия сходимости.

1) Последовательность ,^s{oj), s ~ 1,2,,.., сходится к (и) по чти наверное (с вероятностью 1) и обозначается ^s —> п.и., если lim ^s(w) = (w) для почти всех и по мере Р,

8—>О0

2) Последовательность ^s(w), s = 1,2,..., сходится к (w) по веро ятности и обозначается = Р — lim³, если для каждого е > О UmP{||?-fl|>e} = 0.

3) Последовательность '⁴(uj)_; s = 1,2,..., сходится к (о>) в среднем квадратичном и обозначается ^s —> с.к., если HmM||f ~||² = 0.

Имеет место следующая сравнительная таблица сходимостей: сходимость п.н. =» сходимость по вероятности <= сходимость в с.к.

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

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

Если цепочка начинается со слова "решение" и оно встречается N раз, то задачу выбора решения называют JV-этапной задачей перспективного стохастического программирования и ее решение будет детерминированным. Если со слова "наблюдение" — iV-этапной задачей оперативного стохастического программирования и решение будет представлять собой случайный вектор.

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

Часто случайные факторы заменяют их средними значениями (математическими ожиданиями) и задача принимает вид: F_Q{x) = M_u{f{u, х)} -> min (0.16) при условиях

Р,(х) = М^{д_{(_Ш,х)}<0^ = 1,...,т, (0.17) хХ, (0.18) где М_и — операция математического ожидания.

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

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

Но во многих постановках задач принятия решений в условиях неполной информации, связанных с повторяющимися ситуациями, нет необходимости в том, чтобы ограничения задачи удовлетворялись при каждой реализации случайного параметра и. Часто конкретное содержание задачи требует лишь, чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число а > 0. В тех случаях, когда возможные невязки в отдельных ограничениях вызывают различный ущерб, целесообразно дифференцированно подходить к разным условиям, то есть естественно ограничить снизу вероятность выполнения каждого из них различными числами pi > 0. В качестве целевой функции можно выбрать вероятность превышения функцией f(x,u) некоторого фиксированного порога /. В этом случае получается следующая задача: Qo(x) = P{f(x,co) > /} -> min (0.19) при условиях Qi{x) = Р{ф,ы) > 0} -_Pi > 0, * = 1,...777, (0.20) х Є X, (0.21) где f, pi — некоторые числа.

Задачи (0.16)-(0.18} и (0.19)-(0.21) не исчерпывают всего многообразия постановок, так как можно рассматривать задачи, являющиеся смесью этих постановок.

Сложность решения задач (0.16)-(0.18), (0.19)-(0.21) состоит в том, что очень часто при каждом х невозможно вычислить точные значения функций Fi(x), Qi(x), і = 0,1,... ,7п, тем более их производных. Обычно доступной является информация только о значениях функций f(cu,x), ді(и,х), і = 1,...,m, и только для отдельных w, поэтому основная трудность заключается в том, чтобы решить задачи (0.16)-(0.18), (0.19)-(0.21), не зная функций Fi(x), Qi(x), а пользуясь только значениями f{yj,x), gi(oj,x), і = 1,... ,m.

В тех случаях, когда удается найти функции і^(а;), Qi{x), экстремальные задачи (0.16)-(0.18), (0.19)-(0.21) ничем не отличаются от детерминированных задач нелинейного программирования, их стохастическая природа проявляется только на этапе поиска функций Fi(x)> Qi{x). В большинстве случаен идут именно по этому пути. Если же это не удается сделать,то пытаются заменить задачу некоторым приближенным детерминированным эквивалентом. Подобные подходы к решению получили название непрямых методов стохастического программирования, так как стохастическая задача решается как бы в обход, через детерминированную задачу.

Методы, основанные на информации о значениях f(u),x), д-_ь{и},х), г = 1,...,т, или аналогов их градиентов, называются прямыми методами стохастического программирования. Существенная особенность прямых методов состоит в том, что они применимы для решения задач, в которых законы распределения си неизвестны. В процессе оптимизации сложных объектов могут возникнуть ситуации, когда формулировка вероятностных свойств и) представляет значительную трудность и необходимо решить задачу без аналитического исследования вероят- постной модели. Для применения прямых методов в этом случае требуются только наблюдения ш_І5 oj2, ...,u)₃> параметра w [9]. В диссертации используются методы именно этого класса, то есть прямые методы.

Перейдем теперь к рассмотрению специфики задач выбора решений при неопределенности. Часто на практике возникают ситуации, когда нет оснований для каких бы то ни было суждений о статистических особенностях явлений, способных изменить предполагаемые значения параметров условий задачи. В таких случаях говорят о выборе решений при неопределенности [6. 22, 26, 30]. Эти задачи также являются объектом диссертационных исследований.

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

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

Ю.Б. Гермейер подчеркивал, что в проблемах принятия решений в условиях неопределенности может быть лишь один строгий математический результат — это оценка, полученная на основе принципа мак- симина. Гарантированный результат — это единственная опорная точка. Дальше лежат гипотезы и риск. Это утверждение не означает, что выбирать нужно именно то решение, которое реализует этот гарантированный результат. Он может быть и очень хорошим, и совершенно неприемлемым — это та информация, которая полезна оперирующей стороне. В конечном счете никогда никакой математический анализ не может дать строгого точного результата выбора решений в условиях неопределенности. Именно с этих позиций надо оценивать и попытку одного из известных специалистов в прикладной математике Л. Заде, который предложил отказаться от какого-либо четкого описания в задачах выбора решений в условиях неопределенности.

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

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

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

Нечетким множеством С в X называется совокупность пар вида (ж, fi_c(x)), где х Є X, а (л_с : X -> [0,1] — функция, называемая функцией принадлежности нечеткого множества С. Значение у._с{х) этой функции для конкретного х называется степенью принадлежности этого элемента нечеткому множеству С.

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

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

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

Максимизация обычной функции цели / : X —> R¹ на заданном нечетком множестве допустимых альтернатив fi_c : X —) [0,1]. Для решения подобной задачи предлагается рассматривать функцию f(x) = f{x)j sup f{x) (нормировка к единице) как функцию принадлежности нечеткого множества цели. Значение f(x) этой функции рассматривается как степень выполнения цели при выборе альтернативы хеХ.

Нечеткий вариант стандартной задачи нелинейного программирования, получаемый путем "смягчения" ограничений. То есть допускается возможность нарушения ограничений с той или иной степенью. Кроме того, вместо максимизации функции f(x) можно стремиться к достижению некоторого заданного значения этой функции, причем различным отклонениям значения /(ж) от этой величины приписывать различные степени допустимости (например, чем больше отклонение, тем меньше степень его допустимости). Такие задачи являются предметом изучения третьей главы диссертации.

Нечетко описана максимизируемая функция, то есть задано отображение fx_f : X х R^l -> [0,1], где X — универсальное множество, R¹ — числовая ось. Задано также нечеткое множество допустимых решений \i_c : X —> [0,1]. В этом случае функция fi_f(x$,r) при каждом фиксированном жо Є X представляет собой нечеткое описание оценки результата выбора решения х<$.

Заданы обычная максимизируемая функция / : X -> Л¹ и си- стема ограїшчеїшй вида gt(x) < 6;, і — 1,.. . m, причем параметры в описаниях функций ді{х) заданы нечетко в форме нечетких множеств.

5) Нечетко описаны как параметры функций, определяющих ограничения задачи, так и сама максимизируемая функция.

Задачи, в которых нечетко описано множество решений и четко целевая функция, в [22] называются задачами нечеткого математического программирования.

Коротко остановимся на наиболее известных подходах к решению задачи нечеткого математического программирования, которую для удобства сформулируем в следующем виде: X — некоторое универсальное множество решений, / — целевая функция из X в пространство R¹. В множестве X задано нечеткое подмножество \х_с : X -* [0,1], которое называется нечетким множеством допустимых решений. Задача заключается в максимизации в некотором смысле функции / на нечетком множестве \i_c.

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

Другой подход, предложенный в [22], опирается па разложение нечеткого множества ограничений по множествам уровня. Подход состоит в том, что исходная задача нечеткого математического программирования представляется в виде совокупности обычных задач максимизации функции / на всевозможных множествах уровня множества допустимых решений. Если решение xq Є X есть решение задачи max f(x) на множестве уровня А, то число А и принимается за степень принадлежности решения х₀ нечеткому множеству решений исходной задачи. Перебрав таким образом всевозможные значения А, мы получим функцию принадлежности нечеткого решения.

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

Для исследования задач принятия решений в условиях неполной информации в диссертации используется линейная задача дополнительности, которая в теории математического программирования является самостоятельным большим разделом [31, 54, 55).

Рассмотрим постановку линейной задачи дополнительности [24, 33].

Пусть заданы вектор q Є Rⁿ и вещественная пхп-матрица В. Линейной задачей дополнительности называется задача решения следующей смешанной системы неравенств и уравнений, выписанных относительно вектора переменных х Є Я":

Вх - q > 0, х > 0, (0.22) (Вх - q)x = 0. (0.23)

Нетрудно видеть, что в силу неотрицательности векторов Вх — q и х множество решений выписанной системы (0.22), (0.23) не изменится, если равенство нулю скалярного произведения (0.23) заменить требованием (В^гх — qtjxi = 0 при всех г ~ 1,..., п, где В^% — г'-я строка матрицы В. Будем обозначать сформулированную линейную задачу дополнительности через LCP(B,q),

Геометрически задача (0.22), (0.23) состоит в поиске неотрицательного вектора, образ которого при заданном афинном преобразовании также неотрицателен и ортогонален ему.

В связи с исследованием и решением задачи дополнительности (0.22), (0.23) выделяют ряд матричных классов [24]: класс Р-матриц — матрицы, все главные миноры которых положительны; класс положительно определенных матриц, то есть матриц В таких, что хВх > 0 для любого х ф 0; класс положительно полуопределенных матриц, то есть матриц В таких, что хВх > 0 для любого х\ класс неположительных матриц, то есть матриц В таких, что хВх > 0 для любого х > 0; класс сильно неположительных матриц, то есть коположительных матриц В таких, что при х > 0 и хВх = 0 имеет место равенство (В + В^г)а: = 0.

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

Для существования решения необходимо выполнение одного из следующих условий: матрица В принадлежит классу положительно полуопределениых матриц и система (0.23) совместна; матрица В — неотрицательная матрица и все её диагональные элементы положительны; матрица В является Р-матрицей: матрица В является симметричной Р-матрицей; матрица принадлежит классу положительно определенных матриц; матрица В принадлежит классу сильно неположительных мат-

Укажем несколько свойств, связанных с числом решений линейной задачи дополнительности LCP(B,q).

Свойство 1. Число решений задачи LCP(B,q) не обязательно единственно, если матрица В положительно полуопредсленная матрица и система (0.23) совместна.

Свойство 2. Число решений задачи LCP(B,q) не обязательно единственно, если матрица В неотрицательна и все её диагональные элементы положительны.

Свойство 3. Если матрица В является Р-матрицсй, то задача LCP(B,q) имеет единственное решение.

Свойство 4. Если матрица В симметричная и принадлежит классу F-матриц, то задача LCP(B, q) имеет единственное решение.

Свойство 5. Если матрица В положительно определенная матрица, то задача LCP(B,q) имеет единственное решение.

Свойство 6. Число решений задачи LCP(B,q) не обязательно единственно, если матрица В сильно ко положи тельная матрица.

Следует отмстить связь линейной задачи дополнительности (0.22), (0.23) с задачей квадратичного программирования вида (x,Bx-q) -» min (0.24) при условиях

Вх - q > 0, х > 0. (0.25)

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

Первыми итерационными методами, предложенными для решения линейной задачи дополнительности, являются алгоритм дополнительного ведущего преобразования Данцига [54] для задачи с положительными главными минорами матрицы В и метод Лемке [57], пригодный для более широкого класса матриц. По существу эти методы являются аналогами симплекс-метода.

Отметим тот факт, что задачи линейного и квадратичного программирования сводятся к задаче дополнительности при помощи теоремы Куиа-Таккера [2]. При этом решение задачи линейного программирования как задачи дополнительности методом Лемке иногда в 2-3 раза эффективнее обычного симплекс-метода [61].

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

Для достижения поставленной цели в работе решаются следующие задачи:

Построение и исследование новой постановки двухэтапной задачи стохастического программирования.

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

Построение решений для задач с нечеткими исходными данными.

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

Научную новизну полученных в работе результатов определяют;

Использование линейной задачи дополнительности в задаче второго этапа для двухэтапной задачи стохастического программирования.

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

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

Использование линейной задачи дополнительности для конструирования чебышевских решений задач принятия решений с нечеткими исходными данными.

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

Результаты диссертационной работы использованы при решении оптимизационной задачи минимизации энергопотребления насосного оборудования и внедрены на Муниципальном унитарном предприятии (МУП) "Водоканал" г. Омска.

Рассмотренные в диссертационной работе постановки задач принятия решений в условиях неполной информации и разработанные алгоритмы используются в учебном процессе Омского государственного технического университета в лекционном курсе по дисциплине "Основы прогнозирования", в курсовых и дипломных проектах и при моделировании практических задач, выполняемых в рамках госбюджет-пых научно-исследовательских работ Омского государственного технического университета (регистрационный номер НИР 4.01.Ф).

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

Рассмотрим краткое содержание диссертационной работы.

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

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

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

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

В заключении приводится развернутое изложение основных научных результатов, их использование и дальнейшее развитие.

В приложении содержатся тестовые примеры численных экспериментов но разработанным алгоритмам.

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

Новая постановка задачи второго этапа

1) принятие решений при определенности, если каждое действие неизменно приводит к однозначному исходу;

2) принятие решений при риске, если каждое действие приводит к одному из множества возможных частных исходов, каждый из которых имеет известную вероятность появления;

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

Таким образом задача нелинейного программирования заключается в нахождении такой допустимой точки х = (x i,... ,хп), для которой /0е) /(#) ! РИ всех допустимых решениях х — (х\,... ,хп). Точка х называется оптимальным решением, или просто решением задачи.

Связь задачи нелинейного программирования (0.1)-(0.4) (или (0.7)-(0.10)) и функции Лагранжа(а;,и, ;) задастся критерием оптимальности решений прямой и двойственной задач в терминах седловой точки функции Лагранжа. Этот критерий утверждает [2], что если X — непустое множество вй и существуют х Є X и (u,v), такие, что й 0 и выполняются неравенства для всох х Є X и всех (u,v), для которых и 0, то тогда х и (й,у) являются соответственно решениями прямой задачи (0.1)-(0.4) и двойственной задачи (0.5), (0.6).

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

Основная идея метода состоит в следующем. Если выпуклая вниз функция F(x) не имеет непрерывной производной, то ее линии уровня могут терпеть изломы в некоторых точках Xs. В этом случае в точке Xs нет единственной касательной гиперплоскости, а имеется целое семейство так называемых опорных гиперплоскостей, которые можно провести через точку Xя.

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

Метод проектирования стохастических к вази градиентов

Нечетким множеством С в X называется совокупность пар вида (ж, fic(x)), где х Є X, а (лс : X - [0,1] — функция, называемая функцией принадлежности нечеткого множества С. Значение у.с{х) этой функции для конкретного х называется степенью принадлежности этого элемента нечеткому множеству С.

1) Максимизация обычной функции цели / : X — R1 на заданном нечетком множестве допустимых альтернатив fic : X —) [0,1]. Для решения подобной задачи предлагается рассматривать функцию f(x) = f{x)j sup f{x) (нормировка к единице) как функцию принадлежности нечеткого множества цели. Значение f(x) этой функции рассматривается как степень выполнения цели при выборе альтернативы хеХ.

2) Нечеткий вариант стандартной задачи нелинейного программирования, получаемый путем "смягчения" ограничений. То есть допускается возможность нарушения ограничений с той или иной степенью. Кроме того, вместо максимизации функции f(x) можно стремиться к достижению некоторого заданного значения этой функции, причем различным отклонениям значения /(ж) от этой величины приписывать различные степени допустимости (например, чем больше отклонение, тем меньше степень его допустимости). Такие задачи являются предметом изучения третьей главы диссертации.

3) Нечетко описана максимизируемая функция, то есть задано отображение fxf : X х Rl - [0,1], где X — универсальное множество, R1 — числовая ось. Задано также нечеткое множество допустимых решений \ic : X — [0,1]. В этом случае функция fif(x$,r) при каждом фиксированном жо Є X представляет собой нечеткое описание оценки результата выбора решения х $.

4) Заданы обычная максимизируемая функция / : X - Л1 и си стема ограїшчеїшй вида gt(x) 6;, і — 1,.. . m, причем параметры в описаниях функций ді{х) заданы нечетко в форме нечетких множеств.

Коротко остановимся на наиболее известных подходах к решению задачи нечеткого математического программирования, которую для удобства сформулируем в следующем виде: X — некоторое универсальное множество решений, / — целевая функция из X в пространство R1. В множестве X задано нечеткое подмножество \хс : X - [0,1], которое называется нечетким множеством допустимых решений. Задача заключается в максимизации в некотором смысле функции / на нечетком множестве \ic.

Другой подход, предложенный в [22], опирается па разложение нечеткого множества ограничений по множествам уровня. Подход состоит в том, что исходная задача нечеткого математического программирования представляется в виде совокупности обычных задач максимизации функции / на всевозможных множествах уровня множества допустимых решений. Если решение XQ Є X есть решение задачи max f(x) на множестве уровня А, то число А и принимается за степень принадлежности решения х0 нечеткому множеству решений исходной задачи. Перебрав таким образом всевозможные значения А, мы получим функцию принадлежности нечеткого решения.

Максимизирующее решение

Если выполняется у0 Є Z, то найденная точка у0 является оптимальным решением задачи (2.115)-(2.117). Иначе положить s — О, ф = С, где С — достаточно большое положительное число. Перейти к основному этапу.

Основной этап. Перебираем все смежные с ys вершины по следующей схеме. В индексной строке симплексной таблицы симплекс-метода для решения задачи линейного программирования находим но порядку отрицательные элементы Y и для каждого из них осуществляем переход из базисной точки у3 в базисную точку ysJrl по ведущему столбцу, которому соответствует 7я- Для каждого вновь найденного вектора ys+l проводим проверку на принадлежность множеству Z. Если ys+1 Z и значение целевой функции в этой точке меньше значения ф, то ф = ф(и,х,у3+1). Далее для каждой вершины ys+1 аналогично перебираем все смежные вершины. И так до тех пор, пока не переберем все вершины, принадлежащие множеству Y. Последняя вершина, для которой запомнили значение ф. и будет оптимальным решением задачи (2.115)-(2.117).

Доказательство. Заметим, что решение задачи дополнительности (2.116), (2.117) находится в вершинах многогранного множества У. Начальное приближение находится как решение задачи линейного программирования (2.118), (2.119) на допустимом множестве У, то есть без учета нелинейного ограничения (2.117). Если после проверки выясняется, что это решение удовлетворяет еще и нелинейному ограничению (2.117), то теорема доказана.

Если найденное начальное приближение нелинейному ограничению (2.117) не удовлетворяет, то двигаясь по той же линейной целевой функции ф(со,х7у), но в направлении возрастания, находим точки, удовлетворяющие нелинейному ограничению (2.117). Поскольку найденная точка запоминается, только если значение целевой функции (2.115) в ней меньше зафиксированного, то последняя зафиксированная точка и будет оптимальной для задачи (2.115)-(2.117). Теорема доказана.

Замечание 2.1. Введение дополнительных ограничений у сверху на переменные у необходимо для разрешимости задачи линейного программирования (2.118), (2.119) с любой целевой функцией ф(и ,х,у). При этом из содержательного смысла решения задачи второго этапа с минимальными затратами на число мероприятий y(oj, х) по ликвидации возникающих невязок следует, что компоненты оптимального решения у будут заведомо меньше значений компонент у. Поэтому, решая задачу (2.115)-(2.117), мы фактически получаем решение задачи второго этапа, т. е. без дополнительных ограничений на переменные у.

Если информация о параметрах задачи и требованиях к системе задается экспертом на естественном языке, то для описания модели можно использовать методы теории нечетких множеств [7]. В этом случае в нашем распоряжении оказываются нечеткие описания функций f(x) — С, ?і(ж), ... , /7„(ж), или параметров, от которых зависят эти функции. Следует отметить, что если функция зависит от нечетко заданного параметра, то эта зависимость сводится к нечетко описанной функции [22].

Рассмотрим классический подход Беллмана-Заде к анализу и решению оптимизационных задач в нечеткой постановке. В этом подходе решение исходной нечеткой задачи (3.126) определяется как пересечение нечетких множеств, соответствующих функциям /(ж) — С, gi(x), ... , дт{х). Для того, чтобы задать нечеткие множества функций f{x) — С, д\{х), ... , дт(х), вводятся функции принадлежности, содержательно описывающие степени выполнения соответствующих неравенств системы (3.125) с точки зрения эксперта.

В силу произвольности выбора параметров C,CQ,CI,. ..,( множество допустимых решений задачи (3.131) может оказаться пустым и задача (3.131) — неразрешимой, а значит несобственной [14]. Это озна чает, что для исходной задачи в нечеткой постановке (3.126) получено пустое множество решений.

Для решения задачи (3.131) используем параметрический подход, который позволяет находить так называемое обобщенное решение. В основе этого подхода лежит аппарат линейных задач дополнительности. Подход предложен В. А. Вулавским [3] и получил дальнейшее развитие в работах А. В. Зыкиной [36].

Проведем параметризацию правой части системы (3.133). Для этого введем в рассмотрение вектор оценок у (ї/і,..., ут), компоненты которого являются неотрицательными величинами и интуитивный смысл которых — оценка степени жесткости ограничений системы (3.133).

Вектор х Є Rn, для которого решение задачи (3.134) у — у(х) удовлетворяет дополнительному условию (3.135), называется обобщенным решением задачи (3.133). Соответствующий вектор у = у{х ) называется вектором оптимальных оценок, вектор By определяет невязку системы (3.133).

В случае совместной системы в качестве обобщенного решения х получается решение системы в обычном смысле с нулевыми оценками у = 0 и, следовательно, вектор невязок By будет нулевым. Для несовместной системы обобщенное решение х имеет ненулевые оценки у ф 0 и вектор невязок By будет ненулевым. В последнем случае получается обобщенное решение, определяемое выбранной матрицей В.

Алгоритм 4 позволяет найти максимизирующее решение задачи (3.126) в случае, если она разрешима. Если же параметры С, со, ci,...,cm назначены экспертами таким образом, что задача (3.12G) не имеет решение (то есть функция принадлежности нечеткого множества решений fio{x) тождественно равна нулю), то в процессе решения алгоритмом будет произведена подправка параметров таким образом, что задача выйдет на "предел совместности", определяемый выбором матрицы В. 4. Прикладные задачи

Система регулирования насосной станции

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

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

В задаче (4.156)-(4.158) вместо средних значений ГІ будем рассматривать непосредственно сами случайные величины pi. Тогда задача (4.156)-(4.158) является задачей стохастического программирования.

Следует отметить, что распределение средств х = (#1, ...,ж„) происходит на этапе формирования портфеля, а значения случайных величин pi,..., рп становятся известны на этапе продажи портфеля. Следовательно решение х в данной постановке принимается до того, как станут известными значения случайных величин pi, г = 1,..., п.

Представим себе процесс решения задачи (4.156)-(4.158) следующим образом. Вначале выбираем предварительное решение х є X. Затем, после того как станут известными значения случайных параметров /. і = 1,... ,п, вычисляем невязки, возникшие в ограничениях (4.157).

Невязки корректируются выбором плана компенсации у — — {Уи ! Уп), который должен удовлетворять условиям By r-xR, у 0, (4.159) yBy = y(r-xR), (4.160) где R — диагональная матрица размерности п хп, на диагонали которой стоят случайные величины pi, г = 1,...,п. Условия (4.159), (4.160) образуют линейную задачу дополнительности LCP(B, q) относительно переменных у при фиксированных жире заданной квадратной матрицей В и вектором q = r — xR. Штраф за реализацию плана компенсации у будем задавать в виде функции y{r-xR). (4.161) В результате выбор плана компенсации у состоит в минимизации затрат (4.161) при условиях (4.159), (4.160). Изложенная схема решения может быть записана в виде задачи: min{a;Wa; + M,{miny(r - xR)}} (4.162) х у при условиях By r xR, у 0, (4.163) yBy = y{r-xR), (4.164) хеХ. (4.165) Задача (4.162)-(4.165) является двухэтаппой задачей стохастического программирования.

Содержательно предложенный процесс решения интерпретируется следующим образом. Значения rf, г = 1,...,п, — желаемые уровни получения доходов по активам, планируются на момент формирования портфеля. На момент продажи портфеля, в случае невозможности получения запланированного дохода, предусматривается проведение некоторых мероприятий по компенсации получаемых невязок. При этом компоненты вектора у понимаются как количество мероприятий по соответствующему виду актива. Компоненты bij заданной матрицы В в этом случае показывают количество средств, необходимых для компенсации г -й невязки при условии, что проводится одно мероприятие но коррекции невязки j-то актива. Тогда Ьгу = Ьцу\ + ... 4- hnyn, г = 1,..., п, — величина, па которую следует изменить заданный уровень доходности для г-го актива, чтобы вывести задачу на предел разре-. шимости после того, как станут известными значения величин р\,...,рп (доходностей соответствующих активов). При этом вектор у выбирается таким образом, чтобы издержки, связанные с затратами на проведение мероприятий по компенсации полученных невязок, были минимальны. Модель Марковича (4.156)-(4.158) и предложенная двухэтанная-схема формирования портфеля (4.162)-(4.165) реализованы в автоматизированной системе формирования портфеля ценных бумаг. Результаты численных экспериментов приведены в приложении. Заключение

Параметрические методы для решения оптимизационных задач в условиях неполной информации Канева Ольга Николаевна

Новая постановка задачи второго этапа

Метод проектирования стохастических к вази градиентов

Максимизирующее решение

Система регулирования насосной станции

Похожие диссертации на Параметрические методы для решения оптимизационных задач в условиях неполной информации