State and prove fundamental theorem of duality 

### Fundamental Theorem of Duality

The **Fundamental Theorem of Duality** in linear programming states that every linear programming problem (known as the **primal problem**) has an associated dual problem. The optimal solution to one provides bounds to the optimal solution of the other. Specifically:

1. **If the primal problem has an optimal solution, then the dual problem also has an optimal solution.**
2. **If one of these problems is unbounded, then the other has no feasible solution.**
3. **If either the primal or the dual problem has no feasible solution, then the other is either infeasible or unbounded.**

### Primal and Dual Problems

Given a primal linear programming problem in the standard form:

\[
\text{Maximize } c^T x \text{ subject to } Ax \leq b, \ x \geq 0,
\]

its corresponding dual problem is:

\[
\text{Minimize } b^T y \text{ subject to } A^T y \geq c, \ y \geq 0.
\]

### Proof of the Fundamental Theorem of Duality

**1. Weak Duality Theorem**:

This theorem states that for any feasible solution \( x \) of the primal problem and any feasible solution \( y \) of the dual problem, the objective value of the dual is greater than or equal to the objective value of the primal:

\[
c^T x \leq b^T y.
\]

**Proof of Weak Duality**:
- Suppose \( x \) is a feasible solution for the primal, so \( Ax \leq b \) and \( x \geq 0 \).
- Suppose \( y \) is a feasible solution for the dual, so \( A^T y \geq c \) and \( y \geq 0 \).

Now consider the expression:

\[
c^T x \leq (A^T y)^T x = y^T A x.
\]

Since \( Ax \leq b \), we have:

\[
y^T A x \leq y^T b.
\]

Therefore:

\[
c^T x \leq b^T y.
\]

This inequality shows that the value of the objective function of the primal is always less than or equal to the value of the objective function of the dual. This is the essence of the weak duality theorem.

**2. Strong Duality Theorem**:

This theorem states that if the primal problem has an optimal solution \( x^* \), then the dual problem also has an optimal solution \( y^* \), and their objective values are equal:

\[
c^T x^* = b^T y^*.
\]

**Proof of Strong Duality**:
- The strong duality theorem is usually proved using the **Karush-Kuhn-Tucker (KKT) conditions**, which are necessary and sufficient conditions for optimality in linear programming.
- For the primal problem's optimal solution \( x^* \) and the dual problem's optimal solution \( y^* \), the KKT conditions are:
  1. Primal feasibility: \( Ax^* \leq b, \ x^* \geq 0 \).
  2. Dual feasibility: \( A^T y^* \geq c, \ y^* \geq 0 \).
  3. Complementary slackness: \( y_i^* (b_i - (Ax^*)_i) = 0 \) for all \( i \), and \( x_j^* (c_j - (A^T y^*)_j) = 0 \) for all \( j \).

Using these conditions, it can be shown that the optimal values of the primal and dual problems must be equal. This equality is the heart of the strong duality theorem.

### Conclusion

The Fundamental Theorem of Duality guarantees that solving either the primal or the dual provides the same optimal value, ensuring consistency between the two formulations. The weak duality gives us a bound, while the strong duality confirms the exact equivalence at optimality.

---

Would you like further details on any part of this theorem or the proof? Here are some related questions that might interest you:

1. What are the Karush-Kuhn-Tucker (KKT) conditions in more detail?
2. How does the duality gap relate to the optimality of solutions?
3. What are some examples of primal and dual problems in real-world applications?
4. Can you explain the complementary slackness condition with examples?
5. How does duality theory apply to non-linear programming problems?

**Tip:** Understanding duality can provide deep insights into the structure of optimization problems, often leading to more efficient solution methods.

Explore the Fundamental Theorem of Duality in linear programming, its implications, and proof. Understand how primal and dual problems relate, and discover the implications of weak and strong duality theorems. Suitable for advanced undergraduate students and professionals.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation