NED UNIVERSITY OF ENGINEERING & TECHNOLOGY

Master of Engineering (Industrial/Manufacturing)

2nd Semester Examination – 2005, Batch 2004-2005
Subject: OPERATIONS RESEARCH (CI-505)
Date: 15-11-2005
Maximum Marks: 70 Time: 3 hours

Instructions: 1. All questions carry equal marks. Question No. 1 is compulsory.

3. Attempt any four (4) out of the remaining 7 questions.
4. Use of any supplementary material, other than that provided is prohibited.

Q1) A local Pakistani organization is considering collaborating with a major Chinese enterprise in assembling
and marketing of a variety of electronics household products throughout the country. These products are
intended to be affordable and reliable though not as elegantly styled and featured as most others in the
market.

The company has set a target of achieving at least 15 percent of the market share within 5 years of
launching the products. An operations management consultant has suggested that the organization tries to
perceive its decision-making needs within the contextual framework (Figure 1 below) for managing most
of its operations.

Figure 1: A Rationale for the Development of MS / OR

Given the above scenario, give your comments on the following issues:
i. What decisions in the early stages of operations can lend complexity to decision making? (2)
ii. What could be the likely impact of such decisions on costs? (2)
iii. Which operations research models can help the company to address such decisions? (2)

1
 iv. How would a goal programming approach work for the company to help it achieve the desired market
share? What should be some of the other goals considered? (2)
v. In the wake of intense competition, which decisions will need to be taken quickly? (2)
vi. Will a transportation model be of any use to the company? (2)
vii. What other models will be useful? (2)

Q2) An engineering company manufactures two gear boxes, ‘Manual’ (M) and ‘Automatic’ (A). There are four
stages in the production of these, with details of required times and weekly availabilities given in the table
below. The company makes a profit of Rs 640 on each Manual sold and Rs 1,000 on each Automatic.

Time required
Stage in Time available
(hours per unit)
manufacture (hours a week)
M A
1) Foundry 3 5 7,500
2) Machine Shop 5 4 10,000
3) Assembly 2 1 3,500
4) Testing 1 1 2,000

The optimal solution for this problem (profit maximization), using the simplex method of linear
programming, is shown below, where S1…. S4 are slack variables associated with the four resources.

Basic M A S1 S2 S3 S4 Solution
Z 0 0 180 0 0 100 1,550,000
A 0 1 0.50 0 0 -1.50 750
S2 0 0 0.50 1 0 -6.50 750
S3 0 0 0.50 0 1 -3.50 250
M 0 0 -0.50 0 0 2.50 1250

i. What are the quantities of M and A being manufactured per week? (2)
ii. The company realizes some resources are surplus and these could be utilized to enhance the weekly
profit. Which amongst the scarce resources should be given priority and how many of its extra units
should be engaged? (4)
iii. A known subcontractor who has testing facilities available has made an offer to the gear box
manufacturer to avail these at a cost of Rs 1000 per hour. If the manufacturer does not consider the
option in part (b) above, should he accept the subcontractor’s offer? (2)
iv. A new ‘Semi-automatic, gear box is proposed which needs 4, 4, 1, and 1 hours respectively in each
manufacturing stage and is expected to yield a profit of Rs 800 a unit. Should the company start
making the new product? (3)
v. In order to make the packaging of its products more robust, the company has decided to divert required
resources from its other product line. Each unit of M will need 2 hours and each unit of A will need 3
hours of this facility. A total of 5000 hours per week can be made available. Is this capacity sufficient
to continue producing the current product mix? (3)

Q3) Three refineries with capacities of 6, 5, and 6 million gallons, respectively, supply three distribution areas
with daily demands of 4, 8, and 7million gallons, respectively. Gasoline is transported to the three
distribution areas through a network of pipelines. The transportation cost is 10 cents per 1000 gallons per
pipeline mile. The table below gives the mileage between the refineries and the distribution areas.
Refinery 1 is not connected to distribution area 3.

Distribution Area
1 2 3
1 120 180 -
Refinery 2 300 100 80
3 200 250 120

2
 A necessary condition is that distribution area 1 must receive all its demand. Additionally, any shortages at
areas 2 and 3 will incur a penalty cost of 5 cents per gallon.

i. Formulate the problem as a transportation model. (4)

ii. Solve the problem and determine an optimal distribution plan for the refinery including the cost. (8)
iii. Determine the cost of the penalty incurred by the distribution areas. (2)

Q4) The investment committee of a corporation is deciding projects to

fund for the next year. Many departments have submitted Project Capital Net Present
proposals, which have passed some screening tests. All of the Required Value
remaining projects (shown in the accompanying table) are (millions) (millions)
attractive; the net present value and the investment capital required 1 Rs 7.33 m Rs 8.83 m
are also shown. 2 4.64 m 5.58 m
3 5.88 m 7.04 m
A total of Rs 25 million of capital is available for investments. The 4 2.35 m 2.81 m
committee has also identified certain preferences and these are: 5 6.14 m 7.19 m
a) Exactly two projects must be selected from projects 1, 2, 6 9.46 m 12.31 m
and 3. 7 6.15 m 6.99 m
b) No more than two projects may be selected from projects 4, 5, 6, and 7.
c) Project 4 is contingent upon project 3.

