Annotation of OpenXM_contrib/PHC/Ada/Math_Lib/Supports/dictionaries.ads, Revision 1.1
1.1 ! maekawa 1: with Standard_Floating_Numbers; use Standard_Floating_Numbers;
! 2: with Standard_Floating_Vectors; use Standard_Floating_Vectors;
! 3: with Standard_Floating_Matrices; use Standard_Floating_Matrices;
! 4: with Standard_Integer_Vectors;
! 5:
! 6: package Dictionaries is
! 7:
! 8: -- DESCRIPTION :
! 9: -- This package manages dictionaries, used to solve
! 10: -- the linear programming problem, in standard primal form
! 11: --
! 12: -- max <c,x>
! 13: -- <a,x> <= 0, m linear inequalities
! 14: --
! 15: -- where x = (1,x1,x2,..,xn);
! 16: --
! 17: -- and for the dual formulation of the problem
! 18: --
! 19: -- min <c,x>
! 20: -- <a,x> >= 0, m linear inequalities
! 21: --
! 22: -- where x = (1,x1,x2,..,xn).
! 23:
! 24: -- A dictionary is the linear system that corresponds to a feasible solution.
! 25: -- The right-hand side vector yields the primal solution, whereas the
! 26: -- vector of the objective function determines the dual solution.
! 27: -- A dictionary is reprented by a matrix of dimension (0..m,0..n) and
! 28: -- by two vectors which indicate the unknowns that are in/out the basis,
! 29: -- of respective dimensions (1..m) and (1..n).
! 30:
! 31: -- USAGE : be consequent when using primal and dual models.
! 32:
! 33: -- IMPORTANT ASSUMPTIONS :
! 34: -- The initializers do not check on the validity on the input tableau.
! 35: -- In particular:
! 36: -- * primal : all right-hand sides to be positive;
! 37: -- * dual : all coefficients of the objective function must be positive.
! 38: -- Otherwise, the claims on unboundedness and infeasibility may be false.
! 39:
! 40: -- INITIALIZERS :
! 41:
! 42: procedure Init_Basis
! 43: ( in_bas,out_bas : in out Standard_Integer_Vectors.Vector );
! 44:
! 45: -- DESCRIPTION : Initializes the basis.
! 46:
! 47: -- ON ENTRY :
! 48: -- in_bas unknowns in the basis, vector with range 1..m,
! 49: -- out_bas unknowns out the basis, vector with range 1..n.
! 50:
! 51: function Init_Primal_Dictionary
! 52: ( c : Standard_Floating_Vectors.Vector; a : Matrix )
! 53: return Matrix;
! 54:
! 55: function Init_Dual_Dictionary
! 56: ( c : Standard_Floating_Vectors.Vector; a : Matrix )
! 57: return Matrix;
! 58:
! 59: -- DESCRIPTION : Initializes the matrix for the dictionary.
! 60:
! 61: -- MATRIX DIMENSIONS : c(0..m), a(1..m,0..n).
! 62:
! 63: -- ON ENTRY :
! 64: -- c coefficients of the target function;
! 65: -- a coefficients of the constraints, stored row-wise,
! 66: -- with right-hand side at column zero.
! 67:
! 68: -- ON RETURN :
! 69: -- Matrix of dimension (0..m,0..n), with first row contains -c, the
! 70: -- rest is filled with a, or with -a in the dual case.
! 71:
! 72: procedure Primal_Init
! 73: ( c : in Standard_Floating_Vectors.Vector;
! 74: a : in Matrix; dic : out Matrix;
! 75: in_bas,out_bas : in out Standard_Integer_Vectors.Vector );
! 76:
! 77: procedure Dual_Init
! 78: ( c : in Standard_Floating_Vectors.Vector;
! 79: a : in Matrix; dic : out Matrix;
! 80: in_bas,out_bas : in out Standard_Integer_Vectors.Vector );
! 81:
! 82: -- DESCRIPTION :
! 83: -- This procedure initializes the dictionary by consecutive application
! 84: -- of the producedure Init_Basis and Init_Primal/Dual_Dictionary.
! 85:
! 86: -- ON ENTRY :
! 87: -- c the coefficients of the target function: c(0..n);
! 88: -- a the coefficients of the constraints: a(1..m,0..n).
! 89:
! 90: -- ON RETURN :
! 91: -- dic dictionary a matrix of ranges 0..m,0..n;
! 92: -- in_bas unknowns in the basis, vector with range 1..m;
! 93: -- out_bas unknowns out the basis, vector with range 1..n.
! 94:
! 95: -- MODIFIERS :
! 96:
! 97: procedure Primal_Update
! 98: ( dic : in out Matrix;
! 99: in_bas,out_bas : in out Standard_Integer_Vectors.Vector;
! 100: eps : in double_float; unbounded : out boolean );
! 101:
! 102: procedure Dual_Update
! 103: ( dic : in out Matrix;
! 104: in_bas,out_bas : in out Standard_Integer_Vectors.Vector;
! 105: eps : in double_float; feasible: out boolean );
! 106:
! 107: -- DESCRIPTION :
! 108: -- This procedure performs one step of the simplex algorithm.
! 109:
! 110: -- ON ENTRY :
! 111: -- dic current matrix for the dictionary;
! 112: -- in_bas unknowns in the basis;
! 113: -- out_bas unknowns not in the basis;
! 114: -- eps used to determine wether a number is zero.
! 115:
! 116: -- ON RETURN :
! 117: -- dic modified matrix for the dictionary;
! 118: -- in_bas updated list of basis unknowns;
! 119: -- out_bas updated list of non-basis unknowns;
! 120: -- unbounded true when the solution is unbounded, false otherwise;
! 121: -- feasible false when infeasibility is detected, true otherwise.
! 122:
! 123: -- SELECTORS :
! 124:
! 125: function Primal_Optimal ( dic : Matrix; eps : double_float ) return boolean;
! 126: function Dual_Optimal ( dic : Matrix; eps : double_float ) return boolean;
! 127:
! 128: -- DESCRIPTION :
! 129: -- Returns true if the dictionary offers an optimal solution.
! 130: -- The parameter eps is used determine whether a number equals zero or not.
! 131:
! 132: function Optimum ( dic : Matrix ) return double_float;
! 133:
! 134: -- DESCRIPTION :
! 135: -- Returns the current value of the objective function.
! 136:
! 137: function Primal_Solution
! 138: ( dic : Matrix;
! 139: in_bas,out_bas : Standard_Integer_Vectors.Vector )
! 140: return Standard_Floating_Vectors.Vector;
! 141:
! 142: function Dual_Solution
! 143: ( dic : Matrix;
! 144: in_bas,out_bas : Standard_Integer_Vectors.Vector )
! 145: return Standard_Floating_Vectors.Vector;
! 146:
! 147: -- DESCRIPTION :
! 148: -- Returns the current values of the n unknowns in the primal or the
! 149: -- dual formulation of the linear program. If the program is dual,
! 150: -- then the signs of the dual solution should be reversed.
! 151:
! 152: end Dictionaries;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to dictionaries.ads CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / PHC / Ada / Math_Lib / Supports