Дөңес программалау есептері. Дөңес программалау есебінің қойылымы Дөңес программалаудың қажетті және жеткілікті шарттары

Дәріс 11Дөңес программалау

Анықтама 1. В дөңес программалау мәселесі барлық функциялар дөңес болатын сызықты емес бағдарламалау есебі деп аталады.

Сонымен, дөңес программалау мәселесі шартты минимизациялау есебі болып табылады, мұндағы мақсат функциясы дөңес, ал рұқсат етілген ауданы дөңес теңсіздіктер жүйесі арқылы құрылған дөңес жиын болып табылады. Сондықтан 6-тармақта бұрын алынған мәлімдемелер дөңес программалау мәселесі үшін жарамды. Бұл бөлімде біз оларды нақтылаймыз жалпы нәтижелержәне оларды дөңес программалаудың келесі мәселесін зерттеуге және шешуге ыңғайлы формаға келтіріңіз:

(1)

, (2)

. (3)

Бізге ғарышта кейбір қосалқы құрылыстар қажет
векторлар
. Біріншісінің векторы
нүктелік компонент арқылы белгіленеді . Сонымен,
.

(1) - (3) есебі үшін жиынды анықтаймыз

қайда
.

Лемма . Дөңес программалау есебі үшін (1) - (3) бір топ дөңес.

Дәлелдеу. Біз ерікті векторларды таңдаймыз
көптен және саны
. Содан кейін ұпайлар бар және бастап және сияқты. Бұл теңсіздіктерді көбейтеміз және
, тиісінше және оларды қосыңыз. Барлық функциялардың дөңес болуына байланысты біз аламыз

Алынған теңсіздіктер жиынның дөңестігін білдіреді .

Теорема 1. (Дөңес программалау есебінің Лагранж функциясының седл нүктесі түріндегі Кун-Такер теоремасы ) Дөңес программалау есебінде (1) – (3) жүйе (2) Слейтер шартына қатысты қанағаттандырылсын. болды Мәселені шешу(1) – (3), теріс емес вектордың болуы қажетті және жеткілікті солай
Лагранж функциясының седла нүктесі болып табылады.

Дәлелдеу. Бұл шарттың жеткіліктілігі ерікті сызықты емес бағдарламалау мәселесі үшін дәлелденгендіктен (Кіріспенің 2.6 теоремасын қараңыз), бұл қажеттілікті дәлелдеу ғана қалады.

Қажет. Болсын – (1) – (3) есептің шешімі. қояйық
. Ол анық
, өйткені
,
және
.

Соған көз жеткізейік
. Керісінше делік. Бұл бір нүктенің бар екенін білдіреді
солай
. Демек, - мақсат функциясының мәні минимумнан аз болатын мұндай рұқсат етілген нүкте. Біз бұл фактімен қайшылық аламыз – дөңес программалау есебін шешу.

Сонымен,
. Леммаға сәйкес жиынтық дөңес. Сондықтан 8.2 теоремасының барлық талаптары қанағаттандырылады. Демек, нөлден басқасы бар

векторы
анықтамалық нүкте көпшілікке :

Әрі қарай вектордың барлық координаталары екенін тексерейік оң емес. Керісінше делік. Координатасы болсын
. Біз векторда бекітеміз қоспағанда барлық компоненттер -Ой. Содан кейін, өнімді ескере отырып
ерікті түрде үлкен мәндерді қабылдай алады (өйткені координаттар жоғарыдан шектелмеген ), (4) теңсіздігімен қайшылықты аламыз.

Мұны кез келген адамға көру оңай
векторлар
жиынтығына кіреді . Сонда (4) бізде:

Соны көрсетейік
. Олай болмасын. Содан кейін
. Демек,
. Слейтер шарты бойынша вектор бар
солай
. Сонымен
. Алынған қайшылық мынаны білдіреді
.

Белгілеу
. Құрылған вектор екенін көрсетейік Лагранж көбейткіштерінің қажетті векторы болып табылады. Ол анық
және (5) нүктесінен аламыз

Осы жерден
керек

. (7)

Екінші жағынан, бері
(шайында
) және
, теңсіздігін аламыз

. Осы жерден және (7) нүктесінен бұл шығады
комплементарлы босаңсу шарты орындалады:

. (8)

(6) және (8) тармақтарынан бізде бар

немесе, бұл бірдей,

Әрі қарай, рұқсат етіңіз
. Содан кейін
. Осы жерден және (8) теңсіздікті аламыз

(9), (10) теңсіздіктері және соны білдіреді
дөңестің Лагранж функциясының седла нүктесі болып табылады

бағдарламалау логотипі. Бұл талап етілді.

Кун-Такер теоремасының басқа нұсқасымен таныспас бұрын тірек векторлық конустар бойынша шартты минимум критерий болып табылатын келесі теореманы ұсынамыз.

2-теорема. Болсын – дөңес және дифференциалданатын
функция, жиын
дөңес. Содан кейін нүктеге жету үшін
функцияның шартты минимумы болды жиынтықта
, қосу үшін қажетті және жеткілікті

. (11)

Дәлелдеу 6.5 теоремасынан және конус анықтамасынан тікелей шығады
нүктедегі тірек векторлары көпшілікке
.

