13-amaliy mashg’ulot. Ryukzak haqidagi masala
Ishning maqsadi: Talabalarga Ryukzak haqidagi masala haqida ma`lumot berish va ular bilan shlash ko`nikmasini shakllantirish.
Ryuzak haqidagi masalani qo‘yilishi quyidagicha n- xil predmetlar berilgan bo‘lib (ularning soni yetarlicha ko‘p), j-nomerli predmetning bittasining bahosi Cj0 butun bo‘lsin. b(b -butun son) og‘irlikdagi yukni ko‘taruvchi ryukzak ichiga shu predmetlardan shunday joylashtirish kerakki, natijada olingan predmetlarning umumiy bahosi maksimal bo‘lsin. Ya’ni bu yerda masala olinishi kerak bo‘lgan predmetlarning nomerini va sonini aniqlashga keladi. Bu masalaning matematik modeli quyidagicha bo‘ladi.
Maqsad funksiya
(1)
ni maksimal qiymati
, (2)
xj0, j1,...,n (3)
(xj0 (j1,...,n) j- nomerli predmetning soni) shartlar ostida topilsin. Bu qo‘yilgan (1)-(3) masala butun sonli chiziqli programmalash masalasi bo‘lib, uni yechish bilan qo‘yilgan masala hal qilinadi.
Endi yuqoridagi masalani umumlashgan ya’ni (2) ga o‘xshash chegara bir nechta bo‘lgan holni ko‘ramiz va shu bilan birga yechish algoritmini keltiramiz. Bu masalaning matematik modeli quyidagicha bo‘ladi:
max (4)
, i1,...,m, (5)
xj - manfiy bo‘lmagan butun sonlar va Cj0 , bi0 , aij0 lar barcha i1,...,m, j1,...,n larda butun sonlar. Masalani yechish uchun qulaylik tug‘dir maqsadida quyidagi belgilashlarni kiritamiz
,
, i 1,...,m. (6)
xj (j1,...,k) manfiy bo‘lmagan butun sonlar, k1,...,n, yi 1,...,bi , i1,...,m. Endi k1 bo‘lgan holni alohida ko‘raylik
1(y1, ... ,ym)
ai1x1yi ; i1,...,m , x10- butun.
Tushunarliki, agar biror i{1,...,m} uchun ai10 bo‘lsa, u holda shu indeks uchun ixtiyoriy x10 va ai1x1yi tengsizlik o‘rinli bo‘ladi. Shuning uchun bu holda musbat ai1 koeffitsient ishtirok etgan tengsizliklarni etiborga olish yetarlidir. Demak, x1- o‘zgaruvchi
x1
tengsizlikni musbat ai1 larga mos keluvchi i-indekslarda qanoatlantirishi kerak ekan. Agar x1 ni butun qiymat qabul qilishini etiborga olsak, k1 holdagi masalaning yechimi ekanligi kelib chiqadi. Ravshanki, maqsad funksiyaning qiymati quyidagicha aniqlanadi:
1(y1, ... ,ym)
Demak k1 da maqsad funksiya 1(y1, ... ,ym) ning barcha qiymatlarini aniqlash mumkin bo‘lar ekan. Hisoblashni soddalashtirish maqsadida (tabiiy bo‘lgan) quyidagilarni qabul qilamiz: argumentlar y1, ... ,ym larning barcha qiymatlarida 0(y1, ... ,ym)0 va argumentlarning manfiy bo‘lmagan qiymatlarining kamida birortasi nolga teng bo‘lsa, k(y1, ... ,ym)0 deb olamiz. Agar y1,...,ym larning kamida bittasi manfiy qiymat qabul qilgan bo‘lsa, k(y1, ... ,ym) - bo‘lsin.
Endi 1k(y1,... ,ym) ning qiymatlarini topish uchun rekurrent formulani keltirib chiqaraylik. Faraz etaylik k-1(y1,...,ym) funksiya qiymatlari (y1,...,ym) argumentning qabul qilishi mumkin bo‘lgan barcha qiymatlarida aniqlangan bo‘lsin. U holda, ravshanki k(y1,...,ym) qiymatni hosil qilishda k-nomerli predmet kamida bir marta ishtirok etishi yoki umuman ishtirok etmasligi mumkin.
Shunga ko‘ra, ikkinchi holda k(y1,...,ym) k-1(y1, ...,ym) tenglik o‘rinli bo‘ladi. Birinchi holni ko‘raylik, bunda k-nomerli predmetning kamida bittasi ishtirok etganligi uchun uni bir donasini alohida olib qaraymiz. Uning bittasini alohida ajratib olsak, u ishtirok etgan (6) tengsizliklarning o‘ng chegaralari y1,...,ym lar mos ravishda aik ga kamayadi, ya’ni tengsizlik chegaralari mos ravishda yi-aik bo‘lib qoladi. Shunda maqsad funksiyaning maksimal qiymati belgilanishga asosan k(y1-a1k,...,ym-amk) ga teng. Endi bu qiymatga olib qo‘yilgan bitta k-nomerli predmet bahosi Sk ni qo‘shsak k(y1 - a1k,...,ym-amk) Sk bahoga ega bo‘lamiz. Bu yerda e’tibor berish kerakki k indeks saqlanib qolyapti, chunki k-nomerli predmet bittadan ortiq qatnashgan bo‘lishi mumkin. Shunday qilib k-predmet agar kamida bitta olingan bo‘lsa, maqsad funksiyaning maksimal qiymati k(y1-a1k,...,ym-amk) Sk , umuman olinmagan bo‘lsa k-1(y1,...,ym), ga teng bo‘ladi. Bu ikki variantni qaysi biri afzal ekanligini bilish uchun k-1(y1,...,ym) bilan k(y1-a1k,...,ym-amk) Sk larni taqqoslab ko‘rish kerak bo‘ladi. Agar
k-1(y1,...,ym)< k(y1-a1k,...,ym-amk) Sk
tengsizlik o‘rinli bo‘lsa, k-predmetdan kamida bitta olish maqsadga muvofiq bo‘ladi.
Demak, bir-birini inkor etuvchi bu ikki variantga mos keluvchi maqsad funksiyaning eng katta qiymati k (y1,...,ym) ni beradi, ya’ni
k(y1,...,ym)max(k-1(y1,...,ym),k(y1-a1k,...,ym-amk)Sk) (7)
Aniqki, (7) formula yordamida maqsad funksiya k(y1,...,ym) , k1,...,n ; yi0,1,...,bi, i1,...,m ni faqat qiymatlarini hisoblashimiz mumkin. Qaysi predmetdan nechtadan olinishi kerakligini ko‘rsatuvchi I(k;y1,...,ym), (k1,...,n, yi0,1,...,bi i1,...,n) butun argumentli va qiymatli funksiyani tuzamiz. Agar (k;y1,...,ym) argumentning biror qiymatida φkˉֿ( 1,..., m)j , 1 j bo‘lsa, bu ( 1,..., m) bahoga erishishda j-nomerli predmet kamida bir marta qatnashganligini bildiradi, ya’ni xj1 I(k:y1,...,ym) funksiya qiymatlarini k1 bo‘lganda hisoblash hech qanday qiyinchilik tug‘dirmaydi, haqiqatan, agar 1-nomerli predmetdan olinmagan bo‘lsa , baho 1(y1,...,ym)0 , aks holda
1(y1,...,ym)0 bo‘ladi , shunga asosan
(8)
bu yerda yi 0, 1,...,bi , i1,...,m.
Endi 11,...,ym) funksiya qiymatlarini aniqlovchi formulani keltiramiz. k(y1,...,ym) funksiyani qiymatlarini topish usuli (7) formulaga asosan, agar (y1,...,ym) argumentning biror
( 1,..., m) qiymatida k(y1-a1k,...,ym-amk) Sk< k-1( 1,..., m) tengsizlik o‘rinli bo‘lsa (bu degani k( 1,..., m) k-1( 1,..., m)), ya’ni k( 1,..., m) bahoga erishish uchun k-nomerli predmet qatnashma ganligi ma’lum bo‘ladi, shuning uchun I(k; 1,..., m) I(k-1; 1,..., m) deb olinadi. Agar k( 1-ak,..., m-ak)Sk k-1(y1,..., m) tengsizlik bajarilsa bunda k( 1,..., m) bahoga erishish uchun k-nomerli predmet kamida bir marta qatnashganligini bildiradi, demak I(k; 1,..., m)k` deb olinishi kerak. Shunday qilib I(k;y1,...,ym), 1
I(k: y1,...,ym) (9)
Bu yerda yi0,1,...,bi , i1,...,m .
Natijada (8) va (9) formulalar yordamida I(k:y1,...,ym), k1,n; yi0,1,...,bi, i1,m funksiyani barcha qiymatlari aniqlanadi. Yuqorida aytilganlardan ko‘rinib turibdiki k(y1,...,ym) va I(k;y1,...,ym) funksiyalarning qiymatlari bir paytda (parallel) hisoblab borilishi maqsadga muvofiqdir. Agar k fiksirlanganda k(y1,...,ym) va I(k;y1,...,ym) yi0,1,...,bi , i1,...,m funksiyalar qiymatlarini mos ravishda birinchi va ikkinchi jadvallarning k-qatlamlari deb atasak, u holda tushunarlikki ikkala jadval qatlamlarini hisoblash ketma-ket kichigidan kattasiga qarab olib borilar ekan. Bu yerda jadval so‘zini ishlatilishiga sabab har bir k(y1,...,ym) va I(k;y1,...,ym) k1,...,n, yi0,1,...,bi , i1,...,m funksiyalarning qiymatlarini n∙(b11)∙...∙(bm1) o‘lchamli ikkita jadval ko‘rinishida ifodalash mumkin. Bularni birinchisini baholar jadvali, ikkinchisini predmet sonlarini aniqlash jadvali deb ataladi. Yana shuni ta’kidlash kerakki, jadvallarni biror k-qatlamini hosil qilishda faqat k-1-qatlam elementlari ishtirok etadi ((7)- (9)), bu esa hisoblash mashinasining xotirasini tejash manosida muhimdir. Faraz etaylik , jadvallarning oxirgi n-qatlami , ya’ni n(y1,...,ym) va I(n:y1,...,ym) funksiyalarning qiymatlari (y1,...,ym) argumentni barcha mumkin bo‘lgan qiymatlarida aniqlangan bo‘lsin. U holda qo‘yilgan masalani yechimi quyidagicha topiladi: Predmetlarni sonini aniqlash jadvalidan I(n:b1,...,bm) songa qaraladi. Faraz etaylik y j1 ga teng bo‘lsin, bu j1- nomerli predmet kamida bir marta olinishligini bildiradi. Shuning uchun xj11 deymiz. Keyin I(n;b1-a1j,...,bm-amj1) I(n; 1,..., m) ning qiymatiga qaraymiz , agar y j2 ga teng bo‘lsa, xuddi avvalgidek, bu j2- nomerli predmet kamida bir marta olinish kerakligini bildiradi. Demak, xj21 agar j2j1 bo‘lsa, u holda j1-nomerli predmet kamida ikki marta ishtirok etganligini bildiradi. Shuning uchun xj22 deb olinadi. Bunda, birinchi holda ya’ni I(n; 1,..., m)j2 bo‘lganda, I(n; 1-a1j2,..., m-amj2)ning qiymatiga qaraladi. Ikkinchi holda, ya’ni I(n; 1,..., m)j, da I(n; 1-a1j1,..., m -amj) dan so‘ng 1,..., n sonlari aniqlanib, ular har bir predmetdan nechtadan olinishi kerakligini bildiradi va bundan maqsad funksiya qiymati maksimal bo‘lib, birinchi jadvaldan n(b1,...,bm) bilan aniqlanadi. Bunda shu etiborga loyiqki, agar jadvallarning barcha qiymatlari saqlanib qolgan bo‘lsa, n dan kichik predmet turlari va b1,...,bm chegaralarni mos ravishda katta bo‘lmagan butun sonlarga almashtirishdan hosil bo‘lgan masalalarni ham huddi yuqoridagi usul yordamida (jadvallarning mos qatlamidan) yechimlarini topish mumkin. Yuqoridagi algoritm yordamida quyidagi sonli misolni yechib ko‘raylik. n3, m2, c12, c23, c31, a112, a121, a131, a211, a222, a230, b13, b24 bo‘lsin.
Ya’ni quyidagi ko‘rinishdagi masalaga ega bo‘lamiz:
2x13x2x3max
2x1x2x33
x12x24
x1,x20 - butun.
k1 da (7) - formula yordamida 1(y1,y2) va (8) - formula yordamida I(1:y1,y2) funksiyalarning qiymatlarini aniqlaymiz.
1(1,2)2 min{ ,2}0, I(1;1,2)0
1(1,3)2 min{ ,3}0, I(1;1,3)0
1(1,4)2 min{ ,4}0, I(1;1,4)0
1(2,1)2 min{1,1}2, I(1;2,1)1
1(2,2)2 min{1,2}2 , I(1;2,2)1
1(2,3)2 min{1,3}2 , I(1;2,3)1
1(2,4)2 min{1,4}2 , I(1;2,4)1
1(3,1)2 min{ ,1}2, I(1;3,1)1
-- -- -- -- -- --
1(3,4)2 min{ ,4}2 , I(1;3,4)1.
k2 da (7) va (9) formulalar yordamida mos ravishda 2(y1,y2) va I(2:y1,y2) larni aniqlaymiz.
2(1,1)max(1(1,1), 2(1-1,1-2)3)0 , I(2;1,1)0
2(1,2)max(1(1,2), 2(1-1,2-2)3)3, I(2;1,1)2
2(1,3)max(1(1,3), 2(1-1,3-2)3)3, I(2;1,3)2
2(1,4)max(1(1,4), 2(1-1,4-2)3)3, I(2;1,4)2
2(2,1)max(1(2,1), 2(2-1,1-2)3)2, I(2;2,1)1
2(2,2)max(1(2,2), 2(2-1,2-2)3)3, I(2;2,2)2
2(2,3)max(1(2,3), 2(2-1,3-2)3)3, I(2;2,3)2
2(2,4)max(1(2,4), 2(2-1,4-2)3)6, I(2;2,4)2
2(3,1)max(1(3,1), 2(3-1,1-2)3)2, I(2;3,1)1
2(3,2)max(1(3,2), 2(3-1,2-2)3)3, I(2;3,2)2
2(3,3)max(1(3,3), 2(3-1,3-2)3)5, I(2;3,3)2
2(3,4)max(1(3,4), 2(3-1,4-2)3)6, I(2;3,4)2
Endi k3 qatlam elementlarining qiymatlarini ya’ni k(y1,y2), I(k:y1,y2) topamiz.
3(1,1)max(2(1,1), 3(1-1,1)1)1, I(3;1,1)3
3(1,2)max(2(1,2), 3(1-1,2)1)3, I(3;1,2)2
3(1,3)max(2(1,3), 3(1-1,3)1)3, I(3;1,3)2
3(1,4)max(2(1,4), 3(1-1,4)1)3, I(3;1,4)2
3(2,1)max(2(2,1), 3(2-1,1)1)2, I(3;2,1)3
3(2,2)max(2(2,2), 3(2-1,2)1)3, I(3;2,2)2
3(2,3)max(2(2,3), 3(2-1,3)1)3, I(3;2,3)2
3(2,4)max(2(2,4), 3(2-1,4)1)6, I(3;2,4)2
3(3,1)max(2(3,1), 3(3-1,1)1)3, I(3;3,1)3
3(3,2)max(2(3,2), 3(3-1,2)1)3, I(3;3,2)3
3(3,3)max(2(3,3), 3(3-1,3)1)5, I(3;3,3)2
3(3,4)max(2(3,4), 3(3-1,4)1)7, I(3;3,4)3
Predmetlar sonini aniqlovchi jadvalning oxirgi k3 qatlami I(3;3,4)3 bo‘lganligi uchun 31 deb olamiz va I(3;3,-1,4-0)2 bo‘lgani uchun 21 bo‘ladi. Xuddi shunday I(3;2-1,4-2)2, demak 22; I(3;1-1,2-2) I(3;0,0)- element jadvalda yo‘qligi uchun predmetlarni sonini topish jarayonini to‘xtatamiz. Shunday qilib, 10, 22 , 31 yechimga ega bo‘lamiz. Endi baholar jadvalini oxirgi k3 qatlamidan maqsad funksiyani maksimal qiymati 3(3,4)7 ekanligini aniqlaymiz. Demak, qo‘yilgan masalaning yechimi quyidagicha bo‘lar ekan: birinchi predmetdan olinmaydi, ikkinchi predmetdan ikkita, uchinchi predmetdan bitta, shu holda maqsad funksiya qiymati maksimal yetti qiymatga ega bo‘ladi.
Dostları ilə paylaş: |