Week 3 - LP minimisation, non negativity, multiple optima

Question 1

No. of effective constraints = ?

Answer 1

No. of effective constraints = # of basic variables

taken from # of non-negativity constraints = # of nonbasic variables

Question 2

Necessary (but not sufficient) condition for MULTIPLE OPTIMAL solutions

Answer 2

If the LP problem has multiple optimal solutions then some constraints DEFINING x* must have DUAL VALUE 0.

If ALL dual values associated to the constraints that define an optimal extreme solutions are ≠ 0, then the solution is the unique optimum

Necessary but not sufficient b/c…
- if there are dual cases = 0, it does NOT necessarily mean that there are multiple optima
- b/c there are cases where a dual value = 0 but there is a unique optimum

Question 3

Weak duality theorem

Answer 3

If the primal problem admits an optimal solution, then the primal optimum value is AT MOST the dual optimum value.

Question 4

Weak duality theorem - Proof

Answer 4

See notes!

Question 5

Strong duality theorem

Answer 5

1. If an LP problem admits an optimal solution, then also its dual admits an optimal solution.
2. Furthermore, the optimal values of the primal and dual problems are EQUAL.

Question 6

2 optimality conditions for an extreme solution
An extreme solution x* to an LP is optimal IF AND ONLY IF there exists a feasible solution y* for the dual that satisfies these 2 conditions…

Answer 6

1. ystar satisfies AT EQUALITY all the dual constraints corresponding to BASIC VARIABLES
2. For every INEFFECTIVE CONSTRAINT for xstar, the corresponding component of ystar is 0

Such a solution ystar is optimal for the dual