Muxammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti algoritimlash va loyihalash Amaliy ish -1

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKASIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUXAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI


Algoritimlash va loyihalash


Amaliy ish -1

Bajardi :	Mingboyev Adxamjon Axmadjon o‘g‘li
Fan :	Algoritimlash va loyihalash
Guruh : Variant:	070-20 14

Variant-14

Berilgan misol:

Yechim:
Muammo shundaki
Tegishli ravishda bo'sh, ortiqcha va sun'iy o'zgaruvchilarni qo'shish orqali muammo kanonik shaklga aylantiriladi.
1. Cheklov-1 '≤' turi bo'lgani uchun biz S1 o'zgaruvchisini qo'shishimiz kerak.
2. Cheklov-2 '≤' turi bo'lgani uchun biz S2 bo'sh o'zgaruvchisini qo'shishimiz kerak.
3. Cheklov-3 '≤' turi bo'lgani uchun biz S3 bo'sh o'zgaruvchisini qo'shishimiz kerak.


Ishlanishi=>
Tengsizlikdan tenglamaga o’tkizib olamiz.

Dastlabki bosqich cheklovlarning o'ng qismida salbiy qiymatlardan (agar mavjud bo'lsa) qutulish zarurati bilan boshlanadi. Nima uchun tegishli cheklovlar

-1 ga ko'paytiriladi. Ushbu manipulyatsiyadan so'ng, tengsizlik belgisi teskari bo'ladi.

Keyinchalik, siz tengsizliklardan xalos bo'lishingiz kerak, buning uchun biz tengsizliklarning chap tomoniga kompensatsion o'zgaruvchilar kiritamiz. Agar ≤ ko'rinishdagi tengsizlik bo'lsa, kompensatsion o'zgaruvchi + belgisiga ega, agar tengsizlik ≥ ko'rinishdagi bo'lsa, kompensatsion o'zgaruvchi - belgisiga ega bo'ladi. Kompensatsion o'zgaruvchilar nol koeffitsientli muammoning maqsad funktsiyasiga kiritilgan.

E ndi cheklash tizimida etarli miqdordagi bazis o'zgaruvchilarni topish kerak. Har bir cheklov bitta asosiy o'zgaruvchiga ega bo'lishi kerak. Asosiy o'zgaruvchi bo'lib, u bilan 1 koeffitsientiga ega va faqat bitta cheklovda topiladi. Agar biron bir cheklashda bazis o'zgaruvchilari bo'lmasa, ularni sun'iy ravishda qo'shamiz va agar maqsad funktsiyasi max ga moyil bo'lsa va M, agar maqsad funktsiyasi minga moyil bo'lsa, sun'iy o'zgaruvchilar -M koeffitsienti bilan maqsad funktsiyaga kiradi.