Textaufgabe über Müllcontainer

20.02.2010, 07:37

Hilfebeduerftiger

Wurde von diesem Thread abgetrennt.

Hallo an alle, die hier echt guten Support geben. Ich hab schon so einiges lesen koennen und fuer mich gewinnen koennen.

Allerdings habe ich ein Problem bei dem ich unbedingt nochmal hilfe benoetigen koennte.

Ich waere allen sehr dankbar.
Um ehrlich zu sein bin ich nicht so der OR-crack aber interessant ist es schon.
Also hier mal eine kleine Aufgabe.

Ein Entsorgungsunternehmen stellt an mehreren Standorten Muellcontainer auf.
Die Container muessen regelmaessig zu einer der umliegenden Deponien gebracht
und entleert werden. Dabei kann jede Deponie aus Kapazitaetsgruenden nur je
einen Container aufnehmen.
Gegeben sind die Kosten (Transport und Deponiegebuehren), die die Entleerung
eines Containers von einem bestimmten Standort an einer bestimmten Deponie
verursacht. Gesucht ist diejenige Zuordnung von Containerstandort zu Deponie,
die minimale Gesamtkosten hat.

Mit den gegebenen Kosten ist gemeint, dass bei der Aufgabe angenommen werden soll, dass Kosten existieren aber hier auch verallgemeinert angenommen werden sollen.

Fuer diese Art der Aufgabe ist die Zielfunktion und die Nebenbedingungen zu erstellen.

Kann mir jemand helfen? Bitte bitte.
Welche Variablen muss ich beruecksichtigen?
Dadurch das nur je ein Container abgeholt werden kann, kann man Container und Standort gleichsetzen. <<richtig?

20.02.2010, 15:00

Elvis

Auf diesen Beitrag antworten »

Binäre Variable X_ij := Container_i (i=1,...,n) wird zur Deponie_j (j=1,...,n) transportiert.
Dann darfst du dir überlegen, wie die Nebenbedingungen lauten, die dafür sorgen, dass jeder Container zu genau einer Deponie transportiert wird.
(Alternativ kannst du die Nebenbedingungen formulieren, so dass jede Deponie genau einen Container abbekommt.)
Die Zielfunktion in den X_ij dürfte dir nach kurzem Nachdenken klar sein. Setze t_ij=Transportkosten Container_i zur Deponie_j, d_j=Deponiekosten für Deponie_j.

21.02.2010, 05:01

Hilfebeduerftiger1

Auf diesen Beitrag antworten »

Hallo Elvis. Danke schon mal fuer die Antwort.

Aus irgenteinem Grund kann ich dir nicht antworten, wenn ich angemeldet bin...frag mich nicht warum. K.a. also antworte ich dir wieder als nich angemeldeter.

Also wenn ich ich richtig sehe
sind die Var. so zusammengesetzt das folgende Matrix entsteht.

x_i1 x_i2 x_i3 x_in b

d_1j tij tij tij tij Summe t_1j (j=1...n)(sind dann ja Kosten/Deponie)d_2j tij ... ... ... Summe t_1j (j=1...n)
d_3j usw.
d_nj

Z Summe t_i1 (i=1..n) usw. --> MIN!!

Ist dann die Zielfunktion= ?? gruebel verwirrt

Summe ( tij * xi(oder j??)* dj) (i=1...n)(j=1...n) =MIN
( wobei xij ja eigentlich =1 sein soll)
das irritiert mich etwas!

Mit xij = Container
dij = Deponien
tij = Transportkosten
xij ; dij ; tij >0

Ich hab das Gefuehl ich bin da voellig auf dem Holzweg und steh auch etwas auf dem Schlauch

21.02.2010, 08:02

Hilfebeduerftiger2

Auf diesen Beitrag antworten »

------x_i1--x_i2--x_i3--x_in---| b
d_1j --tij-- tij-----tij-----tij-----| Summe t_1j (j=1...n)(sind dann ja Kosten/Deponie)
d_2j --tij-- ...---...---... -------|Summe t_1j (j=1...n)
d_3j --usw.--
d_nj
-------------------------------------
Z -----Summe t_i1 (i=1..n) usw.| --> MIN!

Hier nochmal die Matrix, ich hoffe man kann es so besser erkennen.

Die NB sollte dann doch eigentlich sein:

Anzahl der Container / Anzahl Deponien =1

xij / dij =1 (wenn das jetzt aber schon eine Gleichung ist, ist es dann noch notwendig mit Schlupfvar. zu arbeiten? Es gibt doch hier kein nichtausgeschoepftes Potential)

21.02.2010, 08:51

Gualtiero

Auf diesen Beitrag antworten »

OFF TOPIC

Zitat:

Original von Hilfebeduerftiger1
Aus irgenteinem Grund kann ich dir nicht antworten, wenn ich angemeldet bin...frag mich nicht warum. K.a. also antworte ich dir wieder als nich angemeldeter.

Tipp: Was solche Probleme angeht, kannst Du hier Fragen dazu stellen. In diesem Thread achtet kaum jemand darauf.

Und so kann man schön eine Matrix darstellen:

$\begin{eqnarray*} \begin{vmatrix} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \end{vmatrix} \end{eqnarray*}$

END OT

21.02.2010, 11:41

Elvis

Auf diesen Beitrag antworten »

@Hilfsbeduerftiger
du hast meinen Vorschlag noch nicht ganz "verdaut". In einer LP-Matrix kann kein i und kein j vorkommen.
Versuche erst einmal mit 3 Containern und 3 Deponien das Beispiel korrekt aufzuschreiben, dann ist die Verallgemeinerung ganz leicht (du brauchst dann nur noch 3 durch n zu ersetzen).
Noch ein Tipp: Für n=3 bekommst du 9 binäre Variable X_11,...,X_33
X_ij=0 heißt: Container_i wird nicht zur Deponie_j transportiert.
X_ij=1 heißt: Container_i wird zur Deponie_j transportiert.

21.02.2010, 12:55

chris0815

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \begin{vmatrix} c_1 & c_2 & c_3 \\ 1 & 0 & 1 & d_1 \\ 0 & 0 & 1 & d_2 \\ 1 & 1 & 0 & d_3\end{vmatrix} \end{eqnarray*}$

Habs nochmal versucht mit der Anmeldung! Hat geklappt, also jetzt statt Hilfebedürftiger>> chris0815
Meinst du die Matrix so aufgebaut?
Gut, dann weiß ich wann ein Container zu welcher Deponie kommt.
Aber ich weiß doch so gar nicht wie ich hier die Kosten dafür minimieren soll!!

Ich steh auf`m Schlauch oder??......Kann ma jemand den Elefanten vom Schlauch verjagen!! Augenzwinkern

21.02.2010, 13:50

Elvis

Auf diesen Beitrag antworten »

Nein, so habe ich das nicht gemeint und nicht gesagt. Wenn du dir helfen lassen möchtest, lies was ich gesagt habe, dann wird alles ganz einfach. Was du da machst, hilft leider gar nichts.

21.02.2010, 16:44

chris0815

Auf diesen Beitrag antworten »

Ok, also doch falsch....ich bin mir sicher, dass es nicht so schwer ist wie es mir gerade scheint aber ich muss zugeben, dass ich nicht so recht weiß wie ich weiter machen soll.

Mitlerweile bin ich auch etwas verwirrt.

X_ij stehen als binäre Var. in der Mitte der Matrix. (binär=1 oder 0)
wobei 0=Container wird nicht geliefert oder auch Strom fließt nicht
und 1=Container wird geliefert heißt respektive Strom fließt
eine N x N Marix mit N=3 ergibt 9 binäre Var. Das ist auch klar.

Kann es sein, dass ich Zeilen mit Spalten vertauscht habe?
Und ich hab zu viele 1en drin.
Jede Deponie kann immer nur einen einzigen Container aufnehmen!

Komm ich so schon etwas näher?

21.02.2010, 20:58

Elvis

Auf diesen Beitrag antworten »

Nein, es ist keine 3x3-Matrix, sondern eine Matrix mit 9 Variablen X_11,...,X_33 = 9 Spalten. (Das habe ich übrigens schon einmal gesagt. Augenzwinkern

)
Die Idee, dass nicht so viele Einsen in der Lösung sein dürfen sind genau die Nebenbedingungen. Davon braucht man 2*n^2=2*9=18.

22.02.2010, 11:15

chris0815

Auf diesen Beitrag antworten »

Hehe, ja du sagtest etwas in dieser Richtung allerdings konnte ich damit nicht sooo viel anfangen.

Aber ich hab ja gewarnt, ich bin da noch nicht so richtig auf der Höhe. Aber ich bemühe mich.

Ok bevor ich hier noch mehr schrott poste. Wie verteile ich denn dann die Einsen?

Tut mir echt leid, dass ich bei diesen Dingen nicht so richtig vorankomme.

Ich wäre dir echt dankbar, wenn du mir da nochmal ein wenig unter die Arme greifen könnest.

Vielen Dank!!

23.02.2010, 18:43

Elvis

Auf diesen Beitrag antworten »

Nicht du verteilst die Einsen, sondern ein Programm zur Lösung von Optimierproblemen. Du stellst das Problem auf, der Computer berechnet eine Lösung für das Problem so dass die Zielfunktion (=Kosten) minimal ist.
Das Problem wird beschrieben durch Variable und ihren Typ (das habe ich für dich gemacht: binäre Variable X_ij). In der Lösung kann jede binäre Variable nur die Werte 0 oder 1 annehmen.
In der Lösung muss jeder Container zu genau einer Deponie - was heißt das für die Summen $\begin{eqnarray*} \sum_{j=1}^n X_{ij} , i=1,...,n \end{eqnarray*}$ ?
In der Lösung bekommt jede Deponie genau einen Container - was heißt das für die Summen $\begin{eqnarray*} \sum_{i=1}^n X_{ij},j=1,...,n \end{eqnarray*}$ ?
Das sind die Nebenbedingungen. Wäre nett, wenn du auch mal ein bißchen mitdenkst. Schreib bitte die Nebenbedingungen auf, denke über die Zielfunktion nach. Wenn du immer noch nicht klarkommst, darst du nochmal (und nochmal, ...) nachfragen.

Sorry, ich sehe gerade, man braucht nur 2*n=2*3=6 Nebenbedingungen (nicht 18, wie ich früher mal gepostet habe).

24.02.2010, 18:57

Elvis

Auf diesen Beitrag antworten »

Habe ich dich verschreckt ? Das täte mir leid, ich wollte nur helfen. Also helfe ich noch ein bißchen...

Wenn wir eine Deponie j festhalten und i=1,...,n läuft, dann betrachten wir nacheinander alle Container. Diese können zur Deponie j transportiert werden (X_ij=1) oder nicht (X_ij=0). Genau einer wird zur Deponie j transportiert, also heißt die Nebenbedingung $\begin{eqnarray*} \sum_{i=1}^n X_{ij}=1 \end{eqnarray*}$ , und das gilt für alle $\begin{eqnarray*} j=1,...,n \end{eqnarray*}$ .
Wenn wir einen Container i festhalten und j=1,...,n läuft, dann betrachten wir nacheinander alle Deponien. Der Container i kann zur Deponie j transportiert werden (X_ij=1) oder nicht (X_ij=0). Genau zu einer Deponie wird der Container i transportiert, also heißt die Nebenbedingung $\begin{eqnarray*} \sum_{j=1}^n X_{ij}=1 \end{eqnarray*}$ , und das gilt für alle $\begin{eqnarray*} i=1,...,n \end{eqnarray*}$ .

Damit ist das Transportproblem vollständig beschrieben. Es fehlt nur noch die Zielfunktion.

24.02.2010, 19:27

Elvis

Auf diesen Beitrag antworten »

In Matrixform sieht das Transportproblem für n=3 bisher so aus (es fehlt nur noch die Zielfunktion)

$\begin{eqnarray*} \begin{pmatrix} X_{11} & X_{12} & X_{13} & ... & X_{31} & X_{32} & X_{33} & Bin & Var \\ \\ 1 & 0 & 0 & ... & 1 & 0 & 0 & = & 1 \\ 0 & 1 & 0 & ... & 0 & 1 & 0 & = & 1 \\ 0 & 0 & 1 & ... & 0 & 0 & 1 & = & 1 \\ \\ 1 & 1 & 1 & ... & 0 & 0 & 0 & = & 1 \\ 0 & 0 & 0 & ... & 0 & 0 & 0 & = & 1 \\ 0 & 0 & 0 & ... & 1 & 1 & 1 & = & 1 \end{pmatrix} \end{eqnarray*}$

(Ich kann leider keine Matrix mit 11 Spalten schreiben, das lässt dieser Editor nicht zu, deshalb habe ich den zweiten Container weggelassen).

31.03.2010, 09:13

chris0815

Auf diesen Beitrag antworten »

Sorry, dass ich mich wirklich sehr lange nicht mehr gemeldet habe. Aber ich habe im Rahmen meines derzeitigen Praktikums das Angebot bekommen fuer einige Zeit nach China zu gehen und ich konnte das nicht ablehnen smile

Also deine Unterstuetzung hat mir ehr weiter geholfen und ich werde mich jetzt auch wieder dieser Thematik wittmen. Auch wenn ich etwas weniger Zeit als vorher dafuer habe wear ich dir sehr verbunden, wenn ich dich nicht zu sehr veraergert habe und du mir weiterhin ein paar Tipps geben kannst.

Also zum Problem:

Die Zielfunktion sollte fuer dieses Problem etwa so aussehen

$\begin{eqnarray*} \sum\limits_{i=1;j=1}^n k_{ij}*x_{ij}=min! \end{eqnarray*}$

mit $\begin{eqnarray*} k\neq 0 \end{eqnarray*}$

Damit sollte das Problem theoretisch geloesst sein.

Wenn ich jetzt zu der Theorie in die Praxis gehe und fuer Entfernung folgendes annehmen:

$\begin{eqnarray*} \begin{vmatrix}Container & A & B & C& D & E \\Deponie 1 & 89 & 68 & 59 & 74 & 69\\ Deponie 2 & 69 & 72 & 78 & 62 & 73 \\ Deponie 3 & 65 & 76 & 82 & 79 & 75\\ Deponie 4 & 75 & 83 & 81 & 72& 76\\ Deponie 5 & 70 & 74 & 68 & 69 & 70 \end{vmatrix} \end{eqnarray*}$

Wie bau ich denn jetzt das Simplextableau auf ?

Neue Frage »

Antworten »

Textaufgabe über Müllcontainer

Verwandte Themen