Question

A primal maximization problem is given.

Maximize

f = 60x₁ + 30x₂

subject to

3x1	+	2x2	≤	150
x1	+	x2	≤	70	.

(a) Form the dual minimization problem. (Use y₁ and y₂ as the variables and g as the function.)
Minimize g =  

  subject to

	≥	60
	≥	30
y1, y2	≥	0	.

(b) Solve both the primal and dual problems with the simplex method.

primal	x1	=
primal	x2	=
primal	f	=
dual	y1	=
dual	y2	=
dual	g	=

Answer 1

a) the dual minimization problem is given by

subject to

  

  

  

b) simplex method for primal problem

primal problem is

maximize f = 60x₁+30x₂

subject to

3x₁+2x₂150

x₁+x₂70

x₁,x₂

introducing slack variables x₃,x₄ to the system we get

subject to

  

  

table 1

	60	30	0	0
basic variable					b
	3	2	1	0	150
	1	1	0	1	70
f	-60 (enters)	-30	0	0	0

table 2

  

basic variable					b
	1			0	50
	0			1	20
f	0	10	20	0	3000

simplex table stops here as the last row values are all non negative

the solution is

primal x₁=50

primal x₂=0

primal f = 3000

solution to the dual problem

introducing surplus variables y₃,y₄ into the problem we get

minimize g = 150 y₁+70y₂+0y₃+0y₄

subject to

3y₁+2y₂+y₃=60

y₁+y₂+y₄=30

  

table 1

basic variable					RHS
	3	2	1	0	60
	1	1	0	1	30
g	-150(enters)	-70	0	0	0

table 2

basic variable					RHS
	1			0	20
	0			1	10
g	0	30	50	0	3000

simplex stops here as the values of last row are non - negative

solution is

dual y₁=20

dual y₂=0

dual g = 3000