Answer to Question #114084 in Operations Research for Cross

Question

1 Maximize z = 3a + b + 2c Subject to: 1. a + b + 3c  30 2. 2a + 2b + 5c  24 3. 4a + b + 2c  36 4. a,b,c  0 NB : a= Computers b= Network devices c= IP cameras Z= Performance -Numbers are costs. The problem above consist of maximizing the performance of our computer network by reducing the total cost.

Answer 1

In slack form: 

Maximize z = 3a + b + 2c 

Subject to: d = 30 – a – b - 3c 

  e = 24 - 2a - 2b - 5c  f = 36 - 4a - b - 2c 

  a,b,c, d,e,f ≥ 0 

 

The basic solution is a = 0, b = 0, c = 0, d = 30, e = 24, f = 36, i.e. (0, 0, 0, 30, 24, 36). z = 0. 

 

1. Pivot using a. 

  When we substitute the basic solution into inequality (1), a  30. From 2., a  24/2 = 12. From 3., a  9. Therefore, we can increase a only by 9. So we swap a and f by rewriting equation (3) as a = 9 – b/4 – c/2 – f/4 and substituting it into all other constraints. Maximize z = 3(9-b/4 – c/2 –f/4) + b + 2c 

Subject to: d = 30 – (9-b/4 – c/2 –f/4) – b - 3c 

  e = 24 - 2(9-b/4 – c/2 –f/4) - 2b - 5c 

  a = 9 -b/4 – c/2 –f/4 

  a,b,c, d,e,f ≥ 0 

 

Maximize z = 27 + b/4 + c/2 – 3f/4 

Subject to: 1. a = 9 -b/4 – c/2 –f/4 

2. d = 21 – 3b/4 – 5c/2 + f/4 

  3. e = 6 - 3b/2 – 4c + f/2 

  4. a,b,c, d,e,f ≥ 0 

 

The basic solution is b = 0, c = 0, f=0, a = 9, d = 21, e = 6 i.e. (9,0,0, 21, 6,0). z = 27. 

 

2. Pivot using b or c. Pick c. 

Constraint 1 limits c to 18, 2 limits c to 42/5, and 3 limits it to 3/2. Therefore, rewrite equation (3) and swap e and c. 

 

Maximize z = 111/4 + b/16 – e/8 – 11f/16 

Subject to: 1. a = 33/4 – b/16 – e/8 – 5f/16

2. c = 3/2 – 3b/8 – e/4 + f/8

3. d = 69/4 + 3b/16 + 5e/8 – f/16

4. a,b,c, d,e,f ≥ 0

The basic solution is b = 0, e = 0, f=0, a = 33/4, c = 3/2, d=69/4 i.e. (33/4, 0, 3/2, 69/4, 0, 0). 

z = 111/4. 

3. Pivot using b.

The three constraints give bounds of 132, 4, and infinity (because d increases as b increases). Therefore rewrite equation (2) and swap b and c. 

Maximize z = 28 -c/6 – e/6 – 2f/3 

Subject to: 1. a = 8 + c/6 + e/6 – f/3

2. c = 4 – 8c/3 – 2e/3 + f/3

3. d = 18 – c/2 + e/2

4. a,b,c, d,e,f ≥0

The basic solution is (8, 4, 0, 18, 0, 0). z = 28.