Sharof rashidov nomidagi samarqand davlat universiteti
Shimoliy-g‘arb burchak usuli
Yüklə 0,5 Mb.
|
- Bu səhifədəki naviqasiya:
- Simpleks usuli
|
Shimoliy-g‘arb burchak usuli
„Shimoliy-g'arb burchak" usulining umumiy qoidasi quyidagilardan iborat. Eng awal dastlabki berilganlarning jadvalidan „Shimoliy-g'arbida joylashgan x11 no'malum ning qiymatini aniqlaymiz": Agar birinchi hoi bajarilsa, birinchi qadamdan so'ng masalaning yechimlaridan tashkil topgan matritsa quyidagi ko'rinishda bo'ladi: Endi ikkinchi qatordagi birinchi elementni topamiz. Bu yerda ham ikki hol bo'lishi mumkin: Agar bu yerda ham birinchi hoi bajarilsa, u holda ikkinchi qadamdan so'ng yangi matritsa quyidagi ko'rinishda bo'ladi: Bu jarayon qadam-baqadam barcha ai va bj lar nolga aylanguncha davom ettiriladi. Ma’lumki, har bir x. ning qiymati a va b} laming turli kombinatsiyalarini ayirish yoki qo'shish yordamida topiladi. Shundan keyin (3.2) formula orqali transport xarajatlari hisoblanadi. Simpleks usuli Faraz qilaylik, masalaning boshlang‘iya tayanch plani, shu planga mos keluvchi o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar sistemasi bo‘lsin. Bu vektorlardan tashkil topgan ( ) matritsani V bilan belgilaymiz. U holda Bundan va kelib chiqadi. Bu yerda vektor ustunlar. Simpleks jarayoni boshlashdan avval masalaning vektorlarini quyidagidek gruppalaymiz: yoki (30) Elementlari ayrim qismlardan iborat bo‘lgan (30) matritsani ga ko‘paytiramiz va quyidagiga ega bo‘lamiz: yoki So‘ngra har bir uchun ni hisoblaymiz. Agar barcha lar uchun bo‘lsa, 2-teoremaga asosan topilgan tayanch plan optimal plan bo‘ladi. Agar ayirma ba’zi lar uchun musbat bo‘lsa, 1-teoremaga asosan topilgan tayanch plan optimal plan bo‘lmaydi, bu planni optimal planga yaqin bo‘lgan boshqa plan bilan almashtirish kerak bo‘ladi. Berilgan masalada dastlabki vektorlar - o‘lchovli vektor fazodagi bazisini tashkil qilsin, ya’ni bo‘lsin, bu yerda - o‘lchovli birlik matritsa. Bu holda bo‘lganligi sababli va bo‘ladi. Masalaning berilganlarini quyidagi ko‘rinishdagi jadvalga joylashtiramiz. Chiziqli sistemasi ko‘rinishda berilgan masala uchun deb qabul qilamiz. 1-jadval. Hisoblarning birinchi iteratsiyasi.
vektor – ustunni vektor – ustunga skalyar ko‘paytmasidan iborat, ya’ni va larni jadvalning qatoridagi tegishli ustunlarga joylashtiramiz. Bazis vektorlar uchun har doim bo‘ladi. Agar bo‘lsa, optimal plan bo‘ladi. Bu plandagi chiziqli funksiyaning qiymati ga teng. Endi kamida bitta uchun bo‘lsin deb faraz qilaylik. Bu holda topilgan tayanch planni optimal planga yaqinroq plan bilan almashtirish kerak, buning uchun shartni qanoatlantiruvchi vektorni bazisga kiritib, bazisdan shartni qanoatlantiruvchi vektorni chiqarish kerak bo‘ladi. Yangi plan uchun vektorlar bazis vektorlar bo‘ladi. Yangi tayanch planni hosil qilish va uning optimal plan ekanligini tekshirish uchun va vektorlarning bazis vektorlar orqali yoyilmasini hosil qilish kerak. Dastlabki bazis vektorlardan tuzilgan matritsa birlik matritsadan iborat edi, ya’ni Shuning uchun (31) (32) (33) (32) dan: . (34) ning bu qiymatini (31) ga qo‘yamiz, natijada quyidagiga ega bo‘lamiz: yoki Shunday qilib, yangi tayanch plan quyidagi formulalar orqali hisoblanadi: (35) Xuddi shuningdek, (34) ni (33) ga qo‘yib vektorning yangi bazis vektorlar bo‘yicha yoyilmasini hosil qilamiz: bu yerda (36) (35) va (36) ni birlashtirib, lar uchun yangi tayanch planni va vektorlarning yangi bazis vektorlar bo‘yicha yoyilmasi formulasini hosil qilamiz: (37) Bu formula esa Jordan-Gaussning to‘la ajratish formulasidan iboratdir. Haqiqatan ham, da yangi bazisga kiritilayotgan vektorning ga (bundan keyin bu elementni aniqlovchi element deb ataymiz) mos keluvchi elementi 1 ga teng bo‘lib, qolgan elementlari 0 ga teng bo‘ladi. yangi plan uchun bo‘lganligi sababli, (36) dan foydalanib quyidagi ifodani hosil qilamiz: (38) xudi shuningdek, ning qiymatini (35) dan ifodaga qo‘yib, (39) ni topamiz. Yuqoridagilardan xulosa qilib aytganda, simpleks jadval ustida tartib bilan quyidagi ishlarni bajarish kerak: 1. Har bir uchun lar tekshiriladi. Agar barcha lar uchun bo‘lsa, topilgan plan optimal plan bo‘ladi. 2. Agar birorta uchun bo‘lsa, bazisga kiritiladigan vektor tanlanadi. Bazisga shartni qanoatlantiruvchi vektor kiritiladi; 3. Bazisdan chiqarilishi kerak bo‘lgan vektor aniqlanadi. Bazisdan ga mos keluvchi vektor chiqariladi. Agar vektorga mos keluvchi barcha bo‘lsa, chiziqli funksiya quyidan chegaralanmagan bo‘ladi; 4. Aniqlovchi element tanlangandan so‘ng simpleks jadval (37) formula orqali almashtiriladi. Shunday yo‘l bilan har bir iteratsiyada yangi tayanch plan topiladi. 1 va 2 – teoremaga asosan simpleks usul yo optimal planni beradi, yoki masaladagi chiziqli funksiyaning chekli minimumga ega emasligini aniqlaydi. 1-misol.
Yechish. Masalada o‘zaro chiziqli bog‘liq bo‘lmagan vektorlar berilgan. Ularni bazis vektorlar deb qabul qilamiz. Bu bazis vektorlarga plan mos keladi. Bu planda chiziqli funksiyaning qiymati bo‘ladi. Simpleks jadval tuzamiz: 1-i t ye r a s i ya
Jadvalning 4-qatoriga va larning qiymatini yozamiz. bo‘lganligi sababli bazisga vektorni kiritamiz va bo‘lganligi sababli bazisdan vektor chiqariladi. Shunday qilib aniqlovchi element bo‘ladi. Simpleks jadvalni (37), (38), (39) formulalar yordami bilan almashtiramiz, natijada quyidagi yangi jadvalga ega bo‘lamiz: 2-i t ye r a s i ya
Yangi simpleks jadvalda Shuning uchun bazisga vektor kiritiladi. demak, bazisdan vektor chiqariladi, aniqlovchi element bo‘ladi. Simpleks jadvalni (37), (38), (39) formulalar yordami bilan almashtirib yana keyingi yangi simpleks jadvalni hosil qilamiz. 3-i t ye r a s i ya
Bu simpleks jadvaldan ko‘rinib turibdiki, barcha lar uchun . Demak topilgan plan optimal plan bo‘lib, bu plandagi chiziqli funksiyaning qiymati ga teng. Yüklə 0,5 Mb. Dostları ilə paylaş:
|