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

Сызықты емес программалау есебі класы сызықты программалау есебі класынан ауқымдырақ. Сызықтық деп есептелінетін практикалық есептерді толық зерттеу нәтижесі олардың шын мәнінде сызықтық емес екендігін көрсетеді. Сызықты программалау есептері шешімдерінің тиімдісін табу мәселесі туындайды. Белгілі әдістердің барлығы есепті (2.3) түріндегі шағын кластарда ғана шешуге арналған, ал мақсаттық функция сепарабелдік немесе квадраттық функция болады. Тіпті шешім алынған облыс дөңес облыс болса, онда есептер қатарында мақсаттық функция бірнеше локалді экстремумға ғана ие болуы мүмкін. Көптеген есептеу әдістерінің көмегімен локалді оптимум нүктесін табуға болады, бірақ, ол глобалдік (абсолюттік) оптимум нүктесі болатын, болмайтынын анықтау мүмкін емес. Егер сызықтық программалау есептерінде шешімнің экстремум нүктесі көпжақтың төбесі болса, онда сызықты емес программалау есептерінде көпжақтың төбесінде, қабырғасында немесе облыстың ішінде жатуы мүмкін. Егер есеп сызықты емес шектеулі болса, онда шешім алынған облыс дөңес болмайды, сондай-ақ глобалдік оптимумнан басқа локалдік оптимум нүктесі табылуы да мүмкін. Екі айнымалылы сызықтық емес прораммалау есептеріне мысалдар
        
        Ф-ОБ-011/003
