I have one linear programming problem given by
\begin{matrix}{}
\min & \displaystyle\sum_{i=1}^I c_ix_i ; &c_i\geq 0\\
&\\
s.a & \sum_{i=1}^{I}x_i=d,& d\geq0\\
&\\
&0\leq x_i\leq b_i& 1\leq i\leq I
\end{matrix}
Where $c_i$ are parameter that indicates cost.
I have determined that this problem has an optimal solution if and only if $d\leq b_1+b_2+\cdots b_I$.
And since the coefficients are positive, then this problem can be solved by placing as much of the decision variable $x_i$ as possible, from the lowest cost to the highest cost , and so on until the sum is $ d $. But I can't mathematically formulate this fact, i mean, i want to show that if I take another $ x $ in the feasible region then the value given by this point will be less than the point generated by the process mentioned above.
Example of the processe
\begin{matrix}{}
\min & 5x_1+3x_2+x_3 ; &\\
&\\
s.a & x_1+x_2+x_3=800& \\
&\\
&0\leq x_1\leq 400&\\
&\\
&0\leq x_2\leq 200\\
&\\
&0\leq x_3\leq 500\\
\end{matrix}
the variable associated with the lowest cost is $ x_3 $, so to minimize the objetive function i put $x_3=500$ (the maximum possible), then $x_2$ is the next with $x_2=200$, so at this point i have $700$ and i only need 100 more to obtain 800, then $x_1=100$. Thus the optimal point is $(100,200,500)$.
How do I show that if I choose another point this can't be optimal?
Best Answer
Here are two alternative approaches to prove optimality: