minimum in maximumoptimierung umwandeln

27.10.2011, 18:55

ONeil

minimum in maximumoptimierung umwandeln

Meine Frage:
Hallo an alle,

ich hab ein kleines Probelem.
Als Ausgangspunkt haben wir ein Lineares Optimierungsproblem. Dieses ist ein Minimumproblem, welches man in ein Maximumproblem umwandeln muss.
Nun stellt sich die Frage wie.
Durch google habe ich gefunden, dass man anscheinend nur die Zielfunktion * (-1) nehmen muss.
Meiner Meinung nach ist das ein bisschen zu einfach, oder täusche ich mich da?

Beispielsweise diese:

| 8x1 + 0x2 ? 40
|| 0x1 + 4x2 ? 16
||| 4x1 + 4x2 ? 36
R x1 + 2x2 = 0

ist dann diese in maximum?:

| 8x1 + 0x2 ? 40
|| 0x1 + 4x2 ? 16
||| 4x1 + 4x2 ? 36
R -x1 - 2x2 = 0

Vielen Dank für Hilfe,

ONeil

Meine Ideen:

Beispielsweise diese:

| 8x1 + 0x2 ? 40
|| 0x1 + 4x2 ? 16
||| 4x1 + 4x2 ? 36
R x1 + 2x2 = 0

ist dann diese in maximum?:

| 8x1 + 0x2 ? 40
|| 0x1 + 4x2 ? 16
||| 4x1 + 4x2 ? 36
R -x1 - 2x2 = 0

Vielen Dank für Hilfe,

ONeil

27.10.2011, 19:32

mnt

Auf diesen Beitrag antworten »

RE: minimum in maximumoptimierung umwandeln
Hi,

Deine Beispiele verstehe ich leider nicht. Was ist ? und was die Zielfunktion...

Zitat:

Original von ONeil
ich hab ein kleines Probelem.
Als Ausgangspunkt haben wir ein Lineares Optimierungsproblem. Dieses ist ein Minimumproblem, welches man in ein Maximumproblem umwandeln muss.
Nun stellt sich die Frage wie.
Durch google habe ich gefunden, dass man anscheinend nur die Zielfunktion * (-1) nehmen muss.
Meiner Meinung nach ist das ein bisschen zu einfach, oder täusche ich mich da?

Aber so einfach ist es doch schon. Beim Minimiumproblem ist folgendes gegeben:

Zielfunktion: f(x) -> min
und Nebenbedingungen.

Betrachtet man nun -f anstatt f, dann muss man -f maximieren, also
Zielfunktion -f(x) -> max
und die Nebenbedingungen bleiben genau gleich.

Gehs doch mal bei diesem Beispiel durch:
f(x) = 2*x+3 (hier ist x eine Variable, oben ein Vektor)
Nebenbedingungen:
x >= 1
x <= 2

VG

27.10.2011, 19:50

ONeil

Auf diesen Beitrag antworten »

sorry, ka wrums ned anzeigt,

aber in der ersten Formel sind die Fragezeichen alle =>
in der zweiten formel alle <=

27.10.2011, 19:52

ONeil

Auf diesen Beitrag antworten »

okey danke smile

27.10.2011, 20:03

ONeil

Auf diesen Beitrag antworten »

dann hätte ich gleich nochmal ne frage falls sich wer gut in Linearer Optimierung auskennt.

Ich habe das Maximumproblem gegeben:

8 0 | 1 0 0 | 40
0 4 | 0 1 0 | 16
4 4 | 0 0 1 | 36

1 2 | 0 0 0 | 0

Die oberen sind die Einschränkungen, die unterste Zeile die Zielfunktion.

die 3., 4. und 5. Spalte sind die Schlupfvariablen
1. und 2. Spalte die 'normalen' Variablen.
die letzte Spalte die Werte, die bei den jeweiligen Funktionen raus kam.

Nun meine Frage:

ich habe eine Bild datei hochgeladen

und wollte wissen ob ich da die ganzen dinge richtig benannt hab.
Also ob ich für die allgemein formulierten xB bzw. xN und die ganzen anderen richtig eingesetzt habe.

Vielen Dank im voraus smile

ONeil

PS: Falls ich zum besseren Verständnis noch mehr angeben muss, bitte sagen

27.10.2011, 20:05

ONeil

Auf diesen Beitrag antworten »

sorry nachgeliefert des pic:

http://ul.to/uxnama93

27.10.2011, 20:23

ONeil

Auf diesen Beitrag antworten »

oder hier nochmal direkt:

[attach]21644[/attach]

hoffe es klappt..

30.10.2011, 13:49

mnt

Auf diesen Beitrag antworten »

Hi,

Sorry, dass es so lange gedauert hat, aber ich hatte Probleme mit den Cookies...

Beim nächsten Mal fang bitte für jede neue Frage ein neues Thema an.
Außerdem ist es für Helfer viel angenehmer, wenn du deine Formel hier ins Forum schreibst und nicht in ein Bild (wegen Copy+Paste), und schreib bitte x_1 anstatt x1.

Zum Beginn: Zielfunktion: Hast du die abgeschrieben? Beim Überfliegen sieht das schlüssig aus. Bei mir ist das schon eine Weile her...

Zur Rechnung:
Die stimmt leider nicht. $\begin{eqnarray*} c^T x \end{eqnarray*}$ ist doch eine Zahl in R (wie sollte man sonst auch maxi-/minimieren?). Bei dir kommt aber ein Vektor heraus...

30.10.2011, 13:50

mnt

Auf diesen Beitrag antworten »

Berechne $\begin{eqnarray*} \Phi \end{eqnarray*}$ und $\begin{eqnarray*} s_N \end{eqnarray*}$ mit der Formel von oben.

31.10.2011, 10:13

ONeil

Auf diesen Beitrag antworten »

Danke jetzt weiß ich wie was eingeben muss smile

ja die Formel hab ich aus einem Buch abgeschrieben und sollte auch richtig sein.
mir geht es hauptsächlich darum ob ich von der gegebenen Aufgabe alles richtig eingegeben habe, anscheinend ja nicht.
ja ich weiß dass ich so $\begin{eqnarray*} \Phi \end{eqnarray*}$ und $\begin{eqnarray*} s_N \end{eqnarray*}$ berechnen kann aber ich bin mir nicht ganz sicher was $\begin{eqnarray*} c_B \end{eqnarray*}$ und $\begin{eqnarray*} c_N \end{eqnarray*}$ auf meine aufgabe bezogen ist. $\begin{eqnarray*} c_B \end{eqnarray*}$ und $\begin{eqnarray*} c_N \end{eqnarray*}$ sind ja normal 'Basis und Nichtbasislösungen'
Kann es sein, dass $\begin{eqnarray*} c_B \end{eqnarray*}$ die variablen $\begin{eqnarray*} x_3 \end{eqnarray*}$ , $\begin{eqnarray*} x_4 \end{eqnarray*}$ und $\begin{eqnarray*} x_5 \end{eqnarray*}$ sind? also 0, 0 und 0 in der Zielfunktion?
und $\begin{eqnarray*} c_N \end{eqnarray*}$ dann im Umkehrschluss die variablen $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ mit 1 und 2?

also die aufgabe nochmal:

8 0 | 1 0 0 | 40
0 4 | 0 1 0 | 16
4 4 | 0 0 1 | 36

1 2 | 0 0 0 | 0

31.10.2011, 15:57

mnt

Auf diesen Beitrag antworten »

Du möchtest also nur $\begin{eqnarray*} c^T x \end{eqnarray*}$ aufschreiben?

Zitat:

Kann es sein, dass $\begin{eqnarray*} c_B \end{eqnarray*}$ die variablen $\begin{eqnarray*} x_3 \end{eqnarray*}$ , $\begin{eqnarray*} x_4 \end{eqnarray*}$ und $\begin{eqnarray*} x_5 \end{eqnarray*}$ sind? also 0, 0 und 0 in der Zielfunktion?
und $\begin{eqnarray*} c_N \end{eqnarray*}$ dann im Umkehrschluss die variablen $\begin{eqnarray*} x_1 \end{eqnarray*}$ und $\begin{eqnarray*} x_2 \end{eqnarray*}$ mit 1 und 2?

Ja das stimmt so. Allerdings bin ich mir nicht sicher, ob c_N oder c_B der Nullvektor ist (also der Teil der Schlupfvariablen)...

Die Umformung von $\begin{eqnarray*} c^T x \end{eqnarray*}$ soll zeigen, dass man im Prinzip eine Funktion mit (i.A.) weniger als n Unbekannten hat (nämlich nur Anz. der Komponenten von x_N).

31.10.2011, 16:52

ONeil

Auf diesen Beitrag antworten »

ja genau ich will nur $\begin{eqnarray*} c^T x \end{eqnarray*}$ aufschreiben smile

also ich habs jetzt mal so gemacht:

[attach]21709[/attach]

kann leider keine vektoren und matizen schreiben drum hab ich wieder ein pic angehängt.

der erste Vektor (0 0 0) ist von den Schlupfvariablen, die ja die 'Basislösung' sind.

(1 2) Vektor kommt von der Zielfunktionszeile, die 'Nichtbasislösung'

ist schon richtig oder?

31.10.2011, 18:04

mnt

Auf diesen Beitrag antworten »

Es fällt doch einiges weg, so dass x_1 + 2*x_2 stehen bleibt.

01.11.2011, 11:42

ONeil

Auf diesen Beitrag antworten »

ja genau

ich wollte nur erstmal alles in diese Formel schreiben, weil es so gewünscht war
Danke für deine Hilfe mnt smile

01.11.2011, 11:54

mnt

Auf diesen Beitrag antworten »