Chiziqli programmalash masalasini yechishning Simpleks usuli

Mavzu: Chiziqli programmalash masalasini

yechishning Simpleks usuli.



Reja

1.Simpleks usul haqida qisqacha umumiy maʼlumot

2.Simpleks usulning algoritmi

3.Baʼzi iqtisodiy masalalarni simpleks usul yordamida yechish

4.Mustaqil yechish uchun tavsiya qilingan misollar

1.Biz bilamizki chiziqli programmalash masalasi bu chiziqli funktsionalni koʻp oʻlchovli fazoda chiziqli cheklovlarni qanoatlantirgan holda minimum yoki maksimum qiymatini topishdan iborat. Bu masaladagi har bir chiziqli cheklovlar n- oʻlchovli fazoni (n-1)- oʻlchovli yarim fazosi boʻladi, demak bundan chiqadiki barcha chiziqli cheklovlarni umumiy yechimi (mumkin boʻlgan rejalar toʻplami) n- oʻlchovli fazoda qavariq koʻpyoq boʻladi. Optimal yechim esa mavjud boʻlsa, u faqatgina shu koʻpyoqning uchlaridan birida boʻladi.

Simpleks usul chiziqli programmalash masalasini mumkin boʻlgan rejalar toʻplami boʻlgan koʻpyoqni uchlari orasidan optimal yechimni topish usulidir. Agar masalani oʻzgaruvchilar soni n-ta cheklovlar soni m-ta boʻlsa u holda tayanch rejalar (koʻpyoqning uchlari) soni Сnm– ga teng boʻladi, bu yesa katta son boʻlib, bularni birma-bir tekshirib chiqish maqsadga muvofiq emas.

2. Quyidagi ishlab chikarishni rejalashtirish masalasini ko'raylik: Korxona n -xil mahsulot ishlab chiqaradi. Bu mahsulotlarni ishlab chiqarish uchun korxona oʻz ixtiyoridagi m -ta resurslardan (xomashyo, ishchi kuchi, elektr energiyasi va hakozo) foydalanadi. Har bir resursning zaxirasi (zapasi) ; har bir mahsulot birligini ishlab chiqarish uchun sarf qilinadigan har bir resursning miqdori (sarf normalari) ; har bir mahsulot birligini sotishdan olinadigan daromad сj -lar (i=1,2,…,m; j=1,2,…,n) maʼlum boʻlsin.

Ishlab chiqarish rejanini shunday tuzish kerakki, unda sarf qilingan resurslar miqdori, berilgan zaxiralar miqdorlaridan ortmasin va hamma ishlab chiqarilgan mahsulotlarni sotishdan olinadigan daromad eng koʻp boʻlsin.