Чизикли программалаштириш масаласининг

+авари= тыпламлар
Чизи=ли программалаштириш масалаларининг
ечим хоссалари

+авари= тыпламлар назариясидан баъзи тушунчаларни келтирайлик.

1-таъриф. (геометрик) Агар тыплам ихтиёрий 2 ну=таси билан уларни туташтирувчи кесмани ыз ичига олса тыплам =авари= дейилади (Чизма 9.а) да =авари= былмаган, (Чизма 9.б) да =авари= былган тыпламлар тасвирланган.



2-таъриф. (алгебраик) Агар щар бир , ва ихтиёрий учун былса тыплам =авари= дейилади (чизма 9.б) бу ерда тыпламнингг ихтиёрий ну=таси.
Энди масала ечимлари хоссаларини баён этамиз.
1-хосса. Агар чизи=ли программалаштириш масаласининг ечимлар тыплами биттадан орти= ну=тага эга былса, у =авари=дир. Каноник кыринишда берилган масалани кырайлик.
(4.1)
(4.2)
(4.3)
Исбот. Ихтиёрий ва , -(4.1)-(4.3) масаланинг ечимлар тыплами, у щолда , (4.2)-(4.3) системани =аноатлантиради, яъни
(4.4)
(4.5)
(4.6)
(4.7)

(4.4) тенгламани иккала томонини га (4.6) тенгламанинг икки томонини га кыпайтириб ва уларни щадма-щад =ышиб, ни щосил =иламиз. деб белгилаб, ни оламиз. Маълумки, , . Бундан нинг (4.1)-(4.3) масаланинг ечими эканлиги келиб чи=ади, яъни , таъриф быйича -=авари= тыплам.

2-хосса. Агар чизи=ли программалаштириш масаласининг оптимал ечимлар тыплами 1 дан орти= ну=тага эга былса, у щолда у =авари=дир.
Исбот. , -(4.1)-(4.3) масаласининг оптимал ечимлари былсин.
, щам масаланинг оптимал ечимлари тыплами- былгани учун ва , -оптимал ечимлигидан, , ва лигидан , яъни масаланинг ечими былади. Энди уни оптималлигини исботлайлик.
, яъни ечимда ма=сад функцияси энг катта =ийматга эга былади ва -оптимал ечими ва =авари= тыплам таърифидан -оптимал ечимлар тыплами =авари= тыплам.
3-таъриф. Агар тыпламнинг ну=тасининг =андайдир 2 хил ну=та =авари= комбинацияси кыринишида тасвирлаш мумкин былмаса ну=та тыпламнинг четки ну=таси дейилади, (Кыпбурчакнинг чекка ну=таси унинг учидир).