simplex algorithm
Summary
Simplex algorithm
TODO
Finding a feasible solution
given Ax = b
1. multiply the equations such that b>=0
2. construct an auxiliary problem, add m auxiliary variables
3. solve the auxiliary problem using the simplex algorithm
4. if z = 0, return the feasible solution to the original problem
5. else, return "infeasible"
Concept
Simplex algorithm
- finds the optimal solution given a basic feasible solution
- pick non-basic variable where the corresponding entry in the objective matrix is >0
For a feasible basis in canonical form, simplex moves between BFSs.
repeat
if every reduced cost c̄_j ≤ 0: return current BFS (optimal)
choose entering k with c̄_k > 0
if Ā_k ≤ 0: return unbounded ray
t <- min { b̄_i/Ā_ik : Ā_ik > 0 }
choose a minimizing basic index to leave; pivot
Optimality follows because
Bland’s rule
- prevent cycling in the simplex algorithm
- ensures termination
- choose the smallest element to enter and leave the basis
Simplex tableau
Finding a feasible solution
- the simplex algorithm finds the optimal solution given a feasible solution
- we first need to find a feasible solution
canonical form is insufficient, we might see a solution that is infeasible due to negative coefficients
Auxiliary problem
- add auxiliary variables to have a very obvious feasible solution
- try to reduce the auxiliary variables to 0
we want to minimize the effect that the auxiliary variables have on the problem
note: the auxiliary problem is not in SEF, we have to convert it to SEF and then to canonical form
Non-zero auxiliary variables implies infeasibility
if there is a feasible solution, this step always gives a basic solution
Two-phase simplex
- proves the fundemental theorem of LP
Phase I: minimize sum of artificial variables
if z > 0: report infeasible
extract a feasible original basis
Phase II: restore original objective and run simplex
With Bland’s rule, this proves an SEF LP is infeasible, unbounded, or has an optimal BFS. See LP outcomes.
Application
Finding a better the optimal solution
note that the new feasible solutions are all basic solutions
the -1 term does not restict
, since any value of will gaurentee
stop the algorithm, since there are no more non-basic variables with
Unbounded LP
and can be considered the certificate for the LP’s unboundedness
notice, if the column of the chosen non-basic solution is <=0, then the LP is unbounded
Finding a feasible solution
Detect infeasibility
Simplex tableau
Extra
Octave function to solve an LP using two-phase simplex
function [x, z, B, status] = simplex_lp(c, A, b)
% Solve:
% maximize c' * x
% subject to A*x = b, x >= 0
%
% status: "optimal", "infeasible", or "unbounded"
%
% Uses two-phase primal simplex with Bland's pivot rule.
% Intended for small classroom problems.
tol = 1e-9;
maxiter = 10000;
c = c(:);
b = b(:);
[m, n] = size(A);
if length(c) != n || length(b) != m
error("Dimensions of c, A, and b do not match.");
endif
if any(!isfinite(A(:))) || any(!isfinite(b)) ...
|| any(!isfinite(c))
error("Inputs must contain only finite numbers.");
endif
x = [];
z = NaN;
B = [];
% Make every RHS nonnegative.
neg = (b < 0);
A(neg, :) = -A(neg, :);
b(neg) = -b(neg);
% Phase I:
% Add artificial variables a >= 0:
% A*x + I*a = b
% Maximize -sum(a), initially using a as the basis.
Awork = [A, eye(m)];
cphase1 = [zeros(n, 1); -ones(m, 1)];
B = n + (1:m);
[B, phase_status] = simplex_pivots( ...
cphase1, Awork, b, B, tol, maxiter);
if !strcmp(phase_status, "optimal")
error("Numerical failure during Phase I.");
endif
[Ac, bc, ~, phase_value] = ...
canonical_lp(cphase1, Awork, b, B);
if phase_value < -tol
status = "infeasible";
B = [];
return;
endif
% Remove any zero-valued artificial variables still basic.
% Pivot in an original variable when possible.
% Otherwise, the transformed row is redundant.
while any(B > n)
[Ac, bc] = canonical_lp(cphase1, Awork, b, B);
r = find(B > n, 1);
if abs(bc(r)) > tol
error("Numerical failure removing artificial variables.");
endif
nonbasic = setdiff(1:n, B);
candidates = nonbasic(abs(Ac(r, nonbasic)) > tol);
if !isempty(candidates)
B(r) = candidates(1);
else
% Work with the equivalent canonical equations.
Awork = Ac;
b = bc;
Awork(r, :) = [];
b(r) = [];
B(r) = [];
endif
endwhile
% Delete all artificial-variable columns.
Awork = Awork(:, 1:n);
% Phase II: optimize the original objective.
[B, status] = simplex_pivots( ...
c, Awork, b, B, tol, maxiter);
[~, bc] = canonical_lp(c, Awork, b, B);
bc(abs(bc) < tol) = 0;
x = zeros(n, 1);
x(B) = bc;
if strcmp(status, "unbounded")
z = Inf;
else
z = c' * x;
endif
endfunction
function [B, status] = simplex_pivots(c, A, b, B, tol, maxiter)
% Primal simplex from a feasible basis.
n = columns(A);
for iteration = 1:maxiter
[Ac, bc, cc] = canonical_lp(c, A, b, B);
if any(bc < -tol)
error("The current basis is not feasible.");
endif
bc(abs(bc) < tol) = 0;
% Bland's rule: smallest-index improving variable enters.
nonbasic = setdiff(1:n, B);
improving = nonbasic(cc(nonbasic) > tol);
if isempty(improving)
status = "optimal";
return;
endif
entering = improving(1);
d = Ac(:, entering);
% x_B = bc - d*t, so only d_i > 0 limits t.
eligible = find(d > tol);
if isempty(eligible)
status = "unbounded";
return;
endif
ratios = bc(eligible) ./ d(eligible);
theta = min(ratios);
% Break minimum-ratio ties using basic-variable indices.
tied = eligible(abs(ratios - theta) <= tol);
[~, k] = min(B(tied));
leaving_row = tied(k);
B(leaving_row) = entering;
endfor
error("Iteration limit reached.");
endfunction