2-мавзу. Чизиқли дастурлаш режа

i

Базислар

Базис коэф. Сб

…

…

…

…

…

…

…

…

…

…

1

1

0

…

0

…

0

…

…

…

2

0

1

…

0

…

0

…

…

…



































l

0

0

…

1

…

0

…

…

…



































m

0

0

…

0

…

1

…

…

…

m+1

0

0

…

0

…

0

…

…

…

Биринчи симплекс жадвал тузилгандан кейин унинг (m+1) сатрини қараймиз. Чизиқли дастурлаш масаласи минимумга ечилаётган бўлса, барча лар учун ёки масала максимумга ечилаётган бўлса, бўлса, таянч ечим оптимал бўлади ва чизиқли функциянинг оптимал қиймати дан иборат бўлади.
Чизиқли дастурлаш масаласи минимумга ечилаётган бўлиб, бўлса, ечим оптимал бўлмайди ва бу баҳога мос векторни базисга киритиб ечимни яхшилаш мумкин, яъни чизиқли функциянинг олдинги қийматидан кичикроқ қийматини топиш мумкин бўлади.
Мусбат баҳолар бир нечта бўлса, улардан энг каттасини базисга киритилади. Энг катталари бир нечта бўлса, улардан бўлгани олдин базисга киритилади. Ҳеч бўлмаганда битта мусбат баҳо учун мос вектор ёйилмасидаги коэффициентлари ичида манфийлари бўлса, чизиқли функция ечимлар кўпбурчагида чегарланмаган бўлади.
Энг катта бўлсин, яъни максимал қиймат k - вектор учун бўлсин, . Бу ҳолда вектор базисга киритилиб, мос келган вектор базисдан чиқарилади. бўлсин, яъни l - сатрдаги вектор базисдан чиқарилади. элемент очувчи (калитли) элемент дейилади ва бу элементга мос устун ва сатрлар йўналтирувчи (калитли) деб аталади.
Янги таянч ечим ва векторлар янги базисдаги ёйилмаси ( учун)

формулалар ёрдамида топилади. Бу Жордан-Гаусс номаълумларни тўла йўқотиш формулаларидир, ҳақиқатан учун

ҳосил бўлади, яъни базисга киритилган вектор ёйилмаси учун очувчи элемент коэффициенти 1 бўлиб қолган коэффициентлари 0 лардан иборат бўлади.
Шундай қилиб, , ( ) векторларнинг янги базисдаги ёйилмаси коэффициентларини, янги таянч ечим баҳоси қийматини ҳамда чизиқли функция қийматини топиш учун йўналтирувчи сатр ҳамма элементларини ечувчи элементга бўламиз ва бир марта тўлиқ Жордан-Гаусс методидан фойдаланиб, 2-симплекс жадвални тузамиз.
2-симплекс жадвал.

i

Базислар

Базис коэф. Сб

…

…

…

…

…

…

…

…

…

…

1

1

0

…

…

0

…

…

0

…

2

0

1

…

…

0

…

…

0

…



































l

0

0

…

…

0

…

…

1

…



































m

0

0

…

…

1

…

…

0

…

m+1

0

0

…

0

…

…

0

…

Ҳисоблашларнинг тўғри бажарилганлигини
;
формулалар ёрдамида назорат қилиш мумкин.
2-симплекс жадвалнинг (m+1) сатрида ҳамма баҳолар бўлса олинган ечим оптимал бўлади. Мусбат баҳолар бўлса, кейинги таянч ечимни топишга ўтилади. Жараён оптимал ечимни олгунча давом эттирилади ёки чизиқли функция чегараланмаганлиги кўрсатилади. Оптимал ечим баҳолар ичидаги 0 баҳо факат базис векторларига мос келса, оптимал ечим ягона бўлади, 0 баҳо базисда бўлмаган векторга ҳам мос келса, умуман оптимал ечим ягона бўлмайди.
Чизиқли дастурлаш масаласида чизиқли функциянинг максимум қиймати топилаётган бўлса ва баҳолар бир нечта бўлса, улардан бўлган вектор олдин базисга киритилади. Бу ҳолда ҳам симплекс усул жараёни, чизиқли функциянинг минимум қийматини топишдагидек бўлади.
1-мисол. чизиқли функциянинг

чеклаш шартлари системасини қаноатлантирувчи максимум қийматини топинг.
Ечиш. Бошланғич таянч ечим қаралган усулда озод ҳадларнинг фақат мусбат қийматларида топилганлиги учун иккинчи тенгсизликни (-1)га кўпайтириб

чеклаш шартларини ҳосил қиламиз. Энди тенгсизликлардан тенгликларга ўтамиз:

Охирги системани вектор формада ёзамиз:

бирлик векторларни бошланғич таянч ечим учун қабул қилиб, номаълумларни 0 га тенг деймиз. Натижада таянч ечимни олмиз, бунга

ёйилма мос келади.
ечимнинг оптималлигини текшириш учун биринчи симплекс жадвални тузамиз:
1-симплекс жадвал.

i	Базис-лар	Базис коэффи-циент-лар Сб	A0	4	6	0	0	0
				A1	A2	A3	A4	A5
1	A3	0	784	16	4	1	0	0
2	A4	0	552	8	7	0	1	0
3	A5	0	567	5	9	0	0	1
m+1			0	-4	-6	0	0	0

ва баҳоларни ҳисоблаймиз:
, , , , , , , , , , .
Олинган баҳолар ичида иккита, , манфий баҳолар мавжуд бўлиб, улар бошланғич таянч ечим оптимал эмаслигини билдиради. Базисга бўлган вектор ни киритамиз. бўлганлиги учун очувчи (калит) элемент 9 бўлиб, у жойлашган устун ва сатрлар йўналтирувчи бўлади. Демак, базисга векторни киритиб векторни базисдан чиқарамиз. 2-симплекс жадвални тузамиз:

2-симплекс жадвал.

i	Базис-лар	Базис коэффи-циент-лар Сб	A0	4	6	0	0	0
				A1	A2	A3	A4	A5
1	A3	0	532	124/9	0	1	0	-4/9
2	A4	0	111	37/9	0	0	1	-7/9
3	A2	6	63	5/9	1	0	0	1/9
m+1			378	-6/9	0	0	0	6/9

Биринчи симплекс жадвалдаги йўналтирувчи (калит) сатрга мос иккинчи симплекс жадвалдаги сатрга бош сатр деб атаймиз ва унинг элементларини ҳисоблашдан бошлаймиз: 3-сатр яъни йўналтирувчи (калит) сатр элементларини очувчи (калит) элементга бўлиб, 63, 5/9, 1, 0, 0, 1/9 ларни топамиз. Бу сатрни 4 га кўпайтириб 1-сатр мос элементларидан айириб 532, 124/9, 0, 1, 0, -4/9, 2-симплекс жадвал биринчи сатр элементларини, 7 га кўпайтириб 2-сатр элементларидан айириб, 111, 37-9, 0, 0, -7/9, 2-жадвалнинг 2-сатр элементларини ҳисобладик. Энди 6 га кўпайтириб (m+1) сатр мос элементларига қўшиб 378, -6/9, 0, 0, 0, 6/9 2-жадвалнинг (m+1) сатр элементларини оламиз.

2-симплекс жадвалда

2-таянч ечим олинди. Бу ечимга чизиқли функциянинг

қиймати мос келади.
(m+1) - сатрда манфий баҳо мавжуд бўлганлиги учун ечим оптимал эмас. вектор базисга киритилиши керак. бўлиб, 37/9 очувчи (калит) элемент бўлади.
Базисдан вектор чиқарилади, 3-симплекс жадвалда бош сатр 2-сатр бўлиб унинг элементлари мос равишда
27, 1, 0, 0, 9/37, -7/37
бўлади. Олдинги жадвалдагидек, Жордан-Гаусс тўла йўқотиш усулидан фойдаланиб, бошқа сатрлар элементларни ҳисоблаб, 3-симплекс жадвални тузамиз:
3-симплекс жадвал.

i	Базис-лар	Базис коэффи-циент-лар Сб	A0	4	6	0	0	0
				A1	A2	A3	A4	A5
1	A3	0	160	0	0	1	-124/37	80/37
2	A1	4	27	1	0	0	9/37	-7/37
3	A2	6	48	0	1	0	-5/37	8/37
m+1			396	0	0	0	6/37	20/37

(m+1) сатрда, 3-итерацияда манфий баҳолар йўқ, демак, олинган режа оптимал бўлиб, оптимал ечим бўлади. . (m+1) - сатр баҳоларидан келиб чиқадики, оптимал ечим ягонадир, чунки 0 баҳолар фақат базис ўзгарувчиларига мос келади.

