binäre Variablen < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 19:08 So 11.02.2007 | | Autor: | claudi1980 |
Hallo, ich habe da noch ne Frage zu binären Variablen. Und zwar soll die binäre Variable y den Wert 1 annehmen, wenn die binären Variablen x und z beide jeweils den Wert 1 entsprechen. Wenn x oder z den Wert Null haben, soll y=0 sein.
Könnt ihr mir auch da weiterhelfen?
Da mir das Handling mit binären Variablen sehr schwer fällt, wollte ich noch fragen, ob mir jemand bestimmte Literatur mit guten Beispielen dazu empfehlen kann.
Vielen Dank!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Claudia
|
|
| |
|
Hallo claudi1980!
> Hallo, ich habe da noch ne Frage zu binären Variablen. Und
> zwar soll die binäre Variable y den Wert 1 annehmen, wenn
> die binären Variablen x und z beide jeweils den Wert 1
> entsprechen. Wenn x oder z den Wert Null haben, soll y=0
> sein.
>
> Könnt ihr mir auch da weiterhelfen?
Ich glaube, das gehört eher in den Bereich der Aussagenlogik, deswegen verschiebe ich es mal.
Außerdem ist mir nicht klar, was denn die Aufgabenstellung ist. Die angegebenen "Funktion" nennt sich "AND" und man schreibt sie ganz einfach so: [mm] $y=x\wedge [/mm] z$. Aber was sollst du damit machen?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Hallo Bastiane, ich schreibe gerade meine Diplomarbeit in Operations Research und bearbeite dabei ein praktisches Problem. Dieses praktische Problem möchte ich mit einem mathematischen Modell lösen. Dabei kommen ganz viele verschachtelte "wenn, dann, sonst (wenn...)" - Bedingungen vor. Um diese Bedingungen zu entschachteln, wollte ich binäre Variablen einfügen, aber leider bekomme ich das nicht so hin, wie ich will.
Dieser Ausdruck steht für mein Problem:
[mm] y_{n}=\begin{cases} 1, & \mbox{für } x_{n}+ z_{n}=2\mbox{ für n=1,...,m} \\ 0, & \mbox{sonst} \mbox{} \end{cases}, [/mm]
aber ich weiss nicht, wie ich das so formulieren kann, dass ich die sich ergebende Gleichung(en) in einem z.B. Simplexalgorithmus verwenden kann.
Ich hoffe, Du verstehst, was ich meine.
Liebe Grüße und danke für die Antwort!
Claudia
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:36 So 11.02.2007 | | Autor: | piet.t |
Hallo Claudia,
wenn man die zwei Binärvariablen x und z als Wahrheitswerte ansieht (1 = wahr, 0=falsch), dann lassen sich elementare logische Formeln auch als lineare Restriktionen formulieren.
Zum Beispiel:
[mm]x \vee y[/mm] schreibt sich als x+y >= 1
[mm]x \wedge y[/mm] schreibt sich als x+y>=2
Soll jetzt z genau dann = 1 sein, wenn x=1 und y=1, dann könnte man das so formulieren:
x+y >= 2z
Denn die linke Seite wird ja nur dann >=2 wenn x und y beide = 1 sind.
Ich hoffe das hilft schon mal.
Gruß
piet
P.S.: Wenn Du mit Binärvariablen arbeitest hilft Dir der einfache Simplex-Algorithus natürlich nicht mehr weiter, da man dann ja schon ein gemischt ganzzahliges Problem vorliegen hat, welches etwas raffiniertere Lösungsmehtoden braucht. Aber das war Dir ja wahrscheinlich sowieso schon klar...
|
|
|
| |
|
Hallo Piet,
vielen Dank für Deine Antwort.
Da plumsen mir echt ein paar Steine vom Herzen. Ich ärgere mich nur, dass ich da nicht drauf gekommen bin.
Gibt es einen Trick, wie man das mit den binären Variablen immer hin bekommt?
Mit dem Simplex hast Du recht, ich wollte nur verdeutlichen, was ich meine und wusste nicht, wie ich es besser ausdrücken soll.
Liebe Grüße!
Claudia
|
|
|
| |
|
Hallo Piet, ich habe jetzt nochmal eine Nacht drüber geschlafen und da ist mir aufgefallen, dass bei x+y>=2z, wenn x=1 und y=1, dann kann z 0 oder 1 sein. Aber meine bedingung soll doch so sein, dass z dann nur 1 sein muss. Für die "sonst" Bedingungen, also x=1 und y=0 oder umgekehrt und x=y=o muss z=0 sein. Da stimmt es.
Hast Du noch eine Idee? Kann man noch eine 2. (Un)gleichung dazu aufstellen?
Danke!
Claudia
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:02 Mo 12.02.2007 | | Autor: | piet.t |
Uuups, jetzt wo Du es sagst....
Ich hab mir das ganze nochmal in meinem OR-Skript durchgesehen, da ist relativ systematisch dargestellt, wie man Aussagenlogische Formeln in entsprechende lineare Restriktionen umsetzt. Wir machen das mal an einem Beispiel durch - vielleicht beantwortet das dann auch Deine andere Frage.
Was wir also brauchen ist eine Restriktion in der (logischen) Form
[mm](x\wedge y) \leftrightrightarrow z[/mm]
Als erstes muss man diese Formel in "konjunktive Normalform" bringen, d.h. es dürfen nur durch "und" verknüpfte "oder"-Ketten dastehen.
Dazu entfernen wir erstmal die Pfeile:
[mm]x\wedge y \leftrightarrow z[/mm]
[mm]((x\wedge y)\rightarrow z) \wedge(z\rightarrow(x\wedge y))[/mm]
[mm](\neg(x\wedge y)\vee z)\wedge(\neg z \vee(x \wedge y))[/mm]
Dann die Nageationen möglichst weit nach innen ziehen
[mm](\neg x \vee \neg y \vee z) \wedge (\neg z \vee(x\wedge y))[/mm]
...und dann noch alle "oder", die noch nicht auf der untersten Klammerebene sind "ausmultiplizieren":
[mm](\neg x \vee \neg y \vee z) \wedge ((\neg z \vee x)\wedge(\neg z \vee y))[/mm]
Also insgesamt:
[mm](\neg x \vee \neg y \vee z) \wedge (\neg z \vee x)\wedge(\neg z \vee y)[/mm]
Nun wird für jede "oder"-Kette eine Restriktion nach den folgenden Regeln eingeführt:
- Für jede nicht-negierte Variable wird die varaible selbst als Summand auf die linke Seite geschrieben
- Für jede negierte Variable kommt (1-Variable) auf die linke Seite
- und rechs steht immer >= 1
In unserem Beispiel:
[mm](1-x) + (1-y) + z \ge 1[/mm]
[mm](1-z) + x \ge 1[/mm]
[mm](1-z) + y \ge 1[/mm]
Diese drei Restriktionen müssten es jetzt hoffentlich tun (die erste löst unser Problem von gestern und die anderen beiden addiert ergeben die Ungleichung, die ich gestern aufgeschrieben habe).
Ich hoffe Du bist jetzt nicht gleich total erschlagen, aber auf diesem Weg sollte man von jeder logischen Formel zu einer entsprechenden Formulierung für ein lineares Optimierungsproblem kommen.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:47 Mi 14.02.2007 | | Autor: | claudi1980 |
Hallo Piet, vielen Dank für Deine ausführliche Erläuterung. Und JA, ich bin total erschlagen. Ich hatte in meinem bisherigen Matheleben nur etwas mit "UND" und "Oder" oder "Teilmenge" zu tun. Alles andere habe ich noch nie in meinem Leben vorher gesehen. Aber ich denke, dass ich mich da rein arbeiten kann und dann schaffe ich es vielleicht noch die anderen logischen Verknüpfen mit binären Variablen in (Un)gleichungen zu formulieren. Ich glaube, ich muss das in meiner Arbeit noch das Öfteren machen.
Also, vielen Dank!
Wenn ich nicht weiterkomme, werde ich mich hier wieder melden.
Liebe Grüße! Claudia
|
|
|
|
