12-mavzu. Butun sonli chiziqli programmalashtirish masalasi ma’ruza mashg’uloti rejasi

12-MAVZU. BUTUN SONLI CHIZIQLI PROGRAMMALASHTIRISH MASALASI
MA’RUZA MASHG’ULOTI REJASI:
12.1. Butun sonli chiziqli programmalash masalasini yechish.
12.2. Jihozlarni almashtirish va ta’mirlash


Tayanch so’z va iboralar: loyiha, jarayon, tadqiqot, maqsad funksiya, hisoblash, ma`lumotlar, zahira, harajatlar, bosqichlar, qavariq, tengsizlik, optemal, algoritm, funksiya, minimal, maksimal, marshurut, effiktiv, mahsulot, chiziqli, tarmoqlar, chegaralar, to‘la axborotli, strategiya, anta­go­nis­tik o‘yinlar, o‘yinning normal shakli.


12.1. Butun sonli chiziqli programmalash masalasini yechish.

Biz quyida chiziqli programmalash masalasini qo‘yilishi bilan shug‘ullanamiz. Agar o‘zgaruvchilarga yana qo‘shimcha shart: barcha o‘zgaruvchilarni yoki ularn ing bir qismini butunligi talab qilinsa, biz mos ravishda to‘la butun sonli yoki qisman butun sonli chiziqli programmalash masalasi (BSChP) ga kelamiz. Shunday qilib BSChP masalasi quydagicha: ushbu

(1)
(2)
(3)

shartlar ostida

(4)
funksiyaning ekstremumi topilsin.
Biz bundan keyin, aniqlik uchun (4) maqsad funksiyani maksimumga tekshiramiz.
(1)- (4) masalada (1)- (3) shartlarni qanoatlantiruvchi vektorlar joiz yechimlar deb ataladi. Maqsad funksiyaga maksimum qiymat beruvchi joiz yechim optimal yechim deyiladi.
Yuqorida, ko‘rib chiqilganidek, bu yerda ham (1)- (4) masalani kanonik va diagonal formaga keltirish mumkin


-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.



Ta’kidlab o‘tamizki, bunda masalani to‘la yoki qisman butunlik sharti o‘zgarmaydi. Endi BSChP masalasiga doir bir nechta misollarni ko‘rib chiqaylik.
I-misol. Daryo paraxodchilik boshqarmasi shuni aniqladiki, n ta marshrutning har bir marshruti bo‘yicha sezon davomida o‘rtacha sondagi pasajirlar yurar ekan. Transport vositasini ishlatilish samaradorligi har bir marshrut bo‘yicha ishlatilish samaradorliklar yig‘indisidan iborat bo‘lib, ularning har biri o‘z navbatida mos reysdan keladigan foyda bilan reysga ketgan harajat ayirmasiga teng.
Foyda sotilgan biletlar soni bilan, xizmatchilarga ketgan haq va yoqilg‘i uchun ketgan sarflar orqali aniqlanadi. Qaysi marshrutga qanday turdagi kemadan nechtadan ajratilsa, pasajirlar talabi to‘la qondiriladi va keladigan foyda maksimal bo‘ladi?
Faraz qilaylik,j- marshrut bo‘yicha sezon davomida b¹_j ta passajir qatnasin: Bu marshrutda 1,2,...,m turdagi kemalardan foydalanish mumkin va har bir i -tipdagi kema uchun quydagi ko‘rsatkichlar ma’lum:
1) a_i1 -yuk ko‘tarishlik (o‘rinlar soni);
2) a_i2 -xizmat ko‘rsatuvchilar soni;
3) a_i3 -sezon davomida sarflanadigan yoqilg‘i miqdori;
4) c_ij-j marshrut bo‘yicha i- turdagi bitta kema ishlatilgandagi cheklanishlar quyidagicha bo‘ladi.
5) Sezon davomida ishlatiladigan yoqilg‘i miqdori b₁ dan, xizmat ko‘rsatuvchilar soni esa b₂ dan oshmasin. x_ij j- marshrutdagi i-turdagi kemalar sonini bildirsin. U holda, shartga ko‘ra cheklanishlar quyidagicha bo‘ladi


butun
Masalani qo‘yilishiga asosan, shu berilgan soxada shunday vektorlarni topish kerakki, u

funksiyaga maksimal qiymat bersin.
2-misol. Faraz qilaylik n ta turli turdagi samolyotlar bo‘lib, ularni n ta yo‘nalish bo‘yicha taqsimlash lozim.
Agar i - turdagi samalyot j -yo‘nalishga qo‘yilsa, bundan keladigan foyda c_ij ga teng. Samolyotlarni yo‘nalishlarga shunday taqsimlash kerakki, natijaviy foyda maksimal bo‘lsin.
Bu masalani yechish uchun quydagicha x_ij o‘zgaruvchilar kiritamiz

U holda, biz quydagi BSChP masalasiga kelamiz:
1. (har bir yo‘nalishga bitta samolyot tayinlanadi):
2. (har bir samolyot faqat bitta yo‘nalishga tayinlanadi)
shu shartlar ostida

funksiyaning maksimumini toping.
Ma’lumki, o‘zgaruvchi faqat ikkita 0 va 1 qiymatlarni qabul qilsa, bunday o‘zgaruvchi bul o‘zgaruvchisi deyiladi. Shunga asosan, bunday o‘zgaruvchisi bo‘lgan masalalar bul masalalari deb yuritiladi. Biz ko‘rgan 2-masala xuddi shunday masalalardan biridir.