2 %> Algorithm 16.5: Two phases
simplex algorithm with tableau to solve a linear optimization problem in standard from. Implementation of algorithm 16.5 of \cite Bier15-book
4 %> @note Tested with \ref run1615.m
5 %> @note Tested with \ref run1616.m
9 %> @note Called by \ref
gomory 11 %> @author Michel Bierlaire
12 %> @date Sun Mar 22 14:25:13 2015
13 %> @ingroup Algorithms
16 %> Solve a linear optimization problem in standard form
using the tableau
simplex with two phases
17 %> \f[ \min_{x \in \mathbb{R}^n} c^T x
23 %> where \f$A\in\mathbb{R}^{m\times n}\f$, \f$ b\in\mathbb{R}^m\f$ and
24 %> \f$c\in \mathbb{R}^n\f$.
25 %> @param A the constraint matrix
26 %> @param b the constraint right hand side
27 %> @param c the cost vector
for the objective
function 28 %> @
return [x,copt,finaltableau]
29 %> @
return x the optimal solution
30 %> @
return copt the value of the objective
function 31 %> @
return finaltableau the optimal tableau
37 error(
"The number of rows in A and b do not match") ;
40 error(
"The number of columns in A and do not match the size of c") ;
43 % Make sure that b >= 0
51 % First tableau
for Phase I
52 tab = [ A eye(m,m) b ; zeros(1,n+m+1) ];
54 tab(m+1,i) = -sum(tab(1:m,i));
56 tab(m+1,n+m+1) = -sum(tab(1:m,n+m+1)) ;
58 % The basic variables are variables n+1 to n+m
59 rowindex = [n+(1:m)] ;
60 % Solve the phase I problem
71 if (opttableau(m+1,n+m+1) > sqrt(eps))
72 printf(
"Optimal cost is %e > %e. No feasible solution exists.\n",opttableau(m+1,n+m+1),sqrt(eps)) ;
83 rowstoberemoved = [] ;
84 % Remove the auxiliary variables from the basis
86 basic = any(rowindex == i) ;
88 rowpivot = find(opttableau(:,i)
') ; 92 while (colpivot < 0 && k <= n) 93 if (abs(opttableau(rowpivot,k)) > eps) 100 rowstoberemoved(end + 1) = rowpivot ; 102 opttableau = pivoting(opttableau,rowpivot,colpivot) ; 103 rowindex(rowpivot) = colpivot ; 107 % Remove the redundant constraints 108 for r = size(rowstoberemoved,2):-1:1 109 opttableau(rowstoberemoved(r),:) = [] ; 110 rowindex(rowstoberemoved(r)) = [] ; 113 finaltableau = opttableau ; 114 finaltableau(:,n+1:n+m) = [] ; 116 [m,n] = size(finaltableau) ; 122 cb(i) = c(rowindex(i)) ; 126 if (any(rowindex==i)) 127 finaltableau(m+1,i) = 0 ; 129 finaltableau(m+1,i) = c(i) - cb' * finaltableau(1:m,i) ;
132 finaltableau(m+1,n+1) = - cb
' * finaltableau(1:m,n+1) ; 137 [finaltableau,bounded,rowindex] = simplexTableau(finaltableau,rowindex) ; 140 x(rowindex(j)) = finaltableau(j,n+1) ; 142 copt = -finaltableau(m+1,n+1) ; function twoPhasesSimplex(in A, in b, in c)
Solve a linear optimization problem in standard form using the tableau simplex with two phases subje...
function simplexTableau(in tab, in rowindex)
Solve a linear optimization problem in standard form using the tableau simplex.
function gomory(in A, in b, in c)
Solve an integer optimization problem by generating valid inequalities using a Gomory cut: subject t...
function transhipment(in adj, in cost, in lb, in ub, in supply, in useGlpk)
Solve the transhipment problem with bound constraints.
function pivoting(in tab, in l, in j)
Pivot the tableau.
function simplex(in A, in b, in c, in basis)
Applies the simplex method to solve subject to and , where , , and .