Butun sonli programmalashtirish

Mutaxassislar o‘rtasida turli xildagi ishlarni taqsimlash masalasi.

Belgilashlar kiritamiz:

i - mutaxassisning tartib nomeri;

j - bajaradigan ish nomeri;

Cij - j-nomerli ishni bajarish uchun i-nomerli mutaxassisning mehnat unumdorligi;

xij - j-nomerli ishni bajarish uchun i - nomerli mutaxassislar soni

Bu yerda, xij - j-nomerli ishni i - nomerli mutaxassislar bajarsa xij=1, bajarmasa xij=0 bo‘ladi.

Ishlab chiqarishni rejalashtirishni ikkilangan masalasining iqtisodiy-matematik modeli:

Maqsad funksiya:

Chegaraviy shartlar:

Butun sonli programmalashtirish masalasini umumiy holda quyidagi ko‘rinishda ifodalash mumkin.

Vektor shaklda:

Butun sonli programmalashtirish masalasining turlari:

Butun sonli sonli programmalashtirish masalalaridagi noma’lumlarning hammasi uchun butun bo‘lishlik sharti qo‘yoilsa, bunday masalalar to‘la butun sonli programmalashtirish masalasi deyiladi.

Noma’lumlarning ma’lum bir qismi uchun butun bo‘lishlik sharti qo‘yilsa, qisman butun sonli programmalashtirish masalasi deyiladi.

Noma’lumlar faqat 0 yoki 1 qiymatlarni qabul qilishi mumkin bo‘lsa, u holda bunday masala Bul programmalashtirish masalasi deyiladi.

Masala

Sexda qo‘shimcha uskuna o‘rnatishga qaror qabul qilinib, uning uchun 19/3 m2 maydon ajratildi. Bu uskunani sotib olish uchun 10 mimg so‘m pul sarf qilishi mumkin. Sex o‘z imkoniyatidan kelib chiqib 2 turdagi uskuna sotib olishi mumkin.

1-turdagi uskunaning bahosi 1000 so‘m, 2-turdagisining bahosi 3000 so‘m. 1- va 2-tur uskunalarning o‘rnatilishi oqibatida har smenada mos ravishda 2 va 4 birlik mahsulot ko‘proq ishlab chiqariladi. 1-tur uskunani o‘rnatish uchun 2 m2 2-tur uskuna uchun 1 m2 maydon kerak bo‘ladi.

Qaysi uskunadan qanchadan sotib olganda sexda ishlab chiqarilgan qo‘shimcha mahsulotlarning miqdori maksimal bo‘ladi.

Masalaning matematik modeli

1-tur uskunadan x1 dona, 2-tur uskunadan x2 dona sotib olsin.

OABC ko‘pburcha ichida berilgan butun sonli programmalashtirish masalasini yechimi bo‘la oladigan nuqtani toppish uchun bu ko‘pburchakni OKEMNF ko‘pburchak bilan almashtiramiz. Bu ko‘pburchak ichidan masalaga optimal qiymat beruvchi yechim qidiriladi.

Shakldan yechim E(1,3) nuqtadan iborat.

x1=1, x2=3, Ymax=14

Masalani geometrik talqini.

Butun sonli programmalashtirish masalasi yechish uchun unib bu xususiyatlarini e’tiborga oluchi usullar yaratilgan bo‘lib, ulardan biri amerikalik olim R.Gomori yaratgan.

Butun sonli programmalashtirish masalasi chiziqli programmalashtirish masalasidan xij=0 yoki xij=1 va xj>0, butun ko‘rinishdagi shrtlar bilan farq qiladi. Bu shartlar butun sonli programmalashtirish masalasini yechishni qiyinlashtiradi.

Masalani yechishning Gomori usulini asosiy g‘oyasi quyidagicha. Berilgan butun sonli programmalashtirish masalasida noma’lumlarning butun bo‘lishlik shartiga e’tibor bermasdan, ularni oddiy chiziqli programmalashtirish masalasi sifatida simpleks usuldan foydalanib yechamiz. Agar yechi butun sonlardan iborat bo‘lsa, u butun sonli programmalashtirish masalasining ham yechimi bo‘ladi. Aks holda noma’lumlarning butun bo‘lishlik shartini e’tiborga oluvchi va “kesuvchi tenglama” deb ataluvchi qo‘shimcha tenglama tuziladi.

Kesuvchi tenglamalar asosiy tenglamalar sistemasiga qo‘shib yoziladi va basis yechim almashtiriladi. Buning uchun noma’lumni kesuvchi tenglamadan ajratiladi va uning qiymatini boshqa tenglamalarga qo‘yib chiqiladi. Bunday ishlar masalaning butun sonli yechimi topilguncha yoki uning mavjud emasligi aniqlanguncha davom ettiriladi.