I'm trying to solve a simple LP using Lagrangian method. But I don't know how to use the soloution of the dual problem to find the solution of the main LP.
I consider the following simple problem: $$ \min_{x} \sum_{i=1}^n -f_ix_i $$ $$ \text{s.t.}\quad \sum_{i=0}^n x_i=1, x\ge 0 $$
The general form is: $$ \min c^Tx $$ $$ \text{s.t.}\quad Ax=b, x\ge 0 $$
In my problem: $A=[1 \, 1\,1 \cdots \,1]$, $c=-f=[-f_1\,-f_2\,\cdots\,-f_n]^T$ and $b=1$.
The dual problem will be: $$\max \,-v$$ $$\text{s.t. }A^Tv-f\ge 0$$
The constraint means: $$\forall i\le n, \, v\ge f_i\Rightarrow -v\le -f_i$$ $$\Rightarrow -v\le \min{-f_i} \Rightarrow \,-v= \min{-f_i}= -\max f_i\Rightarrow v=\max f_i$$
Therefore I've solved the dual problem. but what is the solution of the original problem? My question is:
In general how can I find the solution $x$ after solving the dual problem for $v$?
Complementary Slackness Principle tells us that either the inequality $i$ in $A^Tv_{opt}-f\ge 0$ becomes equality or $x_i=0$. Assuming all the numbers $f_i$ are distinct and $\nu_{opt}=\max f_i=f_k$. Then $\nu_{opt}>f_i$ for $i\ne k$, hence, $x_i=0$ for $i\ne k$. Clearly then $x_k=1$.