chapitre 4

Question 1

dual linear program of the initial primal
canonical LP

Answer 1

To find the best upper bound, i.e. the smallest one, we need to solve the
following LP: check sur cours

Question 2

weak duality problem

Answer 2

Let x (= xD) be a feasible solution of a canonical LP and y (= yD) a feasible solution of its dual problem, then cx ≤ yb

Question 3

weak duality problem Corollary

Answer 3

Let x (= xD) be a feasible solution of PLP of value z and y (= yD) a feasible solution of DLP of value w. If z = w, then the solutions x and y are optimal for their respective problem.

if the primal and dual solutions are feasible, then there are both optimal

If PLP has no finite optimum, then its dual cannot have a feasible solution without contradicting the weak duality theorem!

the weak duality property implies that the duality gap is either zero or greater zero. If the duality gap is zero, then the obtained solution of primal and dual are optimal respective of their problem.

Question 4

i) primal-feasible        
ii) dual-feasible        
iii) optimal        
iv) primal-unbounded        
v) dual-unbounded        
vi) primal-degenerated        
vii) dual-degenerated