Solve a linear program with Simplex. Illustrate the need for scaling.
------------------------------------------------------------------------
See also Simplex, SimplexScaling
------------------------------------------------------------------------
Contents
load the example problem data (a,b,c,nSlack)
load SimplexScalingDemoData.mat
disp('=================================================')
disp('Loaded mat-file "SimplexScalingDemoData.mat"...');
disp('Calling Simplex with original (a,b,c) matrices.')
disp('-> NOTE: This problem is poorly scaled, and will')
disp(' therefore result in warnings within the')
disp(' simplex method during matrix inversion.')
disp(' The resulting solution will not satisfy')
disp(' the constraint a*u=b.')
disp('================================================')
disp(' ');
=================================================
Loaded mat-file "SimplexScalingDemoData.mat"...
Calling Simplex with original (a,b,c) matrices.
-> NOTE: This problem is poorly scaled, and will
therefore result in warnings within the
simplex method during matrix inversion.
The resulting solution will not satisfy
the constraint a*u=b.
================================================
first call Simplex without scaling
tic
x = Simplex( c, a, b );
fprintf('Run time without scaling: %f sec\n',toc)
fprintf('Error without scaling: %f\n\n',norm(a*x-b))
disp('================================================')
disp('Now we scale the columns of the "a" matrix that');
disp('correspond to the slack variables. ');
disp('Calling Simplex again with (a2,b,c).');
disp('Now, the simplex method runs faster and achieves');
disp('a solution that DOES satisfy a*u=b.');
disp('================================================');
disp(' ');
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate.
RCOND = 2.872511e-17.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate.
RCOND = 1.239089e-20.
Warning: Matrix is close to singular or badly scaled. Results may be inaccurate.
RCOND = 3.694128e-20.
Run time without scaling: 0.096692 sec
Error without scaling: 47.142500
================================================
Now we scale the columns of the "a" matrix that
correspond to the slack variables.
Calling Simplex again with (a2,b,c).
Now, the simplex method runs faster and achieves
a solution that DOES satisfy a*u=b.
================================================
now scale and try again
tic
[a2,anorm] = SimplexScaling(a,b,nSlack);
[x2,flag] = Simplex( c, a2, b );
fprintf('Run time WITH scaling: %f sec\n',toc)
fprintf('Error WITH scaling: %f\n\n',norm(a2*x2-b))
Run time WITH scaling: 0.027132 sec
Error WITH scaling: 0.000000