Кун-Таккер теоремасы және квадраттық программалау

Кіріспе

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

Пән: Математика, Геометрия
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 57 бет
Таңдаулыға:

Ф-ОБ-011003

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ
ҒЫЛЫМ МИНИСТРЛІГІ

Қ.А.Ясауи атындағы Халықаралық қазақ-түрік университеті

Математика кафедрасы

БЕКІТЕМІН
Кафедра меңгерушісі
техн.ғ.д., профессор
______________Ә.Мұратов

Д И П Л О М Д Ы Қ Ж Ұ М Ы С

Тақырыбы: Кун-Таккер теоремасы және квадраттық
программалау

Орындаған: ЖМА-711 Абдулсаматқызы З.

Тобы, студенттіњ аты-жөні
Ғылыми жетекшісі: проф. Көлекеев К.

Түркістан 2011
І.Негізгі түсініктер.

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

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

(2.1)

қанағаттандыратын және

(2.2)

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

(2.3)
және

(2.4)
мұндағы және - белгісіз тұрақтылар, болса, онда шешімнің теріс
емес болу шартынан сызықтық программалау есебін аламыз. Математикалық
программалаудың (2.3) және (2.4) шарттарын қанағаттандырмайтын кез-келген
басқа есебін сызықты емес деп айтамыз.
Сызықты емес программалау есебі класы сызықты программалау есебі
класынан ауқымдырақ. Сызықтық деп есептелінетін практикалық есептерді толық
зерттеу нәтижесі олардың шын мәнінде сызықтық емес екендігін көрсетеді.
Сызықты программалау есептері шешімдерінің тиімдісін табу мәселесі
туындайды. Белгілі әдістердің барлығы есепті (2.3) түріндегі шағын
кластарда ғана шешуге арналған, ал мақсаттық функция сепарабелдік немесе
квадраттық функция болады. Тіпті шешім алынған облыс дөңес облыс болса,
онда есептер қатарында мақсаттық функция бірнеше локалді экстремумға ғана
ие болуы мүмкін. Көптеген есептеу әдістерінің көмегімен локалді оптимум
нүктесін табуға болады, бірақ, ол глобалдік (абсолюттік) оптимум нүктесі
болатын, болмайтынын анықтау мүмкін емес. Егер сызықтық программалау
есептерінде шешімнің экстремум нүктесі көпжақтың төбесі болса, онда сызықты
емес программалау есептерінде көпжақтың төбесінде, қабырғасында немесе
облыстың ішінде жатуы мүмкін. Егер есеп сызықты емес шектеулі болса, онда
шешім алынған облыс дөңес болмайды, сондай-ақ глобалдік оптимумнан басқа
локалдік оптимум нүктесі табылуы да мүмкін.
Екі айнымалылы сызықтық емес прораммалау есептеріне мысалдар
келтірейік. Сызықтық программалау есебі сияқты бұл да графикалық түрде
шешіледі.

2.1-сурет 2.2-сурет

1-мысал. сепарабелдік функциясының

, .

шектелуідегі ең үлкен және ең кіші мәнін тап.
Шешілуі. Шешім алынған облыс (2.1 сурет) көпбұрышы болады. Егер
десек, онда түріндегі шеңбер теңдеуін аламыз. -дің мәнін
азайтсақ (арттырсақ) сәйкесінше функциясының мәні азаяды (артады).
нүктесінен радиусы әртүрлі шеңбер жүргізу арқылы келесіні
аламыз: функциясы ең кіші мәнге нүктесінде ие болады. Ал,
шеңбер шешімнің облысын жанайды. нүктесі бұрыштық емес болады. Оның
координаталары және түзулеріне сәйкес теңдеулер жүйесін шешу
арқылы табылады.
функциясы екі локалдік максимумға ие болады: төбесінде
функциясы, төбесінде функциясы. болғандықтан
нүктесі глобалді максимум нүктесі болып табылады.
2-мысал. Шешім алынған облыс бұрынғысынша қалсын, ал, болсын.
Осы функцияның ең үлкен және ең кіші мәнін табу керек.
Шешілуі. Функция ең кіші мәніне нүктесінде ие болады (2.2
сурет): . функциясы екі локалді максимумға ие болады:
төбесінде функциясы, төбесінде функциясы, ал, глобалді
максимумге нүктесінде ие болады.
3-мысал. функциясының

