Linear Programming Problem - Looking for an Explicit Solution

887 Views Asked by At

How can I solve a linear program of the form:

$$\min c^Tx\\ \mathrm{s.t.}\ Ax=b\\ x\geq0\\$$

where $c$ is fixed.

In the specific case I am looking at, $$x \in R^n$$ $A$ is an $m\times n$ matrix whose first row is all $1$'s and other elements are all zero.

$b$ is $m\times 1$ whose first element is $1$ and all others are zero.

(Note: this is a standardization of the given constraints: $\{x\mid \sum_{i=1}^n x_i = 1,x_i \ge 0\}$)

I am unfamiliar with linear programming. Am I able to derive an explicit solution for $x$: the minimum of this function?

1

There are 1 best solutions below

2
On BEST ANSWER

If I understand you, your problem is

$$ \min c^T x $$ $$ \sum x_i = 1, x\geq 0$$

So the optimal objective value is $$ \min_i c_i $$ with $x^\ast = 0$ except for the index corresponding to the minimum element of $c$ which $=1$. For example if $$c=[3,-5,-2]$$ then the optimal solution is $$x=[0,1,0], z=-5$$