Übung 10: Mehrfache Zielsetzung

Grundlagen Operations Research

Video zur Übung

Das Modell

Gegeben ist das folgende Standortplanungsmodell für Verkaufsgebiete (vgl. Vorlesung 10).

Mengen: $\mathcal{I}$: Gebiete mit Index $i$; $\mathcal{J}$: potenzielle Verkaufsstandorte mit Index $j$, $\mathcal{J} \subset \mathcal{I}$; $\mathcal{N}_i$: Nachbarn des Gebiets $i$.

Parameter: $u_i$: Umsatzpotenzial des Gebiets $i$; $d_{ih}$: Distanz zwischen Gebiet $i$ und Gebiet $h$; $F_1^*$: maximaler Umsatz; $F_2^*$: minimale Reisekosten.

Variablen: $X_{ij} = 1$, wenn das Gebiet $i$ dem Verkaufsstandort $j$ zugeordnet wird (0, sonst); $Y_j = 1$, wenn der Verkaufsstandort $j$ errichtet wird (0, sonst); $Q_j$: Umsatz des Verkaufsstandorts $j$; $K_j$: Reisekosten des Verkaufsstandorts $j$.

$$\begin{aligned} \text{maximiere } \; & F_1 \le Q_j + 1000 \cdot (1 - Y_j) && \forall j \\ \text{minimiere } \; & F_2 = \sum_j K_j \\ \text{minimiere } \; & F = \frac{F_1^* - F_1}{F_1^*} + \frac{F_2 - F_2^*}{F_2^*} \\ \text{u.d.N.} \quad & \sum_j Y_j = 2 \\ & X_{ij} \le Y_j && \forall i, j \\ & \sum_j X_{ij} = 1 && \forall i \\ & X_{jj} = Y_j && \forall j \\ & \sum_i u_i \cdot X_{ij} = Q_j && \forall j \\ & \sum_i d_{ij} \cdot X_{ij} = K_j && \forall j \\ & X_{ij} \le \sum_{h \in \mathcal{N}_i \mid d_{ij} > d_{hj}} X_{hj} && \forall i, j \mid d_{ij} > 1 \\ & Q_j, K_j \ge 0 && \forall j \\ & X_{ij}, Y_j \in \{0, 1\} && \forall i, j \end{aligned}$$

Für die Menge der Gebiete $\mathcal{I} = \{1, \dots, 15\}$ sind die Umsatzpotenziale $u_i$:

$i$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$u_i$	2	3	6	4	3	7	6	3	1	7	8	6	3	4	3

Zusätzlich ist eine abstrahierte Ansicht der Gebietsanordnung gegeben. Als potenzielle Verkaufsstandorte wurden $\mathcal{J} = \{2, 5, 11, 14\}$ identifiziert. Die Distanz zwischen zwei benachbarten (Kante an Kante) Gebieten beträgt eine Einheit (d. h. $d_{1,6} = 1$ bzw. $d_{1,7} = 2$):

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

Aufgabe 1

1. Was wird mit der ersten Zielfunktion maximiert?
2. Was wird durch den zweiten Term ($1000 \cdot (1 - Y_j)$) in der ersten Zielfunktion berücksichtigt?
3. Stellen Sie eine Nebenbedingung auf, die fordert, dass nur Gebiete mit einer maximalen Distanz von $d^{\text{MAX}}$ Einheiten einem Standort zugeordnet werden dürfen.
4. Könnte eine Nebenbedingung, die die Einhaltung einer maximalen Distanz $d^{\text{MAX}}$ zwischen einem Standort und zugeordnetem Gebiet fordert, zu einer Unzulässigkeit des Modells führen? Begründen Sie Ihre Antwort!
5. Stellen Sie die Zielfunktion $F$ so um, dass die maximale relative Abweichung des Umsatzbeitrags bzw. Kostenbeitrags vom Optimum minimiert wird! (Hinweis: Sie können hierfür zusätzliche Nebenbedingungen und Variablen einführen.)
6. Bestimmen Sie die zur aktuellen Lösung ($X_{1,2}$, $X_{4,2}$, $X_{7,2}$, $X_{11,2}$, $X_{5,14}$, $X_{8,14}$, $X_{9,14}$, $X_{12,14} = 1$) gehörenden Werte für $X_{ij}$, $Y_j$, $Q_j$, $K_j$ und $F$. (Hinweis: Es müssen nur die von null verschiedenen Werte angegeben werden!)
7. Überprüfen Sie in Julia, ob die aktuelle Lösung optimal ist!

Ihre Lösung in Julia

Bestimmen Sie zuerst die Einzeloptima $F_1^*$ (Maximierung) und $F_2^*$ (Minimierung), danach das Optimum der gemeinsamen Zielfunktion $F$. Nennen Sie Ihr Modell modell:

using JuMP, HiGHS

I = 1:15
J = [2, 5, 11, 14]
u = [2, 3, 6, 4, 3, 7, 6, 3, 1, 7, 8, 6, 3, 4, 3]
zeile(i) = cld(i, 5)
spalte(i) = mod(i - 1, 5) + 1
d(i, h) = abs(zeile(i) - zeile(h)) + abs(spalte(i) - spalte(h))
nachbarn(i) = [h for h in I if d(i, h) == 1]

modell = Model(HiGHS.Optimizer)
set_silent(modell)

# IHR CODE HIER

optimize!(modell)

TippSelbstkontrolle: Maximierung von $F_1$

# Führen Sie diese Zelle nach der Maximierung von F1 aus:
@assert isapprox(objective_value(modell), 33.0; atol = 1e-4) "F1* noch nicht korrekt, prüfen Sie die Min-Umsatz-Bedingung mit 1000·(1-Y)."
println("F1* korrekt: ", objective_value(modell))

TippSelbstkontrolle: Minimierung von $F_2$

# Führen Sie diese Zelle nach der Minimierung von F2 aus:
@assert isapprox(objective_value(modell), 22.0; atol = 1e-4) "F2* noch nicht korrekt, prüfen Sie die Reisekosten-Definition."
println("F2* korrekt: ", objective_value(modell))

TippSelbstkontrolle: gemeinsame Zielfunktion

@assert isapprox(objective_value(modell), 1 / 33; atol = 1e-4) "Noch nicht korrekt, relative Abweichungen: (F1*-F1)/F1* + (F2-F2*)/F2*."
println("Optimum korrekt: F = ", round(objective_value(modell); digits = 4))
println("Vergleichen Sie mit dem F-Wert der in Aufgabenteil 6 gegebenen Lösung!")