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.
Comments