# Linear Programming Problem

• Sep 20th 2009, 08:01 PM
thaopanda
Linear Programming Problem
This is a rather long problem...

Consider the following:
maximize $\displaystyle \sum c_{j}x_{j}$ with j = 1 as it goes to n
subject to $\displaystyle \sum a_{ij}x_{j} \leq b_{i}$ where j = 1 as it goes to n, i = 1, 2,...,m
$\displaystyle x_{j} \geq 0$ where j = 1,2,...,n

first form its dual:
minimize $\displaystyle \sum b_{i}y_{i}$ with i = 1 as it goes to m
subject to $\displaystyle \sum y_{i}a_{ij} \geq c_{j}$with i = 1 as it goes to m, j = 1,2,...,n
$\displaystyle y_{i} \geq 0$ where i = 1,2,...,m

Then write that minimization to a maximization in standard form:
maximize $\displaystyle \sum b_{i}y_{i}$ with i=1 as it goes to m
subject to $\displaystyle \sum -y_{i}a_{ij} \leq -c_{j}$ with i=1 as it goes to m, j = 1,2,...,n
$\displaystyle y_{i} \geq 0$ with i=1,2,...,m

The above process can be thought of as a Transformation T on the space of data defined by: $\displaystyle (a_{ij},b_{i},c_{j}) \longrightarrow^T (-a_{ji}, -c_{j},b_{i})$

Let $\displaystyle \zeta^* (a_{ij},b_{i},c_{j})$ denote the optimal objective function value of the standard-form linear programming problem haing data $\displaystyle (a_{ij},b_{i},c_{j}$. By strong duality and the fact that a maximation dominates a minimization, it follows that:
$\displaystyle \zeta^* (a_{ij},b_{i},c_{j}) \leq \zeta^* (-a_{ij},-c_{j},b_{i})$

If the process is repeated, transformation T becomes:
$\displaystyle (a_{ij},b_{i},c_{j}) \longrightarrow^T (-a_{ij},-c_{j},b_{i})$
$\displaystyle \longrightarrow^T (a_{ij},-b_{i},-c_{j})$
$\displaystyle \longrightarrow^T (-a_{ij},c_{j},-b_{i})$
$\displaystyle \longrightarrow^T (a_{ij},b_{i},c_{j})$

and hence...
$\displaystyle \zeta^* (a_{ij},b_{i},c_{j}) \leq \zeta^* (-a_{ij},-c_{j},b_{i})$
$\displaystyle \leq \zeta^* (-a_{ij},-c_{j},b_{i})$
$\displaystyle \leq \zeta^* (a_{ij},-b_{i},-c_{j})$
$\displaystyle \leq \zeta^* (-a_{ij},c_{j},-b_{i})$
$\displaystyle \leq \zeta^* (a_{ij},b_{i},c_{j})$

But the first and last entry in this chain of inequalities is equal, therefore all these inequalities appear equal. Although possible, this isn't always true.

THE QUESTIONS:
1. What is the error in this logic?
2. Can you state a (correct) nontrivial theorem that follows from this line of reasoning?
3. Can you give an example where the four inequalities are indeed all equalities?