1612726871-fd1970eb57207f2e4883f7549db906ce (Ларин, Плясунов - Примеры и задачи)

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈÍÎÂÎÑÈÁÈÐÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÐ. Ì. Ëàðèí, À. Â. Ïëÿñóíîâ, À. Â. ÏÿòêèíÌÅÒÎÄÛ ÎÏÒÈÌÈÇÀÖÈÈ.Ïðèìåðû è çàäà÷èÓ÷åáíîå ïîñîáèåÍîâîñèáèðñê2003ÓÄÊ 519.6ÁÁÊ Â.173.1/2Ëàðèí Ð. Ì., Ïëÿñóíîâ À. Â., Ïÿòêèí À. Â. Ìåòîäû îïòèìèçàöèè. Ïðèìåðû è çàäà÷è:Ó÷åá. ïîñîáèå / Íîâîñèá. óí-ò. Íîâîñèáèðñê, 2003.

115 ñ.Ó÷åáíîå ïîñîáèå ïðåäñòàâëÿåò ñîáîé ñáîðíèê ïðèìåðîâ è çàäà÷ ïî îñíîâíîé ÷àñòè ñåìåñòðîâîãî êóðñà "Ìåòîäû îïòèìèçàöèè", ÷èòàåìîãî íà ìåõàíèêî-ìàòåìàòè÷åñêîì ôàêóëüòåòå è ôàêóëüòåòå èíôîðìàöèîííûõ òåõíîëîãèé Íîâîñèáèðñêîãî óíèâåðñèòåòà è ïîñâÿù¼ííîãî ìåòîäàì ðåøåíèÿ îïòèìèçàöèîííûõ çàäà÷ â êîíå÷íîìåðíûõ ïðîñòðàíñòâàõ. Ïîñîáèåñîäåðæèò òàêæå îïðåäåëåíèÿ è ôîðìóëèðîâêè îñíîâíûõ òåîðåì, ÷òî ïîçâîëÿåò ïîëüçîâàòüñÿ èì íåçàâèñèìî îò òåîðåòè÷åñêîãî êóðñà. Ïîäðîáíî ðàññìîòðåíû êëàññè÷åñêèå ìåòîäûðåøåíèÿ çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ, à òàêæå âûïóêëîå è ëèíåéíîå ïðîãðàììèðîâàíèå.Ïîñîáèå ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ ìåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòà, ôàêóëüòåòà èíôîðìàöèîííûõ òåõíîëîãèé, à òàêæå äëÿ âñåõ, êòî æåëàåò îñâîèòü ðàññìàòðèâàåìûåìåòîäû ñàìîñòîÿòåëüíî.Àâòîðû âûðàæàþò ñâîþ ïðèçíàòåëüíîñòü Í.

È. Ãëåáîâó çà ðÿä ïîëåçíûõ çàìå÷àíèé,êîòîðûå áûëè ó÷òåíû ïðè ïîäãîòîâêå ïîñîáèÿ.Ðåöåíçåíòêàíäèäàò ôèçèêî-ìàòåìàòè÷åñêèõ íàóê, äîöåíò Þ. À. Êî÷åòîâc Íîâîñèáèðñêèé ãîñóäàðñòâåííûé°óíèâåðñèòåò, 2003ÎÃËÀÂËÅÍÈÅÏðåäèñëîâèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . 41. Îñíîâíûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ . . . . . . . . . . . . . . . . . . . . . . . 52. Çàäà÷è íåëèíåéíîãî ïðîãðàììèðîâàíèÿ . . . . . . . . . . . . . . . . . . . . . 72.1. Îäíîìåðíûé ñëó÷àé . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2. Ìíîãîìåðíàÿ áåçóñëîâíàÿ îïòèìèçàöèÿ . . . . . . . . . . . . . . . . . . . . . . 92.3. Çàäà÷è ñ îãðàíè÷åíèÿìèðàâåíñòâàìè.Ìåòîä íåîïðåäåë¼ííûõ ìíîæèòåëåé Ëàãðàíæà . . . . . . . . . . . . . . . . . . . . . . 122.4. Çàäà÷è ñ îãðàíè÷åíèÿìèíåðàâåíñòâàìè . . .

. . . . . . . . . . . . . . . . . 173. Âûïóêëîå ïðîãðàììèðîâàíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1. Âûïóêëûå ìíîæåñòâà è ôóíêöèè; êâàçèâûïóêëûå ôóíêöèè 203.2. Êðèòåðèé îïòèìàëüíîñòè; òåîðåìà ÊóíàÒàêêåðà . . . . . .

. . . . 224. Ëèíåéíîå ïðîãðàììèðîâàíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.1. Ðàçëè÷íûå ôîðìû çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ . . . 264.2. Áàçèñ è áàçèñíîå ðåøåíèå . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . 304.3. Ñèìïëåêñòàáëèöà è êðèòåðèé îïòèìàëüíîñòè.Ýëåìåíòàðíîå ïðåîáðàçîâàíèå áàçèñà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.4. Ïðÿìîé ñèìïëåêñìåòîä . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . 374.5. Ëåêñèêîãðàôè÷åñêèé âàðèàíò ïðÿìîãî ñèìïëåêñìåòîäà . . . 444.6. Ìåòîä èñêóññòâåííîãî áàçèñà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.7. Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ ñèìïëåêñìåòîäà . . . . . . . . . . . 535. Äâîéñòâåííûå çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ . .

. . . 575.1. Ïîñòðîåíèå äâîéñòâåííûõ çàäà÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . .575.2. Òåîðåìû äâîéñòâåííîñòè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615.3. Äâîéñòâåííûé ñèìïëåêñìåòîä . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Ïðèëîæåíèå. Ìåòîä âîçìîæíûõ íàïðàâëåíèé . .

. . . . . . . . . . . . 67Áèáëèîãðàôè÷åñêèé ñïèñîê . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743ÏðåäèñëîâèåÓ÷åáíîå ïîñîáèå ñîäåðæèò çàäà÷è è óïðàæíåíèÿ, ïðåäíàçíà÷åííûå äëÿ ïðàêòè÷åñêèõçàíÿòèé ïî êóðñó ìåòîäîâ îïòèìèçàöèè â êîíå÷íîìåðíîì ïðîñòðàíñòâå. Ðàññìàòðèâàþòñÿ çàäà÷è ïîèñêà ìèíèìóìà èëè ìàêñèìóìà ñêàëÿðíîé ôóíêöèè íà ìíîæåñòâå, ðàñïîëîæåííîì â êîíå÷íîìåðíîì åâêëèäîâîì ïðîñòðàíñòâå è îïðåäåëÿåìîì êîíå÷íîé ñèñòåìîéîãðàíè÷åíèéðàâåíñòâ èëè îãðàíè÷åíèéíåðàâåíñòâ. Çà îñíîâó ïîñîáèÿ âçÿòà ïðîãðàììàêóðñà "Ìåòîäû îïòèìèçàöèè", êîòîðûé ÷èòàåòñÿ íà ìåõàíèêî-ìàòåìàòè÷åñêîì ôàêóëüòåòåÍÃÓ.

Åìó ïðåäøåñòâóþò êóðñû ìàòåìàòè÷åñêîãî àíàëèçà è ëèíåéíîé àëãåáðû. Ïðåäïîëàãàåòñÿ, ÷òî ñòóäåíòû óæå çíàêîìû ñ óêàçàííûìè êóðñàìè.Îñíîâíóþ ÷àñòü ïîñîáèÿ ñîñòàâëÿþò çàäà÷è îïòèìèçàöèè, êîòîðûå ïðèíÿòî òàêæå íàçûâàòü ýêñòðåìàëüíûìè çàäà÷àìè. Èõ ðåøåíèå ïîçâîëÿåò îñâîèòü àëãîðèòìû ñîîòâåòñòâóþùèõ ìåòîäîâ è ïðèîáðåñòè íåîáõîäèìûå âû÷èñëèòåëüíûå íàâûêè.×èñëî òåîðåòè÷åñêèõ óïðàæíåíèé íåâåëèêî. Îáû÷íî îíè ôîðìèðóþòñÿ â ïðîöåññå ÷òåíèÿ ëåêöèé è, êàê î÷åâèäíûå è íåòðóäíûå ÷àñòè äîêàçàòåëüñòâà íåêîòîðûõ óòâåðæäåíèé,îáÿçàòåëüíû äëÿ âûïîëíåíèÿ. Ýòî îñîáåííî êàñàåòñÿ íåêîòîðûõ ñâîéñòâ âûïóêëûõ ôóíêöèé, èñïîëüçóåìûõ â ìåòîäå øòðàôíûõ ôóíêöèé è ïðè ðåãóëÿðèçàöèè íåêîððåêòíûõ çàäà÷êîíå÷íîìåðíîé îïòèìèçàöèè.Îñíîâíûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ, êîòîðûå ÿâëÿþòñÿ îáùèìè äëÿ âñåõ ðàçäåëîâïîñîáèÿ, ðàññìàòðèâàþòñÿ â ðàçä.

1. Ýòî êàñàåòñÿ òàêèõ ïîíÿòèé, êàê îáùàÿ ïîñòàíîâêà çàäà÷è îïòèìèçàöèè (ââîäèòñÿ ïîíÿòèå çàäà÷è ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ), öåëåâàÿôóíêöèÿ, äîïóñòèìîå ìíîæåñòâî è äîïóñòèìîå ðåøåíèå, ëîêàëüíûé è ãëîáàëüíûé ýêñòðåìóìû, óñëîâíûé è áåçóñëîâíûé ýêñòðåìóìû, íåêîòîðûå îáùèå óòâåðæäåíèÿ î ðàçðåøèìîñòèçàäà÷è.Êàæäàÿ íîâàÿ òåìà (â îäíîì ðàçäåëå èõ ìîæåò áûòü íåñêîëüêî) íà÷èíàåòñÿ îïðåäåëåíèÿìè è òåîðåìàìè, èñïîëüçóåìûìè äàëåå, èëè ññûëêîé íà ëèòåðàòóðó, ãäå ìîæíî íàéòèäîïîëíèòåëüíûå ñâåäåíèÿ.

Ïîäîáíàÿ ñòðóêòóðà ïîñîáèÿ ìîæåò îêàçàòüñÿ ïîëåçíîé ïðè ñàìîñòîÿòåëüíîì èçó÷åíèè êóðñà.Ðàçä. 2, ãäå ðàññìàòðèâàþòñÿ îáùèå ìåòîäû ðåøåíèÿ çàäà÷ ñ íåïðåðûâíûìè è íåïðåðûâíî äèôôåðåíöèðóåìûìè ôóíêöèÿìè, ïðåäñòàâëÿåò ñîáîé ââîäíóþ ÷àñòü è ñîäåðæèòêëàññè÷åñêèå ìåòîäû ðåøåíèÿ çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ. Îñíîâíîé óïîðçäåñü ñäåëàí íà ìåòîäå íåîïðåäåë¼ííûõ ìíîæèòåëåé Ëàãðàíæà, èçâåñòíîì ñòóäåíòàì ïîêóðñó ìàòåìàòè÷åñêîãî àíàëèçà. ñâÿçè ñ îòñóòñòâèåì åäèíûõ ó÷åáíûõ ïîñîáèé ïî ïðàêòè÷åñêèì çàíÿòèÿì, ñîîòâåòñòâóþùèõ ÷èòàåìîìó êóðñó, à òàêæå â ñâÿçè ñ íåáîëüøèì êîëè÷åñòâîì âðåìåíè, âûäåëÿåìûì íà íèõ ïî ó÷åáíîìó ïëàíó, â ïîñîáèå âêëþ÷åíû ïðèìåðû, èëëþñòðèðóþùèå ìåòîäû,òðåáóþùèå áîëüøîãî îáú¼ìà âû÷èñëåíèé. Ýòî ïðåæäå âñåãî êàñàåòñÿ ìåòîäà âîçìîæíûõíàïðàâëåíèé è ÷àñòè÷íî ìåòîäà øòðàôíûõ ôóíêöèé.Åñòåñòâåííî, ÷òî â ïîñîáèè, ïðåäíàçíà÷åííîì äëÿ ïåðâîãî çíàêîìñòâà ñ ïðåäìåòîì,ïðåäñòàâëåíû òîëüêî îñíîâíûå ìåòîäû.

