Solution: Chapter 5: LP Graph 1

Chapter 5: Linear Programming

1. Let x1 = number of HCC-1 computers to be produced

x2 = number of HCC-2 computers to be produced

Therefore, the LP formulation is

Maximize Z = 4,000x1 + 6,000x2

subject to
25x1 + 30x2  1500
x1  20
x2  30
x 1, x 2  0

Graphical solution:

25x1 + 30x1 = 1500 -----------------(1)

Two points are (0, 50), (60, 0)

x1 = 20 ----------------(2)
x2 = 30 ----------------(3)

x2

60

50
Feasible region

40
C
B
30
A

20

10

x1
10 20 30 40 50 60 70

For A

x1 = 20, x2 = 30, hence A = (20, 30).

Solution: Chapter 5: LP Graph 2

For B

25x1 + 30x2 = 1500

x2 = 30
Or, 25x1 = 1500 – 30  30 = 600
 x1 = 600/25 = 24

 B = (24, 30)

For C

25x1 + 30x2 = 1500

x1 = 20
30x2 = 1500-2520 = 1000
 x2 = 1000/30 = 33.33

 C = (20, 33.33)

Z at A = 4000x1 + 6000x2 = (400020)+(600030) = 260,000

Z at B = (400024)+(600030) = 276,000
Z at C = (400020)+(600033.33) = 279,980

Optimal solution is

C: x1 = 20, x2 = 33.33; Zmax = Rs. 279,980

2. x1 = number of undergraduate courses to be offered
x2 = number of postgraduate courses to be offered

Therefore, the LP formulation is

Minimize Z = 4,200x1 + 6,000x2

x2
subject to
x1 + x2  65
80 x1  35
x2  20
70 x 1, x 2  0

Graphical solution: Feasible region

60
x1 + x2 = 65 -----------------(1)
50
Two points are (0, 65), (65, 0)

40 x1 = 35 ----------------(2)
x2 = 20 ----------------(3)
30 B

20
A

10

x1
10 20 30 40 50 60 70 80
Solution: Chapter 5: LP Graph 3

For A
x1 + x2 = 65
Since x2 = 20
x1 = 65-20=45, hence A = (45, 20).

For B

x1 + x2 = 65
x1 = 35
x2 = 65– 35= 30

 B = (35, 30)

Z at A = 4200x1 + 6000x2 = (420045)+(600020) = 309,000

Z at B = (420035)+(600030) = 327,000
Optimal solution is

A: x1 = 45, x2 = 20

Zmin = $ 309,000
Solution: Chapter 5: LP Graph 4

3. Let x1 = number of tables to be produced

x2 = number of chairs to be produced

Therefore, the LP formulation is

Maximize Z = 120x1 + 80x2

subject to
3x1 + 2x2  200
2x1 +2x2  180
x1 + x2  40
x2 – 2x1  0

Graphical solution:

3x1 + 2x2 = 200 -----------------(1)

Two points are (0, 100), (66.67, 0)

x1 +x2 = 90 ----------------(2)

Two points are (0, 90), (90, 0)

x1 + x2 = 40 ----------------(3)

Two points are (0, 40), (40,0)

x2 = 2x1
Two points are (50,100), (25,50)

x2

100

90

80

70

60
Feasible region
50
40 
B
30 
A 
20

10

x1

10 20 30 40 50 60 70 80 90 100
Solution: Chapter 5: LP Graph 5

For A

x1 + x2 = 40
x2 = 2x1
x1 + 2x2 = 40 x1 = 40/3 = 13.33
x2 = 26.66,
Hence A = (13.33, 26.66).

B = (0, 40)

Objective function value calculation:

Z at A = 120x1 + 80x2 = (12013.33)+(8026.66) = RM 3732.4
Z at B = (1200)+(8040) = RM 3200

Hence optimal solution is

A: x1 = 13.33, x2 = 26.66

Zmax = RM 3732.4

Remark: Constraints (1) and (2) are redundant.

4. Let x1 = number of acres to be allocated for tomatoes

x2 = number of acres to be allocated for lettuce
x3 = number of acres to be allocated for radishes

Revenue from tomatoes per acre of land = 20001.00 = Rs. 2000

Per acre fertilizer expenditure for tomatoes = 1000.50 = Rs. 50
Per acre expenditure due to labor for tomatoes = 520 = Rs. 100.

Hence profit from 1 acre of tomatoes = Rs (2000-50-100) = Rs. 1850

Similarly profit from 1 acre of letture and 1 acre of radishes are Rs 2080 and Rs. 1875,
respectively. Hence the LP formulation is

Maximize Z = 1850x1 + 2080x2 + 1875x3

subject to
x1 + x2 + x3 = 100
5x1 +6x2 + 5x3  400
x1, x2, x3  0

5. Let x1 = number of newspaper ads

x2 = number of radios ads

Therefore, the LP formulation is the following:

Maximize Z = 6,000x1 + 2,000x2

subject to
Solution: Chapter 5: LP Graph 6

600x1 + 400x2  7200

x1 + x2  15
x1  2
x2  2
x1, x2  0

Graphical solution:

600x1 + 400x1 = 7200 -----------------(1)

Two points are (0, 18), (12, 0)

x1 + x2 = 15----------------(2)

Two points are (0, 15), (15, 0)

x1 = 2 --------------------(3)
x2 = 2 --------------------(4)

x2

20

18

16 Feasible region
A
14
B
12
10
C
8

6 

4

2

x1

2 4 6 8 10 12 14 16 18 20

For A

600x1 + 400x2 = 7200

x1 = 2,
 400x2 = 7200-1200 = 6000
 x2 = 6000/400 = 15
Solution: Chapter 5: LP Graph 7

Hence A = (2, 15).

For B

x1 + x2 = 15
x1 = 2
x2 = 13

 B = (2, 13)

For C

600x1 + 400x2 = 7200

x1 + x2 = 15
Or, 600x1 = 7200-400(15-x1) = 7200-6000+400x1
Or, 200x1 = 1200
 x1 = 6, x2 = 9

 C = (6, 9)

Objective function value calculation:

Z at A = 6,000x1 + 2000x2 = (60002)+(200015) = 42,000

Z at B = (60002)+(200013) = 38,000
Z at C = (60006)+(20003) = 54,000

Optimal solution is: C (6, 9); Zmax = 54,000.

6. Let xDE = number of enamel paint cans produced at Dubai plant

xDL = number of latex paint cans produced at Dubai plant
xAE = number of enamel paint cans produced at Abu Dhabi plant
xAL = number of Latex paint cans produced at Abu Dhabi plant

Profit from one can of enamel paint produced at Dubai plant is 8-5 = $3, and the profit
from one can of latex paint produced at Dubai plant is 7-4.50 = $2.50. Similarly, profits
from one can of enamel and one can of latex paint produced at Abu Dhabi plant are: $2,
and $4, respectively.

The LP formulation is the following:

Maximize Z = 3xDE + 2.5xDL +2xAE + 4xAL

subject to
xDE  500
xDL  500
xDE + xDL  500
xAE + xAL  800
5xDE + 4.5xDL  20,000
6xAE + 3xAL  30,000
xDE + xAE  600
Solution: Chapter 5: LP Graph 8

xDL + xAL  800

xDE , xDL , xAE , xAL  0

7. Let x1 = number of PCs for production dept.

x2 = number of PCs for marketing dept.
x3 = number of PCs for finance dept.

Therefore, the LP formulation is

Maximize Z = 5x1 + 3x2 + 2x3

subject to
x1 + x2 + x3  20
x1  5
x3  x2/2
x2  x1/3
x1, x2, x3  0

Or,

Maximize Z = 5x1 + 3x2 + 2x3

subject to
x1 + x2 + x3  20
x1  5
-x2 + 2x3  0
-x1 + 3x3  0
x1, x2, x3  0

8. Let x1 = number of untrained workers

x2 = number of semi-trained workers
x3 = number of highly trained workers

Total cost of providing training to an untrained workers is (28+35)5 = $315

Similarly, the costs of providing training to a semi-trained and highly-trained workers are
$450.5 and $367.5, respectively.

The required LP formulation is:

Minimize Z = 315x1 + 450.5x2 + 367.5x3

subject to x1 + x2 + x3  25
28x1 +23x2 + 15x3  700
35x1 +30x2 + 20x3  775
x1, x2, x3  0

9. Let x1= the quantity of phosphate used

x2 = the quantity of potassium used

Then the problem can be formulated as a linear programming as follows:

Solution: Chapter 5: LP Graph 9

Minimize Z = 5x1+6x2
subject to:
x1+ x2 =1000
x1  300
x2  150
x1, x2  0.

(b) x1 + x2 = 1000

If x1 = 0, x2 = 1000
If x2 = 0, x1 = 1000

Hence the two points are (0,1000), (1000,0).

The graph is the following:

x2

B
1000
900

800

700 A

600

500

400

300

200

100

x1
100 200 300 400 500 600 700 800 900 1000

The feasible region is on the line segment AB.

A = (300,700), B = (0,1000)
Z at A = (5300) + (6700) = 570
Z at B = (50) + (61000) = 6000
Hence the best solution is to mix 300 pounds of phosphate and 700 pounds of potassium and
minimum cost will be RM 5,700.
10. The given LPP is:

maximize Z = 12x1+8x2
subject to:
x1 + x2 ≤ 20 (1)
3x1 + x2 ≥ 30 (2)
2x1 + 6x2 ≥ 60 (3)
2x1 – x2 ≥ 0 (4)
x1, x2 ≥ 0
Solution: Chapter 5: LP Graph 10

x1+ x2 = 20
Two points are (0,20), (20,0).

3x1+x2 = 30
Put x1 = 0, x2 = 30,  (0, 30)
Put x2 = 0, x1 = 10,  (10, 0)

2x1+6x2 = 60
Put x1 = 0, x2 = 10,  (0, 10)
Put x2 = 0, x1 = 30,  (30, 0)

2x1- x2 = 0 or 2x1 = x2; Two points are: (5, 10), (10, 20).

Let us plot the points one by one and obtain the following graph:

40

35

30
④
25

20

15
Feasible region
D
10 C ①
B ② ③
5 A

O
5 10 15 20 25 30 35 40
Solution: Chapter 5: LP Graph 11

For A
3 x1  x 2  30
2 x1  6 x 2  60
or , 2 x1  6(30  3 x1 )  60
or , 2 x1  180  18 x1  60
or ,  16 x1  60  180
or , 16 x1  120
120
 x1   7. 5
16
 x 2  30  3  7.5  7.5
 A  (7.5, 7.5)
For B

x1  x 2  20
2 x1  6 x 2  60
or , 2 x1  6( 20  x1 )  60
or , 2 x1  120  6 x1  60
or ,  4 x1  60  120
or , 4 x1  60
 x1  15
 x 2  20  15  5
 B  (15, 5)

For C
3 x1  x 2  30
2 x1  x 2  0
or , 3x1  2 x 2  30
 x1  6
 x 2  12
 C  (6, 12)
For D

x1  x 2  20
2 x1  x 2  0
or , x1  2 x 2  20
20
 x1 
3
40
 x2 
3
 D  ( 20 / 3, 40 / 3)
Solution: Chapter 5: LP Graph 12

Now we calculate the objective function values at the four corner points :

Z at A  12 x1  8 x 2
 12  7.5   8  7.5
 150
Z at B  12 x1  8 x 2
 12  15   8  5
 220
Z at C  12 x1  8 x 2
 12  6    8  12 
 156
Z at D  12 x1  8 x 2
 20   40 
 12    8  
 3   3 
 186.67

Z max  220 at x1  15, x 2  5.

11. Minimize Z = 2x1 + 3x2

subject to:

x1  125
x1 + x2  350
2x1 + x2  600
x 1, x 2  0

Graphical solution:
x2
x1 = 125 ----------------(1)
x1 + x2 = 350 -----------------(2)

600

550  (0, 350), (350, 0)


500 2x1 + x2 = 600 -----------------(3)
 (0, 600), (300, 0)
450
C Feasible region
400

350

300
250
A
200

150

100 B 
50

50 100 150 200 250 300 350 400 450 500 550 600
Solution: Chapter 5: LP Graph 13

x1

For A

x1 = 125, x1+x2 = 350

x2 = 350-125 = 225
Hence A = (125, 225).

For B

2x1 + x2 = 600
x1+x2 = 350
Or, 2x1 = 600 – (350-x1) = 600 – 350 + x1
 x1 = 600-350 = 250
