Mavzu: Algoritmlarni vaqt bo’yicha va hajmiy murakkabligini baholash uchun tekis va logarifmik baholash usullari

Foydalanilgan adabiyotlar

1. 
   https://dasturchi.uz/algorithm/algoritm-haqida-tushuncha2/
   
2. 
   https://dasturchi.uz/algorithm/algoritm-algoritm-haqida-tushuncha/
   
3. 
   https://ilyarm.ru/uz/lineinyi-vid-algoritma-tipy-algoritmov-lineinye-razvetvlyayushchiesya-ciklicheskie.html
   
4. 
   https://fayllar.org/1-mavzu-algoritm-tushunchasi-va-ulardan-foydalanish.html?page=2
   
5. 
   https://arxiv.uz/ru/documents/slaydlar/informatika-va-at/algoritm-turlari-xossalari-berilish-usullari-algoritm-blok-sxema-shaklida-berilish-usuli
   

Ustun asos elementlari (B)

Dastlabki bosqichda biz aniqlagan asosiy elementlarni jadvalga o'tkazamiz:
B₁ = x₄;
B2 = x 5;
B3 = x 6;
Cb ustun elementlari
Ushbu ustundagi har bir katak mos keladigan qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng.
Cb₁ = 0;
Cb₂ = 0;
Cb₃ = 0;

Maqsad funksiyasi qiymati

Maqsad funksiyasining qiymatini elementlar bo'yicha Cb ustunini P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz.
Maksimal qiymat _P = (Cb₁ * P₀₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ = (0 * 149) + (0 * 194) + (0 * 531) = 0;
Har bir boshqariladigan o‘zgaruvchi bo‘yicha ballarni o‘zgaruvchi ustunidagi qiymatni Cb ustunidagi qiymatga elementlar bo‘yicha ko‘paytirish, mahsulotlar natijalarini yig‘ish va shu o‘zgaruvchi yordamida ularning yig‘indisidan maqsad funksiya koeffitsientini ayirish yo‘li bilan hisoblaymiz.
Max_x1 = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) ) - k_x1 = ((0 * 3) + (0 * 4) + (0 * 9) ) - 110 = -110;
Max_x2 = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) ) - k_x2 = ((0 * 3) + (0 * 4) + (0 * 9) ) - 110 = -110;
Max_x3 = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) ) - k_x3 = ((0 * 1) + (0 * 1) + (0 * 9) ) - 82 = -82;
Max_x4 = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) ) - k_x4 = ((0 * 1) + (0 * 0) + (0 * 0) ) - 0 = 0;
Max_x5 = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) ) - k_x5 = ((0 * 0) + (0 * 1) + (0 * 0) ) - 0 = 0;
Max_x6 = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) ) - k_x6 = ((0 * 0) + (0 * 0) + (0 * 1) ) - 0 = 0;

Ustun asos elementlari (B)
Oldingi iteratsiyaning hisob-kitoblari natijalari uchun biz o'zgaruvchini x5 bazasidan olib tashlaymiz va uning o'rniga x1 ni qo'yamiz. Boshqa barcha hujayralar o'zgarishsiz qoladi.
Cb ustun elementlari
Ushbu ustundagi har bir katak mos keladigan qatordagi asosiy o'zgaruvchiga mos keladigan koeffitsientga teng.
Cb1 = 0;
Cb2 = 110;
Cb3 = 0;
O'zgaruvchan o'zgaruvchilarning qiymatlari va P ustuni
(Oldingi iteratsiya ma'lumotlari dastlabki ma'lumotlar sifatida olinadi)
Barcha kataklarni faqat asosga kiritilgan o'zgaruvchiga mos keladigan nol bilan to'ldiring:
(Ruxsat elementi o'zgarishsiz qoladi)
x1,1 = 0;
x3.1 = 0;
Biz ruxsat beruvchi elementi bo'lgan qatorni oldingi jadvaldan joriy jadvalga o'tkazamiz, uning qiymatlarini ruxsat beruvchi elementga elementlar bo'yicha ajratamiz:
Р2 = Р2 / х 2,1 _{= 194}/ 4 = 48,5;
х_2,1 = х_2,1 / х_2,1 = 4/4 = 1;
х_2,2 = х_2,2 / х_2,1 = 4/4 = 1;
х_2,3 = х_2,3 / х_2,1 = 1/4 = 0,25;
х_2,4 = х_2,4 / х_2,1 = 0/4 = 0;
х_2,5 = х_2,5 / х_2,1 = 1/4 = 0,25;
х_2,6 = х_2,6 / х_2,1 = 0/4 = 0;
Qolgan bo'sh katakchalar, ballar qatori va Q ustunidan tashqari, ruxsat elementiga nisbatan to'rtburchaklar usuli yordamida hisoblanadi:
P1 = (P1 * x_2,1) - (x_1,1 *P2) / x_2,1 = ((149 * 4) - (3 * 194)) / 4 = 3.5;
Р3 = (Р3 * х_2,1) - (х 3,1 * Р2) / х_2,1 = ((531 * 4) - (9 * 194)) / 4 = 94.5;
x_1,1 = ((x_1,1 * x_2,1) - (x_1,1 * x_2,1)) / x_2,1 = ((3 * 4) - (3 * 4)) / 4 = 0;
х_1,3 = ((х_1,3 * х_2,1) - (х_1,1* х_2,3)) / х_2,1 = ((1 * 4) - (3 * 1)) / 4 = 0.25;
х_1,4 = ((х_1,4* х_2,1) - (х_1,1* х_2,4)) / х_2,1 = ((1 * 4) - (3 * 0)) / 4 = 1;
х_1,5 = ((х_1,5* х_2,1) - (х_1,1* х_2,5)) / х_2,1 = ((0 * 4) - (3 * 1)) / 4 = -0.75;
х_1,6 = ((х_1,6 * х_2,1) - (х_1,1* х_2,6)) / х_2,1 = ((0 * 4) - (3 * 0)) / 4 = 0;
х_3,1 = ((х_3,1 * х_2,1) - (х_3,1* х_2,1)) / х_2,1 = ((9 * 4) - (9 * 4)) / 4 = 0;
х_3,3 = ((х_3,3 * х_2,1) - (х_3,1* х_2,3)) / х_2,1 = ((9 * 4) - (9 * 1)) / 4 = 6.75;
х_3,4 = ((х_3,4 * х_2,1) - (х_3,1* х_2,4)) / х_2,1 = ((0 * 4) - (9 * 0)) / 4 = 0;
х_3,5 = ((х_3,5* х_2,1) - (х_3,1* х_2,5)) / х_2,1 = ((0 * 4) - (9 * 1)) / 4 = -2.25;
х_3,6 = ((х_3,6 * х_2,1) - (х_3,1* х_2,6)) / х_2,1 = ((1 * 4) - (9 * 0)) / 4 = 1;
Maqsad funksiyasi qiymati
Maqsad funksiyasining qiymatini elementlar bo'yicha Cb ustunini P ustuniga ko'paytirib, mahsulotlarning natijalarini qo'shib hisoblaymiz.
maksimal qiymat _P = (Cb₁ * P₀₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ = (0 * 3.5) + (110 * 48.5) + (0 * 94.5) = 5335;

Cb₁ = 82; Cb₂ = 110; Cb₃ = 0;
х_2,3 = 0; х_3,3 = 0;
_Р1 =_Р1 / х_1,3 = 3,5 / 0,25 = 14;
х_1,1 = х_1,1 / х_1,3 = 0 / 0,25 = 0;
х_1,2 = х_1,2 / х_1,3 = 0 / 0,25 = 0;
х_1,3 = х_1,3 / х_1,3 = 0,25 / 0,25 = 1;
х_1,4 = х_1,4 / х_1,3 = 1 / 0,25 = 4;
х_1,5 = х_1,5 / х_1,3 = -0,75 / 0,25 = -3;
х_1,6 = х_1,6 / х_1,3 = 0 / 0,25 = 0;
Qolgan bo'sh katakchalar, ballar qatori va Q ustunidan tashqari, ruxsat elementiga nisbatan to'rtburchaklar usuli yordamida hisoblanadi:
P2 = (P2 * x_1,3) - (x 2,3 * P1) / x_1,3 = ((48.5 * 0.25) - (0.25 * 3.5)) / 0.25 = 45;
Р3 = (Р3 * х_1,3) - (х_3,3 * Р1) / х_1,3 = ((94.5 * 0.25) - (6.75 * 3.5)) / 0.25 = 0;
х_2,1 = ((х_2,1 * х_1,3) - (х_2,3* х_1,1)) / х_1,3 = ((1 * 0.25) - (0.25 * 0)) / 0.25 = 1;
х_2,2 = ((х_2,2 * х_1,3) - (х_2,3*х_1,2)) / х_1,3 = ((1 * 0.25) - (0.25 * 0)) / 0.25 = 1;
х_2,3 = ((х_2,3 * х_1,3) - (х_2,3* х_1,3)) / х_1,3 = ((0.25 * 0.25) - (0.25 * 0.25)) / 0.25 = 0;
х_2,5 = ((х_2,5 * х_1,3) - (х_2,3* х_1,5)) / х_1,3 = ((0.25 * 0.25) - (0.25 * -0.75)) / 0.25 = 1;
х_2,6 = ((х_2,6 * х_1,3) - (х_2,3* х_1,6)) / х_1,3 = ((0 * 0.25) - (0.25 * 0)) / 0.25 = 0;
х_3,1 = ((х_3,1 * х_1,3) - (х_3,3* х_1,1)) / х_1,3 = ((0 * 0.25) - (6.75 * 0)) / 0.25 = 0;
х_3,2 = ((х_3,2 * х_1,3) - (х_3,3*х_1,2)) / х_1,3 = ((0 * 0.25) - (6.75 * 0)) / 0.25 = 0;
х_3,3 = ((х_3,3 * х_1,3) - (х_3,3* х_1,3)) / х_1,3 = ((6.75 * 0.25) - (6.75 * 0.25)) / 0.25 = 0;
х_3,5 = ((х_3,5 * х_1,3) - (х_3,3* х_1,5)) / х_1,3 = ((-2.25 * 0.25) - (6.75 * -0.75)) / 0.25 = 18;
х_3,6 = ((х_3,6 * х_1,3) - (х_3,3* х_1,6)) / х_1,3 = ((1 * 0.25) - (6.75 * 0)) / 0.25 = 1;
maksimal qiymat  _P = (Cb₁ * P₀₁) + (Cb₁₁ * P₂ + (Cb₂₁ * P₃ = (82 * 14) + (110 * 45) + (0 * 0) = 6098;
Har bir boshqariladigan o‘zgaruvchi bo‘yicha ballarni o‘zgaruvchi ustunidagi qiymatni Cb ustunidagi qiymatga elementlar bo‘yicha ko‘paytirish, mahsulotlar natijalarini yig‘ish va shu o‘zgaruvchi yordamida ularning yig‘indisidan maqsad funksiya koeffitsientini ayirish yo‘li bilan hisoblaymiz.
Max_x1 = ((Cb₁ * x_1,1) + (Cb₂ * x_2,1) + (Cb₃ * x_3,1) ) - k_x1 = ((82 * 0) + (110 * 1) + (0 * 0) ) - 110 = 0;
Max_x2 = ((Cb₁ * x_1,2) + (Cb₂ * x_2,2) + (Cb₃ * x_3,2) ) - k_x2 = ((82 * 0) + (110 * 1) + (0 * 0) ) - 110 = 0;
Max_x3 = ((Cb₁ * x_1,3) + (Cb₂ * x_2,3) + (Cb₃ * x_3,3) ) - k_x3 = ((82 * 1) + (110 * 0) + (0 * 0) ) - 82 = 0;
Max_x4 = ((Cb₁ * x_1,4) + (Cb₂ * x_2,4) + (Cb₃ * x_3,4) ) - k_x4 = ((82 * 4) + (110 * -1) + (0 * -27) ) - 0 = 218;
Max_x5 = ((Cb₁ * x_1,5) + (Cb₂ * x_2,5) + (Cb₃ * x_3,5) ) - k_x5 = ((82 * -3) + (110 * 1) + (0 * 18) ) - 0 = -136;
Max_x6 = ((Cb₁ * x_1,6) + (Cb₂ * x_2,6) + (Cb₃ * x_3,6) ) - k_x6 = ((82 * 0) + (110 * 0) + (0 * 1) ) - 0 = 0;
Boshqariladigan o'zgaruvchilarning baholari orasida salbiy qiymatlar mavjud bo'lganligi sababli, joriy jadval hali optimal echimga ega emas. Shuning uchun biz bazaga eng kichik salbiy bahoga ega o'zgaruvchini kiritamiz.
Bazisdagi o'zgaruvchilar soni doimo doimiy bo'ladi, shuning uchun qaysi o'zgaruvchini bazadan olib tashlashni tanlash kerak, buning uchun biz Q ni hisoblaymiz.
Q ustunining elementlari P ustunidagi qiymatlarni asosga kiritilgan o'zgaruvchiga mos keladigan ustunning qiymatiga bo'lish yo'li bilan hisoblanadi:
Q1 = P1 / x_1,5 = 14 / -3 = -4,67;
Q2_{= P2 / x 2,5} = 45/1 = 45;
_{Q3 = P3 / x 3,5 = 0 / 18 = 0};

Javob:
F* = 12218

X* = (0; 0; 149)