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

На правах рукописи

КАНЕВА Ольга Николаевна

ПАРАМЕТРИЧЕСКИЕ МЕТОДЫ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В УСЛОВИЯХ НЕПОЛНОЙ ИНФОРМАЦИИ

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Барнаул - 2005

м

з

На правах рукописи

КАНЕВА Ольга Николаевна

ПАРАМЕТРИЧЕСКИЕ МЕТОДЫ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ В УСЛОВИЯХ НЕПОЛНОЙ

ИНФОРМАЦИИ

05.13.18 — Математическое моделирование, численные методы и комплексы

программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Барнаул - 2005

Работа выполнена в Омском государственном техническом университете

Научный руководитель кандидат физико-математических наук,

доцент Зыкина Анна Владимировна

Официальные оппоненты — доктор физико-математических наук,

профессор Дементьев Владимир Тихонович.

— доктор физико-математических наук.

профессор Нурминский Евгений Алексеевич

Ведущая организация институт систем энергетики

им. Л А. Мелентьева СО РАН

Защита диссертации состоичся 25 ноября 2005 г. в 13 часов на заседании диссертационного совета Д 212 005 04 Алтайского государственного университета по адресу: 656049, г. Барнаул, пр Ленина, 61, конференц-зал

С диссертацией можно ознакомиться в библиотеке Алтайского государственного университета по адресу 656049, г. Барнаул, пр. Ленина, 61

Автореферат разослан 19 октября 2005 г.

Ученый секретарь диссертационного совета

д-р физ.-мат наук, профессор

С.А. Бечносюк

Общая характеристика работы

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

1. Принятие ре/пений при определенности, если каждое действие неизменно приводит к однозначному исходу

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

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие положения.

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

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

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

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

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

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

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

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

5. Построение математических моделей принятия решений при формировании портфеля ценных бумаг и оптимизации режимных параметров работы насосных станций МУП "Водоканал" города Омска.

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

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

Результаты диссертационной работы использованы при моделировании выбора оптимальных режимных параметров дли минимизации чнергопотреб-ления насосного оборудования и внедрены на Муниципальном унитарном предприятии "Водоканал" г. Омска.

Апробация работы. Результаты работы докладывались и обсуждались на IV Международной научно-технической конференции, посвященной 60-лсггию ОмГТУ "Динамика систем, механизмов и машин" (Омск, 2002), на Всероссийской научной молодежной конференции "Под знаком "Сигма" (Омск, 2003). на Международной научно-технической конференции "Актуальные проблемы подготовки специалистов для сферы сервиса" (Омск, 2003), на Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2004), на Международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 2004), на XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркугск-С'еверобайкальск, 2005). а также па научных семинарах лаборатории "Дискретная оптимизация и исследование операций" Омского филиала института математики СО РАН и кафедры "Автоматизированные системы обработки информации и управления" Омского государственного технического университета.

Публикации. По теме диссертационной работы опубликовано 14 работ, из них: статьи в центральных журналах 2 , статьи в местных изданиях 4 , тезисы докладов на конференциях - 7 , отчет о НИР - 1 .

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

Содержание диссертационной работы

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

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

Класс детерминированных задач рассматривается на примере задач нелинейного программирования, которые возникают в том случае, когда каждое допустимое действие (решение) можно однозначно охарактеризовать конечным набором чисел х,\,..., хп. При этом каждому х = (.Г], ..., тп) ставя гея в соответствие однозначные числовые показатели /,(.т), г = 1,..., т. и искомое решение выбирается из условия минимума функции

где X некоторое множество пространства Я", отвечающее обычно ограничениям специального вида. Экстремальная задача (1) -(3) — общая задача нелинейного программирования в детерминированной постановке

В задачах стохастического программирования в отличие от задач в детерминированной постановке имеется большая свобода в том. какие решения следует считать допустимыми и оптимальными. С каждым решением х связывают числовые параметры <р(ш, х). х), г — 1,..., т. которые зависят как от решения х, так и от случайного параметра (состояния природы) ш. Предполагается, что параметр ш является элементарным событием некоторою вероятное того пространства (П Т,Р) Здесь П множество элементарных событий. Т некоторая ег-алгебра определенная на О. Р вероятностная мера Исследованием таких задач занимались Д.Б. Юдин, Е.М Беркович, Ю М Ермольев. В.Т. Дементьев, Е А Нурминский. А И Кибзун и другие.

Если при постановке задачи предполагается, что решение х 6 X детерминированное и принимается перед тем. как наблюдается состояние природы и), то соотношениям (1). (2) для задачи стохастического программирования следует придать определенный вероятностный смысл, поскольку при фиксированном векторе х £ X для одних параметров ш соотношения (2) могут выполняться и х окажется допустимым решением, а для других случайных параметров ограничения (2) могут не выполняться.

(1)

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

/¡(ж) <0, г = 1,...,т, хеХ,

(2) (3)

Часто от этой проблемы уходят, заменяя задачу, зависящую от случайных факторов, некоторой эквивалентной детерминированной задачей. Для ее построения используют информацию о функциях распределения или различные статистические характеристики случайных параметров. Основная сложность при этом состоит в том, что при каждом векторе х невозможно вычислить точные значения соответствующих функций, тем более их производных. Обычно доступной является информация только о значениях функций .т). /,(и>, х), г — 1,..., тп, и только для отдельных -а]. Кроме того, такой путь анализа стохастических задач не всегда оправдан. Это может привести к нарушению адекватности модели изучаемому явлению, или полученная детерминированная задача может иметь сложную структуру Поэтому для решения стохастических задач разрабатываются специальные методы.

В случае, когда решение ищется на основе информации о значениях <р{ш, х). /До;, х), г' = 1,. . ,т, используются методы, которые получили па-звание - прямые методы стохастического программирования Эти методы являются предметом диссертационного исследования.

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

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

В первой главе диссертации исследуется двух этапная задача стохасти-

ческого программирования в классической постановке и предлагается новая постановка.

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

Пусть в задаче (1) (3) функции ограничений имеют вид:

и вместе с целевой функцией (1) зависят от случайного параметра ш, то есть ■р(х) = х), /,(ж) = дг(и, х) — Ь,(и>), г = 1,..., т. Множество же X определяют ограничения, не зависящие от и>.

