|
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Kiberxavfsizlik fakuliteti
Axborot xavfsizliogi yo’nalishi 714-22 guruh talabasi Maxmasoaotv Shaxzodning Algoritim loyihalsh fanidan
2 – amaliy ishi
Bajardi: Maxmasoatov Shaxzod
Tekshirdi : Qo’doshev .H
1-topshiriq
Variant parametrlarini quyidagicha aniqlang: n1={N/3}+1; n2={N/5}+1; n3={N/7}+1, bu yerda N talabalarning potokdagi nomeri. {N/3} bu N sonini 3 ga bo’lgandagi qoldig’i.
N=84
48
𝑛1 = { 3 } + 1 = 0 + 1 = 1
48
𝑛2 = { 5 } + 1 = 3 + 1 = 4
48
𝑛3 = { 7 } + 1 = 6 + 1 = 7
𝑥3 + 1 ∙ 𝑥2 − 4 ∙ 𝑥 − 7 = 0
[0,2.2206928199873]
Chiziqli dasturlash masalasi.
15𝑥1 + 10𝑥2 + 5𝑥3 ≤ 35 ∙ 1 + 35 ∙ 4 + 20 ∙ 7
{10𝑥1 + 4𝑥2 + 12𝑥3 ≤ 32 ∙ 1 + 18 ∙ 4 + 28 ∙ 7
4𝑥1 + 15𝑥2 + 10𝑥3 ≤ 18 ∙ 1 + 34 ∙ 4 + 35 ∙ 7
15𝑥1 + 10𝑥2 + 5𝑥3 ≤ 315
{10𝑥1 + 4𝑥2 + 12𝑥3 ≤300 4𝑥1 + 15𝑥2 + 10𝑥3 ≤ 399
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
𝐿 = 1800𝑥1 + 2000𝑥2 + 1500𝑥3 → 𝑚𝑎𝑥
Bu masalani kanonik ko’rinishga keltirib olamiz, ya’ni sun’iy 𝑥4, 𝑥5, 𝑥6
o’zgaruvchilarni tengsizlikning chap tomoniga kiritamiz.
15𝑥1 + 10𝑥2 + 5𝑥3 + 𝑥4 = 315
{10𝑥1 + 4𝑥2 + 12𝑥3 + 𝑥5 = 300 4𝑥1 + 15𝑥2 + 10𝑥3 + 𝑥6 = 399
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
𝐿 = 1800𝑥1 + 2000𝑥2 + 1500𝑥3 + 0 ∙ 𝑥4 + 0 ∙ 𝑥5 + 0 ∙ 𝑥6 → 𝑚𝑎𝑥
Berilgan tenglama uchun birinchi sipmleks jadvalni tuzib olamiz:
Birinchi jadvalni hisoblarsiz to’gridan-to’gri masalani sharti bo’yicha to’ldiramiz. Bu yerda basis o’zgaruvchilar ham masala berilishidan olinadi. Jadvalda bu o’zgaruvchilarning mos qiymatlari ustunida bir turibdi. Bazis o’zgaruvchilari narxlari ko’rsatilgan ustunida ham nol turibdi, yani 𝐶4 = 𝐶5 = 𝐶6 = 0. Endi ∆𝑗 ni hisoblaymiz.
3
∆𝑗= ∑ 𝐶𝑘𝑖 ∙ 𝐴𝑖𝑗 − 𝐶𝑗
𝑖=1
∆1= 0 ∙ 15 + 0 ∙ 10 + 0 ∙ 4 − 1800 = −1800
∆2= 0 ∙ 10 + 0 ∙ 4 + 0 ∙ 15 − 2000 = −2000
∆3= 0 ∙ 5 + 0 ∙ 12 + 0 ∙ 10 − 1500 = −1500
∆4= 0 ∙ 0 + 0 ∙ 1 + 0 ∙ 0 − 0 = 0
∆5= 0 ∙ 0 + 0 ∙ 0 + 0 ∙ 1 − 0 = 0
∆6= 0 ∙ 0 + 0 ∙ 0 + 0 ∙ 1 − 0 = 0
Bu yerda hal qiluvchi element ikkinchi ustunda bo’ladi. Jadvalda ∆𝑗 qatorda manfiy qiymatlar bo’lgani uchun, bu qatordagi yechimlar rejasi optimal bo’lmaydi. Jadvaldagi 𝛿𝑖 ustunni quyidagi formula bo’yicha qiymatlarini aniqlaymiz.
𝛿𝑖
= 𝐵𝑖
𝐴𝑖2
, 𝑖 = 1,2,3
Topilgan natijalar ichidan eng kichik 𝛿𝑖 ning qiymati 399/15 ga teng ekan, shuning uchun uchinchi qatorda xal qiluvchi element qiymati bo’ladi. Hal qiluvchi elementni belgilab olamiz “26”. Ikkinchi sipleks jadvalni to’ldirishni boshlaymiz. Jadvalni to’ldirishni hal qiluvchi qatordan boshlaymiz. Qatordagi hamma sonlarni
hal qiluvchi element yani 26 ga bo’lamiz.
Jadvalda qolgan qator elementlarini yuqorida aytilgan hisoblashlar orqali to’ldiriladi. Yangi hosil bo’lgan qatorni 4 ga ko’paytirib ikkinchi qator elementlarini ayirib, ikkinchi qatorga yozamiz, xuddi shunday hosil bo’lgan qatorni 10 ga ko’paytirib uchinchi qator elementlarini ayirib, uchinchi qatoga yozamiz.
∆𝑗 ni hisoblaymiz:
∆1= 0 ∙ 12.33 + 0 ∙ 8.93 + 2000 ∙ 0.27 − 1800 = -1260
∆2= 0 ∙ 0 + 0 ∙ 0 + 2000 ∙ 1 − 2000 = 0
−5 28 2 −500
∆3= 0 ∙ 3 + 0 ∙ 3 + 2000 ∙ 3 − 1500 = 3
∆4= 0 ∙ 1 + 0 ∙ 0 + 2000 ∙ 0 − 0 = 0
∆5= 0 ∙ 0 + 0 ∙ 1 + 2000 ∙ 0 − 0 = 0
−2 −4 1 400
∆6= 0 ∙ 3 + 0 ∙ 15 + 2000 ∙ 15 − 0 = 3
∆𝑗 qatorda manfiy qiymatlar borligi uchun uchinchi simpleks jadvalga o’tamiz.
Jadvalda qolgan qator elementlarini yuqorida aytilgan hisoblashlar orqali to’ldiriladi. Yangi hosil bo’lgan qatorni 134/15 ga ko’paytirib ikkinchi qator elementlarini ayirib, ikkinchi qatorga yozamiz, xuddi shunday hosil bo’lgan qatorni 4/15 ga ko’paytirib uchinchi qator elementlarini ayirib, uchinchi qatoga yozamiz.
∆𝑗 ni hisoblaymiz:
∆1= 1800 ∙ 1 + 0 ∙ 0 + 2000 ∙ 0 − 1800 = 0
∆2= 1800 ∙ 0 + 0 ∙ 0 + 2000 ∙ 1 − 2000 = 0
−5 390 26 −12500
∆3= 1800 ∙ 37 + 0 ∙ 37 + 2000 ∙ 37 − 1500 = 37
3 −134 −4 3800
∆4= 1800 ∙ 37 + 0 ∙ 185 + 2000 ∙ 185 − 0 = 37
∆5= 1800 ∙ 0 + 0 ∙ 1 + 2000 ∙ 0 − 0 = 0
−2 8 3 2400
∆6= 1800 ∙ 37 + 0 ∙ 37 + 2000 ∙ 37 − 0 = 37
∆𝑗 qatorda manfiy qiymatlar borligi uchun to’rtinchi simpleks jadvalga o’tami
Jadvalda qolgan qator elementlarini yuqorida aytilgan hisoblashlar orqali to’ldiriladi. Yangi hosil bo’lgan qatorni -5/37 ga ko’paytirib birinchi qator elementlarini ayirib, ikkinchi qatorga yozamiz, xuddi shunday hosil bo’lgan qatorni 26/37 ga ko’paytirib uchinchi qator elementlarini ayirib, uchinchi qatoga yozamiz.
∆1= 1800 ∙ 1 + 1500 ∙ 0 + 2000 ∙ 0 − 1800 = 0
∆2= 1800 ∙ 0 + 1500 ∙ 0 + 2000 ∙ 1 − 2000 = 0
∆3= 1800 ∙ 0 + 1500 ∙ 0 + 2000 ∙ 1 − 1500 = 0
14 −67 2 3100
∆4= 1800 ∙ 195 + 1500 ∙ 975 + 2000 ∙ 75 − 0 = 39
1 37 −1 1250
∆5= 1800 ∙ 78 + 1500 ∙ 390 + 2000 ∙ 15 − 0 = 39
−2 8 1 2800
∆6= 1800 ∙ 39 + 0 ∙ 390 + 2000 ∙ 15 − 0 = 39
Bu jadvalda ∆𝑗 qatorda barcha qiymatlar musbat, shuning uchun topilgan reja optimal bo’ladi. Oxirgi jadval rejasida javobimiz quyidagiga teng bo’ladi:
𝑥1 =
1477
195 , 𝑥 2 =
1477
841
75 , 𝑥 3 =
841
2389
975 , 𝑥 4 = 0, 𝑥 5 = 0, 𝑥 6 = 0
2389
𝐿𝑚𝑎𝑥 = 1800 ∙ 195 + 2000 ∙ 75 + 1500 ∙
1482361
= 39 ≈ 38009.256410
975 + 0 ∙ 0 + 0 ∙ 0 + 0 ∙ 0
Egizak masala.
15𝑦1 + 10𝑦2 + 4𝑦3 ≥ 1800
{10𝑦1 + 4𝑦2 + 15𝑦3 ≥ 2000 5𝑦1 + 12𝑦2 + 10𝑦3 ≥ 1500
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
𝑄 = 315𝑦1 + 390𝑦2 + 399𝑦3 → 𝑚𝑖𝑛
Shuni ta’kidlash kerakki, simpleks usulida bir vaqtning o’zida ham berilgan va ham ikkilangan masalaning yechimini topish mumkin. Oxirgi simpleks jadvalda
∆𝑗 qatorda sun’iy basis noma’lumlari ostida egizak masalaning yechimi bo’ladi.
Bizning misolimizda bu qiymatlar ∆4
= 3100 , ∆
5
39
= 1250 , ∆
6
39
= ga teng. Bundan
2800
39
2800
biz 𝑦 = 3100 , 𝑦 = 1250 , 𝑦 = ekanligini ko’rishimiz mumkin. Bu xol uchun
1 39 2 29 3 39
𝑄 qiymatini hisoblaymiz:
𝑄 = 315 ∙
3100
39 + 390 ∙
1250
39 + 399
∙
2800
=
39
1482361
39 =38009.256
Agar bu yechimni birlamchi yechim bilan solishtirsak bir xilligini ko‘ramiz:
𝑄𝑚𝑖𝑛 = 𝐿𝑚𝑎𝑥 =
1482361
39
|
