Die Mathe-Redaktion - 18.02.2020 01:54 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 389 Gäste und 6 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 

Antworte auf:  Spiel schriftlich modellieren als lineares binäres Optimierungsproblem von Shakei
Forum:  Numerik & Optimierung, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 
 


Eingabehilfen (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-Bereich] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-Bereich][show-Bereich] [Quelltext [num.]][?]
 Zeige Vorschau      Schreibe im fedgeoFormeleditor oder mit Latex.

Wähle Smilies für Deine Nachricht: :-) :-( :-D ;-) :-0 8-) :-? :-P :-|
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.40, eingetragen 2020-01-11 18:15    [Diesen Beitrag zitieren]

2020-01-11 11:56 - Shakei in Beitrag No. 39 schreibt:
Ich habe die beiden visuell programmiert.
Bei den beiden kam es zu Verzweigungen und zu Sprüngen.

Zeige uns doch mal deine Lösungen mit den Verzweigungen und Sprüngen. Dann können wir selber überprüfen, ob die Ungleichungen der letzten Formulierung erfüllt sind oder nicht (überprüfen geht ja viel schneller als finden).


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.39, eingetragen 2020-01-11 11:56    [Diesen Beitrag zitieren]

Meine Antwort kommt etwas zu spät aber lieber spät als nie :D
Also erstmal vielen Dank für die beiden Lösungsvorschläge.
Ich habe die beiden Visuell programmiert.

Bei den beiden kam es zu Verzweigungen und zu Sprüngen. Bedeutet jedoch nicht das die Restriktionen Fehlerhaft waren, könnte auch daran liegen, dass ich noch weitere Restriktionen in meinem Programm einbauen müsste.

Wollte ich nur mal als Info geben.



Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.38, eingetragen 2019-12-17 00:59    [Diesen Beitrag zitieren]

Anscheinend lässt sich das Farbschlangen-Problem über ein ganzzahlig lineares Ungleichungssystem relativ kurz formulieren; freilich immer noch mit  \(|F|^2\)  Variablen und  \(O(|F|^2)\)  Ungleichungen  (für Hinweise auf mögliche Fehler bin ich dankbar):

\[
F ~\stackrel{\rm{def}}{=}~ \{(i,j) ~:~ (i,j)~~\mbox{Feldqindexpaar}\}
\\
N(k,l) ~~\stackrel{\rm{def}}{=}~~
\{\,(k,l-1),\, (k,l+1),\, (k-1,l),\, (k+1,l)\,\} ~~\cap~~ F
\\
C ~\stackrel{\rm{def}}{=}~ \{c ~:~ c~~\mbox{Farbqindex}\},\qquad
T ~\stackrel{\rm{def}}{=}~ \{t ~:~ 0\le t\lt |F|/|C|\}

\\~\\~\\

\forall (i,j)\in F,~~ \forall c\in C,~~ \forall t\in T\qquad
x_{i,j}^{c,t}\in\{0,1\}\\
\mbox{mit \(x_{i,j}^{c,t}=1\)
wenn Feld \((i,j)\) in Zug \(t\) auf Farbe \(c\) wechselt}

\\~\\~\\

\forall c\in C,~~ \forall t\in T\setminus0\qquad
\sum_{(i,j)\in F} x_{i,j}^{c,t} ~=~ 1
\\
\forall (k,l)\in F,~~ \forall c\in C,~~ \forall t\in T\setminus0\qquad
x_{k,l}^{c,t} ~\le \!\!\sum_{(i,j)\in N(k,l)}\!\! x_{i,j}^{c,t-1}
\\~\\
\forall (i,j)\in F,\qquad
\sum_{c\in C}\, \sum_{t\in T}\, x_{i,j}^{c,t} ~=~ 1
\] (plus Startbedingungen)

Das macht die Aufgabe zu einem Zuordnungsproblem mit (sehr vielen) zusätzlichen Nebenbedingungen. Also kein echtes Zuordnungsproblem.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.37, eingetragen 2019-12-16 21:57    [Diesen Beitrag zitieren]

2019-12-16 21:08 - Delastelle in Beitrag No. 36 schreibt:
Wenn Du die Aufgabe mit linearer Optimierung lösen kannst, ist das gut.

Das hängt sicher sehr davon ab, wie groß "die" Aufgabe ist; ich habe auch den Eindruck, dass dein Ansatz weniger Computerzeit beansprucht. Aber wie gesagt dachte ich, dass die Modellierung mit Ungleichungen eine Vorgabe für den Fragesteller sei.


Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1407
Herkunft:
 Beitrag No.36, eingetragen 2019-12-16 21:08    [Diesen Beitrag zitieren]

Hallo,

@Goswin:
wenn Du die Aufgabe mit linearer Optimierung lösen kannst, ist das gut.

Sollte aber die Diskussion in einer Sackgasse enden wie unter Umständen auch eine gelbe oder rote Schlange ( :-) ) so biete ich alternative Lösungsverfahren an.

Viele Grüße
Ronald


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.35, eingetragen 2019-12-16 16:48    [Diesen Beitrag zitieren]

2019-12-15 00:42 - Delastelle in Beitrag No. 32 schreibt:
Wenn ich ein Problem nicht als [ganzzahlig] lineares Optimierungsproblem lösen kann, löse ich es anders.

@Delastelle:
Um deine Sorge zu zertreuen, dass so etwas (mit O(|F|^2) Variablen und ebensovielen Ungleichungen) leicht modellierbar ist, zeige ich dir im folgenden eine Lösung (ohne besondere Erklärungen) razz

Freilich hat uns der Fragesteller bisher noch nicht verraten, ob es ihm um das Modellieren mit Ungleichungssystemen oder um die Suche von Farbschlangen geht (??)


[veraltet, siehe Beitrag No. 38]
\[
F ~\stackrel{\rm{def}}{=}~ \{(i,j) ~:~ (i,j)~~\mbox{Feldqindexpaar}\}
\\
N(k,l) ~~\stackrel{\rm{def}}{=}~~
\{\,(k,l-1),\, (k,l+1),\, (k-1,l),\, (k+1,l)\,\} ~~\cap~~ F
\\
C ~\stackrel{\rm{def}}{=}~ \{c ~:~ c~~\mbox{Farbqindex}\},\qquad
T ~\stackrel{\rm{def}}{=}~ \{t ~:~ 0\le t\lt |F|/|C|\}

\\~\\~\\

\forall (i,j)\in F,~~ \forall c\in C,~~ \forall t\in T\qquad
x_{i,j}^{c,t}\in\{0,1\}\\
\mbox{mit \(x_{i,j}^{c,t}=1\)
wenn Feld \((i,j)\) nach Zug \(t\) die Farbe \(c\) hat}
\\
\forall (i,j)\in F,~~ \forall c\in C,~~ \forall t\in T\qquad
y_{i,j}^{c,t}\in\{0,1\}\\
\mbox{mit \(y_{i,j}^{c,t}=1\)
wenn Schlangenkopf \(c\) nach Zug \(t\) auf Feld \((i,j)\) ist}

\\~\\~\\

\forall c\in C,~~ \forall t\in T\setminus0\qquad
\sum_{(i,j)\in F} y_{i,j}^{c,t} = 1
\\
\forall (k,l)\in F,~~ \forall c\in C,~~ \forall t\in T\setminus0\qquad
y_{k,l}^{c,t} ~\le \!\!\sum_{(i,j)\in N(k,l)}\!\! y_{i,j}^{c,t-1}
\\~\\
\forall (i,j)\in F,~~ \forall c\in C,~~ \forall t\in T\setminus0\qquad
x_{i,j}^{c,t} \ge y_{i,j}^{c,t}
\\
\forall (i,j)\in F,~~ \forall c\in C,~~ \forall t\in T\setminus0\qquad
x_{i,j}^{c,t} \ge x_{i,j}^{c,t-1}
\\~\\
\forall (i,j)\in F,~~ \forall c\in C,~~ \forall t\in T\setminus0\qquad
y_{i,j}^{c,t} + x_{i,j}^{c,t-1} \le 1
\\
\Big(\mbox{oder auch}\quad
\forall (i,j)\in F,~~ \forall t\in T\setminus0\qquad
\sum_{c\in C} y_{i,j}^{c,t} + \sum_{c\in C} x_{i,j}^{c,t-1} \le 1 \Big)
\] (Hier fehlen natürlich noch die Startbedingungen)


Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1407
Herkunft:
 Beitrag No.34, eingetragen 2019-12-15 23:45    [Diesen Beitrag zitieren]

Hallo Shakei!

Manchmal kann man Optimierungsprobleme in ganzzahlig lineare Form bringen. So sind die schwierigen Rundreiseprobleme (TSP) auch als ganzzahlig lineare Probleme lösbar.

Dein Beispiel aus Nr.16 kann man leicht mittels Branch&Bound/Backtracking lösen. Man muss nur alle Rot/Gelbschlangen der Länge 5 herstellen und in den Spielplan einpassen. Die Richtungen sind nur 4 (korrekt?) oben, rechts, unten und links.

Bei größeren Spielbrettern und mehr Schlangen könnte man lokale Suchtechniken anwenden. Man startet beispielsweise mit mehreren Zufallsschlangen berechnet die Kollisionen (typischerweise doppelt belegte Felder oder leere Felder) und macht lokale Verbesserungsschritte. Dabei kann beispielsweise aus einer Schlange eine Richtung in eine andere Richtung geändert werden.

Ob dieser Ansatz eine Lösung liefert, hängt sicherlich auch von der Dimension des Spielfeldes ab bzw. der Anzahl der Schlangen.
Dein Beispiel aus Nr.16 würde nicht mal eine Sekunde Rechnenzeit brauchen.

Viele Grüße
Ronald


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.33, eingetragen 2019-12-15 09:37    [Diesen Beitrag zitieren]

2019-12-15 00:42 - Delastelle in Beitrag No. 32 schreibt:
Hallo,

2019-12-14 17:53 - Shakei in Beitrag No. 31 schreibt:
Hatte mir sowas überlegt wo die Schlange sich immer bewegen darf. Aber das ist auch nicht richtig. (Beispiel für Farbe Rot):
fed-Code einblenden

Was soll bitteschön die Summe von 1 bis 3 über der Zahl 1 sein?

Oh man. Da habe ich was falsches aufgeschrieben...

fed-Code einblenden

Das war eigentlich gemeint.

@Ronald
Ja wirklich weiter kam ich bisher nicht weiter..




Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1407
Herkunft:
 Beitrag No.32, eingetragen 2019-12-15 00:42    [Diesen Beitrag zitieren]

Hallo,

2019-12-14 17:53 - Shakei in Beitrag No. 31 schreibt:
Hatte mir sowas überlegt wo die Schlange sich immer bewegen darf. Aber das ist auch nicht richtig. (Beispiel für Farbe Rot):
fed-Code einblenden

Was soll bitteschön die Summe von 1 bis 3 über der Zahl 1 sein?

Wir sind jetzt bei Beitrag 32 und kommen nicht vorwärts.

@all
Wenn ich ein Problem nicht als lineares Optimierungsproblem lösen kann, löse ich es anders.

Viele Grüße
Ronald


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.31, eingetragen 2019-12-14 17:53    [Diesen Beitrag zitieren]

Hatte mir sowas überlegt wo die Schlange sich immer bewegen darf. Aber das ist auch nicht richtig. (Beispiel für Farbe Rot):
fed-Code einblenden

Oder sowas wie eine Menge mit den Bewegungstupeln (für Beispiel Rot) wie:
fed-Code einblenden
also Nachbar-Tupeln, Horizontal und Vertikal.

Aber komme einfach nicht mehr weiter.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.30, eingetragen 2019-12-14 03:58    [Diesen Beitrag zitieren]

2019-12-14 00:02 - Delastelle in Beitrag No. 29 schreibt:
Sieht für mich nach einem diskreten Optimierungsproblem aus.

Hallo Ronald,

ich halte die Aufgabestellung für sehr interessant, aber auch für dem entsprechend schwierig!

Aber du gehst ja nicht auf meine Frage ein: Ich sehe keine besondere Schwierigkeit, mit Hilfe der Endmatrix einen möglichen Verlauf der verschiedenen Farbschlangen zu finden. Siehst du da etwa eine? (Und diese Suche nach Farbschlangen bei bekannter Endmatrix sieht für mich *nicht* exponentiellbeschränkt aus)

Bisher war ich schon davon ausgegangen, dass die Suche nach einer zulässigen Endmatrix (nicht die Suche nach Farbschlangen bei bekannter Endmatrix) als diskretes Problem modelliert werden müsste. Aber das wäre ja noch kein Grund, die Fragestellung nicht so anzugehen!

Ich gebe aber zu, dass ich bisher keine (kurze) Modellierung für eine solche zulässige Endmatrix gefunden habe; vielleicht ist dieser Endmatrix-Ansatz ganz nutzlos und man muss tatsächlich (wie Shakei vorgeschlagen hat) das Wachstum der Farbschlangen Schritt für Schritt im Modell nachbilden.


Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1407
Herkunft:
 Beitrag No.29, eingetragen 2019-12-14 00:02    [Diesen Beitrag zitieren]

Hallo,

aus Beitrag 16:
Gelbschlange = [1 4; 2 4; 3 4; 3 3; 2 3; 1 3]
Rotschlange = [2 2; 3 2; 3 1; 2 1; 1 1; 1 2]
(Zeilenindex, Spaltenindex)
Dazu kann man berechnen welche Felder vom Spielbrett noch nicht belegt sind und ob es Kollisionen gibt als doppelt belegte Felder.
Weiterhin kann man schauen ob noch alle Felder erreichbar sind.
Sieht für mich nach einem diskreten Optimierungsproblem aus.

Viele Grüße
Ronald

Edit:
2 Schlangen mit Länge 5 ergibt:
4^4 * 4^4 als obere Schranke der Anzahl der
Möglichkeiten = 256*256 = 65536 mit
Zugmöglichkeiten rechts, links, oben, unten.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.28, eingetragen 2019-12-13 15:27    [Diesen Beitrag zitieren]

2019-12-13 07:39 - Shakei in Beitrag No. 27 schreibt:
Das ist genau mein Problem was ich von Anfang an sagte.
Mir fällt nicht ein wie ich diesen "Sprung" vermeiden kann.

Das ist eines der Probleme. Ein anderes wäre, zu vermeiden, dass eine "Farbschlange" mehr als zwei Enden hat (wie im Beispiel Rot). Dafür bräuchtest du zusätzliche Variablen.

Ich bin mir aber jetzt nicht mehr sicher, dass mein Endmatrix-Ansatz zum Ziel führt, vielleicht muss man tatsächlich, wie du anfangs wolltest, jede Bewegung der Schlangen einzeln modellieren. Für so etwas brauchst du dann freilich noch viel mehr Variablen, wie zum Beispiel \(x_{ijsf}\in\{0,1\}\) mit \(s\in\{1,\ldots,\rm{Schrittanzahl}\}\).

Im Startbeitrag schreibst du "Ich muss ein Spiel als lineares binäres Optimierungsproblem modellieren". Wie bist du eigentlich auf diese Aufgabestellung gekommen, die dich (und vielleicht auch mich) etwas überfordern könnte?  Und wer hat dir aufgetragen, das Problem mit binärer linearer Optimierung zu lösen (es gibt ja auch andere Ansätze)?


@Delastelle:
Ich habe natürlich bei meinem Ansatz ausgeklammert, wie genau wir mit Hilfe der Endmatrix im Anschluss einen Verlauf der verschiedenen Farbschlangen finden. Siehst du da eine besondere Schwierigkeit?


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.27, eingetragen 2019-12-13 07:39    [Diesen Beitrag zitieren]

2019-12-13 00:29 - Goswin in Beitrag No. 26 schreibt:
Nein, du hast eine Eigenschaft deiner Endmatrix aufgeschrieben; da fehlen noch viele andere. Wie zum Beispiel schließt du folgendes aus:

fed-Code einblenden
?

Das ist genau mein Problem was ich von Anfang an sagte.
Mir fällt nicht ein wie ich diesen "Sprung" vermeiden kann.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.26, eingetragen 2019-12-13 00:29    [Diesen Beitrag zitieren]

2019-12-11 17:30 - Shakei in Beitrag No. 25 schreibt:
Dann habe ich wohl die Eigenschaften meiner Endmatrix aufgeschrieben.

Nein, du hast eine Eigenschaft deiner Endmatrix aufgeschrieben; da fehlen noch viele andere. Wie zum Beispiel schließt du folgendes aus:

fed-Code einblenden
?


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.25, eingetragen 2019-12-11 17:30    [Diesen Beitrag zitieren]

Dann habe ich wohl die Eigenschaften meiner Endmatrix aufgeschriebeni


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.24, eingetragen 2019-12-11 16:51    [Diesen Beitrag zitieren]

Deine Ungleichungen darfst du gerne auch in zusammenfassender Notation aufstellen, also \[
\forall f \in \{G,R,B\}\qquad
\sum_{i=1}^3 \sum_{j=1}^4 a_{ijf} \le4
\] oder mit den Definitionen  \(M(3,4) \stackrel{\rm def}{=} \{1,2,3\}\!\times\!\{1,2,3,4\},~\) \(F \stackrel{\rm def}{=} \{G,R,B\}\)  auch \[
\forall f \in F\quad
\sum_{(i,j)\in M(3,4)}\!\! a_{ijf} \le4
\] (Dass du deine Variablen \(a_{ijf}\) und nicht \(x_{ijf}\) nennst ist zwar unüblich, aber in Ordnung, solange du selber damit zurechtkommst, und sie nicht mit Farben, Indizes oder sonst etwas verwechselst)


2019-12-11 13:27 - Shakei in Beitrag No. 23 schreibt:
Rechtecke einer Farbe dürfen nicht vorhanden sein
Das stimmt zwar für das oben vorgegebene Beispiel, ist aber allgemein falsch; für die folgende Endmatrix trifft es jedenfalls nicht zu:

Schritt-3
fed-Code einblenden


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.23, eingetragen 2019-12-11 13:27    [Diesen Beitrag zitieren]

2019-12-11 11:53 - Goswin in Beitrag No. 22 schreibt:

Schritt-3:
fed-Code einblenden

Gegeben ist eine 3x4-Matrix mit der variable
fed-Code einblenden

fed-Code einblenden
Die Farben Gelb, Rot, Blau haben jeweils einen Startpunkt die Festgelegt sind:
fed-Code einblenden
In meiner Endmatrix müssen jeweils 4-Gelbe, 4-Rote und 4-Blaue Farben vorhanden sein:
fed-Code einblenden
Rechtecke einer Farbe dürfen nicht vorhanden sein:
fed-Code einblenden

Jetzt müsste ich noch etwas konstruieren, dass die Farben keine Sprünge haben bzw. sich immer von deren Startpunkten Horizontal bzw. Vertikal bewegen


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.22, eingetragen 2019-12-11 11:53    [Diesen Beitrag zitieren]

2019-12-11 09:25 - Shakei in Beitrag No. 21 schreibt:
Ich bin der Meinung, dass wenn man ein Optimierungsproblem mit meinem 3x4 Feld Bsp. angeben kann auch in einen größeren Spielverlauf übertragen kann.

Deine Aufgabestellung glaube ich, wie bereits erwähnt, gut verstanden zu haben.  Aber ich befürchte, dass du dein Beispiel etwas ungeschickt ausgewählt hast, weil du bei nur zwei Farben anscheinend auf Ideen kommst, welche für "ein 100x200 Feld mit viel viel mehr Farben" völlig unbrauchbar sind.

Ich schlage vor, du nimmst dir jetzt ein Beispiel mit drei Farben vor, Gelb, Rot und Blau, und beschreibst die Eigenschaften, die folgende Endmatrix erfüllen muss:

Schritt-3:
fed-Code einblenden


2019-12-11 09:25 - Shakei in Beitrag No. 21 schreibt:
Wie kann ich Variablen definieren, wobei ich nicht weiß, welche ich noch brauche?
Ok, ich drücke mich genauer aus:
Erst wenn du alle Variablen definiert (und erklärt) hast, die in einer Ungleichung vorkommen, erst dann  kannst du diese Ungleichung sinnvoll aufstellen.


2019-12-11 09:25 - Shakei in Beitrag No. 21 schreibt:
Im obigen Beiträgen habe ich schon aufgeschrieben was meine Variablen etc. bedeuten.
Nein, ich sehe nicht wo. Du hast beschrieben, wie sich deine Farben auf den verschiedenen Feldern der Matrix verändern, aber das sind ja nicht deine Variablen (sondern Indizes von deinen Variablen), und beides darfst du nicht durcheinanderwerfen.


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.21, eingetragen 2019-12-11 09:25    [Diesen Beitrag zitieren]

2019-12-10 23:27 - Goswin in Beitrag No. 19 schreibt:

Es seien die Variablen \[
\forall i\in\{1,2,3\}, ~ j\in\{1,2,3,4\}, ~ f\in\{G,R\}\qquad
x_{ijf}\in\{0,1\}
\] wobei \(x_{ijf}\) den Wert \(x_{ijf}=1\) annehmen soll, wenn Feld \((i,j)\)  in der Endmatrix die Farbe \(f\) hat, und den Wert \(x_{ijf}=0\), wenn dem nicht so ist, es also in der Endmatrix irgendeine andere Farbe hat.

Mit diesem Beispiel nehme ich dir freilich nur einen Teil der Arbeit ab, da du vermutlich weitere Variablen brauchen wirst. Und wenn du alle deine Variablen definiert (und erklärt) hast, erst dann solltest du anfangen, die Ungleichungen aufzustellen, die sie erfüllen müssen.

Im obigen Beiträgen habe ich schon aufgeschrieben was meine Variablen etc. bedeuten. Auch in Worten erklärt wie das Spiel abläuft und was ich genau brauche. Wieso sollte ich jetzt nochmal so aufschreiben wie du es dir wünschst, das ist nicht das was ich brauche..
Wie kann ich Variablen definieren, wobei ich nicht weiß welche ich noch brauche?

2019-12-11 01:42 - Delastelle in Beitrag No. 20 schreibt:
Hallo Shakei!

Du hast 1x aufgeschrieben wie ein möglicher Spielverlauf aussieht (Beitrag 16).
Möchtest Du wissen wie viele Spielverläufe es geben kann?
Oder suchst Du eine Lösung(einen Spielverlauf) wenn das Brett größer ist?
Sofern man die Aufgabe als Optimierungsproblem angeben kann erhält man vielleicht erst mal nur eine Lösung.

Hallo Ronald,

ich möchte gerne nur eine Lösung. Wie das Spielverlauf aussehen könnte habe ich als Bsp. angegeben damit man es sich eventuell besser vorstellen kann wie ich es meine.

Ich bin der Meinung, dass wenn man ein Optimierungsproblem mit meinem 3x4 Feld Bsp. angeben kann auch in einen größeren Spielverlauf übertragen kann.

Mein Problem von Anfang an war, dass ich zurzeit nicht weiß wie ich eine (bzw. mehrere) Restriktionen aufschreibe die meine Startpunkte (also Gelb und Rot) immer nur Horizontal oder Vertikal bewegen lässt. Und das solange bis das ganze Feld mit den Farben Rot und Gelb voll ist.


Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1407
Herkunft:
 Beitrag No.20, eingetragen 2019-12-11 01:42    [Diesen Beitrag zitieren]

Hallo Shakei!

Du hast 1x aufgeschrieben wie ein möglicher Spielverlauf aussieht (Beitrag 16).
Möchtest Du wissen wie viele Spielverläufe es geben kann?
Oder suchst Du eine Lösung(einen Spielverlauf) wenn das Brett größer ist?
Sofern man die Aufgabe als Optimierungsproblem angeben kann erhält man vielleicht erst mal nur eine Lösung.

Viele Grüße
Ronald


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.19, eingetragen 2019-12-10 23:27    [Diesen Beitrag zitieren]

2019-12-10 16:38 - Goswin in Beitrag No. 17 schreibt:
[Die Bedeutung jeder deiner Variablen] solltest du ganz deutlich mit Worten hinschreiben, was du bisher nicht getan hast, ...
... zum  Beispiel:

Es seien die Variablen \[
\forall i\in\{1,2,3\}, ~ j\in\{1,2,3,4\}, ~ f\in\{G,R\}\qquad
x_{ijf}\in\{0,1\}
\] wobei \(x_{ijf}\) den Wert \(x_{ijf}=1\) annehmen soll, wenn Feld \((i,j)\)  in der Endmatrix die Farbe \(f\) hat, und den Wert \(x_{ijf}=0\), wenn dem nicht so ist, es also in der Endmatrix irgendeine andere Farbe hat.


Mit diesem Beispiel nehme ich dir freilich nur einen Teil der Arbeit ab, da du vermutlich weitere Variablen brauchen wirst. Und wenn du alle deine Variablen definiert (und erklärt) hast, erst dann solltest du anfangen, die Ungleichungen aufzustellen, die sie erfüllen müssen.


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.18, eingetragen 2019-12-10 17:42    [Diesen Beitrag zitieren]

