Modell STAND ORT
γ
i
∈ {0, 1} i = 1, 2, ..., I
Disaggregierte Formulierung (Valid inequalities)
x
ij
≤ d
j
· γ
i
i = 1, 2, ..., I; j = 1, 2, ..., J
Diese Neb enbedingungen werden zum Modell STANDORT hinzugef¨ugt.
5.2 Erl¨auterungen zur disaggregierten Formulierung
Das Modell STANDORT (SPLP, Simple Plant Location Problem) ist ein gemischt-ganz-
zahliges Optimierungsproblem. Zu seiner L¨osung kann man ein Branch-and-Bound-
Verfahren einsetzen. Dabei ersetzt man die Restriktionen γ
i
∈ {0, 1} durch 0 ≤ γ
i
≤ 1 f¨ur
alle oder einige der γ-Variablen. Man relaxiert das Modell. Ein so entstandenes (partiell)
relaxiertes Modell ist ein kontinuierliches LP-Modell, das mit dem Simplex-Verfahren op-
timal gel¨ost werden kann. Die optimale L¨osung enth¨alt normalerweise nicht-ganzahlige
(und damit auch f¨ur da s urspr¨ungliche Modell nicht-zul¨assige, d. h. nicht-bin¨are) Werte
der γ-Variablen. Der Zielwert der optimalen L¨osung des relaxierten Modells bildet
eine unter e Schranke (lower bound, LB) des optimalen Zielwertes f¨ur das Modell mit
zul¨assigen (bin¨aren) Werten der γ-Variablen.
Sind alle γ-Variablen in der optimalen L¨osung eines relaxierten LP-Modells ganzzahlig,
dann hat man eine zul¨assige L¨osung gefunden. Ihr Zielwert bildet eine obere Schranke
(upper bound, UB) f¨ur den optimalen Zielwert des Modells STANDORT. Die Differenz
dieser beiden Schranken gibt die maximale Abweichung einer gefundenen L¨osung vom
exakten Optimum an, das zwischen diesen beiden Schranken liegt.
Im Rahmen des Branch&Bound-Verfahrens verzweigt man ¨uber eine ausgew¨ahlte γ-
Variable und zerteilt den L¨osungsraum dabei in zwei disjunkte Teilmengen, f¨ur die j eweils
ein (partiell, d. h. nur bez¨uglich einiger Bin¨ar variablen) relaxiertes LP-Modell entsteht.
Nach der L¨osung eines (par t iell) relaxierten Problems kann der Verzweigungsprozeß an
dem betreffenden Ast des L¨osungsbaums abgebrochen werden,
1. wenn das relaxierte Problem keine zul¨assige L¨osung hat
2. wenn alle ganzzahligen Variablen auch tats¨achlich ganzzahlige Werte annehmen
(dann hat man m¨oglicherweise eine bessere obere Schranke gefunden)
3. wenn der optimale Zielwert des aktuellen (relaxierten) Problems schlechter
ist als der Zielwert der besten bekannte g anzzahligen L¨osung (obere Schranke). In
diesem Fall f¨uhren weitere Verzweigungen nur noch zu L¨osungen, die nicht besser
sein k¨onnen als die beste bisher bekannte zul¨assige L¨osung.
Das folgende Bild zeigt einen Teil des L¨osungsbaums f¨ur ein Problem mit drei potentiellen
Standorten.
11