CHAPTER 2: GRAPHICAL SOLUTION OF LINEAR PROGRAMMING PROBLEMS

Dr. Miguel Mejía Puente

Problem 2.1
Graphically solve the following LP model.
Maximize Z = 4 X1+ 5 X2
Subject to
2 X1+ 3 X2≤ 120
2 X1+ 1.5 X2≤ 80
With X1, X2≥ 0

Solution
The optimal solution is X1= 20 and X226.7
The optimal value is Z = 213.3

Problem 2.2
Graphically solve the following LP model.
Maximize Z = 1 X1+ 2 X2
Subject to
1 X1≤ 5
1 X2≤ 4
2 X1+ 2 X212
With X1, X2≥ 0

Solution
The optimal solution is X1= 2 y X2= 4
The optimal value is Z = 10

Problem 2.3
Graphically solve the following LP model.
Maximize Z = 3 X1 + 2 X2
Subject to
1 X1≤ 10
1 X2≤ 10
1 X1+ 1 X2≤ 16
With X1, X2≥ 0

Solution

The solution is optimal X1= 10 and X26

The optimal value is Z = 42

2.1
Problem 2.4
Graphically solve the following LP model.
Maximize Z = 3 X1+ 1 X2
Subject to
6 X1+ 4 X2≤ 48
3 X1+ 6 X2≤ 42
With X1, X2≥ 0

Solution

The optimal solution is X1= 8 y X2= 0

The optimal value is Z = 24

Problem 2.5
Graphically solve the following LP model.
Maximize Z = 4 X1+ 1 X2
Subject to
10 X1+ 2 X2 ≤ 30
3 X1+ 2 X2≤ 12
2 X1+ 2 X2≤ 10
With X1, X2≥ 0

Solution

The optimal solution is X1= 2.6 y X2equals 2.1

The optimal value is Z = 12.4

Problem 2.6
The company DYNAMIX manufactures two types of bookshelves. To manufacture these shelves, the company has
two workers each perform a different process. The first worker can work up to 40 hours per
week and is paid $5 for each hour worked, while the second worker can work up to 50 hours per week
and he is paid $6 per hour worked. The information about the shelves is as follows:

Worker 1 Worker 2 Cost of Price of

hour (hour) raw material ($) Sale ($)
Shelf 1 1 2 5.00 30.00
Shelf 2 2 1 5.00 35.00

a) Formulate a linear programming model and solve it graphically.

b) Interpret the results.
c) Suppose that worker 1 can work 6 additional hours, what would the new production plan be and in what
What percentage does the profit vary?
d) Considering the model initially formulated. Suppose that the relationship between the production of shelf type 2 and the
The production of shelf type 1 must be at least 2. What would the new production plan be and by what percentage?
Does the utility vary?
e) Considering the initial data. Formulate the model by defining the decision variables based on the number of
hours.

Solution
a) Formulation
Decision variables
X1number of type 1 shelves that are manufactured and sold in a month
X2number of type 2 shelves that are manufactured and sold in a month
2.2
Maximize Z = (30 - 1*5 - 2*6 - 5) X1(35 - 2*5 - 1*6 - 5) X2
Maximize Z = 8 X1+ 14 X2
Subject to
1 X1+ 2 X2≤ 40
2 X1+ 1 X2≤ 50
With X1, X2≥ 0

The optimal solution is X1= 20 and X2= 10

The optimal value is Z = 300

b) 20 type 1 shelves and 10 type 2 shelves will be produced and sold to achieve a profit of $300.

c) Formulation
Maximize Z = 8 X1+ 14 X2
S. a 1 X1+ 2 X2≤ 46
2 X1+ 1 X2≤ 50
With X1, X2≥ 0

The optimal solution is X1= 18 and X2= 14

The optimal value is Z = 340

18 type 1 shelves will be manufactured and sold.

14 type 2 shelves, to obtain a profit of $340.

d) Formulation
Maximize Z = 8 X1+ 14 X2
Subject to
1 X1+ 2 X2≤ 40
2 X1+ 1 X2≤ 50
- 2 X1+ 1 X2≥ 0
With X1, X2≥ 0

The optimal solution is X1= 8 y X2 = 16

The optimal value is Z = 288

8 type 1 shelves will be manufactured and sold

16 type 2 shelves, to achieve a profit of $288.

Profit decreases by 4%.

e) Formulation
Decision variables
X11number of hours that worker 1 dedicates to producing shelf type 1
X12number of hours that worker 1 dedicates to producing shelf type 2
X21number of hours that worker 2 dedicates to producing shelf type 1
X22number of hours that worker 2 dedicates to producing shelf type 2
Maximize Z = 25 X11+ 30 X225 times115 X12- 6 X21- 6 X22= 20 X115 X12- 6 X21+ 24 X22= 20 X1110 X2212
X11+ 24 X22= 8 X11+ 14 X22
Subject to
X11+ X12≤ 40
X21+ X22≤ 50
2.3
 X11- 0.5 X21= 0
X22- 0.5 X12= 0
With X11, X12, X21, X22≥ 0

Problem 2.7
The company DYNAMIX is engaged in the manufacturing of two products A and B. To manufacture these products, the company
It has three machines; each of them performs a different process on the products. Machine 1 can work
up to 40 hours per week, while machine 2 can work up to 50 hours per week and machine 3 up to 80
hours per week. The technical information of the products, their selling prices, and variable costs are shown in the
next table.

Time in the Time in the Time in the Costs Price of

machine 1 machine 2 machine 3 sales variables ($)
(time) (hour) (hour) ($)
Producto A 0.50 0.50 0.00 100 150
Product B 0.25 0.50 1.00 150 220

a) Formulate a linear programming model and solve it graphically.

b) Interpret the results.
c) Suppose that machine 3 can work 30 additional hours of overtime. If the overtime for this machine is
$10, what is the utility generated by each extra hour used?
d) Considering the initial model, suppose that machine 3 is replaced by machine 4 which can work 40.
hours per week, and requires 1/4 hour to process product A and 1/2 hour to process product B.
This in turn allows the time of machine 1 to process product A to be reduced from 1/2 hour to 1/4.
Right now. Determine if it is advisable to make the change.

Solution

a) Formulation
Decision variables:
X1number of units of product A that will be produced weekly
X2number of units of product B that will be produced weekly

Maximize Z = 50 X1+ 70 X2
Subject to
0.5 X1+ 0.25 X2≤ 40
0.5 X1+ 0.5 X2≤ 50
X2≤ 80
With X1, X2 ≥ 0

The optimal solution is X1= 20 y X2= 80

The optimal value is Z = 6,600

20 units of product A and 80 units of product B will be produced to achieve a profit of $6,600.

c) Formulation
Maximize Z = 50 X1+ 70 X2
Subject to
0.5 X1+ 0.25 X2≤ 40
0.5 X1+ 0.5 X2≤ 50
X2≤ 110
With X1, X2≥ 0

Zero units of product A will be produced.

and 100 units of product B to obtain
a utility of 7,000 - 200 = $6,800.

2.4
The increase in profit is 6,800 - 6,600 = $200. The profit generated by each extra hour is 200 / 20 = $10.

d) Formulación
Maximize Z = 50 X1+ 70 X2
S. a 0.25 X1+ 0.25 X2≤ 40
0.5 X1+ 0.5 X2≤ 50
0.25 X1+ 0.5 X2≤ 40
With X1, X2≥ 0

The optimal solution is X1= 40 and X2= 60

The optimal value is Z = 6,200

So, it is not worthwhile to make the change.

Problem 2.8
The Costa Azul restaurant offers 2 types of menus: one based on meat and the other based on fish. Daily they
sell a maximum of 60 menus.

The fish menu takes 15 minutes to prepare, and the meat menu takes 30 minutes. There are 20 hours of cooking available.
day. It is estimated that at least 3 fish menus will be sold for every 2 meat menus sold. However, it is estimated
that at least 10% of diners will order the meat menu. The net profit from each fish menu is $12,
and the meat is $16.

a) Formulate a linear programming model and solve it graphically.

b) Interpret the results.
c) If it is decided to increase the price of the fish menu, in such a way that the net profits of both menus are
equal. How does this fact affect the initial solution?
d) If it is assumed that 20% of the diners will order the meat menu. How does this fact affect the solution?
initial?

Solution

