LP-Simplex 2 Phasen Algorithmus minimize_lp
History
minimize_lp(11*x1+8*x2,[ 2*x1+x2>=12, x1+2*x2>=12, x1+x2>=10, 3*x1+4*x2<=60 ]), nonegative_lp=true;";
(10) set X to Variables
(11) set Tablo Constraints and Ojective=0 as equations
(19) copy Tab to StdTab and
set Objectiv (-1) Z (make Z coefficient negative)
set in >= constraints rows (-1) slack variable, a constraints equation set slack variable = 0
(29) refer A11
Absolute largest coefficient in Z' (before last row) defines the pivot column
Calculate b/(pivot column) Qb2(Tableau, pivot column) -> Smallest value defines the pivot row
....
stop if all columns of additional variables in Z' (before last row) = -1 -> EndPhase1 matrix
(36) set EndPhase1 matrix to Aij phase1 ending (A14)
(39) refer A1
go ahead with standard simplex algorithm -> all coefficients of Z are negativ -> stop
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 rows containing an auxiliary variable to the objective function row\\
we set all entries of the auxiliary variables in the objective function row to zero:\\
Z'=Load(Start)+Z'\times Start \to penultimate row of A_{11}\\
\to last row original Z to notation of the basis change\\
Pivot selection is done manually after 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.}
(38)
\text\small\blue{Protocol for basis change\{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_1 receives the new Z from the last row of the matrix EndPhase1:
("\text\small\blue{https://statmath.wu.ac.at/~leydold/MOK/HTML/node164.html}")
Matrix Functions
| 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. |
Examples
https://www.mikrocontroller.net/attachment/156858/SimplexMeFile_2012-10-08_19-55.pdf
minimize_lp(
39*x1+21*x2+82*x3+55*x4,[
2*x1+50*x2+6*x3+74*x4<=60,
2*x1+50*x2+6*x3+74*x4>=54,
1*x1+75*x2+13*x3+96*x4<=80,
1*x1+75*x2+13*x3+96*x4>=39,
5*x1+83*x2+5*x3+105*x4<=90,
5*x1+83*x2+5*x3+105*x4>=24,
x1+x2+x3+x4=1
]),numer;
Tablo:={ 2*x1+50*x2+6*x3+74*x4=60, 2*x1+50*x2+6*x3+74*x4=54, 1*x1+75*x2+13*x3+96*x4=80, 1*x1+75*x2+13*x3+96*x4=39, 5*x1+83*x2+5*x3+105*x4=90, 5*x1+83*x2+5*x3+105*x4=24, x1+x2+x3+x4=1,39*x1+21*x2+82*x3+55*x4=0}
Phase1: A_{11}...A_{18}
BasisPhase1:={5, 12, 7, 13, 9, 14, 15}
BasisPhase2:={{5, 12, 7, 13, 9, 14, 1}{7,1}1,{5, 12, 7, 13, 9, 2, 1}{6,2}2,{5, 12, 7, 13, 9, 2, 3}{7,3}3,{5, 12, 7, 13, 9, 4, 3}{6,4}4,{5, 12, 7, 10, 9, 4, 3}{4,10}5,{5, 12, 7, 10, 9, 4, 0}{7,1}6,{5, 8, 7, 10, 9, 4, 0}{2,8}7}
{Basiswechsel}{Pivot}-Folge
\text\small\blue{Protokoll der Basiswechsel \{Basisspalten\},\{ZeilenPivot,Spaltenpivot\}\\
Der Pivot \{z,s\} beschreibt einen Basiwechsel \to Spalte s geht in die Basis, Spalte z verlässt die Basis. \\
Der zweite Basiswechsel \{7,1\} löscht den Basiseintrag \{5, 12, 7, 10, 9, 4, 0\} für Spalte 1\\
Phase2: A_1 {7,2} ... A_2
IL:={{0}, {0.8333333333336}, {0}, {0.1666666666662}}
----
minimize_lp(
2*x1-5*x2+x3,
[2*x1+x2<=100,
-x1+2*x2+2*x3<=90,
x1+x2-x3>=60,
x1+4*x3=44
]), nonegative_lp=true, numer;
Tablo:={2*x1+x2=100, -x1+2*x2+2*x3=90, x1+x2-x3=60, x1+4*x3=44,2*x1-5*x2+x3=0}
Phase1: A_{11}...A_{15}
BasisPhase1:={4, 5, 8, 9}
BasisPhase2:={ {4, 5, 8, 3},{4, 3}1,{4, 5, 8, 1},{4, 1}2,{2, 5, 8, 1},{1, 2}3,{2, 5, 3, 1},{3, 3}4 }
Phase2: A_1 {2,6} ... A_2
IL:={{24}, {52}, {5}}
| https://sagecell.sagemath.org/?q=ohjkyg | https://sagecell.sagemath.org/?q=bxgkkw |