linprog.doc

线性规划工具箱-performing the standard two phase simplex method on linear programming problems.具体介绍里面有

function [zmax,PHIiter,PHIIiter,xbasic,ibasic]=linprog(A,b,c);
%
%Written for MATLAB version 5.0
%
%LINPROG uses the two phase simplex method to solve the linear 
%program maximize cx subject to the constraints Ax = b and x >= 0 , 
%where A is m x n , rank(A) = m , and b >= 0 .    The output vector 
%is [zmax,PHIiter,PHIIiter,xbasic,ibasic], where zmax is the maximal 
%objective value, PHIiter and PHIIiter are the phase I and phase II 
%iteration counts, respectively, where xbasic is the vector of basic 
%x variables at optimality, and where ibasic is the set of indices of  
%the optimal basis columns in A (and hence the indices for the entries 
%in xbasic).  LINPROG detects infeasibility and unboundedness, and
%provides appropriate output messages in such cases.  LINPROG also
%contains a heuristic check for cycling, terminating the algorithm
%when m Phase II iterations occur without a change in the objective 
%value.  See also PHASEI and PHASEII.
%
%Written by Jeff Stuart, Department of Mathematics,
%University of Southern Mississippi, Hattiesburg, MS 39406.
%December 1993. Revised, October, 1997.
[e-mail]
%
[m,n]=size(A);
if max(size(b) ~=[m 1]);  %TEST THAT b IS THE CORRECT SIZE 
   disp('The dimensions of b do not match the dimensions of A.')
   break
end   
if min(b) < 0;  %TEST THAT b IS NONNEGATIVE   
   disp('The RHS vector b must be nonnegative.')
   break
end   
if max(size(c) ~=[1 n]);   %TEST THAT c IS THE CORRECT SIZE
   disp('The dimensions of c do not match the dimensions of A.')
   break
end
if rank(A) ~=m;   %TEST THAT A HAS FULL ROW RANK    
   disp('A does not have full row rank.')
   break
end
f=flops;           %INITIALIZE FLOP COUNTER
t=cputime;         %INITIALIZE CPU CLOCK 
PHIiter=0;         %SET PHASE I ITERATIONS TO ZERO    
PHIIiter=0;        %SET PHASE II ITERATIONS TO ZERO 
tol=0.0000000001;  %SET TOLERANCE FOR (IN)FEASIBILITY CHECK (see PHASEI.M)
xbasic=zeros(1,n); %INITIALIZE STORAGE VECTOR FOR BASIC VARIABLES
[wmax,ibasic,PHIiter]=phasei(A,b);  %RUN PHASE I
if wmax < -tol ;   %TEST PHASE I OUTPUT FOR INFEASIBILITY
     f=flops -f;   %NET FLOPS  
     t=cputime -t; %NET CPU TIME
     disp('The original LP is infeasible.  Infeasibility was')
     disp('detected during Phase I.  The total number of phase')
     disp('one iterations performed was: '), disp(PHIiter)
     disp('The total flops required was: '),disp(f)
     disp('The required cpu time was: '),disp(t)
else;  %BRANCH HERE FOR PHASE I FEASIBLE
     disp('Phase I completed.  Original LP is feasible.')
     disp('The total number of Phase I iterations was: '),disp(PHIiter)
     disp('Starting Phase II.')  %RUN PHASE II
 [zmax,xbasic,ibasic,ienter,PHIIiter,PCOL,OPTEST,CYCTEST]=phaseii(A,b,c,ibasic);
     xbasic=xbasic'; %VECTOR OF BASIC VARIABLE VALUES AT END OF PHASE II
     f=flops - f;    %NET FLOPS
     t=cputime -t;   %NET CPU TIME
     if CYCTEST==1;  %TEST PHASE II OUTPUT FOR CYCLING 
        break        %IF CYCLING DETECTED, STOP
     end   
     if OPTEST == 0; %TEST PHASE II OUTPUT FOR UNBOUNDEDNESS
          disp('The orginal LP is unbounded. An unbounded ray was')
          disp('detected during Phase II.  The output objective')
          disp('value is for the last basic solution found.')
          disp('The number of Phase II iterations was: '),disp(PHIIiter)
          disp('Last objective value is '),disp(zmax)
          disp('The last basic solution, xbasic is '),disp(xbasic)
          disp('The column indices for the last basis: '),disp(ibasic)
          disp('The index of the unbounded entering variable: '),disp(ienter)
          disp('The unbounded ray column is: '),disp(PCOL)
          disp('The total number of flops required was: '),disp(f)
          disp('The required cpu time was: '),disp(t)
     else    %BRANCH HERE IF PHASE II IS NOT UNBOUNDED (THEREFORE OPTIMAL) 
          disp('The original LP has an optimal solution.')
          disp('The number of Phase II iterations was: '),disp(PHIIiter)
          disp('The optimal objective value is '),disp(zmax)
          disp('The indices for the basic columns: '),disp(ibasic)
          disp('The optimal, basic solution is '),disp(xbasic)
          disp('The total number of flops required was: '),disp(f)
          disp('The required cpu time was: '),disp(t)
     end
end