2 %> Algorithm 16.2: Simplex methos. Implementation of algorithm 16.2 of \cite Bier15-book
4 %> @note Tested with \ref run1604simplex.m
5 %> @note Tested with \ref run1607simplex.m
7 %> @author Michel Bierlaire
8 %> @date Sun Mar 22 11:50:34 2015
12 %> Applies the
simplex method to solve \f$\min_x c^Tx\f$ subject to \f$Ax=b\f$ and \f$x \geq 0\f$ , where \f$A \in \mathbb{R}^{m\times n}\f$, \f$b \in \mathbb{R}^m\f$, and \f$c \in \mathbb{R}^n\f$.
13 %> @param A the constraint matrix
14 %> @param b the constraint right hand side
15 %> @param c the cost vector
for the objective
function 16 %> @param basis indices of the basic variables of a feasible basic solution
17 %> @
return [solution,optvalue]
18 %> @
return solution: an optimal solution
19 %> @
return optvalue: the value of the objective
function at the optimal solution
20 function [optimalbasis,unbounded] =
simplex(A,b,c,basis)
23 error(
"The number of rows in A and b do not match") ;
26 error(
"The number of columns in A and do not match the size of c") ;
30 printf(
"%d\t",basis) ;
33 reducedCost = c
' - c(basis)' * d;
35 nonbasic = setdiff(1:n,basis) ;
36 printf(
"%g\t",reducedCost(nonbasic)) ;
37 candidates = find(reducedCost < 0) ;
38 if (isempty(candidates))
39 optimalbasis = basis ;
45 xfull = zeros(size(c)) ;
48 printf(
"%g\t",xfull) ;
50 printf(
"%f\t",-d(:,p)) ;
54 if d(k,p) > 0 && step > 0
55 aStep = xb(k) / d(k,p) ;
63 optimalbasis = zeros(m,1) ;
69 printf(
"|%d\t%d",p,basis(q));
70 printf(
"|%f\n",c(basis)
'*xb) ; function simplex(in A, in b, in c, in basis)
Applies the simplex method to solve subject to and , where , , and .