a) Formulation
Decision variables
X1number of meat menus that will be prepared and sold daily.
X2number of fish menus that will be prepared and sold daily.

Maximize Z = 16 X1+ 12 X2
Subject to
1 X1+ 1 X2≤ 60
0.5 X1+ 0.25 X2 ≤ 20
3 X1- 2 X2≤ 0
0.9 X1- 0.1 X2≥ 0
With X1, X2≥ 0

The optimal solution is X1= 20 and X2= 40

The optimal value is Z = 800.

20 meat menus and 40 fish menus will be prepared and sold to obtain a profit of $800.

2.5
c) Formulation
Maximize Z = 16 X1+ 16 X2
Subject to
1 X1+ 1 X2≤ 60
0.5 X1+ 0.25 X2≤ 20
3 X1- 2 X2≤ 0
0.9 X1- 0.1 X2≥ 0
With X1, X2≥ 0

The optimal solution is the line segment

X1= 20, X2= 40 and X1= 6, X2= 54

The optimal value is Z = 960.

They will prepare and sell 6 meat menus and 54 fish menus to obtain a profit of $960.
However, there are other possible solutions in the line segment (20, 40) and (6, 54).

d) Formulation
Maximize Z = 16 X1+ 12 X2
Subject to
1 X1+ 1 X2≤ 60
0.5 X1+ 0.25 X2≤ 20
3 X1- 2 X2≤ 0
0.9 X1- 0.1 X2≥ 0
0.8 X1- 0.2 X2= 0
with X1, X2≥ 0

The optimal solution is X1= 12 and X2= 48

The optimal value is Z = 768.

12 meat menus and 48 fish menus will be prepared and sold, to achieve a profit of $768.

Problem 2.9
The company DYNAMIX manufactures two types of 35 mm cameras. The production process of the regular cameras
requires two hours of production time in department 1 and three in department 2. Manufacture your model of
luxury requires four hours of time in department 1 and three in department 2. Currently, there are
80 hours of labor are available per week in each of the departments. This labor time is a
a somewhat restrictive factor because the company has a general policy of avoiding overtime, if possible. The
The manufacturer's profit for each standard camera is $30, while the profit for the luxury model is $40.

Previous sales records indicate that, on average, a minimum of 10 regular cameras and 10 can be sold.
luxury per week.

a) Formulate a linear programming model and solve it graphically.

b) Interpret the results.

Solution
a) Formulation
Decision variables
X1number of regular cameras to manufacture.
X2number of luxury cameras to be manufactured.
Maximize Z = 30 X1+ 40 X2
Subject to
2 X1+ 4 X2≤ 80
2.6
 3 X1+ 3 X2≤ 80
1 X1≥ 10
1 X2≥ 10
With X1, X2≥ 0

The optimal solution is X1= 13.3 y X213.3

The optimal value is Z = 933.33

b) 13.3 normal cameras must be manufactured

13.3 luxury cameras to obtain a profit of $933.33.

Problem 2.10
The company DYNAMIX assembles trucks and cars. It takes 60 hours to assemble a truck and 50
hours to assemble a car. The assembly is done by 10 workers, working in shifts of 9 hours a day.
20 days a month. On the assembly line, at least 3 cars must be assembled for each truck. The cost of
Production is $15,000 per truck and $4,000 per car. The company has capital of $210,000.
The selling prices are $25,000 per truck and $8,000 per car.

a) Formulate a suitable linear programming model for this situation, determine the optimal solution graphically, and
interpret the results.
b) Calculate the percentage of resource utilization.
c) A local bank offers the company a loan of $40,000. Do you recommend accepting this loan? If the
the answer is affirmative, how long would it take to pay off the loan? and what is the maximum interest rate that should be paid?
company?

Solution
Decision variables
X1number of trucks produced
and sold monthly
X2number of cars produced
and they sell monthly

Maximize Z = 10000 X1+ 4000 X2

Subject to
60 X1+ 50 X2≤ 1800
15000 X1+ 4000 X2<= 210000
3 X1– X2less than or equal to 0
With X1, X2greater than or equal to 0

6.5 trucks must be produced and sold

28.2 cars to obtain
a monthly profit of $177,647

a) The resources are:

Assembled
60 X1+ 50 X2≤ 1800 is an active restriction.
Therefore, its utilization percentage is 100%.

