LP in Standardform < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:42 Di 20.10.2009 | | Autor: | Elfe |
| Aufgabe | Schreiben Sie die folgende Problemformulierung als LP in Standardform:
max [mm] 2x_{1} [/mm] - [mm] x_{2} [/mm] + [mm] 3x_{3}
[/mm]
s.d.
[mm] 4x_{1} [/mm] + [mm] x_{2} [/mm] = 2
[mm] x_{2} [/mm] - [mm] 3x_{3} \ge [/mm] 1
[mm] 5x_{1} [/mm] + [mm] x_{3} \le [/mm] 3
[mm] x_{1}, x_{2} \ge [/mm] 0
[mm] x_{3} \in \IR [/mm] |
Hallo, also ich habe das LP in Standardform umgeformt, nämlich:
- min [mm] -2x_{1} [/mm] + [mm] x_{2} [/mm] - [mm] 3x^{+}_{3} [/mm] + [mm] 3x^{-}_{3}
[/mm]
s.d.
[mm] 4x_{1} [/mm] + [mm] x_{2} [/mm] = 2
[mm] x_{2} [/mm] - [mm] 3x^{+}_{3} [/mm] + [mm] 3x^{-}_{3} -x_{4} [/mm] = 1
[mm] 5x_{1} [/mm] + [mm] x^{+}_{3} [/mm] - [mm] x^{-}_{3} [/mm] + [mm] x_{5} [/mm] = 3
[mm] x_{1}, x_{2}, x^{+}_{3}, x^{-}_{3}, x_{4}, x_{5} \ge [/mm] 0
Dann bin ich mir aber nicht sicher, wie ich das [mm] x^{+}_{3} [/mm] und das [mm] x^{-}_{3} [/mm] richtig einbringe in der Matrix etc.
Ist es richtig, dass ich die beiden einfach wie weitere Variablen wie [mm] x_{4} [/mm] und [mm] x_{5} [/mm] betrachte, also
der Kostenvektor
c = (-2, 1, -3, 3, 0, 0)
die Matrix
A = [mm] \pmat{ 4 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & -3 & 3 & -1 & 0 \\ 5 & 0 & 1 & -1 & 0 & 1}
[/mm]
und
b= [mm] \vektor{2 \\ 1 \\ 3}
[/mm]
Ist das so richtig oder muss ich was anders machen, wenn [mm] x_{3} [/mm] nicht vorzeichenbeschränkt ist?
Danke schonmal!
Elfe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:37 Di 20.10.2009 | | Autor: | koepper |
Hallo,
> Schreiben Sie die folgende Problemformulierung als LP in
> Standardform:
>
> max [mm]2x_{1}[/mm] - [mm]x_{2}[/mm] + [mm]3x_{3}[/mm]
>
> s.d.
>
> [mm]4x_{1}[/mm] + [mm]x_{2}[/mm] = 2
>
> [mm]x_{2}[/mm] - [mm]3x_{3} \ge[/mm] 1
>
> [mm]5x_{1}[/mm] + [mm]x_{3} \le[/mm] 3
>
> [mm]x_{1}, x_{2} \ge[/mm] 0
>
> [mm]x_{3} \in \IR[/mm]
> Hallo, also ich habe das LP in Standardform
> umgeformt, nämlich:
>
> - min [mm]-2x_{1}[/mm] + [mm]x_{2}[/mm] - [mm]3x^{+}_{3}[/mm] + [mm]3x^{-}_{3}[/mm]
>
> s.d.
>
> [mm]4x_{1}[/mm] + [mm]x_{2}[/mm] = 2
>
> [mm]x_{2}[/mm] - [mm]3x^{+}_{3}[/mm] + [mm]3x^{-}_{3} -x_{4}[/mm] = 1
>
> [mm]5x_{1}[/mm] + [mm]x^{+}_{3}[/mm] - [mm]x^{-}_{3}[/mm] + [mm]x_{5}[/mm] = 3
>
> [mm]x_{1}, x_{2}, x^{+}_{3}, x^{-}_{3}, x_{4}, x_{5} \ge[/mm] 0
>
> Dann bin ich mir aber nicht sicher, wie ich das [mm]x^{+}_{3}[/mm]
> und das [mm]x^{-}_{3}[/mm] richtig einbringe in der Matrix etc.
> Ist es richtig, dass ich die beiden einfach wie weitere
> Variablen wie [mm]x_{4}[/mm] und [mm]x_{5}[/mm] betrachte, also
>
> der Kostenvektor
> c = (-2, 1, -3, 3, 0, 0)
>
> die Matrix
> A = [mm]\pmat{ 4 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & -3 & 3 & -1 & 0 \\ 5 & 0 & 1 & -1 & 0 & 1}[/mm]
>
> und
> b= [mm]\vektor{2 \\ 1 \\ 3}[/mm]
>
>
> Ist das so richtig oder muss ich was anders machen, wenn
> [mm]x_{3}[/mm] nicht vorzeichenbeschränkt ist?
nein, das ist so alles OK.
Die Frage ist allenfalls, ob du in der Gleichungsrestriktion noch eine künstliche Variable (ohne Vorzeichenbeschränkung) hinzufügen willst.
Alternativ kannst du die Gleichung natürlich auch einfach nach einer Variablen auflösen und die damit aus den anderen Gleichungen heraussubstituieren.
Aber eines davon wirst du tun müssen, weil du sonst im Simplex-Verfahren nicht ohne weiteres zu einer initialen Basis kommst.
LG
Will
|
|
|
|
