Кириш. Чизиқли программалаштириш (1-маъруза машғулоти)

Қавариқ тўплам

• 2-таъриф. G -тўплам қавариқ тўплам дейилади, агар у ўзининг ихтиерий иккита нуқтаси билан бирга, уларнинг қавариқ комбинациясини ҳам ўз ичига олса. Четки нуқта қавариқ тўламнинг бошқа ҳечқандай 2 та нуқтасининг қавариқ комбинацияси бўлмайди.
• 3-таъриф. Чизиқли программалаштириш масаласининг бўш тўплам бўлмаган жоиз ечимлар тўплами масаланинг ечим кўпбурчаги ёки ечим сохаси дейилади.
• Текисликда қавариқ кўпбурчак чекли учларга эга бўлган чегараланган, ёпиқ тўпламдир.

Чизиқли программалаштириш масаласининг ечимлар тўплами ҳақида

• 1-теорема. Чизиқли программалаштирш масаласининг мумкин бўлган ечимлар тўплами (агар бўш тўплам бўлмаса) қавариқ тўплам бўлади.
• 2-теорема. Чегараланган, ёпиқ, қаварик кўпбурчак ўзининг учларини қавариқ комбинациясидан иборат.
• 4-таъриф. Агар чизикли программалаш масаласининг жоиз ечимлари, ечим кўпбурчагининг четки нуқталарига мос келса, улар базис ечимлар дейилади.
• Бу таърифдан, мусбат компонентли базис ечимлар таянч ечимлар бўлиши келиб чикади.
• Бундай масалани кононик формага, яъни чегаравий шартларни фақат чизиқли тенгламалардан иборат бўлган кўринишга ўтказиш учун масалани кенгайтирилган тенгкучли масалага айлантирилади

Қавариқ программалаштириш масаласининг қўйилиши

• «қавариқ программалаш масаласи» деганда
• gi(x)=gi(x1,x2,......,xn)≤bi (i=1,…m) , (1)
• xj≥0 (j=1,…,n), (2)
• Z= f(x) =f(x1,x2,......,xn)  min . (3)
• кўринишдаги масала назарда тутилади, бунда gi(x), f(x) функциялар G⋐En қавариқ тўпламда аниқланган, пастга қавариқ функциядир. Агар f(x), gi(x) функциялар G да аниқланган юқорига қавариқ функциялар бўлса, у ҳолда қавариқ программалаш масаласи қуйидаги кўринишда берилади:
• gi(x)=gi(x1,x2,......,xn) ≥bi (i=1,…m) , (4)
• xj≥0 (j=1,…,n), (5)
• Z= f(x) =f(x1,x2,......,xn)  max . (6)