4. Сунъий базис усули. Юқорида қаралган чизиқли дастурлаш масаласида чеклаш шартларида m тартибли бирлик матрица мавжуд эди, яъни чеклаш шартлари эди, бундай система ҳамиша бирлик матрицага эга бўлади. Чизиқли дастурлаш кўп масалаларида чеклаш шартлари юқоридагидек бўлмай ва бирлик матрица мавжуд бўлмайди. Бундай ҳолларда сунъий базис усулидан фойдаланилади. Сунъий базис усулини қуйидаги мисолда қараймиз [3, 68-бет].

2-мисол. чизиқли функциянинг

шартлар системасини қаноатлантирувчи максимал қийматини топинг.
Ечиш. Маълумки, чеклаш шартлари системасида бирлик матрица мавжуд эмас. Ҳар бир тенгламага биттадан манфий бўлмаган, мос равишда сунъий ўзгарувчиларни киритамиз. Энди берилган масалага нисбатан кенгайтирилган масала деб аталувчи ушбу масалага ўтамиз: чизиқли функциянинг

шартлар системасини қаноатлантирувчи максимал қийматини топинг (бунда М етарлича кичик манфий сон, масала минимумга ечилаётган бўлса етарлича катта мусбат сон деб олинади). Вектор шаклида

кўринишда бўлади. Базис учун бирлик векторларни оламиз. Бу сунъий базисни ташқил этади. Эркин ўзгарувчилар ларни 0 га тенглаб, биринчи таянч ечимни оламиз.
1-симплекс жадвални тузамиз:
Жадвалнинг (m+1) ва (m+2) сатрларини тўлдиришда


1-симплекс жадвал

i	Базис-лар	Базис коэффи-циент-лар Сб	A0	5	3	4	1	-М	-М
				A1	A2	A3	А4	А5	A6
1	A5	-M	3	1	3	2	2	1	0
2	A6	-M	3	2	2	1	1	0	1
m+1			0	-5	-3	-4	1	0	0
m+2			-6	-3	-5	-3	-3	0	0

, ,
,
,
ҳисоблашларни бажариб, баҳолар иккита қўшилувчилардан иборат ҳамда М нинг чизиқли функцияси эканлигини пайқаймиз.
Ҳисоблашларнинг қулайлиги учун (m+1) сатрга чизиқли функциянинг озод ҳадини, (m+2) сатрга эса М нинг коэффицентларини ёзамиз. (m+2) сатрда манфий сонларнинг мавжудлиги таянч ечимнинг оптимал эмаслигини билдиради ва уни яхшилаш мумкин бўлади. Жадвалнинг асосий қисми (m+2) сатрда манфий сонларнинг мавжудлиги таянч ечимнинг оптимал эмаслигини билдиради ва уни яхшилаш мумкин бўлади. Жадвалнинг асосий қисми (m+2) сатрида энг кичик сон (-5) А₂ вектор баҳоси бўлганлиги учун йўналтирувчи (калит) устун (А₂) устуни бўлади. , бўлганлиги учун А₅ вектор сатри йўналтирувчи (калит) сатр, 3 очувчи (калит) элемент бўлади. Демак, А₅ ни базисдан чиқариб ўрнига А₂ векторни базисга киритамиз. 2-симплекс жадвални тузамиз.
2-симплекс жадвал.

I	Базислар	Базис коэффи-циент-лар Сб	A0	5	3	4	1	-М	-М
				A1	A2	A3	А4	А5	A6
1	A2	3	1	1/3	1	2/3	2/3	1/3	0
2	A6	-M	1	1/3	0	-1/3	-1/3	-2/3	1
m+1			3	-4	0	-2	3	1	0
m+2			-1	-4/3	0	1/3	1/3	5/3	0

2-симплекс жадвалнинг (m+2) сатри асосий қисмида (-4/3) манфий сон бўлганлиги учун А₁ вектор устуни йўналтирувчи (калит) устун, А₆ вектор сатри йўналтирувчи (калит) сатр, 4/3 очувчи (калит) элемент бўлади. Базисдан А₆ сунъий векторни чиқариб, А₁ векторни базисга киритиб, 2-симплекс жадвалдагидек, 3-симплекс жадвални ҳосил қиламиз:

3-симплекс жадвал.

i	Базислар	Базис коэффи-циент-лар Сб	A0	5	3	4	1	-М	-М
				A1	A2	A3	А4	А5	A6
1	A2	3	3/4	0	1	3/4	3/4	1/2	-1/4
2	A1	5	3/4	1	0	-1/4	-1/4	-1/2	3/4
M+1			6	0	0	-3	2	-1	3
M+2			0	0	0	0	0	1	1

3-жадвалда (m+2) cатрда сунъий базис баҳоларидан ташқари ҳамма баҳолар 0 га тенг бўлади:

М соннинг танланишига асосан А₅ ва A₆ векторлар энди базисга тушмайди, шунинг учун уни бундан кейин қарамасак ҳам бўлади, лекин, тескари матрицани олиш учун уни сақлаш мумкин.
таянч ечим берилган масаланинг ҳам ечими бўлади, лекин у оптимал эмас, чунки (m+1) сатрда манфий баҳо мавжуд. Энди ечимни яхшилаш (m+1) сатр бўйича олиб борилади. бўлганлиги учун А₃ вектор устуни йўналтирувчи (калит) устун, А₂ вектор сатри йўналтирувчи (калит) сатр, 3/4 очувчи (калит) элемент бўлиб, m+2 cатр энди ҳисобга олинмайди. Юқорида кўрсатилган усул билан 4-симплекс жадвални тузамиз:
4-симплекс жадвал.

i	Базислар	Базис коэффи-циент-лар Сб	A0	5	3	4	1	-М	-М
				A1	A2	A3	А4	А5	A6
1	A3	4	1	0	4/3	1	1	2/3	-1/3
2	A1	5	1	1	1/3	0	0	-1/3	2/3
M+1			9	0	4	0	5	1+М	2+М

4-симплекс жадвалдан қўйилган масаланинг оптимал ечими бўлиб, бўлади. Биринчи ва иккинчи сатрларни ўзаро алмаштириб, А₅ ва А₆ векторлар устунида тескари матрицани ҳосил қиламиз.

Қаралган мисолдан кўринадики, чеклаш шартларида бирлик матрица мавжуд бўлса, m та жадвал, сунъий базис киритилган бўлса, тахминан 2m та жадвал тузилади.

5. Аралаш шартли масалалар.

Чизиқли дастурлаш масаласи қуйидагича қўйилган бўлсин:

чизиқли функциянинг

чеклаш шартлари системасини қаноатлантирувчи минимал қийматини топинг.
Бу чеклаш шартлари k та тенгсизликлар ва m-k та тенгламалардан иборат бўлиб, m тартибли, бирлик матрицага эга эмас. Бундай чеклаш шартлари мавжуд бўлган чизиқли дастурлаш масаласига чизиқли дастурлашнинг аралаш шартли масаласи дейилади. Бундай масалаларнинг базиси қўшимча ва сунъий базис векторларидан иборат бўлади.
Аралаш шартлар системасида d та тенгламалар бўлсин. Бошланғич таянч ечимни олиш учун d дан кўп бўлмаган сунъий ўзгарувчилар киритиш керак бўлади.
1-мисол. чизиқли функциянинг

чеклаш шартларини қаноатлантирувчи минимал қийматини топинг.

Ечиш. Бу масалада тенгсизликлардан тенгламаларга ўтсак, иккита сунъий ўзгарувчи киритишга тўғри келади. Бундай қилмаслик учун, иккинчи тенгсизликни 2 га бўлиб, кейин уни тенгламага айлантирамиз ва ҳосил бўлган тенгламани учинчи тенгламадан айирамиз, ҳамда 3-тенгламага сунъий ўзгарувчи киритамиз: натижада ушбу чизиқли дастурлаш масаласини ҳосил қиламиз:

чизиқли функциянинг

чеклаш шартлари системасини қаноатлантирувчи минимал қийматини топинг.

Масала, вектор формада

бўлади. векторларни базис учун оламиз, булар аралаш базисдан иборат бўлади. Эркин ўзгарувчи ларни 0 га тенглаштириб, бошланғич таянч ечимга эга бўламиз. Симплекс усул билан 1-жадвални ҳосил қилиб, оптимал ечим эканлигини аниқлаймиз ва бўлади.

1-жадвал.

i

Базислар

Базис коэффи-циент-лар Сб