ganzzahlige Optimallösung eines linearen Programms

11.11.2013, 13:11	mathemäuschen	Auf diesen Beitrag antworten »
ganzzahlige Optimallösung eines linearen Programms Meine Frage: Hallo Leute! Ich komme bei folgender Aufgabe nicht weiter. Es ist zu zeigen, dass das lineare Programm $\begin{eqnarray} max \sum_{j=1}^{n} \sum_{\substack{i=1 \\ i\neq j}}^{n} c_{i,j} x_{i,j} \end{eqnarray}$ s.t. $\begin{eqnarray} \sum_{\substack{i=1 \\ i\neq j}}^{n} x_{i,j} - \sum_{\substack{i=1 \\ i\neq j}}^{n} x_{j,i}=0 \end{eqnarray}$ wobei $\begin{eqnarray} l_{i,j} \geq x_{i,j} \geq 0 \end{eqnarray}$ , $\begin{eqnarray} i=1,...,n; j=1,...,n \end{eqnarray}$ . $\begin{eqnarray} l_{i,j} \end{eqnarray}$ positiv ganzzahlig. immer eine ganzzahlige optimale Lösung besitzt. Tipp: Total Unimodularität. Meine Ideen: Es gibt drei Möglichkeiten bzgl. der Lösbarkeit eines LPs: 1. LP ist unzulässig 2. LP ist unbeschränkt 3. LP besitzt eine Optimallösung 1. trifft offensichtlich nicht zu, da das LP keine sich widersprechenden Ungleichungen besitzt und z.B. die 0 eine zulässige Lösung ist. 2. ist auch nicht der Fall, da die $\begin{eqnarray} x_{i,j} \end{eqnarray}$ durch die $\begin{eqnarray} l_{i,j} \end{eqnarray}$ beschränkt sind. Somit besitzt das LP auf jeden Fall eine Optimallösung. Jetzt ist zu zeigen, dass diese ganzzahlig ist. Aber wie? Der Tipp mit der totalen Unimodularität hilft mir auch nicht wirklich weiter. Vielen Dank für eure Hilfe! LG $\begin{eqnarray} \end{eqnarray}$
13.11.2013, 17:39	Margarita90	Auf diesen Beitrag antworten »
RE: ganzzahlige Optimallösung eines linearen Programms doch, tut er! versuch mal, diese ganzen Nebenbedingungen als Matrix darzustellen, sodass Ax=0 deine Nebenbedingungen sind. Dank zeigst du, dass A unimodular ist. Ist bestimmt nicht so schwer...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »