Algoritmlarni Loyihalash fanidan 2-laboratoriya ishi tekshirdi: Qilichev Oybek. Topshirdi: Yuldoshev Boboxon

Al-Xorazmiy nomidagi Toshkent Axborot texnologiyalari universiteti Dasturiy inginering fakulteti 311-20 guruh talabasi Yuldoshev Boboxonning Algoritmlarni Loyihalash fanidan

2-LABORATORIYA ISHI


Tekshirdi: Qilichev Oybek.
Topshirdi:Yuldoshev Boboxon.

1. 
   CHD ni simplex usulda yechish
   

1.Bu muammoni hal qilish uchun zaruriy shart:
cheklash tizimining o'ng qismlaridagi raqamlar manfiy bo'lmasligi kerak.
Bu shart bajariladi.
2. Bu masalani hal qilishning zaruriy sharti:
barcha cheklovlar tenglama bo'lishi kerak.

S1 ≥ 0, S2 ≥ 0. Kiritilgan o'zgaruvchilar S1, S2, bo'sh o'zgaruvchilar deyiladi.

Asos nima?

Agar o'zgaruvchi bu tenglamaga bir koeffitsient bilan kirsa va boshqa tenglamalar tizimiga kirmasa (agar tenglamaning o'ng tomonida manfiy bo'lmagan son bo'lsa) o'zgaruvchi tenglama uchun asosiy o'zgaruvchi deyiladi.
Agar har bir tenglama asosiy o'zgaruvchiga ega bo'lsa, ular tizimning asosi borligini aytishadi.
Asosiy bo'lmagan o'zgaruvchilar asosiy bo'lmagan deb ataladi.

Simpleks usulining g'oyasi nima?

Har bir bazis bitta funktsiya qiymatiga mos keladi. Ulardan biri F funksiyaning maksimal qiymatidir.
Biz bir asosdan ikkinchisiga o'tamiz.
Keyingi bazis shunday tanlanadiki, F funksiyaning qiymati bizdagidan kam bo'lmaydi.
Shubhasiz, har qanday muammo uchun mumkin bo'lgan asoslar soni unchalik katta emas.
Shunday qilib, ertami-kechmi javob olinadi.
Qanday qilib biz bir asosdan ikkinchisiga o'tamiz?
Yechimni jadvallar ko'rinishida yozib olish qulayroqdir. Jadvalning har bir satri tizim tenglamasiga teng. Belgilangan qator funksiya koeffitsientlaridan iborat (quyidagi jadvalga qarang). Bu har safar o'zgaruvchilarni qayta yozmaslikka imkon beradi. Bu vaqtni tejaydi.
Belgilangan qatorda maksimal ijobiy koeffitsientni tanlang (biz har qanday ijobiy koeffitsientni tanlashimiz mumkin).
Bu F funksiyaning bizdagidan kam bo'lmagan qiymatini olish uchun kerak.
Ustun tanlangan.
Tanlangan ustunning ijobiy koeffitsientlari uchun biz koeffitsient t ni hisoblaymiz va minimal qiymatni tanlaymiz.
Bu boshqa asosga o'tgandan keyin tenglamalarning o'ng qismida manfiy bo'lmagan raqamlarni olish uchun kerak.
Qator tanlangan.
Asosiy bo'ladigan element topildi. Keyinchalik, biz hisoblashimiz kerak.



Bizning tizimimizda asos bor. Muammoni hal qilishni boshlashimiz mumkin.
F = 2 x1 + 3 x2
Asosiy bo'lmagan o'zgaruvchilar nolga teng. Ongda biz asosiy o'zgaruvchilarning qiymatlarini topishimiz mumkin. (tizimga qarang)
F funktsiyasi faqat asosiy bo'lmagan o'zgaruvchilarni o'z ichiga oladi. Demak, bu asos uchun F funksiyaning qiymatini aqldan topish mumkin.
x1 = 0 x2 = 0
S1 = 1 S2 = 1 => F = 0
Dastlabki asos topildi. F funktsiyaning boshlang'ich bazisiga mos keladigan qiymati topildi.


4. F funksiyaning maksimal qiymatini topish.



Asosiy bo'lmagan o'zgaruvchilar nolga teng. Ongda biz asosiy o'zgaruvchilarning qiymatlarini topishimiz mumkin. (jadvalga qarang)
F funktsiyasi faqat asosiy bo'lmagan o'zgaruvchilarni o'z ichiga oladi. Demak, bu asos uchun F funksiyaning qiymatini aqldan topish mumkin. (jadvaldagi ajratilgan qatorga qarang)

x1 = 0 S1 = 0

x2 = 1/2 S2 = 1/2 => F - 3/2 = 0 => F = 3/2

Asosiy bo'lmagan o'zgaruvchilar nolga teng. Ongda biz asosiy o'zgaruvchilarning qiymatlarini topishimiz mumkin. (jadvalga qarang)
F funktsiyasi faqat asosiy bo'lmagan o'zgaruvchilarni o'z ichiga oladi. Demak, bu asos uchun F funksiyaning qiymatini aqldan topish mumkin. (jadvaldagi ajratilgan qatorga qarang)
S1 = 0 S2 = 0
x1 = 1/3 x2 = 1/3 => F - 5/3 = 0 => F = 5/3
Belgilangan qatorda ijobiy koeffitsientlar mavjud emas. Shuning uchun F funksiyaning maksimal qiymati topildi.