2019-12-10 16:38 - Goswin in Beitrag No. 17 schreibt:
Dein Spielbrett (bzw deine Beispielsmatrix) hat 3 Reihen und 4 Spalten, das macht 3*4=12 Felder (bzw Einträge).

Ich verstehe aber immer noch nicht wie man auf die Formel kommt..
Mann könnte Felderanzahl = 12 setzen und dann erweitern bis man auf die Formel von dir kommt. Jedoch Frage ich mich wieso man es machen würde.

Mein Endmatrix besteht aus Farbanzahl = 2 und Felderanzahl = 12.
Nach der Formel ergibt sich ein Wert von 44.

Nehmen wir das Matrix Schritt-1:
Farbanzahl = 2 und Felderanzahl = 12. Was soll mir das bringen, oder verstehe ich es falsch?

2019-12-08 23:55 - Goswin in Beitrag No. 7 schreibt:
Das solltest du ganz deutlich mit Worten hinschreiben, was du bisher nicht getan hast.

Also bin wirklich verwirrt  confused
1) Meine zwei Farben haben jeweils einen Startpunkt.
2) Es gibt insgesamt 5 Schritte.
3) Bei jedem Schritt müssen sich die beiden Farben einmal (1) bewegen, mit der Bedingung nur Horizontal oder Vertikal.
4) Die Farben dürfen sich nur dort bewegen wo auch noch keine Farbe vorhanden ist.
5) Nach Schritt 5 muss das die Matrix mit 6 Rote und 6 Gelbe bestehen.

Was ich bisher nicht gemacht habe ist eine "Kupplung" zwischen den Schritten, jedoch willst du vermutlich von mir etwas hören was nur mit der Endmatrix zu tun hat.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.17, eingetragen 2019-12-10 16:38    [Diesen Beitrag zitieren]

2019-12-09 21:30 - Shakei in Beitrag No. 14 schreibt:
Die Formel verstehe ich auch nicht. Felderanzahl wäre doch 1?
Und wie kommst du auf die 44?

Dein Spielbrett (bzw deine Beispielsmatrix) hat 3 Reihen und 4 Spalten, das macht 3*4=12 Felder (bzw Einträge).

2019-12-09 21:30 - Shakei in Beitrag No. 14 schreibt:
Also meine Endmatrix muss aus Einsen (1) bestehen.
Ich weiß jetzt nicht, welche Eigenschaften sie noch haben sollte.

Das glaubst du nach deiner Antwort an Delastelle wohl selber nicht. Deine Endmatrix besteht aus *Farben* (und nicht aus "Einsen"). Und diese Farben können nicht beliebig sein.

2019-12-08 23:55 - Goswin in Beitrag No. 7 schreibt:
Es ist nicht klar, was die Werte [der Variablen a11R, a11G, a12R, a12G, ...] für das Spiel bedeuten.

Das solltest du ganz deutlich mit Worten hinschreiben, was du bisher nicht getan hast.


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.16, eingetragen 2019-12-10 07:18    [Diesen Beitrag zitieren]

2019-12-10 01:45 - Delastelle in Beitrag No. 15 schreibt:
Hallo Shakei!

Mal doch mal einen Spielverlauf auf. Also keine Variablen sondern nur Zahlen und eventuell Matrizen.
So könnte klar werden, was Du meinst!

Viele Grüße
Ronald

Hi Ronald!

Ich mache es mal so, hoffentlich wird es klarer. So könnte das Spielverlauf aussehen:

Start (mit Startpunkten):
fed-Code einblenden

Schritt-1:
fed-Code einblenden

Schritt-2:
fed-Code einblenden

Schritt-3:
fed-Code einblenden

Schritt-4:
fed-Code einblenden

Schritt-5:
fed-Code einblenden


Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1407
Herkunft:
 Beitrag No.15, eingetragen 2019-12-10 01:45    [Diesen Beitrag zitieren]

Hallo Shakei!

Mal doch mal einen Spielverlauf auf. Also keine Variablen sondern nur Zahlen und eventuell Matrizen.
So könnte klar werden, was Du meinst!

Viele Grüße
Ronald


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.14, eingetragen 2019-12-09 21:30    [Diesen Beitrag zitieren]

2019-12-09 20:33 - Goswin in Beitrag No. 13 schreibt:
Ein Tip:
Vergiss den Veränderungsvorgang der Matrix, und konzentriere dich darauf, welche Eigenschaften die Endmatrix haben muss. Diese Eigenschaften musst du modellieren. (Ich bräuchte dafür
\[2*\rm{Farbenanzahl}*(\rm{Felderanzahl}-1)=44\] 0-1-Variablen)

Also meine Endmatrix muss mit einsen (1) bestehen. Ich weiß jetzt nicht welche Eigenschaften es noch haben sollte..

Die Formel verstehe ich auch nicht. Felderanzahl wäre doch 1?
Und wie kommst du auf die 44?


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.13, eingetragen 2019-12-09 20:33    [Diesen Beitrag zitieren]

2019-12-09 16:12 - Shakei in Beitrag No. 12 schreibt:
Mir ist ein Licht aufgegangen eek

Mir hingegen ist mein halbes Licht untergegangen, und ich verstehe gar nichts mehr von dir. frown

