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 cT x subject to Ax ³ b. Then if x1 and x2 are optimal solutions, then we must have cT x1=cT x2=v, the optimal value. The general point on the line between x1 and x2 is z=lx1+(1-l) x2, where 0 £ l £ 1; then we have

cT z=lcT x1 + (1-l) cT x2 = lv+(1-l)v=v

and

Az=lAx1+(1-l)A x2

³ lb+(1-l) b=b

so z is also a feasible solution and is optimal.

Now if x1 and x2 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 .