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

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

Мулохазаларимиз содда бўлиши учун уч ўлчовли чизиқли программалаш масалалари мисолида тахлил қиламиз.

(1)

Сунъий базис киритиш ёрдамида масала шартиларни тенглик кўринишига келтирамиз.
(1) ни сунъий базис киртирилган холини тахлил қиламиз.
(2)

(2) масала ечими (1) масала учун ҳам ечим бўлиши кўриниб турибди.
Бунда лар қандай бўлишидан қатъий назар, улар мақсад функциясига хеч қандай таъсир ўтказмайди.
Симплекс усулнинг моҳияти-базисни шундай танлаш керакки, бунда базис ўзгарувчилар қийматларини берсин. (2) масалада базис ўзгарувчилар бўлиб, бу базисда ўзгарувчилар қийматлари , бўлади.
Бу қийматлар (2) масала шартларини тўла қаноатлантиради, лекин мақсад функцияси эса бунда L=0 бўлади. Бу эса (1) масала ечими сифатида қабул қилиниши мумкин эмас. Симплекс усул (2) масала базисини қадамба қадам ўзгартириб айнан оптимал базис ва оптимал ечимга бориш алгоритмидан иборат.
Албатта бу йўлни бир йўла, мураккаб бўлсада, тескари матрица ёрдамида амалга ошириш мумкин. Мантиқан ўйлаганда базис сифатида асосий (1) масала ўзгарувчиларини олган маъқуллиги кўриниб турибди. Аксарият холларда шундай бўлади ҳам. Буни берилган мисол намунасида текшириб кўрамиз.

1. 
   Масала нормативлар матрицаси
   

Учун тескари матрицани топамиз

2. 
   Масалани матрица кўринишида ифодалаб икки тарафдан га кўпайтириб юборамиз. Бу холда
   

(3)
кўринишни олади. (3) Масала ҳам (1), (2) масалага эквивалент бўлиб унинг ечимлари
бўлади.
Бунда мақсад функцияси максимал қиймати L_max=15*10+20*13+24*15=770 эканлигини кўрамиз.
Айнан шу масалани Симплекс усулида ечиш жараёнини кўриб чиқайлик. Биринчи Симплекс жадвал (2) масала асосида тузилади:

Базис	Сi	15	20	24	0	0	0	bi
		A1	A2	A3	A4	A5	A6
A4	0	3	7	5	1	0	0	196	39,2
A5	0	6	4	3	0	1	0	157	52,3
A6	0	2	3	8++	0	0	1	179	22,38
		-15	-20	-24	0	0	0	0
				---------

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

Базис	Сi	15	20	24	0	0	0	bi
		A1	A2	A3	A4	A5	A6
A4	0	1,75	5,125++	0	1	0	-0,625	84,1	16,41
A5	0	5,25	2,875	0	0	1	-0,375	89,86	31,25
A3	24	0,25	0,375	1	0	0	0,125	22,38	59,68
		-9	-11	0	0	0	3	537,12
			----------

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

Базис	Сi	15	20	24	0	0	0	bi
		A1	A2	A3	A4	A5	A6
A2	20	0,341	1	0	0,195	0	-0,122	16,41	48,1
A5	0	4,27++	0	0	-0,561	1	-0,024	42,681	9,996
A3	24	0,122	0	1	-0,073	0	0,171	16,226	133
		-5,252	0	0	2,148	0	14,6	717,624
		-------------

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

Базис	Сi	15	20	24	0	0	0	bi
		A1	A2	A3	A4	A5	A6
A2	20	0	1	0	0,24	-0,08	-0,12	13,001
A1	15	1	0	0	-0,132	0,234	-0,006	9,936
A3	24	0	0	1	-0,057	-0,028	0,172	15,006
		0	0	0	1,452	1,238	1,638	770,111

Бу жадвалда барча бўлгани учун унга мос ечим

Оптимал ечим бўлади. Мақсад функцияси қиймати бу холда ўз максимал қиймати L_max=770,111 га эришади.
4- Симплекс жадвалқийматларини (3) масала коэффицентлари билан солиштирсак улар бир хил эканлигини кўрамиз (фарқ ҳисоблашдаги яхлитлаш хатолиги ҳисобига).
Бундан албатта 1- усул маъқул экан деган хулосага бориш керак эмас. Тескари матрица топиш жараёни анча меҳнат талаб қилади. Ундан ташқари танланган базис оптимал бўлмай қолса барчасини башқатдан бажаришга тўғри келади.
Агар масала
(4)
Кўринишда берилган бўлса, мумкин бўлган базислар сони
формула бўйича ҳисобланади. Хаттоки биз кўрган (2) масалада ҳам n=6; m=3 та вариант бор. Симплекс усул эса хар қадамда аввалгисидан самаралироқ базисни танлаш йўлидан боради. Шунинг учун бу усулда барча базисларни кўриб чиқишга зарурат қолмайди.
Симплекс усули афзалликларидан яна бири, бу усулда бир йўла эгизак масала ечимлари ҳам хосил бўлар экан. Берилган (1) масала учун эгизак масала тузамиз:
(5)

