Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/nconvex/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 28.11.2024 mit Größe 25 kB image not shown  

Quelle  chap6.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/pkg/nconvex/doc/chap6.html


<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (NConvex) - Chapter 6: Polyhedrons</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap6"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap5.html">[Previous Chapter]</a>    <a href="chap7.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap6_mj.html">[MathJax on]</a></p>
<p><a id="X85633D87813F12B0" name="X85633D87813F12B0"></a></p>
<div class="ChapSects"><a href="chap6.html#X85633D87813F12B0">6 <span class="Heading">Polyhedrons</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7C1A095983C57A83">6.1 <span class="Heading">Creating polyhedron</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X83EF304B85ED4C5B">6.1-1 PolyhedronByInequalities</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X842F90887840D3B9">6.1-2 Polyhedron</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X861DE99B8007A4C4">6.1-3 Polyhedron</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X78BCB2888114F56F">6.1-4 Polyhedron</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7A8ECB9B8542EDFF">6.1-5 Polyhedron</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7C701DBF7BAE649A">6.2 <span class="Heading">Attributes</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7ECCE0E480D88952">6.2-1 ExternalCddPolyhedron</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7C7CC5497FC52B67">6.2-2 ExternalNmzPolyhedron</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X842632AB7A09A820">6.2-3 DefiningInequalities</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X87375C8586090666">6.2-4 MainRatPolytope</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7A16114A7FFB3309">6.2-5 MainPolytope</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7A3FB56D7E895535">6.2-6 VerticesOfMainRatPolytope</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X8697AC27862160FE">6.2-7 VerticesOfMainPolytope</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7C248476851AEB4A">6.2-8 TailCone</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7DB9524D7C1A5361">6.2-9 RayGeneratorsOfTailCone</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X79351A698787C5CA">6.2-10 LatticePointsGenerators</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7B57BEAF78559D12">6.2-11 BasisOfLinealitySpace</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X81435DD28524EEE8">6.2-12 FVector</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X871597447BB998A1">6.3 <span class="Heading">Properties</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7B25E29378AF4489">6.3-1 IsBounded</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7B8DDCE685798D9C">6.3-2 IsPointed</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X819F85537D5D9D15">6.4 <span class="Heading">Solving Linear programs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X879BD74A7F6327B2">6.4-1 SolveLinearProgram</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X7F4FE0C883B8AA50">6.4-2 SolveLinearProgram</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X84237872798DB501">6.5 <span class="Heading">ZSolve</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap6.html#X81CA403280755A9B">6.5-1 SolveEqualitiesAndInequalitiesOverIntergers</a></span>
</div></div>
</div>

<h3>6 <span class="Heading">Polyhedrons</span></h3>

<p><a id="X7C1A095983C57A83" name="X7C1A095983C57A83"></a></p>

<h4>6.1 <span class="Heading">Creating polyhedron</span></h4>

<p><a id="X83EF304B85ED4C5B" name="X83EF304B85ED4C5B"></a></p>