Теорема 3. (Дөңес программалау есебі үшін дифференциалдық түрдегі Кун-Такер теоремасы ) Дөңес программалау есебі (1), (2) түрінде берілсін, мұндағы барлық функциялар
үздіксіз дифференциалданатын болса, жүйе (2) Слейтер шартын қанағаттандырады. Содан кейін вектор үшін
(1), (2) есептің шешімі болды, теріс емес вектордың болуы қажет және жеткілікті жағдайлары солай

, (12)

.

Дәлелдеу. (12) және (13) шарттары (11) қосуға эквивалентті екенін көрсетейік. Нүкте болсын
солай ма
. Содан кейін
және
.

Енді рұқсат етіңіз
. Сонда 2 және 10.5 теоремаларынан экстремумның қажетті және жеткілікті шарты осындай факторлардың болуы болып табылады.
,
, ол үшін
. қояйық
барлығына
және соңғы теңдіктен (12) және (13) шарттарын алыңыз. Бұл талап етілді.

Бөлімді қорытындылай келе, біз екі Кун-Такер теоремасының тұжырымдарын ұсынамыз.

сызықтық шектеулермен дөңес программалау.

Теорема 4. Дөңес программалау есебінде (1) - (3) шектеулер жүйесі (2) түрінде болсын.

, b – өлшем векторы
. Содан кейін теріс емес вектор үшін мәселенің шешімі болды, бұл қажет және жеткілікті

теріс емес вектор болды солай
бұл мәселенің Лагранж функциясының седла нүктесі болып табылады.

Бұл жағдайда Лагранж функциясының пішіні бар екенін ескеріңіз.

Теорема 5. Дөңес программалау есебінде (1), (2) мақсат функциясы болсын үздіксіз дифференциалданатын, шектеулер жүйесі (2) формасына ие
, мұндағы A өлшемнің матрицасы
, b – өлшем векторы
. Содан кейін вектор үшін
мәселенің шешімі болды, теріс емес вектордың болуы қажет және жеткілікті жағдайлары солай
,
.

4 және 5 теоремалар Слейтер шартының орындалуын талап етпейтінін ескеріңіз, сондықтан олар 1 және 3 теоремалардың ерекше жағдайлары емес және тәуелсіз дәлелдеуді қажет етеді.

Кез келген нүкте үшін теңсіздік орындалатын болса, дөңес жиында берілген функция дөңес деп аталады. Дөңес жиындағы дөңес функциялардың теріс емес коэффициенттері бар сызықтық комбинация дөңес функция болып табылады. берілген жиынтық. Дөңес жиында анықталған функциялар дөңес болсын.

Егер бұл жұмыс сізге сәйкес келмесе, беттің төменгі жағында ұқсас жұмыстардың тізімі бар. Сондай-ақ іздеу түймесін пайдалануға болады

№12 дәріс

КОНВУЗИВТІ БАҒДАРЛАМАЛАУ

Математикалық бағдарламалау есептерінің кең класы дөңес жиында анықталған көптеген айнымалылардың дөңес функцияларын минимизациялаумен байланысты. Мұндай есептер дөңес бағдарламалау мәселелері (CVPs) деп аталады.

Математикалық программалау мәселесі

(12.1)

барлық функциялар дөңес функциялар болса, программалаудың дөңес есебі деп аталады.

Математиканың дөңес жиындар мен дөңес функциялардың қасиеттері зерттелетін және экстремалды есептерді шешудің теориясы мен әдістерінде іргелі рөл атқаратын саласы – дөңес талдау элементтеріне тоқталайық.

Дөңес талдау элементтері

Кейбір анықтамалар беріп, дөңес жиындардың нақты мысалдарын қарастырайық. Бұдан әрі біз соңғы өлшемді евклидтік кеңістіктің жиындарында анықталған функцияларды қарастырамыз.Е н .

Анықтама 12.1. Көптеген мейірімді

(12.2)

және нүктелерін қосатын кесінді деп аталады және арқылы белгіленеді.

Әлбетте, нүктеде X кесіндінің бір ұшымен (), at - екіншісімен () және at - кесіндінің кейбір ішкі нүктесімен сәйкес келеді.

Анықтама 12.2. Жиын деп аталадыдөңес , егер кез келген екі нүктемен және оларды қосатын кесіндімен бірге оған да тиесілі болса.

Жиынның дөңестігі жиынға жататындықтан барлығына тиесілі болатынын білдіреді.

Кесінді, жартылай түзу, түзу, шеңбер, үшбұрыш, жарты жазықтық және бүкіл жазықтық дөңес екені анық.

Бүкіл кеңістік дөңес жиынды құрайтыны анық. Бос жиынды және бір нүктеден тұратын жиынды дөңес деп қарастырған ыңғайлы.

12.1 теорема. Фаркас теоремасы.Өлшем матрицасы мен векторы берілсін. Теңсіздік барлығы үшін орындалады, егер осындай вектор бар болса ғана.

Дәлелдеу.Адекваттылық. Қарым-қатынастар және қанағаттанарлық болсын. Сонда кез келген вектор үшін болады

Қажет. Барлығына әділетті болсын. Конусты қарастырайық. Егер, онда теорема дәлелденеді. Солай етейік. 12.2-анықтама бойынша жиын дөңес және тұйық болады, сондықтан бөлу теоремасының күшімен мынандай вектор бар

(12.3)

барлығына.

