Assuming finite optimal cost of a specific LP, find an optimal solution directly

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$$.

• What have tou tried and where did you get stuck? – Raphael Sep 23 '14 at 11:07

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.