Vanessa Vanessy

Posted on Wednesday, 24 September, 2003 - 10:10 am:

I want to prove that any point on the line segment connecting two distinct optimal solutions of a canoniccal LPP is an optmal solution. And then deduce that any canonical LPP has either zero, one, or infinitely many optimal solutions.

I know that the line segment joins any two points of the feasible set there it is an optimal solution of a canonical LPP (finds the constraint set).
I really have no idea!

David Loeffler

Posted on Wednesday, 24 September, 2003 - 12:02 pm:

Well, suppose that we have a problem of the usual form - maximise

c^{T} x

subject to

Ax \geq b

. Then if

x_{1}

and

x_{2}

are optimal solutions, then we must have

c^{T} x_{1} = c^{T} x_{2} = v

, the optimal value. The general point on the line between

x_{1}

and

x_{2}

z = λ x_{1} + (1 - λ) x_{2}

, where

0 \leq λ \leq 1

; then we have

$c^{T} z = λ c^{T} x_{1} + (1 - λ) c^{T} x_{2} = λ v + (1 - λ) v = v$

and

$Az = λ {Ax}_{1} + (1 - λ) A x_{2}$

$\geq λ b + (1 - λ) b = b$

so $z$ is also a feasible solution and is optimal.

Now if $x_{1}$ and $x_{2}$ are distinct there are infinitely many possible positions of $z$ , so if your LPP has two optimal solutions, it has infinitely many.

David

Vanessa Vanessy

Posted on Wednesday, 24 September, 2003 - 04:46 pm:

Hi David,
I understand what you wrote but i was more interesting in the proof that any point on the line segment connecting two distinct optimal solutions of a canoniccal LPP is an optmal solution.

David Loeffler

Posted on Wednesday, 24 September, 2003 - 06:04 pm:

Vannessa, that was part of what I just wrote: the z I described above is the most general point of that line.

David

Vanessa Vanessy

Posted on Wednesday, 24 September, 2003 - 07:57 pm:

ah ok. Sorry i thought it was more difficult. Thanks

David Loeffler

Posted on Thursday, 25 September, 2003 - 12:49 pm:

Come on, it's linear programming: it consists of something very easy made difficult by hideously complicated notation and terminology