# Lagrangian method for a silmple linear programming

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$$.
• @SMA.D It is a part of KKT. For inequalities $g(x)\le 0$ the Lagrange function is $f(x)+u^Tg(x)$, then in KKT there is a condition that $u_i g_i(x)=0$. It is CSP. – A.Γ. Dec 20 '18 at 8:57