13-amaliy mashg’ulot. Ryukzak haqidagi masala Ishning maqsadi

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 C_j0 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)
x_j0, j1,...,n (3)
(x_j0 (j1,...,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)
, i1,...,m, (5)
x_j - manfiy bo‘lmagan butun sonlar va C_j0 , b_i0 , a_ij0 lar barcha i1,...,m, j1,...,n larda butun sonlar. Masalani yechish uchun qulaylik tug‘dir maqsadida quyidagi belgilashlarni kiritamiz
,
, i 1,...,m. (6)
x_j (j1,...,k) manfiy bo‘lmagan butun sonlar, k1,...,n, y_i 1,...,b_i , i1,...,m. Endi k1 bo‘lgan holni alohida ko‘raylik
₁(y₁, ... ,y_m)
a_i1x₁y_i ; i1,...,m , x₁0- butun.
Tushunarliki, agar biror i{1,...,m} uchun a_i10 bo‘lsa, u holda shu indeks uchun ixtiyoriy x₁0 va a_i1x₁y_i tengsizlik o‘rinli bo‘ladi. Shuning uchun bu holda musbat a_i1 koeffitsient ishtirok etgan tengsizliklarni etiborga olish yetarlidir. Demak, x₁- o‘zgaruvchi
x₁
tengsizlikni musbat a_i1 larga mos keluvchi i-indekslarda qanoatlantirishi kerak ekan. Agar x₁ ni butun qiymat qabul qilishini etiborga olsak, k1 holdagi masalaning yechimi ekanligi kelib chiqadi. Ravshanki, maqsad funksiyaning qiymati quyidagicha aniqlanadi:
₁(y₁, ... ,y_m)
Demak k1 da maqsad funksiya ₁(y₁, ... ,y_m) ning barcha qiymatlarini aniqlash mumkin bo‘lar ekan. Hisoblashni soddalashtirish maqsadida (tabiiy bo‘lgan) quyidagilarni qabul qilamiz: argumentlar y₁, ... ,y_m larning barcha qiymatlarida ₀(y₁, ... ,y_m)0 va argumentlarning manfiy bo‘lmagan qiymatlarining kamida birortasi nolga teng bo‘lsa, _k(y₁, ... ,y_m)0 deb olamiz. Agar y₁,...,y_m larning kamida bittasi manfiy qiymat qabul qilgan bo‘lsa, _k(y₁, ... ,y_m) - bo‘lsin.
Endi 1k(y₁,... ,y_m) ning qiymatlarini topish uchun rekurrent formulani keltirib chiqaraylik. Faraz etaylik _k-1(y₁,...,y_m) funksiya qiymatlari (y₁,...,y_m) argumentning qabul qilishi mumkin bo‘lgan barcha qiymatlarida aniqlangan bo‘lsin. U holda, ravshanki _k(y₁,...,y_m) qiymatni hosil qilishda k-nomerli predmet kamida bir marta ishtirok etishi yoki umuman ishtirok etmasligi mumkin.
Shunga ko‘ra, ikkinchi holda _k(y₁,...,y_m) _k-1(y₁, ...,y_m) 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 y₁,...,y_m lar mos ravishda a_ik ga kamayadi, ya’ni tengsizlik chegaralari mos ravishda y_i-a_ik bo‘lib qoladi. Shunda maqsad funksiyaning maksimal qiymati belgilanishga asosan _k(y₁-a_1k,...,y_m-a_mk) ga teng. Endi bu qiymatga olib qo‘yilgan bitta k-nomerli predmet bahosi S_k ni qo‘shsak _k(y₁ - a_1k,...,y_m-a_mk) S_k 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(y₁-a_1k,...,y_m-a_mk)  S_k , umuman olinmagan bo‘lsa _k-1(y₁,...,y_m), ga teng bo‘ladi. Bu ikki variantni qaysi biri afzal ekanligini bilish uchun _k-1(y₁,...,y_m) bilan _k(y₁-a_1k,...,y_m-a_mk)  S_k larni taqqoslab ko‘rish kerak bo‘ladi. Agar

_k-1(y₁,...,y_m)< _k(y₁-a_1k,...,y_m-a_mk)  S_k

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 (y₁,...,y_m) ni beradi, ya’ni

_k(y₁,...,y_m)max(_k-1(y₁,...,y_m),_k(y₁-a_1k,...,y_m-a_mk)S_k) (7)

Aniqki, (7) formula yordamida maqsad funksiya _k(y₁,...,y_m) , k_­­1,...,n ; y_i0,1,...,b_i, i1,...,m ni faqat qiymatlarini hisoblashimiz mumkin. Qaysi predmetdan nechtadan olinishi kerakligini ko‘rsatuvchi I(k;y₁,...,y_m), (k1,...,n, y_i0,1,...,b_i i1,...,n) butun argumentli va qiymatli funksiyani tuzamiz. Agar (k;y₁,...,y_m) argumentning biror qiymatida φ_kˉֿ( ₁,..., _m)j , 1 j  bo‘lsa, bu  ( ₁,..., _m) bahoga erishishda j-nomerli predmet kamida bir marta qatnashganligini bildiradi, ya’ni x_j1 I(k:y₁,...,y_m) funksiya qiymatlarini k1 bo‘lganda hisoblash hech qanday qiyinchilik tug‘dirmaydi, haqiqatan, agar 1-nomerli predmetdan olinmagan bo‘lsa , baho ₁(y₁,...,y_m)0 , aks holda

₁(y₁,...,y_m)0 bo‘ladi , shunga asosan
(8)
bu yerda y_i  0, 1,...,b_i , i1,...,m.
Endi 11,...,y_m) funksiya qiymatlarini aniqlovchi formulani keltiramiz. _k(y₁,...,y_m) funksiyani qiymatlarini topish usuli (7) formulaga asosan, agar (y₁,...,y_m) argumentning biror
( ₁,..., _m) qiymatida _k(y₁-a_1k,...,y_m-a_mk)  S_k< _k-1( ₁,..., _m) tengsizlik o‘rinli bo‘lsa (bu degani _k( ₁,..., _m) _k-1( ₁,..., _m)), ya’ni _k( ₁,..., _m) bahoga erishish uchun k-nomerli predmet qatnashma ganligi ma’lum bo‘ladi, shuning uchun I(k; ₁,..., _m) I(k-1; ₁,..., _m) deb olinadi. Agar _k( ₁-a_k,..., _m-a_k)S_k  _k-1(y₁,..., _m) tengsizlik bajarilsa bunda _k( ₁,..., _m) bahoga erishish uchun k-nomerli predmet kamida bir marta qatnashganligini bildiradi, demak I(k; ₁,..., _m)k_` deb olinishi kerak. Shunday qilib I(k;y₁,...,y_m), 1
I(k: y₁,...,y_m)  (9)
Bu yerda y_i0,1,...,b_i , i1,...,m .
Natijada (8) va (9) formulalar yordamida I(k:y₁,...,y_m), k1,n; y_i0,1,...,b_i, i1,m funksiyani barcha qiymatlari aniqlanadi. Yuqorida aytilganlardan ko‘rinib turibdiki _k(y₁,...,y_m) va I(k;y₁,...,y_m) funksiyalarning qiymatlari bir paytda (parallel) hisoblab borilishi maqsadga muvofiqdir. Agar k fiksirlanganda _k(y₁,...,y_m) va I(k;y₁,...,y_m) y_i0,1,...,b_i , i1,...,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(y₁,...,y_m) va I(k;y₁,...,y_m) k1,...,n, y_i0,1,...,b_i , i1,...,m funksiyalarning qiymatlarini n∙(b₁1)∙...∙(b_m1) 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(y₁,...,y_m) va I(n:y₁,...,y_m) funksiyalarning qiymatlari (y₁,...,y_m) argumentni barcha mumkin bo‘lgan qiymatlarida aniqlangan bo‘lsin. U holda qo‘yilgan masalani yechimi quyidagicha topiladi: Predmetlarni sonini aniqlash jadvalidan I(n:b₁,...,b_m) songa qaraladi. Faraz etaylik y j₁ ga teng bo‘lsin, bu j₁- nomerli predmet kamida bir marta olinishligini bildiradi. Shuning uchun x_j11 deymiz. Keyin I(n;b₁-a_1j,...,b_m-a_mj1) I(n; ₁,..., _m) ning qiymatiga qaraymiz , agar y j₂ ga teng bo‘lsa, xuddi avvalgidek, bu j₂- nomerli predmet kamida bir marta olinish kerakligini bildiradi. Demak, x_j21 agar j₂j₁ bo‘lsa, u holda j₁-nomerli predmet kamida ikki marta ishtirok etganligini bildiradi. Shuning uchun x_j22 deb olinadi. Bunda, birinchi holda ya’ni I(n; ₁,..., _m)j₂ bo‘lganda, I(n; ₁-a_1j2,..., _m-a_mj2)ning qiymatiga qaraladi. Ikkinchi holda, ya’ni I(n; ₁,..., _m)j, da I(n; ₁-a_{1j1,..., m} -a_mj) dan so‘ng ₁,..., _n sonlari aniqlanib, ular har bir predmetdan nechtadan olinishi kerakligini bildiradi va bundan maqsad funksiya qiymati maksimal bo‘lib, birinchi jadvaldan _n(b₁,...,b_m) bilan aniqlanadi. Bunda shu etiborga loyiqki, agar jadvallarning barcha qiymatlari saqlanib qolgan bo‘lsa, n dan kichik predmet turlari va b₁,...,b_m 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. n3, m2, c₁2, c₂3, c₃1, a₁₁2, a₁₂1, a₁₃1, a₂₁1, a₂₂2, a₂₃0, b₁3, b₂4 bo‘lsin.
Ya’ni quyidagi ko‘rinishdagi masalaga ega bo‘lamiz:
2x₁3x₂x₃max
2x₁x₂x₃3
x₁2x₂4
x₁,x₂0 - butun.
k1 da (7) - formula yordamida ₁(y₁,y₂) va (8) - formula yordamida I(1:y₁,y₂) funksiyalarning qiymatlarini aniqlaymiz.
₁(1,2)2 min{ ,2}0, I(1;1,2)0
₁(1,3)2 min{ ,3}0, I(1;1,3)0
₁(1,4)2 min{ ,4}0, I(1;1,4)0
₁(2,1)2 min{1,1}2, I(1;2,1)1
₁(2,2)2 min{1,2}2 , I(1;2,2)1
₁(2,3)2 min{1,3}2 , I(1;2,3)1
₁(2,4)2 min{1,4}2 , I(1;2,4)1
₁(3,1)2 min{ ,1}2, I(1;3,1)1
-- -- -- -- -- --
₁(3,4)2 min{ ,4}2 , I(1;3,4)1.
k2 da (7) va (9) formulalar yordamida mos ravishda ₂(y₁,y₂) va I(2:y₁,y₂) larni aniqlaymiz.
₂(1,1)max(₁(1,1), ₂(1-1,1-2)3)0 , I(2;1,1)0
₂(1,2)max(₁(1,2), ₂(1-1,2-2)3)3, I(2;1,1)2
₂(1,3)max(₁(1,3), ₂(1-1,3-2)3)3, I(2;1,3)2
₂(1,4)max(₁(1,4), ₂(1-1,4-2)3)3, I(2;1,4)2
₂(2,1)max(₁(2,1), ₂(2-1,1-2)3)2, I(2;2,1)1
₂(2,2)max(₁(2,2), ₂(2-1,2-2)3)3, I(2;2,2)2
₂(2,3)max(₁(2,3), ₂(2-1,3-2)3)3, I(2;2,3)2
₂(2,4)max(₁(2,4), ₂(2-1,4-2)3)6, I(2;2,4)2
₂(3,1)max(₁(3,1), ₂(3-1,1-2)3)2, I(2;3,1)1
₂(3,2)max(₁(3,2), ₂(3-1,2-2)3)3, I(2;3,2)2
₂(3,3)max(₁(3,3), ₂(3-1,3-2)3)5, I(2;3,3)2
₂(3,4)max(₁(3,4), ₂(3-1,4-2)3)6, I(2;3,4)2
Endi k3 qatlam elementlarining qiymatlarini ya’ni _k(y₁,y₂), I(k:y₁,y₂) topamiz.
₃(1,1)max(₂(1,1), ₃(1-1,1)1)1, I(3;1,1)3
₃(1,2)max(₂(1,2), ₃(1-1,2)1)3, I(3;1,2)2
₃(1,3)max(₂(1,3), ₃(1-1,3)1)3, I(3;1,3)2
₃(1,4)max(₂(1,4), ₃(1-1,4)1)3, I(3;1,4)2
₃(2,1)max(₂(2,1), ₃(2-1,1)1)2, I(3;2,1)3
₃(2,2)max(₂(2,2), ₃(2-1,2)1)3, I(3;2,2)2
₃(2,3)max(₂(2,3), ₃(2-1,3)1)3, I(3;2,3)2
₃(2,4)max(₂(2,4), ₃(2-1,4)1)6, I(3;2,4)2
₃(3,1)max(₂(3,1), ₃(3-1,1)1)3, I(3;3,1)3
₃(3,2)max(₂(3,2), ₃(3-1,2)1)3, I(3;3,2)3
₃(3,3)max(₂(3,3), ₃(3-1,3)1)5, I(3;3,3)2
₃(3,4)max(₂(3,4), ₃(3-1,4)1)7, I(3;3,4)3
Predmetlar sonini aniqlovchi jadvalning oxirgi k3 qatlami I(3;3,4)3 bo‘lganligi uchun ₃1 deb olamiz va I(3;3,-1,4-0)2 bo‘lgani uchun ₂1 bo‘ladi. Xuddi shunday I(3;2-1,4-2)2, demak ₂2; I(3;1-1,2-2) I(3;0,0)- element jadvalda yo‘qligi uchun predmetlarni sonini topish jarayonini to‘xtatamiz. Shunday qilib, ₁0, ₂2 , ₃1 yechimga ega bo‘lamiz. Endi baholar jadvalini oxirgi k3 qatlamidan maqsad funksiyani maksimal qiymati ₃(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.