Ganzzahlige lin. Optimierung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Seien A eine ganzzahlige, vollständig unimodulare Matrix, b und c ganzzahlige Vektoren (Dimensionen passend). Zeigen Sie: Die beiden linearen Programme:
[mm] \max \left \{c^Tx:Ax\leq b\right \} = \min \left \{y^Tb:y\geq 0, y^tA= c^T\right \} [/mm]
haben ganzzahlige Lösungen, falls die Optima endlich sind. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich weiß aus einem Satz, dass der Polyeder zu einer vollständig unimodularen Matrix und einem ganzzahligen Vektor b
[mm] \left \{x: Ax\leq b \right \} [/mm]
ganzzahlig ist und das die Behauptung mit der vollständigen Unimodularität von
[mm]
\begin{bmatrix}
-I\\
A^T\\
-A^T
\end{bmatrix}
[/mm]
folgt. Aber wieso?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Di 09.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
