Optimalisatie helpt u het beste resultaat te vinden dat winst oplevert, kosten verlaagt of een parameter instelt die storingen in bedrijfsprocessen veroorzaakt.
Dit proces wordt ook wel wiskundig programmeren genoemd. Het lost het probleem op van het bepalen van de verdeling van beperkte middelen die nodig zijn om het doel te bereiken dat is gesteld door het hoofd van het optimalisatieprobleem. Van alle mogelijke opties is het wenselijk om degene te vinden die de controlerende parameter maximaliseert (of vermindert), bijvoorbeeld winst of kosten. Optimalisatiemodellen worden ook prescriptief of normatief genoemd omdat ze een haalbare strategie voor het bedrijf zoeken.
Ontwikkelingsgeschiedenis
Lineair programmeren (LP) werkt met een klasse van optimalisatieproblemen waarbij alle beperkingen lineair zijn.
Een korte geschiedenis van de ontwikkeling van LP presenteren:
- In 1762 loste Lagrange eenvoudige optimalisatieproblemen op met gelijkheidsbeperkingen.
- In 1820 besloot Gausslineair systeem van vergelijkingen met behulp van eliminatie.
- In 1866 perfectioneerde Wilhelm Jordan de methode om kleinste-kwadratenfouten te vinden als een geschikt criterium. Dit wordt nu de Gauss-Jordan-methode genoemd.
- De digitale computer verscheen in 1945.
- Danzig vond in 1947 simplex-methoden uit.
- In 1968 introduceerden Fiacco en McCormick de Inside Point-methode.
- In 1984 paste Karmarkar de interieurmethode toe om lineaire programma's op te lossen en voegde hij zijn innovatieve analyse toe.
LP heeft bewezen een extreem krachtig hulpmiddel te zijn, zowel voor het modelleren van problemen in de echte wereld als als een algemeen toegepaste wiskundige theorie. Veel interessante optimalisatieproblemen zijn echter niet-lineair.
Wat te doen in dit geval? De studie van dergelijke problemen omvat een gevarieerde mix van lineaire algebra, multivariate calculus, numerieke analyse en computationele methoden. Wetenschappers ontwikkelen computationele algoritmen, waaronder methoden voor inwendige punten voor lineair programmeren, geometrie, analyse van convexe verzamelingen en functies, en de studie van speciaal gestructureerde problemen zoals kwadratisch programmeren.
Niet-lineaire optimalisatie biedt een fundamenteel begrip van wiskundige analyse en wordt veel gebruikt op verschillende gebieden, zoals engineering, regressieanalyse, hulpbronnenbeheer, geofysische exploratie en economie.
Classificatie van optimalisatieproblemen
Een belangrijke stap inHet optimalisatieproces is de classificatie van modellen, aangezien hun oplossingsalgoritmen zijn aangepast aan een bepaald type.
1. Problemen met discrete en continue optimalisatie. Sommige modellen hebben alleen zin als de variabelen waarden aannemen van een discrete subset van gehele getallen. Andere bevatten gegevens die elke reële waarde kunnen aannemen. Ze zijn meestal makkelijker op te lossen. Verbeteringen in algoritmen, gecombineerd met vooruitgang in computertechnologie, hebben de omvang en complexiteit van een lineair optimalisatieprobleem voor programmering enorm vergroot.
2. Onbeperkte en beperkte optimalisatie. Een ander belangrijk verschil zijn taken waarbij er geen beperking is op variabelen. Het kan sterk variëren van eenvoudige schatters tot systemen van gelijkheden en ongelijkheden die complexe relaties tussen gegevens modelleren. Dergelijke optimalisatieproblemen kunnen verder worden geclassificeerd volgens de aard van de functies (lineair en niet-lineair, convex en glad, differentieerbaar en niet-differentieerbaar).
3. Haalbaarheidstaken. Hun doel is om variabele waarden te vinden die voldoen aan modelbeperkingen zonder een specifiek optimalisatiedoel.
4. Complementariteit taken. Ze worden veel gebruikt in technologie en economie. Het doel is om een oplossing te vinden die voldoet aan de complementariteitsvoorwaarden. In de praktijk worden taken met meerdere doelen vaak geherformuleerd tot doelen met één doel.
5. Deterministische versus stochastische optimalisatie. Deterministische optimalisatie gaat ervan uit dat de gegevens vooropdrachten zijn volledig correct. Over veel actuele onderwerpen zijn ze echter om een aantal redenen niet bekend.
De eerste heeft te maken met een simpele meetfout. De tweede reden is fundamenteler. Het ligt in het feit dat sommige gegevens informatie over de toekomst vertegenwoordigen, bijvoorbeeld de vraag naar een product of de prijs voor een toekomstige periode. Bij het optimaliseren onder stochastische optimalisatiecondities wordt onzekerheid in het model meegenomen.
Hoofdcomponenten
De doelfunctie is degene die geminimaliseerd of gemaximaliseerd moet worden. De meeste soorten optimalisatieproblemen hebben één objectieve functie. Zo niet, dan kunnen ze vaak opnieuw worden geformuleerd om te werken.
Twee uitzonderingen op deze regel:
1. Doelzoektaak. In de meeste zakelijke toepassingen wil de manager een specifiek doel bereiken en tegelijkertijd voldoen aan de modelbeperkingen. De gebruiker wil niet bepaald iets optimaliseren, dus het heeft geen zin om een objectieve functie te definiëren. Dit type wordt gewoonlijk een verzadigingsprobleem genoemd.
2. Veel objectieve kenmerken. Vaak wil een gebruiker meerdere verschillende doelen tegelijk optimaliseren. Ze zijn meestal onverenigbaar. Variabelen die voor het ene doel optimaliseren, zijn misschien niet het beste voor andere.
Onderdeeltypes:
- Een gecontroleerde invoer is een reeks beslissingsvariabelen die de waarde van een objectieve functie beïnvloeden. In een productietaak kunnen variabelen de verdeling van de verschillende beschikbare middelen of de arbeid die nodig is omelke actie.
- Constraints zijn relaties tussen beslissingsvariabelen en parameters. Voor een productieprobleem heeft het geen zin om veel tijd aan een activiteit te besteden, dus beperk alle "tijdelijke" variabelen.
- Mogelijke en optimale oplossingen. De waarde van de beslissing voor variabelen, waaronder aan alle beperkingen is voldaan, wordt verzadigbaar genoemd. De meeste algoritmen vinden het eerst en proberen het vervolgens te verbeteren. Ten slotte veranderen ze variabelen om van de ene haalbare oplossing naar de andere te gaan. Dit proces wordt herhaald totdat de doelfunctie zijn maximum of minimum bereikt. Dit resultaat wordt de optimale oplossing genoemd.
Algoritmen van optimalisatieproblemen die zijn ontwikkeld voor de volgende wiskundige programma's worden veel gebruikt:
- Convex.
- Scheidbaar.
- Kwadratisch.
- Geometrisch.
Google Linear Solvers
Lineaire optimalisatie of programmering is de naam die wordt gegeven aan het rekenproces om een probleem optimaal op te lossen. Het wordt gemodelleerd als een reeks lineaire relaties die zich voordoen in veel wetenschappelijke en technische disciplines.
Google biedt drie manieren om lineaire optimalisatieproblemen op te lossen:
- Glop open source bibliotheek.
- Lineaire optimalisatie-add-on voor Google Spreadsheets.
- Lineaire optimalisatieservice in Google Apps Script.
Glop is ingebouwd in Googlelineaire oplosser. Het is beschikbaar in open source. Je hebt toegang tot Glop via de OR-Tools lineaire oplosser-wrapper, een wrapper voor Glop.
Lineaire optimalisatiemodule voor Google Spreadsheets stelt u in staat om een lineaire verklaring van het optimalisatieprobleem uit te voeren door gegevens in een spreadsheet in te voeren.
Kwadratische programmering
Het Premium Solver-platform gebruikt een uitgebreide LP/Quadratic-versie van de Simplex-methode met LP- en QP-probleemverwerkingslimieten van maximaal 2000 beslissingsvariabelen.
SQP Solver voor grootschalige problemen gebruikt een moderne implementatie van de active set-methode met schaarste om kwadratische programmering (QP) problemen op te lossen. De XPRESS Solver-engine gebruikt een natuurlijke uitbreiding van de "Interior Point"- of Newton Barrier-methode om QP-problemen op te lossen.
MOSEK Solver past ingesloten "Inside Point" en auto-dual methoden toe. Dit is vooral effectief voor losjes gekoppelde QP-problemen. Het kan ook de Scale Quadratic Constraint (QCP) en Second Order Cone Programming (SOCP) problemen oplossen.
Multi-operatieberekeningen
Ze worden redelijk succesvol gebruikt met het gebruik van Microsoft Office-functies, bijvoorbeeld voor het oplossen van optimalisatieproblemen in Excel.
In de bovenstaande tabel zijn de symbolen:
- K1 - K6 - klanten die goederen moeten leveren.
- S1 - S6 zijn potentiële productielocaties die hiervoor kunnen worden gebouwd. Kan worden gemaakt1, 2, 3, 4, 5 of alle 6 locaties.
Er zijn vaste kosten voor elke faciliteit vermeld in kolom I (Fix).
Als de locatie niets verandert, telt deze niet. Dan zijn er geen vaste kosten.
Identificeer potentiële locaties om de laagste kosten te krijgen.
In deze omstandigheden is de locatie al dan niet vastgesteld. Deze twee toestanden zijn: "TRUE - FALSE" of "1 - 0". Er zijn zes statussen voor zes locaties, bijvoorbeeld 000001 is ingesteld op alleen de zesde, 111111 is ingesteld op alle.
In het binaire getallensysteem zijn er precies 63 verschillende opties van 000001 (1) tot 111111 (63).
L2-L64 zou nu {=MEERVOUDIGE BEDIENING (K1)} moeten zijn, dit zijn de resultaten van alle alternatieve oplossingen. Dan is de minimumwaarde=Min (L) en het corresponderende alternatief is INDEX (K).
CPLEX Integer Programming
Soms is een lineaire relatie niet voldoende om tot de kern van een zakelijk probleem te komen. Dit geldt met name wanneer beslissingen discrete keuzes inhouden, zoals het al dan niet openen van een magazijn op een bepaalde locatie. In deze situaties moet integer programmeren worden gebruikt.
Als het probleem zowel discrete als continue keuzes betreft, is het een gemengd geheel getal-programma. Het kan lineaire, convexe kwadratische problemen hebben en dezelfde beperkingen van de tweede orde.
Integer-programma's zijn veel complexer dan lineaire programma's, maar ze hebben belangrijke zakelijke toepassingen. SoftwareDe CPLEX-software gebruikt complexe wiskundige methoden om integer-problemen op te lossen. Zijn methoden omvatten het systematisch zoeken naar mogelijke combinaties van discrete variabelen met behulp van lineaire of kwadratische softwarerelaxaties om de grenzen van de waarde van de optimale oplossing te berekenen.
Ze gebruiken ook LP en andere methoden voor het oplossen van optimalisatieproblemen om beperkingen te berekenen.
Standaard Microsoft Excel Solver
Deze technologie gebruikt de basisimplementatie van de belangrijkste Simplex-methode om LP-problemen op te lossen. Het is beperkt tot 200 variabelen. "Premium Solver" gebruikt een verbeterde primaire simplex-methode met dubbelzijdige grenzen voor variabelen. Het Premium Solver-platform gebruikt een uitgebreide versie van de LP/Quadratic Simplex Solver om een optimalisatieprobleem op te lossen met maximaal 2000 beslissingsvariabelen.
Large-scale LP voor het Premium Solver-platform past een ultramoderne implementatie toe van de eenvoudige en dubbele simplex-methode, die schaarste in het LP-model gebruikt om tijd en geheugen te besparen, geavanceerde strategieën voor updaten en refactoring van matrices, meervoudige en gedeeltelijke prijsstelling en rotaties, en voor het overwinnen van degeneratie. Deze engine is beschikbaar in drie versies (kunnen tot 8.000, 32.000 of onbeperkte variabelen en limieten aan).
MOSEK Solver omvat primaire en dubbele simplex, een methode die ook gebruik maakt van schaarste en geavanceerde strategieën gebruikt voor matrixupdate en "refactorisatie". Het lost problemen van onbeperkte omvang op, wasgetest op lineaire programmeerproblemen met miljoenen beslissingsvariabelen.
Stap voor stap voorbeeld in EXCEL
Voer de volgende stappen uit om het optimalisatieprobleemmodel in Excel te definiëren:
- Organiseer de gegevens voor het probleem in een spreadsheet in een logische vorm.
- Selecteer een cel om elke variabele op te slaan.
- Maak in de cel een formule voor het berekenen van het wiskundige doelmodel van het optimalisatieprobleem.
- Maak formules om de linkerkant van elke beperking te berekenen.
- Gebruik dialoogvensters in Excel om de Oplosser te vertellen over beslissingsvariabelen, doelen, beperkingen en gewenste grenzen aan die parameters.
- Voer "Oplosser" uit om de optimale oplossing te vinden.
- Maak een Excel-blad.
- Organiseer de gegevens voor het probleem in Excel, waar de formule voor de objectieve functie en beperking wordt berekend.
In de bovenstaande tabel zijn de cellen B4, C4, D4 en E4 gereserveerd om beslissingsvariabelen X 1, X 2, X 3 en X 4 weer te geven. Voorbeelden van beslissingen:
- Het productmixmodel ($ 450, $ 1150, $ 800 en $ 400 winst per product) is ingevoerd in respectievelijk cellen B5, C5, D5 en E5. Hierdoor kan het doel worden berekend in F5=B5B4 + C5C4 + D5D4 + E5E4 of F5:=SOMPRODUCT (B5: E5, B4: E4).
- Voer in B8 de hoeveelheid middelen in die nodig zijn om elk type product te vervaardigen.
- Formule voor F8:=SOMPRODUCT(B8:E8, $B$4:$E$4).
- Kopieer ditformule in F9. Dollartekens in $B$4:$E$4 geven aan dat dit celbereik constant blijft.
- Voer in G8 de beschikbare hoeveelheid middelen van elk type in, overeenkomend met de waarden van de beperkingen aan de rechterkant. Hiermee kunt u ze als volgt uitdrukken: F11<=G8: G11.
- Dit komt overeen met vier limieten F8<=G8, F9 <=G9, F10 <=G10 en F11=0
Praktische toepassingsgebieden van de methode
Lineaire optimalisatie heeft veel praktische toepassingen als voorbeeld van een optimalisatieprobleem:
Een bedrijf kan meerdere producten maken met een bekende contributiemarge. De productie van een eenheid van elk item vereist een bekende hoeveelheid beperkte middelen. De taak is om een productieprogramma op te stellen om te bepalen hoeveel van elk product moet worden geproduceerd, zodat de winst van het bedrijf wordt gemaximaliseerd zonder de beperkte middelen te schenden.
Mengproblemen zijn de oplossing voor optimalisatieproblemen met betrekking tot het combineren van ingrediënten in het eindproduct. Een voorbeeld hiervan is het voedingsprobleem dat in 1947 door George Danzig werd bestudeerd. Een aantal grondstoffen wordt gegeven, zoals haver, varkensvlees en zonnebloemolie, samen met hun voedingswaarde, zoals eiwit, vet, vitamine A, en hun prijs per kilogram. De uitdaging is om tegen de laagst mogelijke kosten één of meerdere eindproducten uit grondstoffen te mengen met respect voor de minimale en maximale limieten voor hun voedingswaarde.
Een klassieke toepassing van een lineair optimalisatieprobleem is het bepalen van routering voor behoeftenverkeer in telecommunicatie- of transportnetwerken. Tegelijkertijd moeten stromen zo door het netwerk worden geleid dat aan alle verkeersvereisten wordt voldaan zonder de bandbreedtevoorwaarden te schenden.
In de wiskundige theorie kan lineaire optimalisatie worden gebruikt om optimale strategieën te berekenen in nulsomspellen voor twee personen. In dit geval wordt de kansverdeling voor elke deelnemer berekend, de coëfficiënt van willekeurige vermenging van zijn strategieën.
Geen succesvol bedrijfsproces ter wereld is mogelijk zonder optimalisatie. Er zijn veel optimalisatie-algoritmen beschikbaar. Sommige methoden zijn alleen geschikt voor bepaalde soorten problemen. Het is belangrijk om hun kenmerken te herkennen en de juiste oplossingsmethode te selecteren.
