Optimization: principles and algorithms, by Michel Bierlaire
simplex.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 16.2: Simplex methos. Implementation of algorithm 16.2 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run1604simplex.m
5 %> @note Tested with \ref run1607simplex.m
6 %>
7 %> @author Michel Bierlaire
8 %> @date Sun Mar 22 11:50:34 2015
9 %> @ingroup Algorithms
10 %> @ingroup chap16
11
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)
21  [m,n] = size(A) ;
22  if (m != size(b))
23  error("The number of rows in A and b do not match") ;
24  endif
25  if (n != size(c))
26  error("The number of columns in A and do not match the size of c") ;
27  endif
28  stop = 0 ;
29  while (stop == 0)
30  printf("%d\t",basis) ;
31  B = A(:,basis) ;
32  d = B \ A ;
33  reducedCost = c' - c(basis)' * d;
34  printf("|") ;
35  nonbasic = setdiff(1:n,basis) ;
36  printf("%g\t",reducedCost(nonbasic)) ;
37  candidates = find(reducedCost < 0) ;
38  if (isempty(candidates))
39  optimalbasis = basis ;
40  unbounded = 0 ;
41  stop = 1 ;
42  else
43  p = candidates(1) ;
44  xb = B \ b ;
45  xfull = zeros(size(c)) ;
46  xfull(basis) = xb ;
47  printf("|") ;
48  printf("%g\t",xfull) ;
49  printf("|") ;
50  printf("%f\t",-d(:,p)) ;
51  step = realmax ;
52  q = -1 ;
53  for k=1:m
54  if d(k,p) > 0 && step > 0
55  aStep = xb(k) / d(k,p) ;
56  if (aStep < step)
57  step = aStep ;
58  q = k ;
59  endif
60  endif
61  endfor
62  if (q == -1)
63  optimalbasis = zeros(m,1) ;
64  unbounded = 1 ;
65  stop = 1 ;
66  else
67  printf("|") ;
68  printf("%f\t",step) ;
69  printf("|%d\t%d",p,basis(q));
70  printf("|%f\n",c(basis)'*xb) ;
71  basis(q) = p ;
72  endif
73  endif
74  printf("\n") ;
75  endwhile
76 endfunction
77
function simplex(in A, in b, in c, in basis)
Applies the simplex method to solve subject to and , where , , and .
Copyright 2015-2016 Michel Bierlaire