Lineares Optimierungsproblem formulieren

Question

Aufgabe:

Gegeben sei eine Stadt mit I Wohngebieten, J Schulen und G Klassenstufen an jeder Schule. Jede Schule j kann c(jg) Schüler der Klassenstufe g aufnehmen. In jedem Wohngebiet i ist die Anzahl der Schüler der Klassenstufe g mit s(ig) gegeben. Die Entfernung von Wohngebiet i zur Schule j beträgt d(ij) Kilometer. Die Summe der Kilometer, die alle Schüler zurücklegen müssen soll minimal werden. Formuliere dieses Problem als lineares Optimierungsproblem.

Problem/Ansatz:

Als Zielfunktion die minimal werden soll habe ich mir überlegt, dass

Die Summe von (s(ig)*d(ij)) minimal werden soll. Bei den Restriktionen komme ich leider überhaupt nicht weiter. Ich denke ich muss noch weitere Variablen einführen.

Wenn ich bspw. (ig) geschrieben habe meine ich damit die Indizes.

Wäre super wenn mir vielleicht jemand hierfür ein paar Tipps geben könnte :)

Answer 1

So einfach geht das net:

Beispielhaft: Annahme an jeder Schule gibt es die gleichen Klassenstufen?

$I \, := \, \left\{ w1, w2, w3, w4 \right\}$

$J \, := \, \left\{ s1, s2, s3 \right\}$

$G \, := \, \left\{ g1, g2, g3, g4, g5 \right\}$

$\small S \, := \, \left(\begin{array}{rrrr}w1 \; g1&w2 \; g1&w3 \; g1&w4 \; g1\\w1 \; g2&w2 \; g2&w3 \; g2&w4 \; g2\\w1 \; g3&w2 \; g3&w3 \; g3&w4 \; g3\\w1 \; g4&w2 \; g4&w3 \; g4&w4 \; g4\\w1 \; g5&w2 \; g5&w3 \; g5&w4 \; g5\\\end{array}\right)$

$\small C \, := \, \left(\begin{array}{rrr}s1 \; g1&s2 \; g1&s3 \; g1\\s1 \; g2&s2 \; g2&s3 \; g2\\s1 \; g3&s2 \; g3&s3 \; g3\\s1 \; g4&s2 \; g4&s3 \; g4\\s1 \; g5&s2 \; g5&s3 \; g5\\\end{array}\right)$

$\small D \, := \, \left(\begin{array}{rrrr}w1 \; s1&w2 \; s1&w3 \; s1&w4 \; s1\\w1 \; s2&w2 \; s2&w3 \; s2&w4 \; s2\\w1 \; s3&w2 \; s3&w3 \; s3&w4 \; s3\\\end{array}\right)$

Zusammenklöppeln darfst Du das jetzt:

Comments

Ah okay vielen Dank, dann hab ich mir das wohl ganz falsch gedacht

---

Das wird ein ziemliches Gemetzel, Du hättest ja Variablen wie

w_ig_ks_j

von Wohnort w_i in Klassenstufe g_k geht zum Schulort s_j

im gezeigten Fall also 3*4*5 = 60 Variablen

Das Modell sieht auch unvollständig aus?

---

Mh so war zumindest die Aufgabe gestellt.

Es steht ja da, dass ich nur das Problem formulieren soll. Da reicht es denke ich, wenn ich zeige wie es circa geht.

---

Wäre es dann nicht aber sinnvoller sich einfach ein Beispiel mit jeweils 2 Elementen zu nehmen sodass es dann 8 Variablen werden?

---

Klar, kann man das Beispiel kleiner machen - es diente ja nur mal zur Orientierung.

Ich hab unterschiedliche Indexgrenzen gewählt um leichter unterscheiden zu können.

Ich würde ein konkretes Beispiel basteln und dann überprüfen ob der Ansatz taugt, etwa

$\Sigma \left(w_ig_ks_j \right) \; d\left(w_is_j \right) \to min$

$\sum\limits_i \left(w_ig_ks_j \right) \leq c\left(s_jg_k \right)$

$\sum\limits_k \left(w_ig_ks_j \right) \geq s\left(w_jg_k \right)$

Hab allerdings nicht den Eindruck, das es was zu optimieren gibt?

---

Konkretisierung mit:

I:{w1,w2}, J:{s1,s2,s3], K:{g1,g2}

$D \, := \, \left(\begin{array}{rr}6.1&7.1\\5.6&5.4\\5.1&3.6\\\end{array}\right), C \, := \, \left(\begin{array}{rrr}7&11&8\\9&6&10\\\end{array}\right), S \, := \, \left(\begin{array}{rrr}20\\21\\\end{array}\right)$

minimize_lp(
(6.1*w1g1s1)+(5.6*w1g1s2)+(5.1*w1g1s3)+(6.1*w1g2s1)+(5.6*w1g2s2)+(5.1*w1g2s3)+
(7.1*w2g1s1)+(5.4*w2g1s2)+(3.6*w2g1s3)+(7.1*w2g2s1)+(5.4*w2g2s2)+(3.6*w2g2s3), [
w1g1s1+w2g1s1<=7,
w1g2s1+w2g2s1<=9,
w1g1s2+w2g1s2<=11,
w1g2s2+w2g2s2<=6,
w1g1s3+w2g1s3<=8,
w1g2s3+w2g2s3<=10,
w1g1s1+w2g1s1+w1g1s2+w2g1s2+w1g1s3+w2g1s3=20,
w1g2s1+w2g2s1+w1g2s2+w2g2s2+w1g2s3+w2g2s3=21
]), nonegative_lp=true;

[193.2,[
w2g2s3=10,w1g2s3=0,w2g1s3=8,w1g1s3=0,
w2g2s2=6,w1g2s2=0,w2g1s2=11,w1g1s2=0,
w2g2s1=0,w1g2s1=5,w2g1s1=0,w1g1s1=1]]

Scheint zu funktionieren....