www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenOperations Researchzulässiges/ unbeschr. Problem
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Operations Research" - zulässiges/ unbeschr. Problem
zulässiges/ unbeschr. Problem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

zulässiges/ unbeschr. Problem: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:44 Do 12.04.2018
Autor: Noya

Aufgabe
$ min [mm] \{ x_1+x_2 : ax_1+x_2 \le 4, 1\le x_1 \le 3, 1\le x_2 \le 3 \} [/mm]
(a) Für welche Werte von a [mm] \in \IR [/mm] ist das Problem unzulässig oder unbeschränkt?

(b) Berechnen Sie Optimalmenge und Optimalwert in Abhängigkeit von a.

Hallo ihr Lieben,

ich komme nicht so recht hier voran.
Meine Lösungsmenge ist ja das Quadrat mit den EP (1,1),(1,3),(3,3),(3,1) und darein muss dann noch die Resktriktion : [mm] a*x_1 [/mm] + [mm] x_2 \le [/mm] 4
[mm] \gdw x_2 \le 4-a*x_1 [/mm]
betrachte ich für [mm] 1\le x_1 \le [/mm] 3 fktwerte von [mm] x_2 [/mm]
für [mm] x_1=1 [/mm] : [mm] x_2 [/mm] = 4-a  (A)
für [mm] x_1=2 [/mm] : [mm] x_2 [/mm] = 4-2a (B)
für [mm] x_1=3 [/mm] : [mm] x_2 [/mm] = 4-3a (C)
dabei ist zusätzlich wichtig, dass [mm] 1\le x_2 \le [/mm] 3, also für
A : [mm] 1\le x_2 [/mm] = 4-a  [mm] \le [/mm] 3 [mm] \gdw [/mm] 1 [mm] \le a\le [/mm] 3
B: [mm] 1\le x_2 [/mm] = 4-2a  [mm] \le [/mm] 3 [mm] \gdw \bruch{1}{2} \le [/mm] a [mm] \le \bruch{3}{2} [/mm]
C: [mm] 1\le x_2 [/mm] = 4-3a  [mm] \le [/mm] 3 [mm] \gdw \bruch{1}{3} \le [/mm] a [mm] \le [/mm] 1
heit für mich für alle [mm] a\in \IR \setminu[\bruch{1}{3},3] [/mm] ist das problem unzulässig oder?

Es wäre super wenn ihr mir hier mal helfen könntet.

Schönen Abend noch
Noya


        
Bezug
zulässiges/ unbeschr. Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 09:56 Fr 13.04.2018
Autor: Diophant

Hallo,

> $ min [mm]\{ x_1+x_2 : ax_1+x_2 \le 4, 1\le x_1 \le 3, 1\le x_2 \le 3 \}[/mm]

>

> (a) Für welche Werte von a [mm]\in \IR[/mm] ist das Problem
> unzulässig oder unbeschränkt?

>

> (b) Berechnen Sie Optimalmenge und Optimalwert in
> Abhängigkeit von a.
> Hallo ihr Lieben,

>

> ich komme nicht so recht hier voran.
> Meine Lösungsmenge ist ja das Quadrat mit den EP
> (1,1),(1,3),(3,3),(3,1) und darein muss dann noch die
> Resktriktion : [mm]a*x_1[/mm] + [mm]x_2 \le[/mm] 4
> [mm]\gdw x_2 \le 4-a*x_1[/mm]

Das ist zwar etwas unglücklich formuliert, aber von der Grundüberlegung her richtig.

> betrachte ich für [mm]1\le x_1 \le[/mm] 3
> fktwerte von [mm]x_2[/mm]
> für [mm]x_1=1[/mm] : [mm]x_2[/mm] = 4-a (A)
> für [mm]x_1=2[/mm] : [mm]x_2[/mm] = 4-2a (B)
> für [mm]x_1=3[/mm] : [mm]x_2[/mm] = 4-3a (C)

