0
$\begingroup$

In the book of Papadimitriou. Combinatorial optimization, there is the instance of Linear Programming (LP) s.t. \begin{equation} \begin{split} &{\rm minimize:\;} c_1x_1 + c_2x_2 + c_3x_3,\\ &{\rm subect\; to:\; }x_1 + x_2 + x_3 = 2 \end{split} \end{equation} The authors argue that the minimum is found at the corners of the 3d triangle (see figure) $v_1,v_2,v_3$.enter image description here

I have a couple of questions:

  1. If the $c_i$'s are all positive, then the minimum of the cost function is simply $2c_k$, where $0\leq c_k\leq c_j \leq c_i$, right?

  2. If for instance two $c_i$'s are negative, then one has to pick the two $x_i$'s that multiply them, s.t. $x_i+x_j = 2$, right? In this case, it cannot be that only $v_1,$v_2$ or $v_3$ are the only solutions to the LP program.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Presumably, the additional assumption is that all $x_j$ are non-negative, right?

  1. Yes. The minimum is always $2 \min_j c_j$. This is always true, even if some $c_i$'s are negative.
  2. If two $c_i$'s are negative, one of them is still smaller and you can pick the corresponding $x_i$ to be equal to $2$ (and all others to $0$).
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.