x2 = 350-250 = 100

 B = (250, 100)

For C

x1 = 125
2x1 + x2 = 600

x2 = 600-(2125) = 600 – 250 = 350

 C = (125, 350)
Solution: Chapter 5: LP Graph 14

Calculation of objective function values:

Z at A = 2x1 + 3x2 = (2125)+(3225) = 925

Z at B = (2250)+(3100) = 800
Z at C = (2125)+(3350) = 1300

Optimal solution is:

B = (250, 100)
Zmin = 800

12. Given LPP is:

Minimize Z = 2x1 + 3x2

subject to:

2x1 + 7x2  22
x1 + x2  6
5x1 + x2  10
x1, x2  0

Graphical solution:

2x1 + 7x2 = 22 -----------------(1)

 (0, 3.1), (11, 0)

x1x+ x2 = 6 -----------------(2)
 2(0, 6), (6, 0)
125x + x = 10 -----------------(3)
1 2

11
 (0, 10), (2, 0)

10 D

9
Feasible region
8

6
5
4 C

2  B 
1

x1
O
1 2 3 4 5 6 7 8 9 10 11 12
A
Solution: Chapter 5: LP Graph 15

 

For A

A = (11, 0), D = (0, 10)

For B

2x1 + 7x2 = 22
x1+x2 = 6
Or, 2x1 = 22 – 7(6-x1) = 22 – 42 + 7x1
 5x1 = 20
x1 = 4
x2 = 2

 B = (4, 2)

For C

5x1 + x2 = 10
x1 + x2 = 6
5x1 = 10-(6-x1) = 10 – 6 + x1
or, 4x1 = 4
Solution: Chapter 5: LP Graph 16

or, x1 = 1
x2 = 5
 C = (1, 5)

Calculation of objective function values:

Z at A = 2x1 + 3x2 = (211)+(30) = 22

Z at B = (24)+(32) = 14
Z at C = (21)+(35) = 17
Z at D = (20)+(310) = 30

Optimal solution is:

B = (4, 2)
Zmin = 14

13. a) Given LPP is:

Maximize Z = 2x1 + x2
subject to:

x1 + x2  6
3x1 + 2x2  16
x2  9
x1, x2  0

Graphical solution:

x1 + x2 = 6 -----------------(1)

 (0, 6), (6, 0)

3x1 + 2x2 = 16 -----------------(2)

 (0, 8), (5.33, 0)

x2 = 9 -----------------(3)
Solution: Chapter 5: LP Graph 17

x2

12
Feasible region
10

D
8
C

B
2

x1
0 A
2 4 6 8 10 12

Feasible region is not bounded and given LPP is of maximization type. Hence the given problem
has no finite solution.

b) Minimize Z = -2x1 + 5x2

subject to:

x1 + x2  7
10x1 + 7x2  40
x1, x2  0

Graphical solution:

x1 + x2 = 7 -----------------(1)

 (0, 7), (7, 0)

10x1 + 7x2 = 40 -----------------(2)

 (0, 5.7), (4, 0)
Solution: Chapter 5: LP Graph 18

x2

10

6
5
4

x1

1 2 3 4 5 6 7 8 9 10

The linear programming problem does not have feasible solution.

c) Maximize Z = 3x1 + 2x2

subject to
6x1 + 4x2  24
x1  3
x 1, x 2  0

Graphical solution:

6x1 + 4xx1 = 24 -----------------(1)

2

(0, 6), (4, 0)

10
x1 = 39 ----------------(2)

8  

7
C
6
5
4
Feasible region
3

2
B
1

x1

1 2 3 A 4 5 6 7 8 9 10
Solution: Chapter 5: LP Graph 19

A = (3, 0)

For B

6x1 + 4x2 = 24
x1 = 3
Or, 4x2 = 24 – 18 = 6
 x2 = 6/4 = 3/2

 B = (3, 3/2)

Further, C = (0, 6)

Objective function value calculation:

Z at A = 3x1 + 2x2 = (33)+(20) = 9

Z at B = (33)+(23/2) = 12
Z at C = (30)+(26) = 12

Multiple Optimal solutions exist. Two optimal solutions are:

B(3, 3/2), C (0, 6) and Zmax = 12

________