Optimization: principles and algorithms, by Michel Bierlaire
simplexTableau.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 16.4: Phase II simplex algorithm with tableau. Implementation of algorithm 16.4 of \cite Bier15-book
3 %>
4 %> @note Tested with \ref run1613.m
5 %> @note Calls \ref pivoting
6 %> @note Called by \ref twoPhasesSimplex
7 %>
8 %> @author Michel Bierlaire
9 %> @date Sun Mar 22 12:52:25 2015
10 %> @ingroup Algorithms
11 %> @ingroup chap16
12
13 %> Solve a linear optimization problem in standard form using the tableau simplex
14 %> @param tab the first simplex tableau
15 %> @param rowindex: for each row, index of the corresponding basic variables
16 %> @return opttableau the optimal tableau
17 function [opttableau,bounded,rowindex] = simplexTableau(tab,rowindex)
18
19  [mtab,ntab] = size(tab) ;
20  m=mtab-1 ;
21  n=ntab-1 ;
22  while (true)
23  colpivot = -1 ;
24  i = 1 ;
25  cfirstneg = eps ;
26  while (i <= n )
27  if tab(m+1,i) < -eps
28  cfirstneg = tab(m+1,i) ;
29  colpivot = i ;
30  i = n + 1 ;
31  endif
32  i = i + 1 ;
33  end
34  if (cfirstneg >= -eps)
35  opttableau = tab ;
36  bounded = 1 ;
37  return ;
38  endif
39  bestlambda = 1000000 ;
40  rowpivot = -1 ;
41  for i=1:m
42  if (tab(i,colpivot) > 0)
43  lambda = tab(i,n+1) / tab(i,colpivot) ;
44  if (lambda < bestlambda)
45  bestlambda = lambda ;
46  rowpivot = i ;
47  endif
48  endif
49  endfor
50  if (rowpivot == -1)
51  printf("**** Unbounded problem ****\n") ;
52  bounded = 0 ;
53  return
54  endif
55  tab = pivoting(tab,rowpivot,colpivot) ;
56  rowindex(rowpivot) = colpivot ;
57  endwhile
58
59 endfunction
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 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 .