Selles artiklis räägime teile, kuidas lahendasime laos vabade lahtrite puudumise probleemi ja töötasime välja sellise probleemi lahendamiseks diskreetse optimeerimisalgoritmi. Räägime sellest, kuidas me optimeerimisülesande matemaatilist mudelit “ehitasime” ja raskustest, mis ootamatult tekkisid algoritmi sisendandmete töötlemisel.
Kui sind huvitavad matemaatika rakendused ettevõtluses ja sa ei karda valemite jäikade identiteedi teisendusi 5. klassi tasemel, siis tere tulemast kassile!
Artikkel on kasulik neile, kes seda rakendavad WMS-süsteemid, töötab lao- või tootmislogistika tööstuses, samuti programmeerijaid, kes on huvitatud matemaatika rakendamisest ettevõtluses ja protsesside optimeerimisest ettevõttes.
Sissejuhatav osa
Käesolev väljaanne jätkab artiklite sarja, milles jagame oma edukaid kogemusi optimeerimisalgoritmide rakendamisel laoprotsessides.
В kirjeldab selle lao spetsiifikat, kus rakendasime WMS-süsteemi ja selgitab ka, miks pidime juurutamise ajal lahendama allesjäänud kaubapartiide rühmitamise probleemi WMS-süsteemid ja kuidas me seda tegime.
Kui lõpetasime optimeerimisalgoritmide artikli kirjutamise, osutus see väga suureks, nii et otsustasime kogutud materjali jagada kaheks osaks:
- Esimeses osas (käesolevas artiklis) räägime sellest, kuidas me ülesande matemaatilist mudelit “ehitasime” ja suurtest raskustest, mis meil ootamatult tekkisid algoritmi sisendandmete töötlemisel ja transformeerimisel.
- Teises osas käsitleme üksikasjalikult algoritmi rakendamist keeles C + +, viime läbi arvutusliku eksperimendi ja võtame kokku kogemused, mille saime selliste “intelligentsete tehnoloogiate” rakendamisel kliendi äriprotsessides.
Kuidas artiklit lugeda. Kui loed eelmist artiklit, siis saad kohe minna peatükki “Olemasolevate lahenduste ülevaade”, kui ei, siis lahendatava probleemi kirjeldus on allolevas spoileris.
Kliendi laos lahendatava probleemi kirjeldus
Pudelikael protsessides
2018. aastal saime elluviimiseks valmis projekti WMS-süsteemid Tšeljabinskis asuvas laos “Kaubandusmaja “LD”. Võtsime kasutusele toote “1C-Logistics: Warehouse Management 3” 20 töökoha jaoks: operaatorid WMS, laohoidjad, tõstukijuhid. Keskmine ladu on ca 4 tuhat m2, lahtrite arv 5000 ja SKUde arv 4500. Laos hoitakse erinevas mõõdus meie omatoodangu kuulventiile alates 1 kg kuni 400 kg. Laovarusid hoitakse partiidena, kuna on vaja kaupu valida FIFO järgi.
Laoprotsesside automatiseerimise skeemide kavandamisel seisime silmitsi olemasoleva probleemiga mitteoptimaalse laovarude ladustamisega. Kraanade ladustamise ja paigaldamise eripära on selline, et üks ühikhoidla võib sisaldada ainult ühe partii esemeid (vt joonis 1). Tooted jõuavad lattu iga päev ja iga saabumine on eraldi partii. Kokku tekib 1-kuulise laotöö tulemusena 30 eraldi partiid, hoolimata asjaolust, et iga partii tuleks hoida eraldi lahtris. Tooted valitakse sageli mitte tervete kaubaaluste, vaid tükkidena ja selle tulemusena on paljudes lahtrites tükivaliku tsoonis järgmine pilt: lahtris, mille maht on üle 1 m3, on mitu kraanade tükki, mis hõivavad vähem kui 5-10% raku mahust.
Joonis 1. Foto mitmest tükist lahtris
On selge, et mälumahtu ei kasutata optimaalselt. Katastroofi ulatuse ettekujutamiseks võin anda arvud: keskmiselt on lao erinevatel tööperioodidel selliseid kambreid, mille maht on üle 1 m3 ja mille saldo on väike, 100 kuni 300. Kuna ladu on suhteliselt väike, siis kiirel laohooajal muutub see tegur “pudelikaelaks” ja aeglustab oluliselt lao vastuvõtmise ja väljasaatmise protsesse.
Probleemi lahenduse idee
Tekkis idee: lähimate kuupäevadega jääkide partiid tuleks vähendada üheks partiiks ja sellised ühtse partiiga jäägid paigutada kompaktselt ühte lahtrisse või mitmesse, kui ühes pole piisavalt ruumi lahtrisse mahutamiseks. kogu jääkide kogus. Sellise "kokkusurumise" näide on näidatud joonisel 2.
Joonis 2. Skeem rakkudes jääkide kokkupressimiseks
See võimaldab oluliselt vähendada hõivatud laopinda, mida kasutatakse uute kaupade paigutamiseks. Olukorras, kus lao maht on ülekoormatud, on selline meede äärmiselt vajalik, sest vastasel juhul ei pruugi uute kaupade mahutamiseks lihtsalt piisavalt vaba ruumi olla, mis toob kaasa lao paigutamise ja täiendamise protsesside seiskumise ning selle tulemusena vastuvõtmise ja saatmise peatada. Varem, enne WMS-süsteemi juurutamist, tehti selline toiming käsitsi, mis oli ebaefektiivne, kuna rakkudes sobivate tasakaalude otsimise protsess oli üsna pikk. Nüüd, WMS-süsteemi kasutuselevõtuga, otsustasime protsessi automatiseerida, kiirendada ja muuta see intelligentseks.
Sellise probleemi lahendamise protsess on jagatud kaheks etapiks:
- Esimeses etapis leiame pakkimiskuupäevale lähedal olevate partiide rühmad (sellele ülesandele pühendatud );
- teises etapis arvutame iga partiide rühma jaoks ülejäänud kaupade kõige kompaktsema paigutuse lahtrites.
Käesolevas artiklis keskendume algoritmi teisele etapile.
Olemasolevate lahenduste ülevaatamine
Enne meie väljatöötatud algoritmide kirjeldamise juurde asumist tasub teha lühike ülevaade turul juba olemasolevatest süsteemidest WMS, mis rakendavad sarnaseid optimaalseid tihendusfunktsioone.
Kõigepealt on vaja märkida toode “1C: Enterprise 8. WMS Logistics. Laohaldus 4", mis kuulub 1C-le ja mida kopeerib ning kuulub neljandasse põlvkonda WMS-süsteemid, mille on välja töötanud AXELOT. Sellel süsteemil on tihendusfunktsioon, mis on loodud erinevate tootejääkide ühendamiseks ühte ühisesse lahtrisse. Tasub mainida, et tihendusfunktsionaalsus sisaldab sellises süsteemis ka muid võimalusi, näiteks korrigeerida kaupade paigutust lahtritesse nende ABC klasside järgi, kuid neil pikemalt ei peatu.
Kui analüüsite 1C: Enterprise 8. WMS Logistics süsteemi koodi. Laohaldus 4" (mis on funktsionaalsuse selles osas avatud), saame järeldada järgmist. Jääktihendusalgoritm rakendab üsna primitiivset lineaarset loogikat ja mingist “optimaalsest” pakkimisest ei saa juttugi olla. Loomulikult ei näe see ette parteide rühmitamist. Mitmed kliendid, kellel oli selline süsteem kasutusele võetud, kaebasid tihendusplaneerimise tulemuste üle. Näiteks praktikas tekkis sageli kompressiooni ajal järgmine olukord: 100 tk. Ülejäänud kaubad on plaanis kolida ühest lahtrist teise lahtrisse, kus asub 1 tk. kaupa, kuigi ajakulu seisukohalt on optimaalne teha vastupidist.
Samuti on paljudes välisriikides deklareeritud lahtritesse jäänud kauba kokkupressimise funktsionaalsus. WMS-süsteemid, kuid kahjuks pole meil tegelikku tagasisidet algoritmide tõhususe kohta (see on ärisaladus), veel vähem aimu nende loogika sügavusest (varaline suletud lähtekoodiga tarkvara), mistõttu me ei saa hinnata.
Otsige probleemi matemaatilist mudelit
Kvaliteetsete algoritmide väljatöötamiseks ülesande lahendamiseks on kõigepealt vaja see ülesanne selgelt matemaatiliselt sõnastada, mida me ka teeme.
Rakke on palju , mis sisaldavad mõne kauba jäänuseid. Järgnevalt nimetame selliseid rakke doonorrakkudeks. Tähistame kauba maht lahtris $.
Oluline on öelda, et ainult üks toode ühest partiist või mitu partiid, mis on varem klastrisse ühendatud (loe: ), mis on tingitud kaupade ladustamise ja ladustamise spetsiifikast. Erinevad tooted või erinevad partiirühmad peaksid läbima oma eraldi tihendusprotseduuri.
Rakke on palju , millesse saab potentsiaalselt paigutada doonorrakkude jääke. Edasi nimetame selliseid rakke konteinerrakkudeks. Need võivad olla kas laos olevad vabad rakud või sordi doonorrakud . Alati palju on alamhulk .
Iga raku jaoks paljudelt On seatud mahupiirangud , mõõdetuna dm3. Üks dm3 on kuubik, mille küljed on 10 cm.Laos hoiustatud tooted on üsna suured, nii et antud juhul piisab sellisest diskreetsusest täiesti.
Antud lühimate vahemaade maatriks meetrites iga rakupaari vahel Kus и kuuluvad komplekti и võrra.
Tähistame kaupade lahtrist teisaldamise "kulud". rakku . Tähistame konteineri valimise "kulud". teisaldada jäägid teistest rakkudest sellesse. Kuidas täpselt ja millistes mõõtühikutes väärtused arvutatakse и kaalume edasi (vt sisendandmete ettevalmistamise jaotist), praegu piisab, kui öelda, et sellised väärtused on väärtustega otseselt võrdelised и võrra.
Tähistagem poolt muutuja, mis võtab väärtuse 1, kui jääk pärineb lahtrist teisaldati konteinerisse , ja 0 muidu. Tähistagem poolt muutuja, mis võtab konteineri korral väärtuse 1 sisaldab ülejäänud kaupu ja 0 muidu.
Ülesanne on esitatud järgmiselt: peate leidma nii palju konteinereid ja seega "kinnitada" doonorrakud konteinerrakkudele, et funktsiooni minimeerida
piirangute all
Kokkuvõttes püüame probleemi lahenduse arvutamisel:
- esiteks salvestusmahu säästmiseks;
- teiseks, et säästa laopidajate aega.
Viimane piirang tähendab, et me ei saa teisaldada kaupu konteinerisse, mida me ise ei valinud ja seega ei “kandnud kulusid” selle valimisega. See piirang tähendab ka seda, et lahtritest konteinerisse teisaldatava kauba maht ei tohi ületada konteineri mahutavust. Probleemi lahendamise all peame silmas konteinerite komplekti ja meetodid doonorrakkude kinnitamiseks konteineritesse.
See optimeerimisprobleemi sõnastus ei ole uus ja seda on uurinud paljud matemaatikud alates eelmise sajandi 80ndate algusest. Väliskirjanduses on sobiva matemaatilise mudeliga kaks optimeerimisülesannet: и (ülesannete erinevustest räägime hiljem). Väärib märkimist, et matemaatilises kirjanduses on sellise kahe optimeerimisülesande sõnastus sõnastatud ettevõtete kohapealse asukoha järgi, sellest ka nimetus „rajatise asukoht”. Enamasti on see austusavaldus traditsioonidele, sest esimest korda tekkis vajadus selliste kombinatoorsete probleemide lahendamiseks eelmise sajandi 50ndatel logistikavaldkonnast, peamiselt sõjatööstussektorist. Ettevõtte asukoha osas on sellised ülesanded sõnastatud järgmiselt:
- Linnasid, kuhu on potentsiaalselt võimalik paigutada tootmisettevõtteid (edaspidi tootmislinnad), on piiratud arv. Iga tootmislinna kohta on täpsustatud selles ettevõtte avamise kulud, samuti selles avatud ettevõtte tootmisvõimsuse piirang.
- On olemas piiratud hulk linnu, kus kliendid tegelikult asuvad (edaspidi klientlinnad). Iga sellise kliendilinna jaoks määratakse toodete nõudluse maht. Lihtsuse huvides eeldame, et on ainult üks toode, mida ettevõtted toodavad ja tarbijad tarbivad.
- Iga linn-tootja ja linn-kliendi paari kohta on märgitud transpordikulude väärtus vajaliku koguse toodete tarnimiseks tootjalt kliendile.
Peate leidma, millistes linnades ettevõtteid avada ja kuidas selliste ettevõtetega kliente siduda, et:
- Ettevõtete avamise kogukulud ja transpordikulud olid minimaalsed;
- Ühegi avatud ettevõtte klientide nõudluse maht ei ületanud selle ettevõtte tootmisvõimsust.
Nüüd tasub mainida nende kahe klassikalise probleemi ainsat erinevust:
- Ühe allika mahuga rajatise asukohaprobleem – klienti varustatakse ainult ühest avatud rajatisest;
- Mitme allika mahuga rajatise asukohaprobleem – klienti saab korraga varustada mitmest avatud rajatisest.
Selline erinevus kahe probleemi vahel on esmapilgul tähtsusetu, kuid tegelikult viib selliste probleemide täiesti erineva kombinatoorse struktuurini ja sellest tulenevalt täiesti erinevatele algoritmidele nende lahendamiseks. Ülesannete erinevused on näidatud alloleval joonisel.
Joonis 3. a) Mitme allika mahuga rajatise asukohaprobleem
Joonis 3. b) Ühe allika mahutatava rajatise asukoha probleem
Mõlemad ülesanded -raske, st puudub täpne algoritm, mis sisendandmete suuruse ajapolünoomis sellise ülesande lahendaks. Lihtsamalt öeldes töötavad kõik täpsed algoritmid probleemi lahendamiseks eksponentsiaalse aja jooksul, ehkki võib-olla kiiremini kui valikute täielik otsimine. Alates ülesandest -raske, siis võtame arvesse ainult ligikaudset heuristikat, st algoritme, mis arvutavad järjekindlalt optimaalsele väga lähedased lahendused ja töötavad üsna kiiresti. Kel huvi sellise ülesande vastu, siis hea venekeelse ülevaate leiab siit.
Kui minna üle meie probleemi terminoloogiale, mis käsitleb kaupade optimaalset kokkusurumist rakkudes, siis:
- kliendilinnad on doonorrakud ülejäänud kaubaga,
- tootmislinnad – konteinerrakud , millesse peaks paigutama teiste lahtrite jäägid,
- transpordikulud - ajakulu laopidaja kaubamahu doonorrakust teisaldamiseks konteineri lahtrisse ;
- ettevõtte avamise kulud - konteineri valimise kulud , võrdne konteineri lahtri mahuga , korrutatuna kindla koefitsiendiga vabade mahtude säästmiseks (koefitsiendi väärtus on alati > 1) (vt sisendandmete ettevalmistamise osa).
Pärast ülesande üldtuntud klassikaliste lahendustega analoogia loomist on vaja vastata olulisele küsimusele, millest sõltub lahendusalgoritmi arhitektuuri valik: jääkide teisaldamine doonorrakust on võimalik ainult ühte ja ainult ühte konteinerisse. (Ühe allikaga) või on võimalik ülejäänuid teisaldada mitmesse konteineri lahtrisse (Multi-Source)?
Väärib märkimist, et praktikas leiavad aset mõlemad probleemi sõnastused. Allpool esitame iga sellise seadistuse kõik plussid ja miinused:
| Probleemne variant | Võimaluse plussid | Valiku miinused |
|---|---|---|
| Ühe allikaga | Selle probleemi variandi abil arvutatud kauba liikumise toimingud:
|
|
| Mitme allikaga | Probleemi selle versiooni abil arvutatud tihendused on tavaliselt 10–15% kompaktsemad võrreldes suvandi "Ühe allika" abil arvutatud tihendustega. Kuid märgime ka, et mida väiksem on jääkide arv doonorrakkudes, seda väiksem on erinevus kompaktsuses | Selle probleemi variandi abil arvutatud kauba liikumise toimingud:
|
Tabel 1. Ühe allika ja mitme allika valikute plussid ja miinused.
Kuna Single-Source valikul on rohkem eeliseid ning arvestades ka seda, et mida väiksem on jääkide arv doonorrakkudes, seda väiksem on ülesande mõlema variandi puhul arvutatud tihendusastme erinevus, langes meie valik Ühe allika valik. Allikas.
Tasub öelda, et ka mitme allika valiku lahendus leiab aset. Selle lahendamiseks on suur hulk tõhusaid algoritme, millest enamik taandub mitmete transpordiprobleemide lahendamisele. Samuti pole mitte ainult tõhusaid algoritme, vaid ka elegantseid, näiteks
Sisendandmete ettevalmistamine
Enne probleemi lahendamiseks analüüsima ja algoritmi väljatöötamist on vaja otsustada, milliseid andmeid ja millisel kujul me neid sisendina toidame. Doonorkambrisse jääva kauba mahu ja konteinerkambrite mahutavuse osas probleeme pole, kuna see on triviaalne - selliseid koguseid mõõdetakse m3-des, aga konteinerkambri kasutamise ja kolimiskulu maatriksi kuludega mitte kõike. on nii lihtne!
Vaatame kõigepealt arvutust kaupade teisaldamise kulud doonorrakust konteinerrakku. Kõigepealt tuleb otsustada, millistes mõõtühikutes liikumiskulusid arvutame. Kaks kõige ilmsemat valikut on meetrid ja sekundid. Sõidukulusid "puhastes" meetrites pole mõtet arvutada. Näitame seda näitega. Laske rakku asub esimesel astmel, lahtris eemaldatud 30 meetri võrra ja asub teisel astmel:
- Kolimine в kallim kui kolida в , kuna teiselt astmelt (1,5–2 meetrit põrandast) alla laskumine on lihtsam kui teisele, kuigi vahemaa on sama;
- Liiguta 1 tk. kaubad rakust в See on lihtsam kui 10 tükki teisaldada. sama toode, kuigi vahemaa on sama.
Parem on arvestada kolimiskuludega sekunditega, kuna see võimaldab teil arvestada nii tasandite erinevust kui ka teisaldatud kaupade koguse erinevust. Et arvestada liikumise maksumust sekundites, peame jagama liikumisoperatsiooni elementaarkomponentideks ja võtma iga elementaarkomponendi täitmiseks ajamõõtmisi.
Lase kambrist välja liigub PC. kaubad konteineris ... Las olla – töötaja keskmine liikumiskiirus laos, mõõdetuna m/sek. Lase и – ühekordsete toimingute keskmised kiirused võetakse ja pannakse vastavalt kaubamahule, mis on võrdne 4 dm3 (keskmine maht, mille töötaja korraga laos toimingu tegemisel võtab). Lase и lahtrite kõrgus, millest vastavalt võtmist ja panemist sooritatakse. Näiteks esimese astme (põranda) keskmine kõrgus on 1 m, teise astme kõrgus 2 m jne. Siis on teisaldamistoimingu tegemiseks kuluva koguaja arvutamise valem järgmine:
Tabelis 2 on laotöötajate poolt kogutud statistika iga elementaarse toimingu sooritamise aja kohta, võttes arvesse ladustatava kauba eripära.
| operatsiooni nimi | Nimetus | Tähendab |
|---|---|---|
| Laos ringi liikuva töötaja keskmine kiirus | |
1,5 m/s |
| Ühe paigaldamise keskmine kiirus (toote mahuga 4 dm3) | |
2,4 sek |
Tabel 2. Keskmine laotoimingute sooritamise aeg
Oleme otsustanud kolimiskulude arvestamise meetodi. Nüüd peame välja mõtlema, kuidas arvutada konteinerelemendi valimise kulud. Siin on kõik palju-palju keerulisem kui kolimiskuludega, sest:
- esiteks peaksid kulud sõltuma otseselt raku mahust - sama kogus doonorrakkudest ülekantud jääke on parem paigutada väiksema mahuga mahutisse kui suurde konteinerisse, eeldusel, et selline maht mahub täielikult mõlemasse konteinerisse . Seega, minimeerides konteinerite valimise kogukulusid, püüame säästa valikualal “nappi” vaba lao mahtu, et teha järgnevaid kaupade lahtritesse paigutamise toiminguid. Joonisel 4 on näidatud jääkide suur- ja väikekonteinerite teisaldamise võimalused ning nende ülekandevõimaluste tagajärjed järgnevatel laotoimingutel.
- teiseks, kuna algse probleemi lahendamisel on vaja minimeerida täpselt kogukulud ja see on nii kolimiskulude kui ka konteinerite valimise kulude summa, siis tuleb rakkude mahud kuupmeetrites kuidagi seostada sekunditega, mis pole kaugeltki triviaalne.
Riis. 4. Võimalused ülejääkide teisaldamiseks erineva mahutavusega konteineritesse.
Joonisel 4 on punaselt kujutatud jääkide maht, mis järgnevate kaupade paigutamise teises etapis enam konteinerisse ei mahu.
See aitab siduda konteineri valimise kulud kuupmeetrite kuludega sekundite kuludega probleemi arvutatud lahenduste jaoks:
- Doonorkasti jäägid tuleb igal juhul konteinerkasti viia, kui see vähendab toodet sisaldavate konteinerite koguarvu.
- Konteinerite mahu ja kolimisele kuluva aja vahel tuleb säilitada tasakaal: näiteks kui mingi probleemi uues lahenduses võrreldes eelmise lahendusega on mahu juurdekasv suur, ajakadu aga väike. , siis on vaja valida uus valik.
Alustame viimasest nõudest. Mitmetähendusliku sõna “bilanss” selgitamiseks viisime laotöötajate seas läbi küsitluse, et selgitada välja järgmist. Olgu mahuga konteinerlahter , millele on määratud doonorrakkudest järelejäänud kauba liikumine ja sellise liikumise koguaeg on võrdne . Olgu samadest doonorrakkudest sama koguse kauba paigutamiseks teistesse konteineritesse mitu alternatiivset võimalust, kus igal paigutusel on oma hinnangud Kus < и Kus >.
Esitatakse küsimus: milline on minimaalne mahukasv vastuvõetav, antud ajakao väärtuse jaoks ? Selgitame näitega. Esialgu pidi säilmed paigutama 1000 dm3 (1 m3) mahuga konteinerisse ja ülekandeaeg oli 70 sekundit. Võimalus on panna jäägid teise konteinerisse mahuga 500 dm3 ja aega 130 sekundit. Küsimus: kas oleme valmis kulutama täiendavalt 60 sekundit laopidaja ajast kauba teisaldamisele, et säästa 500 dm3 vaba mahtu? Laotöötajate küsitluse tulemuste põhjal koostati järgmine diagramm.
Riis. 5. Lubatava minimaalse mahusäästu sõltuvuse skeem tööaja erinevuse suurenemisest
See tähendab, et kui lisaajakulu on 40 sekundit, siis oleme valmis neid kulutama alles siis, kui mahuvõit on vähemalt 500 dm3. Vaatamata asjaolule, et sõltuvuses on väike mittelineaarsus, eeldame edasiste arvutuste lihtsuse huvides, et suuruste vaheline sõltuvus on lineaarne ja seda kirjeldab ebavõrdsus
Alloleval joonisel käsitleme järgmisi kauba konteineritesse paigutamise meetodeid.
Riis. 6. Variant (a): 2 konteinerit, kogumaht 400 dm3, koguaeg 150 sek.
Riis. 6. Variant (b): 2 konteinerit, kogumaht 600 dm3, koguaeg 190 sek.
Riis. 6. Variant (c): 1 konteiner, kogumaht 400 dm3, koguaeg 200 sek.
Variant (a) konteinerite valimisel on eelistatavam kui algne variant, kuna ebavõrdsus kehtib: (800-400)/10>=150-120, mis tähendab 40 >= 30. Variant (b) on vähem eelistatud kui originaal variant , kuna ebavõrdsus ei kehti: (800-600)/10>=190-150, mis tähendab 20 >= 40. Kuid variant (c) sellisesse loogikasse ei sobi! Vaatleme seda võimalust üksikasjalikumalt. Ühelt poolt on ebavõrdsus (800-400)/10>=200-120, mis tähendab, et ebavõrdsus 40 >= 80 ei ole täidetud, mis viitab sellele, et mahu juurdekasv ei ole ajas nii suurt kaotust väärt.
Kuid teisest küljest ei vähenda me selle valiku (c) puhul mitte ainult hõivatud kogumahtu, vaid ka hõivatud lahtrite arvu, mis on esimene kahest olulisest nõudest ülaltoodud probleemide arvutuslike lahenduste jaoks. Ilmselgelt on selle nõude täitmiseks vaja ebavõrdsuse vasakule küljele lisada mõni positiivne konstant , ja selline konstant tuleb lisada alles siis, kui konteinerite arv väheneb. Tuletame teile seda meelde on muutuja, mis on võrdne 1-ga, kui konteiner valitud ja konteineri puhul 0 pole valitud. Tähistagem – palju mahuteid alglahuses ja – uues lahenduses palju konteinereid. Üldiselt näeb uus ebavõrdsus välja selline:
Teisendades ülaltoodud ebavõrdsust, saame
Selle põhjal on meil kogumaksumuse arvutamise valem mingi lahendus probleemile:
Nüüd aga tekib küsimus: mis väärtus peaks sellisel konstandil olema? ? Ilmselgelt peab selle väärtus olema piisavalt suur, et esimene nõue probleemi lahendamiseks oleks alati täidetud. Muidugi võite võtta konstandi väärtuseks 103 või 106, kuid ma tahaksin selliseid “maagilisi numbreid” vältida. Kui arvestada laotoimingute teostamise spetsiifikat, saame sellise konstandi väärtuse kohta välja arvutada mitu põhjendatud arvulist hinnangut.
Laskma – ühe tsooni ABC laorakkude vaheline maksimaalne kaugus, mis on meie puhul võrdne 100 m – konteinerkambri maksimaalne maht laos, meie puhul võrdne 1000 dm3.
Esimene viis väärtuse arvutamiseks . Vaatleme olukorda, kus esimesel astmel on 2 konteinerit, milles kaup juba füüsiliselt asub, st nad ise on doonorrakud ja kauba samadesse lahtritesse viimise kulu on loomulikult 0. on vajalik konstandi sellise väärtuse leidmiseks , milles oleks kasulik ülejäägid alati konteinerist 1 konteinerisse 2 teisaldada. Väärtuste asendamine и Ülaltoodud ebavõrdsuses saame:
millest järeldub
Asendades ülaltoodud valemiga elementaartoimingute sooritamise keskmise aja väärtused, saame
Teine viis väärtuse arvutamiseks . Vaatleme olukorda, kus on doonorrakud, millest on plaanis kaup konteinerisse toimetada 1. Tähistame – kaugus doonorrakust konteinerisse 1. Seal on ka konteiner 2, mis juba sisaldab kaupu ja mille maht võimaldab mahutada kõik ülejäänud rakud. Lihtsuse huvides eeldame, et doonorrakkudest konteineritesse viidud kaupade maht on sama ja võrdne . On vaja leida selline konstandi väärtus , kuhu on paigutatud kõik jäägid alates rakkude paigutamine konteinerisse 2 oleks alati tulusam kui paigutada need erinevatesse konteineritesse:
Saadud ebavõrdsuse teisendamine
Et koguse väärtust “tugevdada”. , oletame seda = 0. Laojääkide tihendamise protseduuris tavaliselt kaasatud lahtrite keskmine arv on 10. Asendades koguste teadaolevad väärtused, saame järgmise konstandi väärtuse
Võtame iga variandi jaoks arvutatud suurima väärtuse, see on koguse väärtus antud laoparameetrite jaoks. Nüüd paneme täielikkuse huvides kirja kogukulude arvutamise valemi mõne teostatava lahenduse jaoks :
Nüüd ju Heraklese pingutused Sisendandmeid teisendades saame öelda, et kõik sisendandmed on teisendatud soovitud kujule ja on optimeerimisalgoritmis kasutamiseks valmis.
Järeldus
Nagu praktika näitab, alahinnatakse sageli algoritmi sisendandmete ettevalmistamise ja teisendamise etapi keerukust ja tähtsust. Selles artiklis pöörasime just sellele etapile palju tähelepanu, et näidata, et ainult kvaliteetsed ja arukalt koostatud sisendandmed võivad muuta algoritmi järgi arvutatud otsused kliendi jaoks tõeliselt väärtuslikuks. Jah, valemite tuletusi oli palju, aga hoiatasime juba enne katat :)
Järgmises artiklis jõuame lõpuks selleni, milleks olid mõeldud 2 eelmist väljaannet – diskreetse optimeerimisalgoritmi.
Valmistas artikli ette
Roman Shangin, projektide osakonna programmeerija,
Firma First Bit, Tšeljabinsk
Allikas: www.habr.com