Tanlov masalasining qo'yilishi. Mak usuli

Tanlov masalasining qo'yilishi. Mak usuli Reja: Tanlov masalasining qo'yilishi. Transport masalasining amaliy masala misolida matematik modeli. Tanlov masalasining o'ziga xos xususiyatlari. Mak usuli mohiyati. Mak usulini amaliy misolni yechish bilan tushuntirish. Tanlov masalasi transport masalasi kabi chiziqli programmalash masalasiga kiradi, lekin u maxsus ko'rinishga ega. Xususan, chekliklardagi koeffitsiyentlar 0 yoki 1 koeffitsiyentga ega, har bir o'zgaruvchi esa faqat ikkita cheklikda ishtirok etadi. Mazkur mavzuda o'rganiladigan masala trasport masalasining tanlov xarakteriga ega bo'lgan xususiy ko'rinishidir. Bu usulning mohiyatini quyidagi masalaning mazmuniga bog'lab tushuntiramiz. R1, R2,, R5 - raqamli 5 kishi t1, t2,, t5 raqamli topshiriqlarni bajara oladi. Kasbiy mahoratiga bog'liq ravishda bu topshiriqlarni bajarish uchun har xil vaqt miqdori kerak. Odamlarni topshiriqlar bo'yicha shunday taqsimlash kerakki, natijada vaqt miqdori eng kam sarflansin. Vaqt miqdori soatlarda jadvalda keltirilgan. Xij - i - odamning j - topshiriqni bajarishi uchun ketgan vaqti. Masalaning matematik modeli quyidagi shartlardan iborat. Xij- manfiymas son, chunki har bir odam ishga to'la ishtirok etishi, har bir topshiriq to'la bajarilishi kerak, yani Xij- miqdor quyidagi shartlarga javob berishi kerak. Shu shartlarning bajarilishida jami sarflanadigan vaqt eng kichik songa teng bo'lishi kerak: Bu yerda bij - i- odamning j- topshiriqni bajarish uchun sarflaydigan ish vaqti. Shunday qilib, bu chiziqli programmalashning masalasi transport turiga ega. Chunki satrlar va ustunlar bo'yicha yig'indilar 1 ga teng. U ifodalangan, shuning uchun transport masalasini yechish algoritmini bu masalani yechish uchun ham qo'llash mumkin, lekin u samarali emas. Chunki masalaning optimal butun qiymatli yechimining beshtasi Xij = 1 qolganlari 0 bo'ladi. Boshqa tomondan karaganda esa 55 o'lchamdagi vaqt matritsasida har bir ustun va har bir satrdan bittadan shunday beshta elementni topish kerakki, natijada tanlangan elementlar yig'indisi minimum bo'lsin. Xij - ning 0 yoki 1 ga teng bo'lishi, bazi bir hollarda masala qo'yilishiga mano berish uchun zarur. Masalani nn o'lchamdagi matritsa uchun umumlashtirish mumkin. Har bir bunday matritsa uchun masalada har bir satr va har bir ustundan bittadan n ta elementni tanlash kerakki, ularning yig'indisi eng kichik bo'lsin. Tanlangan elementlarni X1i, X2j,, Xnt deb belgilaymiz. Bu yerda i, j,, t - 1, 2,, n - elementlarning bazi bir o'rin almashtirishidir. Bunday o'rin almashtirishlar n ta bo'ladi, demak hatto eng kam miqdordagi n ta yechimni topish uchun ham hamma yechimlarni ko'rib chiqish, mumkin bo'lmagan darajada cho'zilib ketadi. Shuning uchun bunday masalalarni, transport masalasining xususiy holi bo'lsa ham, transport usuli bilan yechish maqsadga muvofiq emas. Unga boshqa usulni qo'llash kerak. Mak usuli. Tanlov masalalarini yechish uchun hozirgi vaqtgacha ikkita usul ...