SimplexTwoPhase Routine

Summary

Linear optimization by Two-Phase Simplex algorithm.

Declaration

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

Description

Solves the following optimization problem:

where relholds the relation signs. For example, relation string '<=>' means the constraints system consists of one inequality '<=', one equation '=' and one inequality '>='.

See Also
SimplexDual
SimplexLP

Example 1

Solve the following LP problem:

    f(x) = x1+x2+2*x3-2*x4

    subject to:

    x1+2x      <= 700
    2x2-8x4    <= 0
    x2-2x3+x4   > 1
    x1+x2+x3+x4 = 1

which translates to using two-phase simplex method:

    Uses MtxExpr, Optimization, Math387;

    procedure Example;
    var A, AF: Matrix;
      b,c,indexes,x:  Vector;
      sol: TLPSolution;
      f: TSample:
    begin
      A.SetIt(4,4,false,[1,1,0,0
                         0,2,0,-8,
                         0,1,-2,1,
                         1,1,1,1]);
      b.SetIt(false,[700,0,1,1]);
      c.SetIt(false,[1,1,2,-2]);
      f := SimplexTwoPhase(A,b,c,'<<>=',AF,x,indexes,sol,true,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(4,3,false, OPENARRAY(TSample,(1,1,0,0
                         0,2,0,-8,
                         0,1,-2,1,
                         1,1,1,1)));
      b->SetIt(OPENARRAY(TSample,(700,0,1,1)));
      c->SetIt(OPENARRAY(TSample,(1,1,2,-2)));
      // Find minimum using above system
      TSample f = SimplexTwoPhase(A,b,c,"<<>=",Af,x,indexes,sol,true,NULL);
    }

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

    namespace Dew.Examples
    {
      private void Example()
      {
        Matrix A = new Matrix(0,0);
        Matrix AFinal = new Matrix(0,0);
        Vector b = new Vector(0);
        Vector c = new Vector(0);
        Vector x = new Vector(0);
        Vector indexes = new Vector(0);
        TLPSolution sol;
        A.SetIt(4,3,false,new double[] {1,1,0,0
                         0,2,0,-8,
                         0,1,-2,1,
                         1,1,1,1});
        b.SetIt(new double[] {700,0,1,1});
        c.SetIt(new double[] {1,1,2,-2});
        string relations = "<<>=";
        double f = Optimization.SimplexTwoPhase(A,b,c,relations,AFinal,x,indexes, out sol, true,null);
      }
    }