Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования
Рассмотрены модели двухэтапного стохастического программирования с квантильным критерием и модели с вероятностным ограничением на случайные значения целевой функции второго этапа. Такие модели позволяют формализовать требования к надежности и безопасности оптимизируемой системы, а также оптимизирова...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2014 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124694 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования / В.И. Норкин, А.И. Кибзун, А.В. Наумов // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 34-48. — Бібліогр.: 35 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859588200690876416 |
|---|---|
| author | Норкин, В.И. Кибзун, А.И. Наумов, А.В. |
| author_facet | Норкин, В.И. Кибзун, А.И. Наумов, А.В. |
| citation_txt | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования / В.И. Норкин, А.И. Кибзун, А.В. Наумов // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 34-48. — Бібліогр.: 35 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Рассмотрены модели двухэтапного стохастического программирования с квантильным критерием и модели с вероятностным ограничением на случайные значения целевой функции второго этапа. Такие модели позволяют формализовать требования к надежности и безопасности оптимизируемой системы, а также оптимизировать ее функционирование в экстремальных условиях. Предложен способ эквивалентного преобразования моделей при дискретном распределении случайных параметров к задачам частично целочисленного программирования. Число дополнительных целочисленных (булевых) переменных в этой задаче равно числу возможных значений вектора случайных параметров. Полученные смешанные задачи решаются с помощью мощных стандартных компьютерных программ дискретной оптимизации. Приведены результаты численного эксперимента на задаче небольшой размерности.
Розглянуто моделі двоетапного стохастичного програмування з квантильним критерієм, а також моделі з імовірнісним обмеженням на випадкові значення цільової функції другого етапу. Такі моделі дозволяють формалізувати вимоги до надійності і безпеки системи, що оптимізується, а також оптимізувати її функціонування в екстремальних умовах. Запропоновано спосіб еквівалентного перетворення моделей при дискретному розподілі випадкових параметрів до задач частково цілочисельного програмування. Число додаткових цілочисельних (булевих) змінних в цій задачі дорівнює числу можливих значень вектора випадкових параметрів. Отримані змішані задачі розв'язуються за допомогою потужних стандартних комп'ютерних програм дискретної оптимізації. Наведено результати чисельного експерименту на задачі невеликої вимірності.
We consider a two-stage stochastic programming model with quantile criterion, as well as models with a probabilistic constraint on the random value of the objective function of the second stage. These models allow us to formalize the requirements for the reliability and safety of the system being optimized and to optimize the system performance under extreme conditions. We propose a method of equivalent transformation of these models under discrete distribution of random parameters to mixed-integer programming problems. The number of additional integer (Boolean) variables in these problems equals to the number of possible values of the vector of random parameters. The obtained mixed optimization problems can be solved by powerful standard discrete optimization software. To illustrate the approach, the results of numerical experiment for the problem of small dimension are presented.
|
| first_indexed | 2025-11-27T11:30:21Z |
| format | Article |
| fulltext |
ÓÄÊ 519.856
Â.È. ÍÎÐÊÈÍ, À.È. ÊÈÁÇÓÍ, À.Â. ÍÀÓÌÎÂ
ÑÂÅÄÅÍÈÅ ÇÀÄÀ× ÄÂÓÕÝÒÀÏÍÎÉ ÂÅÐÎßÒÍÎÑÒÍÎÉ
ÎÏÒÈÌÈÇÀÖÈÈ Ñ ÄÈÑÊÐÅÒÍÛÌ ÐÀÑÏÐÅÄÅËÅÍÈÅÌ
ÑËÓ×ÀÉÍÛÕ ÄÀÍÍÛÕ Ê ÇÀÄÀ×ÀÌ ×ÀÑÒÈ×ÍÎ
ÖÅËÎ×ÈÑËÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß 1
Àííîòàöèÿ. Ðàññìîòðåíû ìîäåëè äâóõýòàïíîãî ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ êâàí-
òèëüíûì êðèòåðèåì è ìîäåëè ñ âåðîÿòíîñòíûì îãðàíè÷åíèåì íà ñëó÷àéíûå çíà÷åíèÿ öåëå-
âîé ôóíêöèè âòîðîãî ýòàïà. Òàêèå ìîäåëè ïîçâîëÿþò ôîðìàëèçîâàòü òðåáîâàíèÿ ê íàäåæíîñ-
òè è áåçîïàñíîñòè îïòèìèçèðóåìîé ñèñòåìû, à òàêæå îïòèìèçèðîâàòü åå ôóíêöèîíèðîâàíèå
â ýêñòðåìàëüíûõ óñëîâèÿõ. Ïðåäëîæåí ñïîñîá ýêâèâàëåíòíîãî ïðåîáðàçîâàíèÿ ìîäåëåé ïðè
äèñêðåòíîì ðàñïðåäåëåíèè ñëó÷àéíûõ ïàðàìåòðîâ ê çàäà÷àì ÷àñòè÷íî öåëî÷èñëåííîãî ïðî-
ãðàììèðîâàíèÿ. ×èñëî äîïîëíèòåëüíûõ öåëî÷èñëåííûõ (áóëåâûõ) ïåðåìåííûõ â ýòîé çàäà÷å
ðàâíî ÷èñëó âîçìîæíûõ çíà÷åíèé âåêòîðà ñëó÷àéíûõ ïàðàìåòðîâ. Ïîëó÷åííûå ñìåøàííûå
çàäà÷è ðåøàþòñÿ ñ ïîìîùüþ ìîùíûõ ñòàíäàðòíûõ êîìïüþòåðíûõ ïðîãðàìì äèñêðåòíîé
îïòèìèçàöèè. Ïðèâåäåíû ðåçóëüòàòû ÷èñëåííîãî ýêñïåðèìåíòà íà çàäà÷å íåáîëüøîé ðàç-
ìåðíîñòè.
Êëþ÷åâûå ñëîâà: ñòîõàñòè÷åñêîå ïðîãðàììèðîâàíèå, äâóõýòàïíûå çàäà÷è, êâàíòèëüíîå
ïðîãðàììèðîâàíèå, âåðîÿòíîñòíûå îãðàíè÷åíèÿ, äåòåðìèíèðîâàííûé ýêâèâàëåíò, ÷àñòè÷-
íî öåëî÷èñëåííûå çàäà÷è îïòèìèçàöèè, äèñêðåòíîå ïðîãðàììèðîâàíèå.
ÂÂÅÄÅÍÈÅ
Òðàäèöèîííî â çàäà÷àõ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ îïòèìèçèðóåòñÿ ñðåä-
íåå çíà÷åíèå ïîêàçàòåëÿ êà÷åñòâà óïðàâëåíèÿ, çàâèñÿùåãî îò ñëó÷àéíîãî ïàðàìåò-
ðà [1–6]. Íàðÿäó ñî ñðåäíèì çíà÷åíèåì ìîæíî èñïîëüçîâàòü èíûå ïîêàçàòåëè êà-
÷åñòâà óïðàâëåíèÿ, íàïðèìåð ìåäèàíó èëè äðóãèå êâàíòèëè ðàñïðåäåëåíèÿ [7–9].
Òàêèå êðèòåðèè êà÷åñòâà ïðèìåíÿåò, â ÷àñòíîñòè, â çàäà÷àõ óïðàâëåíèÿ ëåòàòåëü-
íûìè àïïàðàòàìè [7]. Îäíàêî çàäà÷à îïòèìèçàöèè ôóíêöèè êâàíòèëè áîëåå ñëîæ-
íàÿ, ÷åì îïòèìèçàöèÿ ñðåäíåãî çíà÷åíèÿ, òàê êàê ôóíêöèÿ êâàíòèëè ìîæåò áûòü
íåâûïóêëîé è ðàçðûâíîé. Äëÿ ïðèáëèæåííîé îïòèìèçàöèè êâàíòèëè ÷àñòî èñ-
ïîëüçóþò îïòèìèçàöèþ åå âåðõíåé îöåíêè, ïîëó÷åííóþ äîâåðèòåëüíûì ìåòîäîì
[7–10] èëè ñ ïîìîùüþ CVaR (conditional value at risk) ôóíêöèé [11]. Äðóãèå ìå-
òîäû ïðèáëèæåííîé è ãëîáàëüíîé îïòèìèçàöèè ôóíêöèè êâàíòèëè (ïðèìåíèòåëü-
íî ê çàäà÷àì ïîðòôåëüíîé îïòèìèçàöèè) ïðèâåäåíû â [12].
 ðàáîòàõ [13, 14] íåêîòîðûå çàäà÷è êâàíòèëüíîé îïòèìèçàöèè ñ äèñêðåò-
íûì ðàñïðåäåëåíèåì ñëó÷àéíûõ ïàðàìåòðîâ ñâåäåíû ê çàäà÷àì ÷àñòè÷íî öåëî-
÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Íàèáîëåå îáùèå ðåçóëüòàòû â ýòîì íàïðàâëåíèè
ïîëó÷åíû â [15, 16]. Ðàíåå ïðèåì ñâåäåíèÿ çàäà÷ ñ âåðîÿòíîñòíûìè îãðàíè÷åíèÿ-
ìè, òåñíî ñâÿçàííûõ ñ çàäà÷åé îïòèìèçàöèè ôóíêöèè êâàíòèëè, ê çàäà÷àì
÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ ïðèìåíÿëñÿ â ðàáîòàõ [17–22].
Äâóõýòàïíûå ìîäåëè ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ öåëåâîé ôóíêöè-
åé â âèäå ìàòåìàòè÷åñêîãî îæèäàíèÿ ÿâëÿþòñÿ îäíèìè èç îñíîâíûõ â ñòîõàñòè-
÷åñêîì ïðîãðàììèðîâàíèè [1–6]. Äâóõýòàïíàÿ ìîäåëü ñòîõàñòè÷åñêîãî ïðîãðàì-
ìèðîâàíèÿ îïèñûâàåò ñèòóàöèè ïðèíÿòèÿ ðåøåíèé â óñëîâèÿõ íåîïðåäåëåííîñ-
òè, êîãäà íà ïåðâîì ýòàïå â óñëîâèÿõ ñòîõàñòè÷åñêîé íåîïðåäåëåííîñòè
ïðèíèìàåòñÿ äåòåðìèíèðîâàííîå ðåøåíèå â ðàñ÷åòå íà òî, ÷òî ïðè ïðîÿñíåíèè
ñèòóàöèè íà âòîðîì ýòàïå áóäåò ïðèíÿòî äîïîëíèòåëüíîå îïòèìàëüíîå êîððåêòè-
ðóþùåå ðåøåíèå. Ðåøåíèå ïåðâîãî ýòàïà îïòèìèçèðóåòñÿ ïî ñóììå ìàòåìàòè-
÷åñêîãî îæèäàíèÿ öåëåâûõ ôóíêöèé ïåðâîãî è âòîðîãî ýòàïîâ.
34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
1
Ðàáîòà âûïîëíåíà ïðè ïîääåðæêå Ãîñóäàðñòâåííîãî ôîíäà ôóíäàìåíòàëüíûõ èññëåäîâàíèé
Óêðàèíû â ðàìêàõ ñîâìåñòíîãî ðîññèéñêî-óêðàèíñêîãî ïðîåêòà Ô40.1/016 (2011-2012) è Ðîññèéñêîãî
ôîíäà ôóíäàìåíòàëüíûõ èññëåäîâàíèé (ïðîåêòû 11-07-90407-Óêð-ô-à, 11-07-00315-à), à òàêæå
÷àñòè÷íî ïîääåðæàíà íîðâåæñêî-óêðàèíñêèì ãðàíòîì CPEALA-2012/10052.
© Â.È. Íîðêèí, À.È. Êèáçóí, À.Â. Íàóìîâ, 2014
Äâóõýòàïíûå ìîäåëè ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ÿâëÿþòñÿ ÷àñòíûì
ñëó÷àåì äâóõóðîâíåâûõ êîîïåðàòèâíûõ ìîäåëåé ïðèíÿòèÿ îïòèìàëüíûõ ðåøå-
íèé, â êîòîðûõ öåëåâàÿ ôóíêöèÿ âåðõíåãî óðîâíÿ àääèòèâíî âêëþ÷àåò ñðåäíåå
çíà÷åíèå öåëåâîé ôóíêöèè íèæíåãî óðîâíÿ.
Ïðèìåíèòåëüíî ê îïòèìèçàöèè ýíåðãåòè÷åñêèõ ñèñòåì çàäà÷è äâóõýòàïíîãî
ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ìîæíî èíòåðïðåòèðîâàòü ñëåäóþùèì îáðà-
çîì. Ïåðåìåííûå ïåðâîãî ýòàïà ìîãóò îïèñûâàòü ôóíêöèîíèðîâàíèå äëèòåëüíî
äåéñòâóþùèõ ìîùíûõ ýíåðãåòè÷åñêèõ óñòàíîâîê, çàïóñê è îñòàíîâêà êîòîðûõ
âåñüìà çàòðàòíû. Ïåðåìåííûå âòîðîãî ýòàïà ìîãóò îïèñûâàòü ïðîèçâîäñòâî
ýíåðãèè ìîáèëüíûìè óñòàíîâêàìè, çàïóñê è îñòàíîâêà êîòîðûõ îòíîñèòåëüíî äå-
øåâû, ïðè ýòîì îíè ñðàâíèòåëüíî ëåãêî àäàïòèðóþòñÿ ê ïèêîâûì íàãðóçêàì.
 êà÷åñòâå öåëåâîé ôóíêöèè çàäà÷è (ïðè ïîñòîÿííûõ öåíàõ íà ýíåðãèþ) ïðèíè-
ìàåòñÿ ñðåäíÿÿ ñòîèìîñòü ïðîèçâîäñòâà ýíåðãèè íà âñåõ âèäàõ óñòàíîâîê. Öåëå-
âàÿ ôóíêöèÿ è ïåðåìåííûå âòîðîãî ýòàïà îïèñûâàþò êîëè÷åñòâî ïðîèçâåäåííîé
ýíåðãèè íà ìîáèëüíûõ óñòàíîâêàõ.  ïîñòàíîâêó çàäà÷è ìîæíî âêëþ÷èòü îãðà-
íè÷åíèÿ ñíèçó íà âåðîÿòíîñòü îáåñïå÷åíèÿ ïèêîâûõ ïîòðåáíîñòåé â ýíåðãèè.
Äëÿ ïîñòðîåíèÿ ñòîõàñòè÷åñêîé ìîäåëè ýíåðãåòè÷åñêîé ñèñòåìû íåîáõîäèìû
âåðîÿòíîñòíûå ñöåíàðèè ïîòðåáíîñòè â ýíåðãèè.
Âìåñòî ôóíêöèè ìàòåìàòè÷åñêîãî îæèäàíèÿ â çàäà÷å ñòîõàñòè÷åñêîãî ïðî-
ãðàììèðîâàíèÿ èíîãäà öåëåñîîáðàçíî èñïîëüçîâàòü ôóíêöèþ êâàíòèëè ñëó÷àé-
íîãî îïòèìàëüíîãî çíà÷åíèÿ êðèòåðèàëüíîé ôóíêöèè çàäà÷è âòîðîãî ýòàïà. Ýòî
ïîçâîëÿåò îïòèìèçèðîâàòü ôóíêöèîíèðîâàíèå ñòîõàñòè÷åñêîé ñèñòåìû â ýêñòðå-
ìàëüíûõ óñëîâèÿõ.  ðàáîòàõ [10, 23–26] äâóõýòàïíûå çàäà÷è ñòîõàñòè÷åñêîãî
ïðîãðàììèðîâàíèÿ ñ êâàíòèëüíîé öåëåâîé ôóíêöèåé ðåøàëèñü ñ ïîìîùüþ äîâå-
ðèòåëüíîãî ìåòîäà [8, 9].
 íàñòîÿùåé ñòàòüå çàäà÷è êâàíòèëüíîãî äâóõýòàïíîãî ñòîõàñòè÷åñêîãî ïðî-
ãðàììèðîâàíèÿ, à òàêæå çàäà÷è äâóõýòàïíîãî ñòîõàñòè÷åñêîãî ïðîãðàììèðîâà-
íèÿ ñ âåðîÿòíîñòíûìè îãðàíè÷åíèÿìè ïðè äèñêðåòíîì ðàñïðåäåëåíèè ñëó÷àé-
íûõ äàííûõ ñâîäÿòñÿ ê çàäà÷àì ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ.
Òàêèì îáðàçîì, ðåçóëüòàòû èç ðàáîò [15, 16] ðàñïðîñòðàíÿþòñÿ íà îáùèå äâóõ-
ýòàïíûå çàäà÷è êâàíòèëüíîé è âåðîÿòíîñòíîé îïòèìèçàöèè ñ äèñêðåòíûì ðàñ-
ïðåäåëåíèåì. Äëÿ ðåøåíèÿ âîçíèêàþùèõ ïðè ýòîì ÷àñòè÷íî öåëî÷èñëåííûõ çà-
äà÷ èñïîëüçóåòñÿ ñîâðåìåííûé ñòàíäàðòíûé ïàêåò IBM ILOG CPLEX [27]
ðåøåíèÿ ÷àñòè÷íî öåëî÷èñëåííûõ çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ.
Ïðåèìóùåñòâà äàííîãî ïîäõîäà ê ðåøåíèþ âåðîÿòíîñòíûõ è êâàíòèëüíûõ
çàäà÷ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ çàêëþ÷àþòñÿ â ñëåäóþùåì:
— ôóíêöèè âåðîÿòíîñòè è êâàíòèëè ïîçâîëÿþò ôîðìàëèçîâàòü òðåáîâàíèÿ
ê íàäåæíîñòè è áåçîïàñíîñòè îïòèìèçèðóåìîé ñèñòåìû, à òàêæå îïòèìèçèðîâàòü
åå ôóíêöèîíèðîâàíèå â ýêñòðåìàëüíûõ óñëîâèÿõ;
— äîïóñêàåòñÿ íàëè÷èå êàê íåïðåðûâíûõ, òàê è äèñêðåòíûõ ïåðåìåííûõ
â ïåðâîíà÷àëüíîé ôîðìóëèðîâêå çàäà÷è;
— ïðîáëåìà íåâûïóêëîñòè è ðàçðûâíîñòè âåðîÿòíîñòíûõ è êâàíòèëüíûõ
ôóíêöèé çàäà÷è ïåðåêëàäûâàåòñÿ íà ìåòîäû äèñêðåòíîé îïòèìèçàöèè;
— â ñëó÷àå íåïðåðûâíîãî ðàñïðåäåëåíèÿ ñëó÷àéíûõ äàííûõ åãî ìîæíî àï-
ïðîêñèìèðîâàòü äèñêðåòíûì, íàïðèìåð ýìïèðè÷åñêèì, ðàñïðåäåëåíèåì ñ äîñòà-
òî÷íî áîëüøèì ìíîæåñòâîì ðåàëèçàöèé;
— ïîëó÷åííûå ýêâèâàëåíòíûå çàäà÷è ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììè-
ðîâàíèÿ ìîæíî ðåøàòü ìîùíûìè ñîâðåìåííûìè ïðîãðàììíûìè ñðåäñòâàìè äèñ-
êðåòíîé îïòèìèçàöèè äàæå ïðè âåñüìà áîëüøîì êîëè÷åñòâå ïåðåìåííûõ çàäà÷è
è âîçìîæíûõ ñöåíàðèåâ äëÿ ñëó÷àéíûõ äàííûõ.
ÎÁÎÇÍÀ×ÅÍÈß È ÏÐÅÄÂÀÐÈÒÅËÜÍÛÅ ÑÂÅÄÅÍÈß
Ïóñòü ( , , )� � P — íåêîòîðîå âåðîÿòíîñòíîå ïðîñòðàíñòâî, X m: ( )� �� �X � —
âåêòîðíàÿ ñëó÷àéíàÿ âåëè÷èíà ñî çíà÷åíèÿìè â ìíîæåñòâå X( )� , U n� � — ìíî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 35
æåñòâî äîïóñòèìûõ ñòðàòåãèé îïòèìèçàöèè, � �: ( )U � �X �
1 è Q U: ( )� �X � �
1
— áîðåëåâñêèå ïî x�X( )� ôóíêöèè äëÿ âñåõ u U� . Îïðåäåëèì ôóíêöèè ìà-
òåìàòè÷åñêîãî îæèäàíèÿ
f u u X u X d1 ( ) [ ( , )] ( , ( )) ( )
def
E P� �
�
� � ,
âåðîÿòíîñòè
P u u X Q u X u X Q� � � � �( ) ( , ) , ( , ) : ( , ( )) , ( � � � �
def
P{ }= P{� � �0 u X, ( ))� � 0}
è êâàíòèëè
� � �� �( ) inf : ( )u P u � �
def
{ }�
1
� � � �min : ( , ) , ( , ){ P{ } }� � ��
1 0� u X Q u X , (1)
ãäå � — ïàðàìåòð, 0
� P * , P{ }� — âåðîÿòíîñòü ñîáûòèÿ â ñêîáêàõ (ïî îï-
ðåäåëåíèþ P{ }� 0 ), E — çíàê ìàòåìàòè÷åñêîãî îæèäàíèÿ,
P Q u X
u U
* sup : ( , ( )) � �
�
def
P{ }� �� 0 .
Çàìåòèì, ÷òî ôóíêöèÿ P� ( )� îïðåäåëåíà íà âñåì ìíîæåñòâå U . Ñâîéñòâà ôóíê-
öèé âåðîÿòíîñòè äåòàëüíî èçó÷åíû â [28, 2, 29, 8, 9], à êâàíòèëè — â [30, 8, 9].
Òàê åñëè �( , ), ( , )u x Q u x ïîëóíåïðåðûâíû ñíèçó ïî u ïðè êàæäîì x, òî ôóíêöèÿ
P u� ( ) ïîëóíåïðåðûâíà ñâåðõó ïî ñîâîêóïíîñòè ïåðåìåííûõ ( , )u � [31]. Êðîìå
òîãî, ôóíêöèÿ P u� ( ) ìîíîòîííà (íå óáûâàåò) ïî � è íåïðåðûâíà ñïðàâà, ïîý-
òîìó èíôèíóì â îïðåäåëåíèè �� ( )u äîñòèãàåòñÿ. Ôóíêöèÿ êâàíòèëè ÿâëÿåòñÿ
ñïåöèàëüíûì ñëó÷àåì ìàðãèíàëüíîé ôóíêöèè (ôóíêöèè ìèíèìóìà), ïîýòîìó
ïðè ñäåëàííûõ ïðåäïîëîæåíèÿõ îíà ïîëóíåïðåðûâíà ñíèçó ïî ( , )u � [32, ãë. 1,
ðàçä. 1, ïðåäëîæåíèå 21].
 ñèëó íåïðåðûâíîñòè âåðîÿòíîñòíîé ìåðû èìååò ìåñòî
lim ( , ) , ( , ) ( , )
�
�
���
� � �P{ } P{ }� u X Q u X Q u X0 0 , (2)
lim ( , ) , ( , )
�
�
���
� � P{ }� u X Q u X 0 0 . (3)
ÇÀÄÀ×À ÎÏÒÈÌÈÇÀÖÈÈ ÔÓÍÊÖÈÈ ÊÂÀÍÒÈËÈ
Ïðîñòåéøàÿ çàäà÷à (îäíîýòàïíîãî) ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ èìååò
âèä [1–6]
f u u X
u U
1 ( ) [ ( , )] inf �
�
def
E � ,
ãäå ìèíèìèçèðóåòñÿ ñðåäíåå çíà÷åíèå ñëó÷àéíîãî ïîêàçàòåëÿ �( , )u X íà ìíî-
æåñòâå U çíà÷åíèé äåòåðìèíèðîâàííîãî ïàðàìåòðà u. Âìåñòî ñðåäíåãî çíà÷å-
íèÿ â êà÷åñòâå öåëåâîé ôóíêöèè ìîæíî èñïîëüçîâàòü ìåäèàíó ðàñïðåäåëåíèÿ
ñëó÷àéíîé âåëè÷èíû �( , )u X èëè êâàíòèëü óðîâíÿ � , 0
� P * . Çàäà÷à ìèíè-
ìèçàöèè ôóíêöèè êâàíòèëè èìååò âèä [33, 30, 8]
� � � �� ( ) min : ( , ) , ( , ) infu u X Q u X
u U
� � � � �
�
def
{ P{ } }�
1 0� . (4)
Èçâåñòíî, ÷òî îíà ýêâèâàëåíòíà ñëåäóþùåé çàäà÷å [8, sec. 4.2]:
�
� �
�
�
�
� � � �
� �
inf ,
( ) ( , ) , ( , ) .
,�
1
0 0
u U
P u u X Q u XP{ }�
(5)
 äàëüíåéøåì ðàññìîòðèì è äðóãèå ýêâèâàëåíòíûå îïòèìèçàöèîííûå çàäà-
÷è, ïðè ýòîì ýêâèâàëåíòíîñòü áóäåò ïîíèìàòüñÿ â ñëåäóþùåì ñìûñëå. Ðàññìîò-
ðèì îáùóþ çàäà÷ó ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ.
36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
Îïðåäåëåíèå 1. Ïîä çàäà÷åé ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ áóäåì ïî-
íèìàòü çàäà÷ó ìèíèìèçàöèè öåëåâîé ôóíêöèè � : U � �
1, îïðåäåëåííîé íà íå-
êîòîðîì äîïóñòèìîì ìíîæåñòâå U òî÷åê (ñòðàòåãèé), â ôîðìàëüíîé çàïèñè
�( ) infu
u U
�
�
. (6)
Ýëåìåíòû u U� íàçîâåì äîïóñòèìûìè ðåøåíèÿìè çàäà÷è. Ìíîæåñòâî U ìîæåò
áûòü ïóñòûì, òîãäà áóäåì ñ÷èòàòü, ÷òî çàäà÷à íå èìååò äîïóñòèìûõ ðåøåíèé.
Îïðåäåëåíèå 2. Íèæíþþ ãðàíü �
* (êîíå÷íóþ èëè áåñêîíå÷íóþ) �( )u íà U ,
�
�
�
inf ( )
u U
u� , íàçîâåì îïòèìàëüíûì çíà÷åíèåì öåëåâîé ôóíêöèè çàäà÷è (6).
Åñëè �
� � �� è ñóùåñòâóåò äîïóñòèìàÿ òî÷êà u U� � òàêàÿ, ÷òî �
� � �( )u , òî
ïîëàãàåì, ÷òî îïòèìàëüíîå çíà÷åíèå çàäà÷è (6) äîñòèãàåòñÿ, à òî÷êó u� íàçîâåì
îïòèìàëüíûì ðåøåíèåì çàäà÷è. Òîãäà çàïèøåì �* min ( )
�u U
u� . Â ïðîòèâíîì ñëó-
÷àå, ò.å. åñëè �
� �� èëè íå ñóùåñòâóåò òî÷êè u U� � òàêîé, ÷òî �
� � �( )u ,
áóäåì ñ÷èòàòü, ÷òî îïòèìàëüíîå çíà÷åíèå çàäà÷è íå äîñòèãàåòñÿ.
Îïðåäåëåíèå 3. Äâå çàäà÷è îïòèìèçàöèè âèäà (6) ýêâèâàëåíòíû, åñëè âû-
ïîëíåíû ñëåäóþùèå óñëîâèÿ:
1) ëèáî îáå çàäà÷è èìåþò äîïóñòèìûå ðåøåíèÿ (ñ êîíå÷íûìè çíà÷åíèÿìè
öåëåâûõ ôóíêöèé), ëèáî îáå íå èìåþò òàêèõ ðåøåíèé;
2) åñëè ýòè çàäà÷è èìåþò äîïóñòèìûå ðåøåíèÿ, òî îïòèìàëüíûå çíà÷åíèÿ èõ
öåëåâûõ ôóíêöèé (êîíå÷íûå èëè áåñêîíå÷íûå) ñîâïàäàþò;
3) åñëè îïòèìàëüíûå çíà÷åíèÿ èõ öåëåâûõ ôóíêöèé êîíå÷íû, òî ýòè çíà÷å-
íèÿ â îáåèõ çàäà÷àõ ëèáî äîñòèãàþòñÿ, ëèáî íå äîñòèãàþòñÿ;
4) åñëè îïòèìàëüíûå çíà÷åíèÿ äîñòèãàþòñÿ, òî ïî îïòèìàëüíîìó ðåøåíèþ
îäíîé çàäà÷è ñ ïîìîùüþ ÿâíî óêàçàííîãî àëãîðèòìà çà êîíå÷íîå ÷èñëî øàãîâ
âîññòàíàâëèâàåòñÿ îïòèìàëüíîå ðåøåíèå äðóãîé.
Çàìåòèì, ÷òî åñëè îïòèìàëüíîå ðåøåíèå çàäà÷è u� ñóùåñòâóåò, òî ýòî îçíà÷à-
åò, ÷òî îïòèìàëüíîå çíà÷åíèå �
� � �( )u êðèòåðèàëüíîé ôóíêöèè äîñòèãàåòñÿ.
Îòìåòèì, ÷òî ââåäåííîå îòíîøåíèå ýêâèâàëåíòíîñòè îïòèìèçàöèîííûõ çà-
äà÷ òðàíçèòèâíî.
Äîêàçàòåëüñòâî ýêâèâàëåíòíîñòè îïòèìèçàöèîííûõ çàäà÷ îñíîâàíî íà óñòà-
íîâëåíèè ñïåöèàëüíîãî ñîîòâåòñòâèÿ ìåæäó ìíîæåñòâàìè äîïóñòèìûõ ñòðàòåãèé
çàäà÷, à èìåííî, äëÿ êàæäîé äîïóñòèìîé ñòðàòåãèè îäíîé çàäà÷è óêàçûâàåòñÿ äî-
ïóñòèìàÿ ñòðàòåãèÿ äðóãîé ñ òàêèì æå èëè ìåíüøèì çíà÷åíèåì öåëåâîé ôóíêöèè.
Ëåììà 1. Äâå îïòèìèçàöèîííûå çàäà÷è
�1
1
( ) infu
u U
�
�
, �2
2
( ) infu
u U
�
�
(7)
ýêâèâàëåíòíû â ñìûñëå îïðåäåëåíèÿ 3, åñëè èçâåñòíû àëãîðèòìû (îòîáðàæå-
íèÿ) A U U1 1 2: � è A U U2 2 1: � , êîòîðûå äëÿ êàæäîé äîïóñòèìîé ñòðàòåãèè
îäíîé çàäà÷è óêàçûâàþò äîïóñòèìóþ ñòðàòåãèþ äðóãîé çàäà÷è ñ òàêèì æå
èëè ìåíüøèì çíà÷åíèåì öåëåâîé ôóíêöèè, ò.å. äëÿ ëþáûõ u U1 1� è u U2 2�
âûïîëíåíî � �2 1 1 1 1( ( )) ( )A u u� , � �1 2 2 2 2( ( )) ( )A u u� .
Ïðè ýòîì åñëè u1
� — îïòèìàëüíîå ðåøåíèå ïåðâîé çàäà÷è, òî A u1 1( )� — îïòè-
ìàëüíîå ðåøåíèå âòîðîé çàäà÷è è � �1 1 2 1 1( ) ( ( ))u A u� � . Íàîáîðîò, åñëè u2
� — îï-
òèìàëüíîå ðåøåíèå âòîðîé çàäà÷è, òî A u2 2( )� — îïòèìàëüíîå ðåøåíèå ïåðâîé
çàäà÷è è � �2 2 1 2 2( ) ( ( ))u A u� � .
Äîêàçàòåëüñòâî ëåììû ïðèâåäåíî â [15]. Ïîäîáíûé ñïîñîá äîêàçàòåëüñòâà ýê-
âèâàëåíòíîñòè çàäà÷ ïðèìåíÿëñÿ, íàïðèìåð, â [34, ñ. 131; 35, 13, 22, 14]. Òàêèì îá-
ðàçîì, äëÿ äîêàçàòåëüñòâà ýêâèâàëåíòíîñòè, âîîáùå ãîâîðÿ, íåò íåîáõîäèìîñòè
ïðåäïîëàãàòü ñóùåñòâîâàíèå ðåøåíèÿ èñõîäíîé çàäà÷è; åãî ñóùåñòâîâàíèå èëè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 37
íåñóùåñòâîâàíèå âîçìîæíî óñòàíîâèòü â õîäå ðåøåíèÿ ýêâèâàëåíòíîé çàäà÷è. Åñëè
èçâåñòíî, ÷òî îäíà èç çàäà÷ èìååò îïòèìàëüíîå ðåøåíèå, òî äîñòàòî÷íûå óñëîâèÿ ýê-
âèâàëåíòíîñòè îïòèìèçàöèîííûõ çàäà÷ èç ëåììû 1 ìîæíî íåñêîëüêî îñëàáèòü.
Ëåììà 2. Ïðåäïîëîæèì, ÷òî îäíà èç çàäà÷ (7) (ïåðâàÿ) èìååò îïòèìàëüíîå
ðåøåíèå u U1 1
� � è ñóùåñòâóåò äîïóñòèìàÿ òî÷êà � �u U2 2 äðóãîé çàäà÷è òàêàÿ,
÷òî � �2 2 1 1( ) ( )� � �u u . Ïðåäïîëîæèì òàêæå, ÷òî èçâåñòåí àëãîðèòì (îòîáðàæå-
íèå) A U U2 2 1: � , êîòîðûé äëÿ êàæäîé äîïóñòèìîé òî÷êè âòîðîé çàäà÷è óêàçû-
âàåò äîïóñòèìóþ òî÷êó ïåðâîé çàäà÷è ñ òàêèì æå èëè ìåíüøèì çíà÷åíèåì öåëå-
âîé ôóíêöèè, ò.å. äëÿ ëþáîãî u U2 2� âûïîëíåíî � �1 2 2 2 2( ( )) ( )A u u� . Òîãäà
è âòîðàÿ çàäà÷à èìååò îïòèìàëüíûå ðåøåíèÿ, ïðè÷åì � �u U2 2 — îäíî èç òàêèõ
îïòèìàëüíûõ ðåøåíèé, à A u2 2( )� — îïòèìàëüíîå ðåøåíèå ïåðâîé çàäà÷è, è îïòè-
ìàëüíûå çíà÷åíèÿ îáåèõ çàäà÷ ñîâïàäàþò. Òàêèì îáðàçîì, ðàññìàòðèâàåìûå
îïòèìèçàöèîííûå çàäà÷è ýêâèâàëåíòíû.
Äîêàçàòåëüñòâî.  ñèëó îïòèìàëüíîñòè òî÷êè u1
� èìååì
� � � �1 1 2 2 1 2 2 1 1( ) ( ) ( ( )) ( )u u A u u� �� � � � ,
ò.å. � � �1 1 1 2 2 2 2( ) ( ( )) ( )u A u u� � � è, òàêèì îáðàçîì, A u2 2( )� — îïòèìàëüíîå
ðåøåíèå ïåðâîé çàäà÷è. Ïîêàæåì, ÷òî �u2 ÿâëÿåòñÿ îïòèìàëüíûì ðåøåíèåì
âòîðîé çàäà÷è. Ïðåäïîëîæèì ïðîòèâíîå. Òîãäà ñóùåñòâóåò äðóãàÿ äîïóñòèìàÿ
òî÷êà �� �u U2 2 ñ ìåíüøèì çíà÷åíèåì öåëåâîé ôóíêöèè, � �2 2 2 2( ) ( )��
�u u . Íî
ïî ïðåäïîëîæåíèþ ñóùåñòâóåò äîïóñòèìàÿ òî÷êà ïåðâîé çàäà÷è A u U2 2 1( )�� �
òàêàÿ, ÷òî � � � �1 2 2 2 2 2 2 1 1( ( )) ( ) ( ) ( )A u u u u�� � ��
� � � , ÷òî ïðîòèâîðå÷èò îïòè-
ìàëüíîñòè òî÷êè u1
� . Ëåììà äîêàçàíà.
Ïðåäïîëîæåíèå 1. Ñëó÷àéíàÿ âåëè÷èíà X ïðèíèìàåò êîíå÷íîå ÷èñëî çíà÷åíèé,
ò.å. X { }( ) , , ,� x x xK1 2 � , ñ âåðîÿòíîñòÿìè p p pK1 20 0 0� � �, , ,� , pk
k
K
�
1
1.
Ïðåäïîëîæåíèå 2. Çàäàíû ôóíêöèè �1 ( , )u x è �2 ( , )u x òàêèå, ÷òî äëÿ ëþ-
áûõ u U� , x�X( )� âûïîëíåíî
��
� �
�
�1 0( , ) inf ( , ) : ( , )
( )
u x u x Q u x
x X
{ }
�
� , (8)
��
� �
�
�
�
�
��
�2 0( , ) max , inf ( , )
( )
u x Q u x
x X �
. (9)
Óñëîâèå (9) îçíà÷àåò, ÷òî ëèáî �2 0( , )u x � , ëèáî �
2
( , ) inf ( , )
( )
u x Q u x
x
�
�X �
.
Ðàññìîòðèì çàäà÷ó ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ
�
� �
�
�
� � �
� � � �
inf ,
( , ) ( ( , ) ( , ))
, ,�
1
1
1
u U w w
k k k
K
u x u x u x
�
� � w k K
Q u x Q u x u x w k K
w p
k
k k k k
k k
k
, , ,
( , ) ( ( , ) ( , )) , , ,
� �
1
12�
1
1
0 1 1
K
kw k K
� � �
�
�
�
�
�
�
��
�
�
�
�
�
�
�,
, , , .{ }
(10)
 ðàáîòå [15] ïîëó÷åí ñëåäóþùèé ðåçóëüòàò î âîçìîæíîñòè ñâåäåíèÿ çàäà÷è
êâàíòèëüíîé îïòèìèçàöèè (4) ê çàäà÷àì ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ.
Òåîðåìà 1. Åñëè âûïîëíåíû ïðåäïîëîæåíèÿ 1 è 2, òî ÷àñòè÷íî öåëî÷èñëåí-
íàÿ çàäà÷à îïòèìèçàöèè (10) ýêâèâàëåíòíà â ñìûñëå îïðåäåëåíèÿ 3 êàæäîé èç çà-
äà÷ (4), (5). Ïðè ýòîì åñëè ( , , , ..., )�
� � � �u w wK1 — îïòèìàëüíîå ðåøåíèå çàäà-
÷è (10), òî u� , ( , )�
� �u — îïòèìàëüíûå ðåøåíèÿ ñîîòâåòñòâåííî çàäà÷ (4), (5).
38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
Çàìå÷àíèå 1.  ðàáîòå [15] âìåñòî (8) èñïîëüçîâàëîñü áîëåå ñèëüíîå óñëî-
âèå: ��
�
�
�
1
( , ) inf ( , )
( )
u x u x
x X �
� äëÿ ëþáîãî u U� . Îäíàêî äîêàçàòåëüñòâî è ðå-
çóëüòàò òåîðåìû 1 ñîõðàíÿþò ñèëó ïðè áîëåå ñëàáîì óñëîâèè (8).
Çàìå÷àíèå 2. Çàäà÷à (10) â îáùåì ñëó÷àå ÿâëÿåòñÿ çàäà÷åé íåëèíåéíîãî ÷àñ-
òè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ, äàæå åñëè ôóíêöèè �, Q ëèíåéíû ïî u .
Îäíàêî â ñèëó îïðåäåëåííîé ñâîáîäû â âûáîðå ôóíêöèé �1, �2 èõ ÷àñòî ìîæíî
âûáðàòü òàê, ÷òî çàäà÷à (10) îêàçûâàåòñÿ âûïóêëîé (èëè äàæå ëèíåéíîé) ÷àñòè÷-
íî öåëî÷èñëåííîé, äëÿ ðåøåíèÿ êîòîðîé ìîæíî ïðèìåíÿòü ìåòîäû ñîêðàùåíèÿ
ïåðåáîðà, ðåàëèçîâàííûå â ïàêåòàõ ïðîãðàìì ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàì-
ìèðîâàíèÿ, íàïðèìåð IBM ILOG CPLEX [27].  îáùåì ñëó÷àå ðåøåíèå çàäà÷è
(10) ñâîäèòñÿ ê ïåðåáîðó âàðèàíòîâ-ïîäìíîæåñòâ I K1 1� { }, ..., òàêèõ, ÷òî
k I k
p�� � �
1
1 � , ðåøåíèþ ñîîòâåòñòâóþùèõ ïîäçàäà÷ ìàòåìàòè÷åñêîãî ïðî-
ãðàììèðîâàíèÿ âèäà
�
�
� �
�
�
� �
�
� �
inf ,
( , ) , , , , \ ,
( , ) ,
,�
1
1 2 1
1
u U
k
k
u x k K I
u x
� { }�
k I
Q u x k K I
u x k I
k
k
�
� �
� �
�
�
�
�
1
1
2 1
0 1 2
0
,
( , ) , , , , \ ,
( , ) , ,
{ }�
�
��
�
�
�
�
�
(11)
è âûáîðó âàðèàíòà ñ ìèíèìàëüíûì çíà÷åíèåì öåëåâîé ôóíêöèè. Åñëè ìíî-
æåñòâî U âûïóêëî è ôóíêöèè �, Q, �1, �2 âûïóêëû ïî u U� , òî (11) — çàäà-
÷à âûïóêëîãî ïðîãðàììèðîâàíèÿ. Åñëè, êðîìå òîãî, �, Q, �1, �2 êóñî÷íî-ëè-
íåéíû ïî u, à U çàäàåòñÿ ëèíåéíûìè îãðàíè÷åíèÿìè, òî (11) ñâîäèòñÿ ê çàäà-
÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ.
Çàìå÷àíèå 3. Ðåçóëüòàò òåîðåìû 1 ìîæíî îáîáùèòü íà çàäà÷è êâàíòèëüíîé
îïòèìèçàöèè ñ ôóíêöèÿìè äèñêðåòíîãî ìàêñèìóìà, à èìåííî, ïóñòü â çàäà÷àõ
(4), (5) ôóíêöèè �, Q èìåþò âèä
� �( , ) max ( , ), ( , ) max ( , )u x u x Q u x Q u x
i I
i
j J
j
� �
, (12)
ãäå I J, — êîíå÷íûå ìíîæåñòâà èíäåêñîâ. Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò
ôóíêöèè �1i u x( , ), �2 j u x( , ) , óäîâëåòâîðÿþùèå ïðè êàæäîì u U x� �, ( )X � è
i I� , j J� óñëîâèÿì
��
�
�
�1i
x
iu x u x( , ) inf ( , )
( )X �
� , (13)
��
� �
�
�
�
�
��
�2 0j
x
ju x Q u x( , ) max , inf ( , )
( )X �
. (14)
Ñîñòàâèì ñëåäóþùóþ çàäà÷ó ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ:
�
� �
�
�
� � �
� �
inf ,
( , ) ( ( , ) (
, , ,...,�
1
1
1
u U w w
i k i k i
K
u x u x u� � , )) , , , ,
( , ) ( ( , ) ( , )) ,
x w i I k K
Q u x Q u x u x w
k k
j k j k j k k
�
� �
1
2� j J k K
w p
w k K
k k
k
K
k
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
, , ,
,
, , , .
1
1
0 1 1
1
�
{ }
�
�
(15)
Ñëåäñòâèå 1. Çàäà÷è (4), (5) ïðè óñëîâèÿõ (12)–(14) ýêâèâàëåíòíû çàäà÷å
÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ (15).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 39
Çàìå÷àíèå 4. Õîòÿ çàäà÷è (10), (15) íå ëèíåéíû ïî ( , )u wk , â ñèëó äîñòàòî÷-
íîé ñâîáîäû â âûáîðå ôóíêöèé � � � �1 2 1 2, , ,i j ïîñëåäíèå ìîæíî ïîäîáðàòü
òàê, ÷òî êîýôôèöèåíòû ïðè wk íå áóäóò çàâèñåòü îò u è, òàêèì îáðàçîì, óêàçàí-
íûå çàäà÷è ñòàíóò ëèíåéíûìè ïî wk . Ëèíåéíîñòü ïî wk ïîçâîëÿåò èñïîëüçîâàòü
íåïðåðûâíóþ ðåëàêñàöèþ çàäà÷ (10), (15) äëÿ ïîëó÷åíèÿ îöåíîê ñíèçó îïòèìàëü-
íûõ çíà÷åíèé ýòèõ çàäà÷. Åñëè ïðè ýòîì ôóíêöèè �, Q ÿâëÿþòñÿ ôóíêöèÿìè ìàê-
ñèìóìà èç ëèíåéíûõ ôóíêöèé è ìíîæåñòâîU ïîëèýäðàëüíî, òî ïðèõîäèì ê çàäà-
÷å (15) ÷àñòè÷íî öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ, êîòîðóþ ìîæíî
ðåøèòü ñòàíäàðòíûìè ïðîãðàììíûìè ïàêåòàìè îïòèìèçàöèè, íàïðèìåð IBM
ILOG CPLEX [27]. Ñëåäóþùèå ïðèìåðû èëëþñòðèðóþò ýòè âîçìîæíîñòè.
Ïðèìåð 1. Ñäåëàåì ïðåäïîëîæåíèÿ îá îáëàñòè èçìåíåíèé ôóíêöèé çàäà÷è.
Ïóñòü ñóùåñòâóþò (èçâåñòíû) êîíñòàíòà � è ôóíêöèè M x( ) è N x( ) òàêèå, ÷òî
ôóíêöèè �, Q èç (4), (10) óäîâëåòâîðÿþò ñëåäóþùèì óñëîâèÿì:
2.1' . ��
� �
� �
� inf ( , ) : ( , )
, ( )u U x
u x Q u x
X
{ }
�
� 0 ;
2.2' . sup ( , ) ( ) , sup ( , ) ( )
u U u U
u x M x Q u x N x
� �
�
� �
�� âûïîëíåíî äëÿ âñåõ
x�X( )� .
Âûáåðåì ôóíêöèè
� � �1 2( , ) ( , ) ( ) , ( , ) ( , ) ( )u x u x M x u x Q u x N x � � �� . (16)
Îíè óäîâëåòâîðÿþò ïðåäïîëîæåíèþ 2. Äåéñòâèòåëüíî, äëÿ ëþáîãî u U� â ñèëó
óñëîâèé 2.1' è 2.2' âûïîëíåíî
� �1 0( , ) inf ( , ) : ( , ) inf
, ( ) ( )
u x u x Q u x
u U x x X
� � � �
� � �X
{ }
� �
� { }�( , ) : ( , )u x Q u x � 0 ,
�2 0( , ) ( , ) ( )u x Q u x N x � � .
Ôóíêöèè M x( ), N x( ) è ÷èñëî � çàâåäîìî ñóùåñòâóþò, åñëè ôóíêöèè �( , )u x ,
Q u x( , ) íåïðåðûâíû ïî u ïðè êàæäîì x�X( )� è ìíîæåñòâî U êîìïàêòíî.
Ïîäñòàâëÿÿ (16) â (10), ïðèõîäèì ê ñëåäóþùåé ëèíåéíîé ïî áóëåâûì ïåðå-
ìåííûì çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ, ýêâèâàëåíòíîé ïðè
ïðåäïîëîæåíèÿõ 1, 2.1' è 2.2' èñõîäíûì çàäà÷àì (4), (5):
�
�
�
�
� �
� � � �
�
inf ,
,
(
, , , , , ,�
1
1 0 1 0 1
1
1
u U w w
k k
k
K
K
p w
{ } { }�
� u x M x w k K
Q u x N x w k
k k k
k k k
, ) ( ( ) ) , , , , ,
( , ) ( ) , ,
� � �
�
� � 1 2
1
�
2, , .� K
�
�
�
�
�
�
�
�
�
(17)
Ïðèìåð 2. Ðàññìîòðèì ÷àñòíûé ñëó÷àé çàäà÷è (4), êîãäà ôóíêöèè �( , )u x
è Q u x( , ) ñåïàðàáåëüíû è èìåþò âèä
� � �( , ) ( ) ( ), ( , ) ( ) ( ).u x u x Q u x Q u Q x � �1 2 1 2
Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò êîíñòàíòà �3 òàêàÿ, ÷òî
��
� �
�
�
�
�
�� �
�3 2 2min inf ( ), inf ( )
( ) ( )x x
x Q x
X X� �
� .
Âûáåðåì
� � � �1 1 3 1 1 3( , ) ( ) , ( , ) ( )u x u u x Q u � �� . (18)
Ýòè ôóíêöèè óäîâëåòâîðÿþò ïðåäïîëîæåíèÿì 2. Äåéñòâèòåëüíî,
� �1 1 3 1 2( , ) ( ) ( ) inf ( )
( )
u x u u x
x
� � � �
�
� � �
�X
� � � �
� �
inf ( ) ( ) inf ( , ) : ( , )
( ) ( )x x
u x u x Q u x
X X
{ } { }
� �
� � �1 2 0 .
40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
Àíàëîãè÷íî ïðîâåðÿåòñÿ âòîðîå óñëîâèå ïðåäïîëîæåíèÿ 2. Ïîäñòàâëÿÿ (18)
â (10), ïðèõîäèì åùå ê îäíîé çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðî-
âàíèÿ, ýêâèâàëåíòíîé ïðè ñäåëàííûõ ïðåäïîëîæåíèÿõ çàäà÷å (4):
�
� �
�
�
� � � �
� � � �
inf ,
( ) ( ) ( ( ) )
, ,�
1
1
1 2 2 3
u U w w
k k k
K
u x w x
�
� � � , , ,
( ) ( ) ( ( ) ) , , ,
k K
Q u Q x w Q x k K
w p
k k k
k k
k
K
� � � �
1
0 11 2 2 3
1
�
� � �
�
�
�
�
�
�
��
�
�
�
�
�
�
1
0 1 1
�,
, , , .w k Kk { }
(19)
Çàìåòèì, ÷òî åñëè ôóíêöèè �1 ( )u è Q u1 ( ) âûïóêëû ïî u U� , òî çàäà÷à (19) ÿâ-
ëÿåòñÿ çàäà÷åé ñìåøàííîãî âûïóêëîãî ïðîãðàììèðîâàíèÿ.
Ïðèìåð 3.  ðàáîòå [14] ðàññìîòðåí åùå îäèí ÷àñòíûé ñëó÷àé çàäà÷è (4),
êîãäà ôóíêöèè �( , )u x è Q u x( , ) ÿâëÿþòñÿ êóñî÷íî-ëèíåéíûìè âûïóêëûìè ôóíê-
öèÿìè ìàêñèìóìà âèäà
�( , ) max ( ),
( , ) max
, ,
, ,
u x A u B x b
Q u x
i k
i i i
j
� �
1
1 1 1
1
1�
� k
j j jA u B x b
2
2 2 2( ),� �
(20)
ãäå u u n�[ , ]0 , x m�� , A A B Bi j i j1 2 1 2, , , — ñòðîêè ìàòðèö A A B B1 2 1 2, , , ñîîò-
âåòñòâåííî, b bi j1 2, — êîìïîíåíòû âåêòîðîâ b b1 2, . Ïóñòü �3 îïðåäåëÿåòñÿ
ñëåäóþùèì îáðàçîì:
�3
1 1
1
1 1
2
1 2
�
�
�
�
min min , min
, , , , , ,i k k K
i k
j k k K
j kB x B x
�
�
�
.
 óêàçàííîé ðàáîòå äîêàçàíî, ÷òî â ýòîì ñëó÷àå ïðè ìíîãîãðàííîì âûïóêëîì
ìíîæåñòâå U çàäà÷à (5) ýêâèâàëåíòíà çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ëèíåé-
íîãî ïðîãðàììèðîâàíèÿ
�
� � �
�
�
� � � � �
� �
inf ,
( )
, , ,...,�
1
1
1 3 1 3 1
u U w w
i k i k i
K
A u w B x b , , , , ,
( ) , , ,
i k k K
A u w B x b j k kj k j k j
� � � � �
1 1
0 1
1
2 3 2 3 2 2� � 1
0 1 1
1
, ,
,
, , , .
K
p w
w k K
k k
k
K
k
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
{ }
(21)
Äàííàÿ çàäà÷à ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì çàäà÷è (15).
Çàìå÷àíèå 5. Äëÿ ïðîâåðêè êîððåêòíîñòè ïîñòàíîâêè çàäà÷ (4), (5) â ñè-
ëó (2) íåîáõîäèìî íàéòè
P Q u X
u U
�
�
�sup ( , )P{ }0 . (22)
Çàäà÷à ìàêñèìèçàöèè âåðîÿòíîñòè (22) â ïðåäïîëîæåíèè (9) ñâîäèòñÿ ê ñëåäó-
þùåé çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ [15, 22, 14]:
p w
Q u x Q u
k
k
K
k
u U w w
k
K � � �
� �
�
1 0 1 0 11
sup ,
( , ) ( ( ,
, , , , ,{ } { }�
x u x w k Kk k k) ( , )) , , , .� �2 1 �
(23)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 41
ÇÀÄÀ×È ÄÂÓÕÝÒÀÏÍÎÃÎ ÊÂÀÍÒÈËÜÍÎÃÎ
ÑÒÎÕÀÑÒÈ×ÅÑÊÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
Äâóõýòàïíàÿ çàäà÷à ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ êðèòåðèåì â ôîðìå ìà-
òåìàòè÷åñêîãî îæèäàíèÿ èìååò ñëåäóþùèé âèä [1, Ch. 12; 3, sec. 3.4; 4, Ch. 2;
5, ãë. IV, § 3; 6, ãë. 6]:
f u u X
u U
1 ( ) [ ( , )] min� �
�
E � ,
ãäå
�( , )
( , ) inf ( , , ), ( , ) ,
,
*
( , )u x
f u x f u x W u x
W
W u x
��
��
�
2 2
�
�
( , ) ,
( , ) ( ) : ( , , ) ,
u x
W u x V x Q u x
�
�
�
�
��
� �{ }� �2 0
(24)
U n� � — ìíîæåñòâî äîïóñòèìûõ ñòðàòåãèé ïåðâîãî ýòàïà; u U� — äåòåðìè-
íèðîâàííàÿ ñòðàòåãèÿ ïåðâîãî ýòàïà; f u1 ( ) — öåëåâàÿ ôóíêöèÿ ïåðâîãî ýòàïà;
X — ñëó÷àéíûé ïàðàìåòð, ïðèíèìàþùèé (â äàííîé ñòàòüå) êîíå÷íîå ìíîæåñ-
òâî çíà÷åíèé X { }( ) , ,� x xK1 � ñ âåðîÿòíîñòÿìè p pK1, ,� (ïðåäïîëîæå-
íèå 1); V x m( ) � — ìíîæåñòâî äîïóñòèìûõ ñòðàòåãèé âòîðîãî ýòàïà ïðè
X x ; ��V x( ) — ñòðàòåãèÿ âòîðîãî ýòàïà (êîððåêöèÿ); f u x2 ( , , )� — öåëåâàÿ
ôóíêöèÿ âòîðîãî ýòàïà; Q u x2 ( , , )� — ôóíêöèÿ â îãðàíè÷åíèÿõ âòîðîãî ýòàïà;
E — çíàê ìàòåìàòè÷åñêîãî îæèäàíèÿ.
Îòìåòèì, ÷òî ìíîæåñòâî äîïóñòèìûõ ñòðàòåãèé â äâóõýòàïíîé çàäà÷å ìîæåò
áûòü �æå, ÷åì U , ïîñêîëüêó îíî âêëþ÷àåò íåÿâíîå îãðàíè÷åíèå E[ ( , )]� u X
�� .
Íåèíòåãðèðóåìîñòü âåëè÷èíû �( , )u X ìîæåò âîçíèêàòü êàê â ñèëó íåèíòåãðèðó-
åìîñòè ñëó÷àéíûõ ïàðàìåòðîâ çàäà÷è, òàê è â ñèëó âîçìîæíûõ áåñêîíå÷íûõ çíà-
÷åíèé �( , )u X .
Âìåñòî ñðåäíåãî E[ ( , )]� u X â äâóõýòàïíîé çàäà÷å âîçìîæíî èñïîëüçîâàíèå
ìåäèàíû èëè êâàíòèëè óðîâíÿ � ñëó÷àéíîé âåëè÷èíû �( , )u X [10, 23–25].
Îïðåäåëèì ôóíêöèè âåðîÿòíîñòè è êâàíòèëè:
P u u X u P u� � � �� � � � �( ) ( , ) , ( ) min : ( ) , � �
P{ } { }� 0 1.
Äâóõýòàïíàÿ çàäà÷à êâàíòèëüíîé îïòèìèçàöèè èìååò âèä
{ }f u u
u U
1 ( ) ( ) min� �
�
�� . (25)
Îíà ýêâèâàëåíòíà ñëåäóþùåé çàäà÷å:
f u
u X
u U
1
1
( ) min ,
( , ) .
,
� �
� �
� �
�
� �
� �
P{ }�
(26)
Çàäà÷à (26) ñ ôèêñèðîâàííûì ïàðàìåòðîì �, íàïðèìåð � 0 , è �( , )u x
èç (24) èìååò ñàìîñòîÿòåëüíîå çíà÷åíèå è íàçûâàåòñÿ çàäà÷åé äâóõýòàïíîãî
ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ âåðîÿòíîñòíûì îãðàíè÷åíèåì (íà ñëó-
÷àéíûå çíà÷åíèÿ öåëåâîé ôóíêöèè âòîðîãî ýòàïà).
Ëåììà 3. Çàäà÷è (25) è (26) ýêâèâàëåíòíû.
Äîêàçàòåëüñòâî. Ïóñòü �u — äîïóñòèìîå ðåøåíèå çàäà÷è (25), òîãäà
� �� �� ( )u êîíå÷íî.  ñèëó ñâîéñòâ êâàíòèëè
P{ } P{ }� �( , ) ( , ) ( )� � � � � � �u X u X u� � �� .
Òàêèì îáðàçîì, ( , )� �� u — äîïóñòèìîå ðåøåíèå çàäà÷è (26) ñ òåì æå ñàìûì
çíà÷åíèåì f u u1 ( ) ( )� � ��� öåëåâîé ôóíêöèè.
Îáðàòíî, ïóñòü ( , )� �� u — äîïóñòèìîå ðåøåíèå çàäà÷è (26), ò.å. � �u U ,
P{ }�( , )� � � � �u X � � 0 è ��
� � �
��f u1 ( ) � .  ñèëó íåïðåðûâíîñòè âåðîÿò-
íîñòíîé ìåðû lim ( , )
�
�
���
� � P{ }� u X 0. Ïîýòîìó ��
� � �� �� ( )u è, ñëåäîâà-
òåëüíî, äëÿ çíà÷åíèé öåëåâûõ ôóíêöèé çàäà÷ (26), (25) èìååì íåðàâåíñòâî
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
� � � � � � � � � ��f f u f u u1 1( ) ( ) ( )� �� , ò.å. �u — äîïóñòèìîå ðåøåíèå äëÿ çàäà-
÷è (25). Òàêèì îáðàçîì, â ñèëó ëåììû 1 çàäà÷è (25) è (26) ýêâèâàëåíòíû. Ëåììà
äîêàçàíà.
Ðàññìîòðèì ñëåäóþùóþ çàäà÷ó:
f u
p I f
u U V x V x
k
k
K
K K
1
1
1
1 1
( ) min ,
, , ( ), , ( )
� �
� � � �
�
�
� � �� �
{ 2 2 0( , , ) , ( , , ) ,u x Q u xk k k k� � � �� � �}
(27)
ãäå I{ }� — èíäèêàòîð óñëîâèé â ôèãóðíûõ ñêîáêàõ, ðàâíûé åäèíèöå, åñëè âñå
óñëîâèÿ â ñêîáêàõ âûïîëíåíû, è ðàâíûé íóëþ â ïðîòèâíîì ñëó÷àå.
Ïðåäïîëîæåíèå 3 (î ñóùåñòâîâàíèè ðåøåíèÿ çàäà÷è âòîðîãî ýòàïà). Åñëè
ìíîæåñòâî W u x V x Q u x( , ) ( ) : ( , , ) � �{ }� �2 0 íå ïóñòî, òî inf â (24) äîñòèãàåòñÿ
è, òàêèì îáðàçîì, ñóùåñòâóåò �( , ) ( , )u x W u x� òàêîå, ÷òî �( , ) ( , ( , ), )u x f u u x x 2 � .
Ýòî ïðåäïîëîæåíèå âûïîëíåíî, íàïðèìåð, åñëè äëÿ ëþáûõ u U x X� �, ( )�
ôóíêöèÿ Q u x2 ( , , )� ïîëóíåïðåðûâíà ñíèçó ïî � íà êîìïàêòíîì ìíîæåñòâåV x( ) .
Ëåììà 4. Ïðè ïðåäïîëîæåíèÿõ 1, 3 çàäà÷è (26) è (27) ýêâèâàëåíòíû.
Äîêàçàòåëüñòâî. Ïóñòü ( , )� �� u — äîïóñòèìîå ðåøåíèå çàäà÷è (26), ò.å.
� �u U , P{ }�( , )� � � �u X � � , ãäå ôóíêöèÿ �( , )u x îïðåäåëåíà â (24). Îáîçíà÷èì
�I � ìíîæåñòâî èíäåêñîâ k òàêèõ, ÷òî �( , )� � �u xk � . Î÷åâèäíî, ÷òî pkk I�� �
�
�
'
.
Äëÿ k I� �� ìíîæåñòâî W u x
k
( , )� íå ïóñòî è â ñèëó ïðåäïîëîæåíèÿ 3 ñóùåñòâóþò
� �� k kV x( ) òàêèå, ÷òî f u x u xk k k2 ( , , ) ( , )� � � � �� �� è Q u xk k2 0( , , )� � �� . Äëÿ
k I! �� âûáåðåì ïðîèçâîëüíûå � �� k kV x( ). Íàáîð ( , , , , )� � � �� � �u K1 � äîïóñòèì äëÿ
çàäà÷è (27) ñ òåì æå çíà÷åíèåì � � � �f f u1 ( ) � öåëåâîé ôóíêöèè.
Îáðàòíî, ïóñòü íàáîð ( , , )� � �� �u k
K{ }
1
ÿâëÿåòñÿ äîïóñòèìûì äëÿ çàäà÷è (27).
Ïîêàæåì, ÷òî ( , )� �� u — äîïóñòèìîå ðåøåíèå äëÿ çàäà÷è (26). Îáîçíà÷èì ñ ïî-
ìîùüþ �I � ìíîæåñòâî èíäåêñîâ k òàêèõ, ÷òî � �� k kV x( ), f u xk k2 ( , , )� � � �� � è
Q u xk k2 0( , , )� � �� . Î÷åâèäíî, ÷òî p
kk I�� �
�
�
'
. Äëÿ k I� �� âûïîëíåíî �( , )� �u xk
� � � � �f u xk k2
( , , )� � , ïîýòîìó P{ }�( , )� � � � ���u X pkk I
� �
�
'
, è, òàêèì îáðà-
çîì, ( , , )� � �f u� — äîïóñòèìîå ðåøåíèå äëÿ çàäà÷è (26) ñ òåì æå ñàìûì çíà÷åíè-
åì � � � �f f u1 ( ) � öåëåâîé ôóíêöèè. Ñëåäîâàòåëüíî, ñîãëàñíî ëåììå 1 çàäà÷è
(26) è (27) ýêâèâàëåíòíû. Ëåììà äîêàçàíà.
 ñèëó òðàíçèòèâíîñòè îòíîøåíèÿ ýêâèâàëåíòíîñòè çàäà÷è (25)–(27) ýêâèâà-
ëåíòíû ïðè ïðåäïîëîæåíèÿõ 1, 3. Çàäà÷à (27) — òîãî æå òèïà, ÷òî è (5), äëÿ êîòî-
ðîé âîçìîæíîñòü ñâåäåíèÿ ê ÷àñòè÷íî öåëî÷èñëåííîìó ýêâèâàëåíòó (15) ïðè
ïðåäïîëîæåíèÿõ 2 äîêàçàíà â òåîðåìå 1. Ñäåëàåì äîïîëíèòåëüíûå ïðåäïîëîæå-
íèÿ îòíîñèòåëüíî çàäà÷è (25) è, ñëåäîâàòåëüíî, (27).
Ïðåäïîëîæåíèå 4. Èçâåñòíû ôóíêöèè � �1 ( , , )u x è � �2 ( , , )u x òàêèå, ÷òî äëÿ
ëþáûõ u U� , x X� ( )� , ��V x( ) âûïîëíåíû ñëåäóþùèå óñëîâèÿ:
4.1. ��
�
� �
� � � �
�
1 2 2( , , ) inf inf ( , , ) : ( , ,
( ) ( )
u x f u x Q u x
x V xX
{
�
) � 0};
4.2. ��
� �
�
�
�
�
� �
� � �
�
2 20( , , ) max , inf inf ( , , )
( ) ( )
u x Q u x
x V xX � �
.
Íåñêîëüêî áîëåå ñëàáûì ÿâëÿåòñÿ ñëåäóþùåå ïðåäïîëîæåíèå, îäíàêî ïðåä-
ïîëàãàþùåå ñóùåñòâîâàíèå ðåøåíèÿ ó çàäà÷è (25).
Ïðåäïîëîæåíèå 4' . Óñëîâèÿ 4.1, 4.2 âûïîëíåíû íå äëÿ âñåõ u U� , à òîëüêî
äëÿ íåêîòîðîãî îïòèìàëüíîãî ðåøåíèÿ u� çàäà÷è (25) è âñåõ x X� ( )� , ��V x( ) .
Îáîçíà÷èì w wK1� �� íàáîð áóëåâûõ ïåðåìåííûõ. Ðàññìîòðèì ñëåäóþùóþ
çàäà÷ó ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 43
f u
p w
u U w w
k k
k
K
K K
1
1
1
1 1
1
( ) min ,
,
, , ; , ,
� �
� �
� � � �
�
�
�
� � �� � �
f u x f u x u x w kk k k k k k k2 2 1 1 2( , , ) ( ( , , ) ( , , )) , , , ,� � � � �� � � � K
Q u x Q u x u x w kk k k k k k k
,
( , , ) ( ( , , ) ( , , )) , , , ,2 2 2 1 2� � � �� � � K
V x w k Kk k k
,
( ), , , , , , .� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
{ }0 1 1 2 �
(28)
Îñíîâíîé ðåçóëüòàò ñòàòüè ïðåäñòàâëÿåò ñëåäóþùàÿ òåîðåìà î âîçìîæíîñòè ñâå-
äåíèÿ çàäà÷è äâóõýòàïíîé êâàíòèëüíîé îïòèìèçàöèè (25) ñ äèñêðåòíûì ðàñïðåäåëå-
íèåì ñëó÷àéíûõ äàííûõ ê çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ (28).
Òåîðåìà 2. Ïðè óñëîâèÿõ 1, 3, 4 çàäà÷è (25)–(28) ýêâèâàëåíòíû â ñìûñëå
îïðåäåëåíèÿ 3. Åñëè ðåøåíèå çàäà÷è (25) ñóùåñòâóåò è âûïîëíåíû ïðåäïîëîæå-
íèÿ 1, 2, 4' , òî çàäà÷è (25)–(28) òàêæå ýêâèâàëåíòíû. Îòñþäà ñëåäóåò, ÷òî åñëè
( , , , , ..., )� � �
� � � � � �� �u w wK K1 1� — îïòèìàëüíîå ðåøåíèå çàäà÷è (28), òî u� —
îïòèìàëüíîå ðåøåíèå çàäà÷è (25), ( , )�
� �u — îïòèìàëüíîå ðåøåíèå çàäà÷è (26),
à ( , , )� � �
� � � �� �u K1 � — îïòèìàëüíîå ðåøåíèå çàäà÷è (27).
Äîêàçàòåëüñòâî. Ýêâèâàëåíòíîñòü çàäà÷ (25)–(27) äîêàçàíà â ëåììàõ 3, 4.
Äîêàæåì ýêâèâàëåíòíîñòü çàäà÷ (27) è (28) ñ ïîìîùüþ ëåììû 1.
 ïðåäïîëîæåíèÿõ 1, 3, 4 äîêàæåì ïåðâîå óòâåðæäåíèå òåîðåìû. Ïóñòü
( , , )� � � � � �� � �u K1 � — äîïóñòèìîå ðåøåíèå çàäà÷è (27) ñî çíà÷åíèåì öåëåâîé
ôóíêöèè f u1 ( )� � �� . Îïðåäåëèì çíà÷åíèÿ áóëåâûõ ïåðåìåííûõ
�
� � � � � � � ��
�
�
w
f u x Q u x
k
k k k k0 0 0
1
2 2, ( , , ) , ( , , ) ,� � �
Ïîêàæåì, ÷òî ( , , , )� � � � � � � � � �� � �u w wK K1 1� � — äîïóñòèìîå ðåøåíèå çàäà-
÷è (28). Îáîçíà÷èì �I 0 è �I1 ìíîæåñòâà èíäåêñîâ k òàêèõ, ÷òî � wk 0 è � wk 1
ñîîòâåòñòâåííî. Òîãäà èç îãðàíè÷åíèÿ-íåðàâåíñòâà (27) ñëåäóåò
p w p w pk
k
K
k k
k
K
k k
k I �
� � �� � � � �
1 1
1 1 1
0
( )
'
� � � � � � � � � � �
�1 0 0 1
1
2 2p I f u x Q u xk
k
K
k k k k{ }( , , ) , ( , , )� � � � .
Òàêèì îáðàçîì, îãðàíè÷åíèå p wk kk
K � � � � 1
1 � â (28) âûïîëíåíî. Ïðîâåðèì
äâå ñëåäóþùèå ãðóïïû îãðàíè÷åíèé â (28). Äëÿ k I� �0 äàííûå îãðàíè÷åíèÿ
ïðèíèìàþò âèä f u xk k2 0( , , )� � � � �� � , Q u xk k2 0( , , )� � �� è âûïîëíåíû â ñèëó
îïðåäåëåíèÿ ìíîæåñòâà èíäåêñîâ �I 0 . Äëÿ k I� �1 ýòè îãðàíè÷åíèÿ ïðèíèìàþò
âèä � � �1 0( , , )� � � � �u xk k , � � �2 0( , , )� � � � �u xk k . Ïðîâåðèì èõ âûïîëíåíèå.
 ñèëó ïðåäïîëîæåíèÿ äîïóñòèìîñòè ( , , , ... )� � � �� � �u K1 èç (27) ñëåäóåò, ÷òî
� ��I 0 è ñóùåñòâóþò x V xk k k' ', ( )'� �� òàêèå, ÷òî f u xk k2 0( , , )� � � � �� �' ' ,
Q u xk k2 0( , , )'� � �� ' .  ñèëó ïðåäïîëîæåíèÿ 4.1 äëÿ k I� �1 èìååò ìåñòî
� � �
�
1 2 2( , , ) inf inf ( , , ) : ( ,
( ) ( )
� � � � �
� �
u x f u x Q uk k
x V xX
{
�
�, )x � �0}
� � � � �f u xk k2 ( , , )'� �'
è, çíà÷èò, ñïðàâåäëèâî íåðàâåíñòâî � � �1 0( , , )� � � � �u xk k .  ñèëó ïðåäïîëîæå-
íèÿ 4.2 âûïîëíåíî èëè � �2 0( , , )� � �u xk k (÷òî è òðåáóåòñÿ), èëè
� � �
�
2 2 2( , , ) inf inf ( , , ) ( ,
( ) ( )
� � � � � � �
� �
u x Q u x Q uk k
x V xX �
� k kx' , )' � 0 .
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
â ïðîòèâíîì ñëó÷àå.
Òàêèì îáðàçîì, âòîðîå íåðàâåíñòâî � �2 0( , , )� � �u xk k òàêæå âûïîëíåíî. Ñëåäî-
âàòåëüíî, ( , , , ..., , , ..., )� � � � � �� � �u w wK K1 1 — äîïóñòèìîå ðåøåíèå çàäà÷è (28) ñ òåì
æå ñàìûì çíà÷åíèåì f u1 ( )� � �� öåëåâîé ôóíêöèè.
Ïóñòü ( , , , ..., , , ..., )� � � � � �� � �u w wK K1 1 — äîïóñòèìîå ðåøåíèå çàäà÷è (28) ñî
çíà÷åíèåì öåëåâîé ôóíêöèè f u1 ( )� � �� . Ïðîâåðèì, ÷òî ( , , , ..., )� � � �� � �u K1 — äî-
ïóñòèìîå ðåøåíèå çàäà÷è (27). Îáîçíà÷èì �I 0 ìíîæåñòâî èíäåêñîâ k òàêèõ, ÷òî
� wk 0. Â ñèëó äîïóñòèìîñòè èìååò ìåñòî p wk kk
K � � � � 1
1 � , ÷òî ýêâèâàëåíòíî
íåðàâåíñòâó pkk I�� �
0
' � . Ïðè k I� �0 âûïîëíåíî � wk 0 , ïîýòîìó èç îãðàíè÷å-
íèé (28) ñëåäóåò f u xk k2 0( , , )� � � � �� � , Q u xk k2
0( , , )� � �� . Ïðîâåðèì âûïîëíåíèå
âåðîÿòíîñòíîãî îãðàíè÷åíèÿ â (27):
p I f u x Q u xk
k
K
k k k k
� � � � � � � � � �
1
2 20 0{ }( , , ) , ( , , )� � �
� � � � � � � � �
�
� p I f u x Q u x pk
k I
k k k k k
k0
2 20 0
'
{ }( , , ) , ( , , )� � �
�
� �
I 0
'
� .
Òàêèì îáðàçîì, ( , , , ..., )� � � �� � �u K1 — äîïóñòèìîå ðåøåíèå çàäà÷è (27) ñ òåì æå
ñàìûì çíà÷åíèåì f u1 ( )� � �� öåëåâîé ôóíêöèè. Cïðàâåäëèâîñòü ïåðâîãî óòâåð-
æäåíèÿ òåîðåìû ñëåäóåò èç ëåììû 1. Âòîðîå óòâåðæäåíèå òåîðåìû äîêàçûâà-
åòñÿ àíàëîãè÷íî, íî íà îñíîâå ëåììû 2.
Òåîðåìà äîêàçàíà.
Ïðåäïîëîæåíèÿ 4 äîïóñêàþò íåêîòîðûé ïðîèçâîë â âûáîðå ôóíêöèé
� �1 2( ), ( )� � . Âûáåðåì èõ òàê, ÷òîáû óïðîñòèòü çàäà÷ó (28).
Ïðåäïîëîæåíèÿ 5 (îá îáëàñòè èçìåíåíèÿ ôóíêöèé çàäà÷è). Ïóñòü ñóùåñò-
âóþò (èçâåñòíû) êîíñòàíòà � è ôóíêöèè M x2 ( ) è N x2 ( ) òàêèå, ÷òî âûïîëíÿþòñÿ
ñëåäóþùèå óñëîâèÿ:
5.1. inf ( , , ) : ( , , )
, ( ), ( )u U x X V x
f u x Q u x
� � �
� � � ��
� �
� � �{ }2 2 0 ;
5.2. sup ( , , ) ( )
, ( )u U V x
f u x M x
� �
�
�
�
�2 2 , sup ( , , ) ( )
, ( )u U V x
Q u x N x
� �
�
�
�
�2 2 .
Ôóíêöèè M x2 ( ) , N x2 ( ) è ÷èñëî � çàâåäîìî ñóùåñòâóþò, åñëè ôóíêöèè
f u x2 ( , , )� , Q u x2 ( , , )� íåïðåðûâíû ïî ( , ) ( )u U V x� � � ïðè êàæäîì x�X( )�
è ìíîæåñòâà U V x, ( ) êîìïàêòíû, à ìíîæåñòâî X( )� êîíå÷íî.
Âûáåðåì ôóíêöèè
� � � � � � �1 2 2 2 2 2( , , ) ( , , ) ( ) , ( , , ) ( , , )u x f u x M x u x Q u x N � � � ( )x .
Îíè óäîâëåòâîðÿþò ïðåäïîëîæåíèÿì 4. Äåéñòâèòåëüíî, äëÿ ëþáîãî u U� â ñè-
ëó óñëîâèé 5.1, 5.2 âûïîëíåíî
� � � � �1 2 2( , , ) ( , , ) ( )u x f u x M x � � � �
� �
� � �
inf ( , , ) : ( , , )
, ( ), ( )u U x V x
f u x Q u x
X
{ }
� �
� �2 2 0 ,
� � �2 2 2 2 0( , , ) ( , , ) ( )u x Q u x N x � � .
Ïîäñòàâëÿÿ ñîîòíîøåíèÿ � � � �1 2 2( , , ) ( , , ) ( )u x f u x M x � � , � �2 ( , , )u x
�Q u x N x2 2( , , ) ( )� â (28), ïðèõîäèì ê ñëåäóþùåé ëèíåéíîé ïî áóëåâûì ïå-
ðåìåííûì ýêâèâàëåíòíîé (ïðè ïðåäïîëîæåíèÿõ 5) çàäà÷å ñìåøàííîãî öåëî-
÷èñëåííîãî ïðîãðàììèðîâàíèÿ [16]
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 45
�
�
�
�
�
�
�
�
�
�
�
f u
p w
u U w w
k k
k
K
K K
1
1
1
1 1
1
( ) min ,
, ; ; ,...,
� �
� �
� � � �
�
�
� � �� �
�
� � �
�
,
( , , ) ( ( ) ) , , , , ,
( , , )
f u x M x w k K
Q u x
k k k k
k k
2
2
1 2� � �
�
�
N x w k K
V x w k K
k k
k k k
( ) , , , , ,
( ), , , , , , .
� �
1 2
0 1 1 2
�
�� { }
(29)
Îòìåòèì, ÷òî åñëè ôóíêöèè f u x2 ( , , )� , Q u x2 ( , , )� êóñî÷íî-ëèíåéíû ïî
( , )u � , íàïðèìåð, ÿâëÿþòñÿ ôóíêöèÿìè ìàêñèìóìà èç ëèíåéíûõ ïî ( , )u � ôóíê-
öèé, à ìíîæåñòâà U , V x( ) çàäàþòñÿ ëèíåéíûìè îãðàíè÷åíèÿìè, òî çàäà÷à (29)
ñâîäèòñÿ ê çàäà÷å ëèíåéíîãî ÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ.
Çàìå÷àíèå 6. Ðàññìîòðèì çàäà÷ó (26) ñ ôèêñèðîâàííûì �, íàïðèìåð � " 0
(êîòîðàÿ â ýòîì ñëó÷àå íàçûâàåòñÿ çàäà÷åé äâóõýòàïíîãî ñòîõàñòè÷åñêîãî ïðî-
ãðàììèðîâàíèÿ ñ âåðîÿòíîñòíûì îãðàíè÷åíèåì), à òàêæå çàäà÷è (27)–(29) ñ òåì
æå ñàìûì ôèêñèðîâàííûì �. Ïðè ýòîì ëåììà 4 è òåîðåìà 2 îñòàþòñÿ ñïðàâåäëè-
âûìè. Òàêèì îáðàçîì, çàäà÷à äâóõýòàïíîãî ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ
ñ âåðîÿòíîñòíûì îãðàíè÷åíèåì (26) ñ � " 0 ïðè äèñêðåòíîì ðàñïðåäåëåíèè ñëó-
÷àéíûõ äàííûõ ýêâèâàëåíòíî ñâîäèòñÿ ê çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ïðî-
ãðàììèðîâàíèÿ (29) ñ � " 0 .
×ÈÑËÅÍÍÛÉ ÝÊÑÏÅÐÈÌÅÍÒ
 ðàáîòå [26] ðàññìîòðåí ÷èñëåííûé ïðèìåð äâóõýòàïíîé ëèíåéíîé çàäà÷è
êâàíòèëüíîé îïòèìèçàöèè âèäà (25), ãäå íà ïåðâîì ýòàïå ðåøàåòñÿ çàäà÷à
c u u
u U1
T � �
�
�� ( ) min , U u A u b u � �{ : , }1 1 0 ,
à çàäà÷à âòîðîãî ýòàïà èìååò âèä
�( , ) min , ( , ) : ,
( , )
u x c Y u x B x A u
y Y u x
� � �
� 2 2 20T { }� � � � .
Ïàðàìåòðû çàäà÷ èìåþò ñëåäóþùèå ÷èñëîâûå çíà÷åíèÿ: � 0 5. ,
c c B1 2 2
3
1
01
0 36
0 875 1 8
1 1
#
$
%%
&
'
((
#
$
%%
&
'
((
�
�
#
$
,
.
.
,
. .
%%
&
'
((
#
$
%%
&
'
((
�
�
#
$
%%
&
'
((,
. .
. .
, ,A A b2 1
11 1 7
28 2 4
1 0
0 1
1
10
10
�
�
#
$
%%
&
'
((.
Ñëó÷àéíûé âåêòîð X (ïðàâûõ ÷àñòåé) çàäàí ðÿäîì ðàñïðåäåëåíèÿ â âèäå
Ïðèáëèæåííîå ðåøåíèå � � �u u u( , )1 2 , íàéäåííîå àëãîðèòìîì, ïðåäëîæåííûì
â [26], èìååò âèä
Ðåøèì ýòó çàäà÷ó ïóòåì ñâåäåíèÿ ê çàäà÷å ÷àñòè÷íî öåëî÷èñëåííîãî ëèíåéíî-
ãî ïðîãðàììèðîâàíèÿ âèäà (29):
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
xk
2 5
4
.#
$
%%
&
'
((
1 5
21
.
.
#
$
%%
&
'
((
2 3
3
.#
$
%%
&
'
((
3 2
1
.#
$
%%
&
'
((
7
4
#
$
%%
&
'
((
3
4
#
$
%%
&
'
((
2
5
#
$
%%
&
'
((
8
9
#
$
%%
&
'
((
pk 0.05 0.10 0.10 0.25 0.15 0.15 0.15 0.05
�u1 �u2 �� ( )�u c u u
1
T � � ��� ( )
0 1.56 0.1 1.67
c u
u u U V w wK
1
0 0 0 11 2 1 1
T
{ }
� �
� � � � � � � �
�
� � � �
min
, ; ; ; , ,...,� K
p w A u b
c M x w
k k
k
K
k k k
�
� � �
� � �
�
{ }
T
0 1
1
1 1
2 2
1
,
,
, ,
( ( ) ) ,
�
� � � k K
A u B x N x w i ki i k ki k k
� � � �
1 2
1 2 122 2 2
, , ..., ,
( ) , , , , , .� .., ,K
ãäå A Bi i2 2, — i-å ñòðîêè ìàòðèö A B2 2, ; x x ik ki { }, ,1 2 ; � 0; U V 100 ;
M x M V c ck2 21 22 46( ) ( )" � ;
N x N U A V Bk
i
ij
j
ij
j
2
1 2
2
1 2
2
1 2
( ) max | ( ) | | ( ) | m
, , ,
" � �
� � ax | | .
, ...,k K
kix
#
$
%
%
&
'
(
(
1
303 5.
Äàííàÿ çàäà÷à ñîäåðæèò 11 íåïðåðûâíûõ ïåðåìåííûõ, âîñåìü áóëåâûõ ïåðå-
ìåííûõ, îäíî áóëåâî îãðàíè÷åíèå-íåðàâåíñòâî, äâà íåïðåðûâíûõ îãðàíè÷å-
íèé-íåðàâåíñòâ, 24 ñìåøàííûõ îãðàíè÷åíèé-íåðàâåíñòâ. Òî÷íîå ðåøåíèå ýòîé
çàäà÷è u u u* * *( , ) 1 2 ïîëó÷åíî ñ ïîìîùüþ ïðîãðàììû IBM ILOG CPLEX V12.1
[27] (ñ ïàðàìåòðàìè ïî óìîë÷àíèþ íà ïåðñîíàëüíîì êîìïüþòåðå AMD Athlon 64
3200+, 200MHz Bus Frequency, 1.50 GB DDR1 RAM) çà 0.05 ñåêóíäû:
u1 0� , u2 1 5331� . , �
� 0 1188. , c u
1
1 6518T � �� � . .
Î÷åâèäíî, ÷òî íàéäåííîå îïòèìàëüíîå ðåøåíèå u� ëó÷øå, ÷åì ïðèáëèæåííîå
ðåøåíèå �u .
ÇÀÊËÞ×ÅÍÈÅ
Ôóíêöèè êâàíòèëè ìîæíî èñïîëüçîâàòü âìåñòî ôóíêöèé ñðåäíåãî çíà÷åíèÿ
â çàäà÷àõ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. Îíè îïèñûâàþò ôóíêöèîíèðîâà-
íèå ñòîõàñòè÷åñêîé ñèñòåìû â ýêñòðåìàëüíûõ óñëîâèÿõ. Ýòîò ïîäõîä ïîïóëÿðåí
â ñîâðåìåííîé ôèíàíñîâîé îïòèìèçàöèè. Îäíàêî ôóíêöèè êâàíòèëè, êàê ïðàâè-
ëî, íå âûïóêëû. Ïîýòîìó äëÿ ðåøåíèÿ çàäà÷ êâàíòèëüíîé îïòèìèçàöèè ïðèìå-
íÿþò ëèáî ýâðèñòè÷åñêèå ïðèáëèæåííûå ìåòîäû, ëèáî ìåòîäû ãëîáàëüíîé
îïòèìèçàöèè. Êðîìå òîãî, çàäà÷è êâàíòèëüíîé îïòèìèçàöèè ñ äèñêðåòíûì ðàñ-
ïðåäåëåíèåì ñëó÷àéíûõ äàííûõ ìîæíî ñâåñòè ê äåòåðìèíèðîâàííûì çàäà÷àì
÷àñòè÷íî öåëî÷èñëåííîãî ïðîãðàììèðîâàíèÿ. Ïðè ýòîì ÷èñëî äîïîëíèòåëüíûõ
áóëåâûõ ïåðåìåííûõ ðàâíî ÷èñëó âîçìîæíûõ çíà÷åíèé âåêòîðà ñëó÷àéíûõ ïà-
ðàìåòðîâ èñõîäíîé çàäà÷è. Àíàëîãè÷íîå ïðåîáðàçîâàíèå âîçìîæíî è äëÿ äâóõ-
ýòàïíûõ çàäà÷ ñ âåðîÿòíîñòíûì îãðàíè÷åíèåì íà öåëåâóþ ôóíêöèþ âòîðîãî
ýòàïà. Ïîëó÷åííûå ñìåøàííûå çàäà÷è ïðåäïîëàãàåòñÿ ðåøàòü ñòàíäàðòíûìè
ïðîãðàììíûìè ñðåäñòâàìè äèñêðåòíîé îïòèìèçàöèè. Ðåçóëüòàòû ïðîèëëþñòðè-
ðîâàíû ÷èñëåííûì ïðèìåðîì íåáîëüøîé ðàçìåðíîñòè. Òàêèì îáðàçîì, îáîñíî-
âàí ïðàêòè÷åñêèé ìåòîä ðåøåíèÿ ðåàëüíûõ çàäà÷ êâàíòèëüíîãî äâóõýòàïíîãî
ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. Äàëüíåéøèå èññëåäîâàíèÿ áóäóò íàïðàâëå-
íû íà ðàçðàáîòêó ñïåöèàëüíûõ ìåòîäîâ äèñêðåòíîé îïòèìèçàöèè, ó÷èòûâàþùèõ
ñòðóêòóðó âîçíèêàþùèõ ÷àñòè÷íî öåëî÷èñëåííûõ çàäà÷.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. D a n t z i g G . B . , T h a p a M . N . Linear programming 2: Theory and extensions. — New York:
Springer, 2003. — 2. — 448 p.
2. E r m o l i e v Y . , W e t s R . (Eds) Numerical techniques for stochastic optimization. — Berlin:
Springer, 1988. — 571 p.
3. B i r g e J . , L u v e a u x F . Introduction to stochastic programming. — New York: Springer, 1997.
— 421 p.
4. S h a p i r o A . , D e n t c h e v a D . , R u s z c z y n s k i A . Lectures on stochastic programming:
Modeling and theory. — Philadelphia: SIAM, 2009. — 442 p.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 47
5. Å ð ì î ë ü å â Þ . Ì . Ìåòîäû ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. — Ì.: Íàóêà, 1976. — 240 ñ.
6. Þ ä è í Ä . Á . Çàäà÷è è ìåòîäû ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ. — Ì.: Ñîâ. ðàäèî, 1979.
— 392 c.
7. Ì à ë û ø å â  .  . , Ê è á ç ó í À . È . Àíàëèç è ñèíòåç âûñîêîòî÷íîãî óïðàâëåíèÿ ëåòàòåëü-
íûìè àïïàðàòàìè. — Ì.: Ìàøèíîñòðîåíèå, 1987. — 304 c.
8. K i b z u n A . I . , K a n Y . S . Stochastic programming problems with probability and quantile
functions. — Chichester; New York; Brisbane et etc.: John Wiley & Sons, 1996. — 301 p.
9. Ê è á ç ó í À . È . , Ê à í Þ . Ñ . Çàäà÷è ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ âåðîÿòíîñòíûìè
êðèòåðèÿìè. — Ì.: Ôèçìàòëèò, 2009. — 372 c.
10. Ê è á ç ó í À . È . , Í à ó ì î â À .  . Ãàðàíòèðóþùèé àëãîðèòì ðåøåíèÿ çàäà÷è êâàíòèëüíîé
îïòèìèçàöèè // Êîñìè÷. èññëåä. — 1995. — 33, ¹ 2. — Ñ. 160–165.
11. L a r s e n N . , M a u s s e r H . , U r y a s e v S . Algorithms for optimization of value-at-risk //
Financial Engineering, e-Commerce and Supply Chain / P. Pardalos and V.K. Tsitsiringos (Eds). —
Dordreht: Kluwer Acad. Publ., 2002. — P. 129–157.
12. W o z a b a l D . , H o c h r e i t e r R . , P f l u g G . C h . A D.C. formulation of value-at-risk
constrained optimization // Optimization. — 2010. — 59, N 3. — P. 377–400.
13. N o r k i n V . On mixed integer reformulations of monotonic probabilistic programming problems
with discrete distributions — (Preprint, 2010). — http://www.optimization-online.org.
14. È â à í î â Ñ . Â . , Í à ó ì î â À . Â . Àëãîðèòì îïòèìèçàöèè êâàíòèëüíîãî êðèòåðèÿ äëÿ ïîëè-
ýäðàëüíîé ôóíêöèè ïîòåðü è äèñêðåòíîãî ðàñïðåäåëåíèÿ ñëó÷àéíûõ ïàðàìåòðîâ // Àâòîìà-
òèêà è òåëåìåõàíèêà. — 2012. — ¹ 1. — Ñ. 95–108.
15. Ê è á ç ó í À . È . , Í à ó ì î â À .  . , Í î ð ê è í  . È . Î ñâåäåíèè çàäà÷è êâàíòèëüíîé îïòè-
ìèçàöèè ñ äèñêðåòíûì ðàñïðåäåëåíèåì ê çàäà÷å ñìåøàííîãî öåëî÷èñëåííîãî ïðîãðàììèðîâà-
íèÿ // Òàì æå. — 2013. — ¹ 6. — Ñ. 66–86.
16. Ê è á ç ó í À . È . , Í à ó ì î â À . Â . , Í î ð ê è í Â . È . Ñâåäåíèå çàäà÷ äâóõýòàïíîé âåðîÿòíîñòíîé
îïòèìèçàöèè ñ äèñêðåòíûì ðàñïðåäåëåíèåì ñëó÷àéíûõ äàííûõ ê çàäà÷àì ÷àñòè÷íî öåëî÷èñëåííîãî
ïðîãðàììèðîâàíèÿ // Ñòîõàñòè÷åñêîå ïðîãðàììèðîâàíèå è åãî ïðèëîæåíèÿ / Ðåä. Ï.Ñ. Êíîïîâ, Â.È. Çîð-
êàëüöåâ. — Èðêóòñê: Èí-ò ñèñòåì ýíåðãåòèêè èì. Ë.À. Ìåëåíòüåâà ÑÎ ÐÀÍ, 2012. — C. 76–103.
17. Ê î ð á ó ò À . À . , Ô è í ê å ë ü ø ò å é í Þ . Þ . Äèñêðåòíîå ïðîãðàììèðîâàíèå. — Ì.: Íàóêà,
1969. — 368 c.
18. S e n S . Relaxation for probabilistically constrained programs with discrete random variables //
Oper. Res. Letters. — 1992. — 11. — P. 81–86.
19. R u s z c z y n s k i A . Probabilistic programming with discrete distributions and precedence
constrained knapsack polyhedra // Math. Program. — 2002. — 93. — P. 195–215.
20. B e n a t i S . , R i z z i R . A mixed integer linear programming formulation of the optimal
mean/Value-at-Risk portfolio problem // Eur. J. Oper. Res. — 2007. — 176. — P. 423–434.
21. L u e d t k e J . , A h m e d S . , N e m h a u s e r G . An integer programming approach for linear
programs with probabilistic constraints // Math. Program. — 2010. — 122, N 2. — P. 247–272.
22. Í î ð ê è í Â . È . , Á î é ê î Ñ . Â . Îïòèìèçàöèÿ ôèíàíñîâîãî ïîðòôåëÿ íà îñíîâå ïðèíöèïà
áåçîïàñíîñòè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2012. — ¹ 2. — Ñ. 29–41.
23. Á î ã ä à í î â À . Á . , Í à ó ì î â À .  . Èññëåäîâàíèå äâóõýòàïíîé öåëî÷èñëåííîé çàäà÷è êâàí-
òèëüíîé îïòèìèçàöèè // Èçâ. ÐÀÍ. Òåîðèÿ è ñèñòåìû óïðàâëåíèÿ. — 2003. — ¹ 5. — Ñ. 62–69.
24. Á î ã ä à í î â À . Á . , Í à ó ì î â À .  . Ðåøåíèå äâóõýòàïíîé çàäà÷è ëîãèñòèêè â êâàíòèëüíîé
ïîñòàíîâêå // Àâòîìàòèêà è òåëåìåõàíèêà. — 2006. — ¹ 12. — Ñ. 36–42.
25. Í à ó ì î â À .  . Äâóõýòàïíàÿ çàäà÷à êâàíòèëüíîé îïòèìèçàöèè èíâåñòèöèîííîãî ïðîåêòà //
Èçâ. ÐÀÍ. Òåîðèÿ è ñèñòåìû óïðàâëåíèÿ. — 2010. — ¹ 2. — Ñ. 40–47.
26. Í à ó ì î â À .  . , Á î á û ë å â È . Ì . Î äâóõýòàïíîé çàäà÷å ñòîõàñòè÷åñêîãî ëèíåéíîãî ïðî-
ãðàììèðîâàíèÿ ñ êâàíòèëüíûì êðèòåðèåì è äèñêðåòíûì ðàñïðåäåëåíèåì ñëó÷àéíûõ ïàðàìåò-
ðîâ // Àâòîìàòèêà è òåëåìåõàíèêà. — 2012. — ¹ 2. — Ñ. 61–72.
27. I B M ILOG CPLEX V12.1. User’s Manual for CPLEX. — Intern. Business Machines Corporation,
2009. — 952 p.
28. Ð à é ê Ý . Êà÷åñòâåííûå èññëåäîâàíèÿ â çàäà÷àõ ñòîõàñòè÷åñêîãî íåëèíåéíîãî ïðîãðàììèðî-
âàíèÿ // Èçâ. ÀÍ ÝÑÑÐ. Ñåð. ôèç.-ìàò. — 1971. — 20, ¹ 1. — Ñ. 8–14.
29. P r e k o p a A . Stochastic programming. — Dordreht: Kluwer Acad. Publ., 1995. — 600 p.
30. Ð à é ê Ý . Î ôóíêöèè êâàíòèëÿ â ñòîõàñòè÷åñêîì íåëèíåéíîì ïðîãðàììèðîâàíèè // Èçâ. ÀÍ
ÝÑÑÐ. Ñåð. ôèç.-ìàò. — 1971. — 20, ¹ 2. — Ñ. 229–231.
31. Ð à é ê Ý . Î çàäà÷àõ ñòîõàñòè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ ðåøàþùèìè ôóíêöèÿìè // Òàì æå.
— 1972. — 21. — Ñ. 258–263.
32. Î á å í Æ - Ï . , Ý ê ë à í ä È . Ïðèêëàäíîé íåëèíåéíûé àíàëèç. — Ì.: Ìèð, 1988. — 510 c.
33. K a t a o k a S . A stochastic programming model // Econometrica. — 1963. — 31. — P. 181–196.
34. Ì è õ à ë å â è ÷ Â . Ñ . , Ã ó ï à ë À . Ì . , Í î ð ê è í Â . È . Ìåòîäû íåâûïóêëîé îïòèìèçàöèè.
— Ì.: Íàóêà, 1987. — 280 c.
35. P a g n o n c e l l i B . K . , A h m e d S . , S h a p i r o A . Sample average approximation method for
chance constrained programming: Theory and applications // J. Optim. Theory Appl. — 2009. —
142. — P. 399–416.
Ïîñòóïèëà 02.04.2013
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-124694 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-27T11:30:21Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Норкин, В.И. Кибзун, А.И. Наумов, А.В. 2017-10-02T18:29:12Z 2017-10-02T18:29:12Z 2014 Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования / В.И. Норкин, А.И. Кибзун, А.В. Наумов // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 34-48. — Бібліогр.: 35 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124694 519.856 Рассмотрены модели двухэтапного стохастического программирования с квантильным критерием и модели с вероятностным ограничением на случайные значения целевой функции второго этапа. Такие модели позволяют формализовать требования к надежности и безопасности оптимизируемой системы, а также оптимизировать ее функционирование в экстремальных условиях. Предложен способ эквивалентного преобразования моделей при дискретном распределении случайных параметров к задачам частично целочисленного программирования. Число дополнительных целочисленных (булевых) переменных в этой задаче равно числу возможных значений вектора случайных параметров. Полученные смешанные задачи решаются с помощью мощных стандартных компьютерных программ дискретной оптимизации. Приведены результаты численного эксперимента на задаче небольшой размерности. Розглянуто моделі двоетапного стохастичного програмування з квантильним критерієм, а також моделі з імовірнісним обмеженням на випадкові значення цільової функції другого етапу. Такі моделі дозволяють формалізувати вимоги до надійності і безпеки системи, що оптимізується, а також оптимізувати її функціонування в екстремальних умовах. Запропоновано спосіб еквівалентного перетворення моделей при дискретному розподілі випадкових параметрів до задач частково цілочисельного програмування. Число додаткових цілочисельних (булевих) змінних в цій задачі дорівнює числу можливих значень вектора випадкових параметрів. Отримані змішані задачі розв'язуються за допомогою потужних стандартних комп'ютерних програм дискретної оптимізації. Наведено результати чисельного експерименту на задачі невеликої вимірності. We consider a two-stage stochastic programming model with quantile criterion, as well as models with a probabilistic constraint on the random value of the objective function of the second stage. These models allow us to formalize the requirements for the reliability and safety of the system being optimized and to optimize the system performance under extreme conditions. We propose a method of equivalent transformation of these models under discrete distribution of random parameters to mixed-integer programming problems. The number of additional integer (Boolean) variables in these problems equals to the number of possible values of the vector of random parameters. The obtained mixed optimization problems can be solved by powerful standard discrete optimization software. To illustrate the approach, the results of numerical experiment for the problem of small dimension are presented. Работа выполнена при поддержке Государственного фонда фундаментальных исследований Украины в рамках совместного российско-украинского проекта Ф40.1/016 (2011-2012) и Российского фонда фундаментальных исследований (проекты 11-07-90407-Укр-ф-а, 11-07-00315-а), а также частично поддержана норвежско-украинским грантом CPEALA-2012/10052. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования Зведення задач двоетапної ймовірнісної оптимізації з дискретним розподілом випадкових даних до задач частково цілочисельного програмування Reducing two-stage probabilistic optimization problems with discrete distribution of random data to mixed-integer programming problems Article published earlier |
| spellingShingle | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования Норкин, В.И. Кибзун, А.И. Наумов, А.В. Системный анализ |
| title | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования |
| title_alt | Зведення задач двоетапної ймовірнісної оптимізації з дискретним розподілом випадкових даних до задач частково цілочисельного програмування Reducing two-stage probabilistic optimization problems with discrete distribution of random data to mixed-integer programming problems |
| title_full | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования |
| title_fullStr | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования |
| title_full_unstemmed | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования |
| title_short | Сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования |
| title_sort | сведение задач двухэтапной вероятностной оптимизации с дискретным распределением случайных данных к задачам частично целочисленного программирования |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/124694 |
| work_keys_str_mv | AT norkinvi svedeniezadačdvuhétapnoiveroâtnostnoioptimizaciisdiskretnymraspredeleniemslučainyhdannyhkzadačamčastičnoceločislennogoprogrammirovaniâ AT kibzunai svedeniezadačdvuhétapnoiveroâtnostnoioptimizaciisdiskretnymraspredeleniemslučainyhdannyhkzadačamčastičnoceločislennogoprogrammirovaniâ AT naumovav svedeniezadačdvuhétapnoiveroâtnostnoioptimizaciisdiskretnymraspredeleniemslučainyhdannyhkzadačamčastičnoceločislennogoprogrammirovaniâ AT norkinvi zvedennâzadačdvoetapnoíimovírnísnoíoptimízacíízdiskretnimrozpodílomvipadkovihdanihdozadaččastkovocíločiselʹnogoprogramuvannâ AT kibzunai zvedennâzadačdvoetapnoíimovírnísnoíoptimízacíízdiskretnimrozpodílomvipadkovihdanihdozadaččastkovocíločiselʹnogoprogramuvannâ AT naumovav zvedennâzadačdvoetapnoíimovírnísnoíoptimízacíízdiskretnimrozpodílomvipadkovihdanihdozadaččastkovocíločiselʹnogoprogramuvannâ AT norkinvi reducingtwostageprobabilisticoptimizationproblemswithdiscretedistributionofrandomdatatomixedintegerprogrammingproblems AT kibzunai reducingtwostageprobabilisticoptimizationproblemswithdiscretedistributionofrandomdatatomixedintegerprogrammingproblems AT naumovav reducingtwostageprobabilisticoptimizationproblemswithdiscretedistributionofrandomdatatomixedintegerprogrammingproblems |