Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.
share|improve this question
    
What does $(P)^*$ mean? Similarly what does $c^*$ and $b^\ast$ mean? Transpose? –  Srivatsan Dec 1 '11 at 16:07
add comment

1 Answer

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.