Optimierungsmodelle

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.

Modellierung 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 v_j verkauft und die variablen Herstellkosten betragen k_j. Das heißt, der Deckungsbeitrag pro Stück db_j  ist gleich v_j minus k_j. Ein Produkt j wird auf 1 bis m verschiedenen Maschinen i bearbeitet. Die Maschinen haben eine begrenzte Produktionskapazität in Maschinenstunden c_i. Die Bearbeitung eines Produkts j auf Maschine i benötigt a_ij  Maschinenstunden. Es kann eine maximale Menge b_j  je Produkt abgesetzt werden.

direkt ins Video springen

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 x_j 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 a_ij 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.

direkt ins Video springen

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 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!