Íàøà öåëü ïîçíàêîìèòü ñòóäåíòîâ ñ íåêîòîðûìè ïðè¼ìàìè è ìåòîäàìè ðåøåíèÿ çàäà÷ êîíå÷íîìåðíîé îïòèìèçàöèè, êîòîðûå ìîãóòïðèãîäèòüñÿ ïðè àíàëèçå âîçíèêøåé ïåðåä íèìè ðåàëüíîé çàäà÷è îïòèìèçàöèè.Êðîìå òîãî, â ïîñîáèè íå ðàññìàòðèâàþòñÿ ÷èñëåííûå ìåòîäû ðåøåíèÿ çàäà÷ áåçóñëîâíîé îïòèìèçàöèè, òàêèå êàê ðàçëè÷íûå ìîäèôèêàöèè ãðàäèåíòíîãî ìåòîäà, ìåòîäà Íüþòîíà, èìåþùèå áîëüøîå ïðàêòè÷åñêîå çíà÷åíèå è èçëàãàåìûå â òåîðåòè÷åñêîì êóðñå.

Ýòîñâÿçàíî ñ òåì, ÷òî âðåìÿ, âûäåëåííîå äëÿ ñåìèíàðñêèõ çàíÿòèé, ïîçâîëÿåò îçíàêîìèòüñÿòîëüêî ñ ñàìûìè îñíîâíûìè ìåòîäàìè â ôîðìå, íå òðåáóþùåé áîëüøîãî îáú¼ìà âû÷èñëåíèéè èñïîëüçîâàíèÿ êîìïüþòåðíûõ ïðîãðàìì.Ñëåäóåò òàêæå ó÷åñòü, ÷òî íåêîòîðûå èç ìåòîäîâ îïòèìèçàöèè äëÿ ñïåöèàëüíûõ êëàññîâçàäà÷ èçëàãàþòñÿ â êóðñå "Èññëåäîâàíèå îïåðàöèé".41. Îñíîâíûå îïðåäåëåíèÿ è îáîçíà÷åíèÿ äàëüíåéøåì èïîëüçóþòñÿ ñëåäóþùèå îáîçíà÷åíèÿ:Z ìíîæåñòâî öåëûõ ÷èñåë;En n-ìåðíîå åâêëèäîâî ïðîñòðàíñòâî;x1 x2 x= .

