Dualisieren < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 08:41 Do 08.03.2007 | | Autor: | Karolin |
| Aufgabe | Dualisiere
min [mm] \summe_{i=1}^{n} \summe_{j=1}^{n} \summe_{t=1}^{x_{ij}} c_{ij}^{t}
[/mm]
[mm] \summe_{j=1}^{n} x_{ij} =r_{i} [/mm] i=1,...,n
[mm] \summe_{i=1}^{n} x_{ij} =s_{j} [/mm] j=1,...,n
[mm] x_{ij} \ge [/mm] 0 [mm] x_{ij} [/mm] ganzzahlig
[mm] x_{ij} [/mm] = falls [mm] a_{ij}=0
[/mm]
Es sei eine nichtnegative nxn Matrix [mm] A=(a_{ij}) [/mm] gegeben. [mm] (x_{ij}) [/mm] soll die gleiche Vorzeichenstruktur haben.
|
Hallo,
ich muss dieses Problem im Zusammenhang mit einem Beweis dualisieren und habe leider ein paar Probleme damit.
Also ich denke, dass das duale Problem zwei Variablen [mm] \alpha_{i} [/mm] und [mm] \beta_{j} [/mm] hat wegen der Restriktionen im Primalen. Diese Variablen müssten ja unbeschränkt sein, da es sich im Primalen um Gleichheitsrestriktionen handelt.
Da [mm] x_{ij} [/mm] vorzeichenbeschränkt ist, erhält man im Dualen Ungleichheitsrestriktionen.
Ich denke, dass die Zielfunktion im Dualen so aussieht:
max [mm] \summe_{i=1}^{n}\alpha_{i}r_{i} [/mm] + [mm] \summe_{j=1}^{n}\beta_{j}s_{j}
[/mm]
Mit den Restriktionen habe ich jetzt allerdings Schwierigkeiten.
Es wäre schön, wenn mir da jemand weiterhelfen könnte.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Do 15.03.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
