Ii-bob. Chiziqli programmalashtirish masalasining simpleks algoritmi

2.3-masala. Simpleks jadvalidan foydalanib sun’iy bazis metodi yordamida ushbu masalani yeching.

Yechish. Dastlab standart ko‘rinishidagi masalani kanonik ko‘rinishga keltiramiz.

Yangi kiritilgan o‘zgaruvchi va lar bazis o‘zgaruvchi bo‘lolmaydi.
Sun’iy bazis o‘zgaruvchilarni kiritamiz.

Birinchi simpleks jadvalni tuzamiz. (3.4-jadval)
2.3.1-jadval

BU							OH
	1	2	-1	0	1	0	2
	1	5	0	-1	0	1	3
F	-7	-20	0	0	0	0	0
M	-2	-7	1	1	-1	-1	-5

Oxirgi qator, bu funksiya, ya’ni funksiya. Bu qatorni to‘ldirish uchun va qatorlarni (-1) ga ko‘paytirib ustun bo‘yicha ularni qo‘shamiz. funksiyani maksimumini izlashda optimallik kriteriyasini bajarilishini tekshirish maqsadida oxirgi qatorning manfiy elementlari ichida eng kichigini tanlaymiz, bu ikkinchi ustunda; demak, u hal qiluvchi element 5 bo‘ladi. Sun’iy bazis o‘zgaruvchi ni keyingi jadvalga kiritmaymiz. Yangi 2.5-jadvalni tuzamiz.

2.3.2-jadval

BU						OH
	3/5	0	-1	2/5	1	4/5
	1/5	1	0	-1/5	0	3/5
F	-3	0	0	-4	0	12
M	-3/5	0	-1	-2/5	-1	-4/5

2.3.3-jadval

BU					OH
	1	0	-5/3	2/3	4/3
	0	1	1/3	-1/3	1/3
F	0	0	-5	-2	16
M	0	0	0	0	0

Oxirgi qator shuni ko‘rsatadiki, optimallik kriteriyasi bajariladi, , demak, , F funksiya uchun ham optimallik kriteriyasi bajarildi. .

Agar bo‘lib, F funksiya uchun optimallik kriteriyasi bajarilmasa, M qatorni jadvaldan chiqarib tashlaymiz va masalani yechishni oxiriga yetkazib qo‘yamiz.
2.4-masala.

Yechish. Cheklovlar sistemasining manfiy bo‘lgan ozod hadlarini musbat holga keltirib olamiz.

Birinchi tenglamaga sun’iy bazis o‘zgaruvchi ni keltiramiz.

Simpleks jadvalni tuzamiz.
2.3.4-jadval

BU							OH
	-1	1	-1	0	0	1	1
	-1	1	0	1	0	0	3
	1	0	0	0	1	0	3
F	-1	-2	0	0	0	0	0
M	1	-1	1	0	0	-1	-1

2.3.5-jadval

BU						OH
	-1	1	-1	0	0	1
	0	0	1	1	0	2
	1	0	0	0	1	3
F	-3	0	-2	0	0	2
M	0	0	0	0	0	0

2.3.6-jadval

BU						OH
	-1	1	-1	0	0	1
	0	0	1	1	0	2
	1	0	0	0	1	3
F	-3	0	-2	0	0	2

_{Birinchi ustun aniqlovchi ustun, aniqlovchi element 1. Birinchi ustunda 1 aniqlovchi elementdan boshqa barchasida 0 hosil qilamiz.}
2.3.7-jadval

BU						OH
	0	1	-1	0	1	4
	0	0	1	1	0	2
	1	0	0	0	1	3
F	0	0	-2	0	3	11

2.3.8-jadval

BU						OH
	0	1	0	1	1	6
	0	0	1	1	0	2
	1	0	0	0	1	3
F	0	0	0	2	3	15

Mustaqil yechish uchun misollar
_{Ushbu chiziqli tenglamalar sistemasining nomanfiy bazis yechimlarini toping.}

1. 
   _2.
   

<sub>3. 4.
5. 6.
7. 8.</sub>

9. 
   _10.
   

Chiziqli programmalashtirish masalalarini grafik usulda yeching.
1. 2.
3. 4.
5. 6.
7. 8.

Chiziqli programmalashtirish masalalarini simpleks usulda yeching
9. 10.
11.
12.
13. 14.