Reja Chiziqli dasturlash masalasining qo’yilishi. Maqsad funksiyasini tuzish bo’ladi odatda m

Chiziqli dasturlash masalasi

• Fabrika ikki xil M1 va M2 tikuv mahsuloti ishlab chiqaradi. Bu mahsulotlarni ishlab chiqarishda uch xil N1,N2,N3 turdagi materiallarni ishlatadi. N1-materialdan 15 m., N2-materialdan 16 m., N3-materialdan 18 m. mavjud. M1- mahsulotni ishlab chiqarish uchun N1-dan 2m., N2-dan 1m., N3-dan 3m. ishlatadi. M2- mahsulotni ishlab chiqarish uchun N1-dan 3m., N2-dan 4m., N3-dan 0m. ishlatadi. M1- mahsulotning bir birligidan keladigan foyda 10 so‘mni, M2 - mahsulotdan keladigan foyda 5 so‘mni tashkil qiladi. Ishlab chiqarishning shunday planini tuzish kerakki fabrika maksimal foyda olsin. Masalaning matematik modelini tuzamiz:

• Bu yerda M1 mahsulotni x1 va M2 mahsulotni x2 o’zgaruvchi bilan almashtirib olamiz.
• Bu yerda Z=10x1+5x2 -> max maqsad funksiyasi bo’lib, x1 va x2 larning shatrlarni bajarilgan qiymatlarida Z ning maksimumga erishishini ta’minlash masalasi qaraladi.

Misol .

• Misol .
• Z = 2x + 3y maqsad funksiyasining maksimum qiymatini toping.
• Chegaraviy shartlar quyidagicha berilgan:
• x + y 30, y 3, 0 y 12, x - y 0, va 0 x 20.
•  
• Yechish
• Birinchi navbatda koordinatalar sistemasida x0, y 0 ekanligini belgilab olamiz.
• Koordinatalar sistemasida x + y 30, y 3, y 12, x y va x 20, chegaralarni belgilab, ABCDE shaklni aniqlaymiz.
• Shakl uchlaridagi nuqtalar A(3, 3), B (20, 3), C(20, 10), D(18, 12) va E(12, 12) bo’ladi.
• Shakl uchlaridagi Z ning qiymatlari Z(A) = 15, Z(B) = 49, Z(C)= 70, Z(D)=72, va Z(E) = 60
• D nuqtada Z maksimum qiymatga erishadi. Z(D)=72. Bu nuqtada x va y ning qiymatlari x = 18, y = 12 ga teng.

•  

Asosiy adabiyotlar
1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы построение и анализ. Москва-Санкт-Петербург- Киев. Изд. дом “Вильямс”, 2005. 1293 стр.
2. Levetan Anany. Introduction to The Design & Analisis of Algorithms. 3rd ed. Villanova university.New Jersiy. 2012. 693 page.
3. Род Стивенс. Готовые алгоритмы. М.: ДМК Пресс. Питер 2014. 384 стр.
4. Стивен Скиены. Алгоритмы. Руководство по разработке. Питер 2011. 715 стр.
Qo’shimcha adabiyotlar
1. Computer Algorithms by Horowits E., Sahni., Rajasekaran S., Galgotia Publications, 2001.