Muhammad Al-Xorazmiy nomdagi Toshkent Axborot-Texnologiyalari universiteti Algoritmlarni loyihalash fanidan

Chiziqli dasturlash masalasining umumlashgan matematik modeli
1) Ikkitadan ortiq o'zgaruvchini o'zida mujassam etgan har qanday Ch.D.M quyidagicha ifodalanishi mumkin: x₁, x₂, .., x_n o'zgaruvchilarda funktsiyaning maksimal (yoki minimal) qiymatini topuvchi maqsad funksiyasi
Z = c₁x₁ + c₂x₂ +..+ c_nx_n
Chegaraviy shartlar esa

Va o’zgaruvchilarning manfiy bo’lmaslik sharti

CH.D.M.ning chegaralarini qanoatlantiradigan x₁, x₂, .., x_n qiymatlari to'plami uning yechimi deyiladi.
CH.D.M.ning manfiy bo’lmagan, shartlarini qanoatlantiradigan har qanday yechimi uning mumkin bo'lgan yechimi deb ataladi.
CH.D.M.ning maqsad funksiyasini maksimal (yoki minimal) qiymatga erishtiradigan yechim uning optimal yechimi deb ataladi.
2) Chiziqli dasturlash masalasining umumlashgan matematik modeli formasining yozilishi quyidagi ko‘rinishga ega.
(1)
(2)
(3)
Matematik modelning birinchi formulasi izlananayotgan miqdorlarga qo‘yiladigan cheklanishlarni ifodalaydi, ular resurslar miqdori, ma’lum talablarni qondirish zarurati, texnologiya sharoiti va boshqa iqtisodiy hamda texnikaviy faktorlardan kelib chiqadi. Ikkinchi shart - o‘zgaruvchilarning, ya’ni izlanayotgan miqdorlarning manfiy bo‘lmaslik sharti bo‘lib hisoblanadi.
Uchinchisi maqsad funksiyasi deyilib, izlanayotgan miqdorning biror bog‘lanishini ifodalaydi.


Misol 2.
Ishlab chiqaruvchi ikki turdagi M₁ va M₂ mahsulotlarni ishlab chiqaradi. M₁ mahsuloti ni ishlab chiqarishda 4 soat silliqlash va 2 soat bo’yash talab qiladi; har bir M₂ mahsulotida 2 soat silliqlash va 5 soat bo’yash talab etiladi. Ishlab chiqaruvchining 2 ta silliqlash va 3 bo’yash mashinasi mavjud. Har bir silliqlash mashinasi haftasiga 40 soat harakat qiladi va har bir bo’yash mashinasi haftasiga 60 soat harakat qiladi. M₁ mahsuloti bo'yicha olingan daromad 3 dollar, M₂ mahsulotida esa 4 dollar turadi. Bir hafta ichida ishlab chiqariladigan mahsulot bozorda sotiladi. Ishlab chiqaruvchi o'zining ishlab chiqarish quvvatini ikki turdagi mahsulotlarga taqsim qilib, u bir hafta ichida maksimal foydani amalga oshirishi kerak.
Masalaning matematik modeli.
X₁ - M₁ mahsulotlari soni va x₂ har hafta ishlab chiqarilgan M₂ mahsulotlarining soni. Haftalik foyda
Z = 3x₁ + 4x₂ (I) maqsad funksiyasi bilan aniqlanadi
Mahsulotlarni ishlab chiqarish uchun haftada mahsulotlarni silliqlashning umumiy vaqti talab qilinadi
= 4x₁ + 2x₂
va haftada talab etiladigan bo’yash soatlarining umumiy soni
= 2x₁ + 5x₂
Mavjud silliqlash soatlar soni 80 dan oshmaganligi va bo’yash soatlari soni 180 dan oshmaganligi sababli
4x₁ + 2x₂ 80 (II)
2x₁ + 5x₂ 180 (III)
Bundan tashqari, mahsulotlarning manfiy soni ishlab chiqarilmagani uchun, albatta,
x1 0 va x2 0 (IV)
bo'lishi kerak
Shuning uchun bu taqsimlash masalasi - x1, x2 ni topishdir
Z = 3x1 + 4x2 maksimum
Maqsad funksiya va chegaraviy shartlar barchasi chiziqli bo'lib, bu chiziqli dasturlash masalasidir.