ҚАЗАҚСТАН РЕСПУБЛИКАСЫ БІЛІМ ЖӘНЕ
ҒЫЛЫМ МИНИСТРЛІГІ
Қ.А.Ясауи атындағы Халықаралық қазақ-түрік университеті
« Математика » кафедрасы
«БЕКІТЕМІН»
Кафедра меңгерушісі
техн.ғ.д., профессор
______________Ә.Мұратов
Д И П Л О М Д Ы Қ Ж Ұ М Ы ... ... ... және квадраттық
программалау»
Орындаған: ЖМА-711 Абдулсаматқызы З.
Тобы, студенттіњ аты-жөні
Ғылыми ... ... ... ... ... ... Сызықтық емес программалаудың жалпы есебі. Лагранж көбейткіштері
әдісі.
Белгілі болғандай, математикалық ... ... ... ... ... ... және
(2.2)
функциясын экстремумына жеткізуші векторын табу керек.
Мұндағы және функциялары ... ала ... ... ... ... ... ... шарты талап етіледі.
Сондай-ақ, айнымалы қатар үшін шешімнің шектеулі ... ... ... ... ... және - ... ... болса, онда шешімнің теріс
емес болу шартынан сызықтық ... ... ... Математикалық
программалаудың (2.3) және (2.4) шарттарын қанағаттандырмайтын кез-келген
басқа есебін сызықты емес деп ... емес ... ... ... ... программалау есебі
класынан ауқымдырақ. Сызықтық деп есептелінетін практикалық есептерді толық
зерттеу нәтижесі олардың шын мәнінде ... емес ... ... ... ... шешімдерінің тиімдісін табу мәселесі
туындайды. ... ... ... ... (2.3) ... ... ғана шешуге арналған, ал мақсаттық функция сепарабелдік немесе
квадраттық функция болады. Тіпті шешім ... ... ... ... ... есептер қатарында мақсаттық функция бірнеше локалді экстремумға ғана
ие болуы мүмкін. Көптеген есептеу ... ... ... ... ... болады, бірақ, ол глобалдік (абсолюттік) оптимум нүктесі
болатын, болмайтынын анықтау мүмкін емес. Егер ... ... ... ... ... ... ... болса, онда сызықты
емес программалау есептерінде көпжақтың төбесінде, қабырғасында ... ... ... мүмкін. Егер есеп сызықты емес шектеулі болса, онда
шешім алынған облыс дөңес болмайды, ... ... ... ... оптимум нүктесі табылуы да мүмкін.
Екі айнымалылы сызықтық емес прораммалау ... ... ... ... ... ... бұл да ... түрде
шешіледі.
2.1-сурет ... ... ... ... ең ... және ең кіші ... тап.
Шешілуі. Шешім алынған облыс (2.1 сурет) көпбұрышы ... ... онда ... шеңбер теңдеуін аламыз. -дің мәнін
азайтсақ (арттырсақ) сәйкесінше функциясының мәні азаяды (артады).
нүктесінен ... ... ... ... ... ... функциясы ең кіші мәнге нүктесінде ие болады. Ал,
шеңбер шешімнің облысын жанайды. ... ... емес ... ... және түзулеріне сәйкес ... ... ... ... екі ... ... ие ... төбесінде
функциясы, төбесінде функциясы. болғандықтан ... ... ... ... болып табылады.
2-мысал. Шешім алынған облыс бұрынғысынша қалсын, ал, болсын.
Осы функцияның ең үлкен және ең кіші мәнін табу ... ... ең кіші ... ... ие ... ... . функциясы екі локалді максимумға ие болады:
төбесінде ... ... ... ал, ... ... ие ... функциясының
, .
шектелуідегі ең үлкен және ең кіші мәнін тап.
Шешілуі. Бұл жағдайда шешім алынатын облыс дөңес емес ... және ... ... ... Ең кіші мәні және ... ... ... функциясы екі локалді максимумға ие болады:
нүктесінде және ... ... ... ... ... ... табылады.
Лагранж көбейткіштері әдісі.
2.3-сурет
Айталық математикалық программалау есебі берілген болсын:
(2.5)
функциясына максималды мән беретін
(2.6)
Теңдеулер жүйесінің шешімін табу керек.
Есептегі шектелу теңдеумен берілген, сондықтан оны шешу үшін ... ... ... ... ... ... ... қолдануға
болады. Сондай-ақ және функциялары бірінші ... ... ... ... ... ... шешу ... құраймыз, , дербес туындыларын аламыз және оларды
нолге теңестіреміз. Нәтижесінде келесі теңдеулер ... ... ... ... ... Лагранж функциясы, ал, -
Лагранж көбейткіштері деп аталады. Егер ... ... ие ... онда (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 ... ... ... ... ... ... ... жүйесінің шешімі , және ... ... ... ... деталдан 6, екінші түрдегі деталдан 10, ... ... 15. ... ... табамыз :
;
;
;
.
Ескерту. , , мәнін есептеуде
интегралы қолданылады.
Егерде шартын есепке алмасақ, онда жалпы пайда үлкен мән
қабылдайды, ... мәні -ны ... ... ... ... ... түрінде болғанда және оның
шешімі теріс емес ... ... ... ... ... қолдануға
болады. Қосымша айнымалылар енгізу ... ... ... ... ... бұл жерде қосымша айнымалылар теріс емес
болу шартымен сәйкестендіріледі. ... ... ... ... ... қабылдаса, теріс емес октантаның ішкі нүктесінде де солай
қабылдайды. Бірінші кезеңде (2.8) жүйесінің теріс емес шешімдері табылады
және ... үшін ... ... облысына тиісті мәндері
анықталады. Теріс емес октантаның шекарасын зерттеу үшін ... ... ... жағдайды қарастырамыз. Одан кейін дәл солай, бірақ,
айнымалыларының саны болған есепті қарастырамыз. Бұл есеп үшін ... ... ... ... және оған сәйкес мәндері табылады.
Екі ... ... ... ... бар (бұндай есептердің
саны -ге тең болады) және т.с.с есептерді ... ... ... ... ... Соңғы кезеңде ... ... ... қатар қалған айнымалы бірмәнді анықталады. ... үшін де ... ... ... ... ... теңестіру арқылы абсолюттік экстремум табылады.
§3. Дөңес және ойыс функциялар.
Алдағы уақытта ... және ойыс ... ... ... ... ... ... келтірейік. Айталық n өлшемді сызықтық
кеңістігі берілсін. Дөңес жиынында берілген функциясын ... деп ... егер ... ... кез келген ,
нүктесі және кез келген үшін келесі теңсіздік орындалса:
(2.9)
Көп жағдайда жиыны ... ... ... ... ... ... жиынында берілген функциясы ойыс функция деп
аталады, егер жиынынан ... кез ... , ... ... ... үшін ... теңсіздік орындалса:
(2.10)
Егер функциясы дөңес функция болса, онда ... ... ... және ... ... ... ... егер -
дөңес бет () ... онда оның кез ... екі ... ... ... ... немесе оның жоғарғы жағында жатады (2.4 сурет).
Сонымен қатар, функцияның ойыс және дөңестігі анықтама бойынша кез
келген , ... ... ... үшін ... ... ... болса, кеңістігінен ... ... ... ... ... тек ... ... егер жиын дөңес ... ... (2.9) және (2.10) ... ... және олар ... деп есептесек, онда функциясы қатаң дөңес (қатаң ойыс)
функция болады. Бұл геометриялық тұрғыдан кез ... екі ... ... ... жоғарғы (төменгі) жағында жатады дегенді білдіреді.
мәні үшін қатаң дөңес, ... мәні үшін ... ... емес ... ... ... ... мұндағы - кейбір ... ... ... онда функциясы да жиынында дөңес ... ойыс ... ... да ойыс ... ... ... кеңістігінің теріс емес октантасында ... ... ... онда , ... ... барлық
нүктелерінің жиыны дөңес болады (егер бос жиын болмаса).
Бұл тұжырымды дәлелдеу үшін , ... ... ... үшін ... де, ... , жиынында жататынын
көрсетеміз. Егер - дөңес функция болса, онда
.
және нүктелері үшін және шарттары ... ... ... ... керегі де осы болатын.
Дөңес жиындардың қиылысуы ... ... ... ... ... барлық нүктелер жиыны дөңес болады, егер
теңсіздікте «» таңбасы болғанда - ... ... ал, ... болғанда - ойыс функция болса. Функцияның ойыс және ... ... оның ... ... ... талап
етілген жоқ. Егер функциясы жиынының ішкі нүктесінде үзіліссіз,
дифференциалданатын және ... ... онда ... ... ... ... өрнегінен үшін келесіні аламыз:
;
онда Тейлор формуласы бойынша
,
мұндағы - функциясының , ... ... ... жағдайдағы шекті есептеу арқылы келесіні аламыз:
.
Бұл шарт кез келген , нүктелері үшін орындалады және ... ... ... және жеткілікті шарттары болып табылады.
Егер функциясы ... ... ... дербес туындыларымен бірге
үзіліссіз және жиынында ... ... ... және ойыс функциялардың кейбір қасиеттерін қарастырайық.
2.1-теорема. Айталық функциясы ... ... ... ... ... ... онда функциясының жиынына тиісті
кез келген локальді минимумы глобальді ... ... ... ... функциясы локальді минимумға ие
болсын деп есептейік, сонымен қатар ... ... ... ... және болсын. - дөңес ... кез ... үшін ... ... орынды:
(2.12)
жиыны дөңес, сондықтан үшін нүктесі жиынының
өзіне тиісті болады. (2.12) ... ... ... егер ... ... болсақ. Онда
.
мәнін нүктесі мүмкін болғанша нүктесіне жақын
орналасатындай етіп ... ... Онда ... ... ... сондай-ақ бұл жағдайда нүктесіне жақын нүктеде функция
нүктесінде қабылдайтын мәнінен кішірек мән ... ... ... шығады. Теорема дәлелденді.
1-тұжырым. Егер глобальді минимум әр түрлі екі нүктеде бар ... ол осы ... ... кесіндінің кез келген нүктесінде де бар
болады.
2-тұжырым. Егер қатаң дөңес функция ... онда оның ... ... ... ... тек бір ғана ... ... Айталық функциясы берілген дөңес жиынында
дөңес функция болсын, сонымен қатар өзі және ... ... ... ... ішкі ... ... болсын. Айталық
нүктесі үшін болсын. Онда ол нүктесінде глобальді минимуммен
беттесетін локальді минимум нүктесіне ие ... ... ... ... кез ... нүктесі
болсын. (2.11) өрнегінде , деп ... ... ... ... ... ... болса, дөңес функциясы өзінің глобальді минимумына
жиынының ... ... ... ие болады.
Егер - тұйық, төменгі жағынан шенелген, дөңес жиын ... ... ... ... ... ... осы ... бір немесе
бірнеше нүктесінде ие болатынын (сонымен қатар ... ... мәні ... деп ... ... болады. Осындай
есептерді ... ... ... ... ... ... ... максимум нүктесін табуға болады (2.2.-сурет), бірақ бұл нүкте
глобальді максимум болатынын айта алмаймыз.
Дөңес ... үшін ... ... ... ... ... ... - функциясы тұйық, дөңес жиында
дөңес функция болсын. Онда ... ... ... ... локальді максимумы глобальді максимум нүктесі болып ... ... ... ... әр ... екі нүктесінде бар болса, онда ол осы
екі нүктені қосатын кесіндіде жататын барлық нүктелер ... да ... ие ... ... ... ... үшін ... максимум нүктесі
жалғыз болады.
- дөңес функциясының градиенті нөлге тең, егер ... ... ... Егер ... ... ... ... шенелген жиында ақырлы болса, осы жиынның әрбір нүктесінде ақырлы
болса, онда ... ... осы ... бір ... ... нүктесінде
бар болады.
§4. Сепарабельді функциялар ... ... ... ... емес ... ... шешудің жуықтау әдістерінің бірін
қарастырайық.
функциясының
(2.13)
шектеуіндегі максималды мәнін табу ... ... ... және ... ... функциялар
сепарабельдік функция болады.
Жуықтау әдісі және функцияларының ... ... ... ... ... шешімі симплекс
әдісімен табылатын жуықтау есебі орынды ... ... ... жуықтау
есебінің локальді максимумы және (2.13) есебінің жуық ... ... ... ... жиыны дөңес, ал - ойыс функция болса, ... ... ... бір ... ... ... нүктесі де болады.
Бұл жағдайда (2.13) есебінің шешімі үшін жуық ... ... ... жуықтау есебінің глобальді максимум нүктесі табылады.
(2.13) есебі үшін ... ... ... ... ... ... бір ... үзіліссіз функциясы
берілген болсын (2.5-сурет). Осы кесіндіде , болатындай ... ... ... -ның ... мәні үшін табамыз.
және , нүктелерін қос-қостан түзу кесінділермен жалғаймыз.
Алынған ... ... ... ... ... ... -ның сәйкес нүктелерін
таңдау арқылы реттеуге болады. (2.13) есебіндегі барлық және ... ... деп ... ... айнымалысы
нүктелерінде өзгеретіндей етіп бөлеміз, және ... ... ... және функцияларының және құрама-сызықты
аппроксимациясын ... Онда (2.13) ... ... келесі жуықтау есебін
қарастырамыз:
(2.14)
(2.14) есебіндегі құрама-сызықты функция үшін аналитикалық ... ... ... Егер ... ... ... келесі функциямен аппроксимацияланады:
(2.15)
Сонымен қатар кесіндісінде жататын нүктесінің мәнін,
шартын қанағаттандыратын ... ... ... ... ... ... ... . (2.15) өрнегіндегі орнына қою
арқылы ... ... , деп ... онда ... ... мәндерінің келесі өрнекті қанағаттандыратындай ... ... ... ... ... қолданып, келесіні аламыз:
(2.17)
(2.18)
.
Сонымен қатар нөлден өзгеше тек бір немесе екі іргелес бола
алады. Бұндай әдіс ... ... ... ... ... функциясы сынған функциясы үшін аналитикалық өрнектелуді
көрсетеді.
(2.13) есебіне қайта ораламыз. Айталық, мәні ... ... мән ... кесіндісін -дің
нүктелерінің көмегімен аралықтарына, және ... ... ... сәйкесінше келесі түрде жазылатындай етіп бөлеміз:
(2.19)
(2.20)
мұндағы
(2.21)
(2.22)
Бұл жерде барлық үшін болады. және ... ... ... бөлу ... де бірдей қолданылады. Осы
функциялардың өрнектелуін (2.14)-ке қою арқылы ... ... ... үшін ... ... сызықты программалаудың қарапайым есептерінен
айырмашылығы сол, әрбір үшін -дің ... ... емес ... ... ... (2.23) ... осы есепті шешкеннен кейін жуық
мәнін анықтау үшін қажетті (2.21) формуласы ... ... ... емес ... ... келетін екі векторға қосуға болмайтынын
базис таңдаудың шектелуін есепке ала отырып симплекс әдісімен шешеміз.
Есепті шешу процесінде ... ... үшін ... ... , бірақ базис таңдауға сәйкестендірілген шектелу ... ... әсер ... Онда (2.23) ... соңғы
базистік шешіміне сәйкес келетін ... мәні ... ... ... ... Сонымен қатар кіші өлшемдегі (2.13)
есебін үлкен өлшемдегі (2.23) ... ... ... Бірақ, егерде
айнымалысы есепке сызықты тиісті ... ... ... онда -ді ... ... ... жоқ. мәнін
жуықтау есебінің өлшемін мейлінше кішірейтетіндей ... ... ... Жуықтау есебінің локальді максимумы (2.13) ... ... ... ... ... аппроксимациясы болуы
мәселесін алдында берілген аралықта алынған шешімді кіші бөліктерге бөлуден
алынған нәтиже нақтылайды.
Мысал. функциясының
шектелуіндегі ... ... табу ... (2.13) ... ... ... ... болғандықтан, шешім алынған
жиын да дөңес болады. және ... ойыс ... ... ... кез келген локальді максимумы бір уақытта глобальді максимум
бола алады. ... ... ... шешу ... глобальді максимум
нүктесіне жақындаймыз. Есеп екі айнымалыға тәуелді болады. Сондықтан ... ... ... ... ... ... жиын ... көрсетілген. теңдеуі геометриялық
тұрғыдан параболаға сәйкес келеді. Есеп ... ... ... ... түрінде берілген жағдайда ие болады және қисығының
жанамасы қисығына жүргізілген ... ... ... ... ... ... ... шешу арқылы табамыз.
Соңғы теңдеудің сол жағы теңдеуінен ... ... ... теңдеуінен алынған арқылы өрнектеледі. Жүйені шешу арқылы
келесіні аламыз: , , .
Жуық есеп құрастырамыз. ... және ... ... ... ... ... келіп шығады. нүктелерін олардың
аралығы ... етіп ... Онда ... үшін ... мәні ... ... ... сәйкес нүктелеріндегі мәнін
табамыз. Нәтижесі 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.3-кесте).
2.3-кестедегі мәліметтерді пайдалана отырып келесіні аламыз:
.
2.3-кесте.
|1 |А52 | |-1 |
| | |3 | |
| | |0 | |
| | |1 | ... | |-0,8 |
| | |1,92 | |
| | |0 | |
| | |1 | ... | |-0,6 |
| | |1,08 | |
| | |0 | |
| | |1 | ... | |-0,4 |
| | |0,48 | |
| | |0 | |
| | |1 | ... | |-0,2 |
| | |0,12 | |
| | |0 | |
| | |1 | |
|0 |А02 | |0 |
| | |0 | |
| | |0 | |
| | |1 | |
|0 |А51 | |0 |
| | |3 | |
| | |1 | |
| | |0 | ... | |-0,16 |
|6 | |2,24 | |
| | |1 | |
| | |0 | ... | |-0,24 |
|4 | |1,56 | |
| | |1 | |
| | |0 | ... | |-0,24 |
|4 | |0,96 | |
| | |1 | |
| | |0 | ... | |-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 | ... |А52 | |0 |
| | |0 | |
| | |0 | |
| | |1 | ... | |0,2 |
| | |-1,08 | |
| | |0 | |
| | |1 | ... | |0,4 |
| | |-1,92 | |
| | |0 | |
| | |1 | ... | |0,6 |
| | |-2,52 | |
| | |0 | |
| | |1 | ... | |0,8 |
| | |-2,88 | |
| | |0 | |
| | |1 | |
|0 |А02 | |1 |
| | |-3 | |
| | |0 | |
| | |1 | |
|0 |А51 | |0 |
| | |3 | |
| | |1 | |
| | |0 | ... | |-0,16 |
|6 | |2,24 | |
| | |1 | |
| | |0 | ... | |-0,24 |
|4 | |1,56 | |
| | |1 | |
| | |0 | ... | |-0,24 |
|4 | |0,96 | |
| | |1 | |
| | |0 | ... | |-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 | ... |А52 | |0 |
| | |0 | |
| | |0 | |
| | |1 | ... | |-53/275|
| | |-27/11 | |
| | |27/11 | |
| | |1 | ... | ... | |-48/11 | |
| | |48/11 | |
| | |1 | ... | ... | |-63/11 | |
| | |63/11 | |
| | |1 | ... | ... | |-72/11 | |
| | |72/11 | |
| | |0 | |
|0 |А02 | |-1/11 |
| | |-75/11 | |
| | |75/11 | |
| | |1 | |
|0 |А51 | |12/11 |
| | |75/11 | |
| | |-64/11 | |
| | |0 | ... | |36/55 |
|6 | |56/11 | |
| | |-45/11 | |
| | |0 | ... | |18/55 |
|4 | |39/11 | |
| | |-28/11 | |
| | |0 | ... | |6/55 |
|4 | |24/11 | |
| | |-13/11 | |
| | |0 | ... | |0 |
|6 | |1 | |
| | |0 | |
| | |0 | |
|0 |А01 | |0 |
| | |0 | |
| | |1 | |
| | |0 | |
|0 |А3 | |4/11 |
| | |25/11 | |
| | |-25/11 | |
| | |0 | |
| | |1 ... |0 | |
| |1 | |
| |1 | |
| | | ... |0,16 | |
| |0 | |
| |1 | |
| | | ... |А11 | |
| |А01 | |
| |А52 | ... |А52 | |0 |
| | |0 | |
| | |0 | |
| | |1 | ... | |0 |
| | |0 | |
| | |1 | |
| | |0 | ... | |2/45 |
| | |0 | |
| | |16/9 | |
| | |-7/9 | ... | |2/15 |
| | |0 | |
| | |7/3 | |
| | |-4/3 | ... | |4/15 |
| | |0 | |
| | |8/3 | |
| | |-5/3 | |
|0 |А02 | |4/9 |
| | |0 | |
| | |25/9 | |
| | |-16/9 | |
|0 |А51 | |428/675 |
| | |1 | |
| | |-64/27 | |
| | |64/27 | ... | |1/3 |
|6 | |1 | |
| | |-5/3 | |
| | |5/3 | ... | |86/675 |
|4 | |1 | |
| | |-28/27 | |
| | |28/27 | ... | |11/675 |
|4 | |1 | |
| | |-13/27 | |
| | |13/27 | ... | |0 |
|6 | |1 | |
| | |0 | |
| | |0 | |
|0 |А01 | |53/675 |
| | |1 | |
| | |11/27 | |
| | |-11/27 | |
|0 |А3 | |5/27 |
| | |0 | |
| | |-25/27 | |
| | |25/27 | |
| | |1,0785 ... |1 | |
| |11/27 | |
| |16/27 | |
| | | ... |0,16 | |
| |0,8 | |
| |1 | |
| | | ... |А11 | |
| |А42 | |
| |А52 | ... қатар базиске векторын қосу керек. және
векторлары көршілес болмағандықтан ... ... ... ... ... ... ... бұл мүмкін. 2.4-кестеде
есептеулер нәтижесі келтірілген.
2.4-кестенің мәліметтерін пайдалана отырып келесіні аламыз:
.
Сонымен қатар базис ... ... ... бағалауға ие
және векторлары базиске қосылмайды, және ... ... ... ... ... векторының орнына векторын қосуға болады.
Нәтижесінде айырмасы теріс емес болады, бұл ... ... ... ... ... алынған шешімге сәйкес келесіні аламыз:
(2.21) өрнегінің негізінде , аламыз. Табылған шешімді оптималды
шешіммен ... , , . Жуық ... ... ... өте аз ... ... ... қарағанда). Осы
есепті базис таңдаудың шектелуін есепке ... да ... ... Бұл
тұжырым орынды, өйткені шешім алынған жиын дөңес, ал, - ойыс функция.
Қарастырылып отырған локальді максимум нүктесін ... ... ... ... ... ол есептің шартындағы аналитикалық функциялардың
қасиетіне тәуелсіз. Бірақ бұл әдісті үлкен ... ... ... ... ... ... максимумы глобальді максимум нүктесінен
өзгеше болуы мүмкін.
§5. Кун-Таккер теоремасы.
Сызықты емес программалау теориясында ... ... ... ие. ... ... емес ... ... берілген болсын:
функциясының
(2.24)
шектелуіндегі максималды мәнін табу керек.
Берілген есептің Лагранж функциясын құрамыз:
(2.25)
Егер регулярлық шарты орындалса, [ үшін ... бір ... ... ... ... онда келесі теорема орынды.
2.3-терема. векторы сонда, тек сонда ғана (2.24) ... ... ... егер , үшін ... бар ... ... үшін ... теңсіздік орындалса:
(2.26)
нүктесі функциясының қайқы нүктесі деп аталады, ал, 2.3-
теоремасы ... ... ... ... деп аталады. (2.26) шартының
жеткілікті болуын көрсетеміз.
Дәлелдеуі. Айталық , нүктелері функциясының ... ... Егер (2.26) ... ... орнына оның
(2.25)-тегі мәнін қойсақ, онда келесіні аламыз:
, үшін
болады.
Оң жақтағы теңсіздік кез келген үшін ... ... ... сол ... ... ... ... жағдайда , онда .
Олай болса нүктесі (2.24) шартын қанағаттандырады және ... ... ... ... ... кіші мән қабылдайды.
Бұл тұжырым есептің шешімін ... ... ... ... ... алып ... шартының қажеттілігі оның ... ... ... және ... ... ... ... (2.26) өрнегі келесі түрдегі Кун-Таккер локальді шартына ... ... ... ... ... нүктесіндегі
мәні дегенді білдіреді, мұндағы , . Бұл ... ... ... ... ... ... ... квадраттық программалау есебін қарастырғанда (2.27) ... ... ... ... табу ... ... ... бұл есеп оңай шешіледі: , ,
.
Оптимум ... ... үшін (2.27), (2.28) ... ... шарттары орындалатындай табылады:
.
Келесіні табамыз:
, ,
, , .
(2.28) шартына сәйкес және нөлдік мән қабылдау керек, ... ... және ... ... онда ... мән ... ал, шарт бойынша . Есептің шартына сәйкес ... ... мән ... ... өйткені .
(2.27) өрнегіне сәйке дербес туындысы нөлдік ... ... ... ... ... ... өзгеше. мәнін
табамыз. Осыған ... ... ... ... орындалады және ол
шындығында экстремум нүктесі болып табылады.
§6. Квадраттық программалау.
Квадраттық программалау есебі
шектелуі сызықты ... ... ал, ... және ... ... ... ... сызықты емес
программалау есебінің дербес жағдайларының бірі болып табылады.
айнымалыға тәуелді квадраттық функция квадраттық форма ... және ... ... ... , ... ... - симметриялы матрица деп есептейміз ... деп ... егер ... ... есебін
(2.29)
болған жағдай үшін келесі матрицалық түрде жазамыз:
.
Сызықты емес ... ... ... ... ... есептерінің глобальді экстремумын табудың тиімді әдісі жоқ,
егер кез келген локальді экстремум бір уақытта глобальді экстремум ... ... (2.29) ... ... болған шешімдерінің жиыны дөңес
болады, онда, егер мақсаттық ... ойыс ... кез ... ... нүктесі глобальді максимум да бола алады. Егер мақсаттық функция
дөңес болса, онда кез ... ... ... ... нүкте болады.
функциясы квадраттық форманы және сызықтық ... ... ... ... ... ... Егер де мақсаттық функция ойыс (дөңес) болса,
онда мақсаттық функцияның максимумын ... табу ... ... Квадраттық форманың ойыс немесе дөңес болуы оның теріс
анықталған, ... ... ... оң ... оң ... ... ... анықталмағандықтарынан келіп шығады.
квадраттық формасы теріс анықталған деп аталады, егер барлық
үшін болса.
квадраттық формасы теріс ... ... деп ... егер
барлық үшін орындалса, және болатындай табылса.
квадраттық формасы оң анықталған (оң жартылай анықталған) ... егер ... ... теріс анықталған (теріс жартылай
анықталған) ... ... ... деп ... егер ол ... мәні үшін оң ... қалған кейбір мәндері үшін теріс болса.
Сызықтық түрлендірудің көмегімен квадраттық форманы айнымалының
квадраттарынан ғана ... ... ... ... ... Осы
түрлендірудің нәтижесінде форманың түрін анықтауға болады. Егер түрлендіру
нәтижесінде формасы алынған және барлық ... онда ол ... ал, ... ... ... ... айқын көрініп тұр.
Егер мәніні арасында теріс мәндер мен ... оң ... де бар ... ... ... ... болады.
Мысал. квадраттық формасы берілген. Осы форманы ... ... ... ... ... ... ... формада
жазамыз:
.
формасының мәні бар мүшелерін ажыратып алу арқылы келесіні
аламыз:
.
Жақша ... ... ... квадратқа толықтыру арқылы келесіні аламыз:
.
Енді
(2.30)
деп есептеп квадраттық ... ... ... ... өрнегінен мынаны аламыз:
(2.31)
-ді түрлендіреміз:
.
Айталық
(2.32)
бұдан
(2.33)
Онда . Қорыта келгенде
.
, , ... , , ... ... ... және (2.33) түрлендірулерінің көбейтіндісін, оның сәйкес матрицасын
анықтау арқылы кескіндеуге болады. (2.31) өрнегінің ... ... ... ... ... ... келесі матрица сәйкес келеді:
.
матрицасын табамыз:
.
матрицасын табамыз, онда
.
матрицасы ... ... ... ... ... ... түрлендіру кезінде, егерде матрицасы ... ... оң ... ... ... оң ... анықталған болып қала береді.
квадраттық ... ... ... ... және
матрицасы өзгеше матрица болмаса, онда - ... ... ... ... ... ... оның ... типтердің қайсысына жататынын анықтауға болатын ... ... ... ... ... үшін барлық анықтауыштары нөлден өзгеше болса,
онда бұл форманы үшбұрышты түрлендіру арқылы келесі түрге келтіруге ... ... ... онда ... ... ажыратып алу арқылы
келесіні аламыз:
.
екендігі ... ... ... ... ... болады, үшбұрышты түрлендіруді тағы бір рет қолдану арқылы екінші
квадратты ажыратып аламыз. Айталық, квадратты ... ... ... ... ... ... ... болсын:
.
болса, онда тағы бір квадратты ажыратып алуға болады.
Олай болса, ... ... ... ... канондық түрге
келтіргенге дейін жалғастырамыз. (2.34) анықтауыштары ... ... ... ... ... ... ... деп есептеп диагональдік түрге келтіреміз:
..............................................
немесе , , , ... , . нөлден ... ... ... , , ... , .
Теорема дәлелденді.
Олай болса ... ... ... ... Егер ... анықтауыштары оң болса, онда
коэффиценттері де оң, сонымен қатар ... фома оң ... ... Егер ... қатардағы анықтауыштарының таңбасы
ауыспалы болса, онда барлық онда коэффиценттері теріс, сонымен ... ... ... анықталған болады.
3-жағдай. Егер матрицасының рангі болса, онда оң жартылай
анықталған болады, егер оның алғашқы анықтауышы оң, ал, ... ... ... ... ... мен ... ... ауыстыруға болады. Оң
жартылай анықталған форма нөлге тең болады, егер ... ... ал, ... ... ... мән қабылдаса.
4-жағдай. Егер матрицасының рангі , бір қатардағы ... ... ... және ... онда ... форма
теріс жартылай анықталған болады.
5-жағдай. Егер бірінші қатардағы анықтауыштарының таңбасы
ретсіз болса, сондай-ақ ... ... ... табылса, онда сәйкес
келетін квадраттық форма анықталмаған болады.
Мысал. Келесі квадраттық форманың ... ... ... аламыз
, , ,
.
- таңбасы ауыспалы болса, квадраттық формасы теріс анықталған
болады.
- дөңес функция деп есептеп, (2.29) ... ... ... сызықты, сондықтан шешімнің оптималдылығының қажетті және
жеткілікті шартын алу үшін (2.27'), (2.28') ... ... ... ... (2.29) ... үшін ... ... құрамыз:
. ... ... ... ... ... үшін (2.27') ... өрнектейміз. Егер квадраттық
программалау есебінің тиімді жоспары болса, онда , ... ... ... табылады. Көмекші вектор
енгіземіз
.
Онда (2.27) шартын келесі түрде жазуға болады:
(2.36)
Бұл жағдайда (2.28') шарты ... ... ... ... ... ... онда векторы терім емес болу ... ... кез ... мүмкін болған шешім үшін ... оны алып ... ... ... ... егер , ... орындалатындай болса, онда векторы (2.29) түріндегі квадраттық
программалау есебінің тиімді ... ... ... прогарммалау есебін
шешудің әдістерін қарастырамыз.
Билл әдісі.
Билл әдісі сызықты программалау есебі үшін симплекс әдісінің жалпыламасы
болып табылады. Осы ... есеп ... ... ... ... ... бір базистік, жарамды шешімі маңызды рөл атқарады.
Айталық, келесі түрдегі сызықты ... ... ... ... ... ... ... яғни функциясы ... ... ... ... қатысты шешуге болады деп
есептейік:
(2.38)
(2.38) өрнегі функциясын тек тәуелсіз айнымалылы ... ... ... ... ... , үшін .
Жақша ішіндегі өрнек айнымалысы ... ... ... жағдайда бастапқы нүктеде ... ... бұл ... мәні тең. ... ... ... шарты өте қарапайым түрге ие болады.
Егер барлық туындылар болса, онда кез ... ... ... ... ... ... алып келетіндіктен
бастапқы нүктесі тиімді шешім болады, ... ... ... ... ... ... ... ұлғайту функция
мәнінің ұлғаюына алып келеді. Егер ... , яғни ... ... бірін ұлғайту арқылы, мысалы , ... ... ... тең деп ... ... ... ұлғайтамыз.
айнымалысын өзгерту базистік айнымалылардың өзгеруіне алып келеді. ... ... ... ... бірі ... ... онда ... ұлғайту мүмкін болмайды. Оның дербес туындылары тұрақты ... ... ... үшін бұл ... ... Квадраттық функция
үшін туындысы басқа тәуелсіз айнымалылардың біріне қарағанда ертерек
нөлге айналады. Онда функциясының мәні ... ... ... ... ... ... ... мысалы айнымалысы мәнінен бұрын
нөлге айналатын жағдайды қарастырамыз. Екінші ... ... ... ... айналатын нүктені таңдаймыз, яғни тәуелсіз айнымалылар
, , , ... , ... , , ... , ... ... ... ... ... ... алып
тастаймыз. Нәтижесінде (2.39) өрнегінің орнына келесі жүйені аламыз:
(2.40)
Бұл ... ... ... ... ... сияқты. (2.39)
көмегімен функциясы үшін өрнекті ... ... ... шешімнің алғашқысынан айырмашылығы сол, және
айнымалыларының орындары ауысқан.
Енді туындысы берілген облыстың ... ... ... ... ... ... ... тәуелсіз айнымалылармен келесі
түрде байланысқан айнымалысын енгіземіз
(2.41)
Екінші нүкте ретінде , ... -ден ... ... ... ... ... ... таңдаймыз. (2.41) өрнегінің негізінде
айнымалысын келесі түрде жазуға болады:
(2.42)-нің көмегімен және ... ... ... үшін ... ... ... айнымалылардың саны 1-ге артады.
Екінші нүктеден үшіншісіне және т.с.с. өтеміз. Бұл ... ... ... өзгереді. Таңбасы бойынша шектелмеген айнымалылар үшін Кун-
Таккер ... ... ... мәні ... ... ... -ны ... арқылы -тің мәнін ұлғайтуға болады (егер
болса, онда мәні ұлғаяды, ал, ... онда ... ... ... ... ... нөлден өзгеше болса, онда оны
үшін өрнектен, базистік айнымалылар үшін теңдеуден алып тастауға және ... ... ... ... ... ... ... бірінші кезекте
таңбасы бойынша шектелмеген айнымалылардың ... ... ... ... онда ... таңбасы бойынша шектелген айнымалыны
қосамыз. Түрлендіру нәтижесінде есептің тиімді шешімі табылады.
Мысал. функциясының
шектелуіндегі ең үлкен мәнін табу ... ... ... ... ... шектеулер жүйесін келесі
түрде жазамыз
Шектеулер жүйесін және базистік айнымалыларына қатысты шешеміз:
Тәуелсіз айнымалыларын нөлге тең деп ... ... ... ... онда -тің мәні ... ... ... нөлге тең деп есептеп -дің мүмкін болған өсу шекарасын
анықтаймыз. айнымалысы ... ... ... ал ... және , ... нөлге айналады. Сондықтан
еркін таңбалы жаңа ... ... ... ...
айнымалысын қосамыз, онда шешімнің екінші нүктесі үшін келесіні аламыз:
.
Есептің шешімнің екінші нүктесі: , , , , , ... онда ... ... ... және оның өзгеру
мүмкіндіктерін анықтаймыз. -нің өсуінен тек ұлғаюы мүмкін; ... ... ... ... ... боланда
нөлге айналады, болғанда . Сондықтан базистен айнымалысын
алып тастаймыз және ... ... ... үшін:
.
Есептің шешімінің үшінші нүктесі келесідей: , , ,
, , .
Енді -ді ұлғайту ... ... ... де ... ... ... нөлге айналады, болғанда
, ... ... ... ... болғанда нөлге
айналады. Сонымен қатар айнымалысының ... жаңа ... ... ... ... ... ,
, ... шешімінің төртінші нүктесі мына түрде болады: , , ,
, , , .
, ал ... ... ... ... ... ... шешімін
береді.
үшін төртінші нүктедегі теңдеу оны басқа өрнектерден шығару
үшін қажетті. Егер тағы бір ... ... ... ... онда ... және оған сәйкес келетін теңдеуді есепке алмасақ та болар еді.
, және мәндерін ... ... үшін ... ... үшін ... түрінде өрнектеу орынды. Кестенің жоғарғы
бөлігіне (2.38) жүйесінің ... ... Оған ... ... бойынша шектелмеген сәйкес қатарларды қосамыз. үшін ... -шы ... ... 1-ге тең ... және басқа бағандармен
қиылысуы нөлге тең болады. Кестенің төменгі бөлігіне ... ... ... жазылады. Бұл кесте (2.7) кестеде
көрсетілген.
Бір кестеден екіншісіне ауысу ережесін ... ... ... ... ... ... ... қатарын
қарастырамыз. Егер осы қатардың -шы бағанмен ... ... ... тең ... ал, -ші ... ... ... оң
болмаса, онда шешім тиімді болады. Егер осы қатардың -шы бағанмен
қиылысуында жататын ... ... ... ... онда ... ... аламыз. Егер -шы баған жоқ ... ... ... ... бірінші қатарымен қиылысуында нөлдік элементтер болса,
онда бағыттаушы ... осы ... ... оң ... ... ... элементін 1-ережеге сәйкес, кестенің төменгі бөлігінің
диагональдік элементтеріне сәйкес модульдерге бөлеміз (). ... ... ... ... таңбасы -ның таңбасымен сәйкес
келетін бөліктермен ... Осы ... ... ... қатар
бағыттаушы болып табылады. Бағыттаушы қатармен бағыттаушы ... ... ... ... ... деп ... Егер ... кестенің жоғарғы бөлігінде ... ... онда ... ... ... ... айнымалысының орнына бағыттаушы
қатарға сәйкес келетін ... ... Егер ... ... ... бөлігінде жатса, онда айнымалысын ... ... ... ... ... ... келетін элементін алу
үшін соңғысының элементтерін шешуші элементке бөледі.
4. Аралық кестенің бағыттаушысыныа ... ... ... ... ... ... тең (ол бірге тең және ол бағыттаушы баған
элементтерін шешуші элементтерге бөлгенде ... ... ... басқа элементтері симплексті әдіс ережесіндегідей
алынады. Айталық - ... ... ... ... ... ... ... формулалармен есептелінеді.
6. Қорытынды кестенің жоғарғы бөлігін ... ... ... ... ... ... ... бағанмен кестенің төменгі
бөлігіндегі бас диагональда қиылысатын қатар болып табылады. Егер ... ... ... ... ... ... ондаекінші
бағыттаушы қатар біріншімен беттеседі. Аралық кестенің екінші бағыттаушы
қатарының әрбір ... ... ... бөлу ... ... ... қатары алынады (екінші бағыттаушы қатар сәйкес ... ... ... ... ... ... сәйкес келетін айнымалы да
жазылады).
Есептің шешілуі 2.8-2.14-кестелерде келтірілген.
| | | | | | |
| |1 |u1 |xm+1 |… |xn |
| | | | | | ... | | | |. . . | |
| | | | | | ... | | | |. . . | |
|: |: |: |: |: |: |
|: |: |: |: |: |: |
| | | | | | ... | | | |. . . | |
| | | | | | ... |0 |0 |1 |. . . |0 |
|: |: |: |: |: |: |
|: |: |: |: |: |: |
| | | | | | |
| |0 |0 |0 |. . . |1 |
| | | | | | |
|1 | | | |. . . | |
| | | | | | |
| | | | |. . . | |
| | | | | | |
| | | | |. . . | |
|: |: |: |: |: |: |
|: |: |: |: |: |: |
| | | | | | |
| | | | |. . . | ... |1 | | |
| |10 |-1 |-2 |
| |6 |-1 |-1 |
| |0 |1 |0 |
| |0 |0 |1 |
| 1 |0 |5 |0 |
| |5 |-1 |1 |
| |0 |1 |-2 ... |1 ... |5 |1 |-3 |
| |1 |1 |-2 |
| |5 |-1 |1 |
| |0 |0 |1 |
| 1 |25 |-5 |5 |
| |0 |1 |0 |
| |5 |-1 |-1 ... |1 ... |5 |1 |-3 |
| |1 |1 |-2 |
| |5 |-1 |1 |
| |0 |0 |1 |
| 1 |25 |0 |5 |
| |0 |-1 |0 |
| |5 |0 |-1 ... |1 ... |7/2 |-1/2 |3/2 |
| |0 |0 |1 |
| |11/2 |-1/2 |-1/2 |
| |1/2 |1/2 |-1/2 |
| 1 |55/2 |5/2 |-5/2 |
| |0 |-1 |0 |
| |9/2 |-1/2 |1/2 ... |1 ... |7/2 |-1/2 |3/2 |
| |0 |0 |1 |
| |11/2 |-1/2 |-1/2 |
| |1/2 |1/2 |-1/2 |
| 1 |119/4 |9/4 |-9/4 |
| |9/4 |-5/4 |¼ |
| |-9/4 |1/4 |-1/4 ... |1 ... |13/5 |2/5 |7/5 |
| |0 |0 |1 |
| |23/5 |2/5 |-3/5 |
| |7/5 |-2/5 |-2/5 |
| 1 |169/5 |-9/5 |-9/5 |
| |0 |1 |0 |
| |-9/5 |-1/5 |-1/5 ... |1 ... |13/5 |2/5 |7/5 |
| |0 |0 |1 |
| |23/5 |2/5 |-3/5 |
| |7/5 |-2/5 |-2/5 |
| 1 |169/5 |-9/5 |-9/5 |
| |0 |-4/5 |0 |
| |-9/5 |-1/5 |-1/5 ... ... квадраттық программалау есебін қарастырамыз:
.
квадраттық формасы теріс анықталған (жартылай анықталған).
Жоғарыда айтылғандай берілген есеп үшін (2.37) түріндегі Кун-Таккер
шартын келесі түрде ... ... ... ... ... ... болады: (2.45) жүйесінің мүмкін болған
базистік шешімдерінің ішінен ұзындығын нөлге ... ... ... ... (2.45) үшін кейбір мүмкін болған базистік
шешімдерге симплектік ... ... ... ... ... ... шешімі алынғанға кішірейеді.
Симплектік түрлендіруді базиске ... ... ... ... ала ... ... (2.45) ... бірнеше мүмкін болған базистік шешімі бар
болсын. Оған сәйкес келетін ... ... ... айнымалыдан
тәуелді функция ретінде кіретін айнымалыларды береді.Қолайлылық үшін ,
, түріндегі базиске қосылған айнымалыларын ... ... ал, ... ... ... ... Онда тәуелсіз
айнымалылар үшінде жазуға болатын келесі теңдікті аламыз:
(2.47)
Бұл үшін симплектік кестені жалғыз элементі бірге тең болатын, ... ... ... ... ... ... сияқты). Онда симплектік
кестедегі барлық ... ... ... ... ... ... , , . Тәуелсіз айнымалылары нөлге тең ... ... үшін ... ... ... ... басқа айнымалыларының мәнінің нөлге тең ... ... ... ... ... онда
(2.48)
айнымалысын базистік айнымалылардың қандай да болмасын біреуі нөлге
айналғанша ұлғайтуға болады. Бұл
(2.49)
болғанда орындалады. деп есептеп, жаңа ... ... ... ... ... қабылдайды:
.
(2.50)
мұндағы
(2.51)
(2.52)
(2.53)
Симплексті түрлендіру кезінде Т мәні ... ... ... ... ... ... Бұл базиске кіретін айнымалыны
таңдаудың жаңа ережесі болып табылады. Егер ... саны ... ... ... ішінен көбейтіндісінің ең кішісі сәйкес келетін санды
таңдайды.
ұзындығы -дан бойынша ... ... ... және -ның ... ол ... теріс емес болады.
Сондықтан тек болған жағдайда ғана теріс бола алады. Егер
болса, онда ... ... еш ... жоқ. ... ... ... жағдай кездесуі мүмкін, онда қарастырылып отырған
әдіс жарамсыз болады. Келесі жағдайды қарастырамыз ... ... (2.45) ... ... ... болсын. Пунктирлермен
берілген қисықтардың нүктелері -ға тең мән ... ... ... ... ал, ... ... ... төбеге өтуге
сәйкес келеді. Айталық алынған шешім төбесіне ... ... ... ... ... ... егер және болса.
2.7-суреттен көрініп тұрғандай бұл ... ... ... ... алгоритм есепті шешуге көмектеспейді.
Мысал. Есептің шешімін Баранкин-Дорфман әдісімен табамыз (алдында бұл
есеп Билл әдісімен ... ... ... ... табу керек.
Сәйкес матрицалары мен векторларын жазамыз:
, ,
, , , ... ... бұл ... ... ... ... ... алғашқы базистік шешімін табамыз. Бірінші теңдеуден -
ті, екінші теңдеуден -ті, төртінші теңдеуден -ні, бесінші
теңдеуден -ті, ... ... -ті ... ... ... ... шешеміз. және үшін өрнектерге -нің
табылған мәнін қоямыз. Нәтижесінде келесіні аламыз:
|Айнымалылар |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | ... ... ... ... ... |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| | | | | | ... ... базиске қосылған айнымалыларды анықтау үшін
құралған көмекші кесте қосылған. Бұл ... ... (2.47), ... (2.52), (2.53) формулаларының көмегімен есептейміз. Келесіні
аламыз:
үшін тек бір ғана теріс мәні ... ... ... ... қана ... ... ... кішірейеді. Сондықтан, ,
және көмекші ұзындықтарын тек берілген баған үшін ғана есептей
аламыз:
.
(2.50) ... ... ... және ... базиске
қосамыз. Түрлендіруді 2-5 ережесіне сәйкес, Билл әдісінде ... ... ... ... ... 2.16-кестеде келтірілген.
Көмекші кестенің элементтерін табамыз:
Келесіні аламыз
сондықтан тек базистік айнымалылардың ғана мәнін табамыз: , ,
, , , . , , және ... Билл ... ... ... ... ... келеді. Сонымен
қатар функциясының максималды мәні ... ... ... әрі ... ... ... және ... нәтжесі әсер етті. Олар ұсынған алгоритм әмбебап болды.
Айталық бізге ... ... ... берілсін:
шектелуіндегі
(2.54)
мәнін табу керек.
Мұндағы - теріс ... ... ... форма. Осы
есеп үшін Кун-Таккер шартын жазамыз:
(2.55)
. ... ... (2.55) ... ... ... ... базистік шешімдер белгілі болған жағдайда қолдануға болады.
(2.57)
функциясы айтылған базистік шешімге ... ... ... ... ... ; ; айнымалыларына сәйкес келеді. Базиске ... үшін оған ... -дер ... тең болады. Егер болса,
онда базистік шешім тиімді шешім ... Егер ... онда ... ... ... орындаймыз: -шы қадамның нәтижесінде
(2.55) шартымен қатар оған ... ... ... кестені
қанағаттандыратын мүмкін болған базистік шешімін, сондай-ақ (2.55)
шартын ... ... оң ... ... ... ... деп ... шешімін (базистік болуы шарт
емес) ... ... ... ... ... ... (2.55)
шектелуінде -ға қатысты сызықты болатын формасын минималдаймыз.
, және , векторларын ... ... ... ,
, , . ... ... ... ... тізбегін аламыз, мұндағы . Бұл тізбекті кейбір базистік
шешімдер үшін ... ... бірі ... ... ... яғни ... ... ... ... ... ... ... жағдайда
деп есептейміз, онда
, ... ... ... ... мәні ... болатындай
және арасындағы түзу кесінді нүктесі.
базистік шешімін есепке ала отырып, ... ... ... және ... ... форманы симплекс әдісімен
тағыда минималдаймыз. Франк және Вольф әрбір этапта (2.58а) немесе (2.58б)
жағдайларының тек ... ғана ... және ... ... ... (2.58а) ... ... түрде орындалатынын көрсетті.
Егер (2.55) жүйесінің мүмкін болған шешімі табылған ... ... ... ... ... ... болатынын да атап өтуге болады. Егер
(2.55) үшін мүмкін ... ... табу ... ... ал ... ... ... шешімге ие болса, онда есеп ... ие ... ... ... ерекшеліктерінің графикалық
иллюстрациясы көрсетілген. ... ... ... облыс болып
табылады. Бастапқы нүкте болсын деп есептейік. функциясын
нүктесінде линеарлаймыз және алынған ... ... ... ... ... ... (2.58б) ... орындалатын
нүктесіне өтеміз. Одан кейін ... ... ... нүктені таңдаймыз. Бұл ... ... . ... нүктесінде линеарлау арқылы және түрлендірудің екі қадамын
жасау арқылы нүктесіне, содан кейін ... ... ... тағыда (2.58б)-да қарастырылған жағдай орын алады.
кесіндісінде функциясы минимал ... ... ... . Келесі этапта (2.58а) шарты ... ... ... нүктесіне өтеміз. Суретте сондай-ақ бір
төбеден екінші төбеге өту ... ... ... өзгеруі
көрсетілген.
Франк-Вольф әдісінің келесі есепте қолданылуын ... ең ... ... табу ... ... ... ... жүйесінің келесі түрдегі базистік шешімдерін аламыз:
|Айнымалылар |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| |90 |-23 |-6 |9 |-27 ... . ... ... ... мәні
жазылатын 2.17 түрдегі симплексті кесте арқылы ... ... ... ... элементтері келесі формуламен
есептелінген
.
Сондай-ақ егер айнымалы базиске кірмесе, онда . айнымалысын
базиске ... және ... ... алып ... ... ... ... дәл Баранкин-Дорфман әдісіндегі сияқты).
Симплекті кесте келесі ережелер бойынша ... ... ... және ... ... ... ауыстыруға
болады;
2) шешуші элементтің орнына оған кері ... ... ... ... баған элементтері шешуші элементті бөледі.
4) бағыттаушы қатар элементтері шешуші ... ... ... оған ... ... ... қалған элементтері жоғарыда қарастырылған алгоритмдегідей жолмен
алынады.
|Айнымалылар |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| |387/7 |4 |-177/7 |-18/7 |27/7 ... |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| |30 |-209/8 |177/8 |15/4 |-45/8 ... ... ... ... ... ... онда есептің шешімін жалғастырамыз. ... ... алып ... және ... ... қосу ... аламыз.
және сонымен қатар болса, онда 2) ... орын ... ... ... үшін (2.60) ... пайдаланамыз.
Келесіні аламыз:
.
|Айнымалылар |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| |40 |-53/4 |7/2 |-1/4 |-11/4 ... ... ... ... ең кіші мәнге
ие болады. Функцияны ... ... ... ... |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| |56/29 |106/29 |22/29 |112/29 |-358/29 ... |1 | | | | |
| | | | | | |
| | | | | | |
| | | | | | |
| ... ... |250/841 ... ... ... айнымалыларға -ді қосамыз және -ді алып тастаймыз.
Нәтижесінде 2.21-кестені аламыз.
және болса, онда ... ... ... ... анықтау керек.
Келесіні аламыз:
.
Нәтижесінде . функциясын минималдаймыз (2.22-кесте).
айнымалысын базиске қосып, ... алып ... ... нөлге тең болатын мән қабылдайды. Сондықтан кестедегінің
барлығын есептеп жатпай, тек ... ... ғана ... ... .

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









Ұқсас жұмыстар
Тақырыб Бет саны
Сызықты программалау есептері және оларды шешу әдістері33 бет
Сұрыптау есептері. қою арқылы сұраптау8 бет
Күндегі және планета аралық кеністіктегі бейстационар процестердің мультифракталдық сипаттамалары64 бет
Интервалдағы дифференциалданатын функциялардың негізгі теоремалары.3 бет
Локальді шекті теорема15 бет
Ляпунов тұрақтылығы жайлы ақпарат3 бет
Сызықты дифференциалдық теңдеулер20 бет
Функция экстремумы.2 бет
Функция үзіліссіздігі.2 бет
Хаусдорф теоремасы12 бет


+ тегін презентациялар
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь