Simpleks usuli algoritmi - Dasturiy injiniringi

|
Dasturiy injiniringi
|
bet | 4/8 | Sana | 23.05.2024 | Hajmi | 5,58 Mb. | | #251216 |
Bog'liq Samatova Zarnigor NematovnaSimpleks usuli algoritmi:
Masala. 3 turdagi qishloq xo‘jalik mahsulotini etishtirish uchun 3 turdagi (R1 ,R2 , R34) resurs talab qilinsin. Bu erda R1 -ekin maydoni, R2 - meqnat xarajatlari, R3 -solinadigan o‘ѓitlarning miqdori. Shartlarni aniq ifodalashda foydalaniladigan dastlabki axborotlar 1-jadvalda keltirilgan.
1-jadval
Har bir ishlab chiqariladigan mahsulotning shunday rejasini tuzish kerakki, natijada eng ko‘p foyda olinsin. Masalaning matematik modelini chiziqli programmalashtirish masalasiga olib kelib tuzamiz. X1, X2, X3 lar orqali I1, I2, I3 tur ishlab chiqarishlardagi maksimal foyda beruvchi izlanayotgan mahsulot miqdorini belgilaymiz.
Har bir mahsulotni ishlab chiqarish uchun sarf qilingan resurslar mavjud resurslarning zahirasidan oshib ketmasligi kerak, y’ani
Maqsad funksiyani quyidagicha yozamiz.
Ishlab chiqarish hajmi manfiy bo‘lmasligi kerak:
Bu masalani Simpleks jadval usulida yechish uchun yuqoridagi tengsizliklar sistemasini kanonik shaklga keltiramiz. Buning uchun har bir tengsizlikka manfiy bo‘lmagan yangi noma’lum miqdorlar (X4 , X5 , X6 )ni kiritamiz. Bular ishlatilmasdan yotgan resurslar miqdori.
Qo‘shimcha o‘zgaruvchilarni maqsad funksiyaga ham qo‘shish kerak. Bu o‘zgaruvchilar maqsad funksiyaga nol koeffitsient bilan qo‘shiladi.
Kanonik ko‘rinishdagi masalaning elementlaridan foydalanib, quyidagi tartibda 1-dastlabki jadvalni tuzamiz.
Kanonik ko‘rinishdagi masalaning elementlaridan foydalanib, quyidagi tartibda 1-dastlabki jadvalni tuzamiz:
Bu yerda i-cheklanish tartibi; Xbi -bazis o‘zgaruvchilar(bular 1-simpleks jadvalda qo‘shimcha o‘zgaruvchilar); Ci - maqsad funksiyadagi bazis o‘zgaruvchilar oldidagi koeffitsientlar; ai0 - ozod hadlar; aij - tenglamadagi koeffitsientlar: Cj - maqsad funksiya koeffitsientlari, jumladan C0 - maqsad funksiyaning ozod hadi bo‘lib, ko‘pchilik masalalarda bu nolga teng bo‘ladi.
Keyingi jadvalga o‘tish mumkinmi yoki yo‘qligini simpleks jadvalning indeks qatori ko‘rsatadi bitta manfiy element qatnashsa ham (masala maksimumga echilayotgan bo‘lsa) yoki bitta musbat element qatnashsa ham (masala minimumga echilayotgan bo‘lsa) keyingi jadvalga o‘tish mumkin.
1. Indeks qatorda absolyut qiymati bo‘yicha eng katta bo‘lgan manfiy element (masala maksimumga echilayotgan bo‘lsa) yoki absolyut qiymati eng katta musbat elementni (masala minimumga echilayotgan bo‘lsa) topish kerak.
2. Nolinchi ustunning elementlarini asosiy ustunning mos musbat elementlariga bo‘lib chiqamiz.
3. Eng kichik bo‘linma turgan qator asosiy qator hisoblanadi. Bizning misolimizda birinchi bosqichda ikkinchi qator asosiy qator hisoblanadi, chunki barcha qiymatlarning ichida eng kichigi.
Eng kichik bo‘linma turgan qator asosiy qator hisoblanadi. Misolda birinchi bosqichda ikkinchi qator asosiy qator hisoblanadi, chunki barcha qiymatlarning ichida eng kichigi
ga teng ekan. Asosiy ustun va asosiy satr kesishmasida turgan element asosiy element deb aytiladi.
3. Bazis o‘zgaruvchilarning ayrimlarini almashtirish kerak. Buning uchun asosiy qatorda turgan elementning o‘rniga (bu erda -X5 ) nomeri asosiy ustun nomeriga teng bo‘lgan (X3 ) o‘zgaruvchini kiritish kerak.
4.Asosiy qator (aas.j) da turgan elementlarning yangi qiymatlarini hisoblash kerak. bu yerda -asosiy qatorning avvalgi qiymatlari, -asosiy element qiymati. Natijada asosiy element 1 ga teng bo’lgan qiymatni qabul qiladi.
5. a'ij - ning boshqa qatorlardagi va indeks qatoridagi qiymatlarini quyidagi formula orqali hisoblaymiz: (barcha i as.lar uchun) bu yerda aiac-asosiy ustunda turgan yangi hosil bo’layotgan qator elementlari, a'acj-hosil bo’layotgan qator elementlariga mos turgan ustundagi hosil bo’lgan yangi qatorning elementlari. Natijada asosiy ustunning asosiy elementidan tashqari hamma elementlar nol qiymatlarni qabul qiladi.
Yangi hosil bo‘lgan jadvalning ko‘rinishi 2 – simpleks jadvalda keltirilgan.
|
| |