- #1

- 986

- 8

## Homework Statement

If

**x**

_{1}and

**x**

_{2}solve the LP problem

*P*, show that there are infinitely many solutions.

## Homework Equations

(

*P*): maximize of

**c**

^{T}

**x**subject to

**Ax**≤

**b**,

**x**≥

**0**

(Though the problem doesn't say it, I'm sure we assume

**x**

_{1}≠

**x**

_{2})

## The Attempt at a Solution

So it'll suffice to show that

**Ax**

_{1}=

**Ax**

_{2}= sup{

**Ax**|

**Ax**≤

**b**,

**x**≥

**0**} implies the existence of another

**x**

_{3}= sup{

**Ax**|

**Ax**≤

**b**,

**x**≥

**0**}. I remember my professor saying something about convex sets (I wasn't taking notes so I can't remember the gist of it). I think I need to choose λ ε (0, 1) and then show that

**x**

_{3}= λ

**x**

_{1}+ (1 - λ)

**x**

_{2}= sup{

**Ax**|

**Ax**≤

**b**,

**x**≥

**0**}. How do I do this?