I den här artikeln kommer vi att berätta hur vi löste problemet med bristen på fria celler i ett lager och utvecklingen av en diskret optimeringsalgoritm för att lösa ett sådant problem. Låt oss prata om hur vi "byggde" den matematiska modellen för optimeringsproblemet och om de svårigheter vi oväntat stötte på när vi behandlade indata för algoritmen.
Om du är intresserad av tillämpningar av matematik i affärer och du inte är rädd för stela identitetstransformationer av formler på 5:e klass nivå, välkommen till katten!
Artikeln kommer att vara användbar för dem som implementerar WMS-system, arbetar inom lager- eller produktionslogistikbranschen, samt programmerare som är intresserade av tillämpningar av matematik i affärer och optimering av processer i ett företag.
Inledande del
Den här publikationen fortsätter serien av artiklar där vi delar vår framgångsrika erfarenhet av att implementera optimeringsalgoritmer i lagerprocesser.
В beskriver detaljerna för lagret där vi implementerade WMS-system, och förklarar också varför vi behövde lösa problemet med att gruppera partier av kvarvarande varor under implementeringen WMS-system och hur vi gjorde det.
När vi skrivit klart artikeln om optimeringsalgoritmer visade den sig vara väldigt stor, så vi bestämde oss för att dela upp det ackumulerade materialet i 2 delar:
- I den första delen (den här artikeln) kommer vi att prata om hur vi "byggde" den matematiska modellen av problemet och om de stora svårigheter vi oväntat stötte på när vi bearbetade och transformerade indata för algoritmen.
- I den andra delen kommer vi att i detalj överväga implementeringen av algoritmen i språket C + +, kommer vi att genomföra ett beräkningsexperiment och sammanfatta erfarenheten som vi fick under implementeringen av sådana "intelligenta teknologier" i kundens affärsprocesser.
Hur man läser en artikel. Om du läser föregående artikel kan du omedelbart gå till kapitlet "Översikt över befintliga lösningar"; om inte, så finns beskrivningen av problemet som löses i spoilern nedan.
Beskrivning av problemet som löses på kundens lager
Flaskhals i processer
Under 2018 slutförde vi ett projekt att genomföra WMS-system på lagret "Trading House "LD" i Chelyabinsk. Vi implementerade produkten "1C-Logistics: Warehouse Management 3" för 20 arbetsplatser: operatörer WMS, lagerhållare, truckförare. Det genomsnittliga lagret är cirka 4 tusen m2, antalet celler är 5000 och antalet SKU:er är 4500. Lagret lagrar kulventiler av vår egen produktion av olika storlekar från 1 kg till 400 kg. Inventarier på lagret lagras i partier, eftersom det finns behov av att välja varor enligt FIFO.
Under utformningen av system för automatisering av lagerprocesser ställdes vi inför det befintliga problemet med icke-optimal lagerlagring. Det specifika för lagring och läggning av kranar är sådana att en enhetslagringscell endast kan innehålla föremål från en batch (se fig. 1). Produkterna kommer till lagret dagligen och varje ankomst är en separat batch. Totalt, som ett resultat av 1 månads lagerdrift, skapas 30 separata batcher, trots att var och en ska lagras i en separat cell. Produkter väljs ofta inte i hela pallar, utan i bitar, och som ett resultat, i styckevalszonen i många celler observeras följande bild: i en cell med en volym på mer än 1 m3 finns det flera delar av kranar som upptar mindre än 5-10 % av cellvolymen.
Fig 1. Foto av flera bitar i en cell
Det är tydligt att lagringskapaciteten inte utnyttjas optimalt. För att föreställa mig katastrofens omfattning kan jag ge siffror: i genomsnitt finns det från 1 till 3 celler av sådana celler med en volym på mer än 100 m300 med "minuscula" balanser under olika perioder av lagrets drift. Eftersom lagret är relativt litet, blir denna faktor en "flaskhals" under de hektiska säsongerna i lagret och saktar avsevärt ner lagerprocesserna för mottagning och leverans.
Problemlösning idé
En idé uppstod: partier av rester med de närmaste datumen skulle reduceras till en enda batch, och sådana rester med en enhetlig batch skulle placeras kompakt tillsammans i en cell, eller i flera, om det inte finns tillräckligt med utrymme i en för att rymma hela mängden rester. Ett exempel på sådan "komprimering" visas i figur 2.
Fig.2. Schema för att komprimera rester i celler
Detta gör att du avsevärt kan minska det upptagna lagerutrymmet som kommer att användas för nya varor som placeras. I en situation där lagerkapaciteten är överbelastad är en sådan åtgärd extremt nödvändig, annars kanske det helt enkelt inte finns tillräckligt med ledigt utrymme för att ta emot nya varor, vilket kommer att leda till ett stopp i lagerprocesserna för placering och påfyllning och, som en konsekvens, till stopp i mottagning och leverans. Tidigare, före implementeringen av WMS-systemet, utfördes en sådan operation manuellt, vilket var ineffektivt, eftersom processen att söka efter lämpliga balanser i celler var ganska lång. Nu, med introduktionen av ett WMS-system, bestämde vi oss för att automatisera processen, påskynda den och göra den intelligent.
Processen för att lösa ett sådant problem är uppdelad i två steg:
- i det första steget hittar vi grupper av batcher nära datum för komprimering (tillägnade denna uppgift );
- i det andra steget, för varje grupp av partier, beräknar vi den mest kompakta placeringen av de återstående varorna i cellerna.
I den aktuella artikeln kommer vi att fokusera på det andra steget av algoritmen.
Genomgång av befintliga lösningar
Innan vi går vidare till beskrivningen av de algoritmer vi har utvecklat är det värt att göra en kort översikt över system som redan finns på marknaden WMS, som implementerar liknande optimal komprimeringsfunktion.
Först och främst är det nödvändigt att notera produkten "1C: Enterprise 8. WMS Logistics. Warehouse management 4", som ägs och replikeras av 1C och tillhör fjärde generationen WMS-system utvecklade av AXELOT. Detta system gör anspråk på komprimeringsfunktionalitet, som är utformad för att förena olika produktrester i en gemensam cell. Det är värt att nämna att komprimeringsfunktionen i ett sådant system också inkluderar andra möjligheter, till exempel att korrigera placeringen av varor i celler enligt deras ABC-klasser, men vi kommer inte att uppehålla oss vid dem.
Om du analyserar koden för 1C: Enterprise 8. WMS Logistics system. Lagerhantering 4" (som är öppen i denna del av funktionaliteten), kan vi dra följande slutsatser. Restkomprimeringsalgoritmen implementerar en ganska primitiv linjär logik och det kan inte vara tal om någon "optimal" komprimering. Naturligtvis ger den inte klustring av partier. Flera kunder som lät implementera ett sådant system klagade på resultatet av kompressionsplaneringen. Till exempel inträffade ofta i praktiken under kompression följande situation: 100 st. Det är planerat att flytta resterande gods från en cell till en annan cell, där 1 styck finns. varor, även om det ur tidsåtgångssynpunkt är optimalt att göra tvärtom.
Funktionaliteten för att komprimera de återstående varorna i celler deklareras också i många främmande länder. WMS-system, men tyvärr har vi ingen riktig feedback på effektiviteten av algoritmerna (detta är en affärshemlighet), än mindre en idé om djupet av deras logik (proprietär programvara med stängd källkod), så vi kan inte bedöma.
Sök efter en matematisk modell av problemet
För att designa högkvalitativa algoritmer för att lösa ett problem är det först nödvändigt att tydligt formulera detta problem matematiskt, vilket är vad vi kommer att göra.
Det finns många celler , som innehåller rester av vissa varor. I det följande kommer vi att kalla sådana celler donatorceller. Låt oss beteckna volym varor i cellen $.
Det är viktigt att säga att endast en produkt av en sats, eller flera satser tidigare kombinerade till ett kluster (läs: ), vilket beror på detaljerna för lagring och lagring av varor. Olika produkter eller olika batchkluster bör köra sin egen separata komprimeringsprocedur.
Det finns många celler , i vilka rester från donatorceller potentiellt kan placeras. Vi kommer vidare att kalla sådana celler för behållarceller. Dessa kan antingen vara fria celler i lagret eller donatorceller från en sort . Alltid gott är en delmängd .
För varje cell från många Kapacitetsbegränsningar har satts , mätt i dm3. En dm3 är en kub med sidor på 10 cm. Produkterna som lagras i lagret är ganska stora, så i det här fallet räcker en sådan diskretisering.
Givet en matris med kortaste avstånd i meter mellan varje par av celler var и tillhör uppsättningar и respektive.
Låt oss beteckna "kostnader" för att flytta varor från cellen in i en cell . Låt oss beteckna "kostnader" för att välja en container för att flytta rester från andra celler in i den. Hur exakt och i vilka måttenheter kommer värdena att beräknas и vi kommer att överväga ytterligare (se avsnittet som förbereder indata), för nu räcker det att säga att sådana värden kommer att vara direkt proportionella mot värdena и respektive.
Låt oss beteckna med en variabel som tar värdet 1 om resten är från cellen flyttas till container , och 0 annars. Låt oss beteckna med en variabel som tar värdet 1 om behållaren innehåller de återstående varorna och 0 i övrigt.
Uppgiften anges enligt följande: du behöver hitta så många behållare och därmed "fästa" donatorceller till behållarceller för att minimera funktionen
under restriktioner
Totalt, när vi beräknar lösningen på problemet, strävar vi efter att:
- för det första att spara lagringskapacitet;
- för det andra för att spara lagerhållarnas tid.
Den sista begränsningen innebär att vi inte kan flytta in varor till en container som vi inte har valt och därför inte "drar kostnader" för att välja den. Denna begränsning innebär också att volymen gods som flyttas från celler till containern inte får överstiga containerns kapacitet. Med att lösa ett problem menar vi en uppsättning behållare och metoder för att fästa donatorceller till behållare.
Denna formulering av optimeringsproblemet är inte ny, och har studerats av många matematiker sedan början av 80-talet av förra seklet. I utländsk litteratur finns det 2 optimeringsproblem med en lämplig matematisk modell: и (vi kommer att prata om skillnaderna i uppgifter senare). Det är värt att säga att i den matematiska litteraturen formuleras formuleringen av sådana två optimeringsproblem i termer av platsen för företag på marken, därav namnet "Facility Location". För det mesta är detta en hyllning till traditionen, eftersom behovet av att lösa sådana kombinatoriska problem för första gången kom från logistikområdet, mest från den militärindustriella sektorn på 50-talet av förra seklet. När det gäller företagslokalisering formuleras sådana uppgifter enligt följande:
- Det finns ett begränsat antal städer där det potentiellt är möjligt att lokalisera tillverkningsföretag (nedan kallade tillverkningsstäder). För varje tillverkningsstad specificeras kostnaderna för att öppna ett företag i den, såväl som en begränsning av produktionskapaciteten för det företag som öppnas i den.
- Det finns en ändlig uppsättning städer där kunder faktiskt finns (nedan kallade klientstäder). För varje sådan kundstad anges volymen av efterfrågan på produkter. För enkelhetens skull kommer vi att anta att det bara finns en produkt som produceras av företag och konsumeras av kunder.
- För varje par stad-tillverkare och stadskunder specificeras värdet av transportkostnaderna för att leverera den erforderliga volymen av produkter från tillverkaren till kunden.
Du måste hitta i vilka städer du ska öppna företag och hur du knyter kunder till sådana företag för att:
- De totala kostnaderna för att öppna företag och transportkostnaderna var minimala;
- Volymen av efterfrågan från kunder som tilldelats ett öppet företag översteg inte företagets produktionskapacitet.
Nu är det värt att nämna den enda skillnaden i dessa två klassiska problem:
- Single-Source Capacitated Facility Location Problem – klienten försörjs från endast en öppen anläggning;
- Multi-Source Capacitated Facility Location Problem – klienten kan försörjas från flera öppna anläggningar samtidigt.
En sådan skillnad mellan de två problemen är obetydlig vid första anblicken, men leder i själva verket till helt olika kombinatoriska strukturer för sådana problem och, som en konsekvens, till helt olika algoritmer för att lösa dem. Skillnaderna mellan uppgifterna visas i figuren nedan.
Fig.3. a) Problem med lokalisering av anläggning med flera källor
Fig.3. b) Problem med lokalisering av en källa med kapaciterad anläggning
Båda uppgifterna -svårt, det vill säga det finns ingen exakt algoritm som skulle lösa ett sådant problem i ett tidspolynom i storleken på indata. Med enklare ord kommer alla exakta algoritmer för att lösa ett problem att fungera i exponentiell tid, även om det kanske går snabbare än en fullständig sökning av alternativ. Sedan uppgiften -svårt, då kommer vi bara att överväga ungefärlig heuristik, det vill säga algoritmer som konsekvent kommer att beräkna lösningar mycket nära optimala och kommer att fungera ganska snabbt. Om du är intresserad av en sådan uppgift kan du hitta en bra översikt på ryska här.
Om vi går över till terminologin för vårt problem med optimal komprimering av varor i celler, då:
- klientstäder är donatorceller med resterande varor,
- tillverkningsstäder – containerceller , där resterna från andra celler ska placeras,
- transportkostnader - tidskostnader lagerhållaren att flytta volymen varor från donatorcellen in i en containercell ;
- kostnader för att öppna ett företag - kostnader för att välja container lika med volymen av behållarcellen , multiplicerat med en viss koefficient för att spara lediga volymer (värdet på koefficienten är alltid > 1) (se avsnittet förbereda indata).
Efter att analogin med de välkända klassiska lösningarna av problemet har dragits, är det nödvändigt att svara på en viktig fråga som valet av arkitekturen för lösningsalgoritmen beror på: att flytta resterna från donatorcellen är endast möjligt till en och bara en behållare (Single-Source), eller är det möjligt att flytta resten till flera behållarceller (Multi-Source)?
Det är värt att notera att i praktiken sker båda formuleringarna av problemet. Vi presenterar alla för- och nackdelar för varje sådan inställning nedan:
| Problemvariant | Fördelar med alternativet | Nackdelar med alternativet |
|---|---|---|
| Enskild källa | Varurörelser beräknade med denna variant av problemet:
|
|
| Flera källor | Kompressioner som beräknas med den här versionen av problemet är vanligtvis 10-15 % mer kompakta jämfört med komprimeringar som beräknas med alternativet "Single-Source". Men vi noterar också att ju mindre antalet rester i donatorcellerna är, desto mindre blir skillnaden i kompakthet | Varurörelser beräknade med denna variant av problemet:
|
Tabell 1. För- och nackdelar med alternativen för Single-Source och Multi-Source.
Eftersom alternativet Single-Source har fler fördelar, och även med hänsyn till det faktum att ju mindre antalet rester i donatorceller, desto mindre skillnad i graden av kompressionskompakthet beräknad för båda varianterna av problemet, föll vårt val på alternativet Single-Source.Källa.
Det är värt att säga att lösningen på Multi-Source-alternativet också äger rum. Det finns ett stort antal effektiva algoritmer för att lösa det, varav de flesta handlar om att lösa ett antal transportproblem. Det finns inte bara effektiva algoritmer utan även eleganta, t.ex.
Förbereder indata
Innan man börjar analysera och utveckla en algoritm för att lösa ett problem är det nödvändigt att bestämma vilken data och i vilken form vi ska mata in den som input. Det finns inga problem med volymen av kvarvarande varor i donatorceller och kapaciteten hos containerceller, eftersom detta är trivialt - sådana kvantiteter kommer att mätas i m3, men med kostnaderna för att använda en containercell och den rörliga kostnadsmatrisen, inte allt är så enkelt!
Låt oss först titta på beräkningen kostnader för att flytta gods från donatorcellen till behållarcellen. Först och främst är det nödvändigt att bestämma i vilka måttenheter vi kommer att beräkna kostnaderna för rörelse. De två mest uppenbara alternativen är meter och sekunder. Det är ingen mening att beräkna resekostnader i "rena" mätare. Låt oss visa detta med ett exempel. Låt cellen ligger på den första nivån, cell borttagen med 30 meter och placerad på den andra nivån:
- Flyttar från в dyrare än att flytta från в , eftersom att gå ner från den andra nivån (1,5-2 meter från golvet) är lättare än att gå upp till den andra, även om avståndet kommer att vara detsamma;
- Flytta 1 st. varor från cellen в Det blir lättare än att flytta 10 stycken. samma produkt, även om avståndet blir detsamma.
Det är bättre att överväga flyttkostnader på några sekunder, eftersom detta gör att du kan ta hänsyn till både skillnaden i nivåer och skillnaden i mängden gods som flyttas. För att ta hänsyn till kostnaden för rörelse i sekunder måste vi dekomponera rörelseoperationen i elementära komponenter och ta tidsmätningar för utförandet av varje elementär komponent.
Släpp från cellen rör sig PC. varor i container . låt – den genomsnittliga rörelsehastigheten för en arbetare i lagret, mätt i m/sek. Låta и – genomsnittliga hastigheter för engångsoperationer ta respektive sätta för en godsvolym motsvarande 4 dm3 (den genomsnittliga volym som en anställd tar åt gången i ett lager när han utför operationer). Låta и höjden på cellerna från vilka take- och put-operationerna utförs, respektive. Till exempel är den genomsnittliga höjden på den första nivån (golvet) 1 m, den andra nivån är 2 m, etc. Då är formeln för att beräkna den totala tiden för att slutföra en flyttoperation Nästa:
Tabell 2 visar statistik över utförandetiden för varje elementär operation, insamlad av lageranställda, med hänsyn tagen till detaljerna för de lagrade varorna.
| namnet på operationen | Обозначение | Genomsnittligt värde |
|---|---|---|
| Medelhastigheten för en arbetare som rör sig i lagret | |
1,5 m/s |
| Medelhastighet för en operation att sätta (för en produktvolym på 4 dm3) | |
2,4 sek |
Tabell 2. Genomsnittlig tid för att slutföra lagerverksamheten
Vi har beslutat om metoden för att beräkna kostnaderna för flytt. Nu måste vi ta reda på hur vi ska räkna kostnader för att välja en containercell. Allt här är mycket, mycket mer komplicerat än med flyttkostnader, eftersom:
- För det första bör kostnaderna vara direkt beroende av cellens volym - samma volym av rester som överförs från donatorceller är bättre placerad i en behållare med mindre volym än i en stor behållare, förutsatt att sådan volym helt passar i båda behållarna. Således, genom att minimera de totala kostnaderna för att välja behållare, strävar vi efter att spara "knappt" ledig lagringskapacitet i urvalsområdet för att utföra efterföljande operationer för att placera varor i celler. Figur 4 visar alternativen för att överföra rester till stora och små behållare och konsekvenserna av dessa överföringsalternativ i efterföljande lagerdrift.
- för det andra, eftersom vi för att lösa det ursprungliga problemet måste minimera exakt de totala kostnaderna, och detta är summan av både kostnaderna för att flytta och kostnaderna för att välja behållare, då måste cellvolymerna i kubikmeter på något sätt kopplas till sekunder, vilket är långt ifrån trivialt.
Ris. 4. Alternativ för att flytta överblivna rester till behållare med olika kapacitet.
Figur 4 visar i rött mängden rester som inte längre får plats i behållaren vid det andra steget av att placera efterföljande varor.
Det kommer att hjälpa till att koppla samman kubikmeterkostnaderna för att välja en container med sekundernas kostnader för att flytta följande krav för beräknade lösningar på problemet:
- Det är nödvändigt att saldona från donatorbehållaren flyttas till behållarbehållaren i alla fall om detta minskar det totala antalet behållare som innehåller produkten.
- Det är nödvändigt att upprätthålla en balans mellan volymen av containrar och den tid som går åt till att flytta: till exempel, om en ny lösning på ett problem jämfört med den tidigare lösningen, är volymökningen stor, men tidsförlusten är liten , då är det nödvändigt att välja ett nytt alternativ.
Låt oss börja med det sista kravet. För att förtydliga det tvetydiga ordet "balans" genomförde vi en undersökning av lageranställda för att ta reda på följande. Låt det finnas en behållarcell med volym , till vilken förflyttning av kvarvarande varor från donatorceller tilldelas och den totala tiden för sådan förflyttning är lika med . Låt det finnas flera alternativa alternativ för att placera samma mängd varor från samma donatorceller i andra behållare, där varje placering har sina egna uppskattningar var < и var >.
Frågan ställs: vad är den minsta vinsten i volym acceptabelt för ett givet tidsförlustvärde ? Låt oss förklara med ett exempel. Till en början var det meningen att resterna skulle placeras i en behållare med en volym på 1000 dm3 (1 m3) och överföringstiden var 70 sekunder. Det finns en möjlighet att placera resterna i en annan behållare med en volym på 500 dm3 och en tid på 130 sekunder. Fråga: är vi redo att lägga ytterligare 60 sekunder av lagerhållarens tid på att flytta varorna för att spara 500 dm3 ledig volym? Baserat på resultaten från en undersökning bland lagermedarbetare sammanställdes följande diagram.
Ris. 5. Diagram över beroendet av de minsta tillåtna volymbesparingarna på ökningen av skillnaden i drifttiden
Det vill säga, om de extra tidskostnaderna är 40 sekunder, är vi redo att spendera dem först när vinsten i volym är minst 500 dm3. Trots det faktum att det finns en liten olinjäritet i beroendet, kommer vi för enkelheten att göra ytterligare beräkningar att anta att beroendet mellan storheterna är linjärt och beskrivs av olikheten
I figuren nedan överväger vi följande metoder för att placera varor i containrar.
Ris. 6. Alternativ (a): 2 behållare, total volym 400 dm3, total tid 150 sek.
Ris. 6. Alternativ (b): 2 behållare, total volym 600 dm3, total tid 190 sek.
Ris. 6. Alternativ (c): 1 behållare, total volym 400 dm3, total tid 200 sek.
Alternativ (a) för att välja behållare är mer att föredra än det ursprungliga alternativet, eftersom ojämlikheten gäller: (800-400)/10>=150-120, vilket innebär 40 >= 30. Alternativ (b) är mindre att föredra än originalet option , eftersom ojämlikheten inte håller: (800-600)/10>=190-150 vilket innebär 20 >= 40. Men alternativ (c) passar inte in i sådan logik! Låt oss överväga det här alternativet mer i detalj. Å ena sidan, ojämlikheten (800-400)/10>=200-120, vilket innebär att ojämlikheten 40 >= 80 inte är uppfylld, vilket tyder på att vinsten i volym inte är värd en så stor tidsförlust.
Men å andra sidan, i detta alternativ (c) minskar vi inte bara den totala ockuperade volymen, utan minskar också antalet ockuperade celler, vilket är det första av två viktiga krav för beräkningsbara lösningar på problemen som anges ovan. Uppenbarligen, för att detta krav ska börja uppfyllas, är det nödvändigt att lägga till någon positiv konstant till vänster sida av ojämlikheten , och en sådan konstant behöver bara läggas till när antalet behållare minskar. Låt oss komma ihåg det är en variabel lika med 1 när behållaren vald och 0 när behållare Ej valt. Låt oss beteckna – många behållare i den initiala lösningen och – många containrar i den nya lösningen. I allmänhet kommer den nya ojämlikheten att se ut så här:
Att omvandla ojämlikheten ovan får vi
Utifrån detta har vi en formel för att beräkna totalkostnaden någon lösning på problemet:
Men nu uppstår frågan: vilket värde ska en sådan konstant ha? ? Uppenbarligen måste dess värde vara tillräckligt stort så att det första kravet på lösningar på problemet alltid uppfylls. Du kan naturligtvis ta värdet på konstanten lika med 103 eller 106, men jag skulle vilja undvika sådana "magiska siffror". Om vi överväger detaljerna för att utföra lageroperationer, kan vi beräkna flera välgrundade numeriska uppskattningar av värdet av en sådan konstant.
låt – det maximala avståndet mellan lagerceller i en zon ABC, i vårt fall lika med 100 m. Låt – den maximala volymen av en containercell i ett lager, i vårt fall lika med 1000 dm3.
Det första sättet att beräkna värdet . Låt oss överväga en situation där det finns 2 behållare på den första nivån, där varorna redan finns fysiskt, det vill säga de själva är donatorceller, och kostnaden för att flytta varorna till samma celler är naturligtvis lika med 0. Det är nödvändigt för att hitta ett sådant värde för konstanten , där det skulle vara fördelaktigt att alltid flytta resterna från behållare 1 till behållare 2. Byt ut värdena и I ojämlikheten ovan får vi:
varav följer
Genom att ersätta värdena för den genomsnittliga tiden för att utföra elementära operationer med formeln ovan får vi
Det andra sättet att beräkna värdet . Låt oss överväga en situation där det finns donatorceller från vilka det är planerat att flytta varorna till container 1. Låt oss beteckna – avstånd från donatorcellen till container 1. Det finns också container 2, som redan innehåller varor, och vars volym gör att du kan ta emot resten av alla celler. För enkelhetens skull kommer vi att anta att volymen gods som flyttas från donatorceller till behållare är densamma och lika med . Det krävs att hitta ett sådant värde på konstanten , där placeringen av alla rester från celler i behållare 2 skulle alltid vara mer lönsamma än att placera dem i olika behållare:
Förvandla den ojämlikhet vi får
För att ”stärka” värdet på kvantiteten , låt oss anta det = 0. Det genomsnittliga antalet celler som vanligtvis är involverade i proceduren för att komprimera lagersaldon är 10. Genom att ersätta de kända värdena för kvantiteterna har vi följande värde på konstanten
Vi tar det största värdet beräknat för varje alternativ, detta kommer att vara värdet på kvantiteten för de givna lagerparametrarna. Nu, för fullständighetens skull, låt oss skriva ner formeln för att beräkna totala kostnader för någon genomförbar lösning :
Nu trots allt Herkuliska ansträngningar Genom att transformera indata kan vi säga att all indata har konverterats till önskad form och är redo att användas i optimeringsalgoritmen.
Slutsats
Som praxis visar underskattas ofta komplexiteten och betydelsen av steget att förbereda och transformera indata för en algoritm. I den här artikeln ägnade vi specifikt mycket uppmärksamhet åt detta steg för att visa att endast högkvalitativa och intelligent förberedda indata kan göra de beslut som beräknas av algoritmen verkligt värdefulla för kunden. Ja, det fanns många härledningar av formler, men vi varnade dig redan innan kata :)
I nästa artikel kommer vi äntligen till vad de 2 tidigare publikationerna var avsedda för - en diskret optimeringsalgoritm.
Förberedde artikeln
Roman Shangin, programmerare på projektavdelningen,
First Bit-företag, Chelyabinsk
Källa: will.com