0
$\begingroup$

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$.
  • 0
    What does $(P)^*$ mean? Similarly what does $c^*$ and $b^\ast$ mean? Transpose?2011-12-01

1 Answers 1

2

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?

  • 0
    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.2011-12-01