Lineare Programmierung: Modellbildung, Restriktionen & Schattenpreisanalyse

Erstellung eines linearen Programmierungsmodells

Verfahren zur Herstellung eines linearen Programmierungsmodells:

• Das Ziel bestimmen und definieren (entweder maximieren oder minimieren).
• Entscheidungsalternativen entwickeln.
• Die Entscheidungsvariablen definieren (z.B. X1, X2, ..., Xn).
• Eine Liste der relevanten Einschränkungen erstellen.
• Die Zielfunktion definieren, z.B.: Max Z = 40 X1 + 50 X2.

Arten von Einschränkungen in der linearen Programmierung

Einschränkungen (Restriktionen) sind Bedingungen, die die Verfügbarkeit von Ressourcen und die Notwendigkeit, Verpflichtungen für den Zeitraum zu erfüllen, berücksichtigen.

Im Folgenden werden verschiedene Arten von Restriktionen erläutert:

• Kapazitätsengpässe und/oder Ressourcenverfügbarkeit: Dies sind Grenzen, die auf Systembeschränkungen hinsichtlich der Anzahl der Geräte, des Raums, der Finanzierung, der Rohstoffe und der verfügbaren Arbeitskräfte zurückzuführen sind. Ein Beispiel wäre die Einschränkung bezüglich der verfügbaren Flächen für Kulturpflanzen. Diese Einschränkungen werden als Ungleichungen des Typs (≤) ausgedrückt. Was wir von einer Ressource verbrauchen, darf nicht größer sein als das, was uns zur Verfügung steht.
• Marktbeschränkungen: Es gibt Grenzen (untere, obere oder beide) für die Menge des verkauften oder verwendeten Produkts. Zum Beispiel der maximale und minimale historische Umsatz für ein Produkt. Letzteres (der minimale Umsatz) stellt eine Anforderung oder Ungleichung des Typs (≥) dar, denn wenn ein bestimmter Produktabsatz vertraglich vereinbart ist, kann ich nicht weniger als diesen Betrag produzieren, da ich sonst meine Lieferverpflichtungen nicht erfüllen könnte. Ersteres (der maximale Umsatz) ist eine Beschränkung oder Ungleichung des Typs (≤), da ich nicht mehr Produkt produzieren sollte, als ich historisch zu jeder Jahreszeit verkaufen konnte.
• Qualitäts- oder Zusammensetzungsbeschränkungen einer Mischung: Diese Einschränkungen begrenzen die Mischung von Inhaltsstoffen, die in der Regel die Qualität der Produkte definieren. Diese Beschränkungen können als Begrenzungen (≤), Anforderungen (≥) oder restriktivere Anforderungen des Typs (=) formuliert werden.
• Produktionstechnische oder Materialbilanz-Beschränkungen: Dies sind Beschränkungen, die den Output eines Prozesses in Abhängigkeit von den Inputs definieren, oft unter Berücksichtigung von Verschwendung oder Ertragsverlust. Diese Einschränkungen können, wie oben erwähnt, ebenfalls als Begrenzungen (≤), Anforderungen (≥) oder restriktivere Anforderungen des Typs (=) formuliert werden, abhängig vom zu modellierenden Prozess.
• Definitionsbeschränkungen: Diese Einschränkungen definieren eine Variable in Abhängigkeit von anderen. Oft stammen diese Einschränkungen aus buchhalterischen Definitionen oder Materialbilanzen, wie z.B. die Beziehung, dass die Menge eines Produkts gleich dem sein muss, was verkauft wird plus dem, was im Lager verbleibt. Diese Einschränkungen sind in der Regel vom Typ Anforderungen (=).

Charakterisierung der optimalen Lösung

Arten von Restriktionen (Constraints)

• Aktive Restriktionen: Diese definieren direkt die Position des Optimums.
• Inaktive Restriktionen: Diese sind nicht direkt an der Bestimmung der optimalen Lage beteiligt.
• Redundante Restriktionen: Dies sind inaktive Restriktionen, die weder direkt noch indirekt an der Bestimmung der Grenzen des zulässigen Lösungsbereichs beteiligt sind.

Schattenpreis von Restriktionen (Constraint Shadow Price)

Der Schattenpreis einer Restriktion ist ein quantitatives Maß dafür, wie die einzelnen Restriktionen eines Systems den optimalen Wert der Zielfunktion beeinflussen, d.h. ob dieser besser oder schlechter wird. Es gibt zwei äquivalente Definitionen für den Schattenpreis:

• Definition Nr. 1: Die Rate der Verbesserung des optimalen Wertes der Zielfunktion für jede Einheit, um die der freie Term einer Restriktion erhöht wird.
• Definition Nr. 2: Die Rate der Verschlechterung des optimalen Wertes der Zielfunktion für jede Einheit, um die der freie Term einer Restriktion verringert wird.

Diese beiden Definitionen basieren auf der Annahme, dass der Schattenpreis positiv ist.

Normalerweise ist der Schattenpreis einer aktiven Restriktion vom Typ Begrenzung (≤) immer positiv.

Wenn der Schattenpreis einer Restriktion negativ ist, was normalerweise bei Restriktionen vom Typ Anforderung (≥) der Fall ist, ist der Effekt auf die Zielfunktion entgegengesetzt zur Definition: Wenn der freie Term erhöht wird, verschlechtert sich der Wert; beim Absenken verbessert er sich.

Wertebereiche für den Schattenpreis

• Der Schattenpreis einer Restriktion ist nicht negativ (≥ 0), wenn die Restriktion vom Typ Begrenzung (≤) ist.
• Der Schattenpreis einer aktiven Restriktion ist nicht positiv (≤ 0), wenn die Restriktion vom Typ Anforderung (≥) ist.
• Der Schattenpreis einer aktiven Restriktion kann positiv, negativ oder gleich 0 sein, wenn die Restriktion vom Typ Gleichheit (=) ist; dies hängt vom jeweiligen Modell ab.
• Der Schattenpreis einer inaktiven Restriktion ist immer Null.

Gültigkeitsbereich des Schattenpreises

• Der Wert des Schattenpreises einer Restriktion ist nur gültig für die Erhöhung oder Verringerung ihres freien Terms auf solche Werte, die nicht dazu führen, dass eine der aktiven Restriktionen der ursprünglichen optimalen Lösung aufhört, aktiv zu sein.
• Der optimale Wert wird sich verbessern (bei Maximierung zunehmen, bei Minimierung abnehmen), wenn der Wert des freien Terms einer aktiven Restriktion vom Typ Begrenzung (≤) erhöht wird.
• Der optimale Wert wird sich verschlechtern (bei Maximierung abnehmen, bei Minimierung zunehmen), wenn der Wert des freien Terms einer aktiven Restriktion vom Typ Begrenzung (≤) verringert wird.
• Der optimale Wert wird sich verbessern (bei Maximierung zunehmen, bei Minimierung abnehmen), wenn der Wert des freien Terms einer aktiven Restriktion vom Typ Anforderung (≥) verringert wird.
• Der optimale Wert wird sich verschlechtern (bei Maximierung abnehmen, bei Minimierung zunehmen), wenn der Wert des freien Terms einer aktiven Restriktion vom Typ Anforderung (≥) erhöht wird.
• Der optimale Wert wird seinen Wert behalten (sich nicht ändern), wenn der Wert des freien Terms einer inaktiven Restriktion jeglicher Art erhöht oder verringert wird.