I denne artikkelen vil vi fortelle deg hvordan vi løste problemet med mangel på ledige celler i et lager og utviklingen av en diskret optimaliseringsalgoritme for å løse et slikt problem. La oss snakke om hvordan vi "bygde" den matematiske modellen for optimaliseringsproblemet, og om vanskelighetene vi uventet møtte når vi behandlet inndata for algoritmen.
Hvis du er interessert i anvendelser av matematikk i næringslivet og du ikke er redd for rigide identitetstransformasjoner av formler på 5. klassetrinn, så velkommen til katten!
Artikkelen vil være nyttig for de som implementerer WMS-systemer, jobber i lager- eller produksjonslogistikkindustrien, samt programmerere som er interessert i anvendelser av matematikk i virksomheten og optimalisering av prosesser i en bedrift.
Innledende del
Denne publikasjonen fortsetter serien med artikler der vi deler vår vellykkede erfaring med implementering av optimaliseringsalgoritmer i lagerprosesser.
В beskriver detaljene for lageret der vi implementerte WMS-system, og forklarer også hvorfor vi trengte å løse problemet med å gruppere partier av gjenværende varer under implementering WMS-systemer, og hvordan vi gjorde det.
Da vi var ferdige med å skrive artikkelen om optimaliseringsalgoritmer, viste den seg å være veldig stor, så vi bestemte oss for å dele det akkumulerte materialet i 2 deler:
- I den første delen (denne artikkelen) vil vi snakke om hvordan vi "bygde" den matematiske modellen av problemet, og om de store vanskelighetene vi uventet møtte når vi behandlet og transformerte inndataene for algoritmen.
- I den andre delen vil vi vurdere i detalj implementeringen av algoritmen i språket C + +, vil vi gjennomføre et beregningseksperiment og oppsummere erfaringen vi fikk under implementeringen av slike "intelligente teknologier" i kundens forretningsprosesser.
Hvordan lese en artikkel. Hvis du leser den forrige artikkelen, kan du umiddelbart gå til kapittelet "Oversikt over eksisterende løsninger"; hvis ikke, er beskrivelsen av problemet som løses i spoileren nedenfor.
Beskrivelse av problemet som løses på kundens lager
Flaskehals i prosesser
I 2018 fullførte vi et prosjekt for å implementere WMS-systemer på lageret “Trading House “LD” i Chelyabinsk. Vi implementerte produktet "1C-Logistics: Warehouse Management 3" for 20 arbeidsplasser: operatører WMS, lagerholdere, gaffeltrucksjåfører. Gjennomsnittlig lager er ca. 4 tusen m2, antall celler er 5000 og antall SKUer er 4500. Lageret lagrer kuleventiler av egen produksjon i forskjellige størrelser fra 1 kg til 400 kg. Varelageret på lageret lagres i partier, siden det er behov for å velge varer etter FIFO.
Under utformingen av lagerprosessautomatiseringsordninger ble vi møtt med det eksisterende problemet med ikke-optimal lagerlagring. Spesifikasjonene for lagring og legging av kraner er slik at én enhetslagringscelle kun kan inneholde gjenstander fra én batch (se fig. 1). Produktene ankommer lageret daglig og hver ankomst er et eget parti. Totalt, som et resultat av 1 måneds lagerdrift, opprettes 30 separate batcher, til tross for at hver skal lagres i en egen celle. Produkter velges ofte ikke i hele paller, men i stykker, og som et resultat, i stykkvalgssonen i mange celler, observeres følgende bilde: i en celle med et volum på mer enn 1 m3 er det flere stykker kraner som opptar mindre enn 5-10 % av cellevolumet.
Fig 1. Foto av flere deler i en celle
Det er tydelig at lagringskapasiteten ikke utnyttes optimalt. For å forestille meg omfanget av katastrofen, kan jeg gi tall: I gjennomsnitt er det fra 1 til 3 celler av slike celler med et volum på mer enn 100 m300 med "minuskulære" balanser i forskjellige perioder av lagerets drift. Siden lageret er relativt lite, blir denne faktoren en "flaskehals" i løpet av de travle sesongene på lageret, og bremser i stor grad lagerprosessene for aksept og forsendelse.
Problemløsning idé
En idé oppsto: partier med rester med de nærmeste datoene skulle reduseres til én enkelt batch, og slike rester med en enhetlig batch skulle plasseres kompakt sammen i én celle, eller i flere, hvis det ikke er nok plass i én til å romme hele mengden rester. Et eksempel på slik "komprimering" er vist i figur 2.
Fig.2. Skjema for å komprimere rester i celler
Dette lar deg redusere den okkuperte lagerplassen som vil bli brukt til nye varer som skal plasseres betydelig. I en situasjon der lagerkapasiteten er overbelastet, er et slikt tiltak ekstremt nødvendig, ellers kan det rett og slett ikke være nok ledig plass til å ta imot nye varer, noe som vil føre til stopp i lagerprosessene for plassering og etterfylling, og som en konsekvens, til stopp i aksept og forsendelse. Tidligere, før implementeringen av WMS-systemet, ble en slik operasjon utført manuelt, noe som var ineffektivt, siden prosessen med å søke etter passende balanser i celler var ganske lang. Nå, med introduksjonen av et WMS-system, bestemte vi oss for å automatisere prosessen, øke hastigheten og gjøre den intelligent.
Prosessen med å løse et slikt problem er delt inn i 2 stadier:
- på det første stadiet finner vi grupper med partier som nærmer seg dato for komprimering (dedikert til denne oppgaven );
- på det andre trinnet, for hver gruppe med partier, beregner vi den mest kompakte plasseringen av de gjenværende varene i cellene.
I den nåværende artikkelen vil vi fokusere på den andre fasen av algoritmen.
Gjennomgang av eksisterende løsninger
Før vi går videre til beskrivelsen av algoritmene vi har utviklet, er det verdt å gi en kort oversikt over systemer som allerede eksisterer på markedet WMS, som implementerer lignende optimal komprimeringsfunksjonalitet.
Først av alt er det nødvendig å merke seg produktet “1C: Enterprise 8. WMS Logistics. Warehouse management 4", som eies og kopieres av 1C og tilhører fjerde generasjon WMS-systemer utviklet av AXELOT. Dette systemet krever komprimeringsfunksjonalitet, som er designet for å forene ulike produktrester i én felles celle. Det er verdt å nevne at komprimeringsfunksjonaliteten i et slikt system også inkluderer andre muligheter, for eksempel å korrigere plassering av varer i celler i henhold til deres ABC-klasser, men vi vil ikke dvele ved dem.
Hvis du analyserer koden til 1C: Enterprise 8. WMS Logistikk-systemet. Lagerstyring 4" (som er åpen i denne delen av funksjonaliteten), kan vi konkludere med følgende. Restkompresjonsalgoritmen implementerer en ganske primitiv lineær logikk og det kan ikke være snakk om noen "optimal" komprimering. Naturligvis sørger det ikke for gruppering av partier. Flere klienter som fikk implementert et slikt system klaget på resultatene av kompresjonsplanlegging. For eksempel oppsto ofte i praksis under kompresjon følgende situasjon: 100 stk. Det er planlagt å flytte gjenværende gods fra en celle til en annen celle, hvor 1 stk er plassert. varer, selv om det er optimalt fra et tidsforbrukssynspunkt å gjøre det motsatte.
Også funksjonaliteten til å komprimere de gjenværende varene i celler er deklarert i mange fremmede land. WMS-systemer, men vi har dessverre ingen reell tilbakemelding på effektiviteten til algoritmene (dette er en forretningshemmelighet), og langt mindre en idé om dybden av deres logikk (proprietær programvare med lukket kildekode), så vi kan ikke bedømme.
Søk etter en matematisk modell av problemet
For å designe algoritmer av høy kvalitet for å løse et problem, er det først nødvendig å tydelig formulere dette problemet matematisk, og det er det vi vil gjøre.
Det er mange celler , som inneholder rester av noen varer. I det følgende vil vi kalle slike celler donorceller. La oss betegne volum av varer i cellen $.
Det er viktig å si at bare ett produkt av en batch, eller flere batcher tidligere kombinert til en klynge (les: ), som skyldes spesifikasjonene for lagring og lagring av varer. Ulike produkter eller forskjellige batch-klynger bør kjøre sin egen separate komprimeringsprosedyre.
Det er mange celler , hvori rester fra donorceller potensielt kan plasseres. Vi vil videre kalle slike celler for beholderceller. Disse kan enten være ledige celler på lageret eller donorceller fra en rekke . Alltid nok er en delmengde .
For hver celle fra mange Kapasitetsbegrensninger er satt , målt i dm3. En dm3 er en kube med sider på 10 cm Produktene som er lagret på lageret er ganske store, så i dette tilfellet er en slik diskretisering ganske nok.
Gitt en matrise med korteste avstander i meter mellom hvert cellepar Der и tilhører sett и henholdsvis.
La oss betegne «kostnader» ved å flytte varer fra cellen inn i en celle . La oss betegne "kostnader" ved å velge en container å flytte rester fra andre celler inn i den. Hvordan nøyaktig og i hvilke måleenheter vil verdiene beregnes и vi vil vurdere videre (se avsnittet som forbereder inngangsdata), for nå er det nok å si at slike verdier vil være direkte proporsjonale med verdiene и henholdsvis.
La oss betegne med en variabel som tar verdien 1 hvis resten er fra cellen flyttet til container , og 0 ellers. La oss betegne med en variabel som tar verdien 1 hvis beholderen inneholder de resterende varene, og 0 ellers.
Oppgaven er angitt som følger: du må finne så mange beholdere og dermed "feste" donorceller til beholderceller for å minimere funksjonen
under restriksjoner
Totalt sett, når vi beregner løsningen på problemet, streber vi etter å:
- for det første for å spare lagringskapasitet;
- for det andre for å spare butikkeieres tid.
Den siste begrensningen betyr at vi ikke kan flytte varer inn i en container som vi ikke har valgt, og derfor ikke har "påført kostnader" for å velge den. Denne begrensningen betyr også at volumet av varer som flyttes fra cellene til containeren ikke skal overstige containerens kapasitet. Med å løse et problem mener vi et sett med containere og metoder for å feste donorceller til beholdere.
Denne formuleringen av optimaliseringsproblemet er ikke ny, og har blitt studert av mange matematikere siden tidlig på 80-tallet av forrige århundre. I utenlandsk litteratur er det 2 optimaliseringsproblemer med en passende matematisk modell: и (vi skal snakke om forskjellene i oppgaver senere). Det er verdt å si at i den matematiske litteraturen er formuleringen av slike to optimaliseringsproblemer formulert i form av plasseringen av virksomheter på bakken, derav navnet "Facility Location". For det meste er dette en hyllest til tradisjonen, siden behovet for å løse slike kombinatoriske problemer for første gang kom fra logistikkfeltet, mest fra den militærindustrielle sektoren på 50-tallet av forrige århundre. Når det gjelder bedriftens plassering, er slike oppgaver formulert som følger:
- Det er et begrenset antall byer hvor det potensielt er mulig å lokalisere produksjonsbedrifter (heretter kalt produksjonsbyer). For hver produksjonsby er kostnadene ved å åpne et foretak i den spesifisert, samt en begrensning på produksjonskapasiteten til bedriften som er åpnet i den.
- Det er et begrenset sett med byer hvor klienter faktisk befinner seg (heretter kalt klientbyer). For hver slik kundeby er volumet av etterspørselen etter produkter spesifisert. For enkelhets skyld vil vi anta at det kun er ett produkt som produseres av bedrifter og konsumeres av kunder.
- For hvert par by-produsent og by-klient spesifiseres verdien av transportkostnadene for å levere det nødvendige volumet av produkter fra produsenten til kunden.
Du må finne i hvilke byer du skal åpne virksomheter og hvordan du knytter kunder til slike virksomheter for å:
- De totale kostnadene ved å åpne foretak og transportkostnadene var minimale;
- Etterspørselsvolumet fra kunder som er tilordnet et åpent foretak, oversteg ikke produksjonskapasiteten til det foretaket.
Nå er det verdt å nevne den eneste forskjellen i disse to klassiske problemene:
- Single-Source Capacitated Facility Location Problem – klienten forsynes fra kun ett åpent anlegg;
- Multi-Source Capacitated Facility Location Problem – klienten kan forsynes fra flere åpne anlegg samtidig.
En slik forskjell mellom de to problemene er ubetydelig ved første øyekast, men fører faktisk til helt forskjellige kombinatoriske strukturer av slike problemer og, som en konsekvens, til helt forskjellige algoritmer for å løse dem. Forskjellene mellom oppgavene er vist i figuren under.
Fig.3. a) Problem med plassering av anlegg med flere kilder
Fig.3. b) Problem med plassering av anlegg med én kilde
Begge oppgavene -vanskelig, det vil si at det ikke er noen eksakt algoritme som vil løse et slikt problem i et tidspolynom i størrelsen på inngangsdataene. Med enklere ord vil alle eksakte algoritmer for å løse et problem fungere i eksponentiell tid, men kanskje raskere enn et fullstendig søk etter alternativer. Siden oppgaven -vanskelig, da vil vi kun vurdere omtrentlige heuristikk, det vil si algoritmer som konsekvent vil beregne løsninger veldig nært optimale og vil fungere ganske raskt. Er du interessert i en slik oppgave, kan du finne en god oversikt på russisk her.
Hvis vi skifter til terminologien for problemet vårt med optimal komprimering av varer i celler, så:
- klientbyer er giverceller med de resterende varene,
- produksjonsbyer – containerceller , der restene fra andre celler skal plasseres,
- transportkostnader - tidskostnader lagerholder for å flytte varevolumet fra givercellen inn i en beholdercelle ;
- kostnader ved å åpne en bedrift - kostnader ved valg av container , lik volumet av beholdercellen , multiplisert med en viss koeffisient for å lagre ledige volumer (verdien av koeffisienten er alltid > 1) (se avsnittet forbereder inngangsdata).
Etter at analogien med de velkjente klassiske løsningene av problemet er tegnet, er det nødvendig å svare på et viktig spørsmål som valget av løsningsalgoritmearkitektur avhenger av: flytting av restene fra donorcellen er bare mulig til én og bare én beholder (Single-Source), eller er det mulig å flytte restene inn i flere containerceller (Multi-Source)?
Det er verdt å merke seg at i praksis finner begge problemformuleringene sted. Vi presenterer alle fordeler og ulemper for hver slik innstilling nedenfor:
| Problemvariant | Fordeler med alternativet | Ulemper med alternativet |
|---|---|---|
| Eneste kilde | Varebevegelsesoperasjoner beregnet ved å bruke denne varianten av problemet:
|
|
| Multikilde | Kompresjoner beregnet ved hjelp av denne versjonen av problemet er vanligvis 10-15 % mer kompakte sammenlignet med komprimeringer beregnet ved bruk av "Single-Source"-alternativet. Men vi legger også merke til at jo mindre antall rester i donorcellene er, jo mindre er forskjellen i kompakthet | Varebevegelsesoperasjoner beregnet ved å bruke denne varianten av problemet:
|
Tabell 1. Fordeler og ulemper med alternativer med én kilde og flere kilder.
Siden Single-Source-alternativet har flere fordeler, og også tatt i betraktning at jo mindre antall rester i donorceller, jo mindre forskjell i graden av kompresjonskompakthet beregnet for begge varianter av problemet, falt vårt valg på alternativet Single-Source.Kilde.
Det er verdt å si at løsningen på Multi-Source-alternativet også finner sted. Det finnes et stort antall effektive algoritmer for å løse det, hvorav de fleste går ut på å løse en rekke transportproblemer. Det er heller ikke bare effektive algoritmer, men også elegante, for eksempel,
Forbereder inndata
Før du begynner å analysere og utvikle en algoritme for å løse et problem, er det nødvendig å bestemme hvilke data og i hvilken form vi skal mate dem som input. Det er ingen problemer med volumet av gjenværende varer i donorceller og kapasiteten til containerceller, siden dette er trivielt - slike mengder vil bli målt i m3, men med kostnadene ved å bruke en containercelle og flyttekostnadsmatrisen, ikke alt er så enkelt!
La oss først se på regnestykket kostnader ved å flytte varer fra donorcellen til beholdercellen. Først av alt er det nødvendig å bestemme i hvilke måleenheter vi vil beregne kostnadene ved bevegelse. De to mest åpenbare alternativene er meter og sekunder. Det gir ingen mening å beregne reisekostnader i "rene" meter. La oss vise dette med et eksempel. La cellen plassert på første lag, celle fjernet med 30 meter og plassert på andre nivå:
- Flytter fra в dyrere enn å flytte fra в , siden det å gå ned fra det andre nivået (1,5-2 meter fra gulvet) er lettere enn å gå opp til det andre, selv om avstanden vil være den samme;
- Flytt 1 stk. varer fra cellen в Det vil være lettere enn å flytte 10 stykker. samme produkt, selv om avstanden vil være den samme.
Det er bedre å vurdere flyttekostnader på sekunder, siden dette lar deg ta hensyn til både forskjellen i nivåer og forskjellen i mengde varer som flyttes. For å ta høyde for kostnadene ved bevegelse i sekunder, må vi dekomponere bevegelsesoperasjonen i elementære komponenter og ta tidsmålinger for utførelsen av hver elementær komponent.
Slipp fra cellen beveger seg PC. varer i container . Let – gjennomsnittlig bevegelseshastighet for en arbeider på lageret, målt i m/sek. La и – gjennomsnittshastigheter for engangsoperasjoner henholdsvis ta og sette for et varevolum lik 4 dm3 (gjennomsnittlig volum som en ansatt tar om gangen på et lager når han utfører operasjoner). La и høyden på cellene som henholdsvis take og put-operasjonene utføres fra. For eksempel er gjennomsnittshøyden på det første laget (etasjen) 1 m, det andre laget er 2 m, etc. Da er formelen for å beregne den totale tiden for å fullføre en flytteoperasjon neste:
Tabell 2 viser statistikk over utførelsestiden for hver elementær operasjon, samlet inn av lageransatte, tatt i betraktning detaljene til de lagrede varene.
| navnet på operasjonen | Betegnelse | Mener |
|---|---|---|
| Gjennomsnittlig hastighet for en arbeider som beveger seg rundt på lageret | |
1,5 m/s |
| Gjennomsnittlig hastighet på én operasjon å sette (for et produktvolum på 4 dm3) | |
2,4 sek |
Tabell 2. Gjennomsnittlig tid til å fullføre lagerdrift
Vi har bestemt oss for metode for å beregne kostnadene ved flytting. Nå må vi finne ut hvordan vi skal beregne kostnader ved valg av containercelle. Alt her er mye, mye mer komplisert enn med flyttekostnader, fordi:
- For det første bør kostnadene være direkte avhengige av volumet til cellen - det samme volumet av rester som overføres fra donorceller er bedre plassert i en beholder med et mindre volum enn i en stor beholder, forutsatt at slikt volum passer helt inn i begge beholderne. Ved å minimere de totale kostnadene ved å velge containere, forsøker vi å spare "knappe" ledig lagringskapasitet i utvalgsområdet for å utføre påfølgende operasjoner med å plassere varer i celler. Figur 4 viser alternativene for å overføre rester til store og små beholdere og konsekvensene av disse overføringsmulighetene i etterfølgende lagerdrift.
- for det andre, siden vi for å løse det opprinnelige problemet må minimere nøyaktig de totale kostnadene, og dette er summen av både flyttingskostnadene og kostnadene ved å velge containere, så må cellevolumene i kubikkmeter på en eller annen måte være knyttet til sekunder, som er langt fra trivielt.
Ris. 4. Muligheter for å flytte rester til beholdere med ulik kapasitet.
Figur 4 viser i rødt volumet av rester som ikke lenger passer inn i beholderen i det andre trinnet med å plassere påfølgende varer.
Det vil bidra til å koble kubikkmeter kostnadene for å velge en container med sekunder av kostnader for å flytte følgende krav til beregnede løsninger på problemet:
- Det er uansett nødvendig at saldoene fra giverbingen flyttes til beholderen dersom dette reduserer det totale antallet beholderbinger som inneholder produktet.
- Det er nødvendig å opprettholde en balanse mellom volumet av containere og tiden brukt på å flytte: for eksempel, hvis i en ny løsning på et problem sammenlignet med den forrige løsningen, er volumgevinsten stor, men tapet i tid er lite , så er det nødvendig å velge et nytt alternativ.
La oss starte med det siste kravet. For å tydeliggjøre det tvetydige ordet «balanse», gjennomførte vi en undersøkelse blant lageransatte for å finne ut følgende. La det være en beholdercelle med volum , som bevegelsen av gjenværende varer fra donorceller er tilordnet og den totale tiden for slik bevegelse er lik . La det være flere alternative alternativer for å plassere samme mengde varer fra de samme donorcellene i andre beholdere, der hver plassering har sine egne estimater Der < и Der >.
Spørsmålet stilles: hva er minimumsgevinsten i volum akseptabelt for en gitt tidstapsverdi ? La oss forklare med et eksempel. I utgangspunktet skulle restene legges i en beholder med et volum på 1000 dm3 (1 m3) og overføringstiden var 70 sekunder. Det er mulighet for å legge restene i en annen beholder med et volum på 500 dm3 og en tid på 130 sekunder. Spørsmål: er vi klare til å bruke ytterligere 60 sekunder av lagerholderens tid på å flytte varene for å spare 500 dm3 ledig volum? Basert på resultatene fra en undersøkelse blant lageransatte ble følgende diagram satt sammen.
Ris. 5. Diagram over avhengigheten av minimum tillatte volumbesparelser på økningen i forskjellen i driftstiden
Det vil si at hvis de ekstra tidskostnadene er 40 sekunder, er vi klare til å bruke dem bare når volumgevinsten er minst 500 dm3. Til tross for at det er en liten ikke-linearitet i avhengigheten, vil vi for enkelhetens skyld anta at avhengigheten mellom mengdene er lineær og beskrives av ulikheten
I figuren nedenfor tar vi for oss følgende metoder for å plassere varer i containere.
Ris. 6. Alternativ (a): 2 beholdere, totalt volum 400 dm3, total tid 150 sek.
Ris. 6. Alternativ (b): 2 containere, totalt volum 600 dm3, total tid 190 sek.
Ris. 6. Alternativ (c): 1 beholder, totalt volum 400 dm3, total tid 200 sek.
Alternativ (a) for å velge containere er mer å foretrekke enn det opprinnelige alternativet, siden ulikheten gjelder: (800-400)/10>=150-120, som innebærer 40 >= 30. Alternativ (b) er mindre å foretrekke enn originalen alternativ , siden ulikheten ikke holder: (800-600)/10>=190-150 som innebærer 20 >= 40. Men alternativ (c) passer ikke inn i slik logikk! La oss vurdere dette alternativet mer detaljert. På den ene siden er ulikheten (800-400)/10>=200-120, som betyr at ulikheten 40 >= 80 ikke er tilfredsstilt, noe som tyder på at volumgevinsten ikke er verdt et så stort tap over tid.
Men på den annen side, i dette alternativet (c) reduserer vi ikke bare det totale okkuperte volumet, men reduserer også antallet okkuperte celler, som er det første av to viktige krav til beregningsbare løsninger på problemene som er oppført ovenfor. Åpenbart, for at dette kravet skal begynne å bli oppfylt, er det nødvendig å legge til en positiv konstant på venstre side av ulikheten , og en slik konstant må bare legges til når antall beholdere reduseres. La oss minne deg på det er en variabel lik 1 når beholderen valgt, og 0 når beholder ikke valgt. La oss betegne – mange beholdere i den første løsningen og – mange containere i den nye løsningen. Generelt vil den nye ulikheten se slik ut:
Transformere ulikheten ovenfor, får vi
Basert på dette har vi en formel for å beregne totalkostnaden noen løsning på problemet:
Men nå melder spørsmålet seg: hvilken verdi skal en slik konstant ha? ? Det er klart at verdien må være stor nok til at det første kravet til løsninger på problemet alltid er oppfylt. Du kan selvfølgelig ta verdien av konstanten lik 103 eller 106, men jeg vil gjerne unngå slike "magiske tall". Hvis vi vurderer detaljene ved å utføre lageroperasjoner, kan vi beregne flere velbegrunnede numeriske estimater av verdien av en slik konstant.
Let – maksimal avstand mellom lagerceller i én sone ABC, lik i vårt tilfelle 100 m. La – maksimalt volum av en containercelle i et lager, lik i vårt tilfelle 1000 dm3.
Den første måten å beregne verdien på . La oss vurdere en situasjon der det er 2 containere på det første nivået, der varene allerede er fysisk plassert, det vil si at de selv er donorceller, og kostnadene for å flytte varene til de samme cellene er naturlig nok 0. Det er nødvendig for å finne en slik verdi for konstanten , der det vil være fordelaktig å alltid flytte restene fra beholder 1 til beholder 2. Bytte ut verdiene и I ulikheten gitt ovenfor får vi:
som det følger av
Ved å erstatte verdiene for gjennomsnittlig tid for å utføre elementære operasjoner med formelen ovenfor får vi
Den andre måten å beregne verdien på . La oss vurdere en situasjon der det er donorceller som det er planlagt å flytte varene fra til container 1. La oss betegne – avstand fra donorcellen til container 1. Det er også container 2, som allerede inneholder varer, og volumet som lar deg romme resten av alle celler. For enkelhets skyld vil vi anta at volumet av varer som flyttes fra donorceller til containere er det samme og lik . Det kreves å finne en slik verdi av konstanten , der plasseringen av alle rester fra celler i beholder 2 vil alltid være mer lønnsomt enn å plassere dem i forskjellige beholdere:
Forvandler ulikheten vi får
For å "styrke" verdien av kvantumet , la oss anta det = 0. Gjennomsnittlig antall celler som vanligvis er involvert i prosedyren for å komprimere lagersaldoer er 10. Ved å erstatte de kjente verdiene av mengdene, har vi følgende verdi av konstanten
Vi tar den største verdien beregnet for hvert alternativ, dette vil være verdien av kvantumet for de gitte lagerparametrene. Nå, for fullstendighetens skyld, la oss skrive ned formelen for å beregne totale kostnader for en mulig løsning :
Nå, tross alt Herkulisk innsats Ved å transformere inndataene kan vi si at alle inputdata er konvertert til ønsket form og er klare til bruk i optimaliseringsalgoritmen.
Konklusjon
Som praksis viser, er kompleksiteten og viktigheten av stadiet med å forberede og transformere inputdata for en algoritme ofte undervurdert. I denne artikkelen viet vi spesielt mye oppmerksomhet til dette stadiet for å vise at bare høykvalitets og intelligent forberedt inputdata kan gjøre beslutningene beregnet av algoritmen virkelig verdifulle for klienten. Ja, det var mange avledninger av formler, men vi advarte deg allerede før kataen :)
I neste artikkel skal vi endelig komme til hva de 2 tidligere publikasjonene var ment for – en diskret optimaliseringsalgoritme.
Forberedte artikkelen
Roman Shangin, programmerer for prosjektavdelingen,
First Bit-selskap, Chelyabinsk
Kilde: www.habr.com