You are required to answer SIX questions – Questions 1, 2, 3, and 4 and ANY two others. Answer each question thoroughly and show all your calculations and printouts. Give clear explanations for your answers where necessary.
1. An ad campaign for a new snack chip will be conducted in a limited geographical area and can use TV time, radio time, and newspaper ads. Information about each medium is shown below.
TV / 500 / 10000 / 30
Radio / 200 / 3000 / 40
Newspaper / 400 / 5000 / 25
The number of TV ads cannot exceed the number of radio ads by more than 4, and the advertising budget is $10000.
a. Develop a model that will maximize the number reached and achieve an exposure quality of at least 1000.
Let,andbe the number of TV, radio and newspaper ads, respectively. We need to maximize the number reached, which is
We also have a number of restrictions:
· The budget restriction:
· Exposure Quality:
· Restriction over TV and radio ads:
· Natural restriction over the variables:
The overall model can be written then:
b. Solve the model that you developed in part a.
c. Suppose the advertising budget is raised to $12,000, how would your solution to part b change?
2. Larkin Industries manufactures several lines of decorative and functional metal items. The most recent order has been for 1200 door lock units for an apartment complex developer. The sales and production departments must work together to determine delivery schedules. Each lock unit consists of three components: the knob and face plate, the actual lock itself, and a set of two keys. Although the processes used in the manufacture of the three components vary, there are three areas where the production manager is concerned about the availability of resources. These three areas, their usage by the three components, and their availability are detailed in the table.
Brass Alloy / 12 / 5 / 1 / 15000 units
Machining / 18 / 20 / 10 / 36000 minutes
Finishing / 15 / 5 / 1 / 12000 minutes
A quick look at the amounts available confirms that Larkin does not have the resources to fill this contract. A subcontractor, who can make an unlimited number of each of the three components, quotes the prices below.
Knob and Plate / 10.00 / 6.00
Lock / 9.00 / 4.00
Keys (set of 2) / 1.00 / .50
Develop a linear programming model that would tell Larkin how to fill the order for 1200 lock sets at the minimum cost.
Let X1, X2 and X3 be the number of knob & faceplate , lock and keys produced by Larkin Industries. The remaining numbers (1200 –X1) of Knob & Plate, (1200-X2) of Lock and (1200-X3) of keys are to be ordered from the subcontractor. The additional cost for these items are (10.00-6.00) = 4 , (9.00-4.00) = 5.00 and (1.00-0.50) =0.500 respectively.
Thus the objective function can be written as
Minimize Z = 4*(1200-X1) +5*(1200-X2) + 0.5*(1200-X3)
Subject to
12X1 + 5X2 + X3 ≤ 15000Constraint for Brass Alloy
18X1 + 20X2 + 10X3 ≤ 36000Constraint for Machining
15X1 + 5X2 + X3 ≤12000Constraint for Finishing
X1 ≥0 , X2 ≥0, X3 ≥0
Solving this LPP we can find out the optimum number of Knob & Plate Lock and Key
3. Super City Discount Department Store is open 24 hours a day. The number of cashiers needed in each four hour period of a day is listed below. Suppose each cashier is paid $12.00 per hour with a positive hourly shift differential of 30% of the hourly wage for workers who are on the job between 10:00 P.M. and 6:00 A.M.
10 p.m. to 2 a.m. / 8
2 a.m. to 6 a.m. / 4
6 a.m. to 10 a.m. / 7
10 a.m. to 2 p.m. / 12
2 p.m. to 6 p.m. / 10
6 p.m. to 10 p.m. / 15
If cashiers work for eight consecutive hours, how many should be scheduled to begin working in each period in order to minimize the number of cashiers needed?
LetTNP = the number who begin working at 10 p.m.
TWA = the number who begin working at 2 a.m.
SXA = the number who begin working at 6 a.m.
TNA = the number who begin working at 10 a.m.
TWP = the number who begin working at 2 p.m.
SXP = the number who begin working at 6 p.m.
MinTNP + TWA + SXA + TNA + TWP + SXP
s.t.TNP + TWA 4
TWA + SXA 7
SXA + TNA 12
TNA + TWP 10
TWP + SXP 15
SXP + TNP 8
all variables 0
4. Canning Transport is to move goods from three factories to three distribution centers. Information about the move is given below.
A / 200 / X / 50
B / 100 / Y / 125
C / 150 / Z / 125
Shipping costs are:
DestinationSource / X / Y / Z
A / 3 / 2 / 5
B / 9 / 10 / --
C / 5 / 6 / 4
(Source B cannot ship to destination Z)
a. Develop the network representation of this problem.
b. Formulate this problem as a linear program.
c. Solve the problem.
Min 3XAX + 2XAY + 5XAZ + 9XBX + 10XBY + 5XCX + 6XCY + 4XCZ
s.t. XAX + XAY + XAZ 200
XBX + XBY 100
XCX + XCY + XCZ 150
XAX +XBX +XCX= 250
XAY + XBY +XCY= 125
XAZ +XCZ= 125
Xij 0
5. RVW (Restored Volkswagens) buys 15 used VW's at each of two car auctions each week held at different locations. It then transports the cars to repair shops it contracts with. When they are restored to RVW's specifications, RVW sells 10 each to three different used car lots. There are various costs associated with the average purchase and transportation prices from each auction to each repair shop. Also there are transportation costs from the repair shops to the used car lots. RVW is concerned with minimizing its total cost given the costs in the table below.
Repair Shops / Used Car Lots
S1 / S2 / L1 / L2 / L3
Auction 1 / 550 / 500 / S1 / 250 / 300 / 500
Auction 2 / 600 / 450 / S2 / 350 / 650 / 450
b. / Formulate this problem as a transshipment linear programming model.
6. Tower Engineering Corporation is considering undertaking several proposed projects for the next fiscal year. The projects, the number of engineers and the number of support personnel required for each project, and the expected profits for each project are summarized in the following table:
1 / 2 / 3 / 4 / 5 / 6
Engineers Required / 20 / 55 / 47 / 38 / 90 / 63
Support Personnel Required / 15 / 45 / 50 / 40 / 70 / 70
Profit ($1,000,000s) / 1.0 / 1.8 / 2.0 / 1.5 / 3.6 / 2.2
Formulate an integer program that maximizes Tower's profit subject to the following management constraints:
1) Use no more than 175 engineers
2) Use no more than 150 support personnel
3) If either project 6 or project 4 is done, both must be done
4) Project 2 can be done only if project 1 is done
5) If project 5 is done, project 3 must not be done and vice versa
6) No more than three projects are to be done.
Pi = 1 if project is done, 0 otherwise.
Max P1 + 1.8P2 + 2P3 + 1.5P4 + 3.6P5 + 2.2P6
s.t.20P1 + 55P2 + 47P3 + 38P4 + 90P5 + 63P6 < 175
15P1 + 45P2 + 50P3 + 40P4 + 70P5 + 70P6 < 150
P4 - P6 = 0
P1 - P2 0
P3 + P5 < 1
P1 + P2 + P3 + P4 + P5 + P6 < 3
Pi = 0 or 1
7. Your express package courier company is drawing up new zones for the location of drop boxes for customers. The city has been divided into the seven zones shown below. You have targeted six possible locations for drop boxes. The list of which drop boxes could be reached easily from each zone is listed below.
Downtown Financial / 1, 2, 5, 6
Downtown Legal / 2, 4, 5
Retail South / 1, 2, 4, 6
Retail East / 3, 4, 5
Manufacturing North / 1, 2, 5
Manufacturing East / 3, 4
Corporate West / 1, 2, 6
Let xi = 1 if drop box location i is used, 0 otherwise. Develop a model to provide the smallest number of locations yet make sure that each zone is covered by at least two boxes.
The required constraint is
SUM over i (xi) >= 2
For example the constraints for Downtown Financial is
x1 + x2 + x5 + x6 >=2
Other constraints are
x2 + x4 + x5 >=2
x1 + x2 + x4 + x6 >=2
x3 + x4 + x5 >= 2
x1 + x2 + x5 >=2
x3 + x4 >=2
x1 + x2 + x6>=2