Чизиқли программалаш масалаларучун иккиланганлик теоремасига кўра (1) масала ечими мавжуд бўлса эгизак масала (5) нинг ҳам ечими мавжуд бўлади ва L_max = Q_min бўлади. Агар масала симплекс усулида ишланса сўнгги жадвал охирги қаторга сунъий базис усулларида эгизак масала ечимлари келиб чиқар экан. Бизнинг мисолда
эканини кўрамиз.
Бу қийматларда Q ни ҳисоблансин. келиб чиқади, яъни L_max = Q_min орадаги фарқ, яна яхлитлаш хатоликлари ҳисобига пайдо бўлган дейиш мумкин.
Яна бир турдаги чизиқли программалаш масалаларини ечиш жараёнини таҳлил қиламиз. Бунда барча шартлар тенглик кўринишда берилган бўлиб, бошланғич базис танлаш ва масала шартларини ана шу танланган базисга мослаштириш жараёнини ҳам киритишга тўғри келади. Буни қуйидаги масалада намойиш қиламиз.
(2)

Бу масалада n=4; m=3 бўлиб базис ўзгарувчилар сони 3 га тенг бўлади. Базис танлаш вариантлар сони эса га тенг. Базис танлашда тавсиялардан бири нисбатан арзонроқ махсулотга мос ўзгарувчини базисга киритмаслик йўлидан борган маъқул. Бизда С₄= 10 энг арзони, демак х₄ ни базисга киритмаганлик маъқул. Демак базис сифатида ларни олиш мумкин. Масала шартларини шу танланган базисга мослаштириш учун нормативлар матрицасидан ана шу ўзгарувчиларга мос қисмини базис матрица сифатида олиб унга тескари матрицани топамиз.

Унга тескари матрицани топамиз:

Матрица шартлари кенгайтирилган матрицасини ана шу тескари матрицага кўпайтирамиз


Натижада берилган масала қуйидаги эквивалент кўринишга ўтади.

Бу масала учун биринчи Симплекс жадвал қуйидаги кўринишда бўлади.

Базис	Сi	25	22	24	10	bi
		A1	A2	A3	A4
A4	25	1	0	0	0,7452	11
A2	22	0	1	0	0,7452	15
A3	24	0	0	1	0,4038	12
		0	0	0	34,7156	893

Бу жадвалда барча . Шунинг учун бу жадвалга мос ечим оптимал ечим бўлади. Бунда L_max=893 даромад бўлар экан.

Эслатма. Агар 1- Симплекс жадвалда бирорта < 0 бўлиб қолса базисни алмаштиришга тўғри келган бўлар эди. Унда 2- Симплекс жадвал тузишга тўғри келар эди.
Бизда танланган базис омадли бўлиб биринчи қадамнинг ўзиёқ оптимал ечимга эришишдик.
Чизиқли программалаш масалалари бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар.
Учта турдаги уч хил ҳом ашё асосида тайёрланадиган уч ҳил махсулот учун ҳом ашё сарфлари нормативлари матрицасини тузамиз. Бунда имкон даражасидан матрица устун элементлари йиғиндиси бир бирига яқинроқ танлагани маъқул. Сўнгра ишлаб чиқариладиган махсулотларнинг сонларини ихтиёрий танлаймиз. Ҳом ашё захираларини эса ана шу қийматлар ва норматив матрицаси асосида ҳисоблаб аниқлаймиз.Мақсад функциясини эса махсулот сонларига қараб танлаш мумкин. Бунда аксарият холларда оптимал ечим биз белгиланган махсулотлар сонига мос келади. Намуна сифатида қуйидаги мисолни кўрамиз. Нормативлар матрицаси:


Махсулотлар сонини эса деб белгиласак ҳом ашё захиралари эса мос равишда:

Қийматларга тенг бўлади. Маҳсулот нархларини эса мос равишда пул бирлиги қилиб белгилаймиз (нархлар махсулот сонига мутаносиб тарзда олинди).
Шундай қилиб берилган масала математик модели чизиқли программалаш масалаларини ҳосил қиламиз.


Бу масала ечимини юқорида тўла таҳлил қилдик. Келтирилган мулохазалар асосида ишончли, ечимлари аввалдан маълум бўлган топшириқ вариантларини тузиш мумкин.

1-

2-

3-

4-

5-

6-

7-

8-

9-

10-

Қуйидаги чизиқли программалаш масалалар учун бошланғич базисни танланг, масала шартларини танланган базисга мослаштиринг, Симплекс усули асосида оптимал ечимини топинг.

11-

12-

13-

14-

15-

16-

17-
( ).
.
18-

19-

20-

21-

22-

23-

24-

25-

26-

27-

28-

29-

30-

Вариант жавоблари:

1. L_max=717
2. L_max=857
3. L_max=464
4. L_max=1327
5. L_max=1073
6. L_max=841
7. L_max=729
8. L_max=1169
9. L_max=776
10. L_max=741
11. L_max=889
12. L_max=1552
13. L_max=1210
14. L_max=1467
15. L_max=1129
16. L_max=889
17.
20. L_max=741
21. L_max=870
22. L_max=728
23. L_max=737
24. L_max=870
25. L_max=741
26. L_max=728
27. L_max=729
28. L_max=1169
29. L_max=1210
30. L_max=1467