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

0	0	-1	3	0	-2
0
	10	1	5/2	0	1/4	-2	0
	3	0	-1/2	1	1/4	0	0
	1	0	-5/2	0	-3/4	8	1
	-9	0	1/2	0	-3/4	-2	0
	4	2/5	1	0	1/10	-4/5	0
	5	1/5	0	1	3/10	-2/5	0
	11	1	0	0	-1/2	6	1
	-11	-1/5	0	0	-4/5	-8/5	0

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

1. 
   Симплекс усули нима учун зарур, унинг ғояси нимадан иборат ҳамда симплекс усулини ривожлантиришга ким ҳисса қўшган?
   
2. 
   Данциг яратган симплекс усулининг ўзига хос хусусиятлари нимадан иборат?
   
3. 
   Данциг усулида бошланғич ечим қандай топилади?
   
4. 
   Симплекс жадвал қандай кўринишда бўлади?
   
5. 
   Ечимнинг оптималлик мезони, чизиқли дастурлаш масаласининг мақсад функцияси чекли минимумга (максимумга) эга бўлмаслик ва оптимал ечимнинг ягоналиги шартлари нималардан иборат?
   
6. 
   Ечим оптимал ечимга яқинроқ бўлган бошқа ечимга қандай алмаштирилади?
   

8-мавзу


Чизиқли дастурлаш масалаларини симплекс усулида ечиш


Режа :

1. 
   Баъзи чизиқли дастурлаш масалаларини симплекс усулида ечиш.
   

Аввалги мавзуда кўрганимиздек, агар чизиқли дастурлаш масаласининг чеклашлар системасида m та базис ўзгарувчи, масалан, ўзгарувчилар мавжуд бўлса, у ҳолда чизиқли тенгламаларнинг ўнг томонлари номанфий бўлганда бошланғич ечим аниқланган бўлиб, бу ечимдан келиб чиққан ҳолда симплекс усули ёрдамида оптимал ечим топилади.
Фараз қилайлик, чизиқли дастурлаш масаласи қуйидаги кўринишда берилган бўлсин:
номаълумларнинг
(8.1)
функцияга минимал қиймат берувчи ҳамда
, (8.2)
, , …, (8.3)
шартларни қаноатлантирувчи қийматлари топилсин, бу ерда ( ).
Бу масаладаги (8.2) чеклашларнинг барчаси «≤» кўринишдаги чизиқли тенгсизликлардан иборат ҳамда уларнинг ҳар бири чап томонига номанфий қўшимча ўзгарувчи қўшиш йўли билан чизиқли тенгламага айлантирилади. Бу қўшимча ўзгарувчилар базис ўзгарувчилар бўлади. Демак, бу ҳолда ҳам Данцигнинг симплекс усулини қўллаш мумкин бўлади.


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


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


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

Базис ўзгарувчилар	Озод ҳадлар
	12	2	1	2	1	0	0
	20	3	1	2	0	1	0
	12	2	2	1	0	0	1