Before to write my question. (P) linear programming, and the dual problem is denoted (P*). Th linear problem defined via matrix (m x n) matrix A. b is a vector in R^m and c in R^n. The program (P) can be written as: max_x∈R c*x under the constraints ∀i∈{1,...,m}: i_A ≤ b_i and ∀j∈{1,...,n}:x_j ≥0.

The dual problem (p*) is given as: min y*b, -yA ≥ -c and y ≥ 0

A point $x$ in $\mathbb{R}^n$ and a point $y$ in $\mathbb{R}^m$. Then $x$ is a feasible solution if it satisfies the contraints $Ax ≤ b$ and $0 ≤ x$. Similarly a point in $\mathbb{R}^m$ is a feasible solution to the dual problem if $A^t ≤ c$ and $y ≥ 0$. The set of feasible solution to $(P)$ is denoted $F$. And the set of feasible solution to $(P)^*$ is denoted $F^*$. Suppose that $F\neq\emptyset$ and $F^*\neq \emptyset$.

1. I have to show that for any $x$ in $F$ and any $y$ in $F^*$ we have $c^*x ≤ y^*b$.
2. I have to show that if $x$ in $F$ and $y$ in $F^*$ satisfy $c^*x ≥ y^*b$, then $x$ is an optimal solution to $(P)$ and $y$ is an optimal solution to $(P)^*$ and $c^*x = y^*b$.
-
What does $(P)^*$ mean? Similarly what does $c^*$ and $b^\ast$ mean? Transpose? – Srivatsan Dec 1 '11 at 16:07

Your question is incomplete/missing some things. I will assume that you are talking about the following primal/dual formulations:

Primal

$$\text{Max} \ c^t x$$

$$\text{Subject to:}$$

$$Ax \le b$$

$$x \ge 0$$

Dual

$$\text{Min} \ b^t y$$

$$\text{Subject to:}$$

$$A^t y \ge c$$

$$y \ge 0$$

Now, note the following:

1. Consider $A x \le b$.

Re-write $A x \le b$ as $x^t A^t \le b^t$.

Post-multiply both sides by $y$. The inequality does not change sign as $y \ge 0$. Thus, we get:

$x^t A^t y \le b^t y$

2. Consider $A^t y \ge c$.

Use the ideas from 1 to re-write $A^t y \ge c$ to get $x^t A^t y \ge c^t x$

(I am omitting the steps here. You should be able to fill them in).

3. Put together the conclusions of 1 and 2 above and you get your first result.

4. To prove your second result put together the facts that (a) $c^t x \le b^t y$ for every set of feasible solutions to the respective programs and that (b) there is a point $x^*$ such that $c^t x^* \ge b^t y^*$.

What can you conclude from the above?

-
thank you for your help. In the first i get c^t≤b^ty. and i think i did in an another way. From point 4, can A already conclude that the optimal solutions are equal? – parosara Dec 1 '11 at 18:06
You still need to fill some gaps. E.g., Note that $c^t x^* \ge b^t y^*$ implies that $c^t x^* > b^t y^*$ or $c^t x^* = b^t y^*$. What can you conclude from this? In order to shop that $x^*$ and $y^*$ are optimal solutions you could use proof by contradiction. – tards Dec 1 '11 at 20:22
thank you for helping – parosara Dec 2 '11 at 11:52