‣ Cdd_LinearProgram( P, str, obj ) | ( operation ) |
Returns: a CddLinearProgram Object
The function takes three variables. The first is a polyhedron poly, the second str should be "max" or "min" and the third obj is the objective function.
‣ Cdd_SolveLinearProgram( lp ) | ( operation ) |
Returns: a list if the program is optimal, otherwise returns the value 0
The function takes a linear program. If the program is optimal, the function returns a list of two entries, the solution vector and the optimal value of the objective, otherwise it returns fail.
To illustrate the using of these functions, let us solve the linear program given by:
\[\textbf{Maximize}\;\;P(x,y)= 1-2x+5y,\;\mathrm{with}\]
\[100\leq x \leq 200,80\leq y\leq 170,y \geq -x+200.\]
We bring the inequalities to the form \(b+AX\geq 0\) and get:
\[-100+x\geq 0, 200-x \geq 0, -80+y \geq 0, 170 -y \geq 0,-200 +x+y \geq 0.\]
gap> A:= Cdd_PolyhedronByInequalities( [ [ -100, 1, 0 ], [ 200, -1, 0 ], > [ -80, 0, 1 ], [ 170, 0, -1 ], [ -200, 1, 1 ] ] ); <Polyhedron given by its H-representation> gap> lp1:= Cdd_LinearProgram( A, "max", [1, -2, 5 ] ); <Linear program> gap> Display( lp1 ); Linear program given by: H-representation begin 5 X 3 rational -100 1 0 200 -1 0 -80 0 1 170 0 -1 -200 1 1 end max [ 1, -2, 5 ] gap> Cdd_SolveLinearProgram( lp1 ); [ [ 100, 170 ], 651 ] gap> lp2:= Cdd_LinearProgram( A, "min", [ 1, -2, 5 ] ); <Linear program> gap> Display( lp2 ); Linear program given by: H-representation begin 5 X 3 rational -100 1 0 200 -1 0 -80 0 1 170 0 -1 -200 1 1 end min [ 1, -2, 5 ] gap> Cdd_SolveLinearProgram( lp2 ); [ [ 200, 80 ], 1 ] gap> B:= Cdd_V_Rep( A ); <Polyhedron given by its V-representation> gap> Display( B ); V-representation begin 5 X 3 rational 1 100 170 1 100 100 1 120 80 1 200 80 1 200 170 end
So the optimal solution for \(\texttt{lp1}\) is \((x=100,y=170)\) with optimal value \(p=1-2(100)+5(170)=651\) and for \(\texttt{lp2}\) is \((x=200,y=80)\) with optimal value \(p=1-2(200)+5(80)=1\).
generated by GAPDoc2HTML