Annotation of OpenXM_contrib/PHC/Ada/Math_Lib/Supports/dictionaries.ads, Revision 1.1.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>