2

I have to find the dual to this linear programming problem:

Maximize $-15z-\frac{11}{20}w-3a-3b=-132+p$

subject to

$y+9z+\frac{13}{10}w+3a-2b=12$

$x-2z-\frac{7}{20}-a+b=4$

$14z-\frac{69}{20}w+7a-7b+c=42$

I tried looking it up online, but the explanations remain unclear. This is all I have so far:

Minimize $15z+\frac{11}{20}w+3a+3b-132$

subject to

$y+9z+\frac{13}{10}w+3a-2b-12=0$

$x-2z-\frac{7}{20}w-a+b-4=0$

$14z-\frac{69}{20}w+7a-7b+c-42=0$

Any help is appreciated. Thanks.

Alti
  • 2,458
  • You don't have a normal maximisation problem here, since the function to be maximised always takes the value -132. As such the dual objective function will also always take the value -132, which makes the problem trivial. I would never expect to see an $=$ in an objective function. I suspect this is an error. Please correct this if you still want help, so that's it's clear what you want to find the dual of. – George Tomlinson Oct 14 '13 at 11:14
  • Maybe the formulation is valid, but it seems unlikely as the initial problem is simply max(p) if p is variable, which seems fairly trivial. If p is constant, then so is the objective function, which is even more trivial. – George Tomlinson Oct 14 '13 at 11:52
  • I've put an answer to the problem as you've stated it, but it does seem unusual, so I would check that you've posed the problem correctly @Alti – George Tomlinson Oct 14 '13 at 12:33

1 Answers1

3

I employ the method described by Sebastien Lahaie on the following webpage:

http://www.cs.columbia.edu/coms6998-3/lpprimer.pdf

Find the dual of the following linear program:

Maximize $-15z-\frac{11}{20}w-3a-3b = 132+p$

subject to

$y+9z+\frac{13}{10}w+3a-2b=12$

$x-2z-\frac{7}{20}-a+b=4$

$14z-\frac{69}{20}w+7a-7b+c=42$

where a and b are constant and p, w, x, y and z are variable.

Solution:

Steps 1 and 2.

  1. If necessary, rewrite the objective as a minimization.

  2. Rewrite each inequality as a $ \le$ and rearrange each constraint so that the RHS is 0.

Minimize $15z+\frac{11}{20}w+3a+3b$

subject to

$y+9z+\frac{13}{10}w+3a-2b-12=0$

$x-2z-\frac{7}{20}w-a+b-4=0$

$14z-\frac{69}{20}w+7a-7b+c-42=0$

$-15z-\frac{11}{20}w-3a-3b -132-p = 0$

Steps 3 and 4.

  1. Define a non-negative dual variable for each inequality constraint and an unrestricted dual variable for each equality constraint.

  2. For each constraint, eliminate the constraint and add the term (dual variable $ \times$ LHS of constraint) to the objective. Maximise the result over the dual variables.

Maximise Minimize $15z+\frac{11}{20}w+3a+3b$

$+ \lambda_1 (y+9z+\frac{13}{10}w+3a-2b-12)$

$+ \lambda_2(x-2z-\frac{7}{20}w-a+b-4)$

$+ \lambda_3(14z-\frac{69}{20}w+7a-7b+c-42)$

$+ \lambda_4(-15z-\frac{11}{20}w-3a-3b -132-p)$

Step 5. Rewrite the objective so that it consists of terms involving only dual variables and constants plus several terms of the form (primal variable $\times$ expression with dual variables).

Maximise Minimise $(3a-2b) \lambda_1 + (b-a) \lambda_2 + 7(a-b) \lambda_3 - 3(a+b) \lambda_4+3a+3b$

$+w( \frac{11}{20} + \frac{13}{10} \lambda_1 -\frac{7}{20} \lambda_2 -\frac{69}{20} \lambda_3 -\frac{11}{20} \lambda_4)$

$+x \lambda_2$

$+y \lambda_1$

$+z(15+9 \lambda_1 -2 \lambda_2 +14 \lambda_3 -15 \lambda_4)$

Step 5. Remove each term of the form (primal variable $\times$ expression with dual variables) and replace with a constraint of the form

expression $\ge 0$ if the primal variable is non-negative.

expression $\le 0$ if the primal variable is non-positive.

expression $= 0$ if the primal variable is unrestricted.

Maximise $(3a-2b) \lambda_1 + (b-a) \lambda_2 + 7(a-b) \lambda_3 - 3(a+b) \lambda_4+3a+3b$

$\frac{11}{20} + \frac{13}{10} \lambda_1 -\frac{7}{20} \lambda_2 -\frac{69}{20} \lambda_3 -\frac{11}{20} \lambda_4 = 0$

$ \lambda_1 = 0$

$\lambda_2 = 0$

$15+9 \lambda_1 -2 \lambda_2 +14 \lambda_3 -15 \lambda_4 = 0$

Step 6. If the linear program in step 1 was rewritten as a minimization, rewrite the result of the previous step as a minimization. Otherwise, do nothing.

Minimise $-(3a-2b) \lambda_1 - (b-a) \lambda_2 - 7(a-b) \lambda_3 + 3(a+b) \lambda_4-3a-3b$

($ \lambda_i$ variable, $i = 1..4$ and $a,b$ constant)

subject to

$ \frac{13}{10} \lambda_1 -\frac{7}{20} \lambda_2 -\frac{69}{20} \lambda_3 -\frac{11}{20} \lambda_4 = - \frac{11}{20}$

$ \lambda_1 = 0$

$\lambda_2 = 0$

$9 \lambda_1 -2 \lambda_2 + 14 \lambda_3 -15 \lambda_4 = -15$

Step 7. In this case, since $\lambda_1$ and $\lambda_2$ are $0$, they can be removed from the problem. As such, change the name of $\lambda_3$ to $\lambda_1$ and $\lambda_4$ to $\lambda_2$ , giving

Minimise $ - 7(a-b) \lambda_1 + 3(a+b) \lambda_2-3a-3b$

($ \lambda_i$ variable, $i = 1,2$ and $a,b$ constant)

subject to

$ -\frac{69}{20} \lambda_1 -\frac{11}{20} \lambda_2 = - \frac{11}{20}$

$ 14 \lambda_1 -15 \lambda_2 = -15$

George Tomlinson
  • 1,346
  • 8
  • 11