Ushbu maqolada biz omborda bo'sh hujayralar etishmasligi muammosini qanday hal qilganimizni va bunday muammoni hal qilish uchun diskret optimallashtirish algoritmini ishlab chiqishni aytib beramiz. Keling, optimallashtirish muammosining matematik modelini qanday "qurganimiz" va algoritm uchun kirish ma'lumotlarini qayta ishlashda biz kutilmaganda duch kelgan qiyinchiliklar haqida gapiraylik.
Agar siz matematikani biznesda qo'llashga qiziqsangiz va 5-sinf darajasida formulalarning qat'iy o'zgarishlaridan qo'rqmasangiz, mushukka xush kelibsiz!
Maqola amalga oshiradiganlar uchun foydali bo'ladi WMS-tizimlar, ombor yoki ishlab chiqarish logistikasi sanoatidagi ishlar, shuningdek, biznesda matematikani qo'llash va korxonadagi jarayonlarni optimallashtirishga qiziqqan dasturchilar.
Kirish qismi
Ushbu nashr biz ombor jarayonlarida optimallashtirish algoritmlarini amalga oshirish bo'yicha muvaffaqiyatli tajribamiz bilan o'rtoqlashadigan maqolalar seriyasini davom ettiradi.
Π biz amalga oshirgan omborning o'ziga xos xususiyatlarini tasvirlaydi WMS-tizim, shuningdek, nima uchun biz amalga oshirish jarayonida qolgan tovarlar partiyalarini klasterlash muammosini hal qilishimiz kerakligini tushuntiradi. WMS-tizimlar va biz buni qanday qildik.
Biz optimallashtirish algoritmlari haqidagi maqolani yozishni tugatganimizda, u juda katta bo'lib chiqdi, shuning uchun biz to'plangan materialni 2 qismga bo'lishga qaror qildik:
- Birinchi qismda (ushbu maqola) biz muammoning matematik modelini qanday "qurganimiz" va algoritm uchun kirish ma'lumotlarini qayta ishlash va o'zgartirishda biz kutilmaganda duch kelgan katta qiyinchiliklar haqida gapiramiz.
- Ikkinchi bo'limda biz algoritmni tilda amalga oshirishni batafsil ko'rib chiqamiz C ++, biz hisoblash eksperimentini o'tkazamiz va mijozning biznes jarayonlarida bunday "aqlli texnologiyalar" ni joriy qilish jarayonida to'plagan tajribamizni umumlashtiramiz.
Maqolani qanday o'qish kerak. Agar siz avvalgi maqolani o'qigan bo'lsangiz, darhol "Mavjud echimlarning umumiy ko'rinishi" bo'limiga o'tishingiz mumkin, agar bo'lmasa, hal qilinayotgan muammoning tavsifi quyidagi spoylerda.
Xaridorning omborida hal qilinayotgan muammoning tavsifi
Jarayonlardagi to'siqlar
2018 yilda biz amalga oshirish uchun loyihani yakunladik WMS-Chelyabinskdagi "LD" savdo uyi omboridagi tizimlar. Biz 1 ta ish joyi uchun "3C-Logistics: Omborni boshqarish 20" mahsulotini joriy qildik: operatorlar WMS, omborchilar, forklift haydovchilari. O'rtacha ombor taxminan 4 ming m2, kameralar soni 5000 va SKU soni 4500. Omborda 1 kg dan 400 kg gacha bo'lgan turli o'lchamdagi o'zimiz ishlab chiqargan sharli klapanlar saqlanadi. Ombordagi inventar partiyalarda saqlanadi, chunki FIFO bo'yicha tovarlarni tanlash zarurati mavjud.
Ombor jarayonlarini avtomatlashtirish sxemalarini loyihalash jarayonida biz inventarni optimal bo'lmagan saqlash muammosiga duch keldik. Kranlarni saqlash va yotqizishning o'ziga xos xususiyatlari shundan iboratki, bitta saqlash xujayrasi faqat bitta partiyadagi narsalarni o'z ichiga olishi mumkin (1-rasmga qarang). Mahsulotlar har kuni omborga keladi va har bir kelishi alohida partiya hisoblanadi. Hammasi bo'lib, omborning 1 oylik ishlashi natijasida har biri alohida kamerada saqlanishi kerakligiga qaramay, 30 ta alohida partiyalar yaratiladi. Mahsulotlar ko'pincha butun palletlarda emas, balki bo'laklarda tanlanadi va natijada ko'plab hujayralardagi parcha tanlash zonasida quyidagi rasm kuzatiladi: hajmi 1 m3 dan ortiq bo'lgan hujayrada bir nechta kran bo'laklari mavjud. hujayra hajmining 5-10% dan kamini egallaydi.
1-rasm. Hujayradagi bir nechta bo'laklarning fotosurati
Saqlash hajmidan optimal foydalanilmayotgani aniq. Falokat ko'lamini tasavvur qilish uchun men raqamlarni keltira olaman: o'rtacha hisobda ombor faoliyatining turli davrlarida "minuskulyar" balanslarga ega bo'lgan hajmi 1 m3 dan ortiq bo'lgan bunday hujayralarning 100 dan 300 gacha hujayralari mavjud. Ombor nisbatan kichik bo'lganligi sababli, omborning band bo'lgan mavsumlarida bu omil "tor bo'g'oz" ga aylanadi va omborni qabul qilish va jo'natish jarayonlarini sezilarli darajada sekinlashtiradi.
Muammoni hal qilish g'oyasi
Bir fikr paydo bo'ldi: eng yaqin sanalari bo'lgan qoldiqlarning partiyalari bitta partiyaga qisqartirilishi kerak va birlashtirilgan partiyaga ega bo'lgan bunday qoldiqlar ixcham holda bitta katakka yoki bir nechta bo'sh joy bo'lmasa, joylashtirilishi kerak. qoldiqlarning butun miqdori. Bunday "siqishni" misoli 2-rasmda ko'rsatilgan.
2-rasm. Hujayralardagi qoldiqlarni siqish sxemasi
Bu sizga joylashtiriladigan yangi tovarlar uchun ishlatiladigan ombor maydonini sezilarli darajada kamaytirish imkonini beradi. Ombor sig'imi haddan tashqari yuklangan vaziyatda bunday chora juda zarur, aks holda yangi tovarlarni joylashtirish uchun bo'sh joy etarli bo'lmasligi mumkin, bu esa omborni joylashtirish va to'ldirish jarayonlarini to'xtatishga olib keladi va natijada, qabul qilish va jo'natishni to'xtatish. Ilgari, WMS tizimini joriy etishdan oldin, bunday operatsiya qo'lda amalga oshirildi, bu samarasiz edi, chunki hujayralardagi mos balanslarni izlash jarayoni ancha uzoq edi. Endi WMS tizimini joriy qilish bilan biz jarayonni avtomatlashtirishga, tezlashtirishga va uni aqlli qilishga qaror qildik.
Bunday muammoni hal qilish jarayoni 2 bosqichga bo'linadi:
- birinchi bosqichda biz siqilish muddati yaqin bo'lgan partiyalar guruhlarini topamiz (ushbu vazifaga bag'ishlangan );
- ikkinchi bosqichda har bir partiyalar guruhi uchun biz hujayralardagi qolgan tovarlarning eng ixcham joylashishini hisoblaymiz.
Joriy maqolada biz algoritmning ikkinchi bosqichiga e'tibor qaratamiz.
Mavjud echimlarni ko'rib chiqish
Biz ishlab chiqqan algoritmlarning tavsifiga o'tishdan oldin, bozorda allaqachon mavjud bo'lgan tizimlarning qisqacha sharhini o'tkazishga arziydi. WMS, shunga o'xshash optimal siqish funksiyasini amalga oshiradigan.
Avvalo, "1C: Enterprise 8. WMS Logistics" mahsulotini ta'kidlash kerak. Omborni boshqarish 4", 1C-ga tegishli va ko'paytiriladi va to'rtinchi avlodga tegishli WMS-AXELOT tomonidan ishlab chiqilgan tizimlar. Ushbu tizim turli xil mahsulot qoldiqlarini bitta umumiy hujayrada birlashtirish uchun mo'ljallangan siqish funksiyasiga da'vo qiladi. Shuni ta'kidlash kerakki, bunday tizimdagi siqish funksiyasi boshqa imkoniyatlarni ham o'z ichiga oladi, masalan, ABC sinflari bo'yicha hujayralardagi tovarlarni joylashtirishni to'g'rilash, ammo biz ular haqida to'xtalmaymiz.
Agar siz 1C: Enterprise 8. WMS Logistics tizimining kodini tahlil qilsangiz. Omborni boshqarish 4" (funktsionallikning ushbu qismida ochiq), biz quyidagilarni xulosa qilishimiz mumkin. Qoldiqni siqish algoritmi ancha ibtidoiy chiziqli mantiqni amalga oshiradi va hech qanday "optimal" siqish haqida gap bo'lishi mumkin emas. Tabiiyki, u partiyalarning klasterlanishini nazarda tutmaydi. Bunday tizimni amalga oshirgan bir nechta mijozlar siqishni rejalashtirish natijalari haqida shikoyat qildilar. Misol uchun, ko'pincha amalda siqish paytida quyidagi holat yuzaga keldi: 100 dona. Qolgan tovarlarni bir kameradan 1 dona joylashgan boshqa kameraga o'tkazish rejalashtirilgan. tovarlar, garchi buning aksini qilish vaqt sarfi nuqtai nazaridan optimal bo'lsa-da.
Shuningdek, hujayralardagi qolgan tovarlarni siqish funksiyasi ko'plab xorijiy mamlakatlarda e'lon qilingan. WMS-tizimlar, lekin, afsuski, biz algoritmlarning samaradorligi (bu tijorat siri) haqida aniq fikr-mulohazalarga ega emasmiz, ularning mantig'ining chuqurligi (xususiy yopiq manba dasturiy ta'minot) haqida hech qanday fikrimiz yo'q, shuning uchun biz hukm qila olmaymiz.
Muammoning matematik modelini qidiring
Muammoni hal qilish uchun yuqori sifatli algoritmlarni loyihalash uchun birinchi navbatda bu masalani matematik tarzda aniq shakllantirish kerak, biz buni qilamiz.
Ko'p hujayralar mavjud , unda ba'zi tovarlarning qoldiqlari mavjud. Quyida biz bunday hujayralarni donor hujayralar deb ataymiz. belgilaylik hujayradagi tovarlar hajmi $.
Shuni aytish kerakki, bitta partiyaning faqat bitta mahsuloti yoki ilgari klasterga birlashtirilgan bir nechta partiyalar (o'qing: ), bu tovarlarni saqlash va saqlashning o'ziga xos xususiyatlari bilan bog'liq. Turli mahsulotlar yoki turli partiyali klasterlar o'zlarining alohida siqish protseduralarini bajarishlari kerak.
Ko'p hujayralar mavjud , donor hujayralarining qoldiqlari potentsial ravishda joylashtirilishi mumkin. Keyinchalik bunday hujayralarni konteyner hujayralari deb ataymiz. Bular ombordagi bo'sh hujayralar yoki turli donor hujayralar bo'lishi mumkin . Har doim ko'p kichik toβplamdir .
Har bir hujayra uchun ko'pchilikdan Imkoniyatlar cheklovlari o'rnatildi , dm3 da o'lchanadi. Bir dm3 10 sm tomonlari bo'lgan kubdir.Omborda saqlanadigan mahsulotlar juda katta, shuning uchun bu holda bunday diskretizatsiya juda etarli.
Eng qisqa masofalar matritsasi berilgan har bir juft hujayra orasidagi metrda qayerda ΠΈ to'plamlarga tegishli ΠΈ mos ravishda.
belgilaylik Hujayradan tovarlarni ko'chirish "xarajatlari" hujayra ichiga . belgilaylik Idishni tanlashning "xarajatlari" boshqa hujayralardagi qoldiqlarni unga ko'chirish. Qanchalik aniq va qaysi o'lchov birliklarida qiymatlar hisoblab chiqiladi ΠΈ biz batafsilroq ko'rib chiqamiz (kirish ma'lumotlarini tayyorlash bo'limiga qarang), hozircha bunday qiymatlar qiymatlarga to'g'ridan-to'g'ri proportsional bo'lishini aytish kifoya. ΠΈ mos ravishda.
bilan belgilaymiz agar qolgan hujayradan bo'lsa, 1 qiymatini oladigan o'zgaruvchi konteynerga ko'chirildi , va aks holda 0. bilan belgilaymiz konteyner bo'lsa 1 qiymatini oladigan o'zgaruvchi qolgan tovarlarni o'z ichiga oladi, va boshqa hollarda 0.
Vazifa quyidagicha ifodalanadi: siz juda ko'p konteyner topishingiz kerak va shuning uchun funktsiyani minimallashtirish uchun donor hujayralarni konteyner hujayralariga "biriktiring"
cheklovlar ostida
Umuman olganda, muammoning echimini hisoblashda biz quyidagilarga intilamiz:
- birinchidan, saqlash hajmini tejash;
- ikkinchidan, do'kondorlarning vaqtini tejash.
Oxirgi cheklov shuni anglatadiki, biz tovarlarni biz tanlamagan konteynerga o'tkaza olmaymiz va shuning uchun uni tanlash uchun "xarajat qilmadik". Ushbu cheklov, shuningdek, hujayralardan konteynerga o'tkaziladigan tovarlar hajmi konteyner sig'imidan oshmasligi kerakligini anglatadi. Muammoni hal qilish deganda biz idishlar to'plamini tushunamiz va donor hujayralarni konteynerlarga biriktirish usullari.
Optimallashtirish muammosining bunday formulasi yangi emas va o'tgan asrning 80-yillari boshidan beri ko'plab matematiklar tomonidan o'rganilgan. Xorijiy adabiyotlarda mos matematik model bilan 2 ta optimallashtirish muammosi mavjud: ΠΈ (vazifalardagi farqlar haqida keyinroq gaplashamiz). Aytish joizki, matematik adabiyotlarda bunday ikkita optimallashtirish masalasini shakllantirish korxonalarning yerdagi joylashuvi nuqtai nazaridan shakllantirilgan, shuning uchun "Obyektning joylashuvi" deb nomlanadi. Ko'pincha, bu an'anaga bo'lgan hurmatdir, chunki bunday kombinatsion muammolarni hal qilish zarurati birinchi marta logistika sohasidan, asosan, o'tgan asrning 50-yillarida harbiy-sanoat sektoridan paydo bo'lgan. Korxonaning joylashuvi nuqtai nazaridan bunday vazifalar quyidagicha tuzilgan:
- Ishlab chiqarish korxonalarini (keyingi o'rinlarda ishlab chiqaruvchi shaharlar deb yuritiladi) joylashtirish mumkin bo'lgan chekli shaharlar mavjud. Har bir ishlab chiqaruvchi shahar uchun unda korxona ochish xarajatlari, shuningdek, unda ochilgan korxonaning ishlab chiqarish quvvatiga cheklov ko'rsatilgan.
- Mijozlar haqiqatda joylashgan shaharlarning cheklangan to'plami mavjud (keyingi o'rinlarda mijoz shaharlari deb yuritiladi). Har bir bunday mijoz shahri uchun mahsulotga bo'lgan talab hajmi ko'rsatilgan. Oddiylik uchun biz korxonalar tomonidan ishlab chiqarilgan va mijozlar tomonidan iste'mol qilinadigan faqat bitta mahsulot bor deb taxmin qilamiz.
- Shahar-ishlab chiqaruvchi va shahar-mijozning har bir juftligi uchun ishlab chiqaruvchidan mijozga kerakli hajmdagi mahsulotlarni etkazib berish uchun transport xarajatlarining qiymati ko'rsatilgan.
Qaysi shaharlarda biznes ochish va mijozlarni bunday korxonalarga qanday qilib biriktirish kerakligini bilib olishingiz kerak:
- Korxonalarni ochish va transport xarajatlarining umumiy xarajatlari minimal edi;
- Har qanday ochiq korxonaga biriktirilgan xaridorlarning talab hajmi ushbu korxonaning ishlab chiqarish quvvatidan oshmagan.
Endi ushbu ikkita klassik muammoning yagona farqini eslatib o'tish kerak:
- Yagona manbali sig'imli ob'ektni joylashtirish muammosi - mijoz faqat bitta ochiq ob'ektdan ta'minlanadi;
- Ko'p manbali sig'imli ob'ektni joylashtirish muammosi - mijoz bir vaqtning o'zida bir nechta ochiq ob'ektlardan ta'minlanishi mumkin.
Ikki masala o'rtasidagi bunday farq bir qarashda ahamiyatsiz bo'lsa-da, lekin, aslida, bunday masalalarning butunlay boshqacha kombinatsiyaviy tuzilishiga va natijada ularni yechishning butunlay boshqacha algoritmlariga olib keladi. Vazifalar orasidagi farqlar quyidagi rasmda ko'rsatilgan.
3-rasm. a) Ko'p manbali sig'imli ob'ektni joylashtirish muammosi
3-rasm. b) Yagona manbali sig'imli ob'ektni joylashtirish muammosi
Ikkala vazifa ham -qiyin, ya'ni kiritilgan ma'lumotlarning o'lchamidagi vaqt polinomida bunday masalani hal qiladigan aniq algoritm mavjud emas. Oddiy so'zlar bilan aytganda, muammoni hal qilish uchun barcha aniq algoritmlar eksponensial vaqt ichida ishlaydi, garchi variantlarni to'liq qidirishdan tezroq bo'lsa ham. Vazifadan beri -qiyin bo'lsa, biz faqat taxminiy evristikani ko'rib chiqamiz, ya'ni optimalga juda yaqin yechimlarni doimiy ravishda hisoblab chiqadigan va juda tez ishlaydigan algoritmlarni ko'rib chiqamiz. Agar siz bunday vazifaga qiziqsangiz, bu erda rus tilida yaxshi sharhni topishingiz mumkin.
Agar biz hujayralardagi tovarlarni optimal siqish muammomiz terminologiyasiga o'tadigan bo'lsak, unda:
- mijoz shaharlari donor hujayralardir qolgan tovarlar bilan,
- ishlab chiqarish shaharlari - konteyner hujayralari , unda boshqa hujayralardagi qoldiqlar joylashtirilishi kerak,
- transport xarajatlari - vaqt xarajatlari donor hujayradan tovarlar hajmini ko'chirish uchun omborchi konteyner hujayra ichiga ;
- biznesni ochish xarajatlari - konteyner tanlash xarajatlari , konteyner xujayrasining hajmiga teng , bo'sh hajmlarni saqlash uchun ma'lum bir koeffitsient bilan ko'paytiriladi (koeffitsientning qiymati har doim > 1) (kirish ma'lumotlarini tayyorlash bo'limiga qarang).
Muammoning taniqli klassik echimlari bilan o'xshashlik tuzilgandan so'ng, yechim algoritmining arxitekturasini tanlash bog'liq bo'lgan muhim savolga javob berish kerak: qoldiqlarni donor hujayradan faqat bittasiga ko'chirish mumkin. va faqat bitta konteyner (Yagona manba) yoki qoldiqlarni bir nechta konteyner hujayralariga (Ko'p manbali) ko'chirish mumkinmi?
Shuni ta'kidlash kerakki, amalda muammoning ikkala formulasi ham amalga oshiriladi. Biz quyida har bir bunday sozlamaning barcha ijobiy va salbiy tomonlarini taqdim etamiz:
| Muammoli variant | Variantning afzalliklari | Variantning kamchiliklari |
|---|---|---|
| Yagona manba | Muammoning ushbu variantidan foydalangan holda hisoblangan tovarlarni tashish operatsiyalari:
|
|
| Ko'p manba | Muammoning ushbu versiyasi yordamida hisoblangan siqilishlar odatda "Yagona manba" opsiyasi yordamida hisoblangan siqilishlarga nisbatan 10-15% ixchamroqdir. Ammo shuni ham ta'kidlaymizki, donor hujayralardagi qoldiqlar soni qanchalik kichik bo'lsa, ixchamlikdagi farq shunchalik kichik bo'ladi. | Muammoning ushbu variantidan foydalangan holda hisoblangan tovarlarni tashish operatsiyalari:
|
Jadval 1. Bir manbali va ko'p manbali variantlarning ijobiy va salbiy tomonlari.
Yagona manba varianti ko'proq afzalliklarga ega bo'lganligi sababli, shuningdek, donor hujayralardagi qoldiqlar soni qanchalik kichik bo'lsa, muammoning ikkala varianti uchun hisoblangan siqilish ixchamlik darajasidagi farq shunchalik kichik bo'lishini hisobga olgan holda, bizning tanlovimiz Yagona manba opsiyasi. Manba.
Shuni ta'kidlash kerakki, Ko'p manbali variantni hal qilish ham amalga oshiriladi. Uni hal qilish uchun juda ko'p samarali algoritmlar mavjud bo'lib, ularning aksariyati bir qator transport muammolarini hal qilishga to'g'ri keladi. Bundan tashqari, nafaqat samarali algoritmlar, balki oqlanganlari ham mavjud, masalan,
Kirish ma'lumotlarini tayyorlash
Muammoni hal qilish uchun algoritmni tahlil qilish va ishlab chiqishni boshlashdan oldin, biz qanday ma'lumotlarni va qaysi shaklda kirish sifatida berishimizni hal qilishimiz kerak. Donor hujayralardagi qolgan tovarlar hajmi va konteyner hujayralarining sig'imi bilan bog'liq muammolar yo'q, chunki bu ahamiyatsiz - bunday miqdorlar m3 da o'lchanadi, lekin konteyner kamerasidan foydalanish xarajatlari va harakatlanuvchi xarajat matritsasi bilan hammasi emas. juda oddiy!
Keling, avval hisob-kitobni ko'rib chiqaylik tovarlarni ko'chirish xarajatlari donor hujayradan konteyner hujayragacha. Avvalo, harakat xarajatlarini qaysi o'lchov birliklarida hisoblashimizni hal qilish kerak. Ikkita eng aniq variant - metr va soniya. Sayohat xarajatlarini "sof" metrlarda hisoblash mantiqiy emas. Buni misol bilan ko'rsatamiz. Hujayraga ruxsat bering birinchi qavat, katakda joylashgan 30 metrga olib tashlangan va ikkinchi qavatda joylashgan:
- dan ko'chirish Π² ko'chirishdan qimmatroq Π² , chunki ikkinchi qavatdan pastga tushish (poldan 1,5-2 metr) ikkinchi darajaga ko'tarilishdan ko'ra osonroqdir, garchi masofa bir xil bo'ladi;
- 1 dona harakatlantiring. hujayradan olingan tovarlar Π² 10 qismni ko'chirishdan ko'ra osonroq bo'ladi. bir xil mahsulot, garchi masofa bir xil bo'ladi.
Ko'chirish xarajatlarini soniyalarda ko'rib chiqish yaxshiroqdir, chunki bu sizga sathlardagi farqni ham, ko'chirilgan tovarlar miqdoridagi farqni ham hisobga olishga imkon beradi. Harakatning soniyalardagi narxini hisobga olish uchun biz harakat operatsiyasini elementar komponentlarga ajratishimiz va har bir elementar komponentning bajarilishi uchun vaqt o'lchovlarini olishimiz kerak.
Hujayradan ruxsat bering harakat qiladi Kompyuter. konteynerdagi tovarlar ... Bo'lsin - ishchining ombordagi o'rtacha harakati tezligi, m/sek. Mayli ΠΈ - bir martalik operatsiyalarning o'rtacha tezligi mos ravishda 4 dm3 ga teng bo'lgan tovarlar hajmi uchun olinadi va qo'yiladi (xodimning operatsiyalarni bajarishda bir vaqtning o'zida omborda oladigan o'rtacha hajmi). Mayli ΠΈ mos ravishda olish va qo'yish operatsiyalari bajariladigan kataklarning balandligi. Masalan, birinchi qavatning (qavatning) o'rtacha balandligi 1 m, ikkinchi qavatning balandligi 2 m va hokazo. Keyin ko'chirish operatsiyasini bajarish uchun umumiy vaqtni hisoblash formulasi Keyingisi:
2-jadvalda saqlanadigan tovarlarning o'ziga xos xususiyatlarini hisobga olgan holda ombor xodimlari tomonidan yig'ilgan har bir elementar operatsiyani bajarish vaqti bo'yicha statistik ma'lumotlar keltirilgan.
| operatsiya nomi | Notation | O'rtacha qiymati |
|---|---|---|
| Ombor atrofida harakatlanuvchi ishchining o'rtacha tezligi | |
1,5 m/s |
| Bir operatsiyani bajarishning o'rtacha tezligi (4 dm3 mahsulot hajmi uchun) | |
2,4 soniya |
Jadval 2. Ombor operatsiyalarini bajarish uchun o'rtacha vaqt
Biz ko'chirish xarajatlarini hisoblash usuliga qaror qildik. Endi biz qanday hisoblashni aniqlashimiz kerak konteyner xujayrasini tanlash xarajatlari. Bu erda hamma narsa ko'chirish xarajatlariga qaraganda ancha murakkabroq, chunki:
- birinchidan, xarajatlar to'g'ridan-to'g'ri hujayra hajmiga bog'liq bo'lishi kerak - donor hujayralardan o'tkaziladigan bir xil hajmdagi qoldiqlarni katta idishga qaraganda kichikroq hajmdagi idishga joylashtirish yaxshiroqdir, agar bunday hajm ikkala idishga ham to'liq mos kelsa. . Shunday qilib, konteynerlarni tanlash bo'yicha umumiy xarajatlarni minimallashtirish orqali biz tovarlarni hujayralarga joylashtirish bo'yicha keyingi operatsiyalarni bajarish uchun tanlov hududida "kam" bepul saqlash hajmini tejashga harakat qilamiz. 4-rasmda qoldiqlarni katta va kichik idishlarga o'tkazish variantlari va keyingi ombor operatsiyalarida ushbu o'tkazish variantlarining oqibatlari ko'rsatilgan.
- ikkinchidan, asl muammoni hal qilishda biz aniq jami xarajatlarni minimallashtirishimiz kerak va bu ko'chirish xarajatlari va konteynerlarni tanlash xarajatlarining yig'indisi bo'lganligi sababli, kubometrdagi hujayra hajmi qandaydir tarzda soniyalarga bog'lanishi kerak, bu arzimas narsadan uzoqdir.
Guruch. 4. Qoldiqlarni turli sig'imdagi idishlarga ko'chirish variantlari.
4-rasmda keyingi tovarlarni joylashtirishning ikkinchi bosqichida konteynerga sig'maydigan qoldiqlar hajmi qizil rangda ko'rsatilgan.
Bu muammoning hisoblangan echimlari uchun quyidagi talablarni ko'chirish xarajatlarining soniyalari bilan konteyner tanlash uchun kubometr xarajatlarni bog'lashga yordam beradi:
- Donor qutisidagi qoldiqlar har qanday holatda ham konteyner qutisiga o'tkazilishi kerak, agar bu mahsulotni o'z ichiga olgan konteyner qutilarining umumiy sonini kamaytirsa.
- Konteynerlar hajmi va harakatga sarflangan vaqt o'rtasidagi muvozanatni saqlash kerak: masalan, agar muammoning yangi yechimida oldingi yechim bilan solishtirganda, hajmdagi daromad katta bo'lsa, vaqt yo'qotilishi kichik bo'ladi. , keyin yangi variantni tanlash kerak.
Keling, oxirgi talabdan boshlaylik. "Balans" noaniq so'ziga aniqlik kiritish uchun biz quyidagilarni aniqlash uchun ombor xodimlari o'rtasida so'rov o'tkazdik. Hajmi bo'lgan konteyner hujayrasi bo'lsin , donor hujayralardan qolgan tovarlarning harakatlanishi tayinlangan va bunday harakatning umumiy vaqti tengdir . Xuddi shu donor hujayralaridan bir xil miqdordagi tovarlarni boshqa konteynerlarga joylashtirishning bir nechta muqobil variantlari bo'lsin, bu erda har bir joylashtirish o'z taxminlariga ega. qayerda < ΠΈ qayerda >.
Savol tug'iladi: hajmdagi minimal daromad nima ma'lum vaqt yo'qotish qiymati uchun qabul qilinadi ? Keling, misol bilan tushuntiramiz. Dastlab, qoldiqlar hajmi 1000 dm3 (1 m3) bo'lgan idishga joylashtirilishi kerak edi va uzatish vaqti 70 soniya edi. Qoldiqlarni hajmi 500 dm3 va vaqti 130 soniya bo'lgan boshqa idishga joylashtirish imkoniyati mavjud. Savol: 60 dm500 bo'sh hajmni tejash uchun omborchining qo'shimcha 3 soniya vaqtini tovarlarni tashishga sarflashga tayyormizmi? Ombor xodimlari o'rtasida o'tkazilgan so'rov natijalariga ko'ra quyidagi diagramma tuzildi.
Guruch. 5. Minimal ruxsat etilgan hajm tejamkorligining ish vaqtidagi farqning oshishiga bog'liqligi diagrammasi.
Ya'ni, agar qo'shimcha vaqt xarajatlari 40 soniya bo'lsa, biz ularni faqat hajmdagi daromad kamida 500 dm3 bo'lganda sarflashga tayyormiz. Bog'liqlikda ozgina nochiziqlilik mavjud bo'lishiga qaramay, keyingi hisob-kitoblarning soddaligi uchun biz miqdorlar orasidagi bog'liqlik chiziqli va tengsizlik bilan tavsiflanadi deb taxmin qilamiz.
Quyidagi rasmda biz tovarlarni konteynerlarga joylashtirishning quyidagi usullarini ko'rib chiqamiz.
Guruch. 6. Variant (a): 2 ta konteyner, umumiy hajmi 400 dm3, umumiy vaqt 150 sek.
Guruch. 6. Variant (b): 2 ta konteyner, umumiy hajmi 600 dm3, umumiy vaqt 190 sek.
Guruch. 6. Variant (c): 1 ta konteyner, umumiy hajmi 400 dm3, umumiy vaqt 200 sek.
Konteynerlarni tanlash uchun (a) varianti asl variantdan ko'ra afzalroqdir, chunki tengsizlik o'rinli: (800-400)/10>=150-120, bu 40 >= 30 ni bildiradi. Variant (b) asl variantdan kamroq afzalroqdir. variant , chunki tengsizlik bajarilmaydi: (800-600)/10>=190-150 bu 20 >= 40 ni bildiradi. Lekin (c) variant bunday mantiqqa to'g'ri kelmaydi! Keling, ushbu variantni batafsil ko'rib chiqaylik. Bir tomondan, tengsizlik (800-400)/10>=200-120, ya'ni 40 >= 80 tengsizlik qanoatlanmaydi, bu esa hajmdagi o'sish vaqt ichida bunday katta yo'qotishga arzimasligini ko'rsatadi.
Ammo boshqa tomondan, bu variantda (c) biz nafaqat umumiy ishg'ol qilingan hajmni kamaytiramiz, balki ishg'ol qilingan hujayralar sonini ham kamaytiramiz, bu yuqorida sanab o'tilgan muammolarni hisoblash mumkin bo'lgan echimlar uchun ikkita muhim talabning birinchisidir. Shubhasiz, bu talab bajarila boshlash uchun tengsizlikning chap tomoniga qandaydir musbat doimiy qo'shish kerak. , va bunday konstanta faqat konteynerlar soni kamayganda qo'shilishi kerak. Shuni eslatib o'tamiz konteyner bo'lganda 1 ga teng o'zgaruvchidir tanlangan, va konteyner qachon 0 tanlanmagan. Belgilaymiz β dastlabki eritmada koβplab idishlar va - yangi yechimdagi ko'plab konteynerlar. Umuman olganda, yangi tengsizlik quyidagicha ko'rinadi:
Yuqoridagi tengsizlikni o'zgartirib, biz olamiz
Bunga asoslanib, bizda umumiy xarajatlarni hisoblash formulasi mavjud muammoning ba'zi yechimlari:
Ammo endi savol tug'iladi: bunday doimiy qanday qiymatga ega bo'lishi kerak? ? Shubhasiz, uning qiymati etarlicha katta bo'lishi kerak, shunda muammoni hal qilish uchun birinchi talab har doim qondiriladi. Siz, albatta, 103 yoki 106 ga teng bo'lgan doimiy qiymatni olishingiz mumkin, lekin men bunday "sehrli raqamlar" dan qochishni xohlayman. Agar biz ombor operatsiyalarini bajarishning o'ziga xos xususiyatlarini ko'rib chiqsak, biz bunday doimiy qiymatning bir nechta asosli raqamli hisoblarini hisoblashimiz mumkin.
Keling - bitta ABC zonasining ombor kameralari orasidagi maksimal masofa, bizning holatlarimizda 100 m ga teng. - ombordagi konteyner kamerasining maksimal hajmi, bizning holatlarimizda 1000 dm3 ga teng.
Qiymatni hisoblashning birinchi usuli . Keling, birinchi yarusda 2 ta konteyner bo'lgan vaziyatni ko'rib chiqaylik, ularda tovarlar allaqachon jismoniy joylashgan, ya'ni ular o'zlari donor hujayralar bo'lib, tovarlarni bir xil hujayralarga ko'chirish narxi tabiiy ravishda 0 ga teng. doimiy uchun bunday qiymatni topish kerak , unda qoldiqlarni har doim 1-konteynerdan 2-konteynerga o'tkazish foydali bo'ladi. Qiymatlarni almashtirish ΠΈ Yuqorida keltirilgan tengsizlikda biz quyidagilarni olamiz:
undan kelib chiqadi
Yuqoridagi formulaga elementar operatsiyalarni bajarish uchun o'rtacha vaqt qiymatlarini almashtirsak, biz olamiz
Qiymatni hisoblashning ikkinchi usuli . Keling, mavjud bo'lgan vaziyatni ko'rib chiqaylik tovarni konteynerga o'tkazish rejalashtirilgan donor hujayralar 1. Belgilaymiz - donor hujayradan masofa 1-konteynerga. Bundan tashqari, 2-konteyner mavjud bo'lib, u allaqachon tovarlarni o'z ichiga oladi va uning hajmi qolganlarini joylashtirishga imkon beradi. hujayralar. Oddiylik uchun biz donor hujayralardan konteynerlarga o'tkaziladigan tovarlar hajmi bir xil va teng deb faraz qilamiz. . Konstantaning bunday qiymatini topish talab qilinadi , unda barcha qoldiqlarni joylashtirish Hujayralarni 2-konteynerga joylashtirish har doim ularni turli idishlarga joylashtirishdan ko'ra foydaliroq bo'ladi:
Olingan tengsizlikni o'zgartirish
Miqdorning qiymatini "mustahkamlash" uchun , faraz qilaylik = 0. Odatda ombor balanslarini siqish protsedurasida ishtirok etadigan hujayralarning o'rtacha soni 10 ni tashkil qiladi. Miqdorlarning ma'lum qiymatlarini almashtirsak, biz doimiyning quyidagi qiymatiga ega bo'lamiz.
Biz har bir variant uchun hisoblangan eng katta qiymatni olamiz, bu miqdorning qiymati bo'ladi berilgan ombor parametrlari uchun. Keling, to'liqlik uchun umumiy xarajatlarni hisoblash formulasini yozamiz ba'zi bir mumkin bo'lgan yechim uchun :
Axir, endi Herkulning harakatlari Kirish ma'lumotlarini o'zgartirish orqali biz barcha kirish ma'lumotlari kerakli shaklga aylantirilganligini va optimallashtirish algoritmida foydalanishga tayyorligini aytishimiz mumkin.
xulosa
Amaliyot shuni ko'rsatadiki, algoritm uchun kirish ma'lumotlarini tayyorlash va o'zgartirish bosqichining murakkabligi va ahamiyati ko'pincha kam baholanadi. Ushbu maqolada biz faqat yuqori sifatli va oqilona tayyorlangan kirish ma'lumotlari algoritm tomonidan hisoblangan qarorlarni mijoz uchun haqiqatan ham qimmatli bo'lishi mumkinligini ko'rsatish uchun ushbu bosqichga alohida e'tibor qaratdik. Ha, formulalarning ko'p hosilalari bor edi, lekin biz sizni katadan oldin ham ogohlantirgan edik :)
Keyingi maqolada, nihoyat, oldingi ikkita nashr nima uchun mo'ljallanganligiga - diskret optimallashtirish algoritmiga kelamiz.
Maqolani tayyorladi
Roman Shangin, loyihalar bo'limi dasturchisi,
Birinchi Bit kompaniyasi, Chelyabinsk
Manba: www.habr.com