Capital
15 X1+ 4 X2≤ 210 is an active constraint.
Therefore, their utilization percentage is 100%.

b) Formulation of the LP model

Maximize Z = 10000 X1+ 4000 X2

2.7
Subject to
60 X1+ 50 X2≤ 1800
15000 X1+ 4000 X2<= 250000
3 X1X2<= 0
With X1, X2greater than or equal to 0

8.6 trucks must be produced and sold

25.8 cars to obtain a new one
monthly profit of $188,571.4.

That is, the increase in monthly profit is

$ 10,924.40

I would not recommend accepting the loan.

Problem 2.13
The company DYNAMIX has a machine that operates 150 hours a week distilling orange and grapefruit juice.
concentrates. The machine can distill orange juice at a rate of 25 gallons per hour to obtain 17.5 gallons of
20 gallons of grapefruit juice concentrate to obtain 10 gallons of concentrate. Up to 1,000 gallons of each
concentrate can be stored in separate tanks after processing. The net gain per gallon
Orange or grapefruit juice concentrate is $0.80.

a) Formulate a linear programming model to determine the number of gallons of orange juice and juice of
grapefruit for distillation to maximize net profit.
b) Solve the model graphically. What is the optimal weekly production plan and the total profit?
c) Based on your solution, which of the three resources is mandatory?
d) From the production plan, how many gallons of each concentrate are produced?
e) Graphically determine the sensitivity interval of each objective function coefficient in the optimal solution.
Explain the meaning of each interval in the context of this problem.
f) For each active constraint in the optimal solution, do the following:
f.1) Graphically determine the sensitivity interval of the right side value.
f.2) Calculate the dual price associated with each sensitivity interval found in part f.1). Explain the
meaning of dual price in the context of this problem.
What happens to the optimal solution and total profit if the net gain per gallon of grapefruit juice decreases?
$0.05.

Solution
a) Formulate a linear programming model to determine the number of gallons of orange juice and juice of
grapefruit for distilling to maximize net profit.

Decision variables
N: number of gallons of orange juice that will be distilled per week.
T: number of gallons of grapefruit juice that will be distilled per week.
Objective function
Maximize Z = 0.56 N + 0.4 T
Restrictions
Distillation capacity of the machine
0.04 N + 0.05 T≤ 150
Storage capacity of orange concentrate
0.7 N ≤ 1000
Grapefruit concentrate storage capacity
0.5 T ≤ 1000
Range of Existence
N, T ≥ 0

2.8
b) Solve the model graphically. What is the optimal weekly production plan and the total profit?

The optimal production plan consists of producing 1,428.57 gallons of orange juice and 1,857.14 gallons of grapefruit.
resulting in a profit of $1,542.85

c) Based on your solution, which of the three resources is mandatory?

The machine time and the storage capacity of orange concentrate.

d) From the production plan, how many gallons of each concentrate are produced?

Orange concentrate: (1428.57) (0.7) = 1,000 gallons

Grapefruit concentrate: (1857.14) (0.5) = 928.57 gallons

e) Graphically determine the sensitivity range of each objective function coefficient in the optimal solution.
Explain the meaning of each interval in the context of this problem.

Coefficient of the utility of orange juice: [0.32, +∞[

Coefficient of grapefruit juice utility: [0.0, 0.7]

f) For each active constraint in the optimal solution, do the following:

f.1) Graphically determine the sensitivity interval of the value on the right side.

Machine time restriction: [57.14, 157.14]

Orange concentrate restriction: [875, 2625]

f.2) Calculate the dual price associated with each sensitivity interval found in part f.1). Explain the
meaning of dual price in the context of this problem.

The dual price of the machine time constraint is $8

The dual price of the restriction on orange concentrate storage capacity is $0.34

g) What happens to the optimal solution and total benefit if the net profit per gallon of grapefruit juice decreases?
$0.05.

By decreasing the net profit per gallon of grapefruit juice from $0.40 (0.80x0.5) to $0.375 (0.75x0.5), the optimal solution
remains the same, because this decrease is within the sensitivity range. However, the new benefit
total will be less: 0.56 (1428.57) + 0.375 (1857.14) = $1,496.43.

2.9