, .

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

Лагранж көбейткіштері әдісі.
2.3-сурет
Айталық математикалық программалау есебі берілген болсын:

(2.5)

функциясына максималды мән беретін

(2.6)

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

(2.7)

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

(2.8)

(2.7) өрнекпен анықталған функция Лагранж функциясы, ал, -
Лагранж көбейткіштері деп аталады. Егер функциясы нүктесінде
экстремумға ие болса, онда (2.8) жүйесінің шешімі нүктесі болатындай
векторы табылады. Нәтижесінде, (2.8) жүйені шешу арқылы
функциясы экстремалды мәнге ие болатындай нүктелер жиыны табылады. Сондай-
ақ бұл жағдайда глобалді максимум немесе минимум нүктелерін анықтау әдісі
белгісіз болады. Бірақ, егерде жүйенің шешімі табылса, онда глобалді
максимум (минимум) нүктесін анықтау үшін сәйкес нүктелердегі функцияның
мәнін тапсақ жеткілікті. Егер және функциялары үшін олардың
екінші ретті туындылары бар, үзіліссіз болса, онда (2.8) жүйенің шешімі
болатын нүктеде функцияның локалді экстремумының бар болу шартын шығаруға
болады. Бірақ, бұл шарттың практикалық құндылығы жоғары емес.
Заңдылық бойынша (2.8) жүйесінің бірнеше шешімі бар болатындықтан
Лагранж көбейткіштері әдісі шектеулі қолданысқа ие болады. Лагранж
көбейткіштері әдісін қолданған бірнеше мысал келтірейік.
1-мысал. функциясының

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

.

Бірінші және үшінші теңдеуден болатыны шығады; онда

.

Соңғы теңдеулер жүйесін шешу арқылы келесіні аламыз: , .
2-мысал. Құрылғының дұрыс жұмыс істеуін қамтамасыз ету үшін
теңгелік бағаға қосалқы бөліктің түрін сатып алу қажет. Бірнеше
детальдің бағасы -ға тең. Мұндағы қажеттілік параметрімен
берілген көрсеткіштік үлестіру заңдылығына ие болған кездейсоқ шамасы
болады. -ші детальді қолдану -ға тең пайда алып келеді. Қажет
сәтте деталдің болмауы -ға тең шығын алып келеді. Егер деталді дер
кезінде қолданбаса, онда шығын -ға тең болады. Жалпы пайда максималды
болу үшін бұйымдарды қалай үлестіру керек?
Шешілуі. деп -ші детальді сатып алуға бөлінген сомманы
белгілейік. Онда түрдегі деталь сатып алынған болады. Барлық
айнымалыларды үзіліссіз деп есептейміз. Түскен пайданы анықтаймыз:
болса, пайда -ға тең,
болса, пайда -ға тең болады. -ші детальдің болмауынан
болған шығынның мәні нөлге тең, егер , және -ға тең, егер
болса. Бар детальдардың қолданылмауынан келген шығын нөлге тең, егер
болса, және -ға тең, егер болса.
детальдің жалпы пайдасын анықтайық:

.

деталь бойынша жалпы пайда келесіні құрайды:

.

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

функциясының шектелуіндегі максималды мәнін тап.
Есепті шешу үшін Лагранж функциясын құрып аламыз:

.

Ескерту. Дифференциалдау кезінде келесі формула қолданылды: егер

болса, онда

.

Дербес туындыларын нөлге теңестіру арқылы келесіні аламыз

Берілген жүйені шешу арқылы мәнін табамыз.
Айталық, , , ал , , , және
мәндері 2.1 таблицамен берілген.

i aj bj cj rj qj
1 0,25 20 30 18 12
2 0,15 25 22 18 10
3 0,1 30 25 15 10

2.1. таблица.

Онда теңдеулер жүйесі келесі түрде жазылады:

Теңдеулер жүйесінің шешімі , және мәндері болады,
яғни, бірінші түрдегі деталдан 6, екінші түрдегі деталдан 10, үшінші
түрдегі деталдан 15. Жалпы пайданы табамыз :

;

;

;

.

Ескерту. , , мәнін есептеуде

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

§3. Дөңес және ойыс функциялар.

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

(2.9)

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

(2.10)

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

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

.

және нүктелері үшін және шарттары орындалады.
Онда барлық үшін

.

Демек,

және ,

дәлелдеу керегі де осы болатын.
Дөңес жиындардың қиылысуы дөңес болады, сондықтан
шарттарын қанағаттандыратын барлық нүктелер жиыны дөңес болады, егер
теңсіздікте таңбасы болғанда - дөңес функция, ал,
таңбасы болғанда - ойыс функция болса. Функцияның ойыс және дөңес
болуын анықтағанда оның үзіліссіздігі немесе дифференциалдануы талап
етілген жоқ. Егер функциясы жиынының ішкі нүктесінде үзіліссіз,
дифференциалданатын және дөңес болса, онда келесі нәтижені алуға болады.
(2.9) өрнегінен үшін келесіні аламыз:

;

онда Тейлор формуласы бойынша

,

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

.

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

(2.11)

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

(2.12)

жиыны дөңес, сондықтан үшін нүктесі жиынының
өзіне тиісті болады. (2.12) теңсіздігін жақсартуға болады, егер
орнына қоятын болсақ. Онда

.

мәнін нүктесі мүмкін болғанша нүктесіне жақын
орналасатындай етіп таңдауға болады. Онда нүктесінің локальді минимум
болатынын, сондай-ақ бұл жағдайда нүктесіне жақын нүктеде функция
нүктесінде қабылдайтын мәнінен кішірек мән қабылдайтынын ескерсек
қарама қайшылық шығады. Теорема дәлелденді.
1-тұжырым. Егер глобальді минимум әр түрлі екі нүктеде бар болса,
онда ол осы нүктелерді қосатын кесіндінің кез келген нүктесінде де бар
болады.
2-тұжырым. Егер қатаң дөңес функция болса, онда оның
дөңес жиынындағы глобальді минимумы тек бір ғана нүктеде болады.
2.2-теорема. Айталық функциясы берілген дөңес жиынында
дөңес функция болсын, сонымен қатар өзі және бірінші ретті дербес
туындылары жиынының ішкі нүктелерінде үзіліссіз болсын. Айталық
нүктесі үшін болсын. Онда ол нүктесінде глобальді минимуммен
беттесетін локальді минимум нүктесіне ие болады.
Дәлелдеуі. Айталық нүктесі жиынының кез келген нүктесі
болсын. (2.11) өрнегінде , деп аламыз. Дәлелдеу керегі де
осы болатын. Ондай болса, дөңес функциясы өзінің глобальді минимумына
жиынының орындалатын әрбір нүктесінде ие болады.
Егер - тұйық, төменгі жағынан шенелген, дөңес жиын болса, онда
дөңес функциясы өзінің глобальді максимумына осы жиынның бір немесе
бірнеше нүктесінде ие болатынын (сонымен қатар нүктесінде
функциясының мәні ақырлы деп есептейміз) көрсетуге болады. Осындай
есептерді шешуде шеткі нүктелерді таңдау процедурасын қолдану арқылы
локальді максимум нүктесін табуға болады (2.2.-сурет), бірақ бұл нүкте
глобальді максимум болатынын айта алмаймыз.
Дөңес функциялар үшін қарастырылған нәтижелерді келесі түрде
өрнектеуге болады. Айталық, - функциясы тұйық, дөңес жиында
дөңес функция болсын. Онда жиынынан алынған функциясының кез
келген локальді максимумы глобальді максимум нүктесі болып табылады. Егер
глобальді максимум жиынның әр түрлі екі нүктесінде бар болса, онда ол осы
екі нүктені қосатын кесіндіде жататын барлық нүктелер жиынында да глобальді
максимумға ие болады. Қатаң дөңес функция үшін глобальді максимум нүктесі
жалғыз болады.
- дөңес функциясының градиенті нөлге тең, егер
дифференциалданатын функция болса. Егер дөңес функция тұйық, төменгі
жағынан шенелген жиында ақырлы болса, осы жиынның әрбір нүктесінде ақырлы
болса, онда глобальді максимум осы жиынның бір немесе бірнеше нүктесінде
бар болады.

