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

• Канева, Ольга Николаевна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Канева, Ольга Николаевна

Введение

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Канева, Ольга Николаевна, 2005 год

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. Отчеты