# 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

#### Solution Summary

This posting contains solutions to following Linear programming problems.