Various Linear programming problems

WINTER 2007
OPERATIONS MODELING
IOE 202
Homework 1
IMPORTANT NOTE This is a team homework. The team works on this homework
together, but each member of the team must write their own home work and hand it in with
their name (underlined) and the names of other team members on the front page. Also,
each member of the team must produce all required tables and graphs on his/her own, and
have them identi¯ed with his/her name. Each member of the team is also required to type
his/her name into the Excel Solution when handing in Homework (i.e. no hand-written
names on Excel Solutions will be accepted).
1. A 1200 acre farm includes a well that has capacity of 2000 acre-feet of water per year.
The farm can be used to raise wheat, alfalfa, and beef. Wheat can be sold at $550
per ton. Alfalfa can be bought or sold at the market price of $220 per ton and beef at
$1300 per ton. Each ton of wheat that the farmer produces requires one acre of land,
$50 of labor, and 1.5 acre-feet of water. Each ton of alfalfa that the farmer produces
requires 1
3 acre of land, $40 of labor and 0.6 acre-feet of water. Each ton of beef that
is produced requires 0.80 acres of land, $50 of labor, 2 acre feet of water and 2.5 tons
of alfalfa. The farmer can neither buy or sell water, and wants to run the farm to
maximize the annual pro¯t.
(a) Formulate a linear program to help the farmer find the maximizing plan to run
the farm.
(b) Discuss if this linear model is a good approximation of the reality, i.e., discuss if
the proportionality, divisibility and additivity assumptions hold for this problem.
(c) Find the solution of this linear program using EXCEL.
2. A company makes two products in a single plant. It runs the plant for 100 hours each
week. Each unit of product A that the company produces requires two hours of plant
capacity, earns the company a contribution of $1000, and causes, as an undesirable
1
side effect, the emission of 4 ounces of particulate matter. Each unit of product B
that the company produces requires one hour of plant capacity, earns the company
a contribution of $2000, and causes, as an undesirable side e®ect, the emission of 3
ounces of particulate matter and 1 ounce of chemicals. The EPA (Environmental
Protection Agency) requires the company to limit particulate matter to at most 240
ounces per week and the chemicals to at most 60 ounces per week.
(a) Formulate a linear program to ¯nd the most pro¯table production plan that
meets the EPA standards.
(b) Graphically, ¯nd the optimum solution to this linear program.
(c) What is the optimum solution if the pro¯t of product B becomes $1500.
(d) Find a range of variation in the pro¯t for product A such that the optimum
solution found in (b) remains optimal. Do the same for the pro¯t of product B.
(e) Repeat question (d) for the optimum solution found in (c).
(f) Find how much the EPA standards on the particulate matter and the chemicals
can vary assuming that the optimal solution is still determined by the same
binding constraints that determined the optimal solutions of (b), and of (c).
Also do the same for the hours of week of operations of the plant.
(g) For both the problems of parts (b) and (c) ¯nd the shadow prices EPA standards
and the weekly hours of operations. Discuss the use of this price in decision
making.
(h) The company has found out that they cannot sell more than 50 units of product
B. What will the new solution be?
3. As a schedule setter for an airline you must schedule exactly one early morning de-
parture from Detroit to each of the four cities in the table below. Due to competition,
the contribution earned by each °ight depends on its departure time, as indicated
below. For example the most pro¯table time for a departure to O"Hare is 7:30am.
Your airline has the permission to depart at any time between 7am to 8am, but you
2
have only two departure gates, and you cannot schedule more than two departures at
any time.
Time Laguardia O"Hare Logan National
7:00 am 8.2 7.0 5.6 9.5
7:30 am 7.8 8.2 4.4 8.8
8:00 am 6.9 7.8 3.1 7.0
(a) Formulate a linear integer model to maximize contribution.
(b) Solve this problem on EXCEL.
(c) Another airline wishes to rent one departure gate at 7:00 am. What is the smallest
rent that is pro¯table for you to charge?
(d) It has been decided that there is not enough space to accommodate all travellers
with destinations of Laguardia and O"Hare at the gates, so these °ights cannot
go at the same time. Reformulate this model to re°ect this new constraint, and
solve it on EXCEL.
4. Consider the linear program:
maximize 2x1 + 3x2
x1 · 6
x1 + x2 · 7
2x2 · 9
¡x1 + 3x2 · 9
x1 ¸ 0 x2 ¸ 0
(a) Plot the feasible region of this linear program.
For each one of the questions below, please ¯nd the value of the objective function
and the values of x1 and x2.
i. Solve this linear program graphically, and con¯rm the answer by solving on
EXCEL.
ii. Change the objective function so that this problem has multiple solutions.
3
iii. Consider the problem with the ¯rst, the second and the third constraints
dropped. Graphically solve this revised problem, and note that the problem
is now unbounded.
iv. Change the objective function so that the modi¯ed problem has a solution.
5. Kelly Jumper is going on a holiday to New Zealand, and has heard that the New
Zealanders eat almost anything, and, over the years, have built up a tremendous re-
sistance to germs. As such, Kelly does not trust any eating establishment except
McDonald's, and therefore, while on holiday, has decided to live entirely on McDon-
ald's food. Kelly has managed to procure the information below (Table 1) from a
McDonald's outlet in a remote area of New Zealand where most of the holiday will
be spent. Additionally, McDonald's o®ers a special of 2 McChickens for $4.00 with
single McChickens selling for the regular price of $2.50. Although the menu is limited
compared with the McDonalds we know (and love?), there may be some information
missing, e.g., soft drinks. Kelly has obtained a health brochure that contains a number
of basic recommendations on daily diet, including:
(a) Sodium: not more than 3220mg of sodium per day for adults.
(b) Calories: about 2600 kCals for a male, and about 2000 for a female.
(c) Fat: not more that 35% of the total calories should be from fat.
(d) Cholesterol: not to exceed 500 milligrams of cholesterol
(e) Protein: at least 75 grams of protein
(f) Carbs: at least 75 grams of carbohydrates
In addition to these general nutritional guidelines, Kelly may have considerations and
preferences of her own that she would like to incorporate into the daily menu. Kelly
wants to know what the least expensive diet is, consisting entirely of McDonalds
foods listed above, that meets the listed nutritional criteria and other constraints.
Your task is to use your knowledge of Operations Modelling to answer this question.
Prepare a report for Kelly that analyzes this question. Describe all the additional
assumptions you made, how you represented the nutritional requirement constraints,
4
what additional considerations you incorporated in your model, etc. Discuss whether
the optimal solution to your model represents an acceptable daily diet. You should also
consider several scenarios re°ecting possible additional constraints Kelly may want to
impose (e.g., what if Kelly decides to be adventurous, and wants to eat at least one
Kiwiburger a day?, What if she does not want to eat beef burgers more than once
a day?, etc.). Your report should clearly describe the scenarios you considered and
the resulting menus and their costs and nutritional advantages/disadvantages. As an
appendix, include the mathematical model(s) you constructed to derive these answers,
as well as the EXCEL output with the names of the team members typed into the
EXCEL output.
TABLE 1
Nutrient Content Of McDonald's Foods.
Table showing energy and nutrient content per serving.
5
Menu item Energy Fat Protein Carbo. Cholesterol Sodium Price
kCalories Grams Grams Grams Milligrams Milligrams ($)
Big Mac 452 21 26 42 11 1219 2.00
Cheeseburger 289 12 17 30 33 650 1.00
Hamburger 251 10 13 29 28 570 0.90
Kiwiburger 533 32 37 26 105 524 3.00
McFeast 496 25 32 38 64 722 2.10
Quarter Pounder 499 27 32 34 56 948 1.90
Vegetarian Salad Burger 275 7 10 45 7 612 1.60
Filet-O-Fish 324 9 15 48 5 821 2.30
McChicken 378 12 17 53 10 865 2.50
Chicken McNuggets(6) 329 21 19 17 54 804 2.50
French Fries (large) 311 16 5 39 3 175 1.50
Barbecue Sauce 42 Trace Trace 11 0 357 free
Mustard Sauce 68 2 1 12 15 360 free
Sweet & Sour Sauce 46 Trace Trace 12 0 285 free
Curry Sauce 46 Trace Trace 12 0 390 free
Apple Pie 242 13 3 30 4 480 1.30
Apricot Pie 250 13 3 32 5 233 1.30
Cookies 328 14 5 48 0 125 1.40
Banana Shake 235 2 12 44 4 190 2.00
Chocolate Shake 198 3 12 32 9 232 2.00
Strawberry Shake 228 3 12 40 11 277 2.00
Vanilla Shake 127 2 11 17 11 186 2.00
Caramel Sundae 151 3 7 25 12 122 1.80
Hot Chocolate Sundae 180 5 8 27 9 144 1.90
Strawberry Sundae 184 2 6 37 7 76 1.80
Soft Serve Icecream+Cone 163 2 6 33 5 58 1.70
Orange Juice 61 0 0 16 0 38 1.85
(a) Energy KCal: This is the measure of the total available energy in a food.
(b) Carbohydrate: Carbohydrate is the most useful form of food fuel to the body and
occurs as either starches or sugars in foods. 1 gram provides 3.75 kCal.
(c) Fat: Fats are found in both animal and plant foods and, although structurally di®erent,
provide the same total amount of energy. Fats are the most concentrated form of food
energy available. I gram provides 9kCal.
(d) Protein: Proteins provide the essential materials for growth and repair of body tissue.
l gram provides 4kCals.
(e) The information above has been calculated by an independent New Zealand laboratory
& Consultant Nutritionist/Dietician.
Thanks to Shane G. Henderson for this model.
6