Gemischt-Ganzzahlige Lineare Optimierung

Neue Frage »

25.03.2016, 14:43	Musican	Auf diesen Beitrag antworten »
Gemischt-Ganzzahlige Lineare Optimierung Meine Frage: Hallo ihr Lieben! Ich bin das erste mal hier, so bitte ich bei etwaigen Ungereimtheiten um Hinweise und sollte der Thread falsch eröffnet sein, dann gerne einfach löschen.. Ich habe folgende Aufgabe in meinem Ermessen gelöst und würde mich freuen, wenn jemand, der Ahnung davon hat mir eine Rückmeldung bezüglich der Richtigkeit geben kann. Es geht um folgende Aufgabe : "Ein Energiekonzern betreibt sechs Kraftwerke und muss 10 Städte mit Strom versorgen. Stadt s benötigt insgesamt Bs Einheiten Strom, Kraftwerk k kann insg. maximal Pk Einheiten liefern. Versorgt Kraftwerk k die Stadt s, so müssen mindestens Lk Einheiten abgenommen werden. Pro Stromeinheit entstehen Kosten in Höhe von c_sk. Jede Stadt muss von mindestens 2 versch. Kraftwerken versorgt werden. Wie können ALLE Städte möglichst kostengünstig versorgt werden? Formulieren Sie dieses Problem als gemischt-ganzzahliges lineares Problem." Meine Ideen: So. Nun zu meiner bisherigen Lösung : $\begin{eqnarray} <br /> \text{zuerst habe ich die binäre Variable y eingeführt mit } \\<br /> \end{eqnarray}$ $\begin{eqnarray} <br /> y_{s_k}= \text{1, wenn Stadt s von Kraftwek k versorgt wird. 0 Sonst.}<br /> <br /> <br /> \text{zusätzlich noch die ganzz. Variable, welche die bezogenen Einheiten Strom von Kraftwerk k an Stadt s angibt } \\ = x_{s_k} <br /> <br /> \end{eqnarray}$ $\begin{eqnarray} <br /> \text{Nun mein eigentliches LP : } \\<br /> <br /> MIN \sum \limits_{s=1}^{10} \sum \limits_{k=1}^{6} y_{s_k} (x_{s_k} * c_{s_k})<br /> <br /> s.t \sum \limits_{k=1}^{6} y_{s_k} * x_{s_k} = B_{s} (s \in (1,...,10)<br /> <br /> \sum \limits_{S=1}^{10} y_{s_k} * x_{s_k} \le P_{k} (k \in (1,...,6)<br /> <br /> y_{s_k} * x_{s_k} \ge L_{k} (s \in (1,...,10)(k \in (1,...,6)<br /> <br /> <br /> \sum \limits_{k=1}^{6} y_{s_k} \ge 2 (s \in (1,...,10)<br /> <br /> <br /> <br /> mit y_{s_k} \in (0,1) , x_{s_k} \in \mathbb N <br /> <br /> \end{eqnarray*}$ Ich hoffe die Formatierung ist okay. Besser habe ich es leider nicht hinbekommen. Ich freue mich über jede Antwort. Habe ich die Variablen richtig und vor allem sinnvoll eingeführt? Und wie steht es mit der Richtigkeit der Restriktionen und der Zielfunktion? :-? Vielen Dank schonmal im Voraus! Musican
25.03.2016, 18:06	Elvis	Auf diesen Beitrag antworten »
Die Einzelheiten habe ich noch nicht durchdacht, aber es fällt sofort auf, dass du Variable miteinander multiplizierst. Das geht in einem LP nicht, auch nicht in einem Mixed Integer LP.
25.03.2016, 18:29	Dopap	Auf diesen Beitrag antworten »
@Elvis : ist dir schon aufgefallen, dass wir uns hier nie in die Quere kommen. 'Liegt wohl daran, dass Algebra so gar nicht mein Thema ist Gute Gelegenheit dir und family ein schönes Ostern zu wünschen. Dopap
25.03.2016, 19:14	Musican	Auf diesen Beitrag antworten »
Idee Danke schon einmal für die Antwort Elvis! Ich habe ein wenig nachgedacht, da mir ein Kommilitone das selbe erzählte, mir aber nicht genau erklären konnte, wie es denn anders ginge. Wäre es dann dann legitim, wenn ich z.B statt $\begin{eqnarray} \sum \limits_{k=1}^{6} y_{s_k} x_{s_k} = B_{s} (s \in (1,...,10) \end{eqnarray}$ $\begin{eqnarray} \sum \limits_{k=1}^{6} x_{s_k} = B_{s} * y_{s_k} (s \in (1,...,10) \end{eqnarray*}$ schreibe? Oder was müsste ich verändern um mein Problem zu linearisieren? Lieben Gruß!
25.03.2016, 19:41	Elvis	Auf diesen Beitrag antworten »
@Dopap . Danke sehr. Dir und deiner Familie wünsche ich auch gerne ein frohes Fest und alles Gute. - Der Durchschnitt unseres Wissens ist ohne Zweifel nicht leer, aber die Vereinigung scheint den Durchschnitt beträchtlich zu übertreffen @Musican . Kann es sein, dass dein Problem mit ganzzahligen Variablen schon funktioniert, wenn du die binären Variablen $\begin{eqnarray} y_{sk} \end{eqnarray}$ weglässt ? Mit ganzzahligen nichtnegativen $\begin{eqnarray} x_{sk} \end{eqnarray}$ sieht das doch schon ganz gut aus. Du musst nur noch binäre Variable (oh, das sind die $\begin{eqnarray} y_{sk} \end{eqnarray}$ wieder ) so benutzen dass sie die von x>0 versorgten Städte zählen (das muss gehen, ich weiß nur (noch) nicht (genau) wie). Vorschlag: Denke darüber nach, wenn Du keine Lösung findest aber eine brauchst, sage rechtzeitig bescheid, dann mache ich mir ein paar Gedanken dazu.
25.03.2016, 19:52	Musican	Auf diesen Beitrag antworten »
@Elvis Ein sehr hilfreicher Absatz, danke sehr! Da muss ich aber allerdings erstmal im Bezug auf mein Problem drüber nachdenken. Das geht allerdings besser mit vollem Magen. :-) Ich komme aber gerne auf dein Angebot zurück, falls ich feststecke oder auch wenn ich denke, dass ich eine Lösung gefunden hab, denn mir fehlen leider sämtliche Referenzen und für die Klausur sollte das schon sitzen. Habe einige deiner Beiträge gelesen, du scheinst für diese Art Probleme genau der richtige Ansprechpartner zu sein
Anzeige

25.03.2016, 19:55	Elvis	Auf diesen Beitrag antworten »
Nachtrag: geht vielleicht so: setze penalty-Kosten auf binäre $\begin{eqnarray} y \end{eqnarray}$ und formuliere Nebenbedingung $\begin{eqnarray} y\ge\frac x M \end{eqnarray}$ mit $\begin{eqnarray} M \end{eqnarray}$ groß genug. Nachtrag zum Nachtrag: geht bestimmt auch eleganter
25.03.2016, 20:19	Musican	Auf diesen Beitrag antworten »
fündig geworden? Ich habe gerade einen Absatz in meinem Skript gefunden. Es geht um die letzten Sätze des ersten und den ersten Satz des zweiten Fotos. Also wenn ich das richtig verstehe, wird dort doch gesagt, wenn ich eine binäre Variable y habe, die bestimmt OB etwas produziert wird, x das produzierte Gut und M die obere Schranke ist, dass ich diese Beziehung als $\begin{eqnarray} x \leq M y \end{eqnarray*}$ darstelle kann. M ist doch kostant. Und somit wäre das Problem zwei Variablen zu multiplizieren eliminiert. Siehst du das auch so? http://www.directupload.net/file/d/4304/wgmk8ncf_jpg.htm http://www.directupload.net/file/d/4304/t8gutjkd_jpg.htm
25.03.2016, 21:41	Dopap	Auf diesen Beitrag antworten »
Du solltest die Bilder hier als Dateianhang beifügen. Vorige Umwandlung in .gif oder .png ist angeraten. Externe Links werden nicht akzeptiert.
25.03.2016, 21:56	Musican	Auf diesen Beitrag antworten »
Danke für den Tipp! Ich hoffe man kann es so noch erkennen.
25.03.2016, 22:22	Elvis	Auf diesen Beitrag antworten »
Ich muss deine Bilder nicht ansehen. Unsere Ungleichungen stimmen exakt überein. Die penalty auf y ist notwendig, damit wirklich nur die aktiven x gezählt werden.
25.03.2016, 22:33	Musican	Auf diesen Beitrag antworten »
Du meinst die Ungleichung, in der ich das $\begin{eqnarray} y_{s_k} \end{eqnarray}$ auf die rechte Seite geschoben hab? Und nur so nebenbei : Was meinst du mit penalty? Google spuckt mir in diesem Zusammenhang gar nichts aus Viele Grüße, vielen Dank für die Hilfe und einen schönen Abend noch
25.03.2016, 22:35	Elvis	Auf diesen Beitrag antworten »
Antwort kommt morgen. Bis dann ...
26.03.2016, 11:11	Elvis	Auf diesen Beitrag antworten »
Das Problem ist, binäre Variable y zu definieren, die genau dann in der Lösung die Aktivität 1 haben, wenn die ganzzahlige (geht genau so für kontinuierliche) Variable x positiv ist. Es soll also gelten $\begin{eqnarray} x>0\Rightarrow y=1, x=0\Rightarrow y=0 \end{eqnarray}$ . Wir wählen M groß genug (10 Milliarden oder was auch immer, oder wie du vorschlägst M größer gleich eine obere Schranke für x) und setzen $\begin{eqnarray} y\ge\frac 1 M\cdot x\Leftrightarrow y\ge \frac x M \Leftrightarrow M\cdot y\ge x \end{eqnarray}$ . Das ist eine lineare Ungleichung mit den Variablen x und y und der Konstanten M. Was passiert dann ? $\begin{eqnarray} x>0\Rightarrow y=1 \end{eqnarray}$ , denn für $\begin{eqnarray} y=0 \end{eqnarray}$ ist $\begin{eqnarray} M\cdot y=0<x \end{eqnarray}$ im Widerspruch zur Nebenbedingung. Das Restproblem ist, dass auch für $\begin{eqnarray} x=0 \end{eqnarray}$ die binäre Variable $\begin{eqnarray} y \end{eqnarray}$ straflos den Wert 1 annehmen kann. Der Witz eines LP besteht in der Minimierung der Zielfunktion. Wir bestrafen $\begin{eqnarray} y=1 \end{eqnarray}$ durch (geringe) Kosten, z.B. machen 5$ einem Energieversorger nichts aus, dessen Jahresgewinn in Milliarden $ gerechnet wird. Das LP reagiert darauf, indem es möglichst viele $\begin{eqnarray} y's \end{eqnarray}$ auf 0 setzt, genau das macht es für die $\begin{eqnarray} x'e \end{eqnarray}$ , die gleich 0 sind (für die anderen kann es das ja nicht). Fertig. "Penalty cost" sind "Strafkosten" (vgl. "Penalty"="Strafstoß" im Fußball und Eishockey). In der Literatur spricht man von "big M" und "small m" im Zusammenhang mit mixed integer Problems. Sehr zu empfehlen: "Logic and integer programming" : http://www.springer.com/us/book/9780387922799
26.03.2016, 18:46	Musican	Auf diesen Beitrag antworten »
Danke sehr! Die Herleitung der Restriktion macht natürlich Sinn. Ebenfalls die penalty-cost, wobei wir das nicht in unserem Vorlesungsskript auftaucht, was ich nun durchaus bedenklich finde. Ich habe jetzt nochmal über deine Antworten und Ideen nachgedacht und eine (etwas) veränderte Lösung erstellt. Das müsste nun ja ein zulässiges gemischt-ganzzahliges LP sein. (siehe Foto) Das Einzige, was mir noch etwas unklar ist, ist ob die Variable $\begin{eqnarray} y_{s_k} \end{eqnarray}$ nun auch in der Zielfunktion vorkommen muss. Bzw. ob sie wirklich in allen Restriktionen notwendig ist. Die Restriktionen sorgen doch dafür, dass ich in der Zielfunktion durch meine Software einfach über alle Kraftwerke aller Städte iterieren kann, und schon berücksichtigt wird, dass nur die Kosten der Städte aufsummiert werden, die auch tatsächlich versorgt werden, richtig? (Die penalty-cost hab ich wegen der Irrelevanz für die Klausur erstmal nicht berücksichtigt, ist aber sehr interessant. ) Ich hoffe mein LP ist nun richtig bzgl. meines Anfangsproblems. Danke für die Geduld und die Mühe. Ist schwer zu finden heutzutage. Noch ein ruhiges Restwochenende! Musican
26.03.2016, 19:40	Elvis	Auf diesen Beitrag antworten »
Das sieht noch nicht gut aus. Kann es sein, dass die $\begin{eqnarray} \alpha's \end{eqnarray}$ zu klein sind, um als "big M" zu dienen ? Mindestabnahmen können doch überschritten werden, wir brauchen also mindestens die möglichen Maximalabnahmen (oder nicht ?). Bei den Nebenbedingungen sehe ich noch nicht klar, wie die Indizes laufen müssen. So wie es dasteht, geht es eher nicht, weil auf der rechten Seite $\begin{eqnarray} y_{sk} \end{eqnarray}$ steht, aber einmal k frei ist und einmal s frei ist. Ohne penalties kann ich nicht erkennen, wieso nicht alle y auf 1 gehen sollen. Wenn sie das tun, sind sie nicht mit den x gekoppelt, d.h. sie zählen nicht die aktiven x. Welchen Zweck haben sie dann überhaupt ?
26.03.2016, 20:50	Musican	Auf diesen Beitrag antworten »
Naja, also die möglichen Maximalabnahmen sind uns ja pro Kraftwerk, durch ihre Kapazität gegeben, und andererseits dadurch, dass jede Stadt einen Bedarf hat und die Summe der Stromeinheiten aller Kraftwerke einer Stadt (sofern sie denn von ihm versorgt wird) gleich des Bedarfs sein muss. In meinem Skript steht außerdem so etwas :" Durch die Ungleichung $\begin{eqnarray} x \leq My \end{eqnarray}$ lässt sich erreichen dass $\begin{eqnarray} y = 1 \end{eqnarray}$ wird wenn $\begin{eqnarray} x > 0 \end{eqnarray}$ gilt. Da die Zielfunktion minimiert wird wird auf der anderen Seite für $\begin{eqnarray} x = 0 \end{eqnarray}$ automatisch $\begin{eqnarray} y = 0 \end{eqnarray}$ erzwungen." (Ich tippe mal darauf, dass es um das Optimierungsprogramm "ZIMPL" geht, welches dieses "automatische Erzwingen" vollführt. Ich habe nun mal meinem Tutor diesbezüglich eine Email geschrieben. Mal schauen was er dazu sagt. Hatte mich nur davor gescheut, weil ich nicht wollte, dass er die Aufgaben ändert, wenn er weiß, dass ich die Aufgaben noch habe. Aber Halbwissen ist noch viel gefährlicher ^^ Genau dieses das y an das x koppeln ist mir auch unklar. Mal sehen was er dazu sagt.. vielleicht erledigt ZIMPL ja schon mehr, als ich denke.
26.03.2016, 22:05	Elvis	Auf diesen Beitrag antworten »
Das Problem ist nicht y=1 für x> 0 (falls M gross genug ist), sondern y=0 für x=0 (Stichwort penalty). ZIMPL kenne ich nicht, aber ich kann nicht glauben, dass ein Optimierer etwas macht, was in der mathematischen Modellierung nicht formuliert wird. Tipp: Modelliere immer zuerst ein korrektes LP und erstelle dann die MIP-Strukturen.
29.03.2016, 21:07	Musican	Auf diesen Beitrag antworten »
Soo, also ich habe Antwort von meinem Tutor erhalten. Ich bin jetzt durch ihn und dich viel schlauer. Es muss nämlich tatsächlich ein big "M" her, welches aber nicht näher definiert werden muss. Also ich hab mein Problem aufgrund der Infos nochmal neu aufgestellt, falls es dich interessiert, ist hier meine Lösung : $\begin{eqnarray} MIN \sum\limits_{s=1}^{10} \sum\limits_{k=1}^{6} c_{s_k} x_{s_k} <br /> S.T. 1) x_{s_k} \geq L_{k} * y_{s_k} (s \in (1,..,10), k \in (1,...,6))<br /> <br /> 2) \sum\limits_{k=1}^{6} x_{s_k} = B_{s} (s \in (1,..,10))<br /> <br /> 3) \sum\limits_{s=1}^{10} x_{s_k} \leq P_{k} (k \in (1,...,6))<br /> <br /> 4) \sum\limits_{k=1}^{6} y_{s_k} \geq 2 (s \in (1,..,10))<br /> <br /> 5) x_{s_k} \leq My_{s_k}<br /> <br /> x_{s_k} \in \mathbb N , y_{s_k} \in (0,1)<br /> \end{eqnarray}$ Wenn ichs richtig verstanden hab modelliert meine erste Bedingung nun : aus $\begin{eqnarray} x > 0 \Rightarrow y = 1 \end{eqnarray}$ Bedingung nummer 5) modelliert mit dem big "M" nun : aus $\begin{eqnarray} y=1 \Rightarrow x > 0 \end{eqnarray}$ Eventuelle Penalties brauchen wir nicht berücksichtigen sagte er. Hab ich das mit der 1. und der 5. Bedingung denn wohl endlich richtig verstanden? Musican
29.03.2016, 22:26	Elvis	Auf diesen Beitrag antworten »
Ich glaube, jetzt stimmt das LP x=0, dann y=0 folgt aus 1) x>0, dann y=1 folgt aus 5) Die Interpretation hattest du verwechselt. Also keine penalties mehr nötig. Gut gemacht. "Ich spreche aus: Anerkennung!"

Neue Frage »

Antworten »

Gemischt-Ganzzahlige Lineare Optimierung

Verwandte Themen