LP-Simplex 2 Phasen Algorithmus minimize_lp
English text
(15)
\text\small\blue{LP minimization \mathbb{LP_{min}} works analogously to LP maximization, but\\
in the opposite direction of the gradient. This results in the following changes:\\
\underline{Optimality test}: All coefficients of the objective function \mathbb{Z}_{min} ≤ 0\\
\underline{Pivot column}: largest entry in \mathbb{Z_{min}} }
(18)
\text\small\blue{As in Max-LP, set the slack variable to -1 for NB equal to or greater than.\\
For equations, remove the slack variable \to 0\\
Phase 1:\\Search for a feasible basic solution using the simplex algorithm and an auxiliary objective function.\\
Block entry after slack variables and before b variables }
(21)
\text\small\blue{Setting up the initial simplex table. In each row where we subtract a slack variable, we additionally add an auxiliary variable.}
(23)
\text\small\blue{Replacing the objective function Z with the column sum of all auxiliary variables \to Z'}
(25)
\text\small\blue{By adding all lines containing an auxiliary variable to the target function line,
we set all entries of the auxiliary variables in the target function line to zero:
Z'=Load(Start)+Z'\times Start\\
Pivot selection is made manually based on the quotient Qb2 \to b/pivot column.}
(35)
\text\small\blue{The initial problem now has a basic solution.\\
Remove the data from the auxiliary variables.\\
In the second phase, the optimal target value is determined using the simplex table.}
(37)
\text\small\blue{Protocol for basis change \{base columns\},\{row pivot, column pivot\}\\
The pivot \{z,s\} describes a basis change \\
\to Column s enters the basis, column z leaves the basis. \\
\to Transform Z, Z is expressed by basis variables x1 and x2\\
\to A_2 receives the new Z = Z+A_1(1)Z(1)+A_1(2)Z(2)}:\
("\text\small\blue{https://statmath.wu.ac.at/~leydold/MOK/HTML/node164.html}")
Example x1,x2,x3,x4
https://www.mikrocontroller.net/attachment/156858/SimplexMeFile_2012-10-08_19-55.pdf
Phase1: A_{11}...A_{18}
A_1
"\text\small\blue{Protokoll der Basiswechsel \{Basisspalten\},\{ZeilenPivot,Spaltenpivot\}\\Der Pivot \{z1,s1\} beschreibt einen Basiwechsel \to Spalte s1 geht in die Basis, Spalte z1 verlässt die Basis. \\Der zweite Basiswechsel \{7,1\} löscht den Basiseintrag\\Damit bleibt in Zeile 6/Spalte 4 nur x4 in der Phase2 Basis \to A_2 erhält die neue Z = Z+A_1(6)Z(4)}:\\"
BasisPhase2:={{5, 8, 7, 10, 9, 4, 0}, {2, 8}, {5, 12, 7, 10, 9, 4, 0}, {7, 1}, {5, 12, 7, 10, 9, 4, 3}, {4, 10}, {5, 12, 7, 10, 9, 4, 3}, {4, 10}, {5, 12, 7, 13, 9, 4, 3}, {6, 4}, {5, 12, 7, 13, 9, 4, 3}, {6, 4}, {5, 12, 7, 13, 9, 2, 3}, {35, 36}, {6, 2}, {5, 12, 7, 13, 9, 14, 1}, {7, 1}} {Basiswechsel}, {Pivot}-Folge abarbeiten von rechts nach links.
Matrix Functions
| https://sagecell.sagemath.org/?q=bxgkkw | https://sagecell.sagemath.org/?q=ohjkyg/td] |
| Die Ausstattung zur Matrizen-Behandlung ist sehr schwach ausgeprägt. Es gibt keine Spalten-Werkzeuge. Um Spalten zu bearbeiten muss die Matrix transponiert werden: Element() Take() First() Last() können dann Zeilen barbeiten die mit Join() Append() wieder zusammen gebaut werden. Die bearbeiteten Zeilen werden nach einer Rück-Transponierung wieder zu Spalten" | The features for matrix processing are very limited. There are no column tools. To edit columns, the matrix must be transposed: Element() Take() First() Last() can then edit rows that are reassembled with Join() Append(). After transposing back, the edited rows become columns again. |