Let P ⊆ R 2 be the convex hull of the points ( 0 , 0 ), ( 3 , 1 ) and ( − 1 , 2 ).Exercise: Give a TDI system A x ≤ b describing P with A and b integral.I know the following:Many combinatorial min-max relations can be understood as a result of LP-duality max { w T x : A x ≤ b } = min { y T b : y T A = w T , y ≥ 0 }combined with integrality of optimal solutions on the primal and dual side.Def: Let A x ≤ b be a rational system of linear inequalities and let P := { x : A x ≤ b } be the associated polyhedron. The system A x ≤ b is Totally Dual Integral (TDI) if for every integral objective vector w, the minimum in the dual is attained by an integral vector y (if the minimum is finite).What I should do: I need to find a TDI system A x ≤ x such that P = { x : A x ≤ b } is the convex hull of the points ( 0 , 0 ) , ( 3 , 1 ) and ( − 1 , 2 ) and that A and b are integral. So I think I probably should identify P first.

Question

Let   P  ⊆        R    2   be the convex hull of the points   (  0  ,  0  ),   (  3  ,  1  ) and   (  −  1  ,  2  ).Exercise: Give a TDI system   A  x  ≤  b describing   P with   A and   b integral.I know the following:Many combinatorial min-max relations can be understood as a result of LP-duality  max  {      w    T    x  :  A  x  ≤  b  }  =  min  {      y    T    b  :      y    T    A  =      w    T    ,  y  ≥  0  }combined with integrality of optimal solutions on the primal and dual side.Def: Let   A  x  ≤  b be a rational system of linear inequalities and let   P  :=  {  x  :  A  x  ≤  b  } be the associated polyhedron. The system   A  x  ≤  b is Totally Dual Integral (TDI) if for every integral objective vector w, the minimum in the dual is attained by an integral vector   y (if the minimum is finite).What I should do: I need to find a TDI system   A  x  ≤  x such that   P  =  {  x  :  A  x  ≤  b  } is the convex hull of the points   (  0  ,  0  )  ,  (  3  ,  1  ) and   (  −  1  ,  2  ) and that   A and   b are integral. So I think I probably should identify   P first.

Xzavier Shelton · Accepted Answer

You need to find three lines: one that intersects (0,0) and (3,1); one that intersects (0,0) and (-1,2); and the line that intersect (-1,2).Then you should be able to find the matrix A and the corresponding vector b.For the first line for example you have:       x    1    =  a      x    2    +  b, where   a  =      1    3   and   b  =  0.That is how you identify   P.

Let P ⊆ <mi mathvariant="double-struck">R 2 </msup> be

Answered question

Answer & Explanation

New Questions in Algebra I