Plor

min K = f * B/q + l * q/2

mit f = bestellfixe Kosten

B = Periodenbedarf

l = Lagerkostensatz

q = Losgröße

q= Wurzel( 2 * f * B / l)

t = Wurzel ( (2*f) / l*B) )

1. Lagerbilanzgleichungen: yt = yt-1 + qt – Bt

Der Lagerbestand am Ende einer Periode (yt) errechnet sich aus dem Anfangsbestand zu Beginn der Periode (yt-1), dem Zugang aus Produktion (qt) und dem „Abgang“ durch die Periodennachfrage (Bt).

2. Logische Rüstbedingung: qt ≤ M ∙ xt (für t =1, 2 und 3)

3. Variablenbeschränkungen: qt, yt ≥ 0 und xt ∈ {0,1} (für t =1, 2 und 3)

Während also für die Losgrößen qt und die Lagerbestände yt wieder einfach die NNB anzugeben ist, ist der Wertebereich

von xt auf die Menge 0 und 1 beschränkt. Entweder es wird ein Los aufgelegt oder eben nicht.

Branching

Sukzessive Zerlegung des Ausgangsproblems P0 in Teilprobleme, indem die

entsprechende zulässige Lösungsmenge X(P0) in disjunkte Teilmengen zerlegt wird.

Bounding für Maximierungs- und Minimierungsprobleme

Ermittlung von oberen bzw. unteren Schranken für die Zielfunktions- (ZF)-Werte

der bei Zerlegung entstehenden Teilprobleme zur Prüfung, ob die weitere Zerlegung

abgebrochen werden kann.

Z bzw. Z : untere bzw. obere ZF-Schranke für Ausgangsproblem P0

Zi bzw. i Z : obere bzw. untere ZF-Schranke für Teilproblem Pi

Abbruchkriterium für Weiterzerlegung von Teilproblem Pi

• bei Max-Aufgabe : Z i < Z

• bei Min-Aufgabe : Zi > Z

Fall (a)

Die optimale Lösung des relaxierten Teilproblems ist nicht besser als die beste

bekannte zulässige Lösung.

Fall (b)

Die optimale Lösung des relaxierten Teilproblems ist besser als die beste

bekannte zulässige Lösung und sie ist zugleich selbst zulässig für das Ausgangsproblem (z.B. ganzzahlig bei LOP-Relaxation).

Fall (c)

Das relaxierte Teilproblem besitzt keine zulässige Lösung, so dass dasselbe auch

für das nicht-relaxierte Teilproblem gelten muss.