Барлығы үшін болғандықтан (12.3) біз барлығына дегенді аламыз. білдіреді. Басқа жақтан. Яғни, бұл барлық адамдарға қатысты болғандықтан

. (12.4)

Бірақ, демек, (12.3) тармақтан шығады

. (12.5)

(12.4) және (12.5) тармақтарынан теореманың шарттарына қайшылықты аламыз.

Пікір. Фаркас теоремасының геометриялық түсіндірмесін берейік. Болсын

және. Конус - бұл векторлардың әрқайсысымен сүйір емес бұрыштар құрайтын барлық векторлардың жиынтығы. 12.1-суретте конус тік сызықтармен, ал конус көлденең сызықтармен боялған. Теореманың геометриялық мағынасы келесідей. Кез келген вектор үшін және арасындағы бұрыш, егер ол конусқа жататын болса, сүйір болмайды.

12.1-сурет

Анықтама 12.3. Дөңес жиында анықталған функция шақырыладыдөңес , егер кез келген нүкте және кез келген теңсіздік үшін

(12.6)

Функция шақырыладықатаң дөңес егер (12.6) теңсіздік қатаң түрде барлығы үшін орындалса. Функция шақырыладықатты дөңес , егер мұндай сан болса, (күшті дөңес тұрақты) теңсіздік

(12.7)

Әрбір қатты дөңес функция қатаң дөңес және одан да көп дөңес функция, бірақ керісінше емес.

Дөңес функцияның мысалы оң анықталған матрицасы бар квадраттық функция болып табылады.

Теорема 12.2. Дөңес жиында дөңес болатын функциялардың теріс емес коэффициенттері бар сызықтық комбинация берілген жиындағы дөңес функция болып табылады.

Дәлелдеу. Дөңес жиында анықталған функциялар дөңес болсын. функциясын көрсетейік

, (12.8)

қай жерде дөңес.

Ерікті нүктелер үшін және бастап және бізде кез келген сан

Бұл қатынастар тізбегінде бірінші теңсіздік ақиқат, өйткені функциялар дөңес. Алынған нәтиже (12.8) формуламен анықталған функция жиында дөңес екенін көрсетеді.

12.3 теорема. Егер дөңес жиында дөңес болса, онда Дженсен теңсіздігі орындалатын кез келген нүктелер мен сандар үшін

. (12.9)

Дәлелдеу (индукция бойынша). үшін (12,9) теңсіздік анық. Шынында да, егер, онда және, яғни. (12.9) теңдік ретінде орындалады. (12.9) орындалады делік, яғни, нүктелердің дөңес комбинациясы үшін. Көрсетейік, онда ол жиынтықтағы нүктелердің дөңес комбинациясы үшін де жарамды, яғни,

Оның үстіне, егер, онда (12.9) теңдігі де анық. Егер. Содан кейін дөңес және индуктивті болжамнан шығады

Жиын қанағаттандырады деп айтыладыжүйелілік шарты, егер әрқайсысы үшін осындай нүкте бар болса, яғни.

(12.10)

(12.10) шарты деп аталатын басқа шартқа эквивалент екенін көрсету оңайСлейтер заңдылық шарты.

12.4 теорема. Жиын заңдылық шартын қанағаттандырса(12.10) , содан кейін жиын Слейтерге сәйкес үнемі, атап айтқанда, барлық шектеулер қатаң түрде орындалатын нүкте бар

. (12.11)

Дәлелдеу. (12.10) заңдылық шарты орындалсын. Біз нүктелердің дөңес комбинациясы болып табылатын және, демек, тиесілі нүктені таңдаймыз. Содан кейін кез келген бізде болады

анау. . Бұл қатынастар тізбегінде бірінші теңсіздік Йенсен теңсіздігіне байланысты дұрыс, ал екіншісі қосындының кем дегенде бір мүшесі, атап айтқанда, қатаң аз болғандықтан. Бұл теңсіздіктер қарастырылып отырған шарттың Слейтер заңдылық шартын қанағаттандыратынын көрсетеді.

Біз дөңес функциялардың келесі маңызды қасиетін дәлелсіз келтіреміз.

Дөңес жиында анықталған дөңес функция осы жиынның әрбір ішкі нүктесінде үздіксіз және әрбір ішкі нүктеде кез келген бағытта туынды болады.

Біз жиі қолданатын дөңес дифференциалданатын функциялардың маңызды қасиеті келесі теорема арқылы белгіленеді.

12.5 теорема. Дөңес жиында дифференциалданатын функция кез келген және теңсіздікке жататын болса ғана дөңес болады.

. (12.12)

Дәлелдеу.Қажет . Көбірек болсын. Сонда кез келген және, () және теңсіздік болатын барлық үшін

немесе

қайда

Соңғы теңсіздікте шекке өтіп, біз аламыз

Адекваттылық . Енді жиынның кез келген екі нүктесі үшін (12.12) шарты орындалсын. Сонда тиесілілік нүктесі үшін теңсіздіктер ақиқат болады

Бірінші теңсіздікті, екіншісін көбейтіп, алынған теңсіздіктерді қосқанда, бізде болады

немесе бізде бар екенін ескерсек

яғни жиынтықтағы дөңес функция.

Анықталған дөңес функция өзінің ең кіші мәніне жеткен дөңес жиында нүктені табу есебін шешуде маңызды рөл атқаратын дөңес жиындағы дөңес функциялардың бірқатар экстремалды қасиеттерін қарастырайық: .

12.6 теорема. Дөңес жиындағы функцияның кез келген жергілікті ең кіші нүктесі ғаламдық минимум нүктесі болып табылады

Дәлелдеу. Функцияның жергілікті минималды нүктесі болсын. Содан кейін, жергілікті минималды нүктенің анықтамасы бойынша, бұл нүктенің теңсіздігі болатындай көршілестігі бар

. (12.13)

Бұл функцияның ғаламдық минимум нүктесі емес делік, яғни мұндай нүкте бар делік. Көзқарастың нүктелерін қарастырыңыз.

анау. . Бірақ бұл жергілікті минимум нүктесі болып табылатын шартқа қайшы келеді, өйткені жеткілікті кішкентай нүкте үшін нүкте (12.13) орын алатын маңайда болады.

Сондықтан жаһандық ең төменгі нүкте.

12.7 теорема. Дөңес жиындағы дөңес функцияның ең кіші нүктелерінің жиыны дөңес жиын болып табылады.

Дәлелдеу. Дөңес жиындағы дөңес функцияның минимум нүктелерінің жиыны болсын, яғни.

Біз кез келген екі нүктені таңдаймыз және. және дөңес жиын болғандықтан, кез келген үшін болады

және функцияның дөңестігін ескере отырып, бізде бар

Яғни. Оған қоса, бері функцияның ең төменгі мәні қосулы, содан кейін. Және, демек, яғни. . Демек, дөңес жиын.

12.8 теорема. Дөңес жиындағы қатаң дөңес функция ең көбі бір нүктеде өзінің минимумына жетеді.

Дәлелдеу. Дөңес жиында қатаң дөңес функция болсын, яғни. кез келген және барлығы үшін қатаң теңсіздік

= болсын.

Ондай бір нүкте бар делік

Сонда кез келген нүкте үшін нүкте жиынға жатады және функцияның қатаң дөңестігіне байланысты ол болады.

анау. . Бұл ең төменгі нүкте болып табылатын шартқа қайшы келеді. Сондықтан мәселенің мәні ерекше.

Тест тапсырмалары

1. Дөңес программалау есебінің тұжырымын келтіріңіз.

2. Дөңес жиынды анықтаңыз.

3. Фаркас теоремасының тұжырымын келтіріңіз.

4. Фаркас теоремасының геометриялық түсіндірмесін беріңіз.

5. Дөңес жиында дөңес, қатаң дөңес және қатты дөңес функцияны анықтаңыз.

6. Дөңес функцияларға мысалдар келтір.

7. Жиын заңдылығының шартын тұжырымдаңыз.

8. Слейтер, жиындар бойынша заңдылық шартын тұжырымдаңыз.

9. Функцияның дөңес болуының қажетті және жеткілікті шартын көрсетіңіз, дифференциалданатындөңес жиынтықта .

10. Дөңес жиындағы дөңес функциялардың негізгі экстремалды қасиеттерін көрсетіңіз.

131-бет

Есептердің бұл класын қарастыру әдетте презентациядан басталады анықталмаған Лагранж көбейткіштері әдісі.Ол үшін /(x b..., X")және g(x b ..., X")- үзіліссіз функцияларды олардың жартылай туындыларымен бірге әзірше айнымалылардың теріс еместігінің шарттарын алып тастап, шартты экстремумға келесі есепті тұжырымдаймыз:

Оның шешімін табу үшін енгіземіз Лагранж көбейткіштері y / = 1, Тжәне деп аталатынды жасаңыз Лагранж функциясы:

оның барлық айнымалыларға қатысты жартылай туындыларын табу және нөлге теңестіру

жүйені алды n + tбелгісіздерге арналған теңдеулер x b x p,

Ui -, Жоғары-

Егер функция f(x сағ ..., X")нүктесінде экстремумы бар, онда мұндай Y векторы бар (0> = (y, 0 ,...,) y°) (А r(0) , F (0)) нүктесі (2.23) жүйесінің шешімі екенін. Сондықтан (2.23) жүйені шеше отырып, функцияның (2.20) экстремум болуы мүмкін нүктелерді аламыз. Әрі қарай табылған нүктелер шартсыз экстремумға есепті шешу кезіндегідей зерттеледі.

Осылайша, Лагранж көбейткіш әдісі келесі қадамдарды қамтиды.

• 1. Лагранж функциясын құрастырыңыз.
• 2. қатысты дербес туындыларды табыңыз Xjжәне у,Лагранж функциясынан алып, оларды нөлге теңестіріңіз.
• 3. Шешу жүйесі (2.23), мақсат функциясының экстремум болуы мүмкін нүктелерді табыңыз.
• 4. Экстремумға үміткер ұпайлардың арасынан экстремумға жеткендерін тауып, функцияның мәндерін есептеңдер. f(x, ..., X")осы нүктелерде.

Сипатталған әдіс дөңес программалау есептеріне қолданылады, яғни. мақсат функциясы дөңес (немесе ойыс) және шектеулермен анықталатын орындалатын шешімдер облысы да дөңес болатындарға.

Анықтама 1.Функция f(x,..., x n),дөңес жиынтықта анықталған x,кез келген нүктелер үшін дөңес деп аталады X, X 2бастап Хекез келген сан үшін x, 0 X 1

Анықтама 2.Функция/(*, X„) дөңес жиынтықта анықталған x,кез келген нүктелер үшін ойыс деп аталады X X, X 2бастап Хекез келген сан үшін x, 0 X

Анықтама 3.Дөңес бағдарламалау мәселесінің мүмкін шешімдерінің жиынтығы, егер кем дегенде бір нүкте бар болса, заңдылық шартын қанағаттандырады. xj,рұқсат етілген шешімдер саласына жатады, ол үшін g^XJ) =b h i = 1, Т.

Теорема 1.Дөңес программалау мәселесінің кез келген жергілікті экстремумы ғаламдық болып табылады.

Анықтама 4.Дөңес программалау есебінің Лагранж функциясы функция болып табылады

мұндағы y – Лагранж көбейткіші.

Анықтама 5.Нүкте (X (0) , T(0)) = (x,°,..., X (',y, 0,..., кезінде» ) шақырды Лагранж функциясының седла нүктесі,егер

Біз көмекші сипаттағы екі қысқа теореманы береміз.

2-теорема.Оңтайлы жоспар X (0)тапсырмалар NP- бұл

мұндағы DA) – шарттарды қанағаттандыратын сызықты емес дифференциалданатын функция

функцияның градиенті қайда/

А нүктесінде» (0).

Дәлелдеу.

Тейлор қатарындағы мақсат функциясын нүктеге жақын жерде кеңейтейік X (())

қайда OH- өсу векторы X (0) ;

I – вектордың нормасын (ұзындығын) белгілеу.

(2.26) өрнектен шығатыны, егер х| векторының координатасының кез келген мәні болса 0) > 0, содан кейін туынды

, өйткені ішінде әйтпесекоординатасы бойынша x kмүмкін,

Қалған айнымалылардың тұрақты мәндерімен мақсат функциясын минимизациялауды жалғастырыңыз, егер туынды нөлден үлкен болса x[ 0) мәнін азайтыңыз немесе көбейтіңіз xfтуынды аз болса

нөл. Егер x| 0) = 0, онда ол болуы керек қаншалықты

әйтпесе мәнді төмендетуге болатын еді f(X м), 4 0) басқа айнымалылардың мәндерін өзгертпей Ax* мәніне ұлғайту. Сондықтан кез келген үшін Кімгетеңдік сақталады:

Теорема дәлелденді.

Енді Лагранж функциясының седл нүктесінің болуының қажетті және жеткілікті шарттарын анықтайық.

Теорема 3.Теріс емес координаталары бар нүкте (A 10 *, ЖӘНЕ 0)) дифференциалданатын функцияның седла нүктесі болуы үшін L(X, Y),шарттар орындалуы керек:

Дәлелдеу.

1) Қажет.(X (0) , Y "(0)) седла нүктесі болсын, яғни:

(2.29) формуласы өрнекке баламалы

(2.29) және (2.30) негізінде (2.27) және (2.28) шарттар орындалады. Қажеттілік осылайша дәлелденді.

• 2) Адекваттылық.(2.27) және (2.28) шарттары орындалды деп алайық. Функцияны кеңейтіңіз L(X, Y)нүктеге жақын Тейлор қатарында

Кеңейтуден (2.31) және (2.27) және (2.28) шарттарды ескере отырып, мынандай нәтиже шығады:

Соңғы екі өрнек (2.29) формулаға тең. Теорема дәлелденді.

Жоғарыдағы теоремалардан кейін біз қазір іс жүзінде айқын Кун-Такер теоремасын тұжырымдаймыз.

4-теорема (Кун – Такер).(2.20) - (2.21) дөңес программалау есебі үшін орындалатын шешімдер жиыны заңдылық қасиетіне ие, нүкте X (0) =(xj 0 *,..., x' 0)), x, - 0> >0, / = 1, ПТ =(y 1 (0) ,..., yi 0)), Y/ 0) >0, / = 1, осындай вектор болған жағдайда ғана оңтайлы жоспар болып табылады. Т,(T (0) , H 0>) нүктесі Лагранж функциясының седла нүктесі болып табылады.

Егер дөңес программалау есебінде (2.20) - (2.21) мақсаттық функция мен шектеулер үздіксіз дифференциалданатын болса, онда Кун - Такер теоремасын (Х (0)) нүктесі үшін қажетті және жеткілікті шарттарды анықтайтын аналитикалық өрнектермен толықтыруға болады. , Y i (l), ) Лагранж функциясының седла нүктесі болды, яғни. дөңес программалау мәселесінің шешімі болды. Бұл (2.27) және (2.28) өрнектері. Оларды квадраттық бағдарламалау мәселесі қанағаттандырады. Оның түпкілікті тұжырымы үшін біз бірнеше анықтамалар мен бір теореманы береміз.

Анықтама 6. X[, ..., айнымалыларына қатысты квадраттық пішін X"осы айнымалылардың сандық функциясы деп аталады, оның келесі формасы бар:

Анықтама 7.квадраттық пішін Фегер оң/теріс анықталған деп аталады F(X) > 0/F(X) 0 векторды құрайтын айнымалылардың барлық мәндері үшін x.

Анықтама 8.квадраттық пішін Фегер оң/теріс жартылай анықталған деп аталады F(X") > O / YES») X, және, сонымен қатар, мұндай айнымалылар жиынтығы бар - вектордың құрамдас бөлігі X",не F(X") = 0.

5-теорема.Квадрат пішін оң/теріс жартылай анықталған болса, дөңес/ойыс функция болады.

Анықтама 9. Функцияның мәнін кішірейту/максимизациялау тапсырмасы

шектеулер астында

мұндағы оң/теріс жартылай анықталған квадраттық пішін, деп аталады квадраттық бағдарламалау мәселесі(ЗКП).

Бұл мәселе үшін Лагранж функциясының пішіні бар:

Егер Лагранж функциясының седла нүктесі болса, онда (2.27), (2.28) шарттар орындалады. Енді теңсіздіктерді теңдікке айналдыратын қосымша айнымалыларды енгізе отырып (бұл әдіс LP есептерін шешуде де қолданылады), біз бұл шарттарды келесі түрде жазамыз:

RFP шешімін табу үшін сызықтық жүйенің теріс емес шешімін анықтау керек. алгебралық теңдеулер(2.32). Мұндай шешімді табуға болады жасанды негіз әдісі,жасанды мақсат функциясының ең кіші мәнін табу үшін қолданылады F = ^Pj, whereru-жасанды айнымалылар. Әдіс, қалай-

Шекті қадамдар ішінде ол оңтайлы жоспарды табатыны немесе мәселенің шешілмейтіндігін белгілейтіні белгілі.

Сонымен, RFP шешімін табу процесі келесі қадамдарды қамтиды.

• 1. Лагранж функциясын құрастырыңыз.
• 2. (2.27), (2.28) өрнектер түрінде Лагранж функциясының седла нүктесінің болуының қажетті және жеткілікті шарттарын жазыңыз.
• 3. Жасанды базис әдісін қолданып, Лагранж функциясы үшін седла нүктесінің жоқтығы белгіленеді немесе оның координаталары табылады.
• 4. Бастапқы есептің оңтайлы шешімін жазып, мақсат функциясының мәнін табыңыз.

Бастауышты қарастырыңыз сандық мысал(No1) И.Л.Акуличтің кітабынан « Математикалық бағдарламалаумысалдар мен тапсырмаларда. Өндіріс жоспары бойынша кәсіпорын 180 өнім шығаруы тиіс. Оларды екі технология арқылы жасауға болады. Өндірісте X 1-ші жолмен өнімдер, шығындарды құрады xf+4x, руб., және өндірісте x 2өнімдер 2-ші жолмен олар тең x + 8х 2 руб. Тапсырыс құнын азайту үшін әрбір әдіс қанша элемент шығару керектігін анықтаңыз.

Шешім.Келесі функцияны азайту керек:

жағдайларда:

Бұл жағдайда Лагранж функциясы келесідей болады:

қатысты осы функцияның ішінара туындыларын есептейік X, x 2, yжәне оларды нөлге теңестіріңіз:

Бірінші және екінші теңдеуде көшіру сағоң жаққа және сол жақтарды теңестірсек, біз айқын қысқартулардан кейін аламыз:

Бұл теңдеуді жүйенің үшінші теңдеуімен бірге шешсек, біз оны табамыз Бұл нүкте экстремумға үміткер болып табылады.

Екінші жартылай туындыларды пайдаланып, табылған нүкте функцияның шартты минимумы екенін көрсету оңай /

Жоғарыда қарастырылғанға ұқсас мәселелер көптеген экономикалық тәжірибелерде алға қойылған. Рас, нақты есептер әдетте көптеген айнымалылар мен шектеулерді қамтиды, бұл оларды компьютерді қолданбай шешуді мүмкін емес етеді. Дегенмен, стандартталған пайдалану тиімділігі бағдарламалық қамтамасыз етуЭЕМ орындайтын түрлендірулердің мәнін зерттеушінің білуімен анықталады. Бұл оған оңтайландыру мәселелерін шешу үшін ұсынылған әдістердің, есептеу процедураларының және бағдарламалық жүйелердің жиынтығында дұрыс бағдарлануға көмектеседі.

Тақырыпты бекіту үшін басқасын қарастырыңыз сандық мысал(№ 2). Функцияның ең үлкен мәнін табыңыз

жағдайларда:

Шешім./ функциясы ойыс, өйткені ол сызықтық функцияның қосындысы f \u003d 2x 2 + 4x bойыс деп санауға болатын және квадраттық пішінді / 2 = -x -2x1,бұл теріс анықталған. Шектеулер тек сызықтық шектеулерді қамтиды. Сондықтан Кун-Такер теоремасын және ZKP шешу схемасын қолдануға болады.

1. Лагранж функциясын құрастырыңыз:

2. Функцияның седла нүктесінің болуының қажетті және жеткілікті шарттарын жазайық Л.

3. Сызықтық теңсіздіктер жүйесіне v b V2 қосымша теріс емес айнымалыларды енгізейік, w, w2,теңсіздіктерді теңдікке айналдыру. Теңдеулер жүйесін аламыз:

Бұл жағдайда, әрине, келесі шарттар орындалады:

Лагранж функциясының седль нүктесінің координаталарын анықтау үшін (2.33) теңдеулер жүйесінің негізгі шешімін табу керек. Осы мақсатта біз жасанды негіз әдісін қолданамыз. Жасанды мақсат функциясын минимизациялау

қайда Зи, Зи- жасанды айнымалылар, шарттар бойынша:

Мұнда айқын негізгі орындалатын шешім келесідей көрінеді:

мақсатты функция Фнегізгі емес айнымалылар арқылы көрсетіңіз:

Талқылауды аяқтай отырып, оның Xj (0) = 1, = 1 және нөлдік мәндері бар басқа айнымалылар үшін жойылатынын ескереміз. Осылайша, T (0) = (1, 1) бастапқы есептің оңтайлы жоспары,

Пішіннің теңсіздіктер жүйесі болсын

(4.3) және функция

Z = f (x 1 , x 2 , …, x n), (4.4)

оның үстіне кейбір дөңес M жиынында барлық функциялар дөңес, ал Z функциясы M жиынында дөңес немесе ойыс болады.

Дөңес программалау мәселесі – Z мақсат функциясы өзінің ең кіші мәніне немесе Z ойыс функциясы ең үлкен мәніне жеткен шектеулер жүйесінің (4.3) осындай шешімін табу. (Айнымалылардың теріс еместігінің шарттарын (4.3) жүйесіне енгізілген деп санауға болады).

3 0 қасиетін ескере отырып, кез келген сызықтық бағдарламалау есебі дөңес программалау есебінің ерекше жағдайы болып табылады. Жалпы алғанда дөңес программалау есептері сызықты емес программалау есептері болып табылады. Дөңес программалау есептерін арнайы классқа бөлу дөңес функциялардың экстремалды қасиеттерімен түсіндіріледі: дөңес функцияның кез келген жергілікті минимумы (ойыс функцияның жергілікті максимумы) бір уақытта глобальді болады; сонымен қатар, 2 0 қасиетін ескере отырып, тұйық шектелген жиында анықталған дөңес (ойыс) функция осы жиында ғаламдық максимумға және ғаламдық минимумға жетеді. Демек, бұл мынадай егер Z мақсаттық функциясы қатаң дөңес (қатаң ойыс) болса және шектеулер жүйесінің шешу облысы бос және шектелген болмаса, онда дөңес программалау мәселесі әрқашан бірегей шешімге ие болады.

F(X) = F(x 1 , x 2 , …, x n) функциясы деп аталады. бөлінетін, егер ол функциялардың қосындысы ретінде ұсынылуы мүмкін болса, олардың әрқайсысы тек бір айнымалыға тәуелді, яғни. егер

(кейбір i үшін F i (x i) = 0 болуы мүмкін).

Шектеулер жүйесі (4.3) және мақсаттық функция (4.4) дөңес программалау есебінде берілсін және Z мақсаттық функциясы да, барлық шектеулер де ажыратылатын болсын. Сонда тапсырма келесідей болады:

Дөңес (максимум - ойыс) функцияның минимумын табыңыз

шектеулер астында

Бөлшектік сызықтық жуықтау әдісінің идеясы мынада: барлық f i және барлығы түзу кесінділерден тұратын сынық сызықтармен ауыстырылады. Бұл жағдайда дөңес программалаудың бастапқы есебі жаңа, жуық есеппен ауыстырылады, ол сызықтық программалау мәселесі болып табылады. Бұл есеп әдетте симплекс әдісімен шешіледі, ал оның шешімі бастапқы дөңес программалау есебінің жуық шешімі болып табылады.

Сурет 12. Бөлшектік сызықты жуықтау әдісі арқылы дөңес программалау есебін шешу

Жуық есеп құру үшін аралықта берілген бір h(x) айнымалысының функциясының бөліктік сызықтық жуықтауын қарастырыңыз. Осы кесіндіні r бөлікке х 0 нүктелері арқылы бөлейік

(x k ; h k) және (x k+1 ; h k+1) нүктелері арасындағы полисызық қимасының теңдеуі (екі нүктедегі түзудің теңдеуі) түрінде болады. Егер осы теңдіктегі қатынастың әрқайсысы арқылы белгіленсе, онда мынаны аламыз:

Әрқайсысы үшін шарттарды қанағаттандыратын бірегей мән бар екенін ескеріңіз (4.7). Белгілей отырып, (4.7) келесі түрде қайта жазуға болады:

[(4.8) теңдеулер кесіндінің параметрлік теңдеулері деп аталады.

Егер h(x) = 0 болса, онда бұл теңдеулердің екіншісі 0 = 0 сәйкестігіне айналады, ал біріншісі (4.1) - х осінде жатқан кесіндінің теңдеуі] түрін алады.

Сонымен, кез келген полисызық теңдеуін былай жазуға болады:

және тек екі мән әрқашан нөлден (егер x бөлімнің k-ші сегментінің ішкі нүктесі болса) немесе біреуінен (егер x сегменттің соңына сәйкес келсе) ерекшеленеді.

Бөлінетін функциялары бар дөңес программалау мәселесіне оралсақ, ең алдымен (шектеулер жүйесіне байланысты) әрбір айнымалының өзгеру интервалын анықтау қажет екенін ескереміз x j . Содан кейін әрбір интервал x jk нүктелері арқылы бөліктерге бөлінеді және (4.9) формулаларын пайдаланып f j және функциялары үшін бөліктік сызықтық жуықтау құрастырылады. Осыдан кейін бастапқы есеп (4.6) үшін жуық есептерді жазуға болады:

Функцияның максимумын табыңыз

шектеулер бойынша (4.10)

(4.10) жуық есеп әдетте симплекс әдісімен шешілетін сызықтық программалау мәселесі болғандықтан, айнымалылардың теріс еместігінің шарттары қалған шектеулерден бөлек жазылады.

Алынған есептің (4.10) кәдімгі сызықтық бағдарламалау есебінің айырмашылығы мынада: әрбір xj үшін ең көбі екі көрші нөл емес бір болады, сондықтан j бірдей және көрші емес k екеуі негізгі айнымалылар ретінде қабылданбайды. . Сондай-ақ, f j (x j) және (бар болса) айнымалы мүшелерінің теріс емес шарттары үшін бөліктік сызықтық жуықтау, әрине, қажет емес екенін ескереміз.

Бұл тарауда біз кәсіпорындарда тиімді шешімдер қабылдау үшін менеджерлер қолданатын кейбір оңтайландыру әдістерін ғана қарастырдық. Дегенмен, сипатталған әдістер экономикада математикалық аппаратты пайдаланудың негізгі принципін түсінуге мүмкіндік береді, бұл әртүрлі балама нұсқалардың ішінен белгілі бір нақты жағдай немесе жағдай үшін ең жақсысын таңдауға мүмкіндік береді.

Математикалық бағдарламалаудың пәні болып табылатын практикалық экономикалық жағдайлардың үлкен саны не сызықтық есептерге мүлдем келтірілмейді, немесе (тіпті мұндай сызықтандыру белгілі бір кезеңде жүзеге асырылса да) әлі де егжей-тегжейлі қарастыру әрекеті. сызықтық еместігіне әкеледі.

Сызықты емес программалаудың ең жалпы есебін келесідей тұжырымдауға болады:

m теңдеуді немесе түрдегі теңсіздіктерді қанағаттандыратын n айнымалы x 1 , x 2 , ..., x n мәндерін анықтау қажет.

i = 1, 2, ..., m.

және максималды (немесе ең аз) мақсат функциясына түрлендіру

f (X) \u003d f (x 1, x 2, ..., x n).(2.2)

f және g i сызықты емес берілген функциялар, b i белгілі тұрақтылар деп есептейік. Әдетте айнымалылардың барлығы немесе кем дегенде кейбіреулері теріс емес болуы керек деп есептеледі.

Сызықтық бағдарламалаудың нақты жағдайында f және g i функциялары сызықтық болады деп болжанады, яғни.

Осыдан басқа кез келген басқа математикалық бағдарламалау есептері сызықты емес есептер болып саналады.

Математиканың сәйкес салаларында әртүрлі типтегі функциялардың максимумдары мен минимумдарын анықтаудың жалпы (классикалық) әдістері жасалған. Алайда есептерді шешудің мұндай жалпы тәсілі іс жүзінде сандық нәтижелерді алу үшін шектеулі қолданылады, өйткені ол көптеген белгісіздері бар сызықтық емес теңдеулер жүйесін шешу қажеттілігіне әкеледі және шеткі экстремаларды табу үшін жарамсыз. Сондықтан математикалық бағдарламалауда негізінен алгоритм қызметін атқара алатын әдістер, яғни нақты экономикалық қолданбалы арнайы есептерді сандық шешудің есептеу процедурасы зерттеледі. Осы мәселелердің кейбірін көрсетейік.

Сызықтық шектеулер мен сызықтық емес мақсат функциясы бар есептер барынша мұқият зерттелген. Бірақ бұл есептер үшін де есептеу әдістері мақсат функциясы белгілі бір қасиеттерге ие болған жағдайда ғана жасалған. Атап айтқанда, мысалы, мақсат функциясы ретінде ұсынылуы мүмкін

мұндағы f j (x j) функциялары өз кезегінде белгілі бір шектеулерге ұшырауы керек. Бұл бөлінетін функция деп аталады. Басқа жағдайда мақсат функциясын сызықтық және квадраттық функциялардың қосындысы ретінде жазуға болады:

Мұндай типтегі сызықтық емес есептер квадраттық бағдарламалау есептері деп аталады. Оңтайлы шешімді табу үшін d ij мәндеріне кейбір қосымша шектеулер қойылуы керек.

Сызықты емес шектеулермен есептер сызықтық шектеулермен салыстырғанда қиынырақ. Бұл есептердің оңтайлы шешімін алу үшін g i және f функцияларына өте қатаң талаптар қойылуы керек. Атап айтқанда, сызықты емес есептің оңтайлы шешімін алуға болады, егер сызықтық емес теңсіздіктермен берілген gi шектеулері Айнымалылар кеңістігіндегі дөңес жиынды анықтаса (1-тарауды, § 3-ті қараңыз) және мақсат функциясы сызықты емес тегіс дөңес немесе ойыс функция болса. . Келесіде дөңес және ойыс функциялардың қатаң анықтамасы беріледі. Мұнда тек f функцияларының дөңестік қасиеті бір ғана минимумның болуын қамтамасыз ететінін, ал f-тің ойыс қасиеті шектеулермен көрсетілген аймақ ішінде бір ғана f максимумының болуын қамтамасыз ететінін ғана атап өту қажет. Бұл мақсат функциясының оңтайлы мәнін анықтау алгоритмдерінің негізі болып табылады. Дөңес немесе ойыс болмаған жағдайда математикалық бағдарламалау есебінің шешімі жалпы жағдайда классикалық әдістерді қолдану арқылы табуға болатын жергілікті минимумдар немесе максимумдардың болуымен кездеседі.