§4. Сепарабельді функциялар қатысқан есептерді шешудің жуықтау
әдістері.
Сызықты емес программалау есептерін шешудің жуықтау әдістерінің бірін
қарастырайық.
функциясының

(2.13)

шектеуіндегі максималды мәнін табу керек.
Барлық мақсаттық функция және шектеулер жүйесіндегі функциялар
сепарабельдік функция болады.
Жуықтау әдісі және функцияларының құрама-сызықты
аппроксимациясына негізделіп жасалған. Сонымен қатар шешімі симплекс
әдісімен табылатын жуықтау есебі орынды болады. Жалпы жағдайда жуықтау
есебінің локальді максимумы және (2.13) есебінің жуық локальді максимумы
анықталады.

2.5-сурет
Егер шешім алынған жиыны дөңес, ал - ойыс функция болса, онда
локальді максимум нүктесі бір уақытта глобальді максимум нүктесі де болады.
Бұл жағдайда (2.13) есебінің шешімі үшін жуық глобальді максимум нүктесі
болатын жуықтау есебінің глобальді максимум нүктесі табылады.
(2.13) есебі үшін жуықтау есебінің қойылуын қарастырамыз. Айталық,
кесіндісінде анықталған, бір айнымалы, үзіліссіз функциясы
берілген болсын (2.5-сурет). Осы кесіндіде , болатындай -
ның нүктесін таңдаймыз. -ның барлық мәні үшін табамыз.
және , нүктелерін қос-қостан түзу кесінділермен жалғаймыз.
Алынған құрама-сызықты функциясы функциясын кесіндіде
аппроксимациялайды. Аппроксимацияның дәлдігін -ның сәйкес нүктелерін
таңдау арқылы реттеуге болады. (2.13) есебіндегі барлық және
функциялары үзіліссіз деп есептейік. Аралықты айнымалысы
нүктелерінде өзгеретіндей етіп бөлеміз, және жоғарыда келтірілген әдісті
қолданып, және функцияларының және құрама-сызықты
аппроксимациясын құрамыз. Онда (2.13) есебінің орнына келесі жуықтау есебін
қарастырамыз:

(2.14)

(2.14) есебіндегі құрама-сызықты функция үшін аналитикалық өрнектелуін
табамыз. 2.5-суретті қараймыз. Егер нүктесі кесіндісінде жатса,
онда келесі функциямен аппроксимацияланады:

(2.15)
Сонымен қатар кесіндісінде жататын нүктесінің мәнін,
шартын қанағаттандыратын кейбір -ларды таңдау арқылы түрінде
жазуға болады. Бұдан . (2.15) өрнегіндегі орнына қою
арқылы келесіні аламыз:

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

(2.16)

Қабылданған белгілеуді қолданып, келесіні аламыз:

(2.17)

(2.18)

.

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

(2.19)

(2.20)

мұндағы

(2.21)

(2.22)

Бұл жерде барлық үшін болады. және функцияларын
анықтау кезінде кесіндісін бөлу екеуіне де бірдей қолданылады. Осы
функциялардың өрнектелуін (2.14)-ке қою арқылы келесіні аламыз:

(2.23)

