C} koeffitsiyentlari biror, masalan, [c» - C', C» + C' ] intervalda o’zgarsin.
Tekshirishlarning qulayligi uchun chiziqli funksiya koeffitsiyentlarini
C (A) - C; + ac ;
ifoda bilan almashtiramiz, bu yerda C , c; o’ zgarmaslar, A - biror chegarada
o’zgaruvchi parametr bo’lsin.
Endi chiziqli dasturlash masalasini quyidagicha ifodalash mumkin:
n
Zajx» -bi, 1 - 1,2,.,m (1)
»-i
xj > ° (j -1>2,-,n) (2) chiziqli cheklash shartlarini qanoatlantiruvchi shunday X - (x13 x2,..., xn) vektorni topish kerakki, A ning 8 < A < p intervaldagi har bir qiymati uchun
Z -Z (C; + C)Xj (3)
j-1
chiziqli funksiya minimum qiymatga ega bo’lsin.
Bunday masalaning yechimini A parametrning o’zgarishiga qarab tekshiramiz. A=8 bo’lsin, simpleks usuldan foydalanib ushbu ikki holatga kelamiz: 1) A=8 uchun optimal reja mavjud; 2) A=8 uchun chiziqli funksiya chegaralanmagan.
Bunday hollarni alohida-alohida tekshiramiz:
1-hol. A=8 uchun optimal reja olingan bo’lib, A1, A2,..., An sistemasidan olingan m ta vektorlardan iborat biror bazisga mos kelsin. Optimallik shartiga asosan uning m +1 satri baholari Zi - C < 0 shartni qanoatlantiradi. C - C; + 8C;
bo’lganligi uchun optimallik sharti Zs - C» - a» + 83» < 0, j -1,2,...,n ko’rinishda bo’ladi, bu yerda a», 3j lar biror haqiqiy sonlar. Bundan ma’lum bo’ladiki a» + A/3» <0, j -1,2,...,n tengsizliklar sistemasi birgalikda bo’lib, hamma 3j < 0 lar uchun A > -a» /3», hamma 3j > 0 lar uchun A<-a»/3j yechimlarga ega bo’ladi. Quyidagi belgilashlarni kiritamiz:
A-
да, барча 3» > 0 лар учун,
j
min (-a, 13»)
A-
3» <0 11 1
+ да, барча 3» < 0 лар учун,
bo’lsin, bu holda masalaning A-8 bo’lgandagi optimal yechimi A< A< A tengsizlikni qanoatlantiruvchi hamma X lar uchun optimal yechimi mos keladi. Bu holda [8, p] intervalning chap chetki nuqtasi aniq, ya’ni A < 8 bo’ladi. Endi [8, p] intervalning o’ng chetki nuqtasini aniqlash kerak yoki A > p bo’lganda
masalaning yechimi yo’qligini isbotlash kerak bo’ladi. Demak, Я chekli bo’lsa, p< Я bo’ladi. Я = +^ bo’lsa, yechish jarayoni tugaydi.
8 va p larning qiymati oldindan berilmagan bo’lsa, lekin Я ning o’zgarish intervali sistemasini va ularga mos optimal yechimni topish kerak bo’lsa, aj + ЯР}. < 0, j = 1,2,...,n tengsizliklar sistemasi yechimga ega bo’lgan bazisni
aniqlash kerak va shu sistema yordamida Я va Я larni topish mumkin. Keyin Я > Я va Я < Я bo’lganda tekshirishni yuqoridagi usul bilan davom ettirish kerak bo’ladi.
Bunday masalalarning boshqa hollarini matematik dasturlash o’quv rejasi kengroq kurslarda o’rganiladi.
Endi parametrik dasturlashga misol qaraymiz.
1-misol. Korxona ikki M va N turdagi mahsulot ishlab chiqarish uchun uch xildagi xom ashyodan foydalanadi. Har bir mahsulotni ishlab chiqarish uchun xom ashyo sarfi hamda xom ashyo zahirasi ushbu jadvalda berilgan.
Xom ashyo turlari
|
1 birlik mahsulotlarni ishlab chiqarish uchun xom ashyo sarfi
|
Xom ashyo zahirasi
|
M
|
N
|
I
|
4
|
1
|
16
|
II
|
2
|
2
|
22
|
III
|
6
|
3
|
36
|
Mahsulotlar narxi, M mahsulot uchun 2 dan 12 so’mgacha, N mahsulot uchun 13 dan 3 so’mgacha o’zgarishi mumkin bo’lsin va bu o’zgarish C1 = 2 +t, C2 = 13 -1 tengliklar bilan ifodalansin, bunda 0 < t < 10.
Har bir turdagi mahsulotlar narxlarining mumkin bo’lgan o’zgarishini hisobga olgan holda ularni ishlab chiqarishdan umumiy qiymati maksimum bo’ladigan rejani tuzing [5, 194-bet].
Yechish. x1 bilan ishlab chiqarilishi kerak bo’lgan M mahsulot miqdorini, x2 bilan ishlab chiqarilishi kerak bo’lgan N mahsulotning miqdorini belgilaylik. Bu belgilashdan keyin masalaning matematik modeli quyidagicha ifodalanadi: t (0 < t < 10) parametrining har bir qiymati uchun
4Xj + x2 < 16,
6Xj + 3x2 < 36,
x1 > 0, x2 > 0
(2)
cheklash shartlarini qanoatlantiruvchi х1, х2 o’zgaruvchilarning shunday qiymatini topish kerakki F = (2 +1) x1 + (13 -1) x2 (3)
maqsadli funksiya maksimum qiymatga ega bo’lsin.
va (2) tengsizliklarga mos yechimlar ko’pburchagini yasaymiz (1- chizma).
Keyin t = 0uchun 2x1 +13x2 = 26(26 soni ixtiyoriy olindi) to’g’ri chiziqni va C(2; 13) vektorni yasaymiz. Yasalgan to’g’ri chiziqni C vektor yo’nalishi
1-chizma.
bo’yicha (o’zini-o’ziga) parallel siljitib, uning ОАВДЕ yechimlar ko’pburchagi bilan oxirgi, umumiy nuqtasi A(0;11) da bo’lishini aniqlaymiz. Demak, (1)-(3) masala t = 0 bo’lganda X0(0,11) optimal yechimga ega bo’ladi. Bu yechimning mohiyati M mahsulot 1 birligining narxi 2+0=2 so’m, N mahsulot 1 birligining narxi 13 - 0 = 13 so’m bo’lganda, N mahsulotdan 11 birlik, M mahsulotdan esa ishlab chiqarilmaganda umumiy baho Fmax = 143 bo’lib, u optimal bo’ladi.
Endi t = 2 bo’lsin. (2 + 2)x1 + (13 - 2)x2 = 4x1 + 11x2 = 44 (44 soni ixtiyoriy olindi) to’g’ri chiziqni, С1(4;11) vektorni yasab, to’g’ri chiziqni o’zini-o’ziga parallel siljitib, A(0,11) nuqtada yechimlar ko’pburchagi bilan oxirgi umumiy nuqtaga ega bo’lishini aniqlab, t = 2 bo’lganda ham X0(0,11) yechim optimal yechim ekanligini topamiz. Bundan M mahsulot narxi 2+2=4 so’m va N mahsulot narxi 13-2=11 so’m bo’lganda ham N mahsulotdan 11 birlik, M mahsulot ishlab chiqarilmaganda korxona uchun maqsadga muvofiqligini ifodalaydi hamda mahsulotlarning umumiy bahosi Fmax = 4• 0 +1111 = 121 so’m bo’ladi.
1-chizmadan ko’rinadiki, ishlab chiqarishning bu rejasi t ning istalgan qiymati uchun (2 +1)x1 + (13 -1)x2 = h to’g’ri chiziq 2x1 + 2x2 = 22 to’g’ri chiziqqa
parallel bo’lgunga qadar optimal yechim bo’lib qoladi. Parallellik ,
ya’ni t = 5,5 bo’lganda bajariladi. t ning bu qiymati uchun AV kesmaning istalgan nuqtasi (1)-(3) masalaning optimal rejasi bo’ladi.
Shunday qilib, 0 < t < 5,5 uchun X0(0,11) optimal reja bo’lib qoladi va
maqsadli funksiya maksimum qiymati
Fmax = (2 + t) • 0 + (13 - t)-11 = 143 - 11t bo’ladi.
Endi t ning 5,5 dan katta biror qiymatini olaylik, masalan, t = 6 bo’lsin. t = 6 uchun (1)-(3) masalaning yechimini izlaymiz.
(2 + 6)xx + (13-6)x2 = 56 (56 soni ixtiyoriy olindi) to’g’ri chiziqni va С2(8,7) vektorni yasaymiz. Yasalgan to’g’ri chiziqni С2vektorning yo’nalishi bo’yicha o’zini-o’ziga parallel siljitib, uning yechimlar ko’pburchagi bilan 5(1,10) nuqtada oxirgi umumiy nuqtaga ega bo’lishini aniqlaymiz. Demak, t = 6 bo’lganda (1)-(3) masala optimal yechimga ega bo’ladi. Bu yechimning mohiyati 1 birlik M mahsulotning narxi 2+6=8 so’m, 1 birlik N mahsulotning narxi 13-6=7 so’m bo’lganda, mahsulotlarni ishlab chiqarishning optimal rejasi M mahsulotdan 1 birlik, N mahsulotdan 10 birlik ishlab chiqarish kerak bo’ladi. Bunday rejada mahsulot ishlab chiqarishning umumiy bahosi maksimum
Fmax = 8-1 + 7-10 = 78 so’m bo’ladi.
1-chizmadan ko’rinadiki, har qanday t > 5,5 uchun ishlab chiqarishning X1 (1,10) rejasi (2 + t)x1 + (13 -t)x2 = h to’g’ri chiziq 6x1 + 3x2 = 36 to’g’ri chiziqqa parallel bo’lib qolgunga qadar optimal reja bo’lib qoladi. Parallellik
^, ya’ni t = 8 bo’lganda bajariladi. t ning bu qiymati uchun VD
6 3
kesmaning istalgan nuqtasi (1)-(3) masalaning optimal rejasi bo’ladi. Demak, har qanday 5,5 < t < 8 uchun Xj(1,10) (1)-(3) masalaning optimal rejasi bo’lib, maqsadli funksiyaning maksimal qiymati
Fmax = (2 + t)-1 + (13 — t)-10 = 132 — 9t bo’ladi.
chizmadan foydalanib, yuqoridagidek mulohaza yuritib, har qanday 8 < t < 10 uchun (1)-(3) masalaning optimal yechimi X2(2,8) bo’lishini topish mumkin (buni topishni o’quvchiga havola etamiz). Bu rejada har qanday 8 < t < 10 uchun maqsadli funksiyaning masimal qiymati
Fmax = 108 — 6t
bo’ladi.
Shunday qilib, (1)-(3) masalaning ushbu yechimini hosil qilamiz:
< t < 5,5 bo’lsa, optimal reja X0(0,11) bo’lib, Fmax = 143 — 11t bo’ladi;
5,5 < t < 8 bo’lsa, optimal reja Xj(1,10) bo’lib, Fmax = 132 — 9t bo’ladi;
8 < t < 10 bo’lsa, optimal reja X2(2,8) bo’lib, Fmax = 108 — 6t bo’ladi;
Butun sonli dasturlash masalasining qo’yilishi va uni yechish usuli
Ma’lumki, iqtisodning ko’p masalalarini yechish, butun sonli yechimni topish bilan bog’liq. Bunday masalalarda yechimning butun son bo’lishi talab etiladi. Masalan, korxonalar orasida mahsulot ishlb chiqarish topshiriqlari, buyumlarni bichish, kemalar ishlab chiqarish, samolyotlarni reyslarga taqsimlash va hokazo. Bunday misollarni ko’plab keltirish mumkin. Ayrim masalalarda, uning qo’yilishiga qarab, yechimni butun songacha ixchamlab olish mumkin. Lekin boshqa hollarda ixchamlab olish, optimal yechimdan katta farq qilishi mumkin.
Butun sonli dasturlash masalasi ham chiziqli dasturlash masalasidek qo’yilib, optimal yechim o’zgaruvchilarning qiymati butun musbat son bo’lsin,
n
degan qo’shimcha talab qo’yiladi, ya’ni Z = ^C]x] chiziqli funksiyaning
j=1
Za x =b , i = 1,2,...,m ,
IJ J 5 5 5 5
Do'stlaringiz bilan baham: |