<h5>6.1-1 PolyhedronByInequalities</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PolyhedronByInequalities</code>( <var class="Arg">L</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a <code class="code">Polyhedron</code> Object</p>

<p>The function takes a list of lists <code class="code">L</code><span class="Math">:=[L_1, L_2, ...]</span> where each <span class="Math">L_j</span> represents an inequality and returns the polyhedron defined by them. For example the <span class="Math">j</span>'th entry L_j = [c_j,a_{j1},a_{j2},...,a_{jn}] corresponds to the inequality c_j+\sum_{i=1}^n a_{ji}x_i \geq 0.



<p><a id="X842F90887840D3B9" name="X842F90887840D3B9"></a></p>

<h5>6.1-2 Polyhedron</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Polyhedron</code>( <var class="Arg">P</var>, <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a <code class="code">Polyhedron</code> Object</p>

<p>The input is a polytope <code class="code">P</code> and a cone <code class="code">C</code>. The output is the polyhedron defined by the Minkowski sum <code class="code">P+C</code>.</p>

<p><a id="X861DE99B8007A4C4" name="X861DE99B8007A4C4"></a></p>

<h5>6.1-3 Polyhedron</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Polyhedron</code>( <var class="Arg">L</var>, <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a <code class="code">Polyhedron</code> Object</p>

<p>The input is a list <code class="code">L</code> and a cone <code class="code">C</code>. The output is the polyhedron defined by the Minkowski sum <code class="code">P+C</code> where <code class="code">P</code> is the polytope, i.e., the convex hull, defined by the points <code class="code">L</code>.</p>

<p><a id="X78BCB2888114F56F" name="X78BCB2888114F56F"></a></p>

<h5>6.1-4 Polyhedron</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Polyhedron</code>( <var class="Arg">P</var>, <var class="Arg">L</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a <code class="code">Polyhedron</code> Object</p>

<p>The input is a polytope <code class="code">P</code> and a list <code class="code">L</code>. The output is the polyhedron defined by the Minkowski sum <code class="code">P+C</code> where <code class="code">C</code> is the cone defined by the rays <code class="code">L</code>.</p>

<p><a id="X7A8ECB9B8542EDFF" name="X7A8ECB9B8542EDFF"></a></p>

<h5>6.1-5 Polyhedron</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Polyhedron</code>( <var class="Arg">P</var>, <var class="Arg">C</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a <code class="code">Polyhedron</code> Object</p>

<p>The input is a list <code class="code">P</code> and a list <code class="code">C</code>. The output is the polyhedron defined by the Minkowski sum of the polytope defined by <code class="code">P</code> and the cone defined by <code class="code">C</code>.</p>

<p><a id="X7C701DBF7BAE649A" name="X7C701DBF7BAE649A"></a></p>

<h4>6.2 <span class="Heading">Attributes</span></h4>

<p><a id="X7ECCE0E480D88952" name="X7ECCE0E480D88952"></a></p>

<h5>6.2-1 ExternalCddPolyhedron</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExternalCddPolyhedron</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: cdd Object</p>

<p>Converts the polyhedron to a cdd object. The operations of CddInterface can then be applied on this convex object.</p>

<p><a id="X7C7CC5497FC52B67" name="X7C7CC5497FC52B67"></a></p>

<h5>6.2-2 ExternalNmzPolyhedron</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExternalNmzPolyhedron</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: normaliz Object</p>

<p>Converts the polyhedron to an normaliz object. The operations of NormalizInterface can then be applied on this convex object.</p>

<p><a id="X842632AB7A09A820" name="X842632AB7A09A820"></a></p>

<h5>6.2-3 DefiningInequalities</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DefiningInequalities</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the Defining inequalities of the given polyhedron.</p>

<p><a id="X87375C8586090666" name="X87375C8586090666"></a></p>

<h5>6.2-4 MainRatPolytope</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MainRatPolytope</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a <code class="code">Polytope</code> Object</p>

<p>Returns the main rational polytope of the polyhedron.</p>

<p><a id="X7A16114A7FFB3309" name="X7A16114A7FFB3309"></a></p>

<h5>6.2-5 MainPolytope</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MainPolytope</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a <code class="code">Polytope</code> Object</p>

<p>Returns the main integral polytope of the given polyhedron.</p>

<p><a id="X7A3FB56D7E895535" name="X7A3FB56D7E895535"></a></p>

<h5>6.2-6 VerticesOfMainRatPolytope</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ VerticesOfMainRatPolytope</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the vertices of the main rational polytope of the polyhedron.</p>

<p><a id="X8697AC27862160FE" name="X8697AC27862160FE"></a></p>

<h5>6.2-7 VerticesOfMainPolytope</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ VerticesOfMainPolytope</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the vertices of the main integral polytope of the given polyhedron.</p>

<p><a id="X7C248476851AEB4A" name="X7C248476851AEB4A"></a></p>

<h5>6.2-8 TailCone</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TailCone</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a <code class="code">Cone</code> Object</p>

<p>Returns the tail cone of the polyhedron.</p>

<p><a id="X7DB9524D7C1A5361" name="X7DB9524D7C1A5361"></a></p>

<h5>6.2-9 RayGeneratorsOfTailCone</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RayGeneratorsOfTailCone</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the Ray Generators of the tail cone.</p>

<p><a id="X79351A698787C5CA" name="X79351A698787C5CA"></a></p>

<h5>6.2-10 LatticePointsGenerators</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LatticePointsGenerators</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns the integral lattice generators of the polyhedron. The output is a list <span class="Math">L</span> of length <span class="Math">3</span>. Any integral point in polyhedron can be written as <span class="Math">a+mb+nc</span>, where <span class="Math">a\in L[1],b\in L[2],c\in L[3], m\geq 0</span>.</p>

<p><a id="X7B57BEAF78559D12" name="X7B57BEAF78559D12"></a></p>

<h5>6.2-11 BasisOfLinealitySpace</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BasisOfLinealitySpace</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns a basis to the lineality space of the polyhedron. I.e., a basis to the vector space that is contained in <code class="code">P</code>.</p>

<p><a id="X81435DD28524EEE8" name="X81435DD28524EEE8"></a></p>

<h5>6.2-12 FVector</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ FVector</code>( <var class="Arg">P</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: a list</p>

<p>Returns a list whose <span class="Math">i</span>'th entry is the number of faces of dimension i-1.



<p><a id="X871597447BB998A1" name="X871597447BB998A1"></a></p>

<h4>6.3 <span class="Heading">Properties</span></h4>

<p><a id="X7B25E29378AF4489" name="X7B25E29378AF4489"></a></p>

<h5>6.3-1 IsBounded</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBounded</code>( <var class="Arg">P</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: true or false</p>

<p>The input is a polyhedron P and the output is whether it is bounded or not.</p>

<p><a id="X7B8DDCE685798D9C" name="X7B8DDCE685798D9C"></a></p>

<h5>6.3-2 IsPointed</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPointed</code>( <var class="Arg">P</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: true or false</p>

<p>The input is a polyhedron P and the output is whether its tail cone is pointed or not.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := Polyhedron( [ [ 1, 1 ], [ 4, 7 ] ], [ [ 1, -1 ], [ 1, 1 ] ] );</span>
<A polyhedron in |R^2>
<span class="GAPprompt">gap></span> <span class="GAPinput">VerticesOfMainRatPolytope( P );</span>
[ [ 1, 1 ], [ 4, 7 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">VerticesOfMainPolytope( P );</span>
[ [ 1, 1 ], [ 4, 7 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">P := Polyhedron( [ [ 1/2, 1/2 ] ], [ [ 1, 1 ] ] );</span>
<A polyhedron in |R^2>
<span class="GAPprompt">gap></span> <span class="GAPinput">VerticesOfMainRatPolytope( P );</span>
[ [ 1/2, 1/2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">VerticesOfMainPolytope( P );</span>
[ [ 1, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LatticePointsGenerators( P );</span>
[ [ [ 1, 1 ] ], [ [ 1, 1 ] ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Dimension( P );</span>
1
<span class="GAPprompt">gap></span> <span class="GAPinput">Q := Polyhedron( [ [ 5, 0 ], [ 0, 6 ] ], [ [ 1, 2 ] , [ -1, -2 ] ] );</span>
<A polyhedron in |R^2>
<span class="GAPprompt">gap></span> <span class="GAPinput">VerticesOfMainRatPolytope( Q );</span>
[ [ 0, 6 ], [ 5, 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">V := VerticesOfMainPolytope( Q );</span>
[ [ 0, 6 ], [ 5, 0 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">L := LatticePointsGenerators( Q );</span>
[ [ [ 0, -10 ], [ 0, -9 ], [ 0, -8 ], [ 0, -7 ], [ 0, -6 ],
[ 0, -5 ], [ 0, -4 ], [ 0, -3 ], [ 0, -2 ], [ 0, -1 ],
[ 0, 0 ], [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 0, 4 ],
[ 0, 5 ], [ 0, 6 ] ], [  ], [ [ 1, 2 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Dimension( Q );</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">RayGeneratorsOfTailCone( Q );</span>
[ [ -1, -2 ], [ 1, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">BasisOfLinealitySpace( Q );</span>
[ [ 1, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">DefiningInequalities( Q );</span>
[ [ 6, 2, -1 ], [ 10, -2, 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Q;</span>
<A polyhedron in |R^2 of dimension 2>
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := PolyhedronByInequalities( [ [ -2, 3, 4, -7 ], -[ -2, 3, 4, -7 ] ] );</span>
<A polyhedron in |R^3 >
<span class="GAPprompt">gap></span> <span class="GAPinput">L := LatticePointsGenerators( P );</span>
[ [ [ -4, 0, -2 ] ], [  ], [ [ 0, 7, 4 ], [ 1, 1, 1 ] ] ]
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Q := PolyhedronByInequalities( [ [-3, 4, 6 ], [ 3, -4, -6 ] ] );</span>
<A polyhedron in |R^2 >
<span class="GAPprompt">gap></span> <span class="GAPinput">LatticePointsGenerators( Q );</span>
[ [  ], [  ], [ [ 3, -2 ] ] ]
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := PolyhedronByInequalities( [ [ -1, 2, 3, 2, 0 ], [ -3, 7, 1, 0, 5 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">      [ 1, -2, -3, -2, 0 ], [ 3, -7, -1, 0, -5 ] ] );</span>
<A polyhedron in |R^4 >
<span class="GAPprompt">gap></span> <span class="GAPinput">L := LatticePointsGenerators( P );</span>
[ [ [ -19, 1, 18, 27 ] ], [  ], [ [ 0, 10, -15, -2 ], [ 1, -2, 2, -1 ] ] ]
</pre></div>

<p><a id="X819F85537D5D9D15" name="X819F85537D5D9D15"></a></p>

<h4>6.4 <span class="Heading">Solving Linear programs</span></h4>

<p>The problem of solving linear programs can be solved in the gap package <code class="code">CddInterface</code>, which is required by <code class="code">NConvex</code>.</p>

<p><a id="X879BD74A7F6327B2" name="X879BD74A7F6327B2"></a></p>

<h5>6.4-1 SolveLinearProgram</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SolveLinearProgram</code>( <var class="Arg">P</var>, <var class="Arg">max_or_min</var>, <var class="Arg">target_func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a list or fail</p>

<p>The input is a polyhedron <code class="code">P</code>, a string <code class="code">max_or_min</code> <span class="Math">\in</span> {"max", "min"} and an objective function <code class="code">target_func</code>, which we want to maximize or minimize. If the linear program has an optimal solution, the operation returns a list of two entries, the solution vector and the optimal value of the objective function, otherwise it returns fail.</p>

<p><a id="X7F4FE0C883B8AA50" name="X7F4FE0C883B8AA50"></a></p>

<h5>6.4-2 SolveLinearProgram</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SolveLinearProgram</code>( <var class="Arg">P</var>, <var class="Arg">max_or_min</var>, <var class="Arg">target_func</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: a list or fail</p>

<p>The input is a polytope <code class="code">P</code>, a string <code class="code">max_or_min</code> <span class="Math">\in</span> {"max","min"} and an objective function <code class="code">target_func</code>, which we want to maximize or minimize. If the linear program has an optimal solution, the operation returns a list of two entries, the solution vector and the optimal value of the objective function, otherwise it returns fail.</p>

<p><span class="Math">\newline</span> To illustrate the using of this operation, let us solve the linear program: <span class="Math">\\P(x,y)= 1-2x+5y</span>, with <span class="Math">\newline</span> <span class="Math">100\leq x \leq 200 \newline</span> <span class="Math">80\leq y\leq 170 \newline</span> <span class="Math">y \geq -x+200\newline\newline</span> We bring the inequalities to the form <span class="Math">b+AX\geq 0</span>, we get: <span class="Math">\newline -100+x\geq 0 \newline</span> <span class="Math">200-x \geq 0 \newline</span> <span class="Math">-80+y \geq 0 \newline</span> <span class="Math">170 -y \geq 0 \newline</span> <span class="Math">-200 +x+y \geq 0 \newline</span></p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">P := PolyhedronByInequalities( [ [ -100, 1, 0 ], [ 200, -1, 0 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ -80, 0, 1 ], [ 170, 0, -1 ], [ -200, 1, 1 ] ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">max := SolveLinearProgram( P, "max", [ 1, -2, 5 ] );</span>
[ [ 100, 170 ], 651 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">min := SolveLinearProgram( P, "min", [ 1, -2, 5 ] );</span>
[ [ 200, 80 ], 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">VerticesOfMainRatPolytope( P );</span>
[ [ 100, 100 ], [ 100, 170 ], [ 120, 80 ], [ 200, 80 ], [ 200, 170 ] ]
</pre></div>

<p>So the optimal solutions are <span class="Math">(x=100,y=170)</span> with maximal value <span class="Math">p=1-2(100)+5(170)=651</span> and <span class="Math">(x=200,y=80)</span> with minimal value <span class="Math">p=1-2(200)+5(80)=1</span>.</p>

<p><a id="X84237872798DB501" name="X84237872798DB501"></a></p>

<h4>6.5 <span class="Heading">ZSolve</span></h4>

<p><a id="X81CA403280755A9B" name="X81CA403280755A9B"></a></p>

<h5>6.5-1 SolveEqualitiesAndInequalitiesOverIntergers</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SolveEqualitiesAndInequalitiesOverIntergers</code>( <var class="Arg">eqs</var>, <var class="Arg">eqs_rhs</var>, <var class="Arg">ineqs</var>, <var class="Arg">ineqs_rhs</var>[, <var class="Arg">signs</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of three matrices</p>

<p>This function produces a basis of the system <var class="Arg">eqs</var> = <var class="Arg">eqs_rhs</var> and <var class="Arg">ineqs</var> >= <var class="Arg">ineqs_rhs</var>. It outputs a list containing three matrices. The first one is a list of points in a polytope, the second is the hilbert basis of a cone. The set of solutions is then the minkowski sum of the polytope generated by the points in the first list and the cone generated by the hilbert basis in the second matrix. The third one is the free part of the solution polyhedron. The optional argument <var class="Arg">signs</var> must be a list of zeros and ones which length is the number of variables. If the ith entry is one, the ith variable must be >= 0. If the entry is 0, the number is arbitraty. Default is all zero.</p>

<p><span class="Math">\newline</span> To illustrate the using of this function, let us compute the integers solutions of the system: <span class="Math">\newline3x+5y=8\newline</span> <span class="Math">4x-2y\geq 2\newline</span> <span class="Math"> 3x+y\geq 3\newline</span></p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SolveEqualitiesAndInequalitiesOverIntergers( [ [ 3, 5 ] ], [ 8 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ [ 4, -2 ], [ 3, 1 ] ], [ 2, 3 ] );</span>
[ [ [ 1, 1 ] ], [ [ 5, -3 ] ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">SolveEqualitiesAndInequalitiesOverIntergers( [ [ 3, 5 ] ], [ 8 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ [ 4, -2 ], [ 3, 1 ] ], [ 2, 3 ], [ 1, 1 ] );</span>
[ [ [ 1, 1 ] ], [  ], [  ] ]
</pre></div>

<p>So the set of all solutions is given by <span class="Math">\{(1,1)+y*(5,-3),y\geq 0\}</span> and it has only one positive solution <span class="Math">(1,1)</span>.</p>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap5.html">[Previous Chapter]</a>    <a href="chap7.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

98%


¤ Dauer der Verarbeitung: 0.16 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.