0

I have this LP:

Maximize $ 2x_1 + 3x_2$

S.t

(1) $ 2x_1 + 2x_2 \leq 30 $

(2) $x_1 + 2x_2 \geq 10$

(3) $ x_1, x_2 \geq0 $

I have to solve the LP by using the dual simplex method, and I have to start with the basis consisting of the slack variable in (1) and the surplus variable in (2).

I'm not sure if this is the dual form of the above LP?

Min $30y_1 + 10y_1$

S.t

$2y_1 + y_1 + s_1 = 2$

$ 2y_1 + 2y_1 - s_2 = 3$

$y_1, y_2, s_1, s_2 \geq 0 $

Gabarta123
  • 59
  • 1
  • 4
  • It seems like you incorrectly translated the $<$ (should be $\leq$?) and $\geq$ of (1) and (2) into the sign of $y$. Maybe multiply (2) with -1 first. – LinAlg Nov 04 '18 at 23:35

1 Answers1

1

The primal is

$$\max 2x_1 + 3x_2$$

S.t
$$ 2x_1 + 2x_2 \leq 30 $$

$$-x_1 - 2x_2 \leq -10$$

$$ x_1, x_2 \geq0 $$

where I have multiply the second inequality by $-1$ so that I can easily say that in the dual, all the variables are nonnegative.

Suppose $y_1, y_2$ corresponds to the dual variables of the first and second constraint.

$$\min 30y_1 -10y_2$$

S.t

$$2y_1-y_2 \ge 2$$

$$2y_2-2y_2 \ge 3$$

$$y_1, y_2 \ge 0$$

I will leave the task of introducing slack/surplus to you.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149