1612726871-fd1970eb57207f2e4883f7549db906ce (828573)
Текст из файла
ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈÍÎÂÎÑÈÁÈÐÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÐ. Ì. Ëàðèí, À. Â. Ïëÿñóíîâ, À. Â. ÏÿòêèíÌÅÒÎÄÛ ÎÏÒÈÌÈÇÀÖÈÈ.Ïðèìåðû è çàäà÷èÓ÷åáíîå ïîñîáèåÍîâîñèáèðñê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).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
