Optimierungsmodelle
Du hast manchmal Entscheidungsschwierigkeiten und weißt nicht ob du lieber Kuchen oder Eis essen sollst? Operations Research kann dir bei so manchen Entscheidungen weiterhelfen.
Inhaltsübersicht
Lineare Optimierung in Operations Research
Operations Research wird grundsätzlich zur Entscheidungsunterstützung genutzt. Reale Probleme werden unter Einsatz von mathematischen Modellen und Methoden genau oder annähernd genau gelöst. Ein reales Problem in der Produktionsprogrammplanung ist zum Beispiel zu entscheiden wie viele Einheiten unterschiedlicher Produkte hergestellt werden sollen, um den größten Gewinn zu erzielen.
Modelierung eines realen Problems
Wir zeigen dir jetzt wie man ein solches Problem modelliert. Es sollen 1 bis n verschiedene Produkte j hergestellt werden. Ein Produkt wird zu einem Absatzpreis vj verkauft und die variablen Herstellkosten betragen kj. Das heißt, der Deckungsbeitrag pro Stück dbj ist gleich vj minus kj. Ein Produkt j wird auf 1 bis m verschiedenen Maschinen i bearbeitet. Die Maschinen haben eine begrenzte Produktionskapazität in Maschinenstunden ci. Die Bearbeitung eines Produkts j auf Maschine i benötigt aij Maschinenstunden. Es kann eine maximale Menge bj je Produkt abgesetzt werden.
Gesucht ist jetzt das Produktionsprogramm mit dem maximalen Gesamt-Deckungsbeitrag, also von welchen Produkten wie viel produziert werden soll. Das ist unsere Zielfunktion, die maximiert werden soll. Sie legt fest, welchen Wert wir optimieren wollen. Wir können dabei ein Maximum oder Minimum suchen. Zum Schluss müssen wir noch eine Entscheidungsvariable xj einführen, die die Produktionsmengen der Produkte j angibt.
Von den Komponenten zum Modell
Damit hast du alle Komponenten des Problems aufgelistet. Diese müssen wir jetzt noch in ein Modell bekommen. Zuerst stellen wir die Zielfunktion auf: Maximiere den Deckungsbeitrag in Abhängigkeit von x ist gleich der Deckungsbeitrag von Produkt j mal der Produktionsmenge von Produkt j. Und das summierst du über alle Produkte j von 1 bis n auf. Jetzt brauchst du noch Nebenbedingungen, denn nur mit der Zielfunktion würden ja unendlich viele Produkte produziert werden. Die Nebenbedingungen schränken also deine Zielfunktion ein. Diese aufzustellen braucht etwas Übung, da sie nicht immer sofort einleuchten oder auffallen.
Nebenbedingungen bei der linearen Optimierung
Die erste Nebenbedingung begrenzt, dass die Bearbeitungsdauer aij eines Produkts j auf Maschine i mal der Produktionsmenge des Produkts j kleiner oder gleich der Produktionskapazität der Maschine i sein muss. Denn sonst könnte ja die Kapazität einer Maschine gesprengt werden, was technisch nicht möglich ist. Das muss jetzt noch über alle Produkte j von 1 bis n aufsummiert werden. Dieser Ausdruck bezieht sich jetzt aber nur auf eine Maschine i. Deswegen müssen wir noch daneben schreiben, dass der Ausdruck für alle Maschinen i = 1,…,m gilt. Alternativ kannst du auch dieses umgedrehte A ( ) verwenden, was „für alle“ bedeutet.
Als zweite Nebenbedingung müssen wir noch die maximale Absatzmenge begrenzen. Also, die Produktionsmenge für Produkt j ist kleiner gleich der Absatzmenge für Produkt j. Und das gilt natürlich für alle Produkte j. Die dritte Nebenbedingung ist fast in jedem Optimierungsmodell enthalten. Nämlich, dass die Entscheidungsvariable nicht negativ werden darf. In unserem Fall muss die Produktionsmenge des Produkts j größer gleich 0 sein. Und das gilt für alle Produkte j. Geschafft! Jetzt hast du ein funktionierendes Optimierungsmodell. Im nächsten Video betrachten wir dir dann ein Beispiel mit richtigen Zahlen.
Definition lineares Optimierungsmodell
Genauer gesagt handelt es sich bei unserem Problem um ein Lineares Optimierungsmodell, weil unsere Zielfunktion und alle Nebenbedingungen lineare Komponenten enthalten. Weitere Unterteilungen der Optimierungsmodelle sind noch ganzzahlig lineare, binär lineare und nichtlineare. Auf die nichtlinearen werden wir in dieser Playlist nicht eingehen, da sie sehr kompliziert zu lösen sind.
Jedes linear zu maximierende Optimierungsproblem lässt sich übrigens auch in ein zu minimierendes transformieren und umgekehrt. Dazu änderst du bei jedem Koeffizienten in der Zielfunktion einfach das Vorzeichen. Eine „kleiner-gleich-Nebenbedingung“ wird durch die Multiplikation beider Seiten mit minus 1 in eine „größer-gleich-Restriktion“ transformiert. Wenn eine Nebenbedingung als Gleichung vorliegt, wird sie in zwei Ungleichungen umgewandelt mit „größer-gleich“ und „kleiner-gleich“. Die Nichtnegativitätsbedingung bleibt als einzige gleich.
So, die Theorie sitzt! Im nächsten Video legen wir dann mit der Praxis los. Bis gleich!