. .  âåêòîðñòîëáåö, òî÷êà ïðîñòðàíñòâà En ;xn>x = (x1 , x2 , . . . , xn ) âåêòîðñòðîêà; ñèìâîë > ïðèìåíÿåòñÿ äëÿ îáîçíà÷åíèÿ îïåðàöèè òðàíñïîíèðîâàíèÿ;{x ∈ X| Q} ìíîæåñòâî âñåõ ýëåìåíòîâ èç X , îáëàäàþùèõ ñâîéñòâîì Q. Åñëè X = En ,òî èñïîëüçóåòñÿ çàïèñü {x | Q};[x, y] = {z | z = αx + (1 − α)y, 0 ≤ α ≤ 1} îòðåçîê ñ êîíöåâûìè òî÷êàìè x è y ;(x, y) = [x, y] \ {x, y} = {z | z = αx + (1 − α)y, 0 < α < 1} èíòåðâàë, àíàëîãè÷íîîáîçíà÷àþòñÿ ïîëóèíòåðâàëû(x, y] è [x, y);Phx, yi =px> y = ni=1 xi yi ñêàëÿðíîå ïðîèçâåäåíèå ýëåìåíòîâ x è y ;kxk = hx, xi åâêëèäîâà íîðìà âåêòîðà x;ρ(x, y) = kx − yk åâêëèäîâî ðàññòîÿíèå ìåæäó òî÷êàìè x è y ;Uε (x) = {y | ρ(x, y) ≤ ε} εîêðåñòíîñòü òî÷êè x, ò. å. çàìêíóòûé øàð ðàäèóñà ε ñöåíòðîì â òî÷êå x.Ïóñòü X ⊂ En è x ∈ En .

Òî÷êà x íàçûâàåòñÿ òî÷êîé ïðèêîñíîâåíèÿ ìíîæåñòâà X , åñëèäëÿ ëþáîãî ε > 0 ìíîæåñòâî X ∩ Uε (x) íåïóñòî. Ìíîæåñòâî X âñåõ òî÷åê ïðèêîñíîâåíèÿìíîæåñòâà X íàçûâàåòñÿ çàìûêàíèåì ìíîæåñòâà X . Òî÷êà x íàçûâàåòñÿ ïðåäåëüíîé òî÷êîé ìíîæåñòâà X , åñëè ëþáàÿ εîêðåñòíîñòü ýòîé òî÷êè ñîäåðæèò áåñêîíå÷íî ìíîãî òî÷åêìíîæåñòâà X . Òî÷êà x íàçûâàåòñÿ âíóòðåííåé òî÷êîé ìíîæåñòâà X , åñëè íàéä¼òñÿ ε > 0,äëÿ êîòîðîãî Uε (x) ⊂ X .×åðåç IntX îáîçíà÷àåòñÿ ìíîæåñòâî âñåõ âíóòðåííèõ òî÷åê ìíîæåñòâà X , íàçûâàåìîå âíóòðåííîñòüþ ìíîæåñòâà X . Òî÷êà x ∈ X íàçûâàåòñÿ ãðàíè÷íîéòî÷êîé ìíîæåñòâà X , åñëè â ëþáîé å¼ îêðåñòíîñòè íàéäóòñÿ êàê òî÷êè, ïðèíàäëåæàùèåìíîæåñòâó X , òàê è òî÷êè, íå ïðèíàäëåæàùèå ýòîìó ìíîæåñòâó.

Ìíîæåñòâî FrX = X \ IntXÿâëÿåòñÿ ìíîæåñòâîì âñåõ ãðàíè÷íûõ òî÷åê ìíîæåñòâà X è íàçûâàåòñÿ ãðàíèöåé ýòîãî ìíîæåñòâà. Òî÷êà x, ïðèíàäëåæàùàÿ ìíîæåñòâó X , íàçûâàåòñÿ êðàéíåé (óãëîâîé) òî÷êîé ýòîãîìíîæåñòâà, åñëè íå ñóùåñòâóåò òàêèõ x1 , x2 ∈ X, x1 6= x2 , ÷òî x = (x1 + x2 )/2.Êðîìå òîãî, äëÿ òî÷åê x è y ïðîñòðàíñòâà En ÷àñòî áóäóò èñïîëüçîâàòüñÿ òàêèå îáîçíà÷åíèÿ:x ≥ y ÷àñòè÷íûé ïîðÿäîê â En , îçíà÷àþùèé, ÷òî xi ≥ yi , (i = 1, n).