Чизиқли программалаш масалалари (чпм) ларни ечишда Симплекс усул моҳияти ва алгоритми

5-маъруза
Чизиқли программалаш масалалари (ЧПМ) ларни ечишда Симплекс усул моҳияти ва алгоритми.
Чизиқли программалаш масалалари (ЧПМ) ларни ечишда унинг оптимал ечимини таянч ечимлари орасидан топиш керак. Таянч ечимини топиш учун агар ноъмалумларнинг сони учтадан кўп бўлса биз геометрик усулдан фойдалана олмаймиз. Шунинг учун биз бундай масалаларни қандай катта ўлчовли бўлишидан қатъий назар, уни ечишнинг универсал усулини танлашимиз керак бўлади. Бундай усуллардан бири симплекс усули бўлиб, бошқача қилиб айтганда, бу усулни режаларни такомиллаштириб борувчи усул деб ҳам айтиш мумкин. Симплекс усулининг моҳияти шундан иборатки, аввал унинг бошланғич таянч ечими режасини тузиб оламиз. Биз бошланғич шартни текшириш натижасида кейинги яхшиланган ечим режасини оламиз. Бу жараённи биз оптимал ечим режасини олгунча давом эттирамиз. Хар бир қадамда биз масаланинг яна бир таянч ечимини оламиз. Таянч ечимлар сони кўпбурчак учларидаги ечимлари сонига тенг бўлса, симплекс усулида ҳам ечимлар сони унинг шунча қадамлари сонига тенг бўлади. Чизиқли программалаш масалаларини симплекс усулида ечиш учун уни каноник кўринишга келтириб олиш керак бўлади, яъни, ҳамма чекланишлар шартларидаги тенгсизликлар тенгламалар кўринишига келтирилиши керак. Бунинг учун биз тенгсизликнинг чап томонига сунъий номаълумларни киритиш билан эришамиз.
Бу жараённи қуйидаги чизиқли программалаш масаласида кўриб ўтамиз:

Аввал (5.1) тенгсизликни тенгламага айлантириш учун биз тенгсизликни чап томонига сунъий х_n+1, x_n+2,…,x_n+m, номаълумларни қўшамиз, мақсад функциясида бу номаълумлар учун c_n+1=c_n+2=…=c_n+m=0 га тенг бўлади. Яъни сунъий ўзгарувчиларнинг нархи нолга тенг бўлади. Шундан сўнг (5.1)-(5.3) масалани қуйидагича ёзиб оламиз:
Бундан кўринадики х_n+1, x_n+2,…,x_n+m, лар қандай қиймат қабул қилишидан қатъий назар мақсад функцияси га таъсир қилмайди, чунки c_n+i=0; i=1, 2,…,m.
Чизиқли программалаш масаласи (5.4)-(5.6) ни матрица кўринишини қуйидагича қисқа кўринишда ёзиш мумкин:

Бу ерда тўғри тўртбурчак шаклидаги матрица. сатр матрица, устун матрица, устун матрица.
Энди симплекс усулининг моҳиятини кўриб чиқамиз. Бунинг учун биз олдин базис ўзгарувчиларни танлаб олишимиз керак бўлади, базис ўзгарувчилар m та захиралар сонига тенг бўлиши керак. Базис ўзгарувчилардан тузилган А устун матрица бирлик матрица бўлиши керак. Базис ўзгарувчиларнинг қийматлари тенгламанинг ўнг томонидаги қийматлардан олинади. Агар система шартларни қаноатлантирмаса, у холда шундай кўринишга келтириб олиш керак бўлади. Шундан сўнг биринчи симплекс жадвалини тузишга ўтамиз, у қуйидаги кўринишда бўлади:
1-жадвал.

I
		базис