Ein Tip:
Vergiss den Veränderungsvorgang der Matrix, und konzentriere dich darauf, welche Eigenschaften die Endmatrix haben muss. Diese Eigenschaften musst du modellieren. (Ich bräuchte dafür
\[2*\rm{Farbenanzahl}*(\rm{Felderanzahl}-1)=44\] 0-1-Variablen)


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.12, eingetragen 2019-12-09 16:12    [Diesen Beitrag zitieren]

2019-12-09 16:03 - viertel in Beitrag No. 11 schreibt:
confused
Eine Variable kann nur ihren Wert ändern (aus 0 wird 1), aber nicht ihren Namen (aus <math>a_{11F}</math> kann nicht <math>a_{11G}</math> werden).

Mir ist ein Licht aufgegangen eek

fed-Code einblenden

Ist es jetzt Richtig?




viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 26937
Herkunft: Hessen
 Beitrag No.11, eingetragen 2019-12-09 16:03    [Diesen Beitrag zitieren]

confused
Eine Variable kann nur ihren Wert ändern (aus 0 wird 1), aber nicht ihren Namen (aus <math>a_{11F}</math> kann nicht <math>a_{11G}</math> werden).


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.10, eingetragen 2019-12-09 15:46    [Diesen Beitrag zitieren]

2019-12-09 15:08 - Goswin in Beitrag No. 9 schreibt:
Oder soll jetzt \(a_{11F}\) eine neue Variable sein? So eine neue Variable existiert laut deiner Definition nicht!

fed-Code einblenden

Ist es so klarer?


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.9, eingetragen 2019-12-09 15:08    [Diesen Beitrag zitieren]

2019-12-09 09:07 - Shakei in Beitrag No. 8 schreibt:
fed-Code einblenden

Deine Aufgabestellung glaube ich inzwischen gut verstanden zu haben. Aber ich beobachte, dass du ständig Indizes, Variablennamen und Variablenwerte verwechselst und durcheinanderwirfst.

Welches Konstrukt soll zum Beispiel für \(a_{11F}\) in der Startmatrix stehen? Eine Matrix besteht aus Werten, und laut deiner Definition sind nur \(a_{11R}\) oder \(a_{11G}\) erlaubt, kein anderer. Und selbst das wären Variablen und keine Zahlenwerte.

Oder soll jetzt \(a_{11F}\) eine neue Variable sein? So eine neue Variable existiert laut deiner Definition nicht!


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.8, eingetragen 2019-12-09 09:07    [Diesen Beitrag zitieren]

2019-12-08 23:55 - Goswin in Beitrag No. 7 schreibt:
Und ich befürchte, dass du gar nicht wissen kannst, ob du die zwei Restriktionen "schon geschafft" hast, solange du keine Gesamtformulierung aufgestellt hast. (Sie sehen gut aus, aber lass den Leser nicht ständig herumraten, was du meinst)

Ich mache es mal neu vllt. wird es dann so klarer:

Das Brett ist ein 3x4 Matrix.
Es gibt zwei verschiedene Farben: Rot und Gelb.
fed-Code einblenden
Die beiden Farben haben jeweils einen Startpunkt.
fed-Code einblenden
Die Matrix sieht mit dem Startpunkten so aus:
fed-Code einblenden
Ziel ist es das nach jedem Schritt die Startpunkte mit seiner Farbe Horizontal oder Vertikal bewegen. Nach Schritt-5 muss dass Feld voll mit den beiden Farben Rot und Gelb versehen sein, d.h. 6 mal Gelb und 6 mal Rot.

In jeder Zelle darf nur eine Farbe vorhanden sein:
fed-Code einblenden
Das was ich brauche ist eine Restriktion die meine Startpunkte nach jedem Schritt Horizontal oder Vertikal bewegen lässt.

Nach Schritt-5 könnte die Matrix so aussehen:
fed-Code einblenden

Für die Bewegung habe ich sowas hier überlegt, jedoch ist es auch nicht ganz richtig:
fed-Code einblenden











Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.7, eingetragen 2019-12-08 23:55    [Diesen Beitrag zitieren]

2019-12-06 11:26 - Shakei im Themenstart schreibt:
Folgende Restriktionen habe ich schon geschafft:

Genau ein Wert in jede Zelle:
a11R + a11G = 1
a12R + a12G = 1

Bevor du anfängst, Nebenbedingungen aufzuschreiben, musst du erst einmal einen Satz Variablen und deren Bezug zum Spiel definieren. Es ist nicht klar, welche Werte deine Variablen a11R, a11G, a12R, a12G annehmen sollen und was diese Werte für das Spiel bedeuten. Und in deinem nächsten Beitrag haben die Variablen auf einmal ganz andere Namen!

(Falls "binär" bedeutet, dass deine Variablen in \(\{0,1\}\) sein sollen, mache dir darüber keine Sorgen. Jedes ganzzahlige und beschränkte Ungleichungssystem kann in ein 0-1-System umgewandelt werden)

Und ich befürchte, dass du gar nicht wissen kannst, ob du die zwei Restriktionen "schon geschafft" hast, solange du keine Gesamtformulierung aufgestellt hast. (Sie sehen gut aus, aber lass den Leser nicht ständig herumraten, was du meinst)


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.6, eingetragen 2019-12-08 10:56    [Diesen Beitrag zitieren]

