2
$\begingroup$

Minimize $\sum^n_{i=1} c_i x_i$ subject to $\sum^n_{i=1} a_i x_i = b$ (a single constraint), $x_i \ge 0$.

  1. Derive a simple test for feasibility of this problem

  2. Assuming the optimal cost is finite, develop a simple method for obtaining an optimal solution directly.

For the first part, I have $\sum^n_{i=1} a_i x_i = b \iff \text {sgn}(b)=\text{sgn}(a_i)$ for some $i \in \{1,..,n\}$ or $b = 0$.

I have trouble obtaining this simple method for part two. Could someone help me out here?

I know $ -\infty < \sum^n_{i=1} c_i x_i$ and $\sum^n_{i=1} a_i x_i = b$.

$\endgroup$
  • 3
    $\begingroup$ What have tou tried and where did you get stuck? $\endgroup$ – Raphael Sep 23 '14 at 11:07
1
$\begingroup$

Hint: Since there are $n+1$ constraints on $n$ variables, there is a solution in which all but one constraint are tight. You can calculate all these solutions explicitly ("on paper"), and choose the best one.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.