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

3-хосса. ЧП масаласининг чизи=ли ма=сад функцияси ызининг оптимал =ийматига чеклашлар системаси билан ани=ланган =авари= тыпламнинг четки ну=таларида эришади.
Исбот. Фараз =илайлик бирор ну=таси тыпламнинг четки ну=та билан устма-уст тушмайди ва унда ма=сад функцияси ызининг максимал =ийматига эришади .
четки ну=та былмагани учун уни четки ну=таларининг =авари= комбинацияси кыринишида тасвирлаш мумкин.
- тыпламнинг четки ну=талари былсин у щолда , бу ерда ва . Бу ифодада -ма=сад функциянинг четки ну=талардаги =ийматлари, уларнинг ичидан ма=сад функциясига максимум берадиганини танлаб оламиз, яъни ю=оридаги тенгликдан . -соща ичидаги энг катта =иймати, четки ну=талардаги энг катта =иймати чунки энг катта =иймат мумкин былган =ийматлардан кичик былмайди.
Шундай =илиб, ма=сад функцияси ызининг максимал =ийматига тыпламнинг бирор четки ну=тасида эришади.


Чизи=ли программалаштириш масаласини
ечиш усуллари ва уларнинг и=тисодий тащлили

Чизи=ли программалаштириш масалаларини ечишда иккитадан кып сонли ызгарувчиларга эга былган щолда симплекс усулидан фойдаланилади. Бу усул чизи=ли программалаштириш масалаларини ечишнинг умумий усули былиб, унинг ёрдамида масаланинг фа=атгина оптимал ечимлари топилмай, олинган ечим и=тисодий тащлил щам =илинади. У масалани =адамлар ёрдамида ечади. Бу усул кыпинча оптималлаштириш масалаларида, жараёнларни текшириш моделлари ёрдамида ечиладиган масалаларда =ылланилади. Чизи=ли программалаштириш масалаларини ечишнинг геометрик маъносига кыра оптимал ечим кыпбурчакнинг учки (экстремал) ну=таларидан бирига мос келади. Ана шу натижа симплекс усулининг асосини ташкил этади. Унинг щисоблаш алгоритми бирор дастлабки олинган мумкин былган (экстремал) ну=тадан бош=асига тартиб билан кетма-кет ытишлар ёрдамида оптимал ечимни топишдан иборат. Кыпинча масалаларни ечишда (масалан аввалги бобдаги график усулда ечилган масалани олсак) бошлан\ич ечим танлаб олинади, ундан =ышни учки ну=тага ытилади, щар бир учки ну=тага иккита =ышни ну=та мавжуд былади. Улардан =айси бирини танлаш ма=сад функциясининг коэффициентларига бо\ли=. Ундаги каттаро= коэффициентли ызгарувчининг ысиш томонига юрилади. Шундан кейин процесс =айтарилади. Щар гал оптималлик текширилади, кейин оптимал былмаган ечимдан навбатдаги =ышни ну=тага ытилади. Ор=ага =айтилмайди. Бу жараён токи оптимал ну=та топилгунча давом этади.

Ма=сад функцияси щар бир =адамдан навбатдагисига ытишида =уйидагича ызгаради:1) щар бир =адамда ма=сад функциясининг ысиши сезилади, чекли =адамдан сынг оптимал ечимга я=инлашади; 2) щар бир =адамда ма=сад функциянинг ысиши сезилади, лекин жараён чексиз =адамлардан иборат былади.
Каноник кыринишдаги чизи=ли модел та тенглама ва ызгарувчига эга былсин.
+уйидаги =оидаларни келтирамиз:

1. 
   та тенглама ва та номаълум учун щар бир экстремал ну=тада та номаълум 0 га тенг.
   
2. 
   +ышни экстремал ну=талар битта номаълумга фар= =илади. Экстремал ну=таларни топиш учун та номаълумни га тенглаш керак. Бу экстремал ну=талар бир =ийматлигини билдиради. Щар бир экстремал былмаган ну=тага 1 дан кып былмаган га тенг номаълум мос келади. Сощанинг ичидаги ихтиёрий ну=та 1 та щам нолга тенг ызгарувчига эга эмас, ихтиёрий чегарада ётган экстремал былмаган ну=та эса щамма ва=т щеч былмаганда 1 та нолга тенг ызгарувчига эга.
   

Экстремал ну=таларнинг бир =ийматлилик хоссаси уларни алгебраик усул билан ани=лашга имкон беради. Барча жоиз экстремал ну=талар та 0 га тенг ызгарувчили та тенгламалар системасининг барча бир =ийматли манфий былмаган ечимлари каби ани=ланади.
та ызгарувчини 0 га тенглаш йыли билан топилган бундай бир =ийматли ечимлар базис режалар дейилади. Агар улар система тенгламалари ынг томонларининг манфий эмаслик шартини бажарса жоиз базис режалар дейилади. 0 га тенг ызгарувчилар эркин, =олганлари базис ызгарувчилар дейилади.
+ышни экстремал ну=талар битта ызгарувчига фар= =илади, шунга кыра щар бир кейинги =ышни экстремум ну=тани нобазис ызгарувчини базис ызгарувчига алмаштириб топиш мумкин. Ю=оридаги масалага кыра бир ну=тадан иккинчисига ытишда ызгарувчи (нобазис) 0 га тенг =ийматидан иккинчи ну=тада мос =ийматига ысади. Иккала ну=тада автоматик равишда 0 га айланади ва нобазис ызгарувчи былиб =олади. Шундай =илиб нобазис ва базис ызгарувчилар тыпламлари ыртасида ва ызгарувчилар ызаро ырни алмашади.
Шунга ыхшаш жараённи щамма экстремал ну=талар учун =ыллаб ихтиёрий экстремум ну=тани биттадан нобазис ва базис ызгарувчиларни алмаштириб щар доим топиш мумкин.
Базисга киритилувчи ызгарувчи ва базисдан йы=отилувчи (чи=арилувчи) ызгарувчи тушунчаларини киритиш керак. Киритилувчи ызгарувчи деб щозирча нобазис, кейинги =адамда =ышни экстремал ну=тага ытганда базис ызгарувчилар тыпламига киритиладиган ызгарувчига айтилади. Чи=арилувчи ызгарувчи деб кейинги =адамда базис ызгарувчилар тыпламидан чи=ариладиган базис ызгарувчига айтилади.
Масаланинг оптимал режасини топиш учун унинг мумкин былган базис ечимларини топиш ва улар ичидан оптималини танлаш керак, бунинг учун ||a_ij||, i= матрицасининг устунлари ичидан навбатма-навбат m та устун танлаб m номаълумли m та чизи=ли тенгламалар системасини ечиш керак. Бу усул та тенгламалар системасини ечишни талаб =илади, m унча катта былмаганда щам бу жуда =ийин. Америкалик олим Ж.Б. Дапциг томонидан ишлаб чи=илган симплекс усули бундай масалаларни ечишда =ыл келади.
Ю=орида кырилган 1-боб 1-§ да берилган «картошка масаласи»нинг оптимал режасини топайлик. Масаланинг математик модели
Z=5х₁+6х₂ max

ни каноник кыринишга келтирамиз.

Бу системанинг шундай жоиз (мумкин былган) базис режасини топайликки, у Z=5х₁+6х₂ га максимум =иймат берсин. Система 5 та номаълумли 3 та тенгламадан иборат, демак базис ызгарувчилар сони 3 та, нобазис ызгарувчилар 2 та.
Бу масалани симплекс усул билан ечиш учун ихтиёрий базис ечим топилади. Базис ызгарувчилар сифатида х₃, х₄, х₅, =ышимча ызгарувчиларни оламиз. Уларнинг коэффициентларидан тузилган матрица бирлик матрица былгани учун детерминанти 1 га тенг (0 дан фар=ли),система ечимга эга. Нобазис ызгарувчилар х₁, х₂, ни 0 га тенглаб бошлан\ич Х=(0;0;18;12;24) базис режани оламиз.