1
$\begingroup$

Minimize $$2y_1 -3y_2 + 4y_3$$ subject to

$$8 y_1 -y_3 = 50\\ 6y_2 +y_3 \le 60\\ y_1, y_2 \ge 0, -15 \le y_3 \ge 0$$

The problem is to write the dual. I end up with

Maximize $$50x_5 - 60x_3 + 15 x_4$$ subject to

$$8x_5 \le 2\\ -6x_3 \le -3\\ x_5 + x_3 - x_4 \le -4\\ x_5 \text{unrestricted}, x_3, x_4 \ge 0.$$

Verifying my answer, I look at the objective function of the primal and I see $+4y_3$, so I think the $b$-vector of the dual should have the same sign on the third restriction. Then I multiply that restriction by $-1$, getting

Maximize $$50x_5 - 60x_3 + 15 x_4$$ subject to

$$8x_5 \le 2\\ -6x_3 \le -3\\ -x_5 -x_3 + x_4 \ge 4\\ x_5 \text{unrestricted}, x_3, x_4 \ge 0.$$

Similarly, I look at the $-60x_3$ on the dual's objective function and I think it has the wrong sign because I have a 60 on the $b$-vector of the primal, but I quickly gave up on trying to fix that because I looked at the answer at the back of the book and they wrote

Maximize $$50x_1 — 70x_2 — 15x_3$$ subject to

$$4x_1 \le 1\\ 2x_2 \ge 1\\ - x_1 - x_2 + x_3 \ge 4\\ x_1 \text{unrestricted}, x_2, x_3 \ge 0.$$

So it seems they don't care at all. They reduced the first two inequalities, disrespecting the transpose matrix of the primal. Why aren't they following some strict format to answer? The definition of the dual makes reference to a min or max-form, so the dual to a primal should respect that definition strictly. I'm surprised the book's answer still reduced inequalities (losing a perfect match of numbers against the primal's matrix of restrictions).

The book is "An Introduction to Linear Programming and Game Theory", $3$rd edition, by Thie and Keough. Wiley, 2008. This is exercise $f$ section $4.2$, page $131$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.