1-misol. Maqsad funktsiyasi va cheklanish shartlari quyidagicha bo‘lgan ch. D. M. ning yechimini toping. Yechimi

1-misol. Maqsad funktsiyasi va cheklanish shartlari quyidagicha bo‘lgan CH.D.M.ning yechimini toping.











Yechimi: Cheklanish shartlari bazis noma’lumlarga nisbatan yechilmagan bo‘lganligi uchun simpleks usuldan foydalanib bo‘lmaydi. Bu masalani simpleks jadval usuli bilan yechish uchun sun’iy bazis usulidan foydalanamiz. sun’iy noma’lumlar yordamida bu masalaga mos chiziqli dasturlash masalasini quyidagicha yozamiz:

Bu sistema uchun manfiy bo‘lmagan larni va quyidagi yordamchi maqsad funktsiyaga minimum qiymat beruvchi larni topamiz. Boshlang‘ich jadvalda bazis noma’lumlar uchun larni olib, quyidagiga ega bo‘lamiz:

Bu masalaga mos simpleks jadval quyidagicha bo‘ladi:

	1
	3	1	0	-1	4
	3	2	-1	0	0
	1	3	-2	0	-1
	7	6	-3	-1	3
	0	-1	-1	-2	0

Simpleks jadvalning biridan ikkinchisiga ketma-ket o‘tib, quyidagi jadvallarni tuzamiz

	1
	8/3	-1/3	2/3	-1	13/3
	7/3	-2/3	1/3	0	2/3
	1/3	1/3	-2/3	0	-1/3
	5	-2	1	-1	5
	1/3	1/3	-5/3	-2	-1/3

	1
	4	-1/2	3/2	-3/2	13/2
	1	-1/2	-1/2	1/2	-3/2
	3	0	1	-1	4
	1	-3/2	-3/2	1/2	-3/2
	7	-1/2	-5/2	-9/2	21/2

	1
	7	-2	0	3	2
	2	-1	-1	2	-3
	5	-1	0	2	1
	0	-1	-1	-1	0
	16	-4	-2	9	-3

Oxirgi jadvalda dan boshlanuvchi satrda musbat element mavjud emas. Demak, topilgan yechim optimal yechim bo‘ladi, chunki bu yechimda . Demak, da bo‘lib,

2-misol. Quyida berilgan CH.D.M. uchun simpleks usulni qo‘llab, optimal yechimni toping:





Yechimi: Berilgan masalaning yechimini olish quyidagi qadamlarda bajariladi:

1-qadam. Maqsad funktsiyasini maksimallashtirish va larning musbat ekanligini tekshirish.

Masalaning berilishidan ko‘rinib turibdiki, maqsad funktsiyasi maksimallashtirishga oid va barcha lar musbat, shuning uchun ham ushbu qadam bajarilgan deb hisoblaymiz.

2-qadam. Masalani standart shaklda ifodalash.

Masalani standart shaklga keltirish uchun yordamchi o‘zgaruvchilarni kiritib olamiz, ya’ni:

3-qadam. Boshlang‘ich tayanch yechimni topish.

Beshta noma’lum qatnashgan uchta tenglamalar sistemasi mavjud va shuning uchun biz yechimni olish uchun ixtiyoriy ikkita o‘zgaruvchi noma’lumga 0 qiymatni beramiz. qiymat uchun aniqlanadigan tayanch yechimdan boshlaymiz. (Bu asosiy yechim grafik usuldagi yechimga mos keladi). Ya’ni (1), (2) va (3) tenglamalarga qiymatlarni qo‘yib, quyidagi asosiy yechimlarga ega bo‘lamiz:

Barcha lar musbat bo‘lganligi sababli, mumkin bo‘lgan yechimlar hisoblanadi.

Asosiy mumkin bo‘lgan yechim (asosiy bo‘lmagan) va (asosiy).

Boshlang‘ich asosiy mumkin bo‘lgan yechim quyidagi jadvalda keltirilgan:

		5	3	0	0	0
	Bazis
0		(1)	1	1	0	0	2	2/1
0		5	2	0	1	0	10	10/5
0		3	8	0	0	1	12	12/3
		0	0	0	0	0	0
		5	3	0	0	0

-ustun uchun ( ),

va -ustun uchun ( ),

Xuddi shunday .

4-qadam. Optimallik shartini qo‘llash.

Ba’zi ustunlar uchun musbat bo‘lganligidan boshlang‘ich mumkin bo‘lgan tanyach yechim optimal yechim bo‘lmaydi va shuning uchun keyingi qadamga o‘tamiz.

5-qadam. 1) Kiruvchi va chiquvchi o‘zgaruvchilarni aniqlash.

Yuqorida berilgan jadval ning kiruvchi o‘zgaruvchi ekanligini ko‘rsatadi, chunki, uning o‘sib boruvchi qiymatida maksimal qiymatga erishadi, ushbu qiymat joylashgan ustun hal qiluvchi ustun (key-column) hisoblanadi (jadvalning pastki qismida strelka bilan ko‘rsatilgan).

ustun ostidagi elementlarni hal qiluvchi ustun (key-column)ning mos elementiga bo‘lib minimal musbat munosabatni aniqlaymiz, bu 2 ga teng. Shuning uchun ham hal qiluvchi satr sifatida qatorni (satrning o‘ng tomonidan strelka bilan ko‘rsatilgan) tanlab olamiz. Hal qiluvchi satr va ustun kesishmasidagi element, ya’ni (1) - ning hal qiluvchi elementi hisoblanadi, shuning uchun ham chiquvchi tayanch o‘zgaruvchi endi asosiy bo‘lmaydi.

ni yechimga kiritib, cheklov shartlarini qanoatlantiruvchi uning qanday maksimal qiymatlari bo‘lishi mumkinligini ko‘rsatishga harakat qildik. Shunday qilib, yechimdan ni chiqarib tashlab, yangi asosiy bazis yechim sifatida va larni olamiz.

2) Optmal yechim iteratsiyasi.

Mumkin bo‘lgan asosiy (tayanch) yechimga ega bo‘lgan berilgan tenglamalar sistemasini boshqa mumkin bo‘lgan tayanch yechimga ega ekvivialent tenglamalar bilan almashtirish uchun hal qiluvchi elementni yagona deb olamiz. Bu yerda yagona hal qiluvchi elementni saqlovchi satrni hal qiluvchi satr sifatida saqlab qolamiz. Keyin, hal qiluvchi ustunning qolgan barcha elementlarini nol deb olib, hal qiluvchi satrdagi to‘g‘ri ko‘paytuvchilardan ushbu satr elementlarini ayiramiz. Bu yerda ikkinchi satrdan hal qiluvchi satr elementlarini besh marta ayiramiz va uchinchi satr elementlaridan hal qiluvchi satrning uchta elementini ayiramiz.

Ular quyidagi jadvalning ikkinchi va uchinchi satrlari bo‘ladi. Shuningdek, ustunning ikkinchi satrga mos qiymati 0 ni 5 bilan, bazis usutnidagi ni bilan almashtiramiz. Xuddi shunday, ikkinchi asosiy mumkin bo‘lgan yechimlardan iborat jadval quyidagicha bo‘ladi:

		5	3	0	0	0
	Bazis
5		1	1	1	0	0	2
0		0	-3	-5	1	0	0
0		0	5	-3	0	1	6
		5	5	5	0	0	10
		0	-2	-5	0	0

Yuqorida keltirilgan jadvalda ning barcha ustunlar bo‘yicha qiymatlari yoki 0 yoki manfiy ekanligidan ushbu jadval optimal tayanch yechimni beradi. Bu optimal yechim va

3. Mustaqil ishlash uchun topshiriqlar

1. Quyidagi masalani standart shaklga keltiring va ekanligini hisobga oling:

2. Quyidagi Ch.D. masalasini standart shaklga keltiring:

3. Quyidagi Ch.D. masalasini standart shaklda ifodalang:

4. Quyidagi chiziqli tenglamalar sistemasining barcha asosiy yechimlarini toping:

5. Quyidagi tenglamalar sistemasi ikkita mumkin bo‘lgan tayanch yechimlarga ega ekanligi ko‘rsating:

6. Quyidagi tenglamalar sistemasining barcha mumkin bo‘lgan yechimlarini toping:

7. Quyidagi masalaning barcha asosiy yechimlarini toping:

Asosiy yechimlardan qaysi biri (a) qaytalanmaydigan tayanch yechim, (b)optmal tayanch yechim bo‘ladi?

8. tenglamalar sistemasi uchun mumkin bo‘lgan yechim lar funktsiya uchun boshlang‘ich yechim bo‘lmasligini ko‘rsating.

Quyidagi CH.D.M. ning yechimini olish uchun simpleks usuldan foydalaning (9-17):

9. Maqsad funktsiyasi shartlar:

10. Maqsad funktsiyasi shartlar:

11. Maqsad funktsiyasi shartlar:

12. Maqsad funktsiyasi shartlar:

13. Maqsad funktsiyasi shartlar:

14. Maqsad funktsiyasi shartlar:

15. Maqsad funktsiyasi shartlar:

16. Maqsad funktsiyasi shartlar:

17. Maqsad funktsiyasi shartlar:

18. Firma ikki xil turdagi A va B mahsulotlarni ishlab chiqaradi va bu mahsulotlarni mos ravishda 2 va 3 dollar foyda bilan sotadi. Har bir mahsulot G va H stanoklarda tayyorlanadi. A mahsulotni tayyorlash G stanok uchun 1 minut va H stanok uchun 2 minut talab qiladi, B mahsulotni tayyorlash uchun esa har bir stanokdan 1 minutdan vaqt talab etiladi. G stanokdan bir kunda 6 soat 40 minutdan ortiq foydalanish mumkin emas, H stanokning ish vaqti esa bir kunda 10 soat bilan chegaralangan. Ushbu masalani simpleks usul yordamida maksimal foyda olish uchun yeching.

19. Kompaniya ikki turdagi mahsulot ishlab chiqaradi. Birinchi turdagi har bir mahsulotni tayyorlash ikkinchi turdagi mahsulotga qaraganda ikki marta ko‘p ish vaqtini talab etadi. Agar barcha mahsulotlar ikkinchi turga tegishli bo‘lsa, kompaniya bir kunda 500 dona mahsulot ishlab chiqarishi mumkin. Bozorda birinchi va ikkinchi turdagi mahsulotlar uchun mos ravishda kunlik savdoni 150 donagacha va 250 donagacha cheklaydi. Mahsulotlarning bir birligidan olinadigan foyda I turdagi mahsulotdan 8 dollar va II turdagi mahsulotdan 5 dollar deb olsak, foydani maksimallashtirish uchun ishlab chiqariladigan har bir turdagi mahsulotlar sonini aniqlang.

20. Sut ishlab chiqarish korxonasi (fermasi)ning ma’muriyati ikki xil turdagi omuxta yemlarning to‘g‘ri aralashmasi olish uchun harakat qilmoqda. Ikki turdagi omuxta yemlar to‘rtta asosiy ingredientlarning turli foizlaridan hosil bo‘ladi. Quyida berilgan ma’lumotlar yordamida omuxta yemlarni tayyorlash uchun minimal xarajatni aniqlang:

Ingredientlar	Bir kg omuxta yemda %		kg dagi minimal talab
	1-yem	2-yem
1	40	20	4
2	10	30	2
3	20	40	3
4	30	10	6
Narxi ($/kg)	5	3

21. Ishlab chiqarish firmasi zarar keltirayotgan mahsulotlarni ishlab chiqarishni to‘xtatdi. Bu sezilarli darajada ishlab chiqarish quvvatini yo‘qotadi. Firma rahbariyati ushbu zararni qoplash uchun 1, 2 va 3 turdagi mahsulotlardan bittasi yoki bir nechtasiga ishlab chiqarish quvvatini yo‘naltirmoqchi. Har bir birlikdagi mahsulotni ishlab chiqarish uchun zarur bo‘ladigan ishlab chiqarish stanoklari quvvati va ishlab chiqarish soatlari soni quyidagi jadvalda keltirilgan:

Stanok turi	Sarflanadigan vaqt (soat/hafta)	Ishlab chiqarish quvvati (soat/dona)
		1-mahsulot	2-mahsulot	3-mahsulot
Kesuvchi	250	8	2	3
Teshuvchi	150	4	3	0
Silliqlovchi	50	2	–	1

1, 2 va 3-turdagi mahsulotlarning har birligidan olinadigan foyda mos ravishda 20, 6, 8 dollarga teng. Firma har bir mahsulotdan nechtadan ishlab chiqarisa maksimal foyda olishini aniqlang.

22. Quyidagi jadvalda uch xil turdagi oziq-ovqat mahsulotidagi vitaminlar miqdori va ularga bo‘lgan kunlik talab hamda bir birligini narxi keltirilgan. Eng arzon narxdagi oziq-ovqat kombinatsiyasini aniqlang.

Vitamin (mg)	1-oziq-ovqat	2-oziq-ovqat	3-oziq-ovqat	Kunlik talab (mg)
	1	1	10	1
	100	10	10	50
	10	100	10	10
Narx/dona (ming so‘m)	10	15	5