SimplexDual Routine

Summary

Linear optimization by Dual Simplex algorithm.

Declaration

Function SimplexDual(A: TMtx; b, c: TVec; AFinal: TMtx; x: TVec; Indexes: TVec; out SolutionType: TLPSolution; Minimize: boolean = true; Verbose: TStrings = nil): TSample;

Parameter	Description
A	Defines initial values for A*x>=b relation.
c	Defines values in f=c(T)*x equation.
b	Defines initial values for A*x>=b relation.
AFinal	Returns the final tableaux.
x	Returns values of the legitimate variables (optimal solution).
Indexes	Returns indices (in IValues) of the basic variables in AFinal tableu.
Minimize	If false, find minimum of the objective function f. If false, find maximum of the objective function f.
SolutionType	Returns type of LP solution.
Verbose	If assigned, each tableu and row/column pivoting is logged to Verbose.

Result

Value of the objective function, evaluated at minimum or maximum.

Description

Solves the following optimization problem:

Components of the vector b are not required to satisfy the nonnegativity constraints. The Dual Simplex Algorithm has numerous applications to other problems of linear programming. It is used, for instance, in some implementations of the Gomory's cutting plane algorithm for solving the integer programming problems.

See Also
SimplexTwoPhase

Example 1

Solve linear programming problem with 3 equations and 4 positive constraints.

    Uses Optimization, MtxExpr, Math387;

    procedure Example
    var A,Af: Matrix;
      b,c,x,indexes: Vector;
      f: TSample;
      sol: TLPSolution;
    begin
      A.SetIt(3,4,false,[2,1,5,0,1,2,3,0,1,1,1,1]);
      b.SetIt(false,[20,25,10]);
      c.SetIt(false,[1,2,3,-1]);
      // Find maximum using above system
      f := SimplexDual(A,b,c,Af,x,indexes,sol,false,nil);
    end;

    #include "MtxVecCpp.h" //MtxVecCPP.cpp must be included in the project
    #include "Math387.hpp"
    #include "Optimization.hpp"
    void __fastcall Example;
    {
      Matrix A,Af;
      Vector b,c,x,indexes;
      TLPSolution sol;
      A->SetIt(3,4,false, OPENARRAY(TSample,(2,1,5,0,1,2,3,0,1,1,1,1)));
      b->SetIt(OPENARRAY(TSample,(20,25,10)));
      c->SetIt(OPENARRAY(TSample,(1,2,3,-1)));
      // Find maximum using above system
      TSample f = SimplexDual(A,b,c,Af,x,indexes,sol, false, NULL);
    }

    using Dew.Math.Units;
    using Dew.Math;

    namespace Dew.Examples
    {
      private void Example()
      {
        Matrix A=new Matrix(0,0);
        Matrix Af=new Matrix(0,0);
        Vector b = new Vector(0);
        Vector c = new Vector(0);
        Vector x = new Vector(0);
        Vector iondexes = new Vector(0);
        TLPSolution sol;
        A.SetIt(3,4,false, new double[] {2,1,5,0,1,2,3,0,1,1,1,1});
        b.SetIt(new double[] {20,25,10});
        c.SetIt(new double[] {1,2,3,-1});
        // Find maximum using above system
        double f = Optimization.SimplexDual(A,b,c,Af,x,indexes, out sol, false, null);
      }
    }