4-ma’ruza. Butun sonli chiziqli dasturlash. Gomorining kesuvchi tekisliklar usullari Reja

Misol. Sexda qo’shimcha uskuna o’rnatishga qaror qabul qilinib, uning uchun 19/3 m² maydon ajratildi. Bu uskunani sotib olish uchun sex 10 ming so’m pul sarf qilishi mumkin. Sex o’z imkoniyatidan kelib chiqib 2 turdagi uskuna sotib olishi mumkin. 1-turdagi uskunaning bahosi 1000 sum, II-turdagisining bahosi esa, 3000 so’m turadi.
I va II tur uskunaning o’rnatilishi oqibatida har smenada sex mos ravishda 2 va 4 birlik mahsulot ko’proq ishlab chiqaradi. I tur uskunani o’rnatish uchun 2 m², II tur uskuna uchun esa 1 m² maydon kerak. qaysi uskunadan qanchadan sotib olinganda sexda ishlab chiqarilgan qo’shimcha mahsulotlarning miqdori maksimal bo’ladi?
Yechish. Sex I-tur uskunadan x₁ dona, II-tur uskunadan dona sotib olsin, deylik. U holda masalani shartlari quyidagi tengsizliklar sistemasi orqali ifodalanadi.

butun.
Masalaning maqsadi ishlab chiqarilgan qo’shimcha mahsulotlar miqdorini maksimal qilishdan iborat bo’lib, u quyidagi funksiya ko’rinishida yoziladi.

Shunday qilib, berilgan masalaning matematik modeli quyidagi ko’rinishga ega bo’ldi.
(14)
, (15)
(16)
(17)


2. Butun sonli dasturlash masalasining qo’yilishi, turlari va geometrik talqini

Butun sonli dasturlash masalasini umumiy holda quyidagi ko’rinishda ifodalash mumkin:

(18)
butun (19)
(20)
yoki vektor formada
(21)
va butun (22)
(23)
Butun sonli dasturlash masalalaridagi noma’lumlarning hammasi uchun butun bo’lishlik sharti qo’yilsa, bunday masalalar to’la butun sonli dasturlash masalalari deb ataladi.
Noma’lumlarning ma’lum bir qismi uchun butun bo’lishlik sharti qo’yilgan masalalar qisman butun sonli dasturlash masalalari deb ataladi.
Agar butun sonli dasturlash masalasidagi noma’lumlar faqat 0 yoki 1 qiymatlarni qabul qilishi mumkin bo’lsa, u holda bu masala Bul dasturlash masalasi deb ataladi.
Butun sonli dasturlash masalasining geometrik talqini bilan tanishamiz. Buning uchun 1-bandda keltirilgan (14) – (17) masalani grafik usulda yechish jarayonini tasvirlaymiz. Eng avval masalaning (14) va (15) shartlarini qanoatlantiruvchi yechimlar to’plamidan iborat bo’lgan qavariq ko’pburchakni yasaymiz (1-shakl).

1-shakl.

ko’pburchakning nuqtalari ichida berilgan butun sonli dasturlash masalasining yechimi bo’la oladigan nuqtani topish uchun bu ko’pburchakni ko’pburchak bilan almashtiramiz. ko’pburchak koordinatalari butun sonlardan iborat bo’lgan nuqtalarni o’z ichiga oladi va uning burchak nuqtalarining koordinatalari butun sonlardan iborat bo’ladi.
Endi (17) funksiyaga maksimum qiymat beruvchi nuqtani ko’pburchakning burchak nuqtalari ichida kidiramiz. Bu ko’pburchakning nuqtalari ichida (17) funksiyaga maksimum qiymat beruvchi nuqta berilgan masalaning optimal yechimini aniqlaydi. Bunday nuqtani topish uchun ga ixtiyoriy, masalan, 12 qiymat beramiz va

to’g’ri chiziqni yasaymiz. Bu chiziqni vektor yo’nalishida ko’pburchakning shu yo’nalishidagi chetki nuqtasi bilan kesishguncha siljitib boramiz. Ana shu burchak nuqtaning koordinatalari berilgan masalaning yechimini aniqlaydi, maqsad funksiyaning shu nuqtadagi qiymati esa maksimal bo’ladi. Shakldan ko’rinadiki, bunday nuqta dan iborat. Demak berilgan masalaning yechimi:

bo’ladi.