Ganzzahliges lineares Optimierungsproblem

Neue Frage »

18.01.2017, 11:14	Oggel	Auf diesen Beitrag antworten »
Ganzzahliges lineares Optimierungsproblem Hallo Leute, ich brauche dringend Hilfe bei dieser Aufgabe. Ich denke schon ganze Zeit darüber nach aber komme zu keiner Lösung. Mein Ansatz: Ich habe versucht eine Variable einzuführen: $\begin{eqnarray} x_\text{s} \end{eqnarray}$ welche die Anzahl der Klassen pro Schule angibt. Dann hätte ich die Zielfunktion: $\begin{eqnarray} min \sum_{s=1}^n x_\text{s} \end{eqnarray}$ Aber das funktioniert leider auch nicht so richtig, ich weiß nicht wie ich die Schüler da noch mit einbringen soll. Könnt ihr mir irgendein Tipp geben? Komme echt nicht weiter. Danke schonmal
18.01.2017, 13:30	Elvis	Auf diesen Beitrag antworten »
Ich würde mit $\begin{eqnarray} \sum K_j \end{eqnarray}$ binären Variablen beginnen, die entscheiden, ob oder ob nicht eine Klasse eingerichtet wird, und dann versuchen, die Nebenbedingungen darauf aufzubauen. Das ist eine hübsche und praxisbezogene Aufgabe, halte mich bitte über deine Fortschritte auf dem laufenden. Vielleicht ist es aus Bezeichnungsgründen einfacher, mit $\begin{eqnarray} \sum max(K_j) \end{eqnarray}$ binären Variablen zu starten, die kann man doppelt indizieren und hat so eine natürliche Zuordnung zu den Schulen.
18.01.2017, 14:57	Oggel	Auf diesen Beitrag antworten »
danke schonmal für einen Anfang habe damit echt Probleme einen Anfang zu finden. Also ich nenne die Variable mal $\begin{eqnarray} x \end{eqnarray}$ , da es sonst evtl. zu Verwechslungen kommen könnte mit dem $\begin{eqnarray} K_\text{j} \end{eqnarray}$ aus der Aufgabe. Also führe ich die binäre Variable $\begin{eqnarray} x_\text{jk} \end{eqnarray}$ ein die besagt: 0 = Klasse k nicht eingerichtet an Schule j 1 = Klasse k ist eingerichtet an Schule j du hattest von $\begin{eqnarray} max(K_\text{j}) \end{eqnarray}$ gesprochen? Müsste das nicht eigentlich minimiert werden, da die Anzahl der Klassen möglichst klein sein soll? Meine Idee für eine Zielfunktion wäre: $\begin{eqnarray} min \sum_{j=1}^n \sum_{k=1}^{K_\text{j}} x_{jk} \end{eqnarray}$ Kann man das überhaupt so machen?
18.01.2017, 15:22	Elvis	Auf diesen Beitrag antworten »
Machen kann man alles, was man machen kann. Das Problem liegt darin, die Variablen so geschickt zu wählen, dass man damit alle Nebenbedingungen leicht formulieren kann. Ich finde meinen Ansatz immer noch gut, denke darüber nach, wenn ich heute Abend Zeit habe, kann ich ihn erläutern.
18.01.2017, 16:11	Oggel	Auf diesen Beitrag antworten »
Ja das wäre gut. So ganz versteh ich den Ansatz nämlich noch nicht. Ist mit deinem $\begin{eqnarray} K_{j} \end{eqnarray}$ das gleiche gemeint wie in der Aufgabe? Also die maximale Anzahl an Klassen? Und wieso maximierst du?
18.01.2017, 18:24	Elvis	Auf diesen Beitrag antworten »
"Super-Elvis kommt angefliegt" (siehe Sesamstraße (oder Hallo Spencer ???)) und hat ein fertiges binäres Modell im Gepäck ... und jetzt wieder ganz im Ernst : das Modellchen zu bauen hat Spaß gemacht. Selbstverständlich halte ich mich an die Bezeichnungen deiner Aufgabe, sonst könnten wir uns ja nicht verständigen. Ich maximiere nicht, ich rede zunächst nicht über die Zielfunktion, die kommt ganz zum Schluß und wird wie gewünscht minimiert. Meine übliche Vorgehensweise ist, zuerst Variablen festzulegen, damit Nebenbedingungen zu formulieren und dann auch die Zielfunktion als eine Nebenbedingung zu optimieren. Ich schlage vor, genügend binäre Variable Kkj zu definieren, k=1,...,MAX=max{Kj}, j=1,...,n mit der Bedeutung Kkj=0: keine Klasse k in Schule j, Kkj=1: Klasse k in Schule j Man käme auch mit ein paar weniger Variablen aus, wenn man das k jeweils nur bis zu Kj laufen liesse, aber das wäre irgendwie spießig und langweilig und wir müssten später immer auf die lästigen Indices achten. Du darfst jetzt die Nebenbedingungen formulieren, die gebraucht werden, damit in jeder Schule j maximal Kj Klassen eingerichtet werden. Wenn es dir hilft, darfst Du auch schon die Zielfunktion aufschreiben. Anschließend denkst Du nach, welche weiteren Variablen gebraucht werden, und dann sehen wir weiter ...
Anzeige

18.01.2017, 19:12	Oggel	Auf diesen Beitrag antworten »
Also war meine Variable $\begin{eqnarray} x_{jk} \end{eqnarray}$ schon richtig oder? Bloß dass $\begin{eqnarray} k \in {1,...K_{j}} \end{eqnarray}$ ? Das ist ein bisschen verwirrend, weil in der Aufgabe auch schon $\begin{eqnarray} K_j \end{eqnarray}$ angegeben ist und die die binäre Variable auch $\begin{eqnarray} K_j \end{eqnarray}$ nennst.
18.01.2017, 19:25	Elvis	Auf diesen Beitrag antworten »
Kkj ist eine von mir erfundene binäre Variable, $\begin{eqnarray} K_j \end{eqnarray}$ ist eine in der Aufgabe vorgegebene Konstante. Ja, Du darfst Kkj auch xjk nennen. Vorsicht bei vielen Klassen und schulen, da müssen die Variablen dann vielleicht besser x_j_k heißen, sonst gibt es eine Verwechslung zwischen x_1_11 und x_11_1
18.01.2017, 20:00	Oggel	Auf diesen Beitrag antworten »
Alles klar. Danke schonmal, dass du mir so hilfst Also dann brauchen wir die Variable $\begin{eqnarray} x_{jk} \end{eqnarray}$ und evtl. die Konstante $\begin{eqnarray} MAX = max(K_j) \end{eqnarray}$ . Dann wäre meine Idee für die Bedingung, dass für jede Schule $\begin{eqnarray} j \end{eqnarray}$ maximal $\begin{eqnarray} K_j \end{eqnarray}$ Klassen eingerichtet werden können: $\begin{eqnarray} \sum_{k=1}^{MAX} x_{jk} \le K_j, \forall j \in 1...n \end{eqnarray}$ . Kommt das so hin? Dann müsste man noch eine Variable für die Schüler einführen, damit tue ich mich auch schwer. Könnte man hier auch eine binäre Variable nehmen, die angibt, ob Schüler i in Schule j und Klasse k? Sowas wie $\begin{eqnarray} s_{ijk} \end{eqnarray}$ ?
18.01.2017, 21:48	Elvis	Auf diesen Beitrag antworten »
Die Nebenbedingung ist okay. Die Idee mit den mnMAX binären Variablen S_i_j_k hatte ich genau so, auch ihre Bedeutung stimmt. Damit lassen sich alle im Aufgabentext enthaltenen Nebenbedingungen formulieren. Hau rein! Es fehlen dann noch zwei N.B., die mir der gesunde Menschenverstand gesagt hat.
19.01.2017, 16:51	Oggel	Auf diesen Beitrag antworten »
Alles klar Also für die Bedingung, dass, falls eine Klasse eingerichtet wird minimal l und maximal u Schüler in der Klasse sein müssen, habe ich folgendes überlegt: $\begin{eqnarray} \sum_{i=1}^n s_{ijk} \le u x_{jk} \forall j,k \end{eqnarray}$ und $\begin{eqnarray} \sum_{i=1}^n s_{ijk} \ge l * x_{jk} \forall j,k \end{eqnarray*}$ Kommt das so hin? Dann fehlt nur noch eine Bedingung oder?
19.01.2017, 18:28	Elvis	Auf diesen Beitrag antworten »
Das ist ein löblicher Versuch, denn er sieht so aus, als ob Du weißt, was du willst, aber er enthält Fehler. Die Kleinigkeit, dass hier jeweils über die m Schüler summiert wird, ist leicht zu korrigieren, da muss man nur die Summation bis m und nicht bis n laufen lassen. Kannst Du erklären, warum Du auf der rechten Seite die schönen Konstanten $\begin{eqnarray} u \end{eqnarray}$ und $\begin{eqnarray} l \end{eqnarray}$ mit den hier unnötigen Variablen x_j_k multiplizierst ? Ist das ein Versehen, oder hast Du dir etwas dabei gedacht ? Aus der Aufgabenstellung fehlen nur noch die Abstandsbedingungen, weil man keinem Schüler einen langen Schulweg zumuten kann. Und dann musst du nachdenken, ob das alles funktioniert. (Einer meiner LP-Lehrer hat immer gesagt "you must think like an LP".)
19.01.2017, 19:22	Oggel	Auf diesen Beitrag antworten »
Ups natürlich das muss bis m laufen. Ja ich habe versucht irgendwie einzubauen, dass ja nicht in jedem Fall eine Klasse eingerichtet wird. Also Falls $\begin{eqnarray} x_{jk} = 1 \end{eqnarray}$ , dann darf die Klasse mindenstens l und maximal u Schüler haben. Mhh weiß aber nicht wie es sonst gehen würde
19.01.2017, 20:04	Elvis	Auf diesen Beitrag antworten »
Ich hatte nur die Konstanten als rechte Seiten der Nebenbedingung, und in weiteren Nebenbedingungen habe ich dafür gesorgt, dass Schüler nur in Klassen gehen, die aktiv sind. Deine Idee ist gut und richtig, sie setzt nicht nur die Grenzen sondern erledigt das nebenbei gleich mit. Eine wichtige Sache fehlt noch ...
19.01.2017, 21:50	Oggel	Auf diesen Beitrag antworten »
Nur zum Verständnis: Also sind die Nebenbedingungen richtig? Die Idee für Die Distanz: $\begin{eqnarray} d_{ij} \le d s_{ijk} \forall i,k \end{eqnarray*}$ ? Geht das?
19.01.2017, 21:52	Elvis	Auf diesen Beitrag antworten »
Alles richtig, Abstände sind falsch. Ich habe $\begin{eqnarray} d_{ij}Sikj<=d \end{eqnarray}$ für alle i,k,j Tipp des Tages: Führe die allgemeine Schulpflicht ein, sonst bleiben alle Klassen leer. Grund: alle Variablen=0 ist optimal. "You must think like an LP."
19.01.2017, 22:17	Oggel	Auf diesen Beitrag antworten »
Ahh okay alles klar und : $\begin{eqnarray} \sum_{i=1}^n \sum_{j=1}^m \sum_{i=1}^{MAX} s_{ijk} = n \end{eqnarray}$ Es müssen ja alle Schüler in irgendeine Klasse einer Schule oder?
20.01.2017, 08:05	Elvis	Auf diesen Beitrag antworten »
Wieder von der Idee her gut, aber wieder mangelhaft ausgeführt. 1. Indexfehler 2. Der Schüler Paul, der in der Nähe von 3 Schulen wohnt, wird sich beschweren, dass er dort 2,4 und 7 Klassen besuchen muss. Ob 12 andere Schüler, die deswegen nicht zur Schule müssen, damit zufrieden sind, hängt von ihrer Lebensplanung ab. Anmerkung: In meinem 1. Entwurf des Modells habe ich genau denselben Fehler bei der Nebenbedingung "SCHULPFLICHT" gemacht wie Du. Dann war Peter zufrieden, weil er nicht mehr zur Schule musste, Paul hat sich beschwert, weil er 13 Klassen gleichzeitig besuchen sollte, und Mary hat sich beschwert, weil sie unbedingt zur Schule wollte, um Abitur zu machen und später Gesang zu studieren. Mit anderen Worten "You must think like an LP"
20.01.2017, 10:02	Oggel	Auf diesen Beitrag antworten »
Stimmt hast natürlich Recht so wie ich es gemacht habe, ist es möglich, dass ein Schüler in verschiedene Klassen geht. Achja Indexfehler natürlich auch m Schüler und n Schulen. Aber wenn man die Bedingung so stehen lässt und noch folgende hinzufügt: $\begin{eqnarray} \sum_{j=1}^n \sum_{k=1}^{MAX} s_{ijk} = 1 \forall i \end{eqnarray}$ würde das so funktionieren? Mit dieser Bedingung stellt man sicher, dass jeder Schüler nur in eine Schule und eine Klasse geht. Und mit der oben genannten Bedingung, dass alle Schüler in irgendeine Schule und Klasse gehen müssen.
20.01.2017, 10:29	Elvis	Auf diesen Beitrag antworten »
So ist es korrekt, und die andere Bedingung kann wegfallen. Diese neue Bedingung sagt, dass jeder Schüler in genau eine Klasse genau einer Schule geht. Wenn du jetzt noch alles schön aufschreibst, bist Du fertig. Nachdem das Modell nun fertig ist, sieht man auch, dass deine Zielfunktion gut formuliert war. Dieses LP hat gute Chancen, entsprechend der Aufgabenstellung zu funktionieren (ohne Gewähr). Kritik an der Aufgabenstellung: Dieses bürokratische Monster-LP benötigt eine Schüler-Klassen-Schulen-Verwaltung mit Geschäftsleitung, Public-Relations-Managern und viele technische Mitarbeiter aus Informatikern, Datenverarbeitern, LP-Modellierern und LP-Anwendern. Lehrer werden arbeitslos gemacht, Schulen werden abgerissen, Schüler werden zwangsweise in Schulklassen gepresst, in die sie nicht gehen wollen. Jedesmal wenn sich etwas ändert (Schüler, Lehrer, Wohnorte, Schulen, Klassengröße, ...) muss dieses stalinistische LP um ein Orakel angebetet werden, und garantiert kommt als Lösung etwas heraus, was nahezu alle Schüler in eine neue Schulklasse versetzt. Ich plädiere dafür, diesen Unsinn sofort in die Abfalltonne zu werfen und stattdessen der demokratischen Entscheidungsfreiheit der Schüler eine Chance zu geben.
20.01.2017, 11:16	Oggel	Auf diesen Beitrag antworten »
Also nochmal zum Überprüfen: Konstante $\begin{eqnarray} MAX = max(K_j) \end{eqnarray}$ binäre Variable $\begin{eqnarray} x_{jk} \end{eqnarray}$ die angibt ob Klasse k in Schule j eingerichtet ist binäre Variable $\begin{eqnarray} s_{ijk} \end{eqnarray}$ die angibt ob Schüler i in Schule j und Klasse k geht $\begin{eqnarray} min \sum_{j=1}^n \sum_{k=1}^{MAX} x_{jk} \end{eqnarray}$ und die Nebenbedingungen: $\begin{eqnarray} \sum_{i=1}^m s_{ijk} \le u x_{jk} \forall j,k \end{eqnarray}$ gibt an, dass höchstes u Schüler in eine Klasse $\begin{eqnarray} \sum_{i=1}^m s_{ijk} \ge l * x_{jk} \forall j,k \end{eqnarray}$ gibt an, dass mindestens l Schüler in eine Klasse $\begin{eqnarray} d_{ij} * s_{ikj} \le d \forall i,k,j \end{eqnarray}$ die berücksichtigt, dass Schüler nur in Schulen gehen, die nicht zu weit entfernt sind $\begin{eqnarray} \sum_{j=1}^n \sum_{k=1}^{MAX} s_{ijk} = 1 \forall i \end{eqnarray*}$ damit jeder Schüler in genau eine Schule und eine Klasse geht So richtig? Deine Kritik ist gut
20.01.2017, 11:37	Elvis	Auf diesen Beitrag antworten »
Theoretisch ist das aus meiner Sicht in Ordnung, aber Du hast etwas vergessen, nämlich $\begin{eqnarray} \sum_{k=1}^{MAX} x_{jk} \le K_j, \forall j \in 1...n \end{eqnarray}$ . Dass man in der Modellpraxis die Variablen und Nebenbedingungen geeignet bezeichnen muss, also z.B. x_j_k statt $\begin{eqnarray} x_{jk} \end{eqnarray}$ , habe ich schon gesagt. Mit welcher Modellsprache Du arbeitest weiß ich nicht, da können natürlich weitere technische Probleme auftreten. Dieses Modell hat nun den Vorteil, dass man die Konstanten $\begin{eqnarray} K_j \end{eqnarray}$ nicht weiter berücksichtigen muss, dieser Vorteil hat den Nachteil zur Folge, dass in Schule 5 die Klassen 3,7,15 eingerichtet werden können. Im LP-Report kann man sie oBdA in die Klassen 1,2,3 umbenennen. Zur Kritik: ich habe in jedem LP-Unterricht auf die Verantwortung jedes Menschen für sein Tun hingewiesen, insbesondere auf die Verantwortung von Technikern, Ingenieuren, Wissenschaftlern, Informatikern und Mathematikern. Gerade am 75. Jahrestag der Wannsee-Konferenz will ich, dass man bei jeder Aufgabe und Lösung nicht nur über die Technik nachdenkt, sondern auch darüber nachdenkt, welche Auswirkungen das eigene Handeln hat.
20.01.2017, 11:41	Oggel	Auf diesen Beitrag antworten »
Alles klar. Ja ich habe die Variablenbennenung so gelassen, da ich es nicht lösen muss. Muss nur das Modell aufstellen. Hast mir sehr geholfen danke Hast du eine Idee wo man eventuell ähnliche Probleme mit ähnlichem Schwierigkeitsgrad her bekommt um ein bisschen für die Klausuren zu üben?
20.01.2017, 11:53	Elvis	Auf diesen Beitrag antworten »
Das Buch "Logic and Integer Programming" von H. Paul Williams finde ich richtig gut. Kurz gefasst, leicht zu verstehen, enthält jede Menge gute Tipps und Tricks für die Praxis.
20.01.2017, 18:18	Oggel	Auf diesen Beitrag antworten »
Alles klar Danke dir

Neue Frage »

Antworten »

Ganzzahliges lineares Optimierungsproblem

Verwandte Themen