function SimplexDual(const A: TMtx; const b: TVec; const c: TVec; const AFinal: TMtx; const X: TVec; const Indexes: TVecInt; out SolutionType: TLPSolution; Minimize: Boolean; const Verbose: TStrings): Double;
Linear optimization by the Dual Simplex algorithm, A*x >= b.
| # | Name | Description |
|---|---|---|
| 1 | A | Constraint matrix of the A*x >= b relation |
| 2 | A.Rows = number of constraints (m), A.Cols = number of variables (n). | |
| 3 | b | Right-hand side vector of A*x >= b (length m) |
| 4 | any sign. | |
| 5 | c | Cost vector in f = c^T x (length n) |
| 6 | c >= 0 when minimizing, c <= 0 when maximizing. | |
| 7 | AFinal | Returns the final simplex tableau. |
| 8 | X | Returns the optimal values of the decision variables (length n). |
| 9 | Indexes | Returns the indices of the basic variables in AFinal. |
| 10 | SolutionType | Returns the class of the LP solution. |
| 11 | Minimize | If true (the default) minimize f, otherwise maximize f. |
| 12 | Verbose | If assigned, each tableau and pivot is logged |
| 13 | a [see | Dew.Math.TOptControl] allows interruption/monitoring. |
Returns: Double
Solves the linear programming problem
min (max) f(x)=c^Tx subject to A x >= b, x >= 0,
where the components of b may have any sign. The dual simplex method starts from the dual feasible origin, which requires c >= 0 when minimizing and c <= 0 when maximizing; an exception is raised otherwise. Under this condition a feasible problem is always bounded. For any other combination of relations or cost signs use Optimization.SimplexTwoPhase.
Returns f = c^T x at the optimum, the optimal point in X (length A.Cols), the indices of the basic variables in Indexes, the final simplex tableau in AFinal and the solution class in SolutionType:
LPFiniteSolution: the optimum was found.
LPEmptyFeasableRegion: no point satisfies the constraint system; X is set to zero and NAN is returned.
An exception is raised if c.Length differs from A.Cols, if b.Length differs from A.Rows, if the start is not dual feasible, or if the internal iteration limit is exceeded. The computation runs in the precision of A. Any combination of A.Rows and A.Cols is supported.
Optionally, you can also assign a TOptControl object to the Verbose parameter. This allows the optimization procedure to be interrupted from another thread and optionally also allows logging and iteration count monitoring.
Uses MtxExpr, MtxExprInt, Optimization, Math387;
procedure Example;
var A, AF: Matrix;
b, c, x: Vector;
indexes: VectorInt;
sol: TLPSolution;
f: double;
begin
A.SetIt(3,2,false,[2,1,
1,3,
1,1]);
b.SetIt(false,[10,15,6]);
c.SetIt(false,[4,3]);
f := SimplexDual(A,b,c,AF,x,indexes,sol,true,nil);
// f = 24, x = (3, 4)
end;