Samarqand iqtisodiyot va servis instituti iqtisodiy matematik usullar va modellar

1-misol.



Yechish: yechimlardan tashkil topgan qavariq ko’pburchakni yasash uchun koordinatalar sistemasida





chiziqlarni yasaymiz (1-chizma).

1-chizma.
Berilgan tengsizliklarni qanoatlantiruvchi yechim shtrixlangan  ko’pburchakni tashkil qiladi. Endi koordinatalar boshidan  vektorni yasaymiz va unga perpendikulyar bo;lgan to’g’ri chiziq o’tkazamiz. Bu to’g’ri chiziq

tenglama orqali ifodalanadi. Uni  vektor yo’nalishida o’ziga parallel siljitib boramiz. Natijada chiziqli funksiyaga maksimal qiymat beruvch  nuqtani topamiz bu nuqtani koordinatalari  masalaning optimal yechimi bo’ladi va
 .
bo’ladi.
Simpleks usul.
Simpleks metod yordamida chiziqli programmalashning ko‘pgina masalalarini yechish mumkin. Bu metod yordamida yechish mumkin bo‘lgan masalalarni chekli qadamlar natijasida optimal yechimlarni topish oson. Har bir qadamda shunday mumkin bo‘lgan yechimlarni topish kerakki maqsadli funksiyaning qiymati oldingi qadamdagi qiymatidan katta bo‘lsin. Bu jarayon maqsadli funksiya optimal yechimga ega bo‘lguncha davom ettiriladi.
Simpleks metodni tushuntirish uchun quyidagi ko‘rinishdagi masalani ko‘rib chiqaylik.


Masala:
 (3)

maqsadli funksiyaning quyidagi tengsizliklar sohasida

(4)

manfiy bo‘lmagan shunday yechimlari topilsinki maqsadli funksiya  eng katta (maksimum) qiymatga ega bo‘lsin.

Bu masalani yechish uchun (4) chiziqli tengsizliklar sistemasiga shunday manfiy bo‘lmagan bazisli o‘zgaruvchilarni mos ravishda qo‘shib (4) -chi sistemaga ekvivalent bo‘lgan sistemani hosil qilamiz.

(5)

U vaqtda maqsadli funksiya quyidagi ko‘rinishga ega bo‘ladi.

(6)
Bu masalada  deb olib birinchi mumkin bo‘lgan yechimlar to‘plamini topamiz.

Chiziqli maqsadli funksiyaning yuqoridagi yechimlar to‘plamiga mos bo‘lgan qiymatini topamiz.



Maqsadli funksiyaning qiymatini maksimum (minimum) qiymatga ega yoki ega emasligini tekshiramiz. Agar  maksimum (minimum) ga ega bo‘lmasa, u vaqtda qo‘shimcha o‘zgaruvchilardan bir nechtasini asosiy o‘zgaruvchilar safiga o‘tkazishimiz va yangi o‘zgaruvchilar bilan yuqoridagi kabi ish olib boramiz. Lekin ko‘p adabiyotlarda ko‘rsatilganki bu jarayon uzilishga ega, ya’ni yechimga ega yoki ega emas. Endi simpleks jadvallar tuzishga o‘tamiz. Buning uchun quyidagicha jadval tuzib olib boramiz:
1. Jadvalning eng yuqoridagi  satriga maqsadli funksiyaning koeffitsentlarini joylashtiramiz va bu satrga maqsadli satr deb ataymiz.
2. Jadvalning yuqoridagi 2-chi satriga o‘zgaruvchilar satri deyiladi. Bu satrga  -larni joylashtiramiz.
3.  larning sistemadagi koeffitsentlari asosiy qismni(asosiy matritsa) tashkil qiladi.  o‘zgaruvchilarning sistemadagi koeffitsentlari esa bosh diagonal bo‘yicha yozilib, birlik matritsani tashkil etadi.
4. Jadvalning oxirgi satrini indekslar satri deb ataymiz va bu satr kattaliklarini maqsadli funksiyada qatnashuvchi koeffitsentlarni teskari ishora bilan olib yozamiz. Natijada quyidagi jadval hosil bo‘ladi.
Dastlabki berilganlarning asosiy jadvaliga asoslanib birinchi simpleks jadvalni tuzamiz.

								0				Maksadli satr
												O’zgaruvchilar satri
1	0							1	0		0
2	0							0	1		0
:	:	:	:	:	:	:	:	:	:	:	:	Birlik matritsa
	0							0	0		1
indeks satri	Maq sad ustun	o‘zgaruvchilar ustuni	o‘zgarmaslar ustuni					0	0		0

Dastlabki berilganlarning asosiy jadvalini tahlil qilamiz.
Indekslar satrini tahlil qilganda satr elementlarining musbat va manfiyligiga etibor beramiz. Agar indeks satr elementlarining hammasi musbat bo‘lsa, u vaqtda mumkin bo‘lgan yechimlar to‘plamini o‘zgartirib bo‘lmaydi va yechimlar to‘plami optimal yechim bo‘ladi.
Faraz qilaylikki, indeks satri elementlarining ichida bir necha manfiy va musbat sonlar bor, u vaqtda manfiy sonlar ichidan eng kichigini tanlab olamiz(absolyut qiymati bo‘yicha eng kattasini).
Faraz qilaylikki bu son  ga teng bo‘lsin.  ni (jadvalga qarang) kora to‘rtburchak ichiga olamiz va  joylashgan ustunni kalitli ustun deb ataymiz.
Bu yerda shuni ham aytish kerakki, agar bordiyu indeks satrida bir-biriga teng birorta kichik manfiy sonlar bo‘lsa, u vaqtda chap tomondan boshlab birinchi katakdagi manfiy sonni tanlaymiz.
Kalitli satrni topish uchun, o‘zgarmaslar ustunidagi sonlarni mos ravishda kalitli ustundagi musbat sonlarga (0-dan farqli) bo‘lib ularning ichidan eng kichigini tanlab olamiz. Faraz qilaylikki bu son bo‘lsin, ya’ni

joylashgan satrga kalitli satr deymiz. Kalitli satrni ham qora chiziq bilan chizilgan to‘rtburchak ichiga olamiz. Kalitli ustun bilan kalitli satr kesishgan katakda turgan songa kalitli son deyiladi. Dastlab berilganlar jadvalini oxirgi ustunga tekshirish ustunidagi har bir son o‘zgarmaslar ustunidan boshlab satr kataklardagi sonlar yig‘indisiga ( ) tengdir.
Shuni ham aytish kerakki, tekshirish ustunidagi sonlar kalitli ustunni(satrni) topishda qo‘llanilmaydi.
Natijada birinchi simpleks jadval hosil bo‘ladi.