In linear programming, if we model the solution as a polytope, every vertex is a solution.

I'm trying to prove the following statement:

If $x$ and $y$ are two solutions with $n-1$ joint constraints, there exists a solution vector $c$ such that, for each $v\in P$ (the polytope of the problem) that is different from $x$ and from $y$, we have $\langle c,x\rangle = \langle c,y\rangle < \langle c,z\rangle$.

Basically, this means that only $x$ and $y$ are the optimal solutions for the problem. But why is it true? And what is the vector $c$ that exists here?

  • $\begingroup$ I can't quite figure out your question, but in any case I suggest asking your TA or professor. $\endgroup$ – Yuval Filmus Dec 21 '16 at 15:51
  • $\begingroup$ Hint: try getting an intuition from the 2D case. Generalizing to more dimensions is not too difficult once you understand the 2D solution to your problem. $\endgroup$ – adrianN Dec 21 '16 at 15:54
  • $\begingroup$ @YuvalFilmus When you see text that doesn't make sense but includes one of < and >, it's a good tip is to take a look at the source. Often, it means the asker has included mathematics outside $...$ and the parser has treated random chunks of it as HTML tags and discarded them. $\endgroup$ – David Richerby Dec 21 '16 at 17:30
  • $\begingroup$ Try generalizing the proof that for any solution $x$ there exists a solution vector $c$ such that $\langle c,x \rangle < \langle c,z \rangle$ for all $z \neq x$ in the polytope. $\endgroup$ – Yuval Filmus Dec 21 '16 at 19:18
  • $\begingroup$ thanks guys , great intuition . i'm taking this to account . i'll $\endgroup$ – ChenSho Dec 22 '16 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.