Математик программалаштириш-нинг махсус масалалари Ўйинлар назарияси Чизиқсиз программалаштириш

Қавариқ программалаштириш
Чизиқсиз программалаштириш масаласи берилган бўлсин:

бунда ва - функциялар ўзгарувчиларга боғлиқ.
Бундай масалаларни ечишнинг универсал усули мавжуд эмас. Баъзи қўшимча шартлар киритилганда, уни ечиш усулини ишлаб чиқса бўлади. Агар пастга (юқорига) қавариқ функциянинг мумкин бўлган ечимлар соҳаси, (8) ва (9) чегаравий шартларни қаноатлантирсин. Бошқача айтганда, агар масаланинг мумкин бўлган ечимлари қавариқ, мақсад функцияси эса – ботиқ (максимум масала учун) ёки қавариқ (минимум масала учун) бўлса, оптималь ечим, глобал оптимум бўлади.
Таъриф. функция, қавариқ X тўпламда пастга қавариқ дейилади, агар X тўпламдаги ихтиёрий нуқталар ва учун, қуйидаги муносабат бажарилса (3 - расм)
(10)





3- расм. Функция қавариқ ёки қавариқлиги пастга қараган.
Таъриф. функция, қавариқ X тўпламда юқорига қавариқ дейилади, агар X тўпламдаги ихтиёрий нуқталар ва учун, қуйидаги муносабат бажарилса (4 - расм)
(11)




4 – расм. Функция ботиқ ёки қавариқлиги юқорига қараган.
Таъриф. Агар масаланинг мумкин бўлган ечимлар соҳаси (8), (9) шартларни қаноатлантириб, шу соҳадаги ҳеч бўлмаганда битта нуқтада, шартларни қаноатлантирса, у ҳолда ечимлар соҳаси регулярлик шартини қаноатлантиради дейилади.
Таъриф. (7)-(9) масала, қавариқ программалаштириш масаласи дейилади, агар функция пастга (юқорига) қавариқ ва
лар қавариқ бўлса.
Теорема. Қавариқ программалаштириш масаласининг ихтиёрий локал максимуми (минимуми), унинг глобал максимуми (минимуми) бўлади.
Таъриф. (7)-(9) қавариқ программалаштириш масаласининг Лагранж функцияси қуйидагидан иборат
бунда - Лагранжа кўпайтувчиларидир.
Таъриф. Нуқта Лагранж функцияси учун эгар нуқта дейилади, агар ихтиёрий ва лар учун қуйидаги тенгсизлик бажарилса

Теорема (Кун-Таккер). Қавариқ программалаштириш масаласининг (7)-(9), мумкин бўлган ечимлар соҳаси регулярлик хоссасига эга ва вектор мавжуд бўлса, оптимал ечим мавжуд бўлиши учун, Лагранж функциясининг эгар нуқтаси бўлиши зарур ва етарлидир.
Агар мақсад функция ва функциялар узлуксиз дифференциалланувчи бўлса, Кун – Таккер теоремасини аналитик ифодалар билан тўлдириш мумкин. Бунда, зарурий ва етарлилик шарти бўлиб, Лагранж функциясининг эгар нуқтаси бўлишлиги учун, қавариқ программалаштириш масаласининг ечими бўлишлиги талаб этилади.
Бу муносабатларлар қуйидагича бўлади

Бунда ва - эгар нуқтада ҳисобланган Лагранж функцияси

хусусий ҳосилаларнинг қийматлари.