Optimalisering hjelper deg med å finne det beste resultatet som gir fortjeneste, reduserer kostnader eller setter en parameter som forårsaker feil i forretningsprosesser.
Denne prosessen kalles også matematisk programmering. Det løser problemet med å bestemme fordelingen av begrensede ressurser som er nødvendige for å nå målet satt av lederen for optimaliseringsproblemet. Av alle mulige alternativer er det ønskelig å finne den som maksimerer (eller reduserer) den kontrollerende parameteren, for eksempel fortjeneste eller kostnad. Optimaliseringsmodeller kalles også preskriptive eller normative fordi de søker å finne en gjennomførbar strategi for virksomheten.
Utviklingshistorikk
Lineær programmering (LP) fungerer med en klasse med optimaliseringsproblemer der alle begrensninger er lineære.
Vi presenterer en kort historie om utviklingen av LP:
- I 1762 løste Lagrange enkle optimaliseringsproblemer med likhetsbegrensninger.
- I 1820 bestemte Gausslineært ligningssystem som bruker eliminering.
- I 1866 perfeksjonerte Wilhelm Jordan metoden for å finne minste kvadraters feil som et tilpasningskriterium. Dette kalles nå Gauss-Jordan-metoden.
- Den digitale datamaskinen dukket opp i 1945.
- Danzig oppfant simpleksmetoder i 1947.
- I 1968 introduserte Fiacco og McCormick Inside Point-metoden.
- I 1984 brukte Karmarkar interiørmetoden for å løse lineære programmer, og la til sin innovative analyse.
LP har vist seg å være et ekstremt kraftig verktøy både for å modellere problemer i den virkelige verden og som en mye brukt matematisk teori. Mange interessante optimaliseringsproblemer er imidlertid ikke-lineære.
Hva skal jeg gjøre i dette tilfellet? Studiet av slike problemer involverer en variert blanding av lineær algebra, multivariat kalkulus, numerisk analyse og beregningsmetoder. Forskere utvikler beregningsalgoritmer, inkludert indre punktmetoder for lineær programmering, geometri, analyse av konvekse sett og funksjoner, og studier av spesielt strukturerte problemer som kvadratisk programmering.
Ikke-lineær optimalisering gir en grunnleggende forståelse av matematisk analyse og er mye brukt i ulike felt som engineering, regresjonsanalyse, ressursforv altning, geofysisk utforskning og økonomi.
Klassifisering av optimaliseringsproblemer
Et viktig skritt innOptimaliseringsprosessen er klassifiseringen av modeller, siden løsningsalgoritmene deres er tilpasset en bestemt type.
1. Problemer med diskret og kontinuerlig optimalisering. Noen modeller gir mening bare hvis variablene tar verdier fra en diskret delmengde av heltall. Andre inneholder data som kan få en hvilken som helst reell verdi. De er vanligvis lettere å løse. Forbedringer i algoritmer, kombinert med fremskritt innen datateknologi, har dramatisk økt størrelsen og kompleksiteten til et lineært programmeringsoptimeringsproblem.
2. Ubegrenset og begrenset optimalisering. En annen viktig forskjell er oppgaver der det ikke er noen begrensninger på variabler. Det kan variere vidt fra enkle estimatorer til systemer med likheter og ulikheter som modellerer komplekse forhold mellom data. Slike optimaliseringsproblemer kan videre klassifiseres i henhold til funksjonenes natur (lineære og ikke-lineære, konvekse og glatte, differensierbare og ikke-differensierbare).
3. Mulighetsoppgaver. Målet deres er å finne variabelverdier som tilfredsstiller modellbegrensninger uten noe spesifikt optimaliseringsmål.
4. Komplementaritetsoppgaver. De er mye brukt innen teknologi og økonomi. Målet er å finne en løsning som tilfredsstiller komplementaritetsbetingelsene. I praksis blir oppgaver med flere mål ofte omformulert til enkeltmål.
5. Deterministisk versus stokastisk optimalisering. Deterministisk optimalisering forutsetter at dataene foroppgavene er helt nøyaktige. Men i mange aktuelle saker kan de ikke være kjent av flere grunner.
Den første har å gjøre med en enkel målefeil. Den andre grunnen er mer grunnleggende. Det ligger i det faktum at noen data representerer informasjon om fremtiden, for eksempel etterspørselen etter et produkt eller prisen for en fremtidig tidsperiode. Ved optimering under stokastiske optimaliseringsforhold er usikkerhet inkludert i modellen.
Hovedkomponenter
Den objektive funksjonen er den som skal minimeres eller maksimeres. De fleste typer optimaliseringsproblemer har én objektiv funksjon. Hvis ikke, kan de ofte omformuleres til å fungere.
To unntak fra denne regelen:
1. Målsøkeoppgave. I de fleste forretningsapplikasjoner ønsker lederen å oppnå et spesifikt mål og samtidig tilfredsstille modellbegrensninger. Brukeren ønsker ikke spesielt å optimalisere noe, så det gir ingen mening å definere en objektiv funksjon. Denne typen blir ofte referert til som et tilfredsstillelsesproblem.
2. Mange objektive funksjoner. Ofte ønsker en bruker å optimalisere flere forskjellige mål samtidig. De er vanligvis inkompatible. Variabler som optimaliserer for ett mål er kanskje ikke de beste for andre.
Komponenttyper:
- En kontrollert input er et sett med beslutningsvariabler som påvirker verdien av en objektiv funksjon. I en produksjonsoppgave kan variabler inkludere fordelingen av de ulike tilgjengelige ressursene eller arbeidskraften som kreves for åhver handling.
- Begrensninger er forhold mellom beslutningsvariabler og parametere. For et produksjonsproblem er det ikke fornuftig å bruke mye tid på aktivitet, så begrens alle "midlertidige" variabler.
- Mulige og optimale løsninger. Verdien av avgjørelsen for variabler, der alle begrensninger er oppfylt, kalles tilfredsstillende. De fleste algoritmer finner det først, og prøver deretter å forbedre det. Til slutt endrer de variabler for å flytte fra en gjennomførbar løsning til en annen. Denne prosessen gjentas til målfunksjonen når maksimum eller minimum. Dette resultatet kalles den optimale løsningen.
Algorithmer for optimaliseringsproblemer utviklet for følgende matematiske programmer er mye brukt:
- Konveks.
- Separerbar.
- Kvadratisk.
- Geometrisk.
Google Linear Solvers
Lineær optimalisering eller programmering er navnet som er gitt til beregningsprosessen for å løse et problem optim alt. Den er modellert som et sett med lineære forhold som oppstår i mange vitenskapelige og ingeniørfaglige disipliner.
Google tilbyr tre måter å løse lineære optimaliseringsproblemer på:
- Glop åpen kildekode-bibliotek.
- Lineær optimaliseringstillegg for Google Sheets.
- Lineær optimaliseringstjeneste i Google Apps-skript.
Glop er innebygd i Googlelineær løser. Den er tilgjengelig i åpen kildekode. Du kan få tilgang til Glop gjennom OR-Tools lineære løser-innpakning, som er en wrapper for Glop.
Lineær optimaliseringsmodul for Google Sheets lar deg utføre en lineær uttalelse av optimaliseringsproblemet ved å legge inn data i et regneark.
Kvadratisk programmering
Premium Solver-plattformen bruker en utvidet LP/Quadratic-versjon av Simplex-metoden med LP- og QP-problembehandlingsgrenser på opptil 2000 beslutningsvariabler.
SQP Løser for store problemer bruker en moderne implementering av den aktive settmetoden med sparsomhet for å løse kvadratisk programmeringsproblemer (QP). XPRESS Solver-motoren bruker en naturlig utvidelse av "Interior Point"- eller Newton Barrier-metoden for å løse QP-problemer.
MOSEK Solver bruker innebygde "Inside Point" og auto-dual metoder. Dette er spesielt effektivt for løst koblede QP-problemer. Den kan også løse problemene med Scale Quadratic Constraint (QCP) og Second Order Cone Programming (SOCP).
Multi-operasjonsberegninger
De er ganske vellykket brukt med bruk av Microsoft Office-funksjoner, for eksempel ved å løse optimaliseringsproblemer i Excel.
I tabellen ovenfor er symbolene:
- K1 - K6 - kunder som trenger å levere varer.
- S1 - S6 er potensielle produksjonssteder som kan bygges for dette. Kan opprettes1, 2, 3, 4, 5 eller alle 6 lokasjonene.
Det er faste kostnader for hvert anlegg oppført i kolonne I (Fix).
Hvis plasseringen ikke endrer noe, vil den ikke telle. Da blir det ingen faste kostnader.
Identifiser potensielle steder for å få den laveste kostnaden.
I disse forholdene er plasseringen enten etablert eller ikke. Disse to tilstandene er: "SANN - USANN" eller "1 - 0". Det er seks tilstander for seks lokasjoner, for eksempel er 000001 satt til bare den sjette, 111111 er satt til alle.
I det binære tallsystemet er det nøyaktig 63 forskjellige alternativer fra 000001 (1) til 111111 (63).
L2-L64 skal nå lese {=MULTIPLE OPERATION (K1)}, dette er resultatene av alle alternative løsninger. Da er minimumsverdien=Min (L) og det tilsvarende alternativet er INDEX (K).
CPLEX-heltallsprogrammering
Noen ganger er ikke et lineært forhold nok for å komme til kjernen av et forretningsproblem. Dette gjelder spesielt når avgjørelser involverer diskrete valg, for eksempel om å åpne et lager på et bestemt sted eller ikke. I disse situasjonene må heltallsprogrammering brukes.
Hvis problemet involverer både diskrete og kontinuerlige valg, er det et blandet heltallsprogram. Den kan ha lineære, konvekse kvadratiske problemer og de samme andre ordensbegrensningene.
Heltalsprogrammer er mye mer komplekse enn lineære programmer, men de har viktige forretningsapplikasjoner. ProgramvareCPLEX-programvaren bruker komplekse matematiske metoder for å løse heltallsproblemer. Metodene hans innebærer å systematisk søke etter mulige kombinasjoner av diskrete variabler ved å bruke lineære eller kvadratiske programvarerelaksasjoner for å beregne grenser for verdien av den optimale løsningen.
De bruker også LP og andre optimaliseringsmetoder for problemløsning for å beregne begrensninger.
Standard Microsoft Excel Solver
Denne teknologien bruker den grunnleggende implementeringen av hovedmetoden Simplex for å løse LP-problemer. Den er begrenset til 200 variabler. "Premium Solver" bruker en forbedret primær simpleksmetode med dobbeltsidige grenser for variabler. Premium Solver-plattformen bruker en utvidet versjon av LP/Quadratic Simplex Solver for å løse et optimaliseringsproblem med opptil 2000 beslutningsvariabler.
Storskala LP for Premium Solver-plattformen bruker en state-of-the-art implementering av den enkle og doble simpleksmetoden, som bruker sparsitet i LP-modellen for å spare tid og minne, avanserte strategier for oppdatering og refaktorisering av matriser, multiple og delvise priser og rotasjoner, og for å overvinne degenerasjon. Denne motoren er tilgjengelig i tre versjoner (i stand til å håndtere opptil 8 000, 32 000 eller ubegrensede variabler og grenser).
MOSEK Solver inkluderer primær og dual simpleks, en metode som også utnytter sparsitet og bruker avanserte strategier for matriseoppdatering og "refaktorisering". Det løser problemer av ubegrenset størrelse, vartestet på lineære programmeringsproblemer med millioner av beslutningsvariabler.
Trinn-for-trinn-eksempel i EXCEL
For å definere optimaliseringsproblemmodellen i Excel, utfør følgende trinn:
- Organiser dataene for problemet i et regneark i en logisk form.
- Velg en celle for å lagre hver variabel.
- Lag en formel i cellen for å beregne den matematiske målmodellen for optimaliseringsproblemet.
- Lag formler for å beregne venstre side av hver begrensning.
- Bruk dialoger i Excel for å fortelle Solver om beslutningsvariabler, mål, begrensninger og ønskede grenser for disse parameterne.
- Kjør "Solver" for å finne den optimale løsningen.
- Opprett et Excel-ark.
- Organiser dataene for oppgaven i Excel der formelen for objektivfunksjonen og begrensningen beregnes.
I tabellen ovenfor er cellene B4, C4, D4 og E4 reservert for å representere beslutningsvariablene X 1, X 2, X 3 og X 4. Beslutningseksempler:
- Produktmiksmodellen ($450, $1150, $800 og $400 fortjeneste per produkt) ble lagt inn i henholdsvis cellene B5, C5, D5 og E5. Dette gjør at målet kan beregnes i F5=B5B4 + C5C4 + D5D4 + E5E4 eller F5:=SUMPRODUKT (B5: E5, B4: E4).
- I B8 skriv inn mengden ressurser som kreves for å produsere hver type produkt.
- Formel for F8:=SUMPRODUKT(B8:E8, $B$4:$E$4).
- Kopier detteformel i F9. Dollartegn i $B$4:$E$4 indikerer at dette celleområdet forblir konstant.
- I G8 skriv inn den tilgjengelige mengden ressurser av hver type, tilsvarende verdiene til restriksjonene til høyre. Dette lar deg uttrykke dem slik: F11<=G8: G11.
- Dette tilsvarer fire grenser F8<=G8, F9 <=G9, F10 <=G10 og F11=0
Felter for praktisk anvendelse av metoden
Lineær optimalisering har mange praktiske bruksområder som et eksempel på et optimaliseringsproblem:
En bedrift kan lage flere produkter med kjent dekningsgrad. Produksjonen av en enhet av hver vare krever en kjent mengde begrensede ressurser. Oppgaven er å lage et produksjonsprogram for å bestemme hvor mye av hvert produkt som skal produseres slik at selskapets fortjeneste maksimeres uten å bryte ressursbegrensninger.
Blandingsproblemer er løsningen på optimaliseringsproblemer knyttet til å kombinere ingredienser til sluttproduktet. Et eksempel på dette er kostholdsproblemet studert av George Danzig i 1947. En rekke råvarer er gitt, som havre, svinekjøtt og solsikkeolje, sammen med deres næringsinnhold, som protein, fett, vitamin A, og deres kilopris. Utfordringen er å blande ett eller flere sluttprodukter fra råvarer til lavest mulig kostnad og samtidig respektere minimums- og maksimumsgrensene for deres næringsverdi.
En klassisk anvendelse av et lineært optimaliseringsproblem er å bestemme ruting for behovtrafikk i tele- eller transportnettverk. Samtidig må strømmer rutes gjennom nettet på en slik måte at alle trafikkkrav oppfylles uten å bryte båndbreddevilkår.
I matematisk teori kan lineær optimalisering brukes til å beregne optimale strategier i nullsum-spill for to personer. I dette tilfellet beregnes sannsynlighetsfordelingen for hver deltaker, som er koeffisienten for tilfeldig blanding av strategiene hans.
Ingen vellykket forretningsprosess i verden er mulig uten optimalisering. Det er mange optimeringsalgoritmer tilgjengelig. Noen metoder er kun egnet for visse typer problemer. Det er viktig å kunne gjenkjenne deres egenskaper og velge riktig løsningsmetode.
