îñóäàðñòâåííûé Óíèâåðñèòåò
Êàåäðà òåõíîëîãèè ïðîãðàììèðîâàíèÿ
Èñõàêîâ Àëåêñàíäð Àëåêñàíäðîâè÷
Âûïóñêíàÿ êâàëèèêàöèîííàÿ ðàáîòà áàêàëàâðà
Àëãîðèòìû íàõîæäåíèÿ îïòèìàëüíûõ
òðàåêòîðèé â öåëî÷èñëåííîé ìîäåëè Íåéìàíà
è èõ ðåàëèçàöèÿ íà ÿçûêå Ñ++
Íàïðàâëåíèå 010300
Ôóíäàìåíòàëüíàÿ èíîðìàòèêà è èíîðìàöèîííûå òåõíîëîãèè
Íàó÷íûé ðóêîâîäèòåëü:
àññèñòåíò
Ïàðåíîâ À. Ï.
Ñàíêò-Ïåòåðáóðã
2016
Ñîäåðæàíèå
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
. . . . . . . . . .
5
. . . . . . . . . . . . . . . . . . . . . . . . . . .
11
. . .
16
1.1. Ìåòîä êîíòèíóàëèçàöèè . . . . . . . . . . . . . . . . . . . . .
16
1.2. Ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ . . . . . . . . . . .
25
.
32
. . . . . . . . . . . . . . . . . . . .
32
2.2. Ñðàâíèòåëüíûé àíàëèç . . . . . . . . . . . . . . . . . . . . . .
34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
. . . . . . . . . . . . . . . . . . . . . . . . . .
46
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
Ââåäåíèå
Êëàññè÷åñêàÿ ìîäåëü Íåéìàíà â ëèòåðàòóðå
Ïîñòàíîâêà çàäà÷è
ëàâà 1. Ìåòîäû ðåøåíèÿ çàäà÷è îïòèìèçàöèè ìîäåëè
ëàâà 2. åàëèçàöèÿ ìåòîäîâ è èõ ñðàâíèòåëüíûé àíàëèç
2.1. Ïðîãðàììíàÿ ðåàëèçàöèÿ
Çàêëþ÷åíèå
Ñïèñîê ëèòåðàòóðû
Ïðèëîæåíèå
2
Ââåäåíèå
Ýêîíîìè÷åñêàÿ ìîäåëü, ïðåäñòàâëåííàÿ Äæîíîì îí Íåéìàíîì â îïóáëèêîâàííîé â 1937 ãîäó ñòàòüå1 (ïåðåâîä íà àíãëèéñêèé ÿçûê âûøåë â 1945
ãîäó [1℄), îêàçàëà çíà÷èìîå âëèÿíèå íà ðàçâèòèå ìàòåìàòè÷åñêîé ýêîíîìèêè, ïîñëóæèâ èñòî÷íèêîì áîëüøîìó êîëè÷åñòâó èññëåäîâàíèé è ïîðîäèâ
ìíîæåñòâî èíòåðïðåòàöèé. Ìîäåëü Íåéìàíà ÿâëÿåòñÿ îáîáùåíèåì èçâåñòíîé ìîäåëè Ëåîíòüåâà, äîïóñêàþùèì ïðîèçâîäñòâî êàæäûì òåõíîëîãè÷åñêèì ïðîöåññîì áîëåå îäíîãî âèäà ïðîäóêòîâ. Çíà÷èòåëüíîå ÷èñëî ó÷åáíûõ
ïîñîáèé ïî ìàòåìàòè÷åñêîé ýêîíîìèêå [2℄ [3℄ [4℄, â òîì ÷èñëå ñîâðåìåííûõ [5℄, ñîäåðæèò âûâåäåííûå â îðèãèíàëüíîé ñòàòüå îí Íåéìàíà îïèñàíèå ìîäåëè è èññëåäîâàíèÿ äèíàìè÷åñêîãî ðàâíîâåñèÿ êàê ñáàëàíñèðîâàííîãî ðîñòà áåç èçìåíåíèÿ ñòðóêòóðû, ðàñøèðåííûå è äîïîëíåííûå äðóãèìè àâòîðàìè. Îáçîð îïèñàííîé â ýòîé ëèòåðàòóðå êëàññè÷åñêîé ìîäåëè
Íåéìàíà, áåç óãëóáëåíèÿ â óñëîâèÿ ñóùåñòâîâàíèÿ è ñâîéñòâà ðàâíîâåñèÿ,
ïðèâåäåí â ñîîòâåòñòâóþùåì ðàçäåëå. Âàæíûì ñëåäñòâèåì èññëåäîâàíèé
äèíàìè÷åñêîãî ðàâíîâåñèÿ ÿâëÿþòñÿ òåîðåìû î ìàãèñòðàëÿõ, êîòîðûå íå
ðàññìàòðèâàþòñÿ â ðàìêàõ ýòîé ðàáîòû äëÿ îçíàêîìëåíèÿ ìîæíî îáðàòèòüñÿ ê [6℄.
Ìîäåëü Íåéìàíà íàãëÿäíà è øèðîêî ïðèìåíèìà äëÿ ìîäåëèðîâàíèÿ
ýêîíîìè÷åñêèõ ñèñòåì ðàçíîãî ìàñøòàáà, è ýòà ðàáîòà àêöåíòèðóåò âíèìàíèå íà ñèñòåìàõ ìàëîãî ìàñøòàáà (óðîâåíü îòäåëüíûõ ïðåäïðèÿòèé), äëÿ
êîòîðûõ äèñêðåòíîñòü èçìåíåíèÿ èíòåíñèâíîñòè òåõíîëîãè÷åñêèõ ïðîöåññîâ íå ïîçâîëÿåò ñ÷èòàòü ïîãðåøíîñòü îò èñïîëüçîâàíèÿ íåïðåðûâíîé ìîäåëè íåçíà÷èòåëüíîé. Àâòîðó íå óäàëîñü íàéòè ëèòåðàòóðó, ïîñâÿùåííóþ
ýòîìó âîïðîñó, ïðè ýòîì, ïî ìíåíèþ àâòîðà, èññëåäîâàíèå îïòèìèçàöèîííîé çàäà÷è äëÿ öåëî÷èñëåííîé ìîäåëè ìîæåò ïîìî÷ü ïîíÿòü, êàê áûñòðî
1 Neumann
J. von.
Uber
ein okonomis
hes Glei
hungssystem und eine Verallgemeinerung des Brou-
wers
hen Fixpunktsatzes // Ergebnisse eines Mathematis
hen Kolloquiums, 1937. No 8. P. 73-83.
3
ðàñòåò îïòèìàëüíîå ðåøåíèå äëÿ òàêèõ ñèñòåì.
 ðàáîòå ïðèìåíÿþòñÿ íåñêîëüêî ðàçëè÷íûõ ìåòîäîâ ðåøåíèÿ îïòèìèçàöèîííîé çàäà÷è äëÿ öåëî÷èñëåííîé ìîäåëè, ïðåäñòàâëÿþùèå ðàçëè÷íûå
ïîäõîäû ê çàäà÷å (ñòàòè÷åñêèé è äèíàìè÷åñêèé, ñ íàõîæäåíèåì òî÷íîãî è
ïðèáëèæåííîãî ðåøåíèÿ), âûÿñíÿþòñÿ èõ äîñòîèíñòâà, íåäîñòàòêè è îãðàíè÷åíèÿ. Òàêæå â ðàìêàõ äàííîé ðàáîòû âûïîëíåíà ïðîãðàììíàÿ ðåàëèçàöèÿ ýòèõ ìåòîäîâ, ïîçâîëÿþùàÿ ïðîâåðèòü ýåêòèâíîñòü è ïðîâåñòè
áîëåå äåòàëüíîå ñðàâíåíèå.
4
Êëàññè÷åñêàÿ ìîäåëü Íåéìàíà â ëèòåðàòóðå
Ýòîò ðàçäåë ïîñâÿùåí îðìàëüíîìó îïèñàíèþ êëàññè÷åñêîé ìîäåëè
Íåéìàíà äèíàìè÷åñêîé ëèíåéíîé ìîäåëè ïðîèçâîäñòâà, êàêîé îíà ïðåäñòàâëåíà â ýêîíîìè÷åñêîé ëèòåðàòóðå. Ýòà ìîäåëü ¾ïðåäñòàâëÿåò ñîáîé ñóùåñòâåííûé øàã âïåðåä ïî ñðàâíåíèþ ñ ìîäåëüþ Ëåîíòüåâà¿ [4℄ ëåîíòüåâñêàÿ ìîäåëü òîæå äîïóñêàåò äèíàìè÷åñêóþ îðìóëèðîâêó, îäíàêî â
ìîäåëè Íåéìàíà òåõíîëîãè÷åñêèå ïðîöåññû ìîãóò ïðîèçâîäèòü áîëåå îäíîãî ïðîäóêòà, ÷òî ïîçâîëÿåò îïåðèðîâàòü íå òîëüêî ïîíÿòèåì ¾÷èñòîé¿
îòðàñëè.
àññìîòðèì ýêîíîìè÷åñêóþ ìîäåëü, â êîòîðîé ñóùåñòâóåò n ∈ N
ïðî-
äóêòîâ è m ∈ N ëèíåéíûõ òåõíîëîãè÷åñêèõ ïðîöåññîâ, ïåðåðàáàòûâàþùèõ
íåêîòîðûå êîëè÷åñòâà ïðîäóêòîâ â äðóãèå êîëè÷åñòâà ýòèõ æå ïðîäóêòîâ.
Ïîä ïðîäóêòàìè ïîäðàçóìåâàþòñÿ ïåðâè÷íûå àêòîðû ïðîèçâîäñòâà
(çåìëÿ, òðóä, êàïèòàë), ñûðüå, òîâàðû è óñëóãè âñå, ÷òî íåîáõîäèìî äëÿ
ïðîèçâîäñòâà è âñå, ÷òî â ðåçóëüòàòå îêàçûâàåòñÿ ïðîèçâåäåíî [4, 2.1℄.
Ëèíåéíîñòü òåõíîëîãè÷åñêèõ ïðîöåññîâ ïîíèìàåòñÿ â çíà÷åíèè ëèíåéíîé çàâèñèìîñòè êîëè÷åñòâà ïðîèçâåäåííûõ òîâàðîâ îò êîëè÷åñòâà ðåñóðñîâ.
Êàæäûé i-òûé ïðîöåññ ìîæíî îïèñàòü ïðè ïîìîùè äâóõ íåîòðèöàòåëüíûõ âåêòîðîâ: ai = {ai1 , ai2 , ..., ain}, êîòîðûé âûðàæàåò êîëè÷åñòâî çàòðà÷èâàåìûõ òîâàðîâ, è bi = {bi1, bi2 , ..., bin}, êîòîðûé âûðàæàåò êîëè÷åñòâî
ïðîèçâîäèìûõ.
Îïðåäåëåíèå.
Íåîòðèöàòåëüíàÿ ìàòðèöà A = (aij )m,n
i=1,j=1 íàçûâàåòñÿ
ìàòðèöåé çàòðàò, à íåîòðèöàòåëüíàÿ ìàòðèöà B
ðèöåé âûïóñêà.
= (bij )m,n
i=1,j=1
ìàò-
Ìàòðèöû A è B íåîòðèöàòåëüíû, ïîñêîëüêó ýëåìåíòû ìàòðèö ïðåäñòàâëÿþò êîëè÷åñòâà òîâàðîâ. Òàêæå ýòè ìàòðèöû ïî ñâîåé ïðèðîäå ÿâëÿþòñÿ
5
ðàçðåæåííûìè, òàê êàê ïîäàâëÿþùåå ÷èñëî ïðîöåññîâ çàäåéñòâóåò ëèøü
îïðåäåëåííîå ÷èñëî ðàçíûõ ïðîäóêòîâ, îáû÷íî ñèëüíî ìåíüøåå ÷åì îáùåå
÷èñëî n, ïðåäñòàâëåííîå â ìîäåëè.
×òîáû ¾ìîäåëü óíêöèîíèðîâàëà æåëàòåëüíûì îáðàçîì¿ [3, 9.5℄
âñÿêèé ïðîäóêò âûïóñêàëñÿ õîòÿ áû îäíèì ïðîöåññîì è âî âñÿêîì ïðîöåññå
õîòÿ áû îäèí ïðîäóêò çàòðà÷èâàëñÿ íàëîæèì íà ìàòðèöû A è B ñëåäóþùèå îãðàíè÷åíèÿ:
∀i ∃j aij > 0,
∀j ∃i bij > 0.
(1)
Äèíàìèêó ìîäåëè ìû áóäåì ðàññìàòðèâàòü íà ïðîìåæóòêå âðåìåíè
[0, T ]. È õîòÿ ïðîèçâîäñòâî íåïðåðûâíûé ïðîöåññ, äëÿ ñóùåñòâåííîãî
óïðîùåíèÿ ðàáîòû ñ ìîäåëüþ óäîáíî äîïóñòèòü äèñêðåòíîñòü âðåìåíè.
Äðóãîå âàæíîå äîïóùåíèå: ïðîäîëæèòåëüíîñòü âñåõ òåõíîëîãè÷åñêèõ
ïðîöåññîâ ñîñòàâëÿåò îäíó åäèíèöó âðåìåíè. Â ñòàòüå îí Íåéìàíà óòâåðæäàåòñÿ, ÷òî ïðîöåññû ñ áîëüøåé ïðîäîëæèòåëüíîñòüþ ìîæíî ðàçáèòü íà
ïðîöåññû åäèíè÷íîé ïðîäîëæèòåëüíîñòè, ïðè íåîáõîäèìîñòè ââîäÿ ïðîìåæóòî÷íûå ðåñóðñû êàê äîïîëíèòåëüíûå ïðîäóêòû [1℄. Äîêàæåì ýòî, ñîðìóëèðîâàâ óòâåðæäåíèå â ñëåäóþùåé îðìå:
Ìîäåëü ñ ðàçëè÷íîé ïðîäîëæèòåëüíîñòüþ òåõíîëîãè÷åñêèõ ïðîöåññîâ ìîæíî ñâåñòè ê ìîäåëè Íåéìàíà.
Óòâåðæäåíèå 1.
Äîêàçàòåëüñòâî.
Äîêàæåì óòâåðæäåíèå äëÿ ìîäåëè, â êîòîðîé äâà òåõ-
íîëîãè÷åñêèõ ïðîöåññà Q1 è Q2 è n ïðîäóêòîâ.
Ïóñòü Q1 äëèòñÿ r åä. âðåìåíè, à Q2 s, ïðè ýòîì ÍÎÄ(r, s) = p,
r/p = k , s/p = l. Åñëè ìû ïðèìåì çà íîâóþ åäèíèöó âðåìåíè âðåìåííîé
ïðîìåæóòîê â p åä., òî Q1 áóäåò çàíèìàòü âðåìÿ k .
àçîáüåì Q1 íà k ïîñëåäîâàòåëüíûõ ïðîöåññîâ: äëÿ ýòîãî çàìåíèì åãî
íà ïðîöåññû Q11 , Q21 , ..., Qk1 , äëÿùèõñÿ 1 åäèíèöó âðåìåíè, è ââåäåì k − 1
6
äîïîëíèòåëüíûõ ðåñóðñîâ. Äëÿ Q11 âåêòîð çàòðàò áóäåò òàêèì æå, êàêîé
áûë ó Q1 , à âåêòîð âûïóñêà áóäåò èìåòü åäèíñòâåííîå íåíóëåâîå çíà÷åíèå
òîëüêî äëÿ ýëåìåíòà, ñîîòâåòñòâóþùåãî ïåðâîìó äîïîëíèòåëüíîìó ðåñóðñó. Âåêòîð çàòðàò Q21 ðàâåí âåêòîðó âûïóñêà Q11 , à åäèíñòâåííîå íåíóëåâîå
çíà÷åíèå âåêòîðà âûïóñêà Q21 áóäåò ñîîòâåòñòâîâàòü âòîðîìó äîïîëíèòåëüíîìó ðåñóðñó, è òàê äàëåå. Ïîñëåäíèé ïðîöåññ Qk1 áóäåò èìåòü âåêòîð âûïóñêà, ðàâíûé âåêòîðó âûïóñêà Q1 . Âìåñòå âñå íîâîââåäåííûå ïðîöåññû çà
âðåìÿ k çàòðà÷èâàþò è ïðîèçâîäÿò òå æå ïðîäóêòû, ÷òî è Q1 , à òðåáîâàíèå
ñïåöèàëüíûõ äîïîëíèòåëüíûõ ðåñóðñîâ íå ïîçâîëèò çàïóñòèòü êàêîé-ëèáî
èç âíóòðåííèõ ïðîöåññîâ îòäåëüíî.
Q2 â íîâûõ åäèíèöàõ âðåìåíè áóäåò çàíèìàòü âðåìÿ l. Òàê æå, êàê è
Q1, ðàçîáüåì Q2 íà l ïîñëåäîâàòåëüíûõ ïðîöåññîâ, äëÿùèõñÿ 1 åäèíèöó
âðåìåíè.
 êîíå÷íîì ñ÷åòå ìû ïîëó÷èëè ìîäåëü ñ n + k + l − 2 ïðîäóêòàìè è k + l
ïðîöåññàìè ñ îäèíàêîâîé ïðîäîëæèòåëüíîñòüþ, ïðè÷åì ïî ñâîåìó ñìûñëó
îíà ïîëíîñòüþ ñîâïàäàåò ñ èñõîäíîé.
Àíàëîãè÷íûì îáðàçîì ìîæíî ñâåñòè ìîäåëü ñ ïðîèçâîëüíûì êîëè÷åñòâîì ïðîöåññîâ m ïðîäîëæèòåëüíîñòüþ t1 , t2 , ..., tm . Ïîñëå ïðåîáðàçîâàíèé ìû ïîëó÷èì
t1 +t2 +...+tm
ÍÎÄ(t1 ,t2 ,...,tm )
t1 +t2 +...+tm
ïðîöåññîâ è n+ ÍÎÄ
−m ðåñóðñîâ.
(t1 ,t2 ,...,tm )
Èñõîäíûå m òåõíîëîãè÷åñêèõ ïðîöåññîâ íàçûâàþòñÿ
áàçèñíûìè. Ñîîò-
âåòñòâóþùèå èì ñòðîêè ìàòðèö çàòðàò è âûïóñêà îïðåäåëÿþò òåõíîëîãè÷åñêèé ïîòåíöèàë, çàëîæåííûé â êàæäîì ïðîöåññå. Äëÿ òîãî, ÷òîáû âûðàçèòü, íàñêîëüêî ïðîöåññ ó÷àñòâóåò â îáùåì ïðîèçâîäñòâå â êîíêðåòíûé
ìîìåíò âðåìåíè, èñïîëüçóþò ïîíÿòèå
èíòåíñèâíîñòè.
Ïðåäñòàâèì ïðîèçâîäñòâî â ìîìåíò âðåìåíè t êàê òåõíîëîãè÷åñêèé ïðîöåññ, ïðåäñòàâëÿþùèé èç ñåáÿ ëèíåéíóþ êîìáèíàöèþ áàçèñíûõ ïðîöåññîâ.
Âåêòîðû çàòðàò è âûïóñêà ýòîãî ïðîöåññà áóäóò èìåòü âèä:
at = {
m
X
i=1
zi ai1 ,
m
X
zi ai2 , ...,
i=1
m
X
i=1
7
zi ain } = zA,
bt = {
m
X
i=1
zi bi1,
m
X
zi bi2, ...,
i=1
m
X
zi bin} = zB,
i=1
ãäå z1 , z2 , ..., zn íåêîòîðûå õàðàêòåðíûå äëÿ ìîìåíòà âðåìåíè t êîýèöèåíòû, íàçûâàåìûå èíòåíñèâíîñòÿìè.
Îïðåäåëåíèå.
Âåêòîðîì èíòåíñèâíîñòåé â ìîìåíò âðåìåíè t íàçûâàåò-
ñÿ íåîòðèöàòåëüíûé âåêòîð zt = {z1 , z2 , ..., zm}.
Îïðåäåëåíèå.
Âåêòîð x
áîëüøå èëè ðàâåí (ìåíüøå èëè ðàâåí) âåêòîðà
y òîé æå ðàçìåðíîñòè, åñëè êàæäûé ýëåìåíò xi âåêòîðà x áîëüøå èëè ðàâåí (ìåíüøå èëè ðàâåí) ñîîòâåòñòâóþùåìó ýëåìåíòó yi âåêòîðà y . Âåêòîð
x
áîëüøå (ìåíüøå) âåêòîðà y òîé æå ðàçìåðíîñòè, åñëè ñóùåñòâóåò õîòÿ
áû îäèí ýëåìåíò xi âåêòîðà x, ñòðîãî áîëüøèé (ìåíüøèé) ñîîòâåòñòâóþùåãî ýëåìåíòà yi âåêòîðà y , à âñå îñòàëüíûå ýëåìåíòû x áîëüøå èëè ðàâíû
(ìåíüøå èëè ðàâíû) ñîîòâåòñâóþùèì ýëåìåíòàì y .
Îïðåäåëåíèå.
Ýêîíîìè÷åñêàÿ ìîäåëü íàçûâàåòñÿ
çàìêíóòîé, åñëè â íåé
îòñóòñòâóåò ïîñòóïëåíèå ðåñóðñîâ èçâíå è ýêñïîðò ïðîäóêòîâ.
Íàëîæèì íà ðàññìàòðèâàåìóþ ìîäåëü óñëîâèå çàìêíóòîñòè. Áîëåå òîãî, ââåäåì áîëåå ñòðîãîå îãðàíè÷åíèå: â ïåðèîä (t, t + 1) ìû ìîæåì òðàòèòü
òîëüêî ïðîèçâåäåííûå â ïåðèîä (t − 1, t) ïðîäóêòû (â ïîñîáèè Àøìàíîâà
ýòî îãðàíè÷åíèå è íàçâàíî óñëîâèåì çàìêíóòîñòè [4, 2.1℄, îäíàêî íåîáõîäèìî ñêàçàòü î ïðîäóêòàõ, ïðîèçâåäåííûõ íà ïðåäûäóùèõ ïðîìåæóòêàõ
âðåìåíè, ÷òî áóäåò ñäåëàíî íèæå). Òàê êàê âåêòîðû çàòðàò è âûïóñêà â ìîìåíò âðåìåíè t âûðàæàþòñÿ êàê zt A è zt B , òî èç ýòèõ óñëîâèé ìû ïîëó÷àåì
ñëåäóþùèå íåðàâåíñòâà:
zt+1 A 6 zt B, t ∈ {1, ..., T − 1},
z1 A 6 y0 ,
(2)
ãäå y0 âåêòîð çàïàñîâ íà íà÷àëî ðàññìàòðèâàåìîãî ïåðèîäà âðåìåíè [0, T ].
8
Óñëîâèå îá èñïîëüçîâàíèè òîëüêî ïðîèçâåäåííîãî íà ïðåäûäóùåì ïðîìåæóòêå âðåìåíè íå îçíà÷àåò, îäíàêî, ÷òî äàííàÿ ýêîíîìè÷åñêàÿ ìîäåëü íå
ïîäðàçóìåâàåò õðàíåíèÿ ïðîäóêòîâ. Õðàíåíèå áåç ïîòåðü ìîæíî ïðåäñòàâèòü êàê òåõíîëîãè÷åñêèé ïðîöåññ, âåêòîð çàòðàò êîòîðîãî ðàâåí âåêòîðó
âûïóñêà. Ïðè ýòîì ìîäåëü Íåéìàíà ¾õîðîøî ïðèñïîñîáëåíà, â ÷àñòíîñòè,
ê àíàëèçó ìîäåëåé ñ êàïèòàëîì, èçíàøèâàåìûì ïðè èñïîëüçîâàíèè¿ [2,
10.3℄ Çíàÿ ñðîê ãîäíîñòè èëè âåðîÿòíîñòü ïîëîìêè òîãî èëè èíîãî ïðîäóêòà, â òåõíîëîãè÷åñêèé ïðîöåññ õðàíåíèÿ ìîæíî çàëîæèòü è èçíîñ ïðîäóêòà, ñäåëàâ ñîîòâåòñòâóþùèé ýëåìåíò âåêòîðà âûïóñêà ìåíüøå, ÷åì â
âåêòîðå çàòðàò. Òàê æå è óñëîâèå çàìêíóòîñòè îçíà÷àåò íå ñòîëüêî ïîëíóþ
èçîëÿöèþ ñèñòåìû, ñêîëüêî òî, ÷òî èìïîðò è ýêñïîðò íåîáõîäèìî âûðàæàòü
÷åðåç òåõíîëîãè÷åñêèå ïðîöåññû.
 ñâîåé ìîäåëè îí Íåéìàí òàêæå ðàññìàòðèâàë
öåíû íà òîâàðû. Òî÷-
íî òàê æå, êàê è èíòåíñèâíîñòü äëÿ òåõíîëîãè÷åñêèõ ïðîöåññîâ, öåíû íà
ïðîäóêòû èçìåíÿþòñÿ âî âðåìåíè. Ïðè ýòîì âåêòîðû öåí äâîéñòâåííû âåêòîðàì èíòåíñèâíîñòè [1℄.
Îïðåäåëåíèå.
Âåêòîðîì öåí â ìîìåíò âðåìåíè t íàçûâàåòñÿ íåîòðèöà-
òåëüíûé âåêòîð pt = {p1 , p2 , ..., pm}.
Óñëîâèåì, äâîéñòâåííûì (2), ÿâëÿåòñÿ
íûõ ïðîöåññîâ :
óñëîâèå íåïðèáûëüíîñòè áàçèñ-
Apt > Bpt+1, t ∈ {1, ..., T − 1}.
(3)
Ýòî óñëîâèå îáóñëîâëåíî òåì, ÷òî îñíîâíîé èíòåðåñ äëÿ îí Íåéìàíà
ïðåäñòàâëÿëî ñîñòîÿíèå
ðàâíîâåñèÿ, ïðè êîòîðîì âåêòîð èíòåíñèâíîñòåé
ðàñòåò âî âðåìåíè ñ ïîñòîÿííûì êîýèöèåíòîì, à öåíû îñòàþòñÿ íåèçìåííûìè. Åñëè æå êàêîé-òî ïðîöåññ ÿâëÿåòñÿ ïðèáûëüíûì, òî ýòî ïðèâîäèò ê
ðîñòó öåí è íàðóøàåò ðàâíîâåñèå [1℄. Ìîæíî âñïîìíèòü óñëîâèå ýêîíîìè÷åñêîãî ðàâíîâåñèÿ â óñëîâèÿõ ñîâåðøåííîé êîíêóðåíöèè ðàâåíñòâî ñïðîñà
è ïðåäëîæåíèÿ: ïðè íåì òîæå íå ñîçäàåòñÿ íèêàêîé ïðèáûëè [5, 5.3℄.
9
Äëÿ äåíåæíîé ìàññû â ìîäåëè ñóùåñòâóþò ñëåäóþùèå óñëîâèÿ: îíà íå
èçìåíÿåòñÿ ñî âðåìåíåì è ïîñòîÿííî íàõîäèòñÿ â îáðàùåíèè. Ýòî îçíà÷àåò, ÷òî öåíû íà ïðîäóêòû íà ïðîìåæóòêå (t, t + 1) óñòàíàâëèâàþòñÿ òàêèì
îáðàçîì, ÷òîáû îáùàÿ âûðó÷êà îò ðåàëèçàöèè òîâàðîâ, ïðîèçâåäåííûõ íà
ïðîìåæóòêå (t − 1, t), ðàâíÿëàñü äåíåæíûì çàòðàòàì íà ðåñóðñû íà ýòîì
æå ïðîìåæóòêå (t − 1, t). Ïðè ýòîì âñÿ ýòà âûðó÷êà äîëæíà áûòü ïîëíîñòü
ïîòðà÷åíà íà ðåñóðñû äëÿ ïðîèçâîäñòâà íà ïðîìåæóòêå (t, t + 1). Ìàòåìàòè÷åñêè ÷åðåç ìàòðèöû çàòðàò è âûïóñêà è âåêòîðû èíòåíñèâíîñòè è öåí
ýòî ìîæíî çàïèñàòü êàê:
zt Apt = zt Bpt+1,
zt Bpt+1 = zt+1 Apt+1, t ∈ {1, ..., T − 1},
Îïðåäåëåíèå.
Ìîäåëüþ Íåéìàíà íàçûâàåòñÿ äèíàìè÷åñêàÿ ìîäåëü ñ äèñ-
êðåòíûì âðåìåíåì è ëèíåéíîé òåõíîëîãèåé, â êîòîðîé îïðåäåëåíû n ïðîäóêòîâ è m áàçèñíûõ òåõíîëîãè÷åñêèõ ïðîöåññîâ è äåéñòâóåò ñëåäóþùàÿ
ñèñòåìà îãðàíè÷åíèé:
zt+1 A 6 zt B,
z1 A 6 y0,
Apt > Bpt+1,
zt Apt = zt Bpt+1,
z Bp = z Ap
t
t+1
t+1
(4)
t+1 ,
t ∈ {1, ..., T − 1},
ãäå A è B ìàòðèöû çàòðàò è âûïóñêà, óäîâëåòâîðÿþùèå îãðàíè÷åíèÿì (1), zt è pt âåêòîðû èíòåíñèâíîñòåé è öåí â ìîìåíò âðåìåíè t, y0
âåêòîð íà÷àëüíûõ çàïàñîâ.
10
Ïîñòàíîâêà çàäà÷è
Êëàññè÷åñêàÿ ìîäåëü Íåéìàíà ñ ñèñòåìîé îãðàíè÷åíèé (4), îïèñàííàÿ
â ïðåäûäóùåì ïóíêòå, óäîáíà äëÿ èññëåäîâàíèÿ ýêîíîìè÷åñêîãî ðàâíîâåñèÿ òåîðåòè÷åñêîé ýêîíîìèêè ñ ñîâåðøåííîé êîíêóðåíöèåé. Îäíàêî ìîäåëü
Íåéìàíà â öåëîì èìååò êóäà áîëåå øèðîêîå ïðèìåíåíèå. Íàïðèìåð, ìû ìîæåì íå ðàññìàòðèâàòü äâîéñòâåííûå îãðàíè÷åíèÿ, ñâÿçàííûå ñ âåêòîðîì
öåí âåäü â ðåàëüíûõ ýêîíîìèêàõ, äàëåêèõ îò èäåàëüíîé ýêîíîìèêè ñ
ñîâåðøåííîé êîíêóðåíöèåé, íå ñîáëþäàþòñÿ íåïðèáûëüíîñòü ïðîöåññîâ è
íåèçìåííîñòü äåíåæíîé ìàññû. Òîãäà ìîæíî âîîáùå íå ðàññìàòðèâàòü âåêòîð öåí.
Ìîäåëü Íåéìàíà ïðèìåíèìà äëÿ îïèñàíèÿ ðåàëüíûõ îáúåêòîâ ñàìîãî ðàçíîãî ìàñøòàáà: îò ýêîíîìèêè öåëûõ ñòðàí äî ïðîèçâîäñòâà îäíîãî
ïðåäïðèÿòèÿ. Îäíàêî íà ìàëûõ ìàñøòàáàõ íåïðåðûâíîñòü çíà÷åíèé âåêòîðà èíòåíñèâíîñòåé íå ñîîòâåòñòâóåò ðåàëüíîìó ïîëîæåíèþ äåë, ïîýòîìó
äëÿ çàäà÷ òàêîãî òèïà óäîáíåå ðàññìàòðèâàòü ìîäåëü Íåéìàíà ñ öåëî÷èñëåííûìè èíòåíñèâíîñòÿìè.
Ïðèìåíèâ âûøåóêàçàííûå çàìå÷àíèÿ ê êëàññè÷åñêîé ìîäåëè Íåéìàíà,
ìû ïîëó÷èì ìîäèèêàöèþ ìîäåëè, êîòîðàÿ â äàëüíåéøåì â ðàáîòå áóäåò
íàçûâàòüñÿ
öåëî÷èñëåííîé ìîäåëüþ Íåéìàíà.
Îïðåäåëåíèå.
Öåëî÷èñëåííîé ìîäåëüþ Íåéìàíà áóäåì íàçûâàòü äèíàìè-
÷åñêóþ ìîäåëü ñ äèñêðåòíûì âðåìåíåì è ëèíåéíîé òåõíîëîãèåé, â êîòîðîé
îïðåäåëåíû n ïðîäóêòîâ è m áàçèñíûõ òåõíîëîãè÷åñêèõ ïðîöåññîâ è äåéñòâóåò ñëåäóþùàÿ ñèñòåìà îãðàíè÷åíèé:
zt+1 A 6 zt B, t ∈ {1, ..., T − 1},
z1 A 6 y0,
zt ∈ Zm
+ , t ∈ {1, ..., T },
11
(5)
ãäå A è B ìàòðèöû çàòðàò è âûïóñêà, óäîâëåòâîðÿþùèå îãðàíè÷åíèÿì (1), zt âåêòîð èíòåíñèâíîñòåé â ìîìåíò âðåìåíè t, y0 âåêòîð íà÷àëüíûõ çàïàñîâ.
Òåïåðü, êîãäà ðàññìàòðèâàåìàÿ ìîäåëü îïðåäåëåíà, îðìàëèçóåì çàäà÷ó îïòèìèçàöèè.
Äîïóñòèìûì ìíîæåñòâîì çàäà÷è áóäåò ÿâëÿòüñÿ ìíî-
æåñòâî íàáîðîâ èç T âåêòîðîâ èíòåíñèâíîñòåé â Nm , óäîâëåòâîðÿþùèõ
îãðàíè÷åíèÿì (5). Íåïîñðåäñòâåííî çàäà÷à îïòèìèçàöèè çàêëþ÷àåòñÿ â
òîì, ÷òîáû âûáðàòü èç äîïóñòèìîãî ìíîæåñòâà íåêîòîðûé îïðåäåëåííûé
íàáîð âåêòîðîâ zt , t ∈ {1, ..., T } (ýòîò íàáîð âåêòîðîâ ìû áóäåì íàçûâàòü
îïòèìàëüíûì ðåøåíèåì èëè îïòèìàëüíîé òðàåêòîðèåé ), ìàêñèìèçèðóþùèõ íåêîòîðóþ óíêöèþ, íàçûâàåìóþ öåëåâîé. Òåïåðü îïðåäåëèìñÿ ñ
öåëåâîé óíêöèåé, âûáîð êîòîðîé çàâèñèò îò ïîäõîäà ê ïîíÿòèþ ïîëåçíîñòè.
Ïîëåçíîñòü ìåðà óäîâëåòâîðåíèÿ ïîòðåáíîñòåé èíäèâèäîâ ïðè ïîòðåáëåíèè ïðîäóêòîâ. Îáùàÿ ïîëåçíîñòü ïðåäñòàâëÿåò ñîáîé
ñîâîêóïíóþ ïîëåçíîñòü ïðè ïîòðåáëåíèè âñåõ åäèíèö ïðîäóêòà, à ïðåäåëüíàÿ ïîëåçíîñòü ïðè ïîòðåáëåíèè åùå îäíîé åäèíèöû ïðîäóêòà.
Îïðåäåëåíèå.
Õîòÿ â îïðåäåëåíèè ïîëåçíîñòè èãóðèðóåò ñëîâî ¾ïîòðåáëåíèå¿, äàííîå ïîíÿòèå ïðèìåíèìî íå òîëüêî ê ïîòðåáèòåëÿì, íî è ê ïðîèçâîäèòåëÿì
â êîíòåêñòå ìîäåëè Íåéìàíà ìåðîé óäîâëåòâîðåíèÿ ïîòðåáíîñòåé ïðîèçâîäèòåëÿ ìîæåò âûñòóïàòü êîëè÷åñòâî ïðîèçâåäåííûõ ïðîäóêòîâ.
Èç
çàêîíà óáûâàþùåé ïîëåçíîñòè [5, 3.2℄ èçâåñòíî, ÷òî ïðåäåëüíàÿ
ïîëåçíîñòü ñ óâåëè÷åíèåì êîëè÷åñòâà åäèíèö ïðîäóêòà ïîñòåïåííî ñíèæàåòñÿ. Îäíàêî íà äîñòàòî÷íî áëèçêîì ê íà÷àëó èíòåðâàëå çàâèñèìîñòü îáùåé
ïîëåçíîñòè îò êîëè÷åñòâà ïðîäóêòîâ ïðàêòè÷åñêè ëèíåéíà, ÷òî ïîçâîëÿåò
ðàññìàòðèâàòü óïðîùåííóþ
ëèíåéíóþ ïîëåçíîñòü.
Òîãäà îáùàÿ ïîëåçíîñòü íåêîòîðîãî êîëè÷åñòâà îäíîãî ïðîäóêòà áóäåò ëèíåéíî çàâèñåòü îò êîëè÷åñòâà, ïîýòîìó ïîëåçíîñòü ïðîäóêòà óäîá12
íî âûðàçèòü ÷åðåç íåêîòîðûé êîýèöèåíò. Äëÿ âû÷èñëåíèÿ îáùåé ïîëåçíîñòè âñåé ñîêóïíîñòè ïðîäóêòîâ ââåäåì âåêòîð êîýèöèåíòîâ c =
{c1, c2 , ..., cn}, êàæäûé èç n ýëåìåíòîâ êîòîðîãî áóäåò âûðàæàòü âëèÿíèå
êàæäîãî ïðîäóêòà íà îáùóþ ïîëåçíîñòü.
Åñëè ìû ñòàâèì ïåðåä ñîáîé çàäà÷ó ê êîíöó çàäàííîãî ïåðèîäà äîáèòüñÿ
ìàêñèìàëüíî âîçìîæíîãî ïðèðîñòà ïðîèçâîäñòâà, òî ðå÷ü èäåò î
íàëüíîé
òåðìè-
ïîëåçíîñòè. Òàêàÿ çàäà÷à îðìàëèçóåòñÿ ïðîñòî íåîáõîäèìî
ìàêñèìèçèðîâàòü îáùóþ ïîëåçíîñòü âñåé ïðîèçâåäåííîé ïðîäóêöèè â êîíå÷íûé ìîìåíò âðåìåíè T .
Ïîñêîëüêó ïîëåçíîñòü ïðîäóêòîâ ìû îïðåäåëÿåì ñ ïîìîùüþ âåêòîðà
êîýèöèåíòîâ, à âåêòîð êîëè÷åñòâà ïðîäóêòîâ â ìîìåíò T ðàâåí zT B ,
çàäà÷ó îïòèìèçàöèè òåðìèíàëüíîé ïîëåçíîñòè ìîæíî ñîðìóëèðîâàòü
êàê:
max
zt , t∈{1..T }
c(zT B)T
(6)
 öåëîì â äàííîé ðàáîòå ðàññìàòðèâàåòñÿ òåðìèíàëüíàÿ ïîëåçíîñòü,
îäíàêî îäèí èç ìåòîäîâ îïòèìèçàöèè äîïóñêàåò íåêîòîðîå îáîùåíèå è ïîçâîëÿåò ïåðåéòè ê áîëåå îáùåìó ïîíÿòèþ èíòåãðàëüíîé ïîëåçíîñòè.
Ïðè îïòèìèçàöèè èíòåãðàëüíîé ïîëåçíîñòè ó÷èòûâàþòñÿ ïîêàçàòåëè
íà âñåé ïðîòÿæåííîñòè ðàññìàòðèâàåìîãî âðåìåííîãî ïðîìåæóòêà. Îäíàêî âîçíèêàåò âîïðîñ ïîëåçíîñòü ÷åãî èìååò ñìûñë îïòèìèçèðîâàòü? àññìàòðèâàòü ïîëåçíîñòü âñåãî îáúåìà ïðîäóêöèè íà êàæäîì øàãå íå èìååò
ñìûñëà, ïîñêîëüêó íåêîòîðàÿ ÷àñòü ïðîäóêòîâ íà êàæäîì øàãå áóäåò çàòðà÷èâàòüñÿ íà âûïóñê ïðîäóêòîâ íà ñëåäóþùåì øàãå. Ê òîìó æå òàêóþ
çàäà÷ó ìîæíî ñâåñòè ê ðÿäó ïîñëåäîâàòåëüíûõ çàäà÷ îïòèìèçàöèè òåðìèíàëüíîé ïîëåçíîñòè, è íå áóäåò íåîáõîäèìîñòè ðàññìàòðèâàòü îòäåëüíûé
âèä çàäà÷.
Çàäà÷à îïòèìèçàöèè èíòåãðàëüíîé ïîëåçíîñòè îêàçûâàåòñÿ àêòóàëüíîé
13
â êîíòåêñòå ïîääåðæàíèÿ âûñîêîãî óðîâíÿ ïîòðåáëåíèÿ. Ââåäåì ïîíÿòèå
¾ïîòðåáëåíèå¿ äëÿ ìîäåëè Íåéìàíà.
Îïðåäåëåíèå.
Ïîòðåáëåíèåì â ìîìåíò t íàçûâàåòñÿ ðàçíîñòü ìåæäó êî-
ëè÷åñòâîì ïðîèçâåäåííûõ íà øàãå t ïðîäóêòîâ è êîëè÷åñòâîì ïðîäóêòîâ,
çàòðà÷èâàåìûõ íà ïðîèçâîäñòâî íà øàãå t + 1: zt B − zt+1 A.
Íà÷àëüíûì
ïîòðåáëåíèåì (ïîòðåáëåíèåì íà íóëåâîì øàãå) òîãäà áóäåò ñ÷èòàòüñÿ ðàç-
íèöà ìåæäó íà÷àëüíûìè çàïàñàìè è çàòðàòàìè íà ïðîèçâîäñòâî íà ïåðâîì
øàãå: y0 − z1 A. Íà ïîñëåäíåì øàãå T áóäåì ñ÷èòàòü ïîòðåáëåííûìè âñå
ïðîèçâåäåííûå ïðîäóêòû: zT B .
Ïîëåçíîñòü ïîòðåáëåíèÿ ìîæåò áûòü íåîäíîðîäíîé îòíîñèòåëüíî âðåìåíè, ïîýòîìó ââåäåì êîýèöèåíòû k0 , k1 , ..., kT , êîòîðûå áóäóò âûðûæàòü ýòó íåîäíîðîäíîñòü. Ñ ó÷åòîì âåêòîðà êîýèöèåíòîâ ïîëåçíîñòè
ïðîäóêòîâ c, çàäà÷à îïòèìèçàöèè èíòåãðàëüíîé ïîëåçíîñòè îðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì:
max
zt , t∈{1..T }
c k0y0 +
T
X
(ki(zi B)T − ki−1(zi A)T )
i=1
!
(7)
Ìîæíî çàìåòèòü, ÷òî çàäà÷à òåðìèíàëüíîé ïîëåçíîñòè ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì çàäà÷è èíòåãðàëüíîé ïîëåçíîñòè ïðè k0 = 0, ..., kT −1 = 0,
kT = 1 .
Èòàê, çàäà÷à îïòèìèçàöèè îïðåäåëåíà, ìîæíî ïåðåéòè ê âûáîðó ìåòîäîâ ðåøåíèÿ.
Çàäà÷à ðàçâåðíóòà âî âðåìåíè, ò.å. ÿâëÿåòñÿ äèíàìè÷åñêîé, îäíàêî åñëè
ðàññìàòðèâàòü íàáîð èç T âåêòîðîâ ðàçìåðíîñòè m êàê âåêòîð ðàçìåðíîñòè T m, òî çàäà÷ó ìîæíî ñ÷èòàòü ñòàòè÷åñêîé, ÷òî ïîçâîëÿåò ïðèìåíÿòü
ê íåé ìåòîäû ðåøåíèÿ ñòàòè÷åñêèõ çàäà÷. Òàêîé ïîäõîä íàçûâàåòñÿ
ñâå-
äåíèåì ê ñòàòè÷åñêîé çàäà÷å, è äàííûé ïîäõîä ìîæåò îêàçàòüñÿ âåñüìà
ïëîäîòâîðíûì, åñëè ïîëó÷àåìàÿ ñòàòè÷åñêàÿ çàäà÷à õîðîøî èçó÷åíà è äëÿ
íåå èìåþòñÿ ýåêòèâíûå àëãîðèòìû ðåøåíèÿ. Îäíàêî åñëè âðåìåííàÿ
14
ýåêòèâíîñòü àëãîðèòìîâ ýêñïîíåíöèàëüíî çàâèñèò îò ðàçìåðíîñòè, òî
èõ èñïîëüçîâàíèå ìîæåò áûòü íåðàöèîíàëüíûì ïðè äîñòàòî÷íî áîëüøèõ
T.
Äðóãîé ïîäõîä ê äèíàìè÷åñêîé çàäà÷å ïðåäñòàâèòü åå êàê ïîñëåäîâàòåëüíîñòü ïîäçàäà÷, íàõîäÿùèõ êàæäûé èç T âåêòîðîâ îïòèìàëüíîãî ðåøåíèÿ íà îñíîâàíèè óæå íàéäåííûõ. Ñîîòâåòñòâåííî, äëÿ ýòèõ ïîäçàäà÷
èç îöåíêè âðåìåííîé ýåêòèâíîñòè óõîäèò T ÷òî ñàìî ïî ñåáå óæå ÿâëÿåòñÿ áîëüøèì ïðåèìóùåñòâîì. Òàêîé ïîäõîä íàçûâàåòñÿ
ïðîãðàììèðîâàíèåì.
äèíàìè÷åñêèì
Ìåòîäû ìîæíî ðàçäåëèòü íà òî÷íûå è ïðèáëèæåííûå. Òî÷íûå ìåòîäû,
êàê ýòî ñëåäóåò èç íàçâàíèÿ, áóäóò äàâàòü çíà÷åíèå îïòèìàëüíîãî ðåøåíèÿ
ñ íóëåâîé ïîãðåøíîñòüþ. Ïîãðåøíîñòü ðåøåíèé ïðèáëèæåííûõ ìåòîäîâ
áóäåò íåíóëåâîé, îäíàêî âðåìåííàÿ ýåêòèâíîñòü òàêèõ ìåòîäîâ ìîæåò
áûòü çíà÷èòåëüíî âûøå.
 äàííîé ðàáîòå áóäóò ðàññìîòðåíû äâà êîíêðåòíûõ ìåòîäà ðåøåíèÿ
îïòèìèçàöèîííîé çàäà÷è: ïðèáëèæåííûé ìåòîä êîíòèíóàëèçàöèè, ñâîäÿùèé öåëî÷èñëåííóþ çàäà÷ó ê íåïðåðûâíîé ñòàòè÷åñêîé, è òî÷íûé ìåòîä
äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.
Çàäà÷à ðàáîòû: ïîäðîáíîå îðìàëüíîå îïèñàíèå ýòèõ ìåòîäîâ, âûäåëåíèå èõ ñâîéñòâ, îöåíêà âðåìåííîé ýåêòèâíîñòè, à òàêæå èõ ïðîãðàììíàÿ
ðåàëèçàöèÿ è ñðàâíèòåëüíûé àíàëèç íà îñíîâå ðåàëèçàöèè.
Öåëü ðàáîòû: ðàññìîòðåòü ðàçëè÷íûå ïîäõîäû ê ðåøåíèþ îïòèìèçàöèîííîé çàäà÷è äëÿ öåëî÷èñëåííîé ìîäåëè Íåéìàíà, ïîíÿòü ãðàíèöû ïðèìåíèìîñòè êîíêðåòíûõ ìåòîäîâ ðåøåíèÿ çàäà÷è è âûÿâèòü èõ äîñòîèíñòâà è
íåäîñòàòêè.
15
ëàâà 1. Ìåòîäû ðåøåíèÿ çàäà÷è
îïòèìèçàöèè ìîäåëè
Âûïèøåì öåëèêîì îïòèìèçàöèîííûå çàäà÷è, ìåòîäû ðåøåíèÿ êîòîðûõ
ìû áóäåì ðàññìàòðèâàòü â ýòîé ãëàâå:
1. Çàäà÷à òåðìèíàëüíîé ìàêñèìèçàöèè:
max
z
t , t∈{1..T }
c(zT B)T ,
zt+1A 6 zt B, t ∈ {1, ..., T − 1},
(8)
z1 A 6 y0 ,
zt ∈ Zm
+ , t ∈ {1, ..., T }.
2. Çàäà÷à èíòåãðàëüíîé ìàêñèìèçàöèè:
T
P
T
T
max c k0 y0 + (ki(zi B) − ki−1(ziA) ) ,
zt , t∈{1..T }
i=1
zt+1 A 6 zt B, t ∈ {1, ..., T − 1},
z1 A 6 y0 ,
zt ∈ Zm
+ , t ∈ {1, ..., T }.
(9)
1.1. Ìåòîä êîíòèíóàëèçàöèè
 ýêîíîìè÷åñêîé ëèòåðàòóðå èñïîëüçóåòñÿ íåïðåðûâíàÿ ìîäåëü Íåéìàíà, äàæå íåñìîòðÿ íà òî, ÷òî ñóòü ìíîãèõ òåõíîëîãè÷åñêèõ ïðîöåññîâ ïîäðàçóìåâàåò öåëî÷èñëåííîñòü. È äåéñòâèòåëüíî, äëÿ ðàñøèðÿþùèõñÿ ýêîíîìèê, â êîíòåêñòå êîòîðûõ ìîäåëü Íåéìàíà è ðàññìàòðèâàåòñÿ â ëèòåðàòóðå, çíà÷åíèÿ âåêòîðîâ zt áóäóò ðàñòè â ãåîìåòðè÷åñêîé ïðîãðåññèè îò
t è äîïóùåíèå î íåïðåðûâíîñòè íå äîëæíî ñèëüíî ïîâëèÿòü íà çíà÷åíèå
ðåøåíèÿ îïòèìèçàöèîííîé çàäà÷è. Îäíàêî êîíêðåòíûé ìåòîä ñâåäåíèÿ ê
16
íåïðåðûâíîé ìîäåëè (
êîíòèíóàëèçàöèè ) è ïîãðåøíîñòü íå îãîâàðèâàþòñÿ.
 ýòîì ïàðàãðàå áóäåò ðàññìîòðåí îäèí èç òàêèõ ìåòîäîâ, óñòàíîâëåíû
íàëàãàåìûå èì îãðàíè÷åíèÿ è îöåíêà ïîãðåøíîñòè îïòèìàëüíîãî ðåøåíèÿ.
Ïîñëåäóþùèå ðàññóæäåíèÿ ïðèìåíèìû äëÿ îáåèõ çàäà÷ òåðìèíàëüíîé (8) è èíòåãðàëüíîé (9) ìàêñèìèçàöèè äàëåå â òåêñòå çàäà÷à ñ öåëî÷èñëåííûìè îãðàíè÷åíèÿìè áóäåò íàçûâàòüñÿ èñõîäíîé. Ïîñêîëüêó â ðàññìàòðèâàåìûõ äàëåå ìîäèèêàöèÿõ çàäà÷è âèä öåëåâîé óíêöèè îñòàåòñÿ
íåèçìåííûì, ïîíÿòèÿ ¾îãðàíè÷åíèÿ çàäà÷è¿ è ¾çàäà÷à¿ èñïîëüçóþòñÿ êàê
ýêâèâàëåíòíûå.
Îòêàæåìñÿ îò îãðàíè÷åíèÿ íà öåëî÷èñëåííîñòü, ïîëó÷èâ íåïðåðûâíóþ
ìîäåëü. Òîãäà âìåñòî äèíàìè÷åñêîé çàäà÷è ïðîùå ðàññìàòðèâàòü ñòàòè÷åñêóþ âûïèñàâ îãðàíè÷åíèÿ ñî âñåõ ìîìåíòîâ âðåìåíè èç [0, T ] â åäèíóþ
ñèñòåìó îãðàíè÷åíèé, ìû ïîëó÷èì çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ
îãðàíè÷åíèÿìè:
z1 A 6 y0,
z2 A 6 z1 B,
(10)
...
zT A 6 zT −1B,
zt > {0, 0, ..., 0}, t ∈ {1, ..., T }.
×òî íàì äàñò íàõîæäåíèå îïòèìàëüíîãî ðåøåíèÿ òàêîé çàäà÷è? Î÷åâèäíî, ÷òî ïîëó÷åííîå ðåøåíèå ìîæåò áûòü âíå ìíîæåñòâà äîïóñòèìûõ
çíà÷åíèé èñõîäíîé çàäà÷è. Íî äàæå îêðóãëåíèå âíèç íå îáÿçàòåëüíî äàñò
äîïóñòèìîå çíà÷åíèå: íåðàâåíñòâî zt+1 A 6 zt B íå ãàðàíòèðóåò âûïîëíåíèÿ
⌊zt+1⌋A 6 ⌊zt ⌋B .
Ïðèìåð 1. z = (1, 0.5), A = 2
2
1
1
, B =
.
50 50
100 100
zt+1 A = 27 27 6 51 51 = zt B,
17
⌊zt+1 ⌋A = 2 2 > 1 1 = ⌊zt ⌋B.
Âîçíèêàåò íåîáõîäèìîñòü ïîñòðîèòü çàäà÷ó, äëÿ êîòîðîé îêðóãëåíèå îïòèìàëüíîãî ðåøåíèÿ áóäåò äàâàòü äîïóñòèìîå ðåøåíèå èñõîäíîé çàäà÷è.
àññìîòðèì çàäà÷ó ñ îãðàíè÷åíèÿìè âèäà:
z1 A 6 y0,
z2 A 6 (z1 − {1, 1, ..., 1})B,
...
zT A 6 (zT −1 − {1, 1, ..., 1})B,
zt > {0, 0, ..., 0}, t ∈ {1, ..., T }.
Îêðóãëåíèå âíèç îïòèìàëüíîãî ðåøåíèÿ çàäà÷è
äàñò äîïóñòèìîå ðåøåíèå èñõîäíîé çàäà÷è.
Óòâåðæäåíèå 2.
Äîêàçàòåëüñòâî.
(11)
(11)
Îáîçíà÷èì îïòèìàëüíûå çíà÷åíèÿ âåêòîðîâ èíòåíñèâ-
íîñòåé â çàäà÷å (11) êàê zt∗ , t ∈ {1, ..., T }. Òîãäà âåðíî, ÷òî
∗
zt+1
A 6 (zt∗ − {1, 1, ..., 1})B, t ∈ {1, ..., T − 1}.
Èç ñëåäóþùåé öåïî÷êè î÷åâèäíûõ íåðàâåíñòâ:
∗
∗
⌊zt+1
⌋A 6 zt+1
A 6 (zt∗ − {1, 1, ..., 1})B 6 ⌊zt∗ ⌋B,
ïîëó÷àåì âûðàæåíèå âèäà
∗
⌊zt+1
⌋A 6 ⌊zt∗ ⌋B, t ∈ {1, ..., T − 1}.
Òàê êàê z1∗ A 6 y0 , òî ⌊z1∗ ⌋A 6 y0 . Óñëîâèå öåëî÷èñëåííîñòè è íåîòðèöà∗
òåëüíîñòè ⌊zt∗ ⌋ ∈ Zm
+ ñëåäóåò èç íåîòðèöàòåëüíîñòè zt , t ∈ {1, ..., T }.
Òàêèì îáðàçîì, äëÿ ⌊zt∗ ⌋, t ∈ {1, ..., T } âûïîëíÿþòñÿ âñå îãðàíè÷åíèÿ
èñõîäíîé çàäà÷è, à çíà÷èò, îíî ÿâëÿåòñÿ äîïóñòèìûì.
18
Çàìåòèì, ÷òî çàäà÷à (11) ìîæåò íå èìåòü ðåøåíèé åñëè (zt −
{1, 1, ..., 1})B 6 {0, 0, ..., 0} äëÿ êàêîãî-ëèáî t ∈ {1, ..., T − 1}, òî â ñèëó íåîòðèöàòåëüíîñòè ìàòðèöû A íå ñóùåñòâóåò òàêîãî íåîòðèöàòåëüíîãî
zt+1, ÷òî zt+1A 6 (zt − {1, 1, ..., 1})B . Äîïóùåíèÿ, äîñòàòî÷íûå äëÿ ñóùåñòâîâàíèÿ ðåøåíèé, áóäóò îáîçíà÷åíû íåìíîãî ïîçæå.
Îáîçíà÷èì êàê εt , t ∈ {1, ..., T } íåêîòîðûå êîíêðåòíûå âåêòîðû, äëÿ
êîòîðûõ âûïîëíÿåòñÿ
εt+1A > (εt + {1, 1, ..., 1})B, t ∈ {1, ..., T − 1},
εt > 0, t ∈ {1, ..., T }.
(12)
Çàìåòèì, ÷òî òàêèå âåêòîðû ñóùåñòâóþò, åñëè êàæäûé ñòîëáåö ìàòðèöû A
ñîäåðæèò õîòÿ áû îäèí íåíóëåâîé ýëåìåíò îäíî èç îãðàíè÷åíèé â ýòîì
ìåòîäå ðåøåíèÿ.
Åñëè äëÿ íàáîðà âåêòîðîâ zet, t ∈ {1, ..., T }, ÿâëÿþùåãîñÿ äîïóñòèìûì ðåøåíèåì èñõîäíîé çàäà÷è, âûïîëíÿþòñÿ íåðàâåíñòâà
εt 6 zet , t ∈ {1, ..., T }, ãäå εt óäîâëåòâîðÿþò îãðàíè÷åíèÿì (12), òî ñóùåñòâóåò íàáîð zt∗, t ∈ {1, ..., T }, ÿâëÿþùèéñÿ äîïóñòèìûì ðåøåíèåì
çàäà÷è (11), òàêîé, ÷òî zt∗ = zet − εt.
Óòâåðæäåíèå 3.
Äîêàçàòåëüñòâî.
Èòàê, ïðåäïîëîæèì, ÷òî íåðàâåíñòâà εt 6 zet , t ∈
{1, ..., T } âûïîëíÿþòñÿ. Èç îãðàíè÷åíèé èñõîäíîé çàäà÷è:
(e
zt+1 − εt+1)A = zet+1 A − εt+1A 6 zet B − εt+1A, t ∈ {1, ..., T − 1}.
Òîãäà èç ýòîãî íåðàâåíñòâà è îãðàíè÷åíèé (12):
−εt+1A 6 −(εt + {1, 1, ..., 1})B,
zet B − εt+1A 6 zet B − (εt + {1, 1, ..., 1})B,
(e
zt+1 − εt+1)A 6 (e
zt − εt − {1, 1, ..., 1})B.
19
Çàìåíèâ â ïîñëåäíåì âûðàæåíèè zet − εt íà zt∗ , ïîëó÷èì
∗
zt+1
A 6 (zt∗ − {1, 1, ..., 1})B, t ∈ {1, ..., T − 1}.
à ïîñêîëüêó εt 6 zet , òî
zt∗ > {0, 0, ..., 0}, t ∈ {1, ..., T }.
Èçâåñòíî, ÷òî ze1 A 6 y0 , ïîýòîìó
z1∗ A = (e
z1 − ε1 )A 6 y0.
Òàêèì îáðàçîì, zt∗ , t ∈ {1, ..., T } óäîâëåòâîðÿþò îãðàíè÷åíèÿì çàäà÷è
(11), à, çíà÷èò, ÿâëÿþòñÿ äîïóñòèìûì ðåøåíèåì.
Ñóùåñòâîâàíèå äîïóñòèìûõ ðåøåíèé èñõîäíîé çàäà÷è,
äëÿ êîòîðûõ âûïîëíÿåòñÿ εt 6 zet, t ∈ {1, ..., T } ÿâëÿåòñÿ äîñòàòî÷íûì
óñëîâèåì ñóùåñòâîâàíèÿ äîïóñòèìûõ ðåøåíèé çàäà÷è (11).
Ìíîæåñòâî äîïóñòèìûõ ðåøåíèé çàäà÷è (11) ÿâëÿåòñÿ ε-ñåòüþ äëÿ ìíîæåñòâà äîïóñòèìûõ ðåøåíèé èñõîäíîé çàäà÷è, äëÿ
êîòîðûõ âûïîëíÿåòñÿ εt 6 zet, t ∈ {1, ..., T }.
Ñëåäñòâèå 3.1.
Ñëåäñòâèå 3.2.
Ñ ïîìîùüþ ñëåäóþùèõ óòâåðæäåíèé íàéäåì âçàèìîñâÿçü ìåæäó εt è
îöåíêîé ïîãðåøíîñòè ìåòîäà. Äëÿ íà÷àëà ðàññìîòðèì öåëåâóþ óíêöèþ
òåðìèíàëüíîé ìàêñèìèèñõîäíîé çàäà÷è.
Îíà èìååò âèä c(zT B)T â ñëó÷àå
T
P
çàöèè è c k0 y0 + (ki (zi B)T − ki−1(zi A)T ) â ñëó÷àå èíòåãðàëüíîé. Ïîi=1
ñêîëüêó A, B , c, ki , i = 0, T çàäàíû, òî îáå ýòè öåëåâûå óíêöèè ìîæíî
âûðàçèòü êàê ëèíåéíóþ êîìáèíàöèþ êîìïîíåíò âåêòîðîâ zi , t ∈ {1, ..., T }
(ïëþñ êîíñòàíòà â ñëó÷àå èíòåãðàëüíîé ìàêñèìèçàöèè). Ïîýòîìó, åñëè ââåñòè âåêòîð z = {zt }Tt=1 , â îáîèõ ñëó÷àÿõ öåëåâóþ óíêöèþ ìîæíî âûðàçèòü
êàê
vz T +
onst,
(13)
ãäå v âåêòîð ðàçìåðíîñòè T m. Ò.å. â îáåèõ çàäà÷àõ öåëåâàÿ óíêöèÿ
ëèíåéíî çàâèñèò îò âåêòîðîâ èíòåíñèâíîñòåé.
20
Åñëè X ∗ ∈ X ÿâëÿåòñÿ ε-ñåòüþ Xe ∈ X , òî äëÿ óíêöèè f , îïðåäåëåííîé íà X , âûïîëíÿåòñÿ íåðàâåíñòâî:
Óòâåðæäåíèå 4.
max∗ f (x) > max f (x) − ωf (ε),
x∈X
e
x∈X
ãäå ωf ìîäóëü íåïðåðûâíîñòè f .
Äîêàçàòåëüñòâî.
Ïî îïðåäåëåíèþ ìîäóëÿ íåïðåðûâíîñòè:
ωf (ε) = sup{|f (x1) − f (x2)| : x1, x2 ∈ X, |x1 − x2| 6 ε}
e äîñòèãàåòñÿ â x
Ïóñòü ìàêñèìóì ïî X
e, òîãäà èç îïðåäåëåíèÿ ε-ñåòè
ñóùåñòâóåò x∗ ∈ X ∗ , äëÿ êîòîðîãî âûïîëíÿåòñÿ |e
x − x∗| 6 ε. Ïîýòîìó
f (e
x) − ωf (ε) 6 f (x∗) 6 f (e
x) + ωf (ε).
Ïîñêîëüêó max∗ f (x) > f (x∗), èç ëåâîé ÷àñòè äâîéíîãî íåðàâåíñòâà ñëåx∈X
äóåò:
max∗ f (x) > max f (x) − ωf (ε).
x∈X
e
x∈X
Åñëè ñóùåñòâóåò âåêòîð ε = {εt}Tt=1, äëÿ êîòîðîãî âûïîëíÿþòñÿ îãðàíè÷åíèÿ (12), à äëÿ îïòèìàëüíîãî ðåøåíèÿ ze = {ezt}Tt=1
èñõîäíîé çàäà÷è âûïîëíÿåòñÿ ε 6 ze, òî
Ñëåäñòâèå 4.1.
v(z ∗ )T > v(e
z − ε)T ,
ãäå z∗ = {zt∗}Tt=1 îïòèìàëüíîå ðåøåíèå çàäà÷è (11), v âåêòîð êîýèöèåíòîâ ïðè ïåðåìåííûõ â öåëåâîé óíêöèè èç (13).
Èç îãðàíè÷åíèé (12) âèäíî, ÷òî εt ñêëîíåí ðàñòè ñ óâåëè÷åíèåì t. Íàéäåì îöåíêó ìèíèìàëüíî âîçìîæíûõ εt , t ∈ {1, ..., T } ñâåðõó, îáîçíà÷èâ åå
êàê εt . Íà ïåðâîì øàãå îöåíêà î÷åâèäíà: ε1 = ε1 = {0, 0, ..., 0}.
 íåðàâåíñòâå εt+1 A > (εt + {1, 1, ..., 1})B ìû íå ìîæåì âûðàçèòü εt+1 ,
ïîñêîëüêó A−1 ìîæåò íå ñóùåñòâîâàòü. Ïîýòîìó äëÿ ïîñëåäóþùèõ øàãîâ
21
t ìû áóäåì èñêàòü îöåíêó êîìïîíåíò âåêòîðà εt . Ïóñòü eit , i = 1, m êîìïîíåíòû, à et èõ âåðõíÿÿ îöåíêà. àñïèøåì íåðàâåíñòâî ïîäðîáíåå:
1
m
e1t+1 a11 + ... + em
t+1 am1 > (et + 1)b11 + ... + (et + 1)bm1,
e1 a12 + ... + em am2 > (e1 + 1)b12 + ... + (em + 1)bm2,
t+1
t+1
t
t
...
e1 a1n + ... + em amn > (e1 + 1)b1n + ... + (em + 1)bmn.
t+1
t+1
t
t
(14)
Ïðåäïîëîæèì, ÷òî ìû çíàåì et . Âîçüìåì òàêîé et+1 , ÷òîáû äëÿ êàæäîãî
i = 1, n âûïîëíÿëîñü
et+1
m
X
aji > (et + 1)
j=1
Pm
j=1 aji
m
X
bji.
j=1
âûðàæàåò îáùåå êîëè÷åñòâî ïðîäóêòà i, çàòðà÷èâàåìîå âî âñåõ
òåõíîëîãè÷åñêèõ ïðîöåññàõ íåðàâåíñòâî ýòîé ñóììû íóëþ ñëåäóåò èç
äîïóùåíèÿ, êîòîðîå ìû ñäåëàëè äëÿ ñóùåñòâîâàíèÿ âåêòîðîâ èç (12) (î
òîì, ÷òî êàæäûé ñòîëáåö ìàòðèöû A ñîäåðæèò õîòÿ áû îäèí íåíóëåâîé
ýëåìåíò). Ò. ê. ñóììà íå ðàâíà íóëþ, íà íåå ìîæíî ðàçäåëèòü:
(et + 1)
et+1 >
m
P
bji
j=1
m
P
.
aji
j=1
Äëÿ ýòîãî áóäåò äîñòàòî÷íî âûïîëíåíèÿ ñëåäóþùåãî ðàâåíñòâà:
(et + 1)
m
P
bji
j=1
et+1 = max
m
P
i=1,n
;
aji
j=1
et+1 = (et + 1) max
i=1,n
m
P
j=1
m
P
j=1
22
bji
.
aji
Èç ýòîé ðåêóððåíòíîé îðìóëû, çíàÿ çíà÷åíèå ε1 , ìû ìîæåì âûðàçèòü
et , t ∈ {1, ..., T }:
m
P
t−1
X
j=1
et =
max P
i=1,n m
k=1
j=1
Ââåäåì çàìåíó q = max (
m
P
i=1,n j=1
bji/
m
P
k
bji
.
aji
aji ) è ñâåðíåì âûðàæåíèå ïî îðìó-
j=1
ëå ñóììû ãåîìåòðè÷åñêîé ïðîãðåññèè:
q(qt−1 −1) , åñëè q 6= 1;
q−1
et =
t − 1, åñëè q = 1.
Îöåíêó âåêòîðà ìîæíî çàïèñàòü êàê âåêòîð èç îöåíîê åãî êîìïîíåíò:
εt = {et , et , ..., et}.
Äëÿ ðàñòóùåé ýêîíîìèêè q > 1, ïîñêîëüêó õîòÿ áû îäèí ïðîäóêò ñóììàðíî âñåìè ïðîöåññàìè ïðîèçâîäèòñÿ áîëüøå, ÷åì ïîòðåáëÿåòñÿ. Ïîýòîìó
εt (à, ñëåäîâàòåëüíî, è ïîãðåøíîñòü ìåòîäà) ýêñïîíåíöèàëüíî ðàñòåò ïî
t. Òàêèì îáðàçîì, ýòîò ìåòîä ïðèãîäåí äëÿ ðåøåíèÿ òîëüêî òåõ çàäà÷, ó
êîòîðûõ îïòèìàëüíîå çíà÷åíèå âåêòîðà èíòåíñèâíîñòåé ïî t ðàñòåò ýêñïîíåíöèàëüíî.
Ïîäûòîæèì ñóòü ðåøåíèÿ ìåòîäîì ñâåäåíèÿ ê íåïðåðûâíîé ìîäåëè:
Ïóñòü â èñõîäíîé çàäà÷å êàæäûé ñòîëáåö ìàòðèöû A ñîäåðæèò õîòÿ áû îäèí íåíóëåâîé ýëåìåíò è îïòèìàëüíîå ðåøåíèå zet, t =
1, T óäîâëåòâîðÿåò íåðàâåíñòâàì zet > {et , et , ..., et}, t = 1, T , ãäå
Òåîðåìà 5.
et =
q(qt−1 −1) ,
q−1
t − 1,
åñëè q 6= 1;
åñëè q = 1;
q = max
i=1,n
m
P
j=1
m
P
j=1
23
bji
aji
Âûðàçèì öåëåâóþ óíêöèþ èñõîäíîé çàäà÷è â âèäå P vtztT +
onst.
t=1
Äëÿ çàäà÷è ñ òàêîé æå öåëåâîé óíêöèåé è îãðàíè÷åíèÿìè âèäà
T
z1 A 6 y0 ,
z2 A 6 (z1 − {1, 1, ..., 1})B,
...
zT A 6 (zT −1 − {1, 1, ..., 1})B,
zt > {0, 0, ..., 0}, t = 1, T
óùåñòâóåò îïòèìàëüíîå ðåøåíèå zt∗,
ñëåäóþùåå íåðàâåíñòâî:
T
X
t=1
vt(zt∗ )T
>
T
X
t = 1, T
, ïðè ýòîì èìååò ìåñòî
vt (e
zt − {et , et , ..., et})T .
t=1
Îêðóãëåíèå âíèç ⌊zt∗⌋, t = 1, T äàñò äîïóñòèìîå ðåøåíèå èñõîäíîé çàäà÷è. Òàêèì îáðàçîì, ⌊zt∗⌋, t = 1, T ìîæíî ñ÷èòàòü îïòèìàëüíûì ðåøåíèåì èñõîäíîé çàäà÷è ñ ïîãðåøíîñòüþ, íå ïðåâûøàþùåé
T
P
vt({et , et , ..., et}T + {1, 1, ..., 1}T ).
t=1
Îäíî èç ñàìûõ ãëàâíûõ ïðåèìóùåñòâ ýòîãî ìåòîäà âûñîêàÿ âðåìåí-
íàÿ ýåêòèâíîñòü. Ñîãëàñíî [7℄, áèòîâàÿ ñëîæíîñòü (ó÷èòûâàþùàÿ òðóäîåìêîñòü îïåðàöèé íàä ÷èñëàìè â êîìïüþòåðíîì ïðåäñòàâëåíèè) ðåøåíèÿ
çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ
T m ïåðåìåííûõ è T n íåðàâåíñòâ
ìåòîäîì âíóòðåííåé òî÷êè Êàðìàðêàðà ïðè çàäàííîé öèðîâîé òî÷íîñòè
ïðèáëèæåííîãî ðåøåíèÿ ñîñòàâëÿåò
O T 3,5 max(n3,5, m3,5)[l + log(T max(n, m))] ,
ãäå l ÷èñëî ðàçðÿäîâ, îòâîäèìûõ íà çàïèñü ÷èñëà âî âõîäíûõ äàííûõ.
Íåîáõîäèìîñòü ñîñòàâëåíèÿ íåîáõîäèìîé íàì ÇËÏ è îêðóãëåíèå îïòèìàëüíîãî ðåøåíèÿ ïåðåä âû÷èñëåíèåì öåëåâîé óíêöèè íå èçìåíÿþò ýòó îöåí24
êó. Òàêèì îáðàçîì, ìû ìîæåì íàéòè ïðèáëèæåííîå ðåøåíèå íàøåé çàäà÷è
çà ïîëèíîìèàëüíîå âðåìÿ.
1.2. Ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ
Òåïåðü ðàññìîòðèì ïîäõîä ê ðåøåíèþ òåðìèíàëüíîé çàäà÷è (8), äëÿ
êîòîðîãî íå òðåáóåòñÿ ñâîäèòü çàäà÷ó ê ñòàòè÷åñêîé, äèíàìè÷åñêîå ïðîãðàììèðîâàíèå.  ýòîì ïàðàãðàå ìû áóäåì ñòðîèòü ìåòîä, äàþùèé òî÷íîå
ðåøåíèå.
Ïîñêîëüêó çàäà÷à ÿâëÿåòñÿ öåëî÷èñëåííîé, îíà äèñêðåòíà è, ñ ó÷åòîì
îãðàíè÷åíèé, êîíå÷íà ïîýòîìó ìû ìîæåì ðåøèòü å¼ ìåòîäîì ïîëíîãî
ïåðåáîðà âñåõ ýëåìåíòîâ: ïîñëåäîâàòåëüíî ñòðîèòü âñå öåïî÷êè âåêòîðîâ
èíòåíñèâíîñòåé, óäîâëåòâîðÿþùèå îãðàíè÷åíèÿì, à çàòåì èç âñåõ öåïî÷åê
âûáèðàòü òó, êîòîðàÿ ìàêñèìèçèðóåò öåëåâóþ óíêöèþ. Îäíàêî î÷åâèäíî, ÷òî òàêîé ìåòîä áóäåò êðàéíå íåýåêòèâåí è ïîòîìó íåïðèãîäåí äëÿ
ïðàêòè÷åñêîãî èñïîëüçîâàíèÿ. Âîçíèêàåò ïîòðåáíîñòü â ñîêðàùåíèè êîëè÷åñòâà ïåðåáèðàåìûõ íà êàæäîì øàãå âàðèàíòîâ, à òàêæå îòñå÷åíèÿ öåïî÷åê, çàâåäîìî íå âåäóùèõ ê îïòèìàëüíîìó ðåøåíèþ. Äëÿ ýòîãî ìîæíî
èñïîëüçîâàòü ïîíÿòèå Ïàðåòî-îïòèìàëüíîñòè.
Îïðåäåëåíèå.
Âåêòîð x ∈ X
Ïàðåòî-îïòèìàëåí íà ìíîæåñòâå X , åñëè
íå ñóùåñòâóåò òàêîãî y ∈ X , ÷òî y > x. Ìíîæåñòâî Ïàðåòî-îïòèìàëüíûõ
íà X âåêòîðîâ îáîçíà÷èì P (X).
Ñëåäóþùèå óòâåðæäåíèÿ êàñàòåëüíî Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ
èíòåíñèâíîñòåé ëÿãóò â îñíîâó îïèñûâàåìîãî â ýòîì ðàçäåëå ìåòîäà äëÿ
òåðìèíàëüíîé çàäà÷è.
Ñóùåñòâóåò îïòèìàëüíîå ðåøåíèå òåðìèíàëüíîé çàäà÷è, ñîñòîÿùåå èç âåêòîðîâ èíòåíñèâíîñòåé, êàæäûé èç êîòîðûõ
Ïàðåòî-îïòèìàëåí íà ìíîæåñòâå äîñòèæèìûõ çíà÷åíèé íà ñîîòâåòñòâóþùåì øàãå.
Óòâåðæäåíèå 6.
25
Äîêàçàòåëüñòâî.
×èñëî äîñòèæèìûõ çíà÷åíèé âåêòîðà zT êîíå÷íî, à çíà-
÷èò, ñóùåñòâóåò êàê ìèíèìóì îäíî Ïàðåòî-îïòèìàëüíîå çíà÷åíèå. Öåëåâóþ óíêöèþ ìîæíî âûðàçèòü êàê ëèíåéíóþ êîìáèíàöèþ êîìïîíåíòîâ zT
ñ íåîòðèöàòåëüíûìè êîýèöèåíòàìè, ïîýòîìó ìàêñèìèçèðóþùèì öåëåâóþ óíêöèþ áóäåò êàêîé-òî èç Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ. Îáîçíà÷èì
ýòîò Ïàðåòî-îïòèìàëüíûé âåêòîð êàê zeT .
Òåïåðü, íà÷èíàÿ îò T è äâèãàÿñü â îáðàòíîì íàïðàâëåíèè, ñòðîèì îï-
òèìàëüíîå ðåøåíèå zet , t = 1, T .
Ïóñòü äîñòèæèìûé zet ÿâëÿåòñÿ Ïàðåòî-îïòèìàëüíûì äîêàæåì, ÷òî
ñðåäè äîñòèæèìûõ çíà÷åíèé zt−1 ñóùåñòâóåò Ïàðåòî-îïòèìàëüíûé âåêòîð,
êîòîðûé ìîæíî âêëþ÷èòü â íàøå ðåøåíèå. zet ÿâëÿåòñÿ äîñòèæèìûì, ïîýòî-
∗
∗
ìó ñóùåñòâóåò íåêîòîðûé zt−1
, äëÿ êîòîðîãî zet A 6 zt−1
B . Åñëè îí Ïàðåòî-
∗
. Èíà÷å â êà÷åñòâå
îïòèìàëåí, òî âêëþ÷èì åãî â íàøå ðåøåíèå: zet−1 = zt−1
∗∗
zet−1 âîçüìåì äîìèíèðóþùèé åãî Ïàðåòî-îïòèìàëüíûé âåêòîð zt−1
: ìû ìî∗∗
∗
∗∗
æåì ýòî ñäåëàòü, ò. ê. èç zt−1
> zt−1
ñëåäóåò, ÷òî zet A 6 zt−1
B.
Òàêèì îáðàçîì, ïî èíäóêöèè ìû ìîæåì ïîñòðîèòü îïòèìàëüíîå ðåøå-
íèå zet , t = 1, T , ñîñòîÿùåå èç âåêòîðîâ, Ïàðåòî-îïòèìàëüíûõ íà ìíîæåñòâå
äîñòèæèìûõ çíà÷åíèé íà ñîîòâåòñâóþùèõ øàãàõ.
Óòâåðæäåíèå 7.
Åñëè
X = X1 ∪ X2... ∪ Xk
, òî P (X)
= P (P (X1 ) ∪
P (X2 )... ∪ P (Xk ))
Äîêàçàòåëüñòâî.
Åñëè x ∈ X ïðèíàäëåæèò ê P (X), òî íå ñóùåñòâóåò y ∈
X , êîòîðûé áóäåò áîëüøå x. Ñóùåñòâóåò Xi , i = 1, k, ÷òî x ∈ Xi , ïðèòîì
y > x íå ñóùåñòâóåò íè â îäíîì Xi , ïîýòîìó x ∈ P (X1 ) ∪ P (X2)... ∪ P (Xk ).
P (X1 ) ∪ P (X2 )... ∪ P (Xk ) ÿâëÿåòñÿ ïîäìíîæåñòâîì X , è ïîýòîìó y > x
òàêæå íå ñóùåñòâóåò â P (X1 ) ∪ P (X2 )... ∪ P (Xk ), ïîýòîìó x ∈ P (P (X1 ) ∪
P (X2 )... ∪ P (Xk )). Òàêèì îáðàçîì,
P (X) ⊂ P (P (X1 ) ∪ P (X2 )... ∪ P (Xk )).
26
Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò x ∈ P (P (X1 ) ∪ P (X2 )... ∪ P (Xk )), êîòîðûé íå ïðèíàäëåæèò P (X). Òîãäà ñóùåñòâóåò òàêîé y ∈ X , ÷òî y >
x. Òàê êàê x íàõîäèòñÿ ñðåäè Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ ìíîæåñòâà
P (X1 ) ∪ P (X2 )... ∪ P (Xk ), òî y ∈
/ P (X1 ) ∪ P (X2 )... ∪ P (Xk ). Íî ïîñêîëüêó y ∈ X , òî y ïðèíàäëåæèò õîòÿ áû íåêîòîðîìó Xi , i = 1, k. Ïîýòîìó â ìíîæåñòâå ñóùåñòâóåò òàêîé z ∈ P (X1 ) ∪ P (X2 )... ∪ P (Xk ), ÷òî
z > y . Òîãäà z òàêæå áóäåò áîëüøå x, è ìû ïîëó÷àåì, ÷òî â ìíîæåñòâå
P (X1 )∪P (X2)...∪P (Xk ) ñóùåñòâóåò âåêòîð, áîëüøå Ïàðåòî-îïòèìàëüíîãî,
÷òî ïðîòèâîðå÷èò îïðåäåëåíèþ Ïàðåòî-îïòèìàëüíîãî âåêòîðà. Çíà÷èò, íàøå ïðåäïîëîæåíèå íå âåðíî è
P (P (X1 ) ∪ P (X2 )... ∪ P (Xk )) ⊂ P (X).
Òàêèì îáðàçîì, P (X) = P (P (X1 ) ∪ P (X2 )... ∪ P (Xk )).
Èç óòâåðæäåíèÿ (6) ñëåäóåò, ÷òî äëÿ ïîèñêà îïòèìàëüíîãî ðåøåíèÿ
äîñòàòî÷íî ðàññìàòðèâàòü Ïàðåòî-îïòèìàëüíûå âåêòîðû èíòåíñèâíîñòåé.
Âîçíèêàåò íîâàÿ çàäà÷à: íåîáõîäèìî íàèáîëåå ýåêòèâíî îïðåäåëÿòü òàêèå âåêòîðû.
Äîïóñòèì, ÷òî ìû çíàåì âåêòîðû, Ïàðåòî-îïòèìàëüíûå íà ìíîæåñòâå
äîïóñòèìûõ çíà÷åíèé íà øàãå t − 1, à íóæíî óçíàòü äëÿ øàãà t. àçîáüåì
çàäà÷ó íà ïîäçàäà÷è: äëÿ íà÷àëà íàéäåì âåêòîðû, Ïàðåòî-îïòèìàëüíûå
ñðåäè äîïóñòèìûõ äëÿ êàæäîãî êîíêðåòíîãî Ïàðåòî-îïòèìàëüíîãî zt−1 ,
îáúåäèíèì èõ â îäèí îáùèé ñïèñîê è âûáåðåì Ïàðåòî-îïòèìàëüíûå ñðåäè
íèõ. Òî, ÷òî òàêèì îáðàçîì áóäóò íàéäåíû âñå âåêòîðû, êîòîðûå ÿâëÿþòñÿ Ïàðåòî-îïòèìàëüíûìè íà ìíîæåñòâå äîïóñòèìûõ íà øàãå t, ñëåäóåò èç
óòâåðæäåíèÿ (7) è äîêàçàòåëüñòâà óòâåðæäåíèÿ (6).
Ïðè çàäàííîì zt−1 áóäåò ãåíåðèðîâàòü âåêòîðû zt â ïîðÿäêå, îáðàòíîì
ëåêñèêîãðàè÷åñêîìó, ò. ê. ýòî áóäåò ýåêòèâíåå ïî ñðàâíåíèþ ñ îáû÷íûì ïåðåáîðîì îò íóëåâîãî âåêòîðà. Ïîñêîëüêó ëåêñèêîãðàè÷åñêèé ïîðÿäîê ðàñøèðÿåò îòíîøåíèå > íà âåêòîðàõ (êîòîðîå ÿâëÿåòñÿ îòíîøåíèåì
27
÷àñòè÷íîãî ïîðÿäêà), òî ïðè ïåðåáîðå ìîæíî ñðàçó íà÷àòü ñîñòàâëÿòü îêîí÷àòåëüíûé ñïèñîê Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ åñëè ñãåíåðèðîâàííûé
âåêòîð íå äîìèíèðóåòñÿ íè îäíèì âåêòîðîì èç óæå ïðèñóòñòâóþùèõ â ñïèñêå, òî îí Ïàðåòî-îïòèìàëåí è åãî íóæíî â ýòîò ñïèñîê äîáàâèòü. Ê òîìó æå,
ïîñëå ãåíåðàöèè âåêòîðà {zt1 , ..., ztm−1, ztm } ìîæíî íå ðàññìàòðèâàòü âåêòîðû {zt1 , ..., ztm−1, x}, ãäå x ïðèíèìàåò çíà÷åíèÿ îò ztm − 1 äî 0, ïîñêîëüêó
îíè áóäóò çàâåäîìî ìåíüøå óæå ðàññìîòðåííîãî âåêòîðà.
Èñõîäÿ èç ðàññóæäåíèé âûøå, àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîãî ðåøåíèÿ òåðìèíàëüíîé çàäà÷è îïòèìèçàöèè ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ âûãëÿäèò ñëåäóþùèì îáðàçîì:
1. Çàäàåì t = 1. Â ïåðâûé ìîìåíò âðåìåíè ó íàñ íåò âåêòîðîâ zt−1 ,
ïîýòîìó âìåñòî zt−1 B íà ñëåäóþùåì øàãå èñïîëüçóåì âåêòîð y0 ;
2.
åíåðèðóåì âåêòîð zt , íàèáîëüøèé â ñìûñëå ëåêñèêîãðàè÷åñêîãî ïîðÿäêà, óäîâëåòâîðÿþùèé îãðàíè÷åíèþ zt A 6 zt−1 B : óñòàíàâëèâàåì
ýëåìåíòû, íà÷èíàÿ ñ ïåðâîãî, â ìàêñèìàëüíî äîïóñòèìîå çíà÷åíèå
(ñ ó÷åòîì óæå óñòàíîâëåííûõ ýëåìåíòîâ). Äîáàâëÿåì åãî â ñïèñîê
Ïàðåòî-îïòèìàëüíûõ ñðåäè äîïóñòèìûõ äëÿ òåêóùåãî zt−1 ;
3. Â ïîñëåäíåì ñãåíåðèðîâàííîì âåêòîðå íàõîäèì ñðåäè èíäåêñîâ ñ 1 ïî
m − 1 íàèáîëüøèé èíäåêñ, ñîîòâåòñòâóþùèé íåíóëåâîìó ýëåìåíòó:
åñëè òàêîãî èíäåêñà íåò, òî ïåðåõîäèì ê øàãó 5, èíà÷å æå îáîçíà÷èì
ýòîò èíäåêñ êàê i è ïåðåõîäèì ê øàãó 4;
4.
åíåðèðóåì íîâûé âåêòîð íà îñíîâå ïðåäûäóùåãî: óìåíüøàåì zti íà 1
è çàäàåì íîâûå çíà÷åíèÿ ýëåìåíòàì ñ èíäåêñàìè áîëüøå ÷åì i: íà÷èíàÿ ñ i+1-ãî, óñòàíàâëèâàåì ýëåìåíòû â ìàêñèìàëüíî äîïóñòèìîå çíà÷åíèå (ñ ó÷åòîì óæå óñòàíîâëåííûõ ýëåìåíòîâ). Ïðîâåðÿåì, äîìèíèðóåòñÿ ëè îí êàêèì-íèáóäü âåêòîðîì èç ñïèñêà Ïàðåòî-îïòèìàëüíûõ
ñðåäè äîïóñòèìûõ äëÿ òåêóùåãî zt−1 : åñëè íåò, òî äîáàâëÿåì åãî â
28
ýòîò ñïèñîê. Ïåðåõîäèì ê øàãó 3;
5. Áåðåì ñëåäóþùèé âåêòîð zt−1 èç ñïèñêà Ïàðåòî-îïòèìàëüíûõ â ìîìåíò t − 1 è ïåðåõîäèì ê øàãó 2. Åñëè òàêèõ âåêòîðîâ áîëüøå íå
îñòàëîñü (èëè t = 1 è ñïèñêà äëÿ t − 1 íåò), òî ïåðåõîäèì ê øàãó 6;
6. Ñîáèðàåì ñïèñêè Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ ñðåäè äîïóñòèìûõ
äëÿ êàæäîãî zt−1 â îäèí ñïèñîê, ïðè ýòîì äëÿ êàæäîãî âåêòîðà ñîõðàíÿåì ññûëêó íà zt−1 , äëÿ êîòîðîãî îí ÿâëÿåòñÿ äîïóñòèìûì (ïðè
êîíëèêòå âûáèðàåì ëþáîé). Ïðè ñëèÿíèè ñîðòèðóåì ñïèñîê â ïîðÿäêå, îáðàòíîì ëåêñèêîãðàè÷åñêîìó;
7. Èñïîëüçóåì àëãîðèòì òèïà ¾ðåøåòà Ýðàòîñåíà¿, ÷òîáû â ïîëó÷åííîì ñïèñêå îòîáðàòü Ïàðåòî-îïòèìàëüíûå: âûáèðàåì â êà÷åñòâå
¾îïîðíîãî¿ ïåðâûé âåêòîð èç ñïèñêà è óäàëÿåì âñå ïîñëåäóþùèå âåêòîðà, êîòîðûå ìåíüøå åãî. Çàòåì â êà÷åñòâå ¾îïîðíîãî¿ âûáèðàåì
ñëåäóþùèé âåêòîð â ñïèñêå è ñíîâà óäàëÿåì âñå ïîñëåäóþùèå âåêòîðà, êîòîðûå ìåíüøå åãî, è òàê äàëåå, ïîêà íîâûé ¾îïîðíûé¿ íå
îêàæåòñÿ ïîñëåäíèì â ñïèñêå;
8. Åñëè t = T , ïåðåõîäèì ê øàãó 9. Èíà÷å óâåëè÷èâàåì t íà 1, ïîëó÷åííûé íà ïðåäûäóùåì øàãå ñïèñîê åñòü íå ÷òî èíîå êàê ñïèñîê Ïàðåòîîïòèìàëüíûõ âåêòîðîâ â ìîìåíò t − 1, áåðåì èç íåãî ïåðâûé âåêòîð
zt−1 ïåðåõîäèì ê øàãó 2;
9. Ñðåäè âåêòîðîâ zT â ñïèñêå íàéäåì òîò, ÷òî ìàêñèìèçèðóåò öåëåâóþ óíêöèþ (ïðè êîíëèêòå âûáèðàåì ëþáîé). Ïî ññûëêå íàéäåì
âåêòîð zT −1 , äëÿ êîòîðîãî ýòîò ìàêñèìèçèðóþùèé ÿâëÿåòñÿ äîïóñòèìûì, çàòåì àíàëîãè÷íî ïî ññûëêå íàõîäèì âåêòîð zT −2 è òàê äàëåå äî
z1 . Íàéäåííûå âåêòîðà zt , t = 1, T ÿâëÿþòñÿ èñêîìûì îïòèìàëüíûì
ðåøåíèåì.
29
Ïðåäñòàâëåííûé àëãîðèòì ðåàëèçóåò ¾äèíàìè÷åñêîå ïðîãðàììèðîâàíèå âïåðåä¿ äëÿ äàííîé çàäà÷è òàêîé ïîäõîä ïðåäïî÷òèòåëüíåé ¾äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ íàçàä¿, ïîñêîëüêó íà÷àëüíîå ñîñòîÿíèå ñèñòåìû (âåêòîð íà÷àëüíûõ çàïàñîâ y0 ) çàäàí åäèíñòâåííûì îáðàçîì, â îòëè÷èå
îò êîíå÷íîãî ñîñòîÿíèÿ, õàðàêòåðèçóåìîãî äëÿ ðàñòóùåé ìîäåëè äîâîëüíî
áîëüøèì ìíîæåñòâîì äîïóñòèìûõ âåêòîðîâ èíòåíñèâíîñòåé íà ïîñëåäíåì
øàãå.
Îöåíèì âðåìåííóþ ñëîæíîñòü ìåòîäà. Ïóñòü T > 1. Ïðè t = 1 ïåðåáîð
âåêòîðîâ îñóùåñòâëÿåòñÿ çà O(L1m−1 R), ãäå R ìàêñèìàëüíîå ÷èñëî íåíóëåâûõ ýëåìåíòîâ â ñòðîêå ìàòðèöû A (ò. ê. ìàòðèöà ðàçðåæåíà, òî R << n),
L1 ìàêñèìàëüíîå äîïóñòèìîå çíà÷åíèå ýëåìåíòà âåêòîðà èíòåíñèâíîñòåé
íà ïåðâîì øàãå, ðàâíîå max min y0j /aij .
i
j
Ïðè t îò 2 äî T ìû äëÿ íà÷àëà âû÷èñëÿåì zt−1 B çà O(Cn), ãäå C
ìàêñèìàëüíîå ÷èñëî íåíóëåâûõ ýëåìåíòîâ â ñòîëáöå ìàòðèöû B (ò. ê. ìàòðèöà ðàçðåæåíà, òî C << m). Çàòåì, êàê è íà ïåðâîì øàãå, ïåðåáèðàåì
âåêòîðû, íî óæå äëÿ êàæäîãî Ïàðåòî-îïòèìàëüíîãî âåêòîðà íà ïðåäûäóùåì øàãå, ïîýòîìó ïåðåáîð îñóùåñòâëÿåòñÿ çà O(Ltm−1 RPt−1 ), ãäå Pt−1
êîëè÷åñòâî Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ íà øàãå t − 1, à Lt ìàêñèìàëüíîå äîïóñòèìîå çíà÷åíèå ýëåìåíòà âåêòîðà èíòåíñèâíîñòåé íà øàãå
t. Äàëåå ïîëó÷åííûå âåêòîðû îáúåäèíÿåì â îäèí ñïèñîê, ïðè ýòîì âðåìÿ
íà îáúåäèíåíèå ëèíåéíî çàâèñèò îò êîëè÷åñòâà âåêòîðîâ âî âñåõ ñïèñêàõ,
ýòî êîëè÷åñòâî ìîæíî ãðóáî îöåíèòü ñâåðõó îáùèì ÷èñëîì ïåðåáèðàåìûõ
âåêòîðîâ, îòêóäà ïîëó÷àåì îöåíêó âðåìåíè ñëèÿíèÿ O(Ltm−1 Pt−1 ). Âðåìÿ
íàõîæäåíèÿ Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ èç îáùåãî ñïèñêà ìîæíî îöåíèòü êàê O(Ltm−1 Pt−1 Pt ), ïîñêîëüêó òî÷íî áóäåò ìåíüøå âðåìåíè ñðàâíåíèÿ
êàæäîãî âåêòîðà îáùåãî ñïèñêà ñ êàæäûì Ïàðåòî-îïòèìàëüíûì.
Ïîñëå ïîëó÷åíèÿ ñïèñêà Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ íà øàãå T ìû
èùåì âåêòîð, ìàêñèìèçèðóþùèé öåëåâóþ óíêöèþ çà O(CnPT ), à ïîòîì
çà O(T ) íàõîäèì îïòèìàëüíîå ðåøåíèå.
30
Ïóñòü L = max Lt , P = max Pt , òîãäà îáùàÿ îöåíêà âðåìåíè èñïîëíåíèÿ
t
t
áóäåò èìåòü âèä:
O(Lm−1R + (T − 1)(Cn + Lm−1RP + Lm−1P + Lm−1P 2 ) + CnP + T ) =
= O((T − 1)Lm−1P (R + P ) + Cn(T + P )).
Èç-çà íåñêîëüêî ãðóáûõ îöåíîê îòäåëüíûõ ÷àñòåé àëãîðèòìà è èãóðèðóþùèõ âåëè÷èí (à òàêæå òîãî àêòà, ÷òî L è P òðóäíî îöåíèòü äî
íà÷àëà ðàáîòû àëãîðèòìà), ïîëó÷åííàÿ îöåíêà íå ãîäèòñÿ äëÿ âû÷èñëåíèÿ
ïðèìåðíîãî âðåìåíè íàõîæäåíèÿ ðåøåíèÿ ðåàëèçàöèåé àëãîðèòìà, îäíàêî
îòðàæàåò, íàïðèìåð, ýêñïîíåíöèàëüíóþ çàâèñèìîñòü îò ðàçìåðà âõîäíûõ
äàííûõ. Íåñìîòðÿ íà òî, ÷òî îðìàëüíî èç îöåíêè ñëåäóåò ëèíåéíàÿ çàâèñèìîñòü îò T , äëÿ ðàñòóùèõ ìîäåëåé âåêòîðà èíòåíñèâíîñòåé ñ êàæäûì
øàãîì ðàñòóò â ãåîìåòðè÷åñêîé ïðîãðåññèè, ÷òî ïðèâîäèò ê áûñòðîìó ðîñòó L, êîòîðûé â îöåíêå èãóðèðóåò êàê îñíîâàíèå ñòåïåíè, ïîýòîìó äëÿ
áîëüøèõ T âûïîëíåíèå àëãîðèòìà ìîæåò çàíÿòü äîâîëüíî áîëüøîå êîëè÷åñòâî âðåìåíè.
31
ëàâà 2. åàëèçàöèÿ ìåòîäîâ è èõ
ñðàâíèòåëüíûé àíàëèç
 ðàìêàõ äàííîé âûïóñêíîé êâàëèèêàöèîííîé ðàáîòû îñóùåñòâëåíà
ïðîãðàììíàÿ ðåàëèçàöèÿ îïèñàííûõ â ïðåäûäóùåì ðàçäåëå ìåòîäîâ íà
ÿçûêå C++. Êàê ÿçûê ïðîãðàììèðîâàíèÿ âûñîêîãî óðîâíÿ, C++ ïîääåðæèâàåò íåîáõîäèìûé óðîâåíü àáñòðàêöèè äëÿ óäîáíîé ïëàòîðìîíåçàâèñèìîé ðàçðàáîòêè àëãîðèòìîâ ðàññìàòðèâàåìûõ ìåòîäîâ, ïðè ýòîì ïðåäîñòàâëÿÿ áîëüøîå êîëè÷åñòâî ñòàíäàðòíûõ ñòðóêòóð äàííûõ, äîïîëíèòåëüíûõ ïîäêëþ÷àåìûõ áèáëèîòåê àëãåáðû ìàòðèö è ëèíåéíîãî ïðîãðàììèðîâàíèÿ, à òàêæå îáåñïå÷èâàÿ âûñîêîå âðåìÿ èñïîëíåíèÿ ñêîìïèëèðîâàííîé
ïðîãðàììû.
2.1. Ïðîãðàììíàÿ ðåàëèçàöèÿ
Ýòîò ïàðàãðà ïîñâÿùåí îïèñàíèþ ñòðóêòóðû ïðîãðàììíîãî êîäà, ðåàëèçîâàííûõ ìåòîäîâ è èñïîëüçîâàííîé ïîäêëþ÷àåìîé áèáëèîòåêè. Ñ ÷àñòè÷íûì ëèñòèíãîì êîäà ìîæíî îçíàêîìèòüñÿ â Ïðèëîæåíèè.
 îñíîâå ðåàëèçàöèè ëåæèò êëàññ NMProblem, ïðåäíàçíà÷åííûé äëÿ
ñîçäàíèÿ îáúåêòîâ òèïà çàäà÷è îïòèìèçàöèè öåëî÷èñëåííîé ìîäåëè Íåéìàíà. Íåïîñðåäñòâåííî ìåòîäû îïòèìèçàöèè ðåàëèçîâàíû publi
-ìåòîäàìè
solveByContinualizationMethod() è solveByDynami
Programming(), ïðè
ýòîì ïîñëåäíÿÿ çàäåéñòâóåò ðÿä private-ìåòîäîâ.
Äëÿ ðåøåíèÿ çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ â ìåòîäå êîíòèíóàëèçàöèè èñïîëüçóþòñÿ âîçìîæíîñòè áèáëèîòåêè Clp (COIN-OR linear
programming). Ýòî ïðîåêò ñ îòêðûòûì èñõîäíûì êîäîì äëÿ ðåøåíèÿ çàäà÷
ëèíåéíîãî ïðîãðàììèðîâàíèÿ, íàïèñàííûé íà C++. Áèáëèîòåêà ïîääåðæèâàåò ðàáîòó ñ ðàçðåæåííûìè ìàòðèöàìè (÷òî ÿâëÿåòñÿ êðàéíå ïîëåçíûì ñâîéñòâîì, ïîñêîëüêó ìàòðèöû A è B â ìîäåëè Íåéìàíà ïî ñâîåé
32
ïðèðîäå ÿâëÿþòñÿ ðàçðåæåííûìè), ïðè÷åì áèáëèîòåêà ñîäåðæèò îòäåëüíûé êëàññ CoinPa
kedMatrix äëÿ ðàçðåæåííûõ ìàòðèö [8℄, ÷òî ïîçâîëÿåò
èñïîëüçîâàòü åå â ðåàëèçàöèè íå òîëüêî ìåòîäà êîíòèíóàëèçàöèè, íî è ìåòîäà äèíàìè÷åñêîãî ïðîãðàìèðîâàíèÿ.
Òàêèì îáðàçîì, ñóòü ðàáîòû solveByContinualizationMethod() çàêëþ÷àåòñÿ â ïðåîáðàçîâàíèè ñâîéñòâ îáúåêòà êëàññà NMProblem â îðìàò
ñòàòè÷åñêîé çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ, îïðåäåëåííîé â ïàðàãðàå 1.1, ðåøåíèè åå ïðè ïîìîùè ñðåäñòâ áèáëèîòåêè Clp è ñîõðàíåíèè
çíà÷åíèÿ îïòèìàëüíîãî ðåøåíèÿ è öåëåâîé óíêöèè. Äëÿ ðåøåíèÿ ÇËÏ èñïîëüçóåì áèáëèîòå÷íûé êëàññ ClpPredi
torCorre
tor, ïðèìåíÿþùèé ìåòîä ïðîãíîçà è êîððåêöèè Ìåõðîòðà îäíó èç ðåàëèçàöèé ìåòîäà âíóòðåííåé òî÷êè, øèðîêî èñïîëüçóåìóþ íà ïðàêòèêå.  ñðåäíåì äëÿ íàõîæäåíèÿ
ðåøåíèÿ åìó òðåáóåòñÿ ïðèìåðíî íà 35-50% ìåíüøå øàãîâ, ÷åì àëãîðèòìó
Êàðìàðêàðà [9℄.
Ìåòîä solveByDynami
Programming() ðåàëèçóåò àëãîðèòì, ïðèâåäåííûé â ïàðàãðàå 1.2. Äëÿ õðàíåíèÿ Ïàðåòî-îïòèìàëüíûõ íà øàãå âåêòîðîâ
èñïîëüçóåòñÿ ñïèñîê èç îáúåêòîâ ñïåöèàëüíîé ñòðóêòóðû Ve
torAndParent
â ïîëå elem ýòîé ñòðóêòóðû õðàíèòñÿ óêàçàòåëü íà ìàññèâ ýëåìåíòîâ
âåêòîðà, à â ïîëå parent õðàíèòñÿ ññûëêà íà Ïàðåòî-îïòèìàëüíûé íà
ïðåäûäóùåì øàãå âåêòîð, äëÿ êîòîðîãî âåêòîð ñî çíà÷åíèÿìè èç elem
ÿâëÿåòñÿ äîïóñòèìûì. Â ñâîåé ðàáîòå ìåòîä èñïîëüçóåò äðóãèå ìåòîäû: fillParetoOptimalVe
torsList() äëÿ ñîñòàâëåíèÿ ñïèñêà Ïàðåòîîïòèìàëüíûõ âåêòîðîâ èç äîïóñòèìûõ äëÿ êîíêðåòíîãî çíà÷åíèÿ âåêòîðà èíòåíñèâíîñòåé íà ïðåäûäóùåì øàãå, maximizeVe
tor() äëÿ ïîñòðîåíèÿ ìàêñèìàëüíîãî â ëåêñèêîãðàè÷åñêîì ñìûñëå âåêòîðà èíòåíñèâíîñòåé ñ ó÷åòîì ìàòðèöû êîýèöèåíòîâ è âåêòîðà îãðàíè÷åíèé,
addIfNotDominated() äëÿ äîáàâëåíèÿ â ñïèñîê íåäîìèíèðóåìûõ âåêòîðîâ, transferToGeneralList() äëÿ ïåðåíîñà âåêòîðîâ èç ñïèñêà äëÿ êîíêðåòíîãî âåêòîðà íà ïðåäûäóùåì øàãå â îáùèé ñïèñîê Ïàðåòî-îïòèìàëüûõ
33
âåêòîðîâ íà øàãå.
2.2. Ñðàâíèòåëüíûé àíàëèç
Áëàãîäàðÿ ïðîãðàììíîé ðåàëèçàöèè ìû ìîæåì ïðîâåñòè áîëåå äåòàëüíûé àíàëèç ìåòîäîâ îïòèìèçàöèè, ïðèìåíèâ èõ ê êîíêðåòíûì çàäà÷àì.
Äëÿ ýòîãî ñãåíåðèðóåì íàáîðû çàäà÷ òåðìèíàëüíîé îïòèìèçàöèè ñ ðàçëè÷íûìè ïàðàìåòðàìè.  êà÷åñòâå ïàðàìåòðîâ áóäóò âûñòóïàòü òàêèå âåëè÷èíû êàê ðàçìåðíîñòü (âåëè÷èíû m è n) è ÷èñëî ðàññìàòðèâàåìûõ ïðîìåæóòêîâ âðåìåíè T . Äëÿ ïîñòðîåíèÿ ãðàèêîâ ïî ðàññ÷èòàííûì äëÿ ñãåíåðèðîâàííûõ çàäà÷ äàííûì áóäåò èñïîëüçîâàòü óòèëèòó gnuplot [10℄.
Ïåðå÷èñëèì ïàðàìåòðû, ïî êîòîðûì áóäåì ñðàâíèâàòü ðàáîòó ìåòîäîâ.
Âî-ïåðâûõ, ïîëó÷àåìîå ìåòîäàìè çíà÷åíèå öåëåâîé óíêöèè íå òîëüêî ïîòîìó ÷òî åå ìàêñèìèçàöèÿ ÿâëÿåòñÿ öåëüþ îïòèìèçàöèîííîé çàäà÷è,
íî è ïîòîìó ÷òî îíà ÿâëÿåòñÿ ëèíåéíîé êîìáèíàöèåé çíà÷åíèé ýëåìåíòîâ
âåêòîðà èíòåíñèâíîñòåé íà øàãå T . Âî-âòîðûõ, âðåìÿ èñïîëíåíèÿ òàêèì
îáðàçîì, ìîæíî ïðîâåðèòü îöåíêè âðåìåííîé ýåêòèâíîñòè íà ïðàêòèêå.
Íåìàëîâàæíûì ïàðàìåòðîì çàäà÷è, êîòîðûé òàêæå ñòîèò îòìåòèòü, ÿâëÿåòñÿ ðîñò ìîäåëè ýòî ïîíÿòèå îïðåäåëÿåò, êàê óâåëè÷èâàåòñÿ îïòèìàëüíûé âåêòîð èíòåíñèâíîñòåé ñ òå÷åíèåì âðåìåíè. Ýòà âåëè÷èíà íåïîñðåäñòâåííî âëèÿåò íà èíàëüíûé âåêòîð èíòåíñèâíîñòåé, à ñëåäîâàòåëüíî, è íà çíà÷åíèå öåëåâîé óíêöèè. Ïðè îäèíàêîâûõ äëÿ ãåíåðèðóåìûõ
çàäà÷ ïîðÿäêàõ çíà÷åíèé ýëåìåíòîâ ñîîòâåòñòâóþùèõ ìàòðèö è âåêòîðîâ
(A, B , y0 , c) ðàçíèöà â îïòèìàëüíûõ çíà÷åíèÿõ öåëåâîé óíêöèè áóäåò
âûðàæàòü ðàçíèöó ðîñòà ìîäåëåé. Ïîýòîìó îïòèìàëüíîå çíà÷åíèå öåëåâîé
óíêöèè â àíàëèçå áóäåò èãóðèðîâàòü íå òîëüêî êàê çàâèñèìûé ïàðàìåòð, íî è êàê íåçàâèñèìûé.
Èòàê, íà ðèñóíêå 1 ìû âèäèì ãðàèê çàâèñèìîñòè âûäàâàåìûõ ìåòîäàìè çíà÷åíèé öåëåâîé óíêöèè îò ðàçìåðà âõîäíîé çàäà÷è (äðóãèå ïàðà34
6x108
continualization
dyn. programming
lin. programming
objective function value
5x108
4x108
3x108
2x108
1x108
0
4
6
8
10
12
14
size (m and n)
èñ. 1:
ðàèê çàâèñèìîñòè çíà÷åíèé öåëåâîé óíêöèè, ïîëó÷åííûõ
ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ìåòîäîì êîíòèíóàëèçàöèè è ñâåäåíèåì ê ÇËÏ îòêàçîì îò öåëî÷èñëåííûõ îãðàíè÷åíèé, îò
ðàçìåðíîñòè çàäà÷è (âåëè÷èí
m, n). T = 5,
ëåâûõ óíêöèé äëÿ çàäà÷ èìååò ïîðÿäîê
îïòèìàëüíîå çíà÷åíèå öå-
108
1
relative error
0.1
0.01
continualization error
lyn. programming error
0.001
4
6
8
10
12
14
size (m and n)
èñ. 2:
ðàèê çàâèñèìîñòè îòíîñèòåëüíîé ïîãðåøíîñòè çíà÷åíèé öåëåâîé óíêöèè, ïîëó÷åííûõ ìåòîäîì êîíòèíóàëèçàöèè è ñâåäåíèåì ê
ÇËÏ îòêàçîì îò öåëî÷èñëåííûõ îãðàíè÷åíèé, îò ðàçìåðíîñòè çàäà÷è
(âåëè÷èí
m, n). T = 5,
çàäà÷ èìååò ïîðÿäîê
îïòèìàëüíîå çíà÷åíèå öåëåâûõ óíêöèé äëÿ
108
35
ìåòðû çàèêñèðîâàíû: T = 5, à îïòèìàëüíîå çíà÷åíèå öåëåâîé óíêöèè
èìååò ïîðÿäîê 108), êàæäàÿ òî÷êà êîòîðîãî ïðåäñòàâëÿåò óñðåäíåííûå äëÿ
10 çàäà÷ çíà÷åíèÿ. Òðè ëèíèè íà ãðàèêå îáîçíà÷àþò çíà÷åíèÿ öåëåâîé
óíêöèè, ïîëó÷åííûå ìåòîäîì êîíòèíóàëèçàöèè, ìåòîäîì äèíàìè÷åñêîãî
ïðîãðàììèðîâàíèÿ è ñâåäåíèåì ê çàäà÷å ëèíåéíîãî ïðîãðàììèðîâàíèÿ ïóòåì îòáðàñûâàíèÿ îãðàíè÷åíèÿ íà öåëî÷èñëåííîñòü.
Çíà÷åíèå, ïîëó÷åííîå ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ÿâëÿåòñÿ òî÷íûì (âåðíåå, èìåþùèì ïîãðåøíîñòü, íå ïðåâûøàþùóþ îøèáêó
ïðè âû÷èñëåíèÿõ ÷èñåë ñ ïëàâàþùåé òî÷êîé), îíî è èñïîëüçîâàëîñü äëÿ
âûáîðà çàäà÷ îäíîãî ïîðÿäêà, ïîýòîìó íà ãðàèêå íàñ â ïåðâóþ î÷åðåäü
èíòåðåñóþò çíà÷åíèÿ, ïîëó÷åííûå äâóìÿ äðóãèìè ìåòîäàìè, à òî÷íåå íàñêîëüêî ýòè çíà÷åíèÿ îòëè÷àþòñÿ îò çíà÷åíèé, ïîëó÷åííûõ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.
Çíà÷åíèÿ äëÿ ÇËÏ áåç îãðàíè÷åíèé íà öåëî÷èñëåííîñòü, êàê âèäíî íà
ãðàèêå, ìîãóò ïðåâûøàòü ìàêñèìàëüíîå çíà÷åíèå öåëåâîé óíêöèè ýòî
ïðîèñõîäèò èç-çà òîãî, ÷òî âåêòîðà èíòåíñèâíîñòåé íà ïîñëåäíåì øàãå ìîãóò ïðèíèìàòü íåäîïóñòèìûå äëÿ èñõîäíîé çàäà÷è çíà÷åíèÿ, è èìåííî ïîýòîìó ìû íå ðàññìàòðèâàëè ýòîò ìåòîä. Îäíàêî ýòè äàííûå ìîæíî ðàññìàòðèâàòü êàê âåðõíþþ îöåíêó îïòèìàëüíîãî çíà÷åíèÿ öåëåâîé óíêöèè
äëÿ íàøåé çàäà÷è.
àñòóùàÿ â ãåîìåòðè÷åñêîé ïðîãðåññèè îøèáêà ìåòîäà êîíòèíóàëèçàöèè ïðèâîäèò ê òîìó, ÷òî ïîãðåøíîñòü çíà÷åíèÿ öåëåâîé óíêöèè äëÿ ýòîãî ìåòîäà ìîæåò äîñòèãàòü òåõ æå ïîðÿäêîâ, ÷òî è ñàìî çíà÷åíèå öåëåâîé
óíêöèè. Òåì íå ìåíåå, ýòè äàííûå ìîæíî èñïîëüçîâàòü êàê íèæíþþ îöåíêó, è ê òîìó æå âûâîäèìûå âåêòîðû èíòåíñèâíîñòåé áóäóò ïðèíàäëåæàòü
äîïóñòèìîìó ìíîæåñòâó.
àññìîòðèì òàêæå ãðàèê íà ðèñóíêå 2, ãäå íà îñè îðäèíàò â ëîãàðèìè÷åñêîì ìàñøòàáå òåïåðü îòîáðàæåíà îòíîñèòåëüíàÿ ïîãðåøíîñòü ïðèáëèæåííûõ ìåòîäîâ. Ìû âèäèì ñëàáóþ çàâèñèìîñòü ïîãðåøíîñòåé îò ðàç36
ìåðíîñòè êóäà áîëüøå íà çíà÷åíèå îøèáêè âëèÿåò ñàìî îïòèìàëüíîå
çíà÷åíèå öåëåâîé óíêöèè. Òåì íå ìåíåå, ìîæíî çàìåòèòü íåáîëüøîé ðîñò
ïîãðåøíîñòè ÇËÏ ïðè ðîñòå ðàçìåðíîñòè.
Òåïåðü ðàññìîòðèì ãðàèê íà ðèñóíêå 3. Íà îñè àáñöèññ âñå òàê æå
ðàñïîëîæåíà ðàçìåðíîñòü, à íà îñè îðäèíàò â ëîãàðèìè÷åñêîì ìàñøòàáå òåïåðü âðåìÿ ðàáîòû ìåòîäîâ êîíòèíóàëèçàöèè è äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ. Çäåñü çàâèñèìîñòü îò ðàçìåðíîñòè áîëåå ÿðêî âûðàæåíà,
îñîáåííî äëÿ ìåòîäà êîíòèíóàëèçàöèè ãðàèê ïîäòâåðæäàåò ñòåïåííóþ
çàâèñèìîñòü îò ðàçìåðà, ïóñòü è ñ ÿâíî ìåíüøèì ïîêàçàòåëåì. Âðåìÿ âûïîëíåíèÿ ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ íà ïîðÿäêè âûøå, íî
çàâèñèìîñòü îò ðàçìåðíîñòè ñëàáåå òðóäíî ñêàçàòü, ñòåïåííàÿ îíà èëè
ëèíåéíàÿ. Óêàçàííàÿ â îöåíêå ýêñïîíåíöèàëüíàÿ çàâèñèìîñòü íàïèñàíà â
ðàñ÷åòå íà ïî÷òè ïîëíûé ïåðåáîð äîïóñòèìûõ âåêòîðîâ èíòåíñèâíîñòåé íà
êàæäîì øàãå ïðè ïîèñêå Ïàðåòî-îïòèìàëüíûõ, ÷åãî â ñðåäíåì ñëó÷àå íå
ïðîèñõîäèò.
Òåïåðü èññëåäóåì çàâèñèìîñòü îò T . Ñãåíåðèðóåì 10 çàäà÷ ñ m = n = 5
100
continualization
dyn. programming
time, sec
10
1
0.1
0.01
4
6
8
10
12
14
size (m and n)
èñ. 3:
ðàèê çàâèñèìîñòè âðåìåíè âûïîëíåíèÿ ìåòîäîâ êîíòèíóàëèçàöèè è äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ îò ðàçìåðíîñòè çàäà÷è
(âåëè÷èí
m, n). T = 5,
çàäà÷ èìååò ïîðÿäîê
îïòèìàëüíîå çíà÷åíèå öåëåâûõ óíêöèé äëÿ
108
37
1
continualization
dyn. programming
lin. programming
objective function value
9
8
1x107
1x106
100000
10000
1000
1
6
7
8
9
number of time intervals (T)
èñ. 4:
ðàèê çàâèñèìîñòè çíà÷åíèé öåëåâîé óíêöèè, ïîëó÷åííûõ ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, ìåòîäîì êîíòèíóàëèçàöèè è ñâåäåíèåì ê ÇËÏ îòêàçîì îò öåëî÷èñëåííûõ îãðàíè÷åíèé,
îò ÷èñëà ðàññìàòðèâàåìûõ âðåìåííûõ ïðîìåæóòêîâ (âåëè÷èíû
m = n = 5,
ïîðÿäîê
T ).
îïòèìàëüíîå çíà÷åíèå öåëåâûõ óíêöèé äëÿ çàäà÷ èìååò
106
äëÿ
T =5
10
continualization error
lyn. programming error
relative error
1
0.1
0.01
0.001
1
2
3
4
5
6
7
8
9
10
number of time intervals (T)
èñ. 5:
ðàèê çàâèñèìîñòè îòíîñèòåëüíîé ïîãðåøíîñòè çíà÷åíèé öåëåâîé óíêöèè, ïîëó÷åííûõ ìåòîäîì êîíòèíóàëèçàöèè è ñâåäåíèåì ê
ÇËÏ îòêàçîì îò öåëî÷èñëåííûõ îãðàíè÷åíèé, îò ÷èñëà ðàññìàòðèâàåìûõ âðåìåííûõ ïðîìåæóòêîâ (âåëè÷èíû
T ). m = n = 5,
çíà÷åíèå öåëåâûõ óíêöèé äëÿ çàäà÷ èìååò ïîðÿäîê
38
106
îïòèìàëüíîå
äëÿ
T =5
è îïòèìàëüíûìè çíà÷åíèÿìè öåëåâûõ óíêöèé ïðè T = 5 ïîðÿäêà 106 , è
áóäåì èõ ðåøàòü, èçìåíÿÿ T . Ñðåäíåå çíà÷åíèé öåëåâûõ óíêöèé, âûäàâàåìûõ ìåòîäàìè çíà÷åíèé öåëåâûõ óíêöèé, ðàñïîëîæåíà íà îñè îðäèíàò
ðèñóíêà 4. Âèäíî, ÷òî äëÿ ðàññìàòðèâàåìûõ çàäà÷ ÿðêî âûðàæåí ýêñïîíåíöèàëüíûé ðîñò çíà÷åíèé öåëåâîé óíêöèè ñ óâåëè÷åíèåì T , òàêîé æå
ðîñò íàáëþäàåòñÿ è äëÿ çíà÷åíèé, ïîëó÷àåìûõ îò âñåõ ìåòîäîâ.
Ïðè ýòîì îòíîñèòåëüíàÿ ïîãðåøíîñòü, èçîáðàæåííàÿ íà ãðàèêå íà ðèñóíêå 5, èçìåíÿåòñÿ ïî-ðàçíîìó. Äëÿ ñâåäåíèÿ ê ÇËÏ îòáðàñûâàíèåì îãðàíè÷åíèé íà öåëî÷èñëåííîñòü ìåäëåííî íåëèíåéíî ðàñòåò (íî ýòîò ðîñò ìîæåò áûòü âûçâàí ðîñòîì çíà÷åíèé öåëåâîé óíêöèè, ïîñêîëüêó íà ïðåäûäóùåì ãðàèêå äëÿ îòíîñèòåëüíîé ïîãðåøíîñòè ýòîò ìåòîä ïîêàçûâàë çàâèñèìîñòü îò ðàçìåðíîñòè). Îòíîñèòåëüíàÿ ïîãðåøíîñòü ìåòîäà êîíòèíóàëèçàöèè íà÷èíàåò îò áëèçêîãî ê íóëþ çíà÷åíèÿ ïðè T = 1 (ìåòîäè÷åñêàÿ
ïîãðåøíîñòü â ýòîì ñëó÷àå ðàâíà 0, çíà÷èò, ýòî ïîãðåøíîñòü âû÷èñëåíèé
è îêðóãëåíèé), à çàòåì ñòàíîâèòñÿ ïî÷òè ïîñòîÿííîé âèäèìî, àáñîëþòíàÿ ïîãðåøíîñòü è çíà÷åíèå öåëåâîé óíêöèè ðàñòóò ïðèìåðíî ñ îäíîé
ñêîðîñòüþ. Âàæíî ëèøü îòìåòèòü, ÷òî òàêîé áàëàíñ ñîáëþäàåòñÿ íå äëÿ
âñåõ çàäà÷ âåêòîðà èíòåíñèâíîñòåé íà îïòèìàëüíîé òðàåêòîðèè äîëæíû
óâåëè÷èâàòüñÿ â ãåîìåòðè÷åñêîé ïðîãðåññèè è äîñòàòî÷íî áûñòðî.
Ñëåäóþùèé ãðàèê íà ëîãàðèìè÷åñêîé øêàëå äåìîíñòðèðóåò çàâèñèìîñòü âðåìåíè âûïîëíåíèÿ ìåòîäîâ îò ÷èñëà ðàññìàòðèâàåìûõ âðåìåííûõ
ïðîìåæóòêîâ (ðèñóíîê 6). Âðåìÿ ìåòîäà êîíòèíóàëèçàöèè äåìîíñòðèðóåò
ñòåïåííóþ çàâèñèìîñòü, ÷òî ñîîòâåòñòâóåò îöåíêå. Âðåìÿ ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ ðàñòåò ýêñïîíåíöèàëüíî, ÷òî íå ñîîòâåòñòâóåò
îöåíêå, êîòîðàÿ çàâèñèò îò T ëèíåéíî ñêàçûâàåòñÿ ðîñò çíà÷åíèÿ öåëåâîé
óíêöèè, êàê ýòî áûëî óïîìÿíóòî â êîììåíòàðèè ê îöåíêå.
Íà ìíîãèõ ðàññìîòðåííûõ ãðàèêàõ ìîæíî âèäåòü êîððåëÿöèþ ìåæäó çàâèñèìûìè âåëè÷èíàìè è îïòèìàëüíûì çíà÷åíèåì öåëåâîé óíêöèè
çàäà÷è. èñóíîê 7 ñîäåðæèò òî÷êè ñ çíà÷åíèÿìè äëÿ 200 çàäà÷ ñ çàèê39
100
continualization
dyn. programming
10
1
0.1
0.01
0.001
0.0001
1
2
3
4
5
6
7
8
9
10
number of time intervals (T)
èñ. 6:
ðàèê çàâèñèìîñòè âðåìåíè âûïîëíåíèÿ ìåòîäîâ êîíòèíóàëèçàöèè è äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ îò ÷èñëà ðàññìàòðèâàåìûõ âðåìåííûõ ïðîìåæóòêîâ (âåëè÷èíû
T ). m = n = 5,
çíà÷åíèå öåëåâûõ óíêöèé äëÿ çàäà÷ èìååò ïîðÿäîê
106
îïòèìàëüíîå
äëÿ
T =5
ñèðîâàííûìè ïàðàìåòðàìè m = n = 7, T = 4 è áåç îãðàíè÷åíèÿ íà ïîðÿäîê çíà÷åíèé öåëåâîé óíêöèè. Îñü àáñöèññ â ëîãàðèìè÷åñêîì ìàñøòàáå
îòîáðàæàåò çíà÷åíèå öåëåâîé óíêöèè ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, à îðäèíàò çíà÷åíèå öåëåâîé óíêöèè ìåòîäîì êîíòèíóàëèçàöèè, òîæå â ëîãàðèìè÷åñêîì ìàñòàáå.
Ñðàçó çàìåòíî áîëüøîå êîëè÷åñòâî çàäà÷, äëÿ êîòîðûõ ìåòîä êîíòèíóàëèçàöèè âûäàåò â êà÷åñòâå çíà÷åíèÿ öåëåâîé óíêöèè íîëü, â òî âðåìÿ
êàê ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ íàõîäèò íåíóëåâîé îïòèìóì
ïðè÷åì ñ ðîñòîì çíà÷åíèÿ ýòîãî îïòèìóìà ÷èñëî òàêèõ çàäà÷ óìåíüøàåòñÿ. Íóëåâîå ðåøåíèå â çàäà÷å òîæå ÿâëÿåòñÿ äîïóñòèìûì, îäíàêî âðÿä
ëè ïðèìåíèìûì â êà÷åñòâå ïîëåçíîé îöåíêè, ÷òî ãîâîðèò î òîì, ÷òî ìåòîä êîíòèíóàëèçàöèè ïðèãîäåí ïðåèìóùåñòâåííî äëÿ çàäà÷ ñ äîñòàòî÷íî
áûñòðîðàñòóùèì ðåøåíèåì. Åñëè âûíåñòè íà îñü îðäèíàò îòíîñèòåëüíóþ
ïîãðåøíîñòü ìåòîäà êîíòèíóàëèçàöèè (ðèñóíîê 8), òî âèäíî, ÷òî ÷åì áîëüøå îïòèìàëüíîå çíà÷åíèå öåëåâîé óíêöèè, òåì ìåíüøå îòíîñèòåëüíàÿ
ïîãðåøíîñòü, ïðè÷åì çàâèñèìîñòü ëèáî ñòåïåííàÿ ñ äîâîëüíî ìàëåíüêîé
40
objective function value (continualization)
1x1014
1x1012
1x1010
1x108
1x106
10000
100
1
0.01
0
100
1x106
10000
1x108
1x1010
1x1012
1x1014
objective function value (dynamic programming)
èñ. 7: Çíà÷åíèÿ öåëåâîé óíêöèè, ïîëó÷åííûå ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, è çíà÷åíèÿ äëÿ òåõ æå çàäà÷, ïîëó÷åííûå
ìåòîäîì êîíòèíóàëèçàöèè.
T = 4, m = n = 7
relative error of continualization
1
0.1
0.01
100
10000
1x106
1x108
1x1010
1x1012
1x1014
objective function value (dynamic programming)
èñ. 8: Çíà÷åíèÿ öåëåâîé óíêöèè, ïîëó÷åííûå ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, è îòíîñèòåëüíàÿ ïîãðåøíîñòü çíà÷åíèé äëÿ òåõ
æå çàäà÷, ïîëó÷åííûå ìåòîäîì êîíòèíóàëèçàöèè.
41
T = 4, m = n = 7
100000
10000
continualization
dyn. programming
1000
100
10
1
0.1
0.01
0.001
100
10000
1x106
1x108
1x1010
1x1012
1x1014
èñ. 9: Çíà÷åíèÿ öåëåâîé óíêöèè, ïîëó÷åííûå ìåòîäîì äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, è âðåìÿ ïîèñêà ñîîòâåòñâóþùèõ èì îïòèìàëüíûõ òðàåêòîðèé äâóìÿ ìåòîäàìè.
T = 4, m = n = 7
îòðèöàòåëüíûì ïîêàçàòåëåì, ëèáî ýêñïîíåíöèàëüíàÿ ñ îáðàòíûì ïîêàçàòåëåì.
Òåïåðü ïîñòàâèì íà îñü îðäèíàò âðåìÿ è îòîáðàçèì âðåìÿ ðàáîòû îáîèõ
ìåòîäîâ 9.  òî âðåìÿ êàê ñ ðîñòîì çíà÷åíèÿ öåëåâîé óíêöèè âðåìÿ äëÿ
ìåòîäà êîíòèíóàëèçàöèè îñòàåòñÿ ïðàêòè÷åñêè íåèçìåííûì, âðåìÿ äëÿ ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ îêàçûâàåòñÿ â ñòåïåííîé çàâèñèìîñòè (÷òî ñîîòâåòñâóåò îöåíêå, ïîñêîëüêó äëÿ ýòèõ çàäà÷ m çàèêñèðîâàí)
äî îïðåäåëåííûõ çíà÷åíèé îí îêàçûâàåòñÿ äàæå áûñòðåå ìåòîäà êîíòèíóàëèçàöèè, íî çàòåì áûñòðûé ðîñò ïðèâîäèò ê òîìó, ÷òî åãî âðåìåííàÿ
ýåêòèâíîñòü ñòàíîâèòñÿ î÷åíü íèçêîé.
 ðåçóëüòàòå àíàëèçà ãðàèêîâ, ìîæíî ïðèéòè ê ñëåäóþùèì âûâîäàì:
ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äîâîëüíî ýåêòèâåí, îäíàêî ñ
î÷åíü áûñòðûì ðîñòîì âåêòîðà èíòåíñèâíîñòåé áûñòðî ðàñòåò âðåìÿ âûïîëíåíèÿ ìåòîäà è ïîèñê ðåøåíèÿ ìîæåò çàíÿòü ñóùåñòâåííîå âðåìÿ. Ìåòîä êîíòèíóàëèçàöèè äàåò äîïóñòèìîå ðåøåíèå, îäíàêî ïîãðåøíîñòü ñ òå÷åíèåì âðåìåíè ðàñòåò â ãåîìåòðè÷åñêîé ïðîãðåññèè è äëÿ íåäîñòàòî÷íî
42
áûñòðî ðàñòóùèõ ìîäåëåé ïîëó÷àåìîå äîïóñòèìîå ðåøåíèå ìîæåò áûòü áåñïîëåçíî äàæå â êà÷åñòâå íèæíåé îöåíêè (â êðàéíåì ñëó÷àå ìîæåò äàâàòü
òðèâèàëüíîå íóëåâîå ðåøåíèå).
Òàêèì îáðàçîì, ýåêòèâíîñòü ðàññìîòðåííûõ ìåòîäîâ ñèëüíî çàâèñèò
îò ñêîðîñòè ðîñòà ìîäåëè. Äëÿ ïðåäâàðèòåëüíîé îöåíêè ðîñòà ìîæíî èñïîëüçîâàòü ðåøåíèå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ áåç îãðàíè÷åíèÿ
öåëî÷èñëåííîñòè, êîòîðîå äàåò âåðõíþþ îöåíêó.
Ñëåäóåò òàêæå çàìåòèòü, ÷òî ïðåäñòàâëåííàÿ â ðàáîòå ðåàëèçàöèÿ ìåòîäîâ ïðåäñòàâëÿåò ïðîñòóþ äåìîíñòðàöèþ îïèñàííûõ â ðàáîòå àëãîðèòìîâ
â ïðîãðàìíîì êîäå è ìîæåò áûòü îïòèìèçèðîâàíà, íàïðèìåð, ñ ïîìîùüþ
ïðèìåíåíèÿ ìíîãîïîòî÷íîñòè.
43
Çàêëþ÷åíèå
 ðàáîòå çíàêîìàÿ ýêîíîìèñòàì ìîäåëü Íåéìàíà ðàññìîòðåíà â íîâîì
êëþ÷å êàê îáúåêò öåëî÷èñëåííîé îïòèìèçàöèîííîé çàäà÷è. Èññëåäîâàíû
ìåòîäû íàõîæäåíèÿ îïòèìàëüíîé òðàåêòîðèè, ïðåäñòàâëÿþùèå ðàçëè÷íûå
ïîäõîäû ê ðåøåíèþ çàäà÷è îïòèìèçàöèè.
Ìåòîä êîíòèíóàëèçàöèè ïðåäñòàâëÿåò èç ñåáÿ ñâåäåíèå íîâîé çàäà÷è ê
õîðîøî èçó÷åííîìó êëàññó çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Ïîñòðîåíà
ìîäèèêàöèÿ çàäà÷è, ïðåäñòàâëÿþùàÿ èç ñåáÿ çàäà÷ó ëèíåéíîãî ïðîãðàììèðîâàíèÿ, ñîðìóëèðîâàíû è äîêàçàíû óòâåðæäåíèÿ î òîì, ÷òî ðåøåíèå ýòîé ìîäèèêàöèè ÿâëÿåòñÿ äîïóñòèìûì ðåøåíèåì èñõîäíîé çàäà÷è,
óñòàíîâëåíû îãðàíè÷åíèÿ ïðèìåíåíèÿ, ïðîèçâåäåíà îöåíêà ïîãðåøíîñòè è
âðåìåííîé ñëîæíîñòè.
Äèíàìè÷åñêîå ïðîãðàììèðîâàíèå ÿâëÿåòñÿ îäíèì èç îñíîâíûõ è óíèâåðñàëüíûõ ïîäõîäîâ ê äèíàìè÷åñêîé çàäà÷å. Âòîðîé ìåòîä, ïðåäñòàâëåííûé â ðàáîòå, ïðèìåíÿåò ýòîò ïîäõîä ê çàäà÷å îïòèìèçàöèè öåëî÷èñëåííîé ìîäåëè Íåéìàíà. Äîêàçàíû óòâåðæäåíèÿ î òîì, ÷òî äàííûé ìåòîä
äàåò òî÷íîå ðåøåíèå îïòèìèçàöèîííîé çàäà÷è, ñîñòàâëåí ïîäðîáíûé àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîé òðàåêòîðèè, ïðîèçâåäåíà îöåíêà âðåìåííîé
ñëîæíîñòè.
Äëÿ îáîèõ ìåòîäîâ íàïèñàíà ïðîãðàììíàÿ ðåàëèçàöèÿ íà ÿçûêå C++ è
ïðîâåäåíî òåñòèðîâàíèå íà íàáîðàõ ñãåíåðèðîâàííûõ çàäà÷ ñ ðàçëè÷íûìè
ïàðàìåòðàìè. Àíàëèç ðåçóëüòàòîâ òåñòîâ ïîäòâåðäèë è óòî÷íèë òåîðåòè÷åñêèå âûâîäû. Ýåêòèâíîñòü èñïîëüçîâàíèÿ ìåòîäîâ çàâèñèò îò ñêîðîñòè
ðîñòà ýêîíîìè÷åñêîé ìîäåëè: ïðè áûñòðîì ýêñïîíåíöèàëüíîì ðîñòå ìîæåò
áûòü ïðåäïî÷òèòåëüíåé íàéòè ïðèáëèæåííîå ðåøåíèå ñ ïîìîùüþ ìåòîäà
êîíòèíóàëèçàöèè, à ïðè óìåðåííîì ðîñòå ìîæíî çà ïðèåìëåìîå âðåìÿ íàéòè òî÷íîå ðåøåíèå ñ ïîìîùüþ ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ.
Èññëåäîâàíèå ìåòîäîâ íå òîëüêî ïîêàçàëî èõ ïðèìåíèìîñòü ê ðåøå44
íèþ çàäà÷è, íî òàêæå è íàãëÿäíî ïðîäåìîíñòðèðîâàëî ðàçëè÷èÿ ïîäõîäîâ,
îïðåäåëÿþùèõ ýòè ìåòîäû. Îäíàêî ïîäõîäû ê äèíàìè÷åñêîé îïòèìèçàöèîííîé çàäà÷å ðàçíîîáðàçíû, è äàæå â ðàìêàõ ïîäõîäîâ ìåòîäû ðåøåíèÿ
ìîãóò áûòü ðàçëè÷íû. Ïîýòîìó èññëåäîâàíèå çàäà÷è îïòèìèçàöèè öåëî÷èñëåííîé ìîäåëè Íåéìàíà ìîæåò áûòü ïðîäîëæåíî ìîæíî îòìåòèòü
òàêèå âîçìîæíûå íàïðàâëåíèÿ èññëåäîâàíèé, êàê îáîáùåíèå îïèñàííîãî
â äàííîé ðàáîòå ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ íà ñëó÷àé èíòåãðàëüíîé ïîëåçíîñòè, ðåàëèçàöèÿ ïðèáëèæåííîãî ìåòîäà äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ, äàþùåãî áîëåå òî÷íóþ íèæíþþ îöåíêó, ÷åì ìåòîä
êîíòèíóàëèçàöèè, à òàêæå ïðèìåíåíèå ê çàäà÷å ìåòîäà âåòâåé è ãðàíèö.
45
Ñïèñîê ëèòåðàòóðû
[1℄
Neumann J. von. A Model of general e
onomi
equilibrium // The Review
of E
onomi
Studies, 1945. Vol. 13, No 1. P. 1-9.
[2℄
Ëàíêàñòåð Ê. Ìàòåìàòè÷åñêàÿ ýêîíîìèêà. Ì.: Ñîâåòñêîå ðàäèî, 1972.
464 ñ.
[3℄
åéë Ä. Òåîðèÿ ëèíåéíûõ
ýêîíîìè÷åñêèõ ìîäåëåé. Ì.: Èçä-âî èíî-
ñòðàííîé ëèòåðàòóðû, 1963. 418 ñ.
[4℄
Àøìàíîâ Ñ. À. Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû â ýêîíîìèêå. Ì.:
Èçä-âî Ìîñêîâñêîãî óíèâåðñèòåòà, 1980. 199 ñ.
[5℄
Äàíèëîâ Í. Í. Êóðñ ìàòåìàòè÷åñêîé ýêîíîìèêè. Ì.: Âûñøàÿ øêîëà,
2006. 407 ñ.
[6℄
Ìîðèøèìà Ì. àâíîâåñèå, óñòîé÷èâîñòü, ðîñò. Ì: Íàóêà, 1972. 280 ñ.
[7℄
Õà÷èÿí Ë.
. Ñëîæíîñòü çàäà÷ ëèíåéíîãî ïðîãðàììèðîâàíèÿ // Íîâîå â æèçíè, íàóêå, òåõíèêå. Ñåð. ¾ Ìàòåìàòèêà, êèáåðíåòèêà¿. Ì.:
Çíàíèå, 1987. 10. 32 ñ.
[8℄ Clp Do
umentation. http://
oin-or.org/Doxygen/Clp/index.html
[9℄
Mehrotra S. On the implementation of a primaldual interior point method
// SIAM Journal on Optimization, 1992. Vol. 2, No 4. P. 575-601.
[10℄ O
ial gnuplot do
umentation. http://gnuplot.info/do
umentation.html
46
Ïðèëîæåíèå
Ìåòîä êîíòèíóàëèçàöèè
void NMProblem::solveByContinualizationMethod()
{
//âåêòîðû äëÿ ñîçäàíèÿ "óïàêîâàííîé" ìàòðèöû êîýèöèåíòîâ çàäà÷è
std::ve
tor<double> elem;
std::ve
tor<int> rowInd;
std::ve
tor<int>
olInd;
//âåêòîð îãðàíè÷åíèé
std::ve
tor<double> lim(T*n, 0);
//èñõîäÿ èç äàííûõ íà âõîäå, îðìèðóåì âûøåóêàçàííûå âåêòîðû
for (int j = 0; j < n; ++j)
{
for (int i = 0; i < m; ++i)
{
if (A[i℄[j℄ != 0)
{
elem.push_ba
k(A[i℄[j℄);
rowInd.push_ba
k(j);
olInd.push_ba
k(i);
}
}
lim[j℄ = y0[j℄;
}
for (int t = 1; t < T; ++t)
for (int j = 0; j < n; ++j)
{
for (int i = 0; i < m; ++i)
{
if (B[i℄[j℄ != 0)
{
elem.push_ba
k(-B[i℄[j℄);
rowInd.push_ba
k(t*n + j);
olInd.push_ba
k((t - 1)*m + i);
lim[t*n + j℄ -= B[i℄[j℄;
}
}
for (int i = 0; i < m; ++i)
{
if (A[i℄[j℄ != 0)
{
elem.push_ba
k(A[i℄[j℄);
rowInd.push_ba
k(t*n + j);
olInd.push_ba
k(t*m + i);
}
}
}
47
//ìàòðèöà êîý. çàäà÷è (Tn x Tm)
CoinPa
kedMatrix
oefPa
kedMatrix(false, &rowInd[0℄,
&
olInd[0℄, &elem[0℄, elem.size());
//
îðìèðóåì âåêòîð êîý. (ïðè z) öåëåâîé óíêöèè
std::ve
tor<double> objCoef(T*m, 0);
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
for (int t = 0; t < T; ++t)
{
if (A[i℄[j℄ != 0)
objCoef[t*m + i℄ -=
[j℄ * k[t℄ * A[i℄[j℄;
if (B[i℄[j℄ != 0)
objCoef[t*m + i℄ +=
[j℄ * k[t + 1℄ * B[i℄[j℄;
}
}
}
//ïîñ÷èòàåì çíà÷åíèå ñâîáîäíîãî ÷ëåíà öåëåâîé óíêöèè
double objFreeTerm = 0;
for (int j = 0; j < n; ++j)
objFreeTerm += k[0℄ *
[j℄ * y0[j℄;
//ñîçäàåì ìîäåëü çàäà÷è, ìàêñèìèçèðóþùóþ öåë. -þ
ClpPredi
torCorre
tor model;
model.loadProblem(
oefPa
kedMatrix, 0, 0, &objCoef[0℄, 0, &lim[0℄);
model.setOptimizationDire
tion(-1);
model.setMaximumIterations(5000);
model.setMaximumBarrierIterations(5000);
model.setMaximumSe
onds(60);
//ðåøàåì ïðè ïîìîùè ìåòîäà ïðîãíîçà è êîððåêöèè Ìåõðîòðà
model.solve();
}
//ïîëó÷àåì îïòèìàëüíîå ðåøåíèå è çíà÷åíèå öåë. -èè
mSolution = new unsigned long int[T*m℄;
for (int i = 0; i < T*m; ++i)
mSolution[i℄ = unsigned long
int(floor(model.primalColumnSolution()[i℄));
mObje
tive = objFreeTerm;
for (int i = 0; i < T*m; ++i)
mObje
tive += objCoef[i℄ * double(
mSolution[i℄);
mSolved = true;
Ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ
void NMProblem::solveByDynami
Programming()
{
if (!terminal) return;
48
//ñîõðàíèì ðàçðåæåííûå A è B â "óïàêîâàííîì" îðìàòå
std::ve
tor<double> elemA, elemB;
std::ve
tor<int> rowIndA, rowIndB;
std::ve
tor<int>
olIndA,
olIndB;
//A ñîõðàíèì ïîñòðî÷íî
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
{
if (A[i℄[j℄ != 0)
{
elemA.push_ba
k(A[i℄[j℄);
rowIndA.push_ba
k(i);
olIndA.push_ba
k(j);
}
}
CoinPa
kedMatrix pa
kedA(false, &rowIndA[0℄,
&
olIndA[0℄, &elemA[0℄, elemA.size());
//B ñîõðàíèì ïî ñòîëáöàì
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i)
{
if (B[i℄[j℄ != 0)
{
elemB.push_ba
k(B[i℄[j℄);
rowIndB.push_ba
k(i);
olIndB.push_ba
k(j);
}
}
CoinPa
kedMatrix pa
kedB(true, &rowIndB[0℄,
&
olIndB[0℄, &elemB[0℄, elemB.size());
//â ýòîì ñïèñêå áóäóò Ï.-îïò. âåêòîðà, äîïóñòèìûå èç îïðåä. z_{t-1})
std::list<unsigned long int*> allowableParetoOptimalVe
tors;
//âåêòîð ññûëêîê íà ñïèñêè Ï.-îïò. íà êàæäîì øàãå âåêòîðîâ
//ïðè ýòîì äëÿ êàæäîãî âåêòîðà õðàíèòñÿ òàêæå
//àäðåñ Ï.-îïò. íà ïðåä. øàãå âåêòîðà, äëÿ êîòîðîãî îí äîïóñòèì
std::ve
tor<std::list<Ve
torAndParent>*> paretoOptimalVe
torsOnStep(T);
for (int t = 0; t < T; ++t)
paretoOptimalVe
torsOnStep[t℄ = new std::list<Ve
torAndParent>;
Ve
torAndParent* newVe
torAndParent;
//ïîëó÷èì ñïèñîê Ïàðåòî-îïòèìàëüíûõ âåêòîðîâ íà ïåðâîì øàãå
fillParetoOptimalVe
torsList(allowableParetoOptimalVe
tors, pa
kedA, y0);
for (auto it = allowableParetoOptimalVe
tors.begin();
it != allowableParetoOptimalVe
tors.end(); ++it)
{
newVe
torAndParent = new Ve
torAndParent(*it, NULL);
(*paretoOptimalVe
torsOnStep[0℄).push_ba
k(*newVe
torAndParent);
}
allowableParetoOptimalVe
tors.
lear();
49
//èñïîëüçóÿ ýòîò ñïèñîê, ïîëó÷èì àíàëîãè÷íûå ñïèñêè äëÿ ñëåä øàãà è ò.ä.
double* zB = new double[n℄;
for (int t = 1; t < T; ++t)
{
//äëÿ êàæäîãî Ï.-îïò. âåêòîðà èç ïðîøëîãî øàãà
//ñòðîèì äîïóñòèìûå Ï.-îïò. âåêòîðû è ñëèâàåì â îäèí ñïèñîê
for (auto prevStepListIt = (*paretoOptimalVe
torsOnStep[t-1℄).begin();
prevStepListIt != (*paretoOptimalVe
torsOnStep[t-1℄).end();
++prevStepListIt)
{
//âû÷èñëåíèå z_{t-1}*B
for (int j = 0; j < n; ++j)
{
zB[j℄ = 0;
for (int k = 0; k < pa
kedB.getVe
tor(j).getNumElements(); ++k)
zB[j℄ += pa
kedB.getVe
tor(j).getElements()[k℄ *
prevStepListIt->elem[pa
kedB.getVe
tor(j).getIndi
es()[k℄℄;
}
}
}
fillParetoOptimalVe
torsList(allowableParetoOptimalVe
tors,
pa
kedA, zB);
transferToGeneralList(allowableParetoOptimalVe
tors,
&(*prevStepListIt), (*paretoOptimalVe
torsOnStep[t℄));
//óäàëèâ äîìèíèðóåìûå âåêòîðû, ïîëó÷èì ñïèñîê Ï-îïò. íà øàãå âåêòîðîâ
bool isDominated;
for (auto pivIt = (*paretoOptimalVe
torsOnStep[t℄).begin();
pivIt != (*paretoOptimalVe
torsOnStep[t℄).end(); ++pivIt)
{
auto
andidateIt = std::next(pivIt);
while (
andidateIt != (*paretoOptimalVe
torsOnStep[t℄).end())
{
isDominated = true;
for (int i = 0; i < m; ++i)
if (
andidateIt->elem[i℄ > pivIt->elem[i℄)
isDominated = false;
if (isDominated)
andidateIt = (*paretoOptimalVe
torsOnStep[t℄).erase(
andidateIt);
else ++
andidateIt;
}
}
//îïðåäåëèì, êàêîé âåêòîð íà ïîñëåäíåì øàãå ìàêñèìèçèðóåò öåëåâóþ -þ
double maxObjVal = 0;
double objVal;
Ve
torAndParent* optimal;
for (auto it = (*paretoOptimalVe
torsOnStep[T-1℄).begin();
it != (*paretoOptimalVe
torsOnStep[T-1℄).end(); ++it)
{
objVal = 0;
50
}
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i)
objVal +=
[j℄*B[i℄[j℄*(it->elem[i℄);
if (objVal >= maxObjVal)
{
maxObjVal = objVal;
optimal = &(*it);
}
//ñ êîíöà ïîñòðîèì îïòèìàëüíóþ öåïî÷êó âåêòîðîâ èíòåíñèâíîñòåé
dpObje
tive = maxObjVal;
dpSolution = new unsigned long int[T*m℄;
for (int t = T - 1; t >= 0; --t)
{
for (int i = 0; i < m; ++i)
dpSolution[t*m + i℄ = optimal->elem[i℄;
optimal = optimal->parent;
}
dpSolved = true;
}
delete[℄ zB;
for (int t = 0; t < T; ++t)
delete paretoOptimalVe
torsOnStep[t℄;
//ãåíåðèðóåò âåêòîðû â îáðàòíîì ëåêñèêîãð. ïîðÿäêå, ñîõðàíÿÿ Ï.-îïòèìàëüíûå
void NMProblem::fillParetoOptimalVe
torsList(
std::list<unsigned long int*>& paretoOptimalVe
tors,
CoinPa
kedMatrix&
oef, double* bound)
{
std::ve
tor<unsigned long int>*
andidate =
new std::ve
tor<unsigned long int>(m);
std::ve
tor<unsigned long int>* prev_
andidate =
new std::ve
tor<unsigned long int>(m);
bool isDominated;
std::ve
tor<double> boundVe
tor(bound, bound + n);
//êàæäóþ èòåðàöèþ ìû îïðåäåëÿåì íåêîòîðûé ýëåìåíò âåêòîðà êàê "îïîðíûé" //íàáîð ðàññìàòðèâàåìûõ âåêòîðîâ-êàíäèäàòîâ ìû ïîëó÷àåì, óìåíüøàÿ
//ýòîò ýëåìåíò íà 1 è ãåíåðèðóÿ ýëåìåíòû ïîñëå íåãî íàèáîëüøèì îáðàçîì
maximizeVe
tor(&(*
andidate)[0℄, 0,
oef, boundVe
tor);
for (int i = 0; i < m-1; ++i)
{
//ïðîâåðÿåì âåêòîð, îò êîòîðîãî áóäåì ïåðåáèðàòü â ýòîé èòåðàöèè
addIfNotDominated(&(*
andidate)[0℄, paretoOptimalVe
tors);
prev_
andidate =
andidate;
andidate = new std::ve
tor<unsigned long int>(*prev_
andidate);
//â öèêëå óìåíüøàåì "îïîðíûé" ýëåìåíò è ïðîâåðÿåì âåêòîðû íà Ï.-îïò.
while ((*
andidate)[i℄ > 0)
{
--(*
andidate)[i℄;
51
}
}
maximizeVe
tor(&(*
andidate)[0℄, i+1,
oef, boundVe
tor);
isDominated = !addIfNotDominated(&(*
andidate)[0℄,
paretoOptimalVe
tors);
prev_
andidate =
andidate;
andidate = new std::ve
tor<unsigned long int>(*prev_
andidate);
if (isDominated) delete prev_
andidate;
}
//ïîñëåäíèé ýë-ò íåò ñìûñëà äåëàòü "îïîðíûì", ïðîâåðÿåì âåêòîð íà Ï.-îïò.
if (!addIfNotDominated(&(*
andidate)[0℄, paretoOptimalVe
tors))
delete
andidate;
//íà÷èíàÿ ñ íåê. ýëåìåíòà ãåíåðèðóåò âåêòîð, íàèá. â ëåêñèêîãð. ñìûñëå
void NMProblem::maximizeVe
tor(unsigned long int* subjVe
tor, int startInd,
CoinPa
kedMatrix&
oef, std::ve
tor<double> bound)
{
CoinShallowPa
kedVe
tor
oefRow;
unsigned long int max;
for (int i = startInd; i < m; ++i)
{
//â
oefRow ñîõðàíèì íåíóëåâûå êîýèöèåíòû äëÿ i-ãî ýëåìåíòà
oefRow =
oef.getVe
tor(i);
//âû÷èñëèì ìàêñèìàëüíîå çíà÷åíèå
ó÷åòîì êîýèöèåíòîâ è îãðàíè÷åíèé
if (
oefRow.getNumElements() != 0)
{
max = unsigned long int(floor(bound[
oefRow.getIndi
es()[0℄℄ /
oefRow.getElements()[0℄));
for (int k = 1; k <
oefRow.getNumElements(); ++k)
{
if (unsigned long int(floor(bound[
oefRow.getIndi
es()[k℄℄ /
oefRow.getElements()[k℄)) < max)
max = unsigned long int(floor(bound[
oefRow.getIndi
es()[k℄℄ /
oefRow.getElements()[k℄));
}
//îáíîâèì çíà÷åíèå îãðàíè÷åíèé
if (max != 0 && i != m - 1)
for (int k = 0; k <
oefRow.getNumElements(); ++k)
bound[
oefRow.getIndi
es()[k℄℄ -=
max*(unsigned long int(
oefRow.getElements()[k℄));
//ïðèñâîèì âû÷èñëåííîå ìàêñèìàëüíîå çíà÷åíèå ýëåìåíòó
subjVe
tor[i℄ = max;
}
else //ýòîò ñëó÷àé ñîîòâ. íåïðàâèëüíîìó çàïîëíåíèþ ìàòðèöû A
{
std::
out << "\nÌàòðèöà A ñîäåðæèò íóëåâóþ ñòðîêó\n";
subjVe
tor[i℄ = 0;
}
}
}
//äîáàâëÿåò âåêòîð â ñïèñîê è âîçâðàùàåò true,
52
//åñëè îí íå äîìèíèðóåòñÿ íè îäíèì âåêòîðîì èç ñïèñêà
bool NMProblem::addIfNotDominated(unsigned long int* subjVe
tor,
std::list<unsigned long int*>& listOfVe
tors)
{
bool isDominated;
for (auto it = listOfVe
tors.begin(); it != listOfVe
tors.end(); ++it)
{
isDominated = true;
for (int i = 0; i < m; ++i)
if (subjVe
tor[i℄ > (*it)[i℄)
isDominated = false;
if (isDominated) return false;
}
listOfVe
tors.push_ba
k(subjVe
tor);
return true;
}
//ïåðåíîñèò ýëåìåíòû ñïèñêà Ï.-îïò. âåêòîðîâ, äîïóñòèìûõ èç îïðåä. z_{t-1},
//â ñïèñîê äëÿ øàãà, ñîõðàíÿÿ ññûëêó íà z_{t-1} è íå íàðóøàÿ ïîðÿäîê
void NMProblem::transferToGeneralList(std::list<unsigned long int*>& in,
Ve
torAndParent* parent, std::list<Ve
torAndParent>& out)
{
bool isDupli
ate;
Ve
torAndParent* newOutElement;
auto itOut = out.begin();
for (auto itIn = in.begin(); itIn != in.end(); ++itIn)
{
for (int i = 0; i < m; ++i)
{
while ((itOut != out.end()) && (itOut->elem[i℄ >(*itIn)[i℄))
++itOut;
if (itOut == out.end()) break;
else
if (itOut->elem[i℄ < (*itIn)[i℄) break;
}
if (itOut == out.end())
{
newOutElement = new Ve
torAndParent(*itIn, parent);
out.push_ba
k(*newOutElement);
}
else
{
//íåîáõîäèìî ïðîâåðèòü, íå ÿâëÿåòñÿ ëè äîáàâëÿåìûé âåêòîð äóáëèêàòîì
isDupli
ate = true;
for (int i = 0; i < m; ++i)
if ((*itIn)[i℄ != itOut->elem[i℄)
isDupli
ate = false;
if (!isDupli
ate)
{
newOutElement = new Ve
torAndParent(*itIn, parent);
out.insert(itOut, *newOutElement);
}
53
else delete[℄ (*itIn);
}
}
}
//ñïèñîê, èç êîòîðîãî ïåðåíåñåíû ýëåìåíòû, î÷èùàåòñÿ
in.
lear();
54
Отзывы:
Авторизуйтесь, чтобы оставить отзыв