Optimering hjälper dig att hitta det bästa resultatet som ger vinst, minskar kostnaderna eller ställer in en parameter som orsakar affärsprocessmisslyckanden.
Denna process kallas även matematisk programmering. Det löser problemet med att bestämma fördelningen av begränsade resurser som är nödvändiga för att uppnå det mål som satts upp av chefen för optimeringsproblemet. Av alla möjliga alternativ är det önskvärt att hitta den som maximerar (eller minskar) den styrande parametern, till exempel vinst eller kostnad. Optimeringsmodeller kallas också preskriptiva eller normativa eftersom de försöker hitta en genomförbar strategi för verksamheten.
Utvecklingshistorik
Linjär programmering (LP) fungerar med en klass av optimeringsproblem där alla begränsningar är linjära.
Presenterar en kort historik om utvecklingen av LP:
- År 1762 löste Lagrange enkla optimeringsproblem med jämlikhetsbegränsningar.
- År 1820 bestämde Gausslinjärt ekvationssystem med eliminering.
- År 1866 fulländade Wilhelm Jordan metoden att hitta minsta kvadraters fel som ett passningskriterium. Detta kallas nu Gauss-Jordan-metoden.
- Den digitala datorn dök upp 1945.
- Danzig uppfann simplexmetoder 1947.
- 1968 introducerade Fiacco och McCormick Inside Point-metoden.
- 1984 använde Karmarkar interiörmetoden för att lösa linjära program och lade till sin innovativa analys.
LP har visat sig vara ett extremt kraftfullt verktyg både för att modellera verkliga problem och som en allmänt tillämpad matematisk teori. Många intressanta optimeringsproblem är dock icke-linjära.
Vad ska jag göra i det här fallet? Studiet av sådana problem involverar en varierad blandning av linjär algebra, multivariaträkning, numerisk analys och beräkningsmetoder. Forskare utvecklar beräkningsalgoritmer, inklusive inre punktmetoder för linjär programmering, geometri, analys av konvexa mängder och funktioner, och studier av speciellt strukturerade problem som kvadratisk programmering.
Icke-linjär optimering ger en grundläggande förståelse för matematisk analys och används i stor utsträckning inom olika områden som teknik, regressionsanalys, resurshantering, geofysisk utforskning och ekonomi.
Klassificering av optimeringsproblem
Ett viktigt steg inOptimeringsprocessen är klassificeringen av modeller, eftersom deras lösningsalgoritmer är anpassade till en viss typ.
1. Problem med diskret och kontinuerlig optimering. Vissa modeller är bara meningsfulla om variablerna tar värden från en diskret delmängd av heltal. Andra innehåller data som kan få vilket verkligt värde som helst. De är oftast lättare att lösa. Förbättringar av algoritmer, i kombination med framsteg inom datorteknik, har dramatiskt ökat storleken och komplexiteten hos ett linjärt programmeringsoptimeringsproblem.
2. Obegränsad och begränsad optimering. En annan viktig skillnad är uppgifter där det inte finns några begränsningar för variabler. Det kan sträcka sig brett från enkla estimatorer till system av likheter och ojämlikheter som modellerar komplexa samband mellan data. Sådana optimeringsproblem kan klassificeras ytterligare efter funktionernas natur (linjära och icke-linjära, konvexa och jämna, differentierbara och icke-differentierade).
3. Genomförbarhetsuppgifter. Deras mål är att hitta variabelvärden som uppfyller modellens begränsningar utan något specifikt optimeringsmål.
4. Komplementaritetsuppgifter. De används ofta inom teknik och ekonomi. Målet är att hitta en lösning som uppfyller komplementaritetsvillkoren. I praktiken omformuleras uppgifter med flera mål ofta till enstaka mål.
5. Deterministisk kontra stokastisk optimering. Deterministisk optimering förutsätter att data föruppdragen är helt korrekta. Men i många aktuella frågor kan de inte vara kända av flera anledningar.
Den första har att göra med ett enkelt mätfel. Det andra skälet är mer grundläggande. Det ligger i det faktum att vissa data representerar information om framtiden, till exempel efterfrågan på en produkt eller priset för en framtida tidsperiod. Vid optimering under stokastiska optimeringsförhållanden ingår osäkerhet i modellen.
Huvudkomponenter
Den objektiva funktionen är den som ska minimeras eller maximeras. De flesta typer av optimeringsproblem har en objektiv funktion. Om inte kan de ofta omformuleras till att fungera.
Två undantag från denna regel:
1. Målsökningsuppgift. I de flesta affärsapplikationer vill chefen uppnå ett specifikt mål samtidigt som modellen uppfyller kraven. Användaren vill inte särskilt optimera något, så det är ingen mening att definiera en objektiv funktion. Denna typ kallas vanligtvis ett tillfredsställelseproblem.
2. Många objektiva egenskaper. Ofta vill en användare optimera flera olika mål samtidigt. De är vanligtvis inkompatibla. Variabler som optimerar för ett mål kanske inte är de bästa för andra.
Komponenttyper:
- En kontrollerad input är en uppsättning beslutsvariabler som påverkar värdet av en objektiv funktion. I en produktionsuppgift kan variabler inkludera fördelningen av de olika tillgängliga resurserna eller den arbetskraft som krävs för attvarje åtgärd.
- Begränsningar är samband mellan beslutsvariabler och parametrar. För ett produktionsproblem är det inte meningsfullt att lägga mycket tid på någon aktivitet, så begränsa alla "tillfälliga" variabler.
- Möjliga och optimala lösningar. Värdet av beslutet för variabler, under vilka alla begränsningar är uppfyllda, kallas tillfredsställbart. De flesta algoritmer hittar det först och försöker sedan förbättra det. Slutligen ändrar de variabler för att flytta från en genomförbar lösning till en annan. Denna process upprepas tills målfunktionen når sitt maximum eller minimum. Detta resultat kallas den optimala lösningen.
Algorithmer för optimeringsproblem som utvecklats för följande matematiska program används i stor utsträckning:
- Konvex.
- Separable.
- Kvadratisk.
- Geometrisk.
Google Linear Solvers
Linjär optimering eller programmering är namnet på beräkningsprocessen för att lösa ett problem optim alt. Den är modellerad som en uppsättning linjära samband som uppstår i många vetenskapliga och ingenjörsvetenskapliga discipliner.
Google erbjuder tre sätt att lösa linjära optimeringsproblem:
- Glop öppen källkodsbibliotek.
- Linjär optimeringstillägg för Google Sheets.
- Linjär optimeringstjänst i Google Apps Script.
Glop är inbyggt i Googlelinjär lösare. Den är tillgänglig i öppen källkod. Du kan komma åt Glop genom OR-Tools linjära lösare, som är en wrapper för Glop.
Linjär optimeringsmodul för Google Sheets låter dig utföra en linjär beskrivning av optimeringsproblemet genom att ange data i ett kalkylark.
Kvadratisk programmering
Premium Solver-plattformen använder en utökad LP/Quadratic-version av Simplex-metoden med LP- och QP-problembearbetningsgränser på upp till 2000 beslutsvariabler.
SQP-lösare för storskaliga problem använder en modern implementering av den aktiva uppsättningsmetoden med gleshet för att lösa problem med kvadratisk programmering (QP). XPRESS Solver-motorn använder en naturlig förlängning av metoden "Interior Point" eller Newton Barrier för att lösa QP-problem.
MOSEK Solver tillämpar inbäddade "Inside Point" och automatiska dubbla metoder. Detta är särskilt effektivt för löst kopplade QP-problem. Det kan också lösa problemen med Scale Quadratic Constraint (QCP) och Second Order Cone Programming (SOCP).
Multi-operation beräkningar
De används ganska framgångsrikt med användning av Microsoft Office-funktioner, till exempel för att lösa optimeringsproblem i Excel.
I tabellen ovan är symbolerna:
- K1 - K6 - kunder som behöver tillhandahålla varor.
- S1 - S6 är potentiella produktionsplatser som skulle kunna byggas för detta. Kan skapas1, 2, 3, 4, 5 eller alla 6 platser.
Det finns fasta kostnader för varje anläggning som anges i kolumn I (Fix).
Om platsen inte ändrar något, räknas det inte. Då blir det inga fasta kostnader.
Identifiera potentiella platser för att få lägsta kostnad.
Under dessa förhållanden är platsen antingen etablerad eller inte. Dessa två tillstånd är: "TRUE - FALSE" eller "1 - 0". Det finns sex tillstånd för sex platser, till exempel är 000001 endast inställt på det sjätte, 111111 är inställt på alla.
I det binära talsystemet finns det exakt 63 olika alternativ från 000001 (1) till 111111 (63).
L2-L64 bör nu läsa {=MULTIPLE OPERATION (K1)}, det här är resultatet av alla alternativa lösningar. Då är minimivärdet=Min (L) och motsvarande alternativ är INDEX (K).
CPLEX heltalsprogrammering
Ibland räcker inte en linjär relation för att komma till kärnan i ett affärsproblem. Detta gäller särskilt när beslut involverar diskreta val, till exempel om man ska öppna ett lager på en viss plats eller inte. I dessa situationer måste heltalsprogrammering användas.
Om problemet involverar både diskreta och kontinuerliga val, är det ett blandat heltalsprogram. Den kan ha linjära, konvexa kvadratiska problem och samma andra ordningens begränsningar.
Heltalsprogram är mycket mer komplexa än linjära program, men de har viktiga affärsapplikationer. programvaraCPLEX-mjukvaran använder komplexa matematiska metoder för att lösa heltalsproblem. Hans metoder innebär att systematiskt söka efter möjliga kombinationer av diskreta variabler med hjälp av linjära eller kvadratiska mjukvaruavslappningar för att beräkna gränser för värdet av den optimala lösningen.
De använder också LP och andra optimeringsproblemlösningsmetoder för att beräkna begränsningar.
Standard Microsoft Excel Solver
Denna teknik använder den grundläggande implementeringen av den huvudsakliga Simplex-metoden för att lösa LP-problem. Den är begränsad till 200 variabler. "Premium Solver" använder en förbättrad primär simplexmetod med dubbelsidiga gränser för variabler. Premium Solver-plattformen använder en utökad version av LP/Quadratic Simplex Solver för att lösa ett optimeringsproblem med upp till 2000 beslutsvariabler.
Storskalig LP för Premium Solver-plattformen tillämpar en toppmodern implementering av den enkla och dubbla simplexmetoden, som använder sparsitet i LP-modellen för att spara tid och minne, avancerade strategier för uppdatering och refaktorisering av matriser, multipla och partiella prissättningar och rotationer, och för att övervinna degeneration. Denna motor finns i tre versioner (kan hantera upp till 8 000, 32 000 eller obegränsade variabler och gränser).
MOSEK Solver inkluderar primär och dubbel simplex, en metod som också utnyttjar sparsitet och använder avancerade strategier för matrisuppdatering och "refaktorisering". Det löser problem av obegränsad storlek, vartestade på linjära programmeringsproblem med miljontals beslutsvariabler.
Steg för steg exempel i EXCEL
För att definiera optimeringsproblemmodellen i Excel, utför följande steg:
- Ordna data för problemet i ett kalkylblad i en logisk form.
- Välj en cell för att lagra varje variabel.
- Skapa i cellen en formel för att beräkna den matematiska målmodellen för optimeringsproblemet.
- Skapa formler för att beräkna vänster sida av varje begränsning.
- Använd dialoger i Excel för att berätta för Solver om beslutsvariabler, mål, begränsningar och önskade gränser för dessa parametrar.
- Kör "Solver" för att hitta den optimala lösningen.
- Skapa ett Excel-ark.
- Ordna data för problemet i Excel där formeln för målfunktionen och begränsningen beräknas.
I tabellen ovan har cellerna B4, C4, D4 och E4 reserverats för att representera beslutsvariablerna X 1, X 2, X 3 och X 4. Beslutsexempel:
- Produktmixmodellen ($450, $1150, $800 och $400 vinst per produkt) angavs i cellerna B5, C5, D5 respektive E5. Detta gör att målet kan beräknas i F5=B5B4 + C5C4 + D5D4 + E5E4 eller F5:=SUMPRODUKT (B5: E5, B4: E4).
- I B8 anger du mängden resurser som krävs för att tillverka varje typ av produkt.
- Formel för F8:=SUMPRODUKT(B8:E8, $B$4:$E$4).
- Kopiera dettaformeln i F9. Dollartecken i $B$4:$E$4 indikerar att detta cellintervall förblir konstant.
- I G8 anger du den tillgängliga mängden resurser av varje typ, motsvarande värdena för begränsningarna till höger. Detta låter dig uttrycka dem så här: F11<=G8: G11.
- Detta motsvarar fyra gränser F8<=G8, F9 <=G9, F10 <=G10 och F11=0
Fält för praktisk tillämpning av metoden
Linjär optimering har många praktiska tillämpningar som exempel på ett optimeringsproblem:
Ett företag kan tillverka flera produkter med en känd täckningsbidrag. Tillverkningen av en enhet av varje artikel kräver en känd mängd begränsade resurser. Uppgiften är att skapa ett produktionsprogram för att avgöra hur mycket av varje produkt som ska produceras så att företagets vinst maximeras utan att bryta mot resursbegränsningar.
Blandningsproblem är lösningen på optimeringsproblem relaterade till att kombinera ingredienser i slutprodukten. Ett exempel på detta är kostproblemet som studerades av George Danzig 1947. Ett antal råvaror ges, såsom havre, fläsk och solrosolja, tillsammans med deras näringsinnehåll, såsom protein, fett, vitamin A och deras pris per kilogram. Utmaningen är att blanda en eller flera slutprodukter från råvaror till lägsta möjliga kostnad samtidigt som minimi- och maxgränserna för deras näringsvärde respekteras.
En klassisk tillämpning av ett linjärt optimeringsproblem är att bestämma rutt för behovtrafik i telekommunikations- eller transportnät. Samtidigt måste flöden dirigeras genom nätet på ett sådant sätt att alla trafikkrav uppfylls utan att bryta bandbreddsvillkoren.
I matematisk teori kan linjär optimering användas för att beräkna optimala strategier i nollsummespel för två personer. I det här fallet beräknas sannolikhetsfördelningen för varje deltagare, vilket är koefficienten för slumpmässig blandning av hans strategier.
Ingen framgångsrik affärsprocess i världen är möjlig utan optimering. Det finns många tillgängliga optimeringsalgoritmer. Vissa metoder är endast lämpliga för vissa typer av problem. Det är viktigt att kunna känna igen deras egenskaper och välja lämplig lösningsmetod.