Warum betrachtest du hier ganzzahlige x-Werte, es ist ja wohl kein diskretes Problem?

> dabei ist zusätzlich wichtig, dass [mm]1\le x_2 \le[/mm] 3, also
> für
> A : [mm]1\le x_2[/mm] = 4-a [mm]\le[/mm] 3 [mm]\gdw[/mm] 1 [mm]\le a\le[/mm] 3
> B: [mm]1\le x_2[/mm] = 4-2a [mm]\le[/mm] 3 [mm]\gdw \bruch{1}{2} \le[/mm] a [mm]\le \bruch{3}{2}[/mm]

>

> C: [mm]1\le x_2[/mm] = 4-3a [mm]\le[/mm] 3 [mm]\gdw \bruch{1}{3} \le[/mm] a [mm]\le[/mm] 1
> heit für mich für alle [mm]a\in \IR \setminu[\bruch{1}{3},3][/mm]
> ist das problem unzulässig oder?

Es ist genau andersherum. Liegt a in dem von dir ermittelten Intervall, dann ist die durch die Restriktionen vorgegebene Menge nichtleer. Für a=3 besteht sie aus dem Punkt (1,1), für kleinere a entsteht ein Simplex, für a=1/3 ist es schließlich das ganze Quadrat. Außerdem darf a auch kleiner als 1/3 werden, das bedeutet ja letztendlich nur, dass dann die Restriktion [mm] ax_1+x_2 \le{4} [/mm] in jedem Fall erfüllt ist.

Zeichne es dir in einem Koordinatensystem auf!


Gruß, Diophant

Bezug
                
Bezug
zulässiges/ unbeschr. Problem: Nachtrag
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:31 Fr 13.04.2018
Autor: Diophant

Hallo,

ok, da hast du bei dem Intervall für a einen Tippfehler, deshalb wird das falsch angezeigt. Das war mir heute morgen entgangen.

Also was a>3 angeht, da hat du recht. Aber wie gesagt, a<1/3 sollte kein Problem sein. Die zugehörigen Geraden verlaufen oberhalb des Quadrats. Und da sich sowieso alles innerhalb und auf dem Rand des Quadrats 'abspielt', stellt das kein Problem dar, weil es ja eine [mm]\le[/mm]-Restriktion ist.


Gruß, Diophant

Bezug
                
Bezug
zulässiges/ unbeschr. Problem: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:52 Fr 13.04.2018
Autor: Noya

Danke schonmal.
also ich habe das jetzt nochmal gezeichnet.
sobald a [mm] \in [\bruch{1}{3},3] [/mm] schneidet die restriktion [mm] a*x_1+x_2 \le4 [/mm] das oben beschriebene Quadrat. andernfalls liegt es außerhalb. Was genau bedeutet das dann?
Ich habe einfach noch nicht so ganz raus, wann das Problem unzulässig /unbeschränkt ist. Kannst du mir das eventuell genauer erklären?

ja hab da anscheinend vergessen was zu schreiben. Vom Gefühl her würde ich sagen das Problem ist zulässig für a [mm] \in [\bruch{1}{3},3] [/mm] und somit unzulässig für a [mm] \in \IR\setminus [\bruch{1}{3},3]. [/mm]




Bezug
                        
Bezug
zulässiges/ unbeschr. Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:57 Fr 13.04.2018
Autor: Diophant

Hallo,

> Ich habe einfach noch nicht so ganz raus, wann das Problem
> unzulässig /unbeschränkt ist. Kannst du mir das eventuell
> genauer erklären?

jetzt habe ich keine Zeit mehr (vielleicht kann ja jemand anderes übernehmen?). Aber du könntest nochmals klären, ob das hier wirklich ein Minimierungsproblem ist. Denn wenn man sich die Richtung der Zielfunktion so anschaut, dann interessiert es die Lösung überhaupt nicht, wie groß a ist, so lange wie gesagt [mm] a\le{3} [/mm] gilt.

