Transforming a Linear Program into the equality constrained standard form.

linear programmingoptimization

[Transform LP to equality constrained standard form][1]

THE PROBLEM: [1]: https://i.stack.imgur.com/JKUlj.png

Rather than using the standard LP form we saw in class, some prefer using a form where all variables are nonnegative, all constraints are equality constraints, and the cost function is a minimization. So a general LP would look like:

$$\begin{aligned}
\text{minimize} \qquad& c^Tx \\
\text{subject to:} \qquad& Ax = b \\
& x \ge 0\\
\end{aligned}$$
Consider the following LP:$$\begin{aligned}
\text{maximize} \qquad& 3z_1 – z_2 \\
\text{subject to:} \qquad& -z_1 + 6z_2 – z_3 + z_4 \ge -3\\
& 7z_2 + z_4 = 5 \\
& z_3 + z_4 \le 2 \\
& -1 \le z_2 \le 5,\quad -1 \le z_3 \le 5,\quad -2 \le z_4 \le 2
\end{aligned}$$

a) Transform the above LP into the equality-constrained standard form of (1). What are A, b, c, and x? Be sure to explain how the decision variables of your transformed LP relate to those of the original LP

Hello,

So I've been stuck on this problem for a minute. I have the solution but I can't quite seem to understand how to derive it myself.

@variable(m, x[1:9] >= 0 )
@constraints(m, begin
x[4] + x[5] == 6
x[2] + x[3] == 6
x[6] + x[7] == 4

x[1]-5x[2]+x[3]+(5/6)x[4]-(1/6)x[5]-(1/2)x[6]+(1/2)x[7]+x[8] == 3
(35/6)x[2]-(7/6)x[3]+(1/2)x[6]-(1/2)x[7] == 5
(5/6)x[4]-(1/6)x[5]+(1/2)x[6]-(1/2)x[7]+x[9] == 2
end)

@objective(m, Min, -3x[1] + (5/6)x[2] - (1/6)x[3] )

Specifically what I am having difficulties "seeing" is how the inequality constraints when transformed to equality constraints get so many slack variables and also were the coefficients like (5/6), (1/6) come from.

I get the first three constraints but when I get to the fourth, I just can't see the logic and so I'm hoping someone could be so kind to clarify what's going on here. Thanks in advance!

Edit2: I don't know if this will help but it's clear that:
$$\begin{aligned}
\qquad& z[1] = x[1] \\
\qquad&z[2] = (5/6)x[2] – (1/6)x[3]\\
\qquad&z[3] = (5/6)x[4] – (1/6)x[5]\\
\qquad&z[4] = (1/2)x[6] – (1/2)x[7]\\
\end{aligned}$$

however why is less clear to me at least.

Also here is A, b and c:

A = [ 0   0    0    1    1    0    0    0    0
      0   1    1    0    0    0    0    0    0
      0   0    0    0    0    1    1    0    0
      1  -5    1   5/6 -1/6 -1/2  1/2   1    0
      0  35/6 -7/6  0    0   1/2 -1/2   0    0
      0   0    0   5/6 -1/6  1/2 -1/2   0    1 ]

b = [ 6; 6; 4; 3; 5; 2 ]

c = [ -3; 5/6; -1/6; 0; 0; 0; 0; 0; 0 ]

Best Answer

There is no one unique solution when rewriting a LP program to normal form. It appears that you have tried rewriting by using a computer program, which has chosen rational coefficients for the program.

We can derive as such:

  • $z_1$ is a free variable, it can be negative. Rewrite by saying $z_1=x_1-x_2$, where $x_1,x_2\geq 0$.
  • $z_2$ and $z_3$ are allowed to be negative. Write $z_2 = x_3-1$, $z_3=x_4-1$. $x_3,x_4\geq 0$, $x_3,x_4 \leq 6$.
  • $z_4$ is allowed to be negative. Write $z_2 = x_5-2$. $x_5\geq 0$, $x_5 \leq 4$.

Now we must first substitute all variables by the new ones resulting in the following program:

$$\begin{align} \text{maximize: } & 3x_1 - 3x_2 - x_3-1 \cr \text{subject to: } & -x_1+x_2+6x_3-6-x_4+1+x_5-2\geq -3\cr & 7x_3-7+x_5-1=5\cr & x_4-1+x_5-2\leq 2 \cr & x_3 \leq 6, x_4\leq 6, x_5\leq 4 \cr & x_1,x_2,x_3,x_4,x_5\geq 0 \end{align}$$

We can now simplify and introduce slack variables to get rid of the inequalities. You see that by substituting variables, we now have more inequalities. We will therefore have to introduce 5 slack variables. Your answer seems to have four slack variables, which is possible since the original program already contains an equality constraint, which allows us to eliminate a variable from the original. Anyway, after introducing slack variables, you can change the sign of the object function and maximize rather than minimize, which will give you a good answer.

It is important to note, that this answer will be different from the one you presented. In general, we could choose to make any substitution along the lines of replacing $z_i = c\cdot x_j$ which explains the different coefficients in your presented answer.

Related Question