Keiner hat einen Vorschlag .. /:


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.5, eingetragen 2019-12-06 17:28    [Diesen Beitrag zitieren]

2019-12-06 16:55 - Goswin in Beitrag No. 4 schreibt:

Wann und wie genau wechselt ein Feld seine Farbe?

Also, zu Beginn sind alle Zellen = 0 (also ohne Farben), außer zwei Zellen nämlich a14G (Gelb) und a22R (Rot). Es gibt Insgesamt 12 Zellen. Es müssen 5 Schritte erfolgen. In jedem Schritt bewegen sich die Festgelegten Startpunkte jeweils einmal. Und das nur Horizontal oder Vertikal. Wenn ein Feld mit einer Farbe versehen ist, kann die Farbe nicht geändert werden

z.B: Im Schritt-1 könnte das Feld so aussehen:

fed-Code einblenden

Im Schritt-5 (also der letzte Schritt) könnte es so aussehen:


fed-Code einblenden

2019-12-06 16:55 - Goswin in Beitrag No. 4 schreibt:
Wenn das Spielbrett "am Ende mit Farben versehen" ist, was soll da noch optimiert werden? Oder soll irgendeine beliebige Art gefunden werden, um das Feld am Ende mit Farben zu versehen?
Das Spielbrett soll am Ende mit den zwei Farben (Gelb und Rot) versehen werden. Dabei sollen die Restriktionen (wie oben beschrieben) berücksichtigt werden.

Würde man sich ein 100x200 Feld mit viel viel mehr Farben Vorstellen, könnte es problematisch werden es intuitiv zu füllen.
Daher fange ich mit einem kleinen Feld an :)

Ich hoffe ich habe deine Frage beantwortet.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.4, eingetragen 2019-12-06 16:55    [Diesen Beitrag zitieren]

2019-12-06 14:11 - Shakei in Beitrag No. 2 schreibt:
Das ganze "Feld" muss am Ende mit Farben versehen sein.
Also sechs Gelbe und sechs Rote.

Wann und wie genau wechselt ein Feld seine Farbe?
(Ich kann mir da zwar einiges vorstellen, habe aber keine Lust, die Zeit in meine Vorstellungen zu investieren)

Wenn das Spielbrett "am Ende mit Farben versehen" ist, was soll da noch optimiert werden? Oder soll irgendeine beliebige Art gefunden werden, um das Feld am Ende mit Farben zu versehen?


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.3, eingetragen 2019-12-06 16:35    [Diesen Beitrag zitieren]

Mein Ansatz wäre sowas hier (Bsp )für die Farbe Gelb:

fed-Code einblenden

Für den ersten Schritt geht es, jedoch für den zweiten Schritt bräuchte die Variable a der im ersten Schritt genommen wurde..








Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Beitrag No.2, eingetragen 2019-12-06 14:11    [Diesen Beitrag zitieren]

Ja, also das ganze "Feld" muss am Ende mit Farben versehen sein.
Also sechs Gelbe und sechs Rote.

Das wars.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1397
Herkunft: Chile, Ulm
 Beitrag No.1, eingetragen 2019-12-06 14:05    [Diesen Beitrag zitieren]

(2019-12-06 11:26 - Shakei im post_id=1782409>Themenstart)
Ich muss ein Spiel als lineares binäres Optimierungsproblem modellieren.
[...]
Es gibt jeweils 5 Schritte. Bei jedem Schritt müssen die Startpunkte (a14G und a22R) sich bewegen. Sie dürfen sich aber nur Horizontal oder Vertikal bewegen. Also wie eine Art Schlange.

... und sonst passiert weiter gar nichts ??


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Herkunft:
 Themenstart: 2019-12-06 11:26    [Diesen Beitrag zitieren]

Hallo,

ich muss ein Spiel als lineares binäres Optimierungsproblem Modellieren.

Das Brett ist ein 3x4 Matrix.
Es gibt zwei verschiedene Farben: Rot und Gelb.
Die beiden Farben haben jeweils einen Startpunkt festgelegt.

So sieht es aus:
F steht für Farbe (Rot oder Gelb das noch nicht festgelegt ist).

Meine Startpunkte sind die beiden:
a14G
a22R
Es sieht wie folgt aus:
fed-Code einblenden

Folgende Restriktionen habe ich schon geschafft:

Genau ein Wert in jede Zelle:
a11R + a11G = 1
a12R + a12G = 1
...

Startpunkt festlegen:
a14G = 1
a22R = 1

aijF kann nur den Wert 1 oder 0 annehmen. Ist der Wert 1, dann ist die Zelle festgelegt.


So zu meinem Problem:
Es gibt jeweils 5 Schritte. Bei jedem Schritt müssen die Startpunkte (a14G und a22R) sich bewegen. Sie dürfen sich aber nur Horizontal oder Vertikal bewegen. Also wie eine Art Schlange. Und da bin ich die ganze Zeit am verzweifeln wie ich es aufschreiben soll..

Hat jemand Tipps für mich?



 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]