Vazirligi muhammad al-xorazmiy nomidagi toshkent
Download 48.68 Kb.
|
2 lab 1 var - Copy - Copy (копия)
O'ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGIMUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI “Algoritmlarni loyihalash” fanidanLABARTORIYA ISHI Chiziqli dasturlash Oddiy usul. Oddiy jadval yordamida sodda usul yordamida chiziqli dasturlashning to'g'ridan-to'g'ri muammosini hal qilamiz. Maqsad funktsiyasining maksimal qiymatini aniqlang F (X) \ u003d 20x 1+23x 2+22x 3 quyidagi sharoitlarda-cheklovlar. 7x 1+5x 2+3x 3≤169 3x 1+4x 2+e6x 3≤139 2x 1 + 3x 2 + 5x 3≤106 birinchi mos yozuvlar rejasini tuzish uchun biz tengsizliklar tizimini qo'shimcha o'zgaruvchilarni kiritish orqali tenglamalar tizimiga keltiramiz (kanonik shaklga o'tish). 1-ma'no tengsizligida ( ≤ ) biz x 4 asosiy o'zgaruvchini kiritamiz. 2-ma'no tengsizligida ( ≤ ) biz x 5 asosiy o'zgaruvchini kiritamiz. 3-ma'no tengsizligida ( ≤ ) asosiy o'zgaruvchini kiriting x 6.7 x 1+5x 2+3x 3+x 4 = 169 3x 1+4x 2 + 6x 3 + x 5 = 139 2x 1+3x 2+5x 3 + x 6 = 106 koeffitsientlar matritsasi a = a (ij) ushbu tenglamalar tizimi shaklga ega:
Asosiy o'zgaruvchilar-bu cheklovlar tizimining faqat bitta tenglamasiga va bundan tashqari, birlik koeffitsientiga kiritilgan o'zgaruvchilar. Qo'shimcha o'zgaruvchilarning iqtisodiy ma'nosi: LP vazifalarining qo'shimcha o'zgaruvchilari ushbu optimal rejani ishlab chiqarishda qolgan ortiqcha xom ashyo, vaqt va boshqa resurslarni anglatadi. Asosiy o'zgaruvchilarga nisbatan tenglamalar tizimini echamiz: x 4, x 5, x 6 Erkin o'zgaruvchilar 0 ga teng deb hisoblasak, biz birinchi mos yozuvlar rejasini olamiz: X0 \ u003d (0,0,0,169,139,106) Asosiy echim, agar u salbiy bo'lmasa, maqbul deb nomlanadi.
Biz simplex usulining asosiy algoritmiga o'tamiz. Iteratsiya raqami 0. 1. Optimallik mezonini tekshirish. Amaldagi mos yozuvlar rejasi suboptimaldir, chunki indeks satrida salbiy koeffitsientlar mavjud. 2. Yangi asosiy o'zgaruvchini aniqlash. Taqdimotchi sifatida x 2 o'zgaruvchiga mos keladigan ustunni tanlang, chunki bu moduldagi eng katta koeffitsient. 3. Yangi erkin o'zgaruvchini aniqlash. D i qiymatlarini chiziqlar bo'yicha bo'linishning bir qismi sifatida hisoblaymiz: b i / a i2 va ulardan eng kichigini tanlaymiz: min (169 : 5 , 139 : 4 , 106 : 3 ) = 33 4/5 Shuning uchun 1-qator etakchi hisoblanadi. Ruxsat beruvchi element (5) ga teng va etakchi ustun va etakchi qatorning kesishmasida joylashgan.
4. Oddiy jadvalni qayta hisoblash. Biz simpleks jadvalning keyingi qismini shakllantiramiz. X 4 o'zgaruvchisi o'rniga x 2 o'zgaruvchisi 1-rejaga kiritiladi. 1-rejadagi x 2 o'zgaruvchiga mos keladigan satr 0-rejaning x 4 qatorining barcha elementlarini re \ u003d 5 hal qiluvchi elementiga bo'lish natijasida olinadi. Ruxsat beruvchi element o'rnida biz 1 ni olamiz. X 2 ustunining qolgan hujayralarida nollarni yozing. Shunday qilib, yangi 1-rejada x 2-qator va x 2-ustun to'ldirilgan. Yangi 1-rejaning boshqa barcha elementlari, shu jumladan indeks satrining elementlari to'rtburchaklar qoidasi bilan belgilanadi. Buning uchun eski rejadan to'rtburchakning yuqori qismida joylashgan va har doim re hal qiluvchi elementini o'z ichiga olgan to'rtta raqamni tanlang. Ne \ u003d SE - (A*C)/re ste - eski rejaning elementi, re - hal qiluvchi element (5) va va B - ste va re elementlari bilan to'rtburchaklar hosil qiluvchi eski rejaning elementlari. Keling, har bir elementning hisob-kitobini jadval shaklida taqdim etamiz:
Biz yangi oddiy jadvalni olamiz:
Iteratsiya raqami 1. 1. Optimallik mezonini tekshirish. Amaldagi mos yozuvlar rejasi suboptimaldir, chunki indeks satrida salbiy koeffitsientlar mavjud. 2. Yangi asosiy o'zgaruvchini aniqlash. Taqdimotchi sifatida x 3 o'zgaruvchiga mos keladigan ustunni tanlang, chunki bu moduldagi eng katta koeffitsient. 3. Yangi erkin o'zgaruvchini aniqlash. D i qiymatlarini chiziqlar bo'yicha bo'linishning bir qismi sifatida hisoblaymiz: b i / a i3 va ulardan eng kichigini tanlaymiz: min (33 4/5 : 3/5 , 3 4/5 : 3 3/5 , 4 3/5 : 3 1/5 ) = 1 1/18 Shuning uchun 2-qator etakchi hisoblanadi. Ruxsat beruvchi element (3 3/5) va etakchi ustun va etakchi qatorning kesishmasida joylashgan.
4. Oddiy jadvalni qayta hisoblash. Biz simpleks jadvalning keyingi qismini shakllantiramiz. X 5 o'zgaruvchisi o'rniga x 3 o'zgaruvchisi 2-rejaga kiritiladi. 2-rejadagi x 3 o'zgaruvchiga mos keladigan satr 1-rejaning x 5 qatoridagi barcha elementlarni re \ u003d 3 3/5 hal qiluvchi elementga bo'lish natijasida olinadi. Ruxsat beruvchi element o'rnida biz 1 ni olamiz. X 3 ustunining qolgan hujayralarida nollarni yozing. Shunday qilib, yangi 2-rejada x 3-qator va x 3-ustun to'ldirilgan. Yangi 2-rejaning barcha boshqa elementlari, shu jumladan indeks satrining elementlari to'rtburchaklar qoidasi bilan belgilanadi. Keling, har bir elementning hisob-kitobini jadval shaklida taqdim etamiz:
Biz yangi oddiy jadvalni olamiz:
1. Optimallik mezonini tekshirish. Indeks satrining qiymatlari orasida salbiy yo'q. Shuning uchun ushbu jadval muammoning optimal rejasini belgilaydi. Simpleks jadvalining yakuniy versiyasi:
Optimal rejani quyidagicha yozish mumkin: x 1 \ u003d 0, x 2 \ u003d 33 1/6, x 3 \ u003d 1 1/18 F(X) = 20*0 + 23*331/6 + 22*11/18 = 7861/18 Optimal rejani tahlil qilish. Optimal rejaga qo'shimcha x 6 o'zgaruvchisi kiritilgan. Shunday qilib, bunday rejani amalga oshirishda 1 2/9 miqdorida 3-turdagi kam ishlatilgan resurslar mavjud. 165/18 > 0 qiymati x 1 dan foydalanish foydali emasligini anglatadi. X 2 ustunidagi 0 qiymati x 2 dan foydalanish foydali ekanligini anglatadi. X 3 ustunidagi 0 qiymati x 3 dan foydalanish foydali ekanligini anglatadi. X 4 ustunidagi 2 7/9 qiymati soya narxi (ikki tomonlama ball) y 1=2 7/9 ekanligini bildiradi. X 5 ustunidagi 2 5/18 qiymati soya narxi (ikki tomonlama ball) y 2=2 5/18 ekanligini bildiradi. X 6 ustunidagi 0 qiymati soya narxi (ikkilik ball) y 3=0 ekanligini bildiradi. Eslatma: 1. Simpleks jadvallar qaysi usul bilan qayta hisoblanadi? To'rtburchak qoidasi qo'llaniladi (Iordaniya transformatsiyasi usuli). 2. Har safar indeks satridan maksimal qiymatni tanlash kerakmi? Siz tanlamasligingiz mumkin, ammo bu algoritmning aylanishiga olib kelishi mumkin. 3. N-ustundagi indeks satrida nol qiymat mavjud. Bu nimani anglatadi? Nol qiymatlar bazaga kiritilgan o'zgaruvchilarga mos kelishi kerak. Agar optimal rejaning sodda jadvalining indeks satrida bazaga kiritilmagan erkin o'zgaruvchiga tegishli nol bo'lsa va ushbu nolni o'z ichiga olgan ustunda kamida bitta ijobiy element bo'lsa, unda muammo juda ko'p optimal rejalarga ega. Belgilangan ustunga mos keladigan erkin o'zgaruvchini algoritmning tegishli bosqichlarini bajarish orqali bazaga kiritish mumkin. Natijada, boshqa asosiy o'zgaruvchilar to'plami bilan ikkinchi optimal reja olinadi. Download 48.68 Kb. Do'stlaringiz bilan baham: 
|