International University, HCMC School of IEM – LSCM Program

Student Full name:

Student ID:

OPERATION RESEARCH
HOMEWORK 1
Problem 1:
Larry Edison is the director of the Computer Center for Buckly College. He now
needs to schedule the staffing of the center. It is open from 8 A.M. until midnight.
Larry has monitored the usage of the center at various times of the day, and
determined that the following number of computer consultants are required:

Two types of computer consultants can be hired: full-time and part-time.

The full-time consultants work for 8 consecutive hours in any of the following
shifts: morning (8 A.M.–4 P.M.), afternoon (noon–8 P.M.), and evening (4 P.M.–
midnight).
Full-time consultants are paid $40 per hour. Part-time consultants can be hired to
work any of the four shifts listed in the above table. Part-time consultants are paid
$25 per hour.
An additional requirement is that during every time period, there must be at least
2 full-time consultants on duty for every part-time consultant on duty. Larry would
like to determine how many full-time and how many part-time workers should
work each shift to meet the above requirements at the minimum possible cost.
Formulate a linear programming model for this problem.
Solution:
Let
𝑥1 : The number of full-time consultants work on morning shift (8AM – 4PM)
𝑥2 : The number of full-time consultants work on afternoon shift (noon – 8PM)
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

𝑥3 : The number of full-time consultants work on evening shift (4PM – midnight)

𝑦1 : The number of part-time consultants work on shift (8AM – noon)
𝑦2 : The number of part-time consultants work on shift (noon – 4PM)
𝑦3 : The number of part-time consultants work on shift (4PM – 8PM)
𝑦4 : The number of part-time consultants work on shift (8PM – midnight)

The objective function: Minimize possible cost

Min 𝑍 = 320(𝑥1 + 𝑥2 + 𝑥3 ) + 100(𝑦1 + 𝑦2 + 𝑦3 + 𝑦4 )
Subject to:
- Minimum number of constants requires on shift 8AM – noon
𝑥1 + 𝑦1 ≥ 4
- Minimum number of constants requires on shift noon – 4PM
𝑥1 + 𝑥2 + 𝑦2 ≥ 8
- Minimum number of constants requires on shift 4PM – 8PM
𝑥2 + 𝑥3 + 𝑦3 ≥ 10
- Minimum number of constants requires on shift 8PM – midnight
𝑥3 + 𝑦4 ≥ 6
- At least 2 full-time consultants on duty for every part-time
𝑥1 ≥ 2𝑦1
𝑥1 + 𝑥2 ≥ 2𝑦2
𝑥2 + 𝑥3 ≥ 2𝑦3
𝑥3 ≥ 2𝑦4
and
𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 , 𝑦4 ≥ 0
𝑥1 , 𝑥2 , 𝑥3 , 𝑦1 , 𝑦2 , 𝑦3 , 𝑦4 are integers

Problem 2:
The Primo Insurance Company is introducing two new product lines: special risk
insurance and mortgages. The expected profit is $5 per unit on special risk
insurance and $2 per unit on mortgages.
Management wishes to establish sales quotas for the new product lines to
maximize total expected profit. The work requirements are as follows:
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

(a) Formulate a linear programming model for this problem.

(b) Use the graphical method to solve this model.
Solution:
(a)
Let
𝑥1 : Number of units of Special risk insurance to produce
𝑥2 : Number of units of Mortgages to produce
The objective function: Maximize total profit
Maximize 𝑍 = 5𝑥1 + 2𝑥2
Subject to:
Underwriting department constraint:
3𝑥1 + 2𝑥2 ≤ 2400
Administration department constraint:
𝑥2 ≤ 800
Claims department constraint:
2𝑥1 ≤ 1200
and
𝑥1 ≥ 0, 𝑥2 ≥ 0

(b)
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

We have the figure

At the point (0,0): Z = 0

At the point (0,800): Z = 1600
At the point (800/3, 800): Z = 2933.33
At the point (600,300): Z = 3600 (optimal)
At the point (600,0): Z = 3000
In conclusion, the Primo Insurance Company need produce 600 units of Special
Risk Insurance and 300 units of Mortgages.
Problem 3:
Farmer Jane owns 45 acres of land. She is going to plant each with wheat or corn.
Each acre planted with wheat yields $200 profit; each with corn yields $300 profit.
The labor and fertilizer used for each acre are given in table below. One hundred
workers and 120 tons of fertilizer are available.
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

(a) Formulate a linear programming model for this problem.

(b) Use the graphical method to solve this model.
Solution:
(a)
Let
𝑥: number of acres of wheat
𝑦: number of acres of corn
Objective function: Maximize profit
Maximize 𝑍 = 200𝑥 + 300𝑦
Subject to:
- Land constraint:
𝑥 + 𝑦 ≤ 45
- Labor constraint:
3𝑥 + 2𝑦 ≤ 100
- Fertilizer constraint:
2𝑥 + 4𝑦 ≤ 120
- Non-negative constraint:
𝑥 ≥ 0, 𝑦 ≥0
(b)
We have the figure:
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

At the point (0,0): Z = 0

At the point (0,30): Z = 9000
At the point (20,20): Z = 10000 (optimal)
At the point (33.3,0): Z = 6666.6
In conclusion, Jane should plant 20 acres of wheat and 20 acres of corn to reach
maximize profit at $10000.
Problem 4:
Use the graphical method to find all optimal solutions for the following model:
Maximize 𝑍 = 500𝑥1 + 300𝑥2 ,
Subject to:
15𝑥1 + 5𝑥2 ≤ 300
10𝑥1 + 6𝑥2 ≤ 240
8𝑥1 + 12𝑥2 ≤ 450
and
𝑥1 ≥ 0, 𝑥2 ≥ 0.
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

Solution:

Because the profit line has the same slope with constraint
10𝑥1 + 6𝑥2 ≤ 240, all of points that belongs to the orange line segment
(contain two points (2.5, 35.8) and (15,15)) are optimal solutions to get highest
profit at $12000.
Problem 5:
Use the graphical method to find all optimal solutions for the following model:
Minimize 𝑍 = 3𝑥1 + 2𝑥2 ,
Subject to:
𝑥1 + 2𝑥2 ≤ 12
2𝑥1 + 3𝑥2 = 12
2𝑥1 + 𝑥2 ≥ 8
and
𝑥1 ≥ 0, 𝑥2 ≥ 0.
Solution:
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

Feasible region is the line segment passing through 2 points (3,2) and (6,0).
We check 2 points:
At the point (3,2): Z = 13 (optimal)
At the point (6,0): Z = 18
In conclusion, the optimal solution is Z = 13 at 𝑥1 = 3, 𝑥2 = 2.
Problem 6:
This is your lucky day. You have just won a $10,000 prize. You are setting aside
$4,000 for taxes and partying expenses, but you have decided to invest the other
$6,000. Upon hearing this news, two different friends have offered you an
opportunity to become a partner in two different entrepreneurial ventures, one
planned by each friend. In both cases, this investment would involve expending
some of your time next summer as well as putting up cash. Becoming a full
partner in the first friend’s venture would require an investment of $5,000 and
400 hours, and your estimated profit (ignoring the value of your time) would be
$4,500. The corresponding figures for the second friend’s venture are $4,000
and 500 hours, with an estimated profit to you of $4,500. However, both friends
are flexible and would allow you to come in at any fraction of a full partnership
you would like. If you choose a fraction of a full partnership, all the above
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

figures given for a full partnership (money investment, time investment, and
your profit) would be multiplied by this same fraction.
Because you were looking for an interesting summer job anyway (maximum of
600 hours), you have decided to participate in one or both friends’ ventures in
whichever combination would maximize your total estimated profit. You now
need to solve the problem of finding the best combination.
(a) Formulate a linear programming model for this problem.
(b) Use the graphical method to solve this model. What is your total estimated
profit?
Solution:
(a)
Let
𝑥1 : Fraction of full partnership in the first friend's venture
𝑥2 : Fraction of full partnership in the second friend's venture
The objective function: Maximize the profit
Maximize 𝑍 = 4500𝑥1 + 4500𝑥2
Subject to:
- Fraction constraint:
𝑥1 ≤ 1, 𝑥2 ≤ 1
- Total investment does not exceed 6000$
5000𝑥1 + 4000𝑥2 ≤ 6000
- Maximum time is 600 hours
400𝑥1 + 500𝑥2 ≤ 600
- Non-negative constraint:
𝑥1 ≥ 0, 𝑥2 ≥ 0
(b)
International University, HCMC School of IEM – LSCM Program
Student Full name:
Student ID:

At the point (0,0): Z = 0

At the point (0,1): Z = 4500
At the point (0.25,1): Z = 5625
At the point (0.67,0.67): Z = 6000 (optimal)
At the point (1,0.25): Z = 5625
At the point (1,0): Z = 4500
2
In conclusion, you can invest the fraction of to both of the friend’s venture to
3
achieve maximum profit of 6000$.