i. Develop an integer programming formulation for the above problem (with the precise notational
system), the objective being to maximize the net present value of the selected projects. (8)
ii. Continuing with the information for part (i) above, in the Second Year Cash
second year some projects require cash, while others Project Required Generated
generate cash. To the preferences above, add the
1 Rs 0.39 m 0
requirement that the projects selected cannot require more
2 0.52 m 0
second-year cash than they generate, in the aggregate. The
3 0 0.35 m
second year cash information is given in the
4 0.57 m 0
accompanying table. Incorporate this requirement in the
5 0 0.27 m
formulation in part (i) above as a separate constraint. (4)
6 0 0.38 m
iii. How do generating cutting planes help in the ILP solution
7 0 0.10 m
process? (2)

Q5) All trucks traveling on the Gwadar Coastal Highway are required to stop at a weigh station. Trucks arrive at
the weigh station at the rate of 200 per 8-hour day (Poisson distributed), and the station can weigh, on the
average, 220 trucks per day (Exponential distributed).

i. Determine the average number of trucks waiting, the average time spent at the weigh station by each
truck, and the average waiting time before being weighed for each truck. (6)
ii. If the truck drivers find out they must remain at the weigh station longer than 15 minutes on the
average, they will start taking a different route or traveling at night, thus depriving the Govt. of
Balochistan of taxes. The state estimates it loses Rs 2,500 in taxes per year for each extra minute that a
truck must remain at the weigh station. A new set of scales will have the same service capacity as the
present set of scales, and it is assumed that arriving trucks would line up equally behind the two set of
scales. It would cost Rs 4,000,000 per year to operate the new scales. Should the state install the new
set of scales? (8)

Q6) A major city has been named for a summer Olympic Games. Municipal officials are concerned about the
ability of the existing highway network to handle the volume of vehicles converging on Olympic Village.
All vehicular traffic must cross a river via one bridge and then choose different routes (as illustrated in the
figure below) to the village.

3
 The network indicates flow capacities along each arc in both directions (in 1,000s of vehicles per hour).

i. Determine the maximum number of vehicles per hour that can reach the Olympic Village via the
current network of highways. Clearly identify the different paths that are feasible and the
corresponding flows on these. (12)
ii. Which route (highway) is the most restrictive to the maximum capacity achievable? (2)

Q7) A company is planning an automated two-way conveyor system to move materials between areas within its
production facility. The table below indicates the feasible connections between the 15 areas and the cost of
installing a conveyor linkage between two areas (in monetary units of 10,000s).

From To Area
Area 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15
1 - 5 4 10 8
2 5 - 7.5 6
3 4 - 6 8
4 7.5 - 8 7 4.5
5 10 6 6 8 - 7.5 8.5 6.5
6 8 7.5 - 6
7 8 8.5 6 - 7.5 5 10
8 7 6.5 7.5 - 6 7 5
9 4.5 6 - 8 5
10 7 8 - 7 8 6
11 5 5 7 - 6 9 7
12 10 6 - 12
13 5 8 - 10
14 6 9 10 - 8
15 7 12 8 -

i. Draw the network diagram corresponding to this problem. (4)

ii. If the objective is to minimize total installation costs, determine the set of interconnections that will
allow parts to be carried from any area to any other area in the production facility. Show the resulting
network. (10)

4
Q8) A power plant generates electricity for a certain residential and commercial area. The plant burns three
types of coal which produce steam that drives the turbines. The Environmental Protection Agency (EPA)
requires that for each ton (1000 kg) of coal burned, the emissions from the furnace stacks contain no more
than 2,500 ppm of sulfur and no more than 2.8 kg of coal dust. The electricity demand requires at least
30,000 lbs of steam. The following table summarizes the amounts of sulfur, coal dust, and steam that result
from burning a ton of each type of coal.

Coal Sulfur Coal Dust Pounds of Steam

(in ppm) (in kg) Produced
1 1,100 1.7 24,000
2 3,500 3.2 36,000
3 1,300 2.4 28,000

The three types of coal can be mixed and burned in any combination. The resulting emission of sulfur or
coal dust and the pounds of steam produced by any mixture are given as the weighted average of the values
shown in the table for each type of coal. For example, if the coals are mixed to produce a blend that
consisted of 35% of coal 1, 40% of coal 2, and 25% of coal 3, the sulfur emission (in ppm) resulting from
burning 1 ton of this blend is:

(0.35 x 1,100) + (0.40 x 3,500) + (0.25 x 1,300) = 2,110

The manager of this facility wants to select a blend of coal to burn while considering the following goals:

Goal 1: Maximize the pounds of steam produced.

Goal 2: Minimize sulfur emissions
Goal 3: Minimize coal dust emissions

i. Formulate a goal programming model for this problem assuming all goals have equal priorities. Use
the precise notational system. (8)
ii. Suppose management considers maximizing the amount of steam produced five times as important as
achieving the best possible values for the other goals. Incorporate this preferential factor into the model
developed in part (i) above. (4)
iii. Intuitively suggest what will be the percentages of each of the three types of coals per ton of the blend
if the demand for steam increases to 40,000 lbs? (2)