Das würde ganz anders aussehen (und mehr Sinn ergeben), wenn es um eine Maximierung ginge.


Gruß, Diophant

Bezug
                                
Bezug
zulässiges/ unbeschr. Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:32 Fr 13.04.2018
Autor: Noya

Trotzdem schon mal vielen Dank.
Nein es ist ganz sicher, laut Aufgabenstellung, ein Minimierungsproblem. Habe extra nochmal nachgeschaut.

hab mir das nochmal angeguckt.Optimalpunkt für Min.prob ist ja nunmal (1,1), dann wäre der Zielfunktionswert z=2 in allen anderen möglichen Ecken deutlich größer. heißt die restriktion spielt ja so oder so keine wirkliche Rolle,oder?

Bezug
                        
Bezug
zulässiges/ unbeschr. Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 17:26 Fr 13.04.2018
Autor: Diophant

Hallo,

jetzt ist doch nochmal ein Zeitfenster aufgegangen. :-)

Also schauen wir mal:

> also ich habe das jetzt nochmal gezeichnet.
> sobald a [mm]\in [\bruch{1}{3},3][/mm] schneidet die restriktion
> [mm]a*x_1+x_2 \le4[/mm] das oben beschriebene Quadrat.

Das ist soweit richtig, wie gesagt. Es entsteht dabei ein Simplex mit drei bis fünf Ecken, je nach Lage der Restriktion.

> andernfalls
> liegt es außerhalb. Was genau bedeutet das dann?

Der gültige Bereich für Lösungen eines LP ist stets die Schnittmenge aller Restriktionen.

Wenn a>3 ist, dann verläuft die fragliche Restriktion unterhalb des Quadrats und die Schnittmenge ist somit leer.

Für den Fall [mm]1/3\le{a}\le{3}[/mm] gilt, was du geschrieben hast.

Für den Fall a<1/3 jedoch ist die Schnittmenge einfach das komplette Quadrat.

> Ich habe einfach noch nicht so ganz raus, wann das Problem
> unzulässig /unbeschränkt ist.

Unzulässig ist es, wenn die Schnittmenge der Restriktionen leer ist. Unbeschränkt, wenn es kein Maximum bzw. Minimum gibt. So lange man Positivität voraussetzt, wird ein Minimierungsproblem niemals unbeschränkt sein, bei  Maximierungsproblemen dagegen kann das auftreten. Dann bilden die Restriktionen kein Simplex, sondern ein ins Unendliche reichendes Gebiet.

> Kannst du mir das eventuell
> genauer erklären?

>

Also wenn das wirklich ein Minimierungsproblem ist, dann ist die Sache sehr einfach.

Für a>3 haben wir ein unzulässiges Problem, wie gesagt.

Jetzt schauen wir uns einmal die Zielfunktion etwas näher an:

[mm] x_1+x_2=c\ \gdw\ x_2=c-x_1 [/mm]

Graphisch gesehen verläuft die Zielfunktion also auf jeden Fall parallel zur 2. Winkelhalbierenden. Wenn wir uns nun überlegen, wie weit wir die Zielfunktion nach unten verschieben können, so dass sie mit dem zulässigen Gebiet noch mindestens einen gemeinsamen Punkt hat, dann sieht man sofort, dass das Minimum durch den Punkt (1,1) gegeben ist, und zwar wie gesagt unabhängig vom Wert von a, solange [mm] a\le{3}. [/mm]

Zusammengefasst:

- a>3: kein zulässiges Problem
- alle anderen a: eindeutiges Minimum 1+1=2.


Gruß, Diophant

Bezug
                                
Bezug
zulässiges/ unbeschr. Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 17:38 Fr 13.04.2018
Autor: Noya

Super!!! Vielen vielen lieben Dank!!! :)


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]