| |
- Hier steht Ihnen das Simplexverfahren zur Lösung eines
linearen Problems der Form
cTx = max, Ax=b, x>=0
zur Verfügung
Das duale Problem ist
bTy = max
-c-ATy >= 0 .
Ist das primale Problem nicht zulässig, dann ist das
duale Problem unbeschränkt. Ist das primale Problem
nicht beschränkt, dann ist das duale Problem nicht
zulässig.
- 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,
der 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 <= 99 !
- 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, ob "Phase 1" vorgeschaltet werden soll.
- Phase 1 berechnet eine zulässige Ausgangsbasis,
(falls n+p <= 99 !)
und ein zulässiger Punkt existiert.
- Oder eigene Eingabe der Indexliste einer Ausgangsbasis
basis(i),i=1,..,p (integer).
Es wird dann
überprüft, ob diese zulässig ist. Ist dies nicht
der Fall, erfolgt Abbruch der Rechnung.
Wenn b>0 komponentenweise gilt und A
die Einheitsmatrix enthält, kann man
die Indizes dieser Einheitsspalten als Basis nehmen.
- Regel zur Wahl der herausgehenden Variablen :
- Maximaler Negativer Multiplikator oder
- Regel von Bland (Wichtig : Es muß eine zulässige
Ausgangsbasis bekannt sein.) Wird die Regel von Bland (kleinster-Index-Regel)
benutzt, dann gilt sie auch für die hereinkommende Variable.
- Maximale Schrittzahl maxstep
- Auswahl, ob zusätzlich das gesamte Simplextableau
ausgegeben werden soll.
|