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

В
1
2
m-1
m
		j

1- жадвалда базис ўзгарувчилар деб танлаб олинган, уларнинг қийматлари тенгламанинг ўнг томонидаги қийматларга тенг деб оламиз. Биринчи жадвалда базис ўзгарувчилар устунидаги қийматлари бирга тенг бўлиши керак (биттаси бирга қолганлари нолга тенг бўлиши керак). Қолган барча базис бўлмаган ўзгарувчилар нолга тенг деб олинади.

Жадвалга мос келувчи оптимал ечимнинг мезонини қуйидагича талқин қилишимиз мумкин. Хар бир устундаги А₁ дан А_n+m гача ҳисоблашлар қуйидагича амалга оширилади:
(5.9)
Агар жадвалнинг қатордаги сонларда манфий қийматлар бўлмаса у холда бу жадвал оптимал режа бўлади ва ҳисоблаш тўхтатилади. Агар жадвалнинг қатордаги сонларда манфий қийматлар бўлса, бу режа оптимал бўлмайди, бу хол учун ҳисоблаш ишлари давом эттирилади. Қадамма қадам оптимал режани топиш давом эттирилади. Манфий қийматлар ичидан қатордаги энг кичиги танланади, шу танланган устун хал қилувчи деб олиб, уни (→) билан белгилаб, қуйидаги муносабат орқали хал қилинувчи элементи танланади:
(5.10)
Бу ерда хал қилувчи устун эканлигини билдиради. Агар қатор элементи манфий бўлса ўтказиб юборилади. нинг кичик қиймати ва шунга мос қаторнинг элементи хал қилувчи деб танлаб олинади. Яъни a_Sl элемент хал қилувчи устун ва хал қилувчи сатр кесишмасида жойлашганлиги учун, хал қилувчи элемент деб олинади. Шундан сўнг кейинги симплекс жадвални тўлдиришга ўтамиз. Бу жараён чизиқли алгебраик тенгламалар ечишнинг номаълумларни кетма кет йўқотиш усулига ўхшаш олиб борилади. Аввало хал қилувчи элемент қаторидаги элементларни хал қилувчи элементга бўламиз. Хал қилувчи элемент ўрнида бирни хосил қиламиз. Кейин хал қилувчи элемент қаторидаги сонларни шундай мос сонга кўпайтириб, бошқа қатор мос сонларига қўшамизки, нарижада хал қилувчи устунимизда қолган сонлар нолга айлансин. Биз кўраётган холда кўпайтувчилар қуйидагига тенг бўлади Шундан сўнг иккинчи симплекс жадвалига ўтамиз, бу жадвалда ҳам юқорида бажарилган амалларни такрорлаймиз. Бу жараён оптимал режа натижасига эришгунимизча давом эттирилади.
Энди олдинги мавзуда ўтилган (4.1)-(4.3) масалани симплекс усулида ечилишини кўриб чиқамиз.

Бу масалани каноник кўринишга келтириб оламиз, яъни сунъий ўзгарувчиларни тенгсизликнинг чап томонига киритамиз

Бу тенглама учун биринчи симплекс жадвалини тузиб оламиз: