Chiziqli dasturlash masalalarini yechishda simpleks usul algoritmi va uning tahlili

Yechimi: Chegaraviy sistemani kanonik ko‘rinishda quyidagicha yozib olamiz:





Tenglamada bazis o‘zgaruvchilarni simpleks o‘zgaruvchilardan farqlash uchun belgilashlarni kiritamiz va Simpleks jadval tuzamiz.

SO’ BO’	1
	2	1	1	1
	3	4	2	1
	-1	1	-1	2
	5	-3	2	-2
	0	-5	1	-3

O’zgaruvchilarning manfiy bo‘lmaslik sharti berilganligini hisobga olib, to‘g‘ridan-to‘g‘ri tayanch yechimni topishga kirishamiz. Ozod hadlar ichida -1 manfiy ishorali koeffitsient bor. Shu qatordan ishorasi manfiy bo‘lgan modul bo‘yicha eng katta elementni topamiz. U ustunidagi -1 elementdir. Qoidaga binoan musbat nisbatlar ichidan eng kichigini topamiz:

Demak, unga mos element ustunidagi -1 element. Bu element hal qiluvchi element bo‘ladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.

SO’ BO’	1
	1	2	1	3
	1	6	2	5
	1	-1	-1	-2
	3	-1	2	2
	-1	-4	1	-1

Bu jadvaldan ko‘rinib turibdiki ozod hadlar musbat, shu sabab tayanch yechim mavjud. Endi optimal yechimini topish uchun qatoriga qaraymiz. Bu qatorda ikkita manfiy ishorali koeffitsient bor. Ulardan modul bo‘yicha qiymati katta bo‘lgan koeffitsientni tanlab olamiz, u -4 elementidir. Qoidaga binoan hal qiluvchi elementni aniqlab yangi jadval tuzamiz:

Unga mos element ustunidagi 6 element. Bu element hal qiluvchi element bo‘ladi. Endi Simpleks almashtirish qilib, quyidagi jadvalni tuzamiz.

SO’ BO’	1
	2/3	-1/3	1/3	4/3
	1/6	1/6	1/3	5/6
	7/6	1/6	-2/3	-7/6
	19/6	1/6	7/3	17/6
	-1/3	2/3	7/3	4/3

Ozod hadlar va qatoridagi koeffitsientlar musbat. Demak, optimal yechim topildi, ya’ni va bo‘lganda ning maksimal qiymati 1/3 ga teng bo‘ladi, ya’ni .
2-misol. Berilgan chiziqli programmalash masalasining maqsad funktsiyasiga min qiymat beruvchi yechimni toping.




Chegaraviy shartlarni kanonik ko‘rinishda quyidagicha yozib olamiz:


Simpleks jadval quramiz. Birinchi jadvalda ozod hadlar ichida manfiy element mavjud. Shuning uchun tayanch yechimni topamiz. Bu jadvaldan hal qiluvchi elementni topib, Simpleks almashtirish bajaramiz va ikkinchi jadvalga ega bo‘lamiz. Ikkinchi jadvalda tayanch yechim mavjud. Shu sabab undan optimal yechimni topishga o‘tamiz.

SO’ BO’	1				SO’ BO’	1
	2	1	1			1	1/2	3/2
	-2	-2	1			1	-1/2	-1/2
	0	-1	1			1	-1/2	1/2

Optimal yechimni topish uchun - qator elementlarini manfay holga keltirish kerak. Buning uchun jadvaldan hal qiluvchi elementni topamiz. Hal qiluvchi element 3/2. Simpleks almashtirish qilib quyidagi jadvalga ega bo‘lamiz.

SO’ BO’	1
	2/3	1/3	2/3
	4/3	-5/6	-1/3
	2/3	-7/6	-1/3

Jadvaldan ko‘rinib turibdiki maqsad funktsiyasiga minimal qiymat beruchi nuqta mavjud, ya’ni: .