Operations Management Excel

Page 1 of 8

IEN 441- Spring 2017

(DO NOT COPY OR DISTRIBUTE)

Handout 3.2 Sample LP Problems

Solution of Post Office Scheduling Problem

Decision variables

xi ︎: number of employees beginning work on day i

For example, x1 is the number of people beginning work on Monday (these people work Monday to Friday).

Note that

(number of full-time employees) = (number of employees who start work on Monday) + (number of employees who start work on Tuesday) + …+ (number of employees who start work on Sunday). Because each employee begins work on exactly one day of the week, this expression does not double-count employees. Thus, when we correctly define the variables, the objective function is

min z = x1 + x2 + x3 + x4 + x5 + x6 + x7

The post office must ensure that enough employees are working on each day of the week. For example, at least 17 employees must be working on Monday. Who is working on Monday? Everybody except the employees who begin work on Tuesday or on Wednesday (they get, respectively, Sunday and Monday, and Monday and Tuesday off). To ensure that at least 17 employees are working on Monday, we require that the constraint

x1 +x4 +x5 +x6 +x7 ≥ 17

be satisfied. Adding similar constraints for the other six days of the week and the sign restrictions xi ≥ 0 (i = 1, 2, …, 7) yields the following formulation of the post office’s problem:

Remark: There is one flaw with the above formulation. Because we are only allowing full-time employees, the variables must be integers. Notice that there is no way that the optimal linear programming solution could have been rounded to obtain the optimal all-integer solution. We will discuss Integer Programming later in the course.

xi ! number of employees beginning work on day i

For example, x1 is the number of people beginning work on Monday (these people work Monday to Friday). With the variables properly defined, it is easy to determine the cor- rect objective function and constraints. To determine the objective function, note that (number of full-time employees) ! (number of employees who start work on Monday) " (number of employees who start work on Tuesday) "###" (number of employees who start work on Sunday). Because each employee begins work on exactly one day of the week, this expression does not double-count employees. Thus, when we correctly define the variables, the objective function is

min z ! x1 " x2 " x3 " x4 " x5 " x6 " x7

The post office must ensure that enough employees are working on each day of the week. For example, at least 17 employees must be working on Monday. Who is working on Monday? Everybody except the employees who begin work on Tuesday or on Wednes- day (they get, respectively, Sunday and Monday, and Monday and Tuesday off). This means that the number of employees working on Monday is x1 " x4 " x5 " x6 " x7. To ensure that at least 17 employees are working on Monday, we require that the constraint

x1 " x4 " x5 " x6 " x7 $ 17

be satisfied. Adding similar constraints for the other six days of the week and the sign re- strictions xi $ 0 (i ! 1, 2, . . . , 7) yields the following formulation of the post office’s problem:

min z ! x1 " x2 " x3 " x4" x5" x6" x7 s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 17 (Monday constraint)

s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 13 (Tuesday constraint)

s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 15 (Wednesday constraint)

s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 19 (Thursday constraint)

s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 14 (Friday constraint)

s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 16 (Saturday constraint)

s.t. x1 " x2 " x3 " x4 " x5 " x6 " x7 $ 11 (Sunday constraint)

xi $ 0 (i ! 1, 2, . . . , 7) (Sign restrictions)

The optimal solution to this LP is z ! %63 7 %, x1 ! %

4 3

%, x2 ! % 1 3 0 %, x3 ! 2, x4 ! %

2 3 2 %, x5 ! 0, x6 !

% 1 3 0 %, x7 ! 5. Because we are only allowing full-time employees, however, the variables must

be integers, and the Divisibility Assumption is not satisfied. To find a reasonable answer in which all variables are integers, we could try to round the fractional variables up, yielding

3 . 5 A Work-Scheduling Problem 73

TA B L E 4 Requirements for Post Office

Number of Full-time Day Employees Required

1 ! Monday 17 2 ! Tuesday 13 3 ! Wednesday 15 4 ! Thursday 19 5 ! Friday 14 6 ! Saturday 16 7 ! Sunday 11

Page 2 of 8

Sample (Real-World) LP Problems with Solutions 1

Remember:

- The most important step in formulating most LPs is to determine the decision variables correctly. - In any constraint, the terms must have the same units. For example, one term cannot have the units “pounds of raw material” while another term has the units “ounces of raw material.” Problem # 1.

You have decided to enter the candy business. You are considering producing two types of candies: Slugger Candy and Easy Out Candy, both of which consist solely of sugar, nuts, and chocolate. At present, you have in stock 100 oz of sugar, 20 oz of nuts, and 30 oz of chocolate. The mixture used to make Easy Out Candy must contain at least 20% nuts. The mixture used to make Slugger Candy must contain at least 10% nuts and 10% chocolate. Each ounce of Easy Out Candy can be sold for 25¢, and each ounce of Slugger Candy for 20¢. Formulate an LP that will enable you to maximize your revenue from candy sales. Answer: Let (all variables are in ounces)

Ing. 1 = Sugar, Ing. 2 = Nuts, Ing. 3 = Chocolate, Candy 1 = Slugger and Candy 2 = Easy Out

Let xij = Ounces of Ing. i used to make candy j.

The appropriate LP is

max z = 25(x12 + x22 + x32) + 20(x11 + x21 + x31)

s.t. x11 + x12 ≤ 100 (Sugar Const.)

x21 + x22 ≤ 20 (Nuts Constraint)

x31 + x32 ≤ 30 (Chocolate Const.)

(1) x22/(x12 + x22 + x32) ≥ 0.20

(2) x21/(x11 + x21 + x31) ≥ 0.10

(3) x31/(x11 + x21 + x31) ≥ 0.10

All variables ≥ 0

(1)-(3) are not LP constraints and should be replaced by the following three constraints:

Replace (1) by x22≥.2(x12+x22+x32) or .8x22-.2x12-.2x32≥0

Replace (2) by x21≥.1(x11+x21+x31) or .9x21-.1x11-.1x31≥0

Replace (3) by x31≥.1(x11+x21+x31) or .9x31-.1x11-.1x21≥0

1. Problem # 5 are from Hamdy A. Taha, Operations Research: An Introduction, Prentice Hall. 9th Edition. (ISBN 10: 0-13- 255593-X) and Problems 1-4 # 6 are from Wayne L. Winston, Operations Research: Applications and Algorithms, Duxbury. (ISBN: 0-534- 38058-1)

Page 3 of 8

Problem # 2. BLENDING

Sunco Oil has three different processes that can be used to manufacture various types of gasoline. Each process involves blending oils in the company’s catalytic cracker. Running process 1 for an hour costs $5 and requires 2 barrels of crude oil 1 and 3 barrels of crude oil 2. The output from running process 1 for an hour is 2 barrels of gas 1 and 1 barrel of gas 2. Running process 2 for an hour costs $4 and requires 1 barrel of crude 1 and 3 barrels of crude 2. The output from running process 2 for an hour is barrels of gas 2. Running process 3 for an hour costs $1 and requires 2 barrels of crude 2 and 3 barrels of gas 2. The output from running process 3 for an hour is 2 barrels of gas 3. Each week, 200 barrels of crude 1, at $2/barrel, and 300 barrels of crude 2, at $3/barrel, may be purchased. All gas produced can be sold at the following per-barrel prices: gas 1, $9; gas 2, $10; gas 3, $24. Formulate an LP whose solution will maximize revenues less costs. Assume that only 100 hours of time on the catalytic cracker are available each week. Answer: 1. Let x1 = Hours of Process 1 run per week x2 = Hours of Process 2 run per week x3 = Hours of Process 3 run per week g2 = Barrels of Gas 2 sold per week o1 = Barrels of Oil 1 purchased per week o2 = Barrels of Oil 2 purchased per week ** you can choose any label instead of g and o max z = 9(2x1)+10g2+24(2x3)-5x1-4x2-x3-2o1-3o2 s.t. o1 = 2x1 +x2 o2 = 3x1+3x2+2x3 o1≤ 200 o2≤ 300 g2+3x3 = x1+3x2 (Gas 2 Prod.) x1+x2+x3≤100 (100 hours per wk. of cracker time) All variables ≥0.

Page 4 of 8

Problem # 3. Inventory Planning A customer requires during the next four months, respectively, 50, 65, 100, and 70 units of a commodity (no backlogging is allowed). Production costs are $5, $8, $4, and $7 per unit during these months. The storage cost from one month to the next is $2 per unit (assessed on ending inventory). It is estimated that each unit on hand at the end of month 4 could be sold for $6. Formulate an LP that will minimize the net cost incurred in meeting the demands of the next four months. Answer:

Let xt = Production during month t and it = Inventory at end of month t.

min z = 5x1+8x2+4x3+7x4+2i1+2i2+2i3+2i4-6i4

s.t. i1 = x1 - 50

i2 = i1 + x2 - 65

i3 = i2 + x3 - 100

i4 = i3 + x4 - 70

All variables ≥0.

Page 5 of 8

Problem # 4. Scheduling

Each year, Paynothing Shoes faces demands (which must be met on time) for pairs of shoes as Quarter 1= 600; Quarter 2= 300; Quarter 3= 800; Quarter 4= 100;

Workers work three consecutive quarters and then receive one quarter off. For example, a worker may work during quarters 3 and 4 of one year and quarter 1 of the next year. During a quarter in which a worker works, he or she can produce up to 50 pairs of shoes. Each worker is paid $500 per quarter. At the end of each quarter, a holding cost of $50 per pair of shoes is assessed. Formulate an LP that can be used to minimize the cost per year (labor + holding) of meeting the demands for shoes. To simplify matters, assume that at the end of each year, the ending inventory is zero. (Hint: It is allowable to assume that a given worker will get the same quarter off during each year.) Let

st = pairs of shoes made during quarter t of each year and

it = inventory of pairs of shoes at the end of each year

xt = workers getting quarter t off during each year

Minimizing cost per year yields the following objective function

min z = 1500 (x1 + x2 + x3 + x4) + 50 i1 + 50 i2 + 50 i3 + 50 i4

subject to.

s1 ≤ 50 (x2 + x3 + x4)

s2 ≤ 50 (x1 + x3 + x4)

s3 ≤ 50 (x1 + x2 + x4)

s4 ≤ 50 (x1 + x2 + x3)

i1 = 0 + s1 - 600

i2 = i1 + s2 - 300

i3 = i2 + s3 - 800

i4 = i3 + s4 - 100

i4 = 0

All variables ≥0

Page 6 of 8

Problem # 5. Production Planning and Inventory Control (2 examples)

Acme Manufacturing Company has a contract to deliver 100, 250, 190, 140, 220, and 110 home windows over the next 6 months. Production cost (labor, material, and utilities) per window varies by period and is estimated to be $50, $45, $55, $48, $52, and $50 over the next 6 months. To take advantage of the fluctuations in manufacturing cost, Acme can produce more windows than needed in a given month and hold the extra units for delivery in later months. This will incur a storage cost at the rate of $8 per window per month, assessed on end-of-month inventory. Develop a linear program to determine the optimum production schedule.

Answer:

Variables: The variables of the problem include the monthly production amount and the end-of-month inventory. For i = 1, 2, ..., 6. The system starts empty

The relationship between these variables and the monthly demand over the 6-month horizon is represented schematically as

Objective Function: Minimize the total cost of production and end-of-month inventory:

Total production cost: 50 x1 + 45 x2 + 55 x3 + 48 x4 + 52 x5 + 50 x6

Total inventory (storage) cost: 8 (I1 + I2 + I3 + I4 + I5 + I6)

Min z = 50 x1 + 45 x2 + 55 x3 + 48 x4 + 52 x5 + 50 x6 + 8 (I1 + I2 + I3 + I4 + I5 + I6)

Constraints: Beginning inventory + Production amount - Ending inventory = Demand

Page 7 of 8

LP Formulation

Minimize Cost

subject to:

Problem # 6. Project Selection Problem Star Oil Company is considering five different investment opportunities. The cash out-flows and net present values (in millions) are given in the Table. Star Oil has $40million available for investment now (time 0); it estimates that one year from now (time1) $20 million will be available for investment. Star Oil may purchase any fraction of each investment. In this case, the cash outflows and NPV are adjusted accordingly. For example, if Star Oil purchases one-fifth of investment 3, then a cash outflow of (1/5)(5) =$1 million would be required at time 1. The one-fifth share of investment 3 would yield an NPV of $3.2million. Star Oil wants to maximize the NPV that can be obtained by investing Formulate an LP that will help achieve this goal. Assume that any funds leftover at time 0 cannot be used at time 1.

Decision Variables:

xi = fraction of investment i to purchase by Star Oil

Objective Function:

Maximize the NPV earned from investments: The objective function is

Max z = 13 x1 + 16 x2 + 16 x3 + 14 x4 + 39 x5

Page 8 of 8

Constraints:

Constraint 1 Star cannot invest more than $40 million at time 0.

Constraint 2 Star cannot invest more than $20 million at time 1.

Constraint 3 Star cannot purchase more than 100% of investment.

LP Formulation

Subject to

Remarks:

In many capital budgeting problems, it is unreasonable to allow the xi to be fractions: Each xi should be restricted to 0 (not investing at all in investment i) or 1 (purchasing all of investment i). We will see later how to do this.