Optimierung hilft Ihnen, das beste Ergebnis zu finden, das Gewinn bringt, Kosten senkt oder einen Parameter festlegt, der Geschäftsprozessfehler verursacht.
Dieser Vorgang wird auch als mathematische Programmierung bezeichnet. Es löst das Problem der Bestimmung der Verteilung begrenzter Ressourcen, die zum Erreichen des vom Leiter des Optimierungsproblems gesetzten Ziels erforderlich sind. Von allen möglichen Optionen ist es wünschenswert, diejenige zu finden, die den steuernden Parameter, zum Beispiel Gewinn oder Kosten, maximiert (oder reduziert). Optimierungsmodelle werden auch als präskriptiv oder normativ bezeichnet, da sie versuchen, eine praktikable Strategie für das Unternehmen zu finden.
Entwicklungsverlauf
Lineare Programmierung (LP) arbeitet mit einer Klasse von Optimierungsproblemen, bei denen alle Einschränkungen linear sind.
Präsentation einer kurzen Geschichte der Entwicklung von LP:
- 1762 löste Lagrange einfache Optimierungsprobleme mit Gleichheitsbeschränkungen.
- 1820 entschied GaußLineares Gleichungssystem mit Elimination.
- Im Jahr 1866 perfektionierte Wilhelm Jordan die Methode, Fehler der kleinsten Quadrate als Anpassungskriterium zu finden. Dies wird jetzt Gauß-Jordan-Methode genannt.
- Der digitale Computer erschien 1945.
- Danzig erfand 1947 die Simplex-Methode.
- 1968 führten Fiacco und McCormick die Inside-Point-Methode ein.
- 1984 wandte Karmarkar die innere Methode an, um lineare Programme zu lösen, und fügte seine innovative Analyse hinzu.
LP hat sich sowohl für die Modellierung realer Probleme als auch als weit verbreitete mathematische Theorie als äußerst leistungsfähiges Werkzeug erwiesen. Viele interessante Optimierungsprobleme sind jedoch nichtlinear.
Was ist in diesem Fall zu tun? Die Untersuchung solcher Probleme beinh altet eine abwechslungsreiche Mischung aus linearer Algebra, multivariater Analysis, numerischer Analyse und Computermethoden. Wissenschaftler entwickeln Rechenalgorithmen, einschließlich Inner-Point-Methoden für lineare Programmierung, Geometrie, Analyse konvexer Mengen und Funktionen und die Untersuchung speziell strukturierter Probleme wie quadratische Programmierung.
Nichtlineare Optimierung vermittelt ein grundlegendes Verständnis der mathematischen Analyse und wird häufig in verschiedenen Bereichen wie Ingenieurwesen, Regressionsanalyse, Ressourcenmanagement, geophysikalische Exploration und Wirtschaft eingesetzt.
Klassifizierung von Optimierungsproblemen
Ein wichtiger SchrittDer Optimierungsprozess ist die Klassifizierung von Modellen, da deren Lösungsalgorithmen an einen bestimmten Typ angepasst sind.
1. Probleme mit diskreter und kontinuierlicher Optimierung. Einige Modelle sind nur sinnvoll, wenn die Variablen Werte aus einer diskreten Teilmenge von ganzen Zahlen annehmen. Andere enth alten Daten, die jeden realen Wert annehmen können. Sie sind in der Regel einfacher zu lösen. Verbesserungen bei Algorithmen, kombiniert mit Fortschritten in der Computertechnologie, haben die Größe und Komplexität eines Optimierungsproblems der linearen Programmierung dramatisch erhöht.
2. Unbegrenzte und begrenzte Optimierung. Ein weiterer wichtiger Unterschied sind Aufgaben, bei denen es keine Einschränkung für Variablen gibt. Sie kann weit reichen von einfachen Schätzern bis hin zu Gleichheits- und Ungleichheitssystemen, die komplexe Beziehungen zwischen Daten modellieren. Solche Optimierungsprobleme können nach der Art der Funktionen weiter klassifiziert werden (linear und nichtlinear, konvex und glatt, differenzierbar und nicht differenzierbar).
3. Machbarkeitsaufgaben. Ihr Ziel ist es, Variablenwerte zu finden, die Modellbeschränkungen ohne spezifisches Optimierungsziel erfüllen.
4. Komplementaritätsaufgaben. Sie sind in Technik und Wirtschaft weit verbreitet. Ziel ist es, eine Lösung zu finden, die die Komplementaritätsbedingungen erfüllt. In der Praxis werden Aufgaben mit mehreren Zielen oft in Einzelziele umformuliert.
5. Deterministische versus stochastische Optimierung. Die deterministische Optimierung geht davon aus, dass die Daten füraufgaben sind absolut korrekt. Bei vielen aktuellen Themen können sie jedoch aus verschiedenen Gründen nicht bekannt sein.
Das erste hat mit einem einfachen Messfehler zu tun. Der zweite Grund ist grundlegender. Sie liegt darin begründet, dass einige Daten Informationen über die Zukunft darstellen, beispielsweise die Nachfrage nach einem Produkt oder der Preis für einen zukünftigen Zeitraum. Beim Optimieren unter stochastischen Optimierungsbedingungen wird Unsicherheit in das Modell aufgenommen.
Hauptkomponenten
Die Zielfunktion ist diejenige, die minimiert oder maximiert werden soll. Die meisten Arten von Optimierungsproblemen haben eine Zielfunktion. Wenn nicht, können sie oft so umformuliert werden, dass sie funktionieren.
Zwei Ausnahmen von dieser Regel:
1. Zielsuchaufgabe. In den meisten Geschäftsanwendungen möchte der Manager ein bestimmtes Ziel erreichen und gleichzeitig Modellbeschränkungen erfüllen. Der Benutzer möchte nicht unbedingt etwas optimieren, daher macht es keinen Sinn, eine Zielfunktion zu definieren. Dieser Typ wird allgemein als Erfüllbarkeitsproblem bezeichnet.
2. Viele objektive Funktionen. Häufig möchte ein Benutzer mehrere unterschiedliche Ziele gleichzeitig optimieren. Sie sind normalerweise nicht kompatibel. Variablen, die für ein Ziel optimiert werden, sind möglicherweise nicht die besten für andere.
Komponententypen:
- Eine kontrollierte Eingabe ist eine Menge von Entscheidungsvariablen, die den Wert einer Zielfunktion beeinflussen. Bei einer Produktionsaufgabe können Variablen die Verteilung der verschiedenen verfügbaren Ressourcen oder die dafür erforderliche Arbeit umfassenjede Aktion.
- Constraints sind Beziehungen zwischen Entscheidungsvariablen und Parametern. Bei einem Produktionsproblem macht es keinen Sinn, viel Zeit mit irgendeiner Aktivität zu verbringen, also beschränken Sie alle "temporären" Variablen.
- Mögliche und optimale Lösungen. Der Wert der Entscheidung für Variablen, unter dem alle Nebenbedingungen erfüllt sind, heißt erfüllbar. Die meisten Algorithmen finden es zuerst und versuchen dann, es zu verbessern. Schließlich ändern sie Variablen, um von einer zulässigen Lösung zu einer anderen zu gelangen. Dieser Vorgang wird wiederholt, bis die Zielfunktion ihr Maximum oder Minimum erreicht. Dieses Ergebnis wird als optimale Lösung bezeichnet.
Algorithmen von Optimierungsproblemen, die für die folgenden mathematischen Programme entwickelt wurden, sind weit verbreitet:
- Konvex.
- Trennbar.
- Quadratisch.
- Geometrisch.
Google Linear Solvers
Lineare Optimierung oder Programmierung ist die Bezeichnung für den Rechenprozess zur optimalen Lösung eines Problems. Es wird als eine Reihe linearer Beziehungen modelliert, die in vielen wissenschaftlichen und technischen Disziplinen auftreten.
Google bietet drei Möglichkeiten, um lineare Optimierungsprobleme zu lösen:
- Glop Open-Source-Bibliothek.
- Add-on zur linearen Optimierung für Google Tabellen.
- Linearer Optimierungsdienst in Google Apps Script.
Glop ist in Google integriertlinearer Löser. Es ist in Open Source verfügbar. Sie können auf Glop über den OR-Tools Linear Solver Wrapper zugreifen, der ein Wrapper für Glop ist.
Lineares Optimierungsmodul für Google Sheets ermöglicht es Ihnen, eine lineare Darstellung des Optimierungsproblems durch Eingabe von Daten in eine Tabelle durchzuführen.
Quadratische Programmierung
Die Premium Solver-Plattform verwendet eine erweiterte LP/quadratische Version der Simplex-Methode mit LP- und QP-Problemverarbeitungsgrenzen von bis zu 2000 Entscheidungsvariablen.
SQP Solver für große Probleme verwendet eine moderne Implementierung der Active-Set-Methode mit Sparseness, um Probleme der quadratischen Programmierung (QP) zu lösen. Die XPRESS Solver-Engine verwendet eine natürliche Erweiterung der „Interior Point“- oder Newton-Barrieren-Methode, um QP-Probleme zu lösen.
MOSEK Solver wendet eingebettete "Inside Point"- und Auto-Dual-Methoden an. Dies ist besonders effektiv bei lose gekoppelten QP-Problemen. Es kann auch die Probleme der Scale Quadratic Constraint (QCP) und Second Order Cone Programming (SOCP) lösen.
Berechnungen mit mehreren Operationen
Sie werden sehr erfolgreich bei der Verwendung von Microsoft Office-Funktionen eingesetzt, beispielsweise um Optimierungsprobleme in Excel zu lösen.
In der obigen Tabelle sind die Symbole:
- K1 - K6 - Kunden, die Waren bereitstellen müssen.
- S1 - S6 sind potenzielle Produktionsstandorte, die dafür gebaut werden könnten. Kann erstellt werden1, 2, 3, 4, 5 oder alle 6 Standorte.
Für jede in Sp alte I (Fix) aufgeführte Einrichtung fallen Fixkosten an.
Wenn der Standort nichts ändert, zählt er nicht. Dann fallen keine Fixkosten an.
Identifizieren Sie potenzielle Standorte, um die niedrigsten Kosten zu erzielen.
Unter diesen Bedingungen ist der Standort entweder etabliert oder nicht. Diese beiden Zustände sind: "TRUE - FALSE" oder "1 - 0". Es gibt sechs Zustände für sechs Standorte, zum Beispiel ist 000001 auf nur den sechsten eingestellt, 111111 auf alle.
Im binären Zahlensystem gibt es genau 63 verschiedene Möglichkeiten von 000001 (1) bis 111111 (63).
L2-L64 sollte jetzt {=MULTIPLE OPERATION (K1)} lauten, das sind die Ergebnisse aller Alternativlösungen. Dann ist der Minimalwert=Min (L) und die entsprechende Alternative ist INDEX (K).
CPLEX Ganzzahlprogrammierung
Manchmal reicht eine lineare Beziehung nicht aus, um ein Geschäftsproblem auf den Punkt zu bringen. Dies gilt insbesondere dann, wenn Entscheidungen diskrete Entscheidungen beinh alten, z. B. ob ein Lager an einem bestimmten Ort eröffnet werden soll oder nicht. In diesen Situationen muss die ganzzahlige Programmierung verwendet werden.
Wenn das Problem sowohl diskrete als auch kontinuierliche Entscheidungen beinh altet, handelt es sich um ein gemischtes ganzzahliges Programm. Es kann lineare, konvex-quadratische Probleme und die gleichen Nebenbedingungen zweiter Ordnung haben.
Ganzzahlige Programme sind viel komplexer als lineare Programme, aber sie haben wichtige Geschäftsanwendungen. SoftwareDie CPLEX-Software verwendet komplexe mathematische Methoden, um ganzzahlige Probleme zu lösen. Seine Methoden umfassen die systematische Suche nach möglichen Kombinationen diskreter Variablen unter Verwendung linearer oder quadratischer Softwarerelaxationen, um Grenzen für den Wert der optimalen Lösung zu berechnen.
Sie verwenden auch LP und andere Optimierungsmethoden zur Problemlösung, um Einschränkungen zu berechnen.
Standard Microsoft Excel Solver
Diese Technologie verwendet die grundlegende Implementierung der wichtigsten Simplex-Methode, um LP-Probleme zu lösen. Es ist auf 200 Variablen begrenzt. "Premium Solver" verwendet ein verbessertes primäres Simplex-Verfahren mit doppelseitigen Grenzen für Variablen. Die Premium-Solver-Plattform verwendet eine erweiterte Version des LP/quadratischen Simplex-Solvers, um ein Optimierungsproblem mit bis zu 2000 Entscheidungsvariablen zu lösen.
Large-Scale LP für die Premium Solver-Plattform wendet eine hochmoderne Implementierung der einfachen und doppelten Simplex-Methode an, die Sparsity im LP-Modell verwendet, um Zeit und Speicher zu sparen, erweiterte Strategien für die Aktualisierung und Refactoring-Matrizen, Mehrfach- und Teilpreise und Rotationen sowie zur Überwindung von Degeneration. Diese Engine ist in drei Versionen erhältlich (kann bis zu 8.000, 32.000 oder unbegrenzte Variablen und Grenzen verarbeiten).
MOSEK Solver umfasst Primary und Dual Simplex, eine Methode, die auch Sparsity ausnutzt und fortschrittliche Strategien für die Matrixaktualisierung und "Refaktorisierung" verwendet. Es löst Probleme von unbegrenzter Größe, wargetestet an linearen Programmierproblemen mit Millionen von Entscheidungsvariablen.
Schritt-für-Schritt-Beispiel in EXCEL
Führen Sie die folgenden Schritte aus, um das Optimierungsproblemmodell in Excel zu definieren:
- Organisieren Sie die Daten für das Problem in einer Tabellenkalkulation in logischer Form.
- Wählen Sie eine Zelle aus, um jede Variable zu speichern.
- Erstellen Sie in der Zelle eine Formel zur Berechnung des mathematischen Zielmodells des Optimierungsproblems.
- Formeln erstellen, um die linke Seite jeder Bedingung zu berechnen.
- Verwenden Sie Dialogfelder in Excel, um Solver über Entscheidungsvariablen, Ziele, Einschränkungen und gewünschte Grenzen dieser Parameter zu informieren.
- Führen Sie "Solver" aus, um die optimale Lösung zu finden.
- Excel-Tabelle erstellen.
- Organisieren Sie die Daten für das Problem in Excel, wo die Formel für die Zielfunktion und die Nebenbedingung berechnet wird.
In der obigen Tabelle wurden die Zellen B4, C4, D4 und E4 reserviert, um die Entscheidungsvariablen X 1, X 2, X 3 und X 4 darzustellen. Entscheidungsbeispiele:
- Das Produktmixmodell (450 $, 1150 $, 800 $ und 400 $ Gewinn pro Produkt) wurde in die Zellen B5, C5, D5 bzw. E5 eingegeben. Dadurch kann das Ziel berechnet werden in F5=B5B4 + C5C4 + D5D4 + E5E4 oder F5:=SUMPRODUCT (B5: E5, B4: E4).
- Geben Sie in B8 die Ressourcenmenge ein, die für die Herstellung jedes Produkttyps erforderlich ist.
- Formel für F8:=SUMPRODUKT(B8:E8, $B$4:$E$4).
- Kopieren Sie diesFormel in F9. Dollarzeichen in $B$4:$E$4 zeigen an, dass dieser Zellbereich konstant bleibt.
- Geben Sie in G8 die verfügbare Menge an Ressourcen jedes Typs ein, die den Werten der Einschränkungen auf der rechten Seite entsprechen. Dadurch können Sie sie wie folgt ausdrücken: F11<=G8: G11.
- Dies entspricht vier Grenzwerten F8<=G8, F9 <=G9, F10 <=G10 und F11=0
Praktische Anwendungsgebiete der Methode
Lineare Optimierung hat viele praktische Anwendungen als Beispiel für ein Optimierungsproblem:
Ein Unternehmen kann mehrere Produkte mit bekanntem Deckungsbeitrag herstellen. Die Produktion einer Einheit jedes Artikels erfordert eine bekannte Menge an begrenzten Ressourcen. Die Aufgabe besteht darin, ein Produktionsprogramm zu erstellen, um festzulegen, wie viel von jedem Produkt produziert werden soll, damit der Gewinn des Unternehmens maximiert wird, ohne Ressourcenbeschränkungen zu verletzen.
Mischprobleme sind die Lösung für Optimierungsprobleme im Zusammenhang mit der Kombination von Zutaten zum Endprodukt. Ein Beispiel dafür ist das von George Danzig 1947 untersuchte Ernährungsproblem. Eine Reihe von Rohstoffen wie Hafer, Schweinefleisch und Sonnenblumenöl werden zusammen mit ihrem Nährwert wie Protein, Fett, Vitamin A und ihrem Preis pro Kilogramm angegeben. Die Herausforderung besteht darin, ein oder mehrere Endprodukte aus Rohstoffen zu möglichst geringen Kosten zu mischen und dabei die Mindest- und Höchstgrenzen für ihren Nährwert einzuh alten.
Eine klassische Anwendung eines linearen Optimierungsproblems besteht darin, das Routing nach Bedarf zu bestimmenDatenverkehr in Telekommunikations- oder Transportnetzen. Gleichzeitig müssen Flüsse so durch das Netzwerk geleitet werden, dass alle Verkehrsanforderungen erfüllt werden, ohne die Bandbreitenbedingungen zu verletzen.
In der mathematischen Theorie kann die lineare Optimierung verwendet werden, um optimale Strategien in Nullsummenspielen für zwei Personen zu berechnen. In diesem Fall wird die Wahrscheinlichkeitsverteilung für jeden Teilnehmer berechnet, das ist der Koeffizient der zufälligen Mischung seiner Strategien.
Kein erfolgreicher Geschäftsprozess der Welt ist ohne Optimierung möglich. Es stehen viele Optimierungsalgorithmen zur Verfügung. Einige Methoden eignen sich nur für bestimmte Arten von Problemen. Es ist wichtig, ihre Eigenschaften zu erkennen und den geeigneten Lösungsweg auszuwählen.
