Optimering hjælper dig med at finde det bedste resultat, der giver overskud, reducerer omkostninger eller indstiller en parameter, der forårsager fejl i forretningsprocesserne.
Denne proces kaldes også matematisk programmering. Det løser problemet med at bestemme fordelingen af begrænsede ressourcer, der er nødvendige for at nå det mål, der er fastsat af lederen af optimeringsproblemet. Af alle de mulige muligheder er det ønskeligt at finde den, der maksimerer (eller reducerer) den kontrollerende parameter, for eksempel fortjeneste eller omkostninger. Optimeringsmodeller kaldes også præskriptive eller normative, fordi de søger at finde en gennemførlig strategi for virksomheden.
Udviklingshistorik
Lineær programmering (LP) fungerer med en klasse af optimeringsproblemer, hvor alle begrænsninger er lineære.
Præsenterer en kort historie om udviklingen af LP:
- I 1762 løste Lagrange simple optimeringsproblemer med lighedsbegrænsninger.
- I 1820 besluttede Gausslineært ligningssystem ved hjælp af eliminering.
- I 1866 perfektionerede Wilhelm Jordan metoden til at finde mindste kvadraters fejl som et egnethedskriterium. Dette kaldes nu Gauss-Jordan-metoden.
- Den digitale computer dukkede op i 1945.
- Danzig opfandt simplex-metoder i 1947.
- I 1968 introducerede Fiacco og McCormick Inside Point-metoden.
- I 1984 anvendte Karmarkar den indre metode til at løse lineære programmer og tilføjede sin innovative analyse.
LP har vist sig at være et ekstremt kraftfuldt værktøj både til modellering af problemer i den virkelige verden og som en udbredt matematisk teori. Mange interessante optimeringsproblemer er dog ikke-lineære.
Hvad skal man gøre i dette tilfælde? Studiet af sådanne problemer involverer en varieret blanding af lineær algebra, multivariat beregning, numerisk analyse og beregningsmetoder. Forskere er ved at udvikle beregningsalgoritmer, herunder indre punktmetoder til lineær programmering, geometri, analyse af konvekse sæt og funktioner og undersøgelse af specielt strukturerede problemer såsom kvadratisk programmering.
Ikke-lineær optimering giver en grundlæggende forståelse af matematisk analyse og er meget udbredt inden for forskellige områder såsom teknik, regressionsanalyse, ressourcestyring, geofysisk udforskning og økonomi.
Klassificering af optimeringsproblemer
Et vigtigt skridt på vejenOptimeringsprocessen er klassificeringen af modeller, da deres løsningsalgoritmer er tilpasset en bestemt type.
1. Problemer med diskret og kontinuerlig optimering. Nogle modeller giver kun mening, hvis variablerne tager værdier fra en diskret delmængde af heltal. Andre indeholder data, der kan få enhver reel værdi. De er norm alt nemmere at løse. Forbedringer i algoritmer, kombineret med fremskridt inden for computerteknologi, har dramatisk øget størrelsen og kompleksiteten af et lineært programmeringsoptimeringsproblem.
2. Ubegrænset og begrænset optimering. En anden vigtig forskel er opgaver, hvor der ikke er nogen begrænsning på variabler. Det kan spænde vidt fra simple estimatorer til systemer af ligheder og uligheder, der modellerer komplekse forhold mellem data. Sådanne optimeringsproblemer kan klassificeres yderligere efter funktionernes art (lineære og ikke-lineære, konvekse og glatte, differentierbare og ikke-differentierbare).
3. Gennemførlighedsopgaver. Deres mål er at finde variable værdier, der opfylder modellens begrænsninger uden noget specifikt optimeringsmål.
4. Komplementaritetsopgaver. De er meget udbredt inden for teknologi og økonomi. Målet er at finde en løsning, der opfylder komplementaritetsbetingelserne. I praksis omformuleres opgaver med flere mål ofte til enkeltmål.
5. Deterministisk versus stokastisk optimering. Deterministisk optimering forudsætter, at data foropgaver er fuldstændig præcise. Men i mange aktuelle emner kan de ikke kendes af en række årsager.
Den første har at gøre med en simpel målefejl. Den anden grund er mere grundlæggende. Det ligger i, at nogle data repræsenterer information om fremtiden, for eksempel efterspørgslen efter et produkt eller prisen for en fremtidig periode. Ved optimering under stokastiske optimeringsforhold er usikkerhed inkluderet i modellen.
Hovedkomponenter
Den objektive funktion er den, der skal minimeres eller maksimeres. De fleste typer optimeringsproblemer har én objektiv funktion. Hvis ikke, kan de ofte omformuleres til at fungere.
To undtagelser fra denne regel:
1. Målsøgningsopgave. I de fleste forretningsapplikationer ønsker lederen at opnå et specifikt mål og samtidig opfylde modellens begrænsninger. Brugeren ønsker ikke specielt at optimere noget, så det giver ingen mening at definere en objektiv funktion. Denne type omtales almindeligvis som et tilfredsstillelsesproblem.
2. Masser af objektive funktioner. Ofte vil en bruger gerne optimere flere forskellige mål på én gang. De er norm alt uforenelige. Variabler, der optimerer til ét mål, er muligvis ikke de bedste for andre.
Komponenttyper:
- Et kontrolleret input er et sæt beslutningsvariable, der påvirker værdien af en objektiv funktion. I en produktionsopgave kan variabler omfatte fordelingen af de forskellige tilgængelige ressourcer eller den nødvendige arbejdskrafthver handling.
- Begrænsninger er relationer mellem beslutningsvariabler og parametre. For et produktionsproblem giver det ikke mening at bruge meget tid på enhver aktivitet, så begræns alle "midlertidige" variabler.
- Mulige og optimale løsninger. Værdien af beslutningen for variabler, hvorunder alle begrænsninger er opfyldt, kaldes tilfredsstillende. De fleste algoritmer finder det først og prøver derefter at forbedre det. Endelig ændrer de variabler for at flytte fra en mulig løsning til en anden. Denne proces gentages, indtil målfunktionen når sit maksimum eller minimum. Dette resultat kaldes den optimale løsning.
Algorithmer for optimeringsproblemer udviklet til følgende matematiske programmer er meget udbredt:
- Konveks.
- Adskilles.
- Kvadratisk.
- Geometrisk.
Google Linear Solvers
Lineær optimering eller programmering er navnet på den beregningsmæssige proces med optimal løsning af et problem. Det er modelleret som et sæt lineære sammenhænge, der opstår i mange videnskabelige og ingeniørfaglige discipliner.
Google tilbyder tre måder at løse lineære optimeringsproblemer på:
- Glop open source-bibliotek.
- Lineær optimering-tilføjelse til Google Sheets.
- Lineær optimeringstjeneste i Google Apps Script.
Glop er indbygget i Googlelineær løser. Den er tilgængelig i open source. Du kan få adgang til Glop gennem OR-Tools lineære solver wrapper, som er en wrapper for Glop.
Lineært optimeringsmodul til Google Sheets giver dig mulighed for at udføre en lineær erklæring om optimeringsproblemet ved at indtaste data i et regneark.
Kvadratisk programmering
Premium Solver-platformen bruger en udvidet LP/Kvadratisk version af Simplex-metoden med LP- og QP-problembehandlingsgrænser på op til 2000 beslutningsvariabler.
SQP Løser til store problemer bruger en moderne implementering af den aktive sæt-metode med sparsomhed til at løse kvadratiske programmeringsproblemer (QP). XPRESS Solver-motoren bruger en naturlig forlængelse af "Interior Point"- eller Newton Barrier-metoden til at løse QP-problemer.
MOSEK Solver anvender indlejrede "Inside Point" og auto-dual metoder. Dette er især effektivt til løst koblede QP-problemer. Det kan også løse problemer med Scale Quadratic Constraint (QCP) og Second Order Cone Programming (SOCP).
Multi-operation-beregninger
De er ganske vellykket brugt med brugen af Microsoft Office-funktioner, f.eks. løsning af optimeringsproblemer i Excel.
I ovenstående tabel er symbolerne:
- K1 - K6 - kunder, der skal levere varer.
- S1 - S6 er potentielle produktionssteder, der kunne bygges til dette. Kan oprettes1, 2, 3, 4, 5 eller alle 6 steder.
Der er faste omkostninger for hver facilitet anført i kolonne I (Fix).
Hvis placeringen ikke ændrer noget, tæller det ikke. Så er der ingen faste omkostninger.
Identificer potentielle steder for at få den laveste pris.
Under disse forhold er placeringen enten etableret eller ej. Disse to tilstande er: "SAND - FALSK" eller "1 - 0". Der er seks tilstande for seks steder, f.eks. er 000001 kun indstillet til den sjette, 111111 er indstillet til alle.
I det binære talsystem er der præcis 63 forskellige muligheder fra 000001 (1) til 111111 (63).
L2-L64 skulle nu læse {=MULTIPLE OPERATION (K1)}, dette er resultaterne af alle alternative løsninger. Så er minimumsværdien=Min (L), og det tilsvarende alternativ er INDEX (K).
CPLEX-heltalsprogrammering
Nogle gange er et lineært forhold ikke nok til at komme til kernen af et forretningsproblem. Dette gælder især, når beslutninger involverer diskrete valg, såsom hvorvidt der skal åbnes et lager på et bestemt sted. I disse situationer skal der bruges heltalsprogrammering.
Hvis problemet involverer både diskrete og kontinuerlige valg, er det et blandet heltalsprogram. Det kan have lineære, konvekse kvadratiske problemer og de samme anden ordens begrænsninger.
Heltalsprogrammer er meget mere komplekse end lineære programmer, men de har vigtige forretningsapplikationer. SoftwareCPLEX-softwaren bruger komplekse matematiske metoder til at løse heltalsproblemer. Hans metoder involverer systematisk søgning efter mulige kombinationer af diskrete variable ved hjælp af lineære eller kvadratiske softwarerelaksationer til at beregne grænser for værdien af den optimale løsning.
De bruger også LP og andre optimeringsproblemløsningsmetoder til at beregne begrænsninger.
Standard Microsoft Excel Solver
Denne teknologi bruger den grundlæggende implementering af den primære Simplex-metode til at løse LP-problemer. Det er begrænset til 200 variabler. "Premium Solver" bruger en forbedret primær simplex-metode med dobbeltsidede grænser for variable. Premium Solver-platformen bruger en udvidet version af LP/Quadratic Simplex Solver til at løse et optimeringsproblem med op til 2000 beslutningsvariabler.
Large-scale LP til Premium Solver platformen anvender en state-of-the-art implementering af den simple og dobbelt simpleks metode, som bruger sparsity i LP modellen til at spare tid og hukommelse, avancerede strategier til opdatering og refactoring matricer, multiple og partielle prissætning og rotationer, og for at overvinde degeneration. Denne motor er tilgængelig i tre versioner (i stand til at håndtere op til 8.000, 32.000 eller ubegrænsede variabler og grænser).
MOSEK Solver inkluderer primær og dual simplex, en metode, der også udnytter sparsitet og bruger avancerede strategier til matrixopdatering og "refaktorisering". Det løser problemer af ubegrænset størrelse, vartestet på lineære programmeringsproblemer med millioner af beslutningsvariabler.
Trin for trin eksempel i EXCEL
For at definere optimeringsproblemmodellen i Excel skal du udføre følgende trin:
- Organiser dataene for problemet i et regneark i en logisk form.
- Vælg en celle for at gemme hver variabel.
- Opret i cellen en formel til beregning af den matematiske målmodel for optimeringsproblemet.
- Opret formler til at beregne venstre side af hver begrænsning.
- Brug dialoger i Excel til at fortælle Solver om beslutningsvariabler, mål, begrænsninger og ønskede grænser for disse parametre.
- Kør "Solver" for at finde den optimale løsning.
- Opret et Excel-ark.
- Organiser dataene for problemet i Excel, hvor formlen for objektivfunktionen og begrænsningen beregnes.
I ovenstående tabel er celler B4, C4, D4 og E4 reserveret til at repræsentere beslutningsvariable X 1, X 2, X 3 og X 4. Beslutningseksempler:
- Produktblandingsmodellen ($450, $1150, $800 og $400 profit pr. produkt) blev indtastet i henholdsvis cellerne B5, C5, D5 og E5. Dette gør det muligt at beregne målet i F5=B5B4 + C5C4 + D5D4 + E5E4 eller F5:=SUMPRODUKT (B5: E5, B4: E4).
- I B8 skal du indtaste mængden af ressourcer, der kræves for at fremstille hver type produkt.
- Formel for F8:=SUMPRODUKT(B8:E8, $B$4:$E$4).
- Kopiér detteformel i F9. Dollartegn i $B$4:$E$4 indikerer, at dette celleområde forbliver konstant.
- I G8 skal du indtaste den tilgængelige mængde ressourcer af hver type, svarende til værdierne af begrænsningerne til højre. Dette giver dig mulighed for at udtrykke dem sådan her: F11<=G8: G11.
- Dette svarer til fire grænser F8<=G8, F9 <=G9, F10 <=G10 og F11=0
Områder for praktisk anvendelse af metoden
Lineær optimering har mange praktiske anvendelser som et eksempel på et optimeringsproblem:
En virksomhed kan fremstille flere produkter med en kendt dækningsbidrag. Produktionen af en enhed af hver vare kræver en kendt mængde begrænsede ressourcer. Opgaven er at lave et produktionsprogram til at bestemme, hvor meget af hvert produkt der skal produceres, så virksomhedens profit maksimeres uden at overtræde ressourcebegrænsninger.
Blandingsproblemer er løsningen på optimeringsproblemer relateret til at kombinere ingredienser i det endelige produkt. Et eksempel på dette er kostproblemet, studeret af George Danzig i 1947. Der gives en række råvarer, såsom havre, svinekød og solsikkeolie, sammen med deres næringsindhold, såsom protein, fedt, vitamin A og deres kilopris. Udfordringen er at blande et eller flere slutprodukter fra råvarer til den lavest mulige pris og samtidig respektere minimums- og maksimumgrænserne for deres næringsværdi.
En klassisk anvendelse af et lineært optimeringsproblem er at bestemme routing efter behovtrafik i tele- eller transportnet. Samtidig skal flows dirigeres gennem netværket på en sådan måde, at alle trafikkrav opfyldes uden at overtræde båndbreddebetingelser.
I matematisk teori kan lineær optimering bruges til at beregne optimale strategier i nulsumsspil for to personer. I dette tilfælde beregnes sandsynlighedsfordelingen for hver deltager, som er koefficienten for tilfældig blanding af hans strategier.
Ingen succesfuld forretningsproces i verden er mulig uden optimering. Der er mange tilgængelige optimeringsalgoritmer. Nogle metoder er kun egnede til visse typer problemer. Det er vigtigt at kunne genkende deres egenskaber og vælge den passende løsningsmetode.
