3-amaliy ish Chiziqli dasturlash masalasining yechimini topishda geometrik usul

3-amaliy ish

Chiziqli dasturlash masalasining yechimini topishda geometrik usul.

Geometrik tahlilni (1.1) – (1.2) masala misolida olib boramiz. (1.1) shartlarning har biri OX₁X₂ koordinat tekisligini to'g'ri chiziq bo'ylab ikki bo'lish va ulardan shartga mos keladigan bittasini tanlashni ifodalaydi. Tahlilni soddalashtirish uchun (1.1) shartlarning hammasini mos ravishda 30;45;12ga bo'lib yozamiz.

L( ) = 1000 + 1400 max

MBESni topish uchun hosil bo'lgan shartlardagi to'g'ri chiziqlarni chizamiz va ulardan pastki qismini olamiz. Natijada OABCD beshburchak shaklidagi soha hosil bo'ladi (1 – rasm).

Bu sohaning istalgan nuqtasining koordinatalari (1.1) – (1.2) masalaning shartlariga mos mumkin bo'lgan yechimlaridan birini ifodalaydi. Bu yerda biz maqsad funksiyasining biror qiyamatiga mos keladigan rejalar (yechimlar)ga mos nuqtalar to'plamini ko'rib chiqamiz. Masalan L( ) = 70000 bo'ladigan nuqtalar to'plami 1000 + 1400 = 70000 tenglama bilan ifodalanadi. Bu tenglamaning ikki tarafini 70000ga bo'lib yuboramiz va ko'rinishdagi tenglamani hosil qilamiz. Bu OX₁X₂ koordinat tekisligida M₁(70;0) va M₂(0;50) nuqtalardan o'tuvchi to'g'ri chiziq tenglamasi bo'lib, 1 – rasmda uning grafigi punktir chiziq bilan ifodalangan. L( ) funksiyaning qiymati orttirilsa, masalan L( ) = 140000 deb olinsa unga mos grafik avvalgisiga parallel bo'lib yuqoriroqdan, ya'ni M₃(140;0) va M₄(0;100) nuqtalardan o'tgan to'g'ri chiziq hosil bo'ladi. Bu to'g'ri chiziqlarning MBESga taaluqli har bir nuqtasining koordinatalari (1.1) – (1.2) masalaning yechimlarini ifodalaydi. Masalan, N₁ nuqtada L(N₁) = 70000, N₂ nuqtada esa L(N₂) = 140000 bo'ladi. Maqsad funksiyasining L( ) = const tartibda olingan grafiklari o'zaro parallel to'g'ri chiziqlardan iborat bo'lar ekan. Maqsad funksiyasining qiymati ortgan sari bu to'g'ri chiziq yuqorilab boraveradi. Bora – bora MBESdan chiqib ketishi mumkin. Xususan berilgan misolda maqsad funksiyasining grafigi MBESdan oxiri C nuqtadan o'tgan holida chiqib ketadi. Ana shu holat, ya'ni C nuqta koordinatalari (1.1) – (1.2) masala yechimini, optimal rejani berar ekan deyishga asos bo’ladi. (1.1) shartlarga mos tengsizliklarni juft-jufti bilan tenglik sifatida olib sistema qilib yechib C, B nuqtalar koordinatalarini topish mumkin. Masala shartlari va 1 – rasmdan kelib chiqqan holda A(100;0), B(70;50), C(30;90), D(0;100) ekanligini ko'ramiz. Chizmada ko'rilganidek MBES qabariq sohadan iborat bo'lib, bu holat barcha CHDMlar uchun o'rinli bo'lgan holatdir. Maqsad funksiyasi grafigi ham to'g'ri chiziq bo'lganligi uchun uni oshirish parallel ko'chirishdan iborat bo'ladi va maqsad funksiyasining maksimal qiymati MBES uchlaridan birida ya'ni maqsad funksiyasining grafigi MBESdan chiqib ketish arafasida o'tgan nuqtasida bo'lar ekan. Bu esa optimal reja, ya'ni CHDMlar yechimini topish uchun umumiy qoida tavsiya qilishga imkoniyat beradi.

CHDMlarni yechishda avvalo MBESni ifodalovchi qabariq soha topiladi va uning uchlarida maqsad funksiyasini hisoblanadi. Bu qiymatlardan eng kattasiga mos keluvchi nuqta koordinatalari izlanayotgan yechim – optimal rejani beradi. Bu qoidani yuqorida ko'rilgan masalaga tatbiq qilamiz. Maqsad funksiyasi (MF) = 1000 + 1400 bo'lib MBES uchlari A(100;0)

B(70;50), C(30;90), D(0;100) dagi qiymatlarini deb belgilasak £_A= 100000, £_B=140000, £_C=156000, £_D= 140000.

Bu qiymatlarni taqqoslash natijasida optimal reja C(30;90) nuqtada ekanligiga ishonch hosil qilamiz. Bu natija 1 – rasmdagi chizmaga ham mos keladi, ya'ni MF grafigini parallel ko'chirishda bu grafik MBESdan C nuqta orqali chiqib ketishi ko'rinib turibdi. Bu keltirilgan grafik usul ikki noma'lumli masalalarda juda qulay bo'lish bilan birga ko'plab umumiy qoida va tavsiyalar ham ishlab chiqishga imkoniyat beradi.

Misollar

1.1 1.2

1.3 1.4

1.5 1.6