Forum:  Numerik & Optimierung
Thema: Drei lineare Ungleichungsrestriktion umschreiben
Themen-Übersicht
Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Themenstart: 2019-11-25 15:19

Hallo,

als erstes, falls das Thema hier nicht passen sollte verschiebe ich es ganz schnell :)

Zu meinem Problem:

fed-Code einblenden

Mein Ansatz war wie folgt:

a + b >= c
a + b <= c

jedoch hat es so nicht geklappt.

Ich versuche schon eine ganze Weile es hinzubekommen jedoch komme ich leider nicht drauf.
Wäre für jede Hilfe/Tipp sehr Dankbar.

Beste Grüße
Shakei


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2809
Aus: der Nähe von Schwerin
Beitrag No.1, eingetragen 2019-11-25 15:28

Hallo,

wenn $a,b,c\in\{0,1\}$ sind und $a\cdot b=c$ gilt, so erfüllen es die folgenden Tripel
\[(0,0,0),\,(1,0,0),\,(0,1,0),\,(1,1,1)\] Betrachte also deren konvexe Hülle (das ist ein Simplex oder auch Tetraeder) und beschreibe die Ebenen, in der sich jede Facette befindet. Eigentlich hat es vier Facetten. Komisch. Dürft ihr $a,b,c\geq 0$ voraussetzen?


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2019-11-25 15:52

Hallo,

vielen Dank für den Tip!

Wie wäre es damit:

fed-Code einblenden
Bin ich hiermit auf dem richtigen Weg?

Beste Grüße
Shakei


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2809
Aus: der Nähe von Schwerin
Beitrag No.3, eingetragen 2019-11-25 16:25

Leider bist du gar nicht auf meine Frage eingegangen, ob ihr voraussetzen dürft, dass alle Koordinaten positiv sind. Wenn nicht, wird es kaum möglich sein, ein beschränktes dreidimensionales Polytop mit nur drei Ungleichungen zu beschreiben.

2019-11-25 15:52 - Shakei in Beitrag No. 2 schreibt:
fed-Code einblenden
Bin ich hiermit auf dem richtigen Weg?

Rechne mal bitte alle Ebenen aus auf denen sich drei der vier Punkte befinden.


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2019-11-25 16:45

Die Frage habe ich garnicht bemerkt 'UPS'.
Ja, das dürfen wir.

Meinst du sowas hier:

fed-Code einblenden

Beste Grüße
Shakei


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.5, vom Themenstarter, eingetragen 2019-11-25 18:20

2019-11-25 16:25 - ochen in Beitrag No. 3 schreibt:

Rechne mal bitte alle Ebenen aus auf denen sich drei der vier Punkte befinden.

Ich glaube jetzt habe ich es verstanden.
Habe sowas hier raus:

fed-Code einblenden


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2019-11-27 10:27

Ich habe nochmals nachgezeichnet und es ist mir ein Fehler unterlaufen..

Also ich habe die x,y-Menge, x,z-Menge und die y,z-Menge gezeichnet und jeweils die Restriktionen aufgeschrieben. Dabei kam ich auf folgende Ungleichungsrestriktionen:

fed-Code einblenden

Jedoch steht in der Aufgabenstellung von drei Ungleichungsrestriktionen daher bin ich mir nicht sicher..


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2809
Aus: der Nähe von Schwerin
Beitrag No.7, eingetragen 2019-11-27 10:54

Hallo,

berechne doch bitte die Ebenen auf denen sich jeweils drei der vier Punkte
\[(0,0,0),\,(1,0,0),\,(0,1,0),\,(1,1,1)\] befinden.

Auf welcher Ebene sind beispielsweise die Punkte $(1,0,0),\,(0,1,0),\,(1,1,1)$ zu finden?

Hier beschreibe ich mal das allgemeine Vorgehen:
Wenn du die Punkte $v_1,v_2,v_3\in \mathbb{R}^3$ gegeben hast, so ist $n=(v_2-v_1)\times (v_3-v_1)$ ein Normalenvektor auf die Ebene durch diese Punkte. Es bildet also $\{v\in \mathbb{R}^3\mid\langle n,v\rangle = \langle n,v_1\rangle\}$ eine Ebene.


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.8, vom Themenstarter, eingetragen 2019-11-27 11:46

Ah Danke sehr.

Also ich habe n=(1,1-1) raus.

für <n,v> = 1

aber ein Wert ist doch keine Ebene? Oder habe ich hier wieder was nicht verstanden..


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2809
Aus: der Nähe von Schwerin
Beitrag No.9, eingetragen 2019-11-27 11:57

Das bedeutet, dass die Ebene mit der Gleichung
\[\{x\in \mathbb{R}^3\mid x+y-z=1\}\] die Punkte $(1,0,0),\,(0,1,0),\,(1,1,1)$ enthält. Insbesondere sind sie in den Halbräumen
\[\{x\in \mathbb{R}^3\mid x+y-z\leq 1\}\quad\text{und}\quad \{x\in \mathbb{R}^3\mid x+y-z\geq1\}\] enthalten. In welchem der beiden Halbräume ist auch der Punkt $(0,0,0)$?


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.10, vom Themenstarter, eingetragen 2019-11-27 12:06

2019-11-27 11:57 - ochen in Beitrag No. 9 schreibt:
Das bedeutet, dass die Ebene mit der Gleichung
\[\{x\in \mathbb{R}^3x+y-z=1\}\] die Punkte $(1,0,0),\,(0,1,0),\,(1,1,1)$ enthält. Insbesondere sind sie in den Halbräumen
\[\{x\in \mathbb{R}^3x+y-z\leq 1\}\quad\text{und}\quad \{x\in \mathbb{R}^3x+y-z\geq1\}\] enthalten. In welchem der beiden Halbräume ist auch der Punkt $(0,0,0)$?

aaah.

Der Punkt $(0,0,0)$ ist hier enthalten.
\[\{x\in \mathbb{R}^3x+y-z\leq 1\}\]


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.11, vom Themenstarter, eingetragen 2019-11-27 12:26

Ich habe die restlichen Vier Kombinationen ausgerechnet und komme kam insgesamt auf diese Gleichungen:

fed-Code einblenden

Die Probe habe ich mit den Vier Möglichen Variationen gemacht und die Ungleichungen erfüllen alle Vier.

Vielen Dank für deine große Hilfe!


ochen
Senior
Dabei seit: 09.03.2015
Mitteilungen: 2809
Aus: der Nähe von Schwerin
Beitrag No.12, eingetragen 2019-11-27 13:25

Hallo, $y-z=-1$ ist keine der Ebenengleichungen, weil hier keiner der Punkte drauf liegt :(

Die Ungleichungen müssen nicht nur erfüllt sein, sondern drei der vier Punkte müssen sie auch mit Gleichheit erfüllen.
Auf der Ebene $y-z=0$ liegen drei der vier Punkte.


Shakei
Aktiv
Dabei seit: 25.05.2019
Mitteilungen: 53
Aus:
Beitrag No.13, vom Themenstarter, eingetragen 2019-11-27 13:51

Hallo,

ah ja Danke für den Hinweis. Habe bei Gleichungsaufstellung da was vertauscht.
Jetzt müsste alles stimmen :)


Anno123
Junior
Dabei seit: 18.11.2019
Mitteilungen: 16
Aus:
Beitrag No.14, eingetragen 2019-11-27 17:46

Hallo,

ich würde auch gerne kurz meinen Senf dazu geben, weil solche Modellierungen Grundwerkzeuge in der Optimierung sind und Optimierung selbst einfach massenweise interessante Anwendungen hat. Solche Modellierungsprobleme (insbesondere mit boolschen Variablen) lassen sich in der Regel recht leicht lösen, aber ich habe das Gefühl, dass vielen Leuten die Strategie dafür nie richtig vermittelt wurde.
Zunächst nehmen wir an, dass $a,b,c \in \{0,1\}$ als Voraussetzung gegeben ist (Ganzzahligkeit mit linearen Nebenbedingungen zu modellieren kann man im Allgemeinen vergessen).
Nun muss $a\cdot b = c$ mittels logischer Aussagen modelliert werden. Wir sehen hier beispielsweise, dass
$$ a= 0 \Rightarrow c = 0$$ gilt. Welche zwei weiteren Aussagen braucht man, damit $a\cdot b = c$ genau dann gilt, wenn diese drei Aussagen für $(a,b,c) \in \{0,1\}^3$ wahr sind?
Wenn man seine Aussagen hat, dann kann man mit etwas Übung schnell sehen, wie man sie mit linearen Ungleichungen ausdrückt. Gerade zu Anfang kann man sowas aber auch gut nachschlagen. Hier werden die "Rezepte" dafür schön übersichtlich dargestellt:

cs.stackexchange.com/questions/12102/express-boolean-logic-operations-in-zero-one-integer-linear-programming-ilp

Viele Grüße,
Anno


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1448
Aus: Chile, Ulm
Beitrag No.15, eingetragen 2019-12-01 18:01

2019-11-25 15:28 - ochen in Beitrag No. 1 schreibt:
Wenn $a,b,c\in\{0,1\}$ sind und $a\cdot b=c$ gilt, so erfüllen es die folgenden Tripel
\[(0,0,0),\,(1,0,0),\,(0,1,0),\,(1,1,1)\] Betrachte also deren konvexe Hülle (das ist ein Simplex oder auch Tetraeder) und beschreibe die Ebenen, in der sich jede Facette befindet. Eigentlich hat es vier Facetten. Komisch.

2019-11-27 17:46 - Anno123 in Beitrag No. 14 schreibt:
Zunächst nehmen wir an, dass $a,b,c \in \{0,1\}$ als Voraussetzung gegeben ist.


Wir arbeiten hier freilich nicht in \(\{0,1\}^3\),  sondern bestenfalls in \(\{0,1\}^2\times\mathbb{R}\).  Dafür brauchen wir die Ungleichung \(c\ge0\), um die Möglichkeit \(a=b=0,\ -1\le c<0\) auszuschließen.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=244558=110
Druckdatum: 2020-06-06 03:43