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

1-жадвал

i			1000	1400	0	0	0
		Базис						В
1	0		0.1	0.3	1	0	0	30	100
2	0		0.5	0.2	0	1	0	45	225
3	0		0.1	0.1	0	0	1	12	120
		J	-1000	-1400 →	0	0	0

Биринчи жадвални ҳисобларсиз тўғридан тўғри масалани шарти бўйича тўлдирамиз. Бу ерда базис ўзгарувчилар ҳам масала берилишидан олинади. Жадвалда бу ўзгарувчиларнинг мос қийматлари устунида бир турибди. Базис ўзгарувчилари нархлари кўрситилган устунида ҳам нол турибди, яъни с₃=с₄=с₅=0. Энди ни ҳисоблаймиз.

Бу ерда хал қилувчи элемент иккинчи устунда бўлади. Жадвалда у стрелка билан белгиланди. Жадвалда қиторда манфий қийматлар бўлгани учун, бу қатордаги ечимлар режаси оптимал бўлмайди. Жадвалдаги устунни қуйидаги формула бўйича қийматларини аниқлаймиз Топилган натижалар ичидан энг кичик нинг қиймати 100 тенг экан, шунинг учун биринчи қаторда хал қилувчи элемент қиймати бўлади. Жадвалди бу қаторни стрелка билан белгилаймиз. Хал қилувчи элементини белгилаб оламиз 0,3. Иккинчи симплекс жадвални тўлдиришни бошлаймиз. Бу жадвални катталиги аввалгиси билан бир хил бўлади. Жадвални тўлдиришни хал қилувчи қатордан бошлаймиз. Қатордаги ҳамма сонларни 0,3 га бўламиз.
3-жадвал.

i			1000	1400	0	0	0
		баз						В
1	1400		1/3	1	10/3	0	0	100	300
2	0		13/30	0	-2/3	1	0	25	16000/13
3	0		2/30	0	-1/3	0	1	2	30
		j	-1600/3	0	14000/3	0	0

Жадвалда қолган қатор катакларини юқорида айтилган ҳисоблашлар орқали тўлдирилади. Янги хосил бўлган қаторни 0,2 га кўпайтириб иккинчи қатор элементларини айириб, шу қаторга ёзамиз, худди шундай учинчи қаторни 0,1 га кўпайтириб юқоридаги амални бажарамиз. Бу жадвал режаси қуйидагига тенг бўлади

Топилган режани оптималикка текширамиз. ҳисоблаймиз:


Бу қаторда манфий қийматлар борлиги учун учинчи симплекс жадвалига ўтамиз. Худди аввалгидек хал қилувчи қаторни танлаб, шу қаторни хал қилувчи элементига бўлиб ёзиб оламиз.
Учинчи симплекс жадвал.
4 -жадвал.

i			1000	1400	0	0	0
		баз
1	1400		0	1	5	0	-5	90
2	0		0	0	3	1	-6.5	12
3	1000		1	0	-5	0	15	30
			0	0	2000	0	8000

Бу жадвалда қаторда ҳаммаси мусбат Шунинг учун топилган режа оптимал бўлади. Шундай қилиб, жадвалдаги топилган режа оптимал бўлади. Охирги жадвал режасида жавобимиз қуйидагига тенг бўлади Симплекс усулида биз хар бир қадамида таянч ечимини оламиз, ва секин аста оптимал ечимга яқинлашиб борамиз. Биз биринчи қадамда О(0,0) нуқтидан бошлаймиз, яъни . 4 расмдан кўриниб турибди. Иккинчи қадамда А (0;100) нуқтага ўтамиз. Учинчи қадамда В(30,90) нуқтага ўтамиз. Бу симплекс ғоясига мос келади.

Шуни таъкидлаш керакки, симплекс усулида бир вақтнинг ўзида ҳам берилган ва ҳам иккиланган масаланинг ечимини топиш мумкин. Охирги симплекс жадвалда устунида базис ўзгарувчилар қийматини оламиз. Бизнинг жадвалимизда бу қийматлар га тенг. Охирги қаторда сунъий базис номаълумлари остида иккиланган масаланинг ечимлари бўлади. Бизнинг мисолимизда бу қийматлар га тенг. Бундан биз эканлигини кўришимиз мумкин. Бу хол учун қийматини ҳисоблаймиз:


_{Агар бу ечимни бирламчи ечим билан солиштирсак бир хиллигини кўрамиз}:
Бу эса иккиланганлик назариясига мос келади.

• 
  Мустақил иш сифатида қуйидаги иккиланган масалани геометрик усулда ечиб кўринг, симплекс жадвал усулдаги ечим билан солиштиринг: