Соли= ва божхона органлари академияси

0	-2	-3	-4	0	0
0
	6	1	1/2	1	1/2	0	0
	8	1	0	0	-1	1	0
	6	1	3/2	0	-1/2	0	1
	24	2	-1	0	2	0	0
	4	2/3	0	1	2/3	0	-1/3
	8	1	0	0	-1	1	0
	4	2/3	1	0	-1/3	0	2/3
	28	8/3	0	0	5/3	0	2/3

Энди чизиқли дастурлаш масалаларини ечишда алоҳида ҳолатлар вужудга келадиган мисолларни кўриб чиқайлик.

8.2-мисол. Симплекс усули ёрдамида қуйидаги чизиқли дастурлаш масаласи ечилсин:


( ).
Ечиш. Масала шартига асосан , ва лар базис ўзгарувчилар, , ва лар эса озод ўзгарувчилар бўлади. (7.3) ифодалардан фойдаланиб, базис ўзгарувчиларни озод ўзгарувчилар орқали ифодалаймиз:

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

8.2 – ж а д в а л

Базис ўзгарувчилар	Озод ҳадлар
	5	1	0	0	2	-3	-2
	6	0	1	0	3	-2	-4
	3	0	0	1	-4	-1	2
	-4	0	0	0	2	2	-1

8.3-мисол. Симплекс усули ёрдамида қуйидаги чизиқли дастурлаш масаласи ечилсин:


, .
Ечиш. ва қўшимча ўзгарувчиларни киритиб, берилган ЧДМни каноник кўринишга келтирамиз:


( ).
Масала шартига асосан ва лар базис ўзгарувчилар, ва лар эса озод ўзгарувчилар бўлади. Мақсад функциясини (7.4) кўринишга келтирамиз (берилган мақсад функциясида базис ўзгарувчилар нолга тенг коэффициентлар билан қатнашганлиги учун (7.3) ифодалардан фойдаланишга зарурат йўқ):
.
Шу муносабатдан ва масаланинг шартларидан фойдаланиб, масаланинг симплекс жадвалини тузамиз (8.3-жадвал). Симплекс усулининг биринчи итерациясида бошланғич ечим учун оптималлик мезони бажарилмайди. Шунинг учун ўзгарувчи базисга киритилиб (бунда масала мақсад функциясининг чекли максимумга эга эмаслиги шарти бажарилмайди), унинг ўрнига (7.5) формулага асосан базисдан ўзгарувчи чиқарилади.

8.3 – ж а д в а л

Базис ўзгарувчилар	Озод ҳадлар
	5	4	1	1	0
	1	1	-1	0	1
	0	-4	-1	0	0
	1	0	5	1	-4
	1	1	-1	0	1
	4	0	-5	0	4
	1/5	0	1	1/5	-4/5
	6/5	1	0	1/5	1/5
	5	0	0	1	0

Иккинчи итерацияда ечим учун ҳам оптималлик мезони бажарилмайди. Шунинг учун базисдан ўзгарувчи чиқарилиб, унинг ўрнига базисга ўзгарувчи киритилади.

Масаланинг оптимал ечими учинчи итерацияда топилди:
, .
Охирги сатр элементларидан озод ўзгарувчиларга мос келувчилари ҳам нолга тенг бўлгани учун бу оптимал ечим ягона эмасдир.
Ҳақиқатан, масалан, , ва ечимлар ҳам оптимал ечимлардир, улар учун ҳам бўлади.


Такрорлаш ва назорат учун саволлар :

1. 
   Чизиқли дастурлаш масаласидаги чеклашларнинг барчаси «≤» кўринишдаги чизиқли тенгсизликлардан иборат бўлган ҳолда Данцигнинг симплекс усулини қандай қўллаш мумкин?