| |
- Hier soll ein lineares Problem der Form
cTx = max, Ax=b, x>=0
gelöst werden.
- Dieses Programm rechnet mit der Methode der dualen affinen Skalierung,
entweder mit dem dualen oder dem dualen erweiterten Problem.
Also
bTy = max, -c-ATy >= 0
bzw.
bTy-big*yp+1 = max ,
-c-AT+e*yp+1 >= 0 , e=(1,...,1)T
yp+1 >= 0 .
Ist der Penalisierungsfaktor "big" gross genug gewählt
(nämlich >= ||x*||1 )
und das primale Problem beschränkt
und zulässig, dann wird die Schlupfvariable yp+1=0 im Optimum.
Ist das primale Problem unbeschränkt, dann ist das
duale Problem unzulässig und es wird yp+1 > 0 .
- Das Verfahren korrigiert iterativ die duale Lösung y gemäss
- vk = -c -AT yk
- Dk = diag( vk1,...,vkn)
- (A*Dk-2*AT) hk = b
lösen
- dk = -AThk
- gamma = alpha * min{ -vik/dik: dik <0 }
- yk+1 = yk + gamma*hk
- Nach erfolgreicher Lösung des dualen Problems wird dann noch
die Lösung des primalen Problems aus den Optimalitätsbedingungen
berechnet. Dies im Falle des erweiterten Problems nur, wenn die Schlupfvariable
kleiner als
sqrt(tiny)=sqrt(2.2d-16*(sum{ |Ai,j|}+sum{|bi|} +p(1+big))
ist.
- Es gibt verschiedene Eingabeformen für die
Koeffizienten c(i) sowie die Einträge in die
Matrix A und den Vektor b. Falls die
Matrix vollbesetzt ist, ist die übliche
zeilenweise Eingabe sinnvoll. Für den Fall
einer schwachbesetzten Matrix gibt es die Möglichkeit,
die Nicht-Null-Elemente zusammen mit den entsprechenden Indizes
anzugeben. Hierzu gibt es verschiedene Eingabeseiten,
um die Seiten übersichtlich zu halten.
|
| |
- Zuerst muß ein Identifizierungstext eingegeben werden,
welcher später mit ausgegeben wird.
- Die Dimension des Unbekannten-Vektors n
(n = dim(x) = dim(c))
Wichtig : 1 <= n <= 99 !
- Die Anzahl der Gleichungsrestriktionen p
(p = dim(b) = Anzahl Zeilen von A)
Wichtig : 1 <= p <= n !
- Es gibt zwei verschiedene Eingabeformen für die
Matrix und die Vektoren:
- Vollbesetzte Matrix :
Direkte Vektoreingabe des Koeffizientenvektors c.
Zeilenweise Eingabe der Matrix A=(a(i,j)) mit dem jeweiligen
Wert b(i) pro Zeile. Das heißt konkret:
a(i,1),...,a(i,n),b(i),
also n+1 Einträge pro Zeile.
- Schwachbesetzte Matrix :
Indexweise Eingabe der Nicht-Null-Elemente der Matrix wie auch der Vektoren.
Konkret : index, wert, also i, c(i) oder i, b(i)
bzw. index1, index2, wert, also i, j, a(i,j)
(Die restlichen Elemente sind mit Null vorinitialisiert.)
Wichtig : Immer nur ein Index-Wert-Tupel pro Zeile !
- Auswahl:
- Standardparameter: alpha=0.5, epsc=1.d-10, rho=1.1d-16,
maxstep=100 oder
- Eingabe der Parameter: alpha, epsc, rho, maxstep
alpha ist oben benutzter Schrittlängenreduktionsfaktor und muss < 2/3
bleiben. Das Verfahren bricht ab, wenn die duale Zielfunktion sich relativ um
weniger als epsc unterscheidet. 1/rho ist eine obere Schranke für
die Kondition des Diagonalteils der QR-Zerlegung von DkAT.
Die QR-Zerlegung dieser Matrix (ihr Dreiecksteil) dient zur Lösung des
Gleichungssystems in Schritt 3. maxstep ist die maximal zulässige
Schrittzahl.
- Soll das Problem um eine Variable erweitert werden,
so daß ein zulässiger innerer Punkt
direkt angebbar ist ?
- Wenn ja,
muß noch der reelle Parameter big
für die Penalisierung der Schlupfvariablen angegeben werden.
(big sollte größer als ||x*||1 sein, sonst wird nicht das Originalproblem
mitgelöst).
- Wenn nein,
Standardstartwert (als Standard wird der Startwert auf
-c gesetzt)
oder eigene Angabe des dualen Startwertes y(1),...,y(p)
mit - c - A'y > 0 (Der Wert wird auf Zulässigkeit geprüft.)
- Die Anzahl der zu protokollierenden dualen Variablen
|