мұндағы барлық үшін .
Алынған есептің сызықты программалаудың қарапайым есептерінен
айырмашылығы сол, әрбір үшін -дің екіден артық емес көршілес
мәні сәйкес келеді. (2.23) өрнегінде осы есепті шешкеннен кейін жуық
мәнін анықтау үшін қажетті (2.21) формуласы пайдаланылмады. Есепті екі
көршілес емес базиске сәйкес келетін екі векторға қосуға болмайтынын
базис таңдаудың шектелуін есепке ала отырып симплекс әдісімен шешеміз.
Есепті шешу процесінде барлық векторлар үшін болуы мүмкін,
немесе , бірақ базис таңдауға сәйкестендірілген шектелу келесі
итерацияның орындалмауына әсер етеді. Онда (2.23) есебінің соңғы
базистік шешіміне сәйкес келетін нүктесінің мәні жуықтау
есебінің локальді максимумы болады. Сонымен қатар кіші өлшемдегі (2.13)
есебін үлкен өлшемдегі (2.23) есебіне келтіруге болады. Бірақ, егерде
айнымалысы есепке сызықты тиісті болса, яғни

және

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

шектелуіндегі максималды мәнін табу керек.
Шешілуі. (2.13) белгілеуін қолданып:

.

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

Шешім алынған жиын 2.6-суретте көрсетілген. теңдеуі геометриялық
тұрғыдан параболаға сәйкес келеді. Есеп глобальді максимум нүктесіне
шектелу теңдеу түрінде берілген жағдайда ие болады және қисығының
жанамасы қисығына жүргізілген жанамамен сәйкес келеді.
және жанасу нүктелерінің координаталарын

теңдеулер жүйесін шешу арқылы табамыз.
Соңғы теңдеудің сол жағы теңдеуінен алынған арқылы, оң
жағы теңдеуінен алынған арқылы өрнектеледі. Жүйені шешу арқылы
келесіні аламыз: , , .
Жуық есеп құрастырамыз. Шектелуден және нүктелері бірден
аспайтын мәндер қабылдауы керектігі келіп шығады. нүктелерін олардың
аралығы болатындай етіп таңдайық. Онда әрбір үшін -дің
алты мәні табылады. Функцияның, бөліктеудің сәйкес нүктелеріндегі мәнін
табамыз. Нәтижесі 2.2-кестеде көрсетілген.
(2.23) есебімен қатар келесі жуықтау есебін жазамыз:

функциясының

,

барлық және үшін

шектелуіндегі максималды мәнін табу керек.

0 0 0 0 0 0
1 0,2 0,44 0,12 0,16 0,2
2 0,4 0,96 0,48 0,24 0,4
3 0,6 1,56 1,08 0,24 0,6
4 0,8 2,24 1,92 0,16 0,8
5 1 3 3 0 1

2.2-кесте

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

; ; ; ;

; ; ; ;

; ; ; ;

; ;

және есептің шектеулер жүйесін векторлық формада жазамыз:

.

, және векторлары оң, бірлік базис құрайды. Алғашқы
симплексті кестені құраймыз (2.3-кесте).

2.3-кестедегі мәліметтерді пайдалана отырып келесіні аламыз:

.
2.3-кесте.

1 А52 -1
3
0
1
0,8А42 -0,8
1,92
0
1
0,6А32 -0,6
1,08
0
1
0,4А22 -0,4
0,48
0
1
0,2А12 -0,2
0,12
0
1
0 А02 0
0
0
1
0 А51 0
3
1
0
0,1А41 -0,16
6 2,24
1
0
0,2А31 -0,24
4 1,56
1
0
0,2А21 -0,24
4 0,96
1
0
0,1А11 -0,16
6 0,44
1
0
0 А01 0
0
1
0
0 А3 0
1
0
0
0
Ао 3
1
1

Сб 0
0
0

Б А3
А01
А02

2.4-кесте.

