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$.
- I have to show that for any $x$ in $F$ and any $y$ in $F^*$ we have $c^*x ≤ y^*b$.
- 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$.