Chiziqli dasturlash masalasini yechishning geometrik usuli. OX1X2 tekislikning (4.1)-(4.2) shartlarga mos keluvchi sohasini quraylik. (4.1) shartlarning har biri ma’lum yarimtekislikni ajratib oladi, (4.2) shartlar esa koordinat tekisligini birinchi choragini ajratib beradi.
Shunday qilib mumkin bo`lgan yechimlar sohasini hosil qilamiz, ya’ni OABCD qabariq beshburchak hosil bo`ladi (4- rasm). Ushbu rasmda L 28000. dagi maqsad funksiya grafigi ham berilgan. Ravshanki, L ni qiymati o`sib borgan sari maqsad funksiyasi yuqoriga ko`tariladi. Bizga maqsad funksiyasining maksimal qiymati zarur. 3- rasmdan ko`rinib turibtiki, bunday ko`tarilish mumkin bo`lgan yechimlar sohasidan chiqguncha, ya’ni bu to`g`ri chiziqda hech bo`lmasa bitta mumkin bo`lgan yechim mavjud bo`lguncha mumkin. Odatda maqsad funksiyasi va mumkin bo`lgan yechimlar sohalarni oxirigi kesishish nuqtasi mumkin bo`lgan yechimlar sohasining biror uchida bo`ladi. Shuning uchun mumkin bo`lgan yechimlar sohasi ko`pburchagining uchlari optimal yechim qidirish kerak bo`lgan to`plam bo`ladi. Bu ko`pburchak uchlari, aniqrog`i, ularni koordinatalari tayanch yechim (TE) deb ataladi. Demak, yechim algoritmi tayanch yechim topishga keladi. Bizning xolda A, B, C, D nuqtalar koordinatalari oson topiladi:
A(0;100), B(70;50), C(30;90), D(90;0). Ushbu nuqtalarda maqsad funksiya qiymatlarini topamiz: 140000; 140000; 156000; 90000. L L L L A B C D Topilgan qiymatlardan ko`rinib turibiki, optimal reja S nuqtada bo`ladi va 1 2 х х 30; 90. Shunday qilib, birinchi tur sharbatdan 30 bankava ikkinchi tur sharbatdan 90 banka ishlab chiqilganda daromad maksimal bo`ladi. Shu yerda ta’kidlab o`tish kerakki, sarflar normativi,resurslar zahirasi,bozor narhi o`zgarganda faqat (4.1)-(4.3) ifodalardagi mos koeffisiyentlar o`zgaradi, yechim algoritmi esa o`zgarmaydi. Yuqorida keltirilgan masala bizga shu turdagi chiziqli dasturlash masala larning umumiy matematik modelini qurish imkoniyatini beradi:
Agar masala shartlari (4.4)-(4.6) larni iqtisod tiliga o`girsak, quyidagi misolni shakllantirishimiz mumkin. Korxona m turdagi resurslar asosida n turdagi maxsulot ishlab chiqaradi. Resurslar zahirasi mos ravishda b1,b2,…,bm. ga teng. Bir dona j -turdagi maxsulot ishlab chiqishga i– chi resurs sarfi aij birligini tashkil qiladi. j -turdagi bitta maxsulot narxi cj – pul birligini tashkil qiladi. Korxona daromadi maksimal bo`ladigan ishlab chiqarishning optimal rejasini aniqlang. Aytib o`tish joizki, masala to`liq bo`lishi uchun resurslar orasida energetik,transport va mehnat resurslarini ham xisobga olishimiz kerak. m va n-ning qiymatlari o`sib borishi bilan (4.4)-(4.6) masala ham murakkablashib boradi, uni yechish esa ko`p mexnat talab qiladi. Bunday xollarda yechim topishni dasturiy usullariga murojaat qilishga to`g`ri keladi. Shu usullardan biri bilan keyinchalik tanishib o`tamiz. Avval chiziqli dasturlash masalasining yana bir hususiyatiga to`htalib o`tamiz. Ixtiyoriy (4.4)-(4.6) ko`rinishdagi chiziqli dasturlash masalasiga egizak masala qurish mumkin. Uning ko`rinishi quyidagicha: 1 1 , 1,2,..., , (4.7) 0, 1,2,..., , (4.8) min. (4.9) m ij i j i i m i i i a y c j n y i m Q y b y Egizaklik teoremasi deb ataladigan teoremada isbot etilishicha agar (4.4)-(4.6) masalani yechish mumkin bo`lsa, u holda (4.7)-(4.9) egizak masalani ham yechish mumkin bo`lib, optimal qiymatlari esa teng bo`ladi: max min L Q . Yechimga ega bo`lish xamda yechimni to`g`riligini baholashda shu shartdan foydalaniladi. Ba’zan egizak masala asosiy masaladan soddaroq bo`lishi mumkin. Bunday xolda tekshirishni egizak masaladan boshlash mumkin. Egizak masalani iqtisodiy ma’nosini ishlab chiqarish resurslarini optimal narhi deb qabul qilish mumkin. Yuqorida biz chiziqli dasturlash masalasining mumkin bo`lgan turlarining faqat bittasida to`xtaldik. Amaliyotda chiziqli dasturlash masalasini turli shaklda uchratish mumkin, u xolda chiziqli dasturlash masalasini qulay ko`rinishga keltirish mumkin. Bunday xollrni keyingi ma’ruzalarda ko`ramiz
|