1 А52 0
0
0
1
0,8А42 0,2
-1,08
0
1
0,6А32 0,4
-1,92
0
1
0,4А22 0,6
-2,52
0
1
0,2А12 0,8
-2,88
0
1
0 А02 1
-3
0
1
0 А51 0
3
1
0
0,1А41 -0,16
6 2,24
1
0
0,2А31 -0,24
4 1,56
1
0
0,2А21 -0,24
4 0,96
1
0
0,1А11 -0,16
6 0,44
1
0
0 А01 0
0
1
0
0 А3 0
1
0
0
1
Ао 0
1
1

Сб 0
0
1

Б А3
А01
А52

2.5-кесте.

1 А52 0
0
0
1
0,8А42 -53275
-2711
2711
1
0,6А32 -82275
-4811
4811
1
0,4А22 -87275
-6311
6311
1
0,2А12 -68275
-7211
7211
0
0 А02 -111
-7511
7511
1
0 А51 1211
7511
-6411
0
0,1А41 3655
6 5611
-4511
0
0,2А31 1855
4 3911
-2811
0
0,2А21 655
4 2411
-1311
0
0,1А11 0
6 1
0
0
0 А01 0
0
1
0
0 А3 411
2511
-2511
0
1
Ао 0
1
1

Сб 0,16
0
1

Б А11
А01
А52

2.6-кесте.

1 А52 0
0
0
1
0,8А42 0
0
1
0
0,6А32 245
0
169
-79
0,4А22 215
0
73
-43
0,2А12 415
0
83
-53
0 А02 49
0
259
-169
0 А51 428675
1
-6427
6427
0,1А41 13
6 1
-53
53
0,2А31 86675
4 1
-2827
2827
0,2А21 11675
4 1
-1327
1327
0,1А11 0
6 1
0
0
0 А01 53675
1
1127
-1127
0 А3 527
0
-2527
2527
1,0785
Ао 1
1127
1627

Сб 0,16
0,8
1

Б А11
А42
А52

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

.

Сонымен қатар базис таңдауымен беттескен теріс бағалауға ие
және векторлары базиске қосылмайды, және векторын алып
тастаймыз. Нәтижесінде 2.5-кестені аламыз.
Базистегі векторының орнына векторын қосуға болады.
Нәтижесінде айырмасы теріс емес болады, бұл жоспардың оптималдылығын
көрсетеді. Шешім 2.6-кестеде келтірілген.
2.6-кестеде алынған шешімге сәйкес келесіні аламыз:

(2.21) өрнегінің негізінде , аламыз. Табылған шешімді оптималды
шешіммен салыстырамыз: , , . Жуық шешімнің оптималдық
шешімнен өзгешелігі өте аз болады (әсіресе мәніне қарағанда). Осы
есепті базис таңдаудың шектелуін есепке алмай да шығаруға болады. Бұл
тұжырым орынды, өйткені шешім алынған жиын дөңес, ал, - ойыс функция.
Қарастырылып отырған локальді максимум нүктесін табудың жуықтау әдісі
өте тиімді, өйткені ол есептің шартындағы аналитикалық функциялардың
қасиетіне тәуелсіз. Бірақ бұл әдісті үлкен ұқыптылықпен қолдану керек,
өйткені жуықтау есебінің локальді максимумы глобальді максимум нүктесінен
өзгеше болуы мүмкін.

§5. Кун-Таккер теоремасы.

Сызықты емес программалау теориясында Кун-Таккер теоремасы маңызды
орынға ие. Айталық, сызықты емес программалау есебі берілген болсын:
функциясының

(2.24)

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

(2.25)

Егер регулярлық шарты орындалса, [ үшін кемінде бір нүктесі бар
болады (барлық үшін)], онда келесі теорема орынды.
2.3-терема. векторы сонда, тек сонда ғана (2.24) есебінің
оптималды шешімі болады, егер , үшін векторы бар болса
және барлық үшін келесі теңсіздік орындалса:

(2.26)

нүктесі функциясының қайқы ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.