Двухэтапная схема решения реализуется следующим образом. На первом этапе выбирается предваритепьный план х Е X, то есть такой план, который удовлетворяет условиям задачи, не зависящим от значений случайного параметра ал Затем фиксируются реализация параметра ш и соответствующие ему значения функций (р(ш,х). дг(ш,х), г — 1 ,...,т, и вектора Ь(ы) = (61(01),..., Ьт(ш)). определяются невязки д(ш, х) — Ь(ш) в условиях (2) задачи и вычисляется вектор коррекции у — (уь ..., уг), компенсирующий невязки в соответствии с соотношением:

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

1.{х) = д,{х) - Ь;, » = 1,2,..., т,

д,(ш,х) - Ь,(ш) < к,{и,у), г = 1 ,...,тп, У >0,

(4)

(5)

Естественно полагать, что компенсация невязок связана с затратами, поэтому за нарушение условий (2) устанавливается штраф, зависящий от координат вектора у, компенсирующего невязки. Штраф задается некоторой функцией

Ф(ш,у), (6)

которая определяет затраты на реализацию компенсации невязок. В этом случае задача второго этапа при принятом предварительном плане х и известном значении случайного параметра ш состоит в минимизации затрат (6) при условиях (4). (5) Тогда двухэтапная задача стохастического программирования запишется в следующем виде:

min х) + min ф{ш, у)}, (7)

g(w, х) - Ь(ш) < у), у > 0, (8)

хеХ. . (9)

Здесь д(ш,х), h(u>,y) — m-мерные вектора, компонентами которых являются функции д,{ш, х). h,(и>, у) соответственно.

В новой постановке двухэтапной задачи стохастического программирования для задачи (1)-(3) ограничения задачи второго этапа записываются в следующем виде:

д(и, х) - 6(w) < В{ш)у, у > 0, (10)

y{g{u;,x)-b{u>)) = yB{w)y. (11)

В терминах планирования производства задача (10), (11) имеет следующую содержательную и нтерпретаци ю:

— компоненты вектора [g{ui, х)—b(ui)]+ задают объем дефицита по каждому виду ресурса, который может возникнуть при известном предварительном плане х и при реализации состояния природы о;;

— компоненты вектора у определяют план компенсации (коррекции) дефицита по каждому виду ресурса;

— элемент bt) матрицы В(и>) задает объем поступления ¿-го ресурса при плане компенсации у — (0,..., 0,1,0____,0). где единица стоит на j-м месте

При фиксированных х и ш задача (10), (11) является линейной задачей дополнительности LCP(B,q) относительно переменных у с квадратной матрицей В = B(w) и вектором q — g(u>,x) — b(a>).

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

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

Следует отметить, что в случае разрешимости задачи (10), (11) при фиксированных х и ш она эквивалентна следующей задаче квадратичного программирования:

шшу{В(и)у - (д(ш,х) - Ь(ш))). (12)

д(ш, х) - Ь(ш) < В{ш)у, у > 0. (13)

Штрафовать за возникающие невязки предлагается с помощью одной из следующих функций: 1)

•ф(ы,х,у) = 0.

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

■ф{ш, х, у) = у(в(ш)у - (д(ш, х) - Ь(ш))). (14)

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

■ф{ш,х,у) = уё(ш).

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

3)

ф{ь>, х, у) = у{д(и, х) - 6(ш)).

В этом варианте и качестве вектора издержек с1(ш) берется величина невязки.

В результате вышеизложенного задача второго этапа при принятом предварительном плане х и известном значении случайного параметра ш принимает следующий вид:

тт 1/1(0/, х, у) (15)

при условиях

g(w,x)-b(uj)< B(w)y,y>0, (16)

»(в(ы,аг)-Ь(«))=уВ(ы)». (17)

В разделе 1.3 диссертации выведены условия разрешимости задачи второго этапа (15)- (17):

Лемма 1.1 Пусть матрица В(ш) положительно полуопределепная и система (16) совместна Тогда задача второго этапа (15)- (17) имеет решение У =

Лемма 1.2 Пусть матрица В(ш) > 0 и все ее диагональные элементы положительны. Тогда задача второго этапа (15)-(17) имеет решение у — у(ш, х)

Лемма 1.3 Пусть матрица В(и>) сильно неположительна и система (16) совместна. Тогда задача второго этапа (15)—(17) имеет решение у = у(и>,х).

Лемма 1.4 Пусть матрица В(ш) является симметричной Р-матрицей. Тогда задача второго этапа (15)—(17) имеет единственное решение у = у(ш, х).

Лемма 1.5 Пусть матрица В {lo) положительно определенная. Тогда задача второго этапа (15) (17) имеет единственное решение у — у(и>,х).

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

min МиМш, х) + ттф(ш,х.у)} (18)

I V

при условиях

д(и, х) - Ь(ш) < В(ш)у, у > 0, (19)

y(g{u,x)-b{w)) = yB{u)y, (20)

х е X (21)

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

Теорема 1.1 Пугть матрица B(w) положительно определенная матрица или симметричная Р-матрица. Тогда тройка векторов (у, и, и) — = (y(üj,x),u(uj,x),v(u>,x)), компоненты которой при у > 0, и > 0 и и > 0 задаются соотношениями

у(и,х) = В~1(и)(д(ш,х) - Ь(ш))+

х> У)(В~\и))ЧФу{ш>2/))«+

+B~1(w)il>u(w,x,y) - ±B~l(uj)ipy(uj,x,y),

tt(w,x) = ьВ~1{ш)(д(ш, х) — b(w))+

+1>v{u, y)(B-1(w))2(Vv(w. х. у))и + 2vB~l{u))il>u(u, х, у).

является седловой точкой функции Лагранжа для задачи (18)-(21).

Теорема 1.1 позволяет выписать явную формулу для нахождения решения задачи второго этапа

У = вг\ы){д{ы,х)-Ъ{ш)). (22)

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

д(ш, х) - 6(w) > 0. (23)

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

При выполнении неравенства (23) для задачи (18) -(21) с положительной диагональной матрицей компенсаций В(ш) выписывается эквивалентная задача вида: 1)

min Mu{ip(w, х) + (д(ш, х) - &(w))B-1(w)d(ü;)}, (24)

х 6 X, (25)

если функция штрафа ф(ш,х,у) = yd(u): 2)

mm Mw{</j(w, х) + {д{ш, х) - Ь{ш))В~ J(w)(g(u», х) - Ä(w))}, (26)

X

* € X, (27)

если функция штрафа ф{ш,х,у) = у(д(и>,х) — Ь(ш)).

Для задачи (24), (25) и задачи (26), (27) в разделе 1.5 доказаны следующие теоремы.

Теорема 1.2 Если при каждом значении параметра ш функции ^(w, х),

х), г = 1,..., т, — выпуклые по переменной х и ¡^''(х), j = 1____,ть

— выпуклые функции, то задача (24), (25) является задачей выпуклого про-грам м и рования.

Теорема 1.3 Пусть X — выпуклое множество и функции ip{ui,x). д,(ш,х), i — 1,... , m, при каждом значении параметра ш выпуклы и непрерывно дифференцируемы по переменной х Тогда функционал вида

Fr{x) = Mu{yx{u,x)+gx(u,x)B-l{u)d(u)}

является обобщенным градиентом функции (24) в точке х € X.

Теорема 1.4 Если при каждом значении параметра ш функции ip(w,x), gt(u>,х), г = I,... ,т, выпуклые по переменной х и j = 1,...,mi,

- выпуклые функции, го задача (26), (27) является задачей выпуклого программирования.

Теорема 1.5 Пусть X выпуклое множество и функции ц>{и>,х). дг(ш,х), г = 1,... ,т, при каждом значении параметра ш выпуклы и непрерывно дифференцируемы по переменной х. Тогда функционал вида

Fx{x) = М^уЛиЛ) + 2дх{и,х)В-\и){д{и,х) - Ь(ш))}

является обобщенным градиентом функции (26) в точке х е X.

Для случая, когда неравенство (23) не выполняется, в разделе. 1.6 доказываются следующие утверждения.

Теорема 1.6 Если В(си) является положительно определенной матрицей или симметричной Р-матрицсй и <;(ш,х) = у(ы,х)В(ш)у(ш,х) — выпуклая функция по переменной х при каждом значении параметра w, то задача вида'

min х) + min у(д(ш, т) - %>))} (28)

х ИбУ

при условии

X 6 X (29)

эквивалентна двухэтапной задаче (18)—(21) с функцией штрафа х, у) = = у(д(ш,х) — Ь(и>)) и является задачей выпуклого программирования при

условии, что ¡р(ш,х), g(w,x)i, г — 1,----т, — выпуклые по х при каждом

значении ы функции и g'1)(x)J, j — 1,..., ггц, выпуклые функции.

Теорема 1.7 Пусть X выпуклое множество и функции х) gv(w,x), i = 1,... , m, при каждом значении параметра ш выпуклы и непрерывно дифференцируемы по переменной х. Тогда функционал вида

Fx{x) = M^{ipx{w,x) + y(ui,x)qJ(uix) + yJ.{oj,x)q(uilx)}.

где q{ui,x) — g(w, ■)') — b(cu) является опорным к целевой функции задачи выпуклого программирования (28), (29).

Используя результаты главы 1 в главе 2 строятся алгоритмы, в основе которых лежит метод проектирования стохастических квазиградиентов.

В разделе 2.2 предложен алгоритм 1 для решения задач (24), (25) и (26), (27). Для задачи (24), (25) в качестве стохастического квазиградиепта, согласно теореме 1.5, берется вектор £ = <рх(ш,х) + дх(и>,х)В~1с1(и)), а для задачи (26). (27) вектор

£ = <рх(ы, х) + 2дх(ш, х)В~1(д(и, х) - Ь(ш)).

Для решения задачи (28). (29) в разделе 2.3 предложен алгоритм 2, в котором в качестве стохастического квазиградиента берется вектор

£ = <Р*(и, х) + у(ш, (о>, х) + ух(ш, х)д(ш, х).

В главе 3 рассматривается оптимизационная задача вида (1) (3). в которой допускается возможность нарушения ограничений (2) с той или иной степенью. Понятие "степень нарушения ограничения" формализуется с помощью введения в задачу (1)-(3) функций принадлежности ц/з(х), ] — 1,. ., го, для каждого ограничения из (2). Эти функции задают степень выполнения соответствующих неравенств системы (2) с точки зрения эксперта и являются монотонно убывающими функциями.

Также предполагается, что вместо минимизации целевой функции <р(х) достаточно дехтижения некоторого заданного значения С этой функции. Причем различным отклонениям значения ¡¿>(х) от этой величины приписывают различные степени допустимости, то есть в задачу вводится еще одна функция принадлежности

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

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

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

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

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

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

Модель строится следующим образом.

Пусть хи — интенсивность работы двигателя г-го насоса, г = 1,..., п, в 7-й момент времени, } = 1,..., т. Задается множество

X = {аг, < х%} < Ь,;}, (30)

где величины а1], Ьг] определяются техническими характеристиками насосов.

Пусть Р3{и}) объем притока жидкости к резервуар в ]-1\ момент времени Эта величина является случайной, гак как чависит от процесса водопотреб-ления, который носит стохастический характер.

За Я(.Ту) обозначим объем жидкости, перекачиваемый г-м насосом в у-й

п

момент времени из резервуара. Тогда Щ — Щхц) — расход жидкости в

1=1

J-i^ момент времени.

Величина 7_,(и>, х^,... ,хп}) отвечает за уровень жидкости в резервуаре в з-й момент времени. Известен некоторый начальный уровень 70. Также заданы верхняя и нижняя допустимые границы %„„ и 7тах, то есть должны выполняться условия

7тш < Ил • • • , Хщ) < 7шах) 3 - I,. . . ,т. (31)

Уравнение

Р»- Я,(*ч) = (32)

= х\}. ..., хп}) - 1(ы. ..., хп]„ )))

задает условие баланса между объемами притока жидкости Р}{ш) и расхода Я,(:г1;) в з'-й момент времени для резервуара с площадью днища, равной 5. При з — 1 выполняется равенство

.. ,х„7_1)) = 7о.

Обозначим за F(x4) электрическую мощность, потребляемую г-м насосом в j-(i момент времени. Тогда в качестве критерия можно рассматривать величину

п т

= (33)

1=] j=i

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

Так как величины х^,..xnj задают интенсивность работы двигателей на начало j-го момента времени, то есть до того, как станет известна реализация случайной величины си. то в ограничениях (31) могут возникнуть невязки. Способ их устранения в диссертационной работе рассматривается как второй этап двухэтанной схемы решения стохастической задачи.

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

В диссертационной работе в качестве математической модели портфеля рассмотрена следующая модель Марковича:

ттхИЛг, (34)

Х!1'1 + ... + хитп > р, (35)

п

х>0, = 1, (36)

<=i

где W — матрица ковариации, г,, г = 1, ...,п. — средняя доходность г-й ценной бумаги, х,, i = 1,..., п, - доля капитала, вложенная в i-ю ценную бумагу.

Предлагается модификация модели (34)-(36), которая учитывает желаемый уровень получения дохода по каждому виду ценных бумаг. Делается предположение, что после продажи портфеля, в случае невозможности получения запланированного дохода, существует возможность проведения некоторых мероприятий по компенсации получаемых невязок. Это позволяет выстроить двухэтапную схему решения поставленной задачи. В такой схеме компонента у,, г = 1,...,п, вектора компенсаций у содержательно интерпретируется как количество мероприятий, которые необходимо провести для ликвидации невязки по 1-й ценной бумаге. Компоненты Ьч заданной матрицы компенсаций В показывают количество средств, необходимых для компенсации г-й невязки при условии, что проводится одно мероприятие по коррекции невязки j-ro актива. При этом вектор компенсаций выбирается таким образом. чтобы издержки, связанные с затратами на проведение мероприятий по компенсации полученных невязок, были минимальны.

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

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

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

Основные научные результаты

В ходс диссертационного исследования получены следующие результаты

1) на основе анализа существующих подходов к решению задач принятия решений в условиях неопределенноеги предложена новая постановка двух-этапной задачи стохастического программирования:

2) изучены свойства новой постановки дв>хэтанной задачи стохастического программирования, сформулированы условия разрешимости;

3) найдены пути компенсации невязок, возникающих после реализации значений параметров неопределенности, позволяющие определять компенсации на пределе "совместности" исследуемой системы;

4) предложены функции штрафа для задачи второго этапа, позволяющие гибко реагировать на сложившуюся ситуацию;

5) для задач с нечеткими исходными данными предложен параметрический подход для нахождения обобщенного чебышевского решения на основе линейной задачи дополнительности:

6) разработаны и численно реализованы методы решения поставленных задач, доказана их сходимость;

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

Список публикаций по теме диссертации

[1] Зыкина A.B., Пригнец О.H Несобственная задача стохастического программирования // Математическое программирование и приложения. Информационный бюллетень Ассоциации математического программирования. № 8.- Екатеринбург: УрО РАН,1999. - С. 126.

[2] Каиева О.Н. Решение стохастической задачи распределения водных ресурсов ■'/ I Всесибирский конгресс женщин математиков (к 150-летию со дня рождения C.B. Ковалевской): Тез. докладов конгресса. - Красноярск: ИВМ СО РАН, 2000. - С. 85.

[31 Канева О.Н Проблема численной реализации алгоритма нахождения обобщенного решения при ограничениях j, Динамика систем, механизмов и машин: Материалы IV Междунар науч -техн. конф., посвященной 60-летию ОмГТУ. Омск: Изд-по ОмГТУ. 2002 Кн. 2 - С 168-170

[4] Канева О.Н. Обобщенное решение для задачи в нечеткой постановке // Математическое программирование и приложения. Информационный бюллетень Ассоциации математического программирования. № 10 Научное издание. Екатеринбур! : УрО РАН, 2003. С.130.

[5] Канева О.Н. Решение оптимизационных задач в условиях риска и неопределенности // Материалы Всероссийской научной молодежной конф "Под знаком "Сигма" ОНЦ СО РАН. Омск: Полиграфический центр КАН, 2003. - С.8-9.

[6] Канева О.Н О решении задачи моделирования малого бизнеса / Актуальные проблемы подготовки специалистов для сферы сервиса. Междунар. науч.-техн конф.: Сборник статей. Часть 1, Омск: Изд-во ОмГИС, 2003. - С. 143-144.

|7| Канева O.H. О решении задачи математического программирования в нечеткой постановке // Омский научный вестник. 2003. №4(25). - С.34-40.

(8] Обобщённое решение в нечётких моделях принятия решений /' С В. Зыкин, A.B. Зыкина, О.Н. Канева, Н.Б. Шамрай // Методология построения автоматизированных систем при неопределенности возмущающих воздействий и параметров в приборостроении, метрологии и контрольно-измерительной технике : отчет о НИР (заключ ) : 4.01 Ф / Омский гос. техн. ун-т (ОмГТУ) ; рук. Н.С. Жилин. - Омск, 2003. - № ГР 01.200106818. - Инв. № 02200402398. - Разд. 1. - С. 10-30

|9] Канева О.Н . Шарканов М.В Обобщенное решение в регрессионном анализе //' Динамика систем, механизмов и машин. Материалы V Междунар. науч.-техн. конф. - Омск: Изд-во ОмГТУ, 2004. - Кн. 2. С. 267-270.

|10) Канева О.Н. Обобщенное решение в регрессионном анализе // Росс.конф "Дискретный анализ и исследование операций": Мат.конф. Новосибирск: Изд-во ИМ СО РАН. 2004. - С. 130.

(11| Зыкина А В , Канева О.Н. Обобщенное решение для задачи математического программирования с нечеткими исходными данными // Доклады АН ВШ РФ. 2004. №2(3). - С.34-40.

[12] Канева О Н. Двухэтапная задача линейного стохастического программирования // Прикладная математика и информационные технологии Омск, 2005. - С 50-58

[13] Канева О.Н. Двухэтапная задача нелинейного стохастического программирования с дснерминированной матрицей коррекции // Математические структуры и моделирование. 2005. №14 С.25-33

[14] Канева О.Н. Двухэтапная задача стохастическою программирования // Математическое программирование: Труды XIII Байкальской между народной школы-семинара "Методы оптимизации и их приложения", Иркутск, Байкал. Том 1. Иркутск, ИСЭМ СО РАН, 2005. - С. 231-237.

Отпечатано с оригинала-макета, предоставленного автором

ИД № 06039 от 12.10.2001.

Подписано в печать 12.10 05. Формат 60х841/1б- Отпечатано на дупликаторе. Бумага офсетная. Усл. печ. л. 1,25. Уч.-изд.л. 1,25. Тираж 100. Заказ 648.

Издательство ОмГТУ. Омск, пр. Мира, 11. т. 23-02-12 Типография ОмГТУ

,1 !

i

i

i

i i i

с

У

í

I \

I

I

I

Г i

i

i »

I I

Р19717

РНБ Русский фонд

2006-4 16843

Введение

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

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

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

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

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

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

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

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

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

2.2. Алгоритм 1. 2.3. Алгоритм 2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0.1) при условиях

0»(®) < о, г = 1,.,га,

0-2)

Нг{х) = 0, г = 1 хех.

0.3) (0.4)

Здесь /, <7ь ., дт, ., /г/ - определенные на В!1 функции, X - множество из Яп, х - вектор с компонентами х1,.,хп.

Функцию / называют целевой функцией или критерием оптимальности. Каждое условие д^х) <0, г = 1,., га, называют ограничением-неравенством, а условие вида Нг(х) = 0, г = 1,— ограничением-равенством. Вектор х е X, удовлетворяющий всем ограничениям, называют допустимым решением или допустимой точкой. Все допустимые точки образуют допустимую область.

Таким образом задача нелинейного программирования заключается в нахождении такой допустимой точки х = (х\,., хп), для которой /(х) > /(х) при всех допустимых решениях х = (х\,. .,хп). Точка х называется оптимальным решением, или просто решением задачи.

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

Если функции f{x),gl(x),.,дт{х), Н\(х),., ^(х) - выпуклые функции, а X — выпуклое множество, то задачу нелинейного программирования (0.1)-(0.4) называют задачей выпуклого программирования

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

Для общей задачи нелинейного программирования (0.1)-(0.4), которая называется прямой задачей, двойственная по Лагранжу задача (в дальнейшем будем называть ее просто двойственной) имеет следующий вид [2]: тахв(и,у) (0.5) при условии > 0, (0.6) т I где 9(и, у) = тЩ(х) + £ щд{(х) + X] х € X]. х г=1 1=1

Функцию

7/1 I

Ь(х, Щ у) = /(X) + ^ пд^х) 4- УгЫ{х)

1 г=1 называют функцией Лагранжа, а функцию 9(и,у) — двойственной функцией Лагранжа. Компоненты векторов и и и называют множителями Лагранжа. Важно отметить, что множители щ, соответствующие ограничениям-неравенствам (0.2), неотрицательны, а множители г>г-, отвечающие ограничениям-равенствам (0.3), могут иметь любой знак.

Прямая и двойственная задачи могут быть записаны в векторной форме. Пусть д : Яп —> Игп — вектор-функция с компонентами д^ а Н : Дп -> К1 — вектор-функция с компонентами /г^. Тогда задача (0.1)-(0.4) примет вид: тт/{х) (0.7) при условиях д(х) < о, (0.8) к(х) = 0, (0.9) ж € X, (0.10) а двойственная функция Лагранжа запишется так: в(и,у) = т£[/(а?) + ид{х) + уН{х) \ х € X].

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

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

Ь(х,и,у) < Ь(х,й,у) < Ь{х,й,у) для всех х 6 X и всех (и, у), для которых и > 0, то тогда х и (й,у) являются соответственно решениями прямой задачи (0.1)-(0.4) и двойственной задачи (0.5), (0.6).

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

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

Пусть Г(х1,. ,хп) — непрерывно дифференцируемая функция, £I = ((¡г,. ,с1п) — некоторое направление. Сдвинемся из точки х в направлении в, с шагом р > 0, то есть рассмотрим точку х + рв,. Тогда при малом р выполняется равенство п

Р(х + р(1) = Г(х) + р^2 Шз + о(р),

3=1 где Рх. = щ, а величина о(р) такова, что ^ 0. Следовательно, направление в котором функция Г(х) убывает, должно удовлетворять условию п

Y^F*№di< О,

J=1 а вектор d = —(FXl,.,FXn) = —Fx(x) всегда будет характеризовать направление убывания F(x), причем этот вектор направлен но внутренней нормали к единственной касательной гиперплоскости, которую можно провести к линии уровня {у : F(y) = F(x)} в точке х. Таким образом, чтобы из точки х сместиться в область меньших значений, достаточно найти вектор — Fx(x).

Вектор Fx(x) = (FXl,., FXn) называется градиентом функции F(x), а вектор — Fx(x) — антиградиентом. Очевидно, если точка х — точка локального экстремума (локального минимума или максимума), то dF(x)

Fx(x) = 0, или v ' = 0, г = 1,., п. (0.11)

OX i

В соответствии с этим определяется градиентный метод поиска минимума: e+1 = ж5 - psjsFx(xs),s = 0,1,., (0.12) где ж0 = (аг®,., ж®) — произвольная начальная точка; xs = (xf,., х„) — точка, полученная после s-ro шага (итерации); ps — величина шага спуска (шаговый множитель), р3 > 0; js — нормирующий множитель. Если при этом удачно выбирается величина ps, то с каждым шагом процесса (0.12) происходит уменьшение F(x) и в пределе точка Xs приближается к точке, в которой выполняются соотношения (0.11).

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

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

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

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

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

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

F(z)-F(x)>(Fx{x),z-x) (0.13) для любых точек z.

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

По аналогии с градиентным методом (0.12) рассмотрим иоследовательность точек ж8, определенную соотношением ха РаЪрх(ха\8 = 0,1,., (0.14) где ж0 — произвольное начальное приближение, ps — величина шага, Fx{xs) ~ 0ДИП из обобщенных градиентов в точке Xs, js — нормирующий множитель. В отличие от метода (0.12) метод (0.14) не дает монотонного уменьшения функции цели с каждым шагом, и в этом его качественное отличие от обычного градиентного метода. Более того, в методе (0.12) изменение шага ps легко поставить в зависимость от изменения функции цели (если функция цели не убывает, то шаг уменьшается, так как поиск происходит уже в окрестности точки минимума, соизмеримой с величиной шага). В процедуре (0.14) обратную связь при управлении величинами р8 ввести подобным образом невозможно, поэтому в работах [34], [53] для метода обобщенных градиентов (0.14) было предложено "программное" управление значением ps : оо

Ра >0, ps 0, Ps = ОО, s=0 причем

7а > 0, 75||FT(ri)|| < const.

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

При минимизации выпуклой ие обязательно гладкой функции F(x) при х Е X, где X — выпуклое множество, процедуру (0.14) несколько обобщают: тгх(х3 ~ PslsFx(xs)),s = 0,1,., (0.15) где 7rx(z) — операция, которую называют операцией проектирования точки z на множество X:

7гx(z) в X, ||у - 7г;г(г)|| < НУ ~ ¿11 для любого у G X.

В качестве irx{z) для метода (0.15) можно принять решение следующей экстремальной задачи (при данном z): min I\z — ж||2 X при условиях х е х.

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

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

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

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

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

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

Пусть & — непустое множество элементов, которые будем называть элементарными событиями [5]. За Т обозначим множество подмножеств Р из О,, которое содержит само множество £7 и замкнуто относительно операций перехода к дополнению, счетного объединения и счетного пересечения, то есть Т— сг-алгебра. Элементы Р сг-алгебры Т будем называть случайными событиями, или просто событиями.

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

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

00 00 оо

2) если и Я = 0, то Р(и Я) = £

1 г=1 г=1

Пара состоящая из и <х-алгебры Т подмножеств О, называется измеримым пространством.

Тройка Р), состоящая из непустого множества О,, сг-алгебры

Т подмножеств О, и вероятности Р на Т, называется вероятностным пространством.

На вероятностном пространстве (£2, Т, Р) определяют случайные величины — функции элементарных событий. Функция £(о>) называется действительной случайной величиной (^-измеримой), если она принимает действительные значения и для каждого числа 2 неравенство < определяет измеримое подмножество в О, то есть выполняется включение {си| < г] 6 Т.

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

Для случайных величин определяется понятие математического ожидания, или среднего значения. Интеграл Лебега / £(а;)Р(сШ). есп ли он существует, называется математическим ожиданием случайной величины и обозначается через (либо Мш£).

Если для случайной величины £ (а;) известна функция

F(x) = P({u,\t(u)<x}), называемая функцией распределения, и она дифференцируема, то есть = F'(x), то математическое ожидание вычисляется как интеграл Римана вида 00

М£ = J x$s(x)dx. — 00

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

1) линейности, так как для любых скалярных величин а, /3 выполняется

М(а£ iH + 0£2(ш)) = аМЫи) + /Ш&М;

2) ограниченности, так как для произвольного F € Т справедливо равенство

MXf = P(F).

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

Величина = М{£, — М£)2 называется дисперсией случайной величины £ (если соответствующие интегралы существуют).

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

Условным математическим ожиданием £(а;) относительно о-алгебры Т называется ^"-измеримая случайная величина, обозначаемая

M(£\!F), такая, что для любого F £ Т выполняется равенство

M(xF 0 = M(XfM(Z\F)).

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

1) Последовательность £я(с<;), s = 1,2,., сходится к £(а;) почти наверное (с вероятностью 1) и обозначается £ п.н., если lim £s(tc) = для почти всех и по мере Р.

S—¥OQ

2) Последовательность s = 1,2,., сходится к £(о>) по вероятности и обозначается £ = Р — lim£s, если для каждого е > О lim >е} = 0. s-*oo Ul 11 J

3) Последовательность s = 1,2,., сходится к в среднем квадратичном и обозначается —> £ с.к., если lim M||£s — £||2 = 0.

S—>00

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

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

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

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

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

Часто случайные факторы заменяют их средними значениями (математическими ожиданиями) и задача принимает вид: в) = МиМ(и,х)} -> ПШ1

0.16) при условиях ж) = Мш{д{(и, х)} < 0, г = 1,., ш

0.17) х ех,

0.18) где Мш — операция математического ожидания.

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

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

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

За(х) = РЦ(х,и) > /} -> шт

0.19) при условиях

X) = Р{д{{х, си) > 0} - Рг > 0, г = 1,. га х еХ, 15

0.20) (0.21) где /, рг — некоторые числа.

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

Сложность решения задач (0.16)—(0.18), (0.19)—(0.21) состоит в том, что очень часто при каждом х невозможно вычислить точные значения функций Е^х), <3г(х), % = 0,1,. ,7П, тем более их производных. Обычно доступной является информация только о значениях функций /(о;,х), дг(и,х), г — 1 ,.,га, и только для отдельных си, поэтому основная трудность заключается в том, чтобы решить задачи (0.16)-(0.18), (0.19)-(0.21), не зная функций ^(ж), а пользуясь только значениями /(а>,х), д((ш,х), г = 1,., га.

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

Методы, основанные на информации о значениях /(о;, х), ^¿(си, х), г = 1 ,.,т, или аналогов их градиентов, называются прямыми методами стохастического программирования. Существенная особенность прямых методов состоит в том, что они применимы для решения задач, в которых законы распределения си неизвестны. В процессе оптимизации сложных объектов могут возникнуть ситуации, когда формулировка вероятностных свойств си представляет значительную трудность и необходимо решить задачу без аналитического исследования вероятпостной модели. Для применения прямых методов в этом случае требуются только наблюдения о>1, . . параметра и [9]. В диссертации используются методы именно этого класса, то есть прямые методы.

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Нечетко описана максимизируемая функция, то есть задано отображение у,j : X х R1 —> [0,1], где X — универсальное множество, R1 — числовая ось. Задано также нечеткое множество допустимых решений fic : X —> [0,1]. В этом случае функция fif(xo,r) при каждом фиксированном жо G X представляет собой нечеткое описание оценки результата выбора решения xq.

4) Заданы обычная максимизируемая функция / : X -» R1 и система ограничений вида д^х) < г — 1 , .т, причем параметры в описаниях функций д^х) заданы нечетко в форме нечетких множеств.

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

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

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

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

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

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

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

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

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

Вх-д>0, х>0, (0.22)

Вх - д)х = 0. (0.23)

Нетрудно видеть, что в силу неотрицательности векторов Вх — д и х множество решений выписанной системы (0.22), (0.23) не изменится, если равенство нулю скалярного произведения (0.23) заменить требованием

Вгх — д{)х{ = 0 при всех г — 1,., п, где В1 — 2-я строка матрицы В. Будем обозначать сформулированную линейную задачу дополнительности через ЬСР(В,д).

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

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

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

Для существования решения необходимо выполнение одного из следующих условий:

1) матрица В принадлежит классу положительно полуопределенных матриц и система (0.23) совместна;

2) матрица В — неотрицательная матрица и все её диагональные элементы положительны;

3) матрица В является Р-матрицей;

4) матрица В является симметричной Р-матрицей;

5) матрица принадлежит классу положительно определенных матриц;

6) матрица В принадлежит классу сильно коположительных матриц.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Основные научные результаты

На защиту выносятся следующие научные результаты:

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

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

3) найдены пути компенсации невязок, возникающих после реализации значений параметров неопределенности, позволяющие определять компенсации на пределе "совместности" исследуемой системы;

4) предложены функции штрафа для задачи второго этапа, позволяющие гибко реагировать на сложившуюся ситуацию;

5) для задач с нечеткими исходными данными предложен параметрический подход для нахождения обобщенного чебышевского решения на основе линейной задачи дополнительности;

6) разработаны и численно реализованы методы решения поставленных задач, доказана их сходимость;

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

Использование и дальнейшее развитие результатов исследований

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

1. Амосов, А. А. Вычислительные методы для инженеров Текст]: учеб. пособие / А. А. Амосов, ЮА. Дубинский, Н. В. Копченова.- М. : Выш. шк., 1994. 544 с.

2. Базара, М. Нелинейное программирование. Теория и алгоритмы Текст]: [пер. с англ.] / М. Базара, К. Шетти. М. : Мир, 1982. -583 с.

3. Булавский, В. А. Методы релаксации для систем неравенств Текст]: учеб. пособие / В. А. Булавский. Новосибирск : НГУ, 1981.-83 с.

4. Васильев, Ф. П. Линейное программирование Текст]/ Ф. П. Васильев, А. Ю. Иваницкий М.: Факториал Пресс, 1997.

5. Вентцсль, Е. С. Теория вероятностей Текст] / Е. С. Вентцель. М. : Академия, 2003. - 576 с.

6. Волков, И. К. Исследование операций Текст]: учеб. для вузов / И. К. Волков, Е. А. Загоруйко; под ред. В. С. Зарубина, А. П. Крищснко. М. : Изд-во МГТУ им. Н. Э. Баумана, 2000. - 436 с.

7. Вощинин, А. П. Оптимизация в условиях неопределенности Текст] / А. П. Вощинин. М. : Изд-во МЭИ (СССР); София : Изд-во "Техника" (НРБ), 1989. - 224 с.

8. Голылтейн, Е. Г. Модифицированные функции Лагранжа. Теория и методы оптимизации Текст] / Е. Г. Голынтсйн, Н. В. Третьяков.- М. : Наука, 1989. 400 с.

9. Гупал, А. М. Стохастические методы решения негладких экстремальных задач Текст] / А. М. Гупал. Киев : Наук, думка, 1979. - 152 с.

10. Дементьев, В. Т. Задачи оптимизации иерархических структур Текст] / В. Т. Дементьев, А. И. Ерзин, Р. М. Ларин, Ю. В. Шамардин. Новосибирск : Изд-во Новосиб. ун-та, 1996. - 167 с.

11. Дсмидснко, Е. 3. Линейная и нелинейная регрессия Текст] / Е. 3. Демиденко. М. : Финансы и статистика, 1981. - 302 с.

12. Демьянов, В. Ф. Нсдифференцируемая оптимизация Текст] / В. Ф. Демьянов, Ф. П. Васильев. М. : Наука, 1981. - 384 с.

13. Еремин, И. И. Несобственные задачи линейного и выпуклого программирования Текст] / И. И. Еремин, В. Д. Мазуров, Н. Н. Астафьев М. : Наука, 1983. - 336 с.

14. Еремин, И. И. Теория линейной оптимизации Текст] / И. И. Еремин. Екатеринбург : УрО РАН, 1998. - 248 с.

15. Еремин, И. И. Двойственность в линейной оптимизации Текст] / И. И. Еремин. Екатеринбург: УрО РАН, 2001. - 180 с.

16. Ермольев, Ю. М. Методы стохастического программирования Текст] / Ю. М. Ермольев. М.: Главная редакция физико-математической литературы изд-ва "Наука", 1976. - 240 с.

17. Загоруйко, Н. Г. Прикладные методы анализа данных и знаний Текст] / Н. Г. Загоруйко. Новосибирск : Изд-во Ин-та математики, 1999. - 270 с.

18. Мальцев, И. А. Линейная алгебра Текст] / И. А. Мальцев. Новосибирск : Изд-во Ин-та математики, 2001. - 316 с.

19. Нурминский, Е. А. Числешгые методы решения детерминированных и стохастических минимаксных задач Текст] / Е. А. Нурминский. Киев : Наук, думка, 1979. - 161 с.

20. Нурминский, Е. А. Численные методы выпуклой оптимизации Текст] / Е. А. Нурминский. М. : Наука. 1991. - 168 с.

21. Нурминский, Е. А. Математические основы теории финансовых рынков Текст]: учеб. пособие / Е. А. Нурминский, Л. Т. Ащеп-ков, Е. В. Трифонов. Владивосток : Изд-во Дальиевост. ун-та, 2000. - 112 с.

22. Орловский, С. А. Проблемы принятия решений при нечеткой исходной информации Текст] / С. А. Орловский. М. : Наука, 1981.- 208 с.

23. Подиновский, В. В. Оптимизация по последовательно применяемым критериям Текст] / В. В. Подиновский, В. М. Гаврилов. М. : "Сов. радио", 1975. - 192 с.

24. Попов, Л. Д. Введение в теорию, методы и экономические приложения задач о дополнительности Текст]: учеб. пособие / Л. Д. Попов.- Екатеринбург : Изд-во Урал, ун-та, 2001. 124 с.

25. Пшеничный, Б. Н. Выпуклый анализ и экстремальные задачи Текст] / Б. Н. Пшеничный. М. : Наука, 1980. - 320 с.

26. Трухасв, Р. И. Модели принятия решений в условиях неопределенности Текст] / Р. И. Трухаев. М. : Наука, 1981. - 258 с.

27. Чен, К. МАТЬАВ в математических исследованиях Текст]: [пер. с англ.] / К. Чен, П. Джиблин, А. Ирвинг. М. : Мир, 2001. - 346 с.

28. Ширяев, А. Н. Основы стохастической финансовой математики Текст] в 2-х т. / А. Н. Ширяев М.: Фазис, 1998.

29. Штойср, Р. Многокритериальная оптимизация. Теория, вычисления и приложения Текст] / Р. Штойер М.: Радио и связь, 1995. - 504 с.

30. Юдин, Д. Б. Математические методы управления в условиях неполной информации Текст] / Д. Б. Юдин. М. : "Сов. радио", 1974. - 400 с.

31. Cottle R. W. The linear complementarity problem Text] / R. W. Cottle, J. S. Pang, R. T. Stone Boston: Academic press, Inc., 1992.1. Статьи

32. Беркович, E. M. Об аппроксимации двухэтапных стохастических задач Текст] // Журнал вычисл. математики и мат. физики. -1971. Т. И, № 5,- С. 1150-1165.

33. Бсрщанский Я.М., Мееров М.В. Теория и методы решения задач дополнительности Текст] // Автоматика и телемеханика. 1983. -Т. 381, т. - С. 5-31.

34. Ермольев, Ю. М. Методы решения нелинейных экстремальных задач Текст] // Кибернетика. 1966. - № 4. - С. 15-19.

35. Зыкина А.В Построение обобщенного решения линейной системы неравенств Текст] // Оптимизация. Сб.науч.тр.- Новосибирск, ИМ СО АН СССР. 1988. - Вып.43(60). - С. 11-25.

36. Зыкина A.B. О вариационном подходе к решению задачи математического программирования Текст] // Алгебра, геометрия, анализ и математическая физика. Тр. 12-й Сибирской школы. 1999. - С. 68-73.

37. Зыкина A.B. Проблемы численной реализации алгоритма нахождения обобщенного решения Текст] // Росс.конф. "Дискретныйанализ и исследование операций": Мат.конф. (Новосибирск, 24-28 июня 2002). Изд-во ИМ СО РАН, - 2002. - С. 166.

38. Зыкина A.B., Пригнец О.Н. Несобственная задача стохастического программирования Текст] // Математическое программирование и приложения. Информационный бюллетень Ассоциации математического программирования. № 8.- Екатеринбург: УрО РАН, 1999. - С. 126.

39. Зыкина A.B., Канева О.Н. Обобщенное решение для задачи математического программирования с нечеткими исходными данными Текст] // Доклады АН ВШ РФ, 2004. №2(3). - С.34-40.

40. Канева О.Н. Решение стохастической задачи распределения водных ресурсов Текст] //I Всесибирский конгресс женщин математиков (к 150-летию со дня рождения C.B. Ковалевской): Тез. докладов конгресса. Красноярск: ИВМ СО РАН, - 2000. - С. 85.

41. Канева О.Н. Обобщенное решение для задачи в нечеткой постановке Текст]// Математическое программирование и приложения. Информационный бюллетень Ассоциации математического программирования. № 10. Научное издание. Екатеринбург: УрО РАН, -2003. С. 130.

42. Канева О.Н. Решение оптимизационных задач в условиях риска и неопределенности Текст]// Материалы Всероссийской научной молодежной конф. "Под знаком "Сигма" ОНЦ СО РАН, Омск: Полиграфический центр КАН, -2003. С.8-9.

43. Канева О.Н. О решении задачи моделирования малого бизнеса Текст] // Актуальные проблемы подготовки специалистов для сферы сервиса. Междунар. науч.-техн. конф.: Сборник статей. Часть 1, Омск: Изд-во ОмГИС2003. С.143-144.

44. Канева О.Н. О решении задачи математического программирования в нечеткой постановке Текст] // Омский научный вестник.2003. №4(25). - С.34-40.

45. Канева О.Н., Шарканов М.В. Обобщенное решение в регрессионном анализе Текст] // Динамика систем, механизмов и машин: Материалы V Междунар. науч.-техн. конф. Омск: Изд-во ОмГТУ,2004. Кн. 2. - С. 267-270.

46. Канева О.Н. Обобщенное решение в регрессионном анализе Текст] // Росс.конф. "Дискретный анализ и исследование операций" : Мат.конф. Новосибирск: Изд-во ИМ СО РАН, 2004. - С. 130.

47. Канева О.Н. Двухэтапная задача линейного стохастического программирования Текст] // Прикладная математика и информационные технологии. Омск, 2005. - С. 50-58.

48. Канева О.Н. Двухэтапная задача нелинейного стохастического программирования с детерминированной матрицей коррекции Текст]// Математические структуры и моделирование. 2005. -№14. - С. 25-33.

49. Кибзун А.И., Наумов A.B. Двухэтаппые задачи квантильного линейного программирования Текст] // Автоматика и телемеханика,- 1995. Ш. - С. 83-93.

50. Кибзун А.И., Кузнецов Е.А. Оптимальное управление портфелем ценных бумаг Текст] // Автоматика и телемеханика, 2001. - №9.- С. 101-113.

51. Поляк, Б. Т. Об одном общем методе решения экстремальных задач Текст] // Б. Т. Поляк // ДАН СССР. 1967. - № 1. - С. 100-111.

52. Cottle R.W., Dantzig G.B. Complementary pivot theory of mathematical programming Text]// Linear Algebra and Its Applications. 1968. - No. 1. - PP. 103-125.

53. Doverspikc R.D. Some pertirbation results for the linear complementarity problem Text]// Math.Program. 1982. - No. 23. - PP. 181-199.

54. Jahanshahlou G.R., Mitra G. Linear complementarity problem and tree search algorithm for its solution Text] // Survey Math. Program./ Proc. 9th Int. Math. Program. Symp. V.2. Budapest: Academiai Kiado.- 1979.- PP. 35-55.

55. Lemke C.E. Bimatrix equilibrium points and mathematical programming Text]// Manag. Sei 1965. - V. 11, No. 7. - PP. 681-689.

56. Mangasarian O. L. Nonlinear programming problems with stochastic objective functions Text] // Manag. Sei. 1964. - V. 10. - PP. 353359.

57. Mangasarian O. L., Rosen J. B. Inequalities for stochastic nonlinear programming problems Text] // Oper. Res. 1964 - V. 12, No. 1. -PP. 143-154.

58. Mitra G. An exposition of the (linear) complementarity problem Text] // Int. J. Math. Educ. Sci. and Technol. 1979. - V.10, No. 3. - PP. 401-416.

59. Ravindran A. Computational aspects of Lemkc's complementary algorithm applied to linear programs Text] // Opsearch. -1970.- V.7, No. 4. PP. 241-262.1. Отчеты