Optimization - models

1

Please You must follow the formatting instructions described in the file

1. Ten jobs are to be completed by three workers (Sam, Joy, and Kelly) during the next week.

Each person works up to 40 hours per week and is paid an hourly rate: Sam, Joy, and Kelly earn $11, $13, and $14 per hour, respectively. Union rules require workers to be treated fairly;

to ensure that most of the work is not assigned to one person while others are too idle, make

sure that no person works more than 8 hours above any other worker. For example, if Joy works

20 hours, then Sam and Kelly should work within 12 to 28 hours, and Sam and Kelly should

have work-hours that are no more than 8 hours apart.

The times for the workers to complete the tasks are shown in the table below. The values in the

cells assume that each task is completed by a single person. However, tasks can be shared with

completion times being determined proportionally (e.g., if Joy and Kelly share task 1 equally,

then Joy works 6 hours and Kelly works 9 hours). If no entry exists in a particular cell, it means

that task cannot be performed by that worker.

a. Formulate the problem as a linear optimization model (that is, define the variables, and write down the objective function and all constraints mathematically).

b. Create a spreadsheet model for this problem and solve with Excel Solver.

c. What is the optimal solution? What is the optimal value?

2. The director of a computer needs to schedule the staffing of the center. It is open from 8am

until midnight. Larry has monitored the usage of the center at various times of the day and

determined that the following number of computer consultants are required:

Time of Day Minimum Number of Consultants

Required to be on Duty

8am – Noon 6

Noon – 4pm 8

4pm – 8pm 12

8pm - Midnight 6

Two types of computer consultants can be hired: full-time and part-time. The full-time

consultants work for eight consecutive hours in any of the following shifts: morning (8am –

4pm), afternoon (noon-8pm), and evening (4pm-midnight). Full-time consultants are paid $14

per hour. Part-time consultants can be hired to work any of the four shifts listed in the table.

Part-time consultants are paid $12 per hour.

An additional requirement is that during every time period, there must be at least two full-time

consultants on duty for every part-time consultant on duty. Larry would like to determine how

2

many full-time and part-time consultants should work each shift to meet the above requirements

at the minimum possible cost.

a. Formulate the problem algebraically (i.e., define the variables, objective and constraints

algebraically).

b. Implement your model in Excel and solve it.

c. What is the optimal solution? What is the optimal value?

3. Diana Dazzle, programming manager for GDUB-TV, must plan her schedule of television

shows for next Wednesday evening. Of the nine one-half hour shows listed below, she must

select exactly five for Wednesday evening. The estimated revenue (in $ million) is given below

for each show. Furthermore, the F.C.C. has classified each show as falling into one or more of

the categories of Public Interest, Violence, Comedy, and Drama as given in the table below.

ID # Show Revenue ($ mill)

Public

Interest Violence Comedy Drama

1 Cheers 7 X X

2 Ghost 6 X X

3 Law and Order 8 X X X

4 Spiderman 5 X X X

5 Dharma and Greg 8 X

6 News Special:Middle East 3 X X

7 Focus on Science 4 X X

8 China Beach 7 X X

9 Urban Action for Education 2 X

Diana's task is to select exactly five shows in order to maximize revenue. However, she must

be mindful of the following limitations and issues:

• There must be at least as many shows aired that are categorized as drama as there are shows

aired that are categorized as comedy.

• She cannot air more than two of the shows "News Special:Middle East", "Focus on

Science" and "Urban Action for Education" (too serious!).

• If Diana airs "Focus on Science", she must air either "Spiderman" or "Law and Order" but

not both.

• If she airs four or more shows in the violence category, she pays F.C.C. a fine of $5 million,

which will be deduced from the revenue.

Formulate Diana Dazzle's selection problem as a binary optimization problem. Clearly define

your decision variables, constraints, and objective function. Use only linear constraints and a

linear objective function. You do not have to solve the model in Excel.

3

4. A shoe manufacturer produces three types of footwear: dress shoes, short boots, and high boots.

To maximize its short-term profits, the company solves the following linear program:

Let D = # of dress shoes to produce,

S = # of short boots to produce, and

H = # of high boots to produce.

max 20𝐷 + 30𝑆 + 40𝐻

s.t. 25𝐷 + 60𝑆 + 140𝐻 ≤ 5000 (leather)

5𝐷 + 5𝑆 + 10𝐻 ≤ 800 (rubber)

𝐷, 𝑆, 𝐻 ≥ 0

Notice that there are two resources which are limited:

• Leather. A total of 5000 square inches of leather are available. Each pair of dress shoes, short boots, and high boots uses 25, 60, and 140 square inches respectively.

• Rubber. A total of 800 cubic inches are available. Each pair of dress shoes, short boots, and high boots uses 5, 5, and 10 cubic inches respectively.

Profits are $20 per pair of dress shoes, $30 per pair of short boots, and $40 per pair of high

boots. Given the following data in an Excel spreadsheet, please answer the following questions.

a. To model the shoe manufacturer’s optimization problem as a linear program in an Excel spreadsheet, what Excel formulas would be placed in the following cells (write “blank” if no

formula should be used in that cell):

B1:

B4:

F8:

4

b. Fill in the following Excel Solver window so that it looks like what you would expect to see

if you were solving this linear program on your computer.

The company generates a Sensitivity Report, which is displayed below.

Variable Cells

Final Reduced Objective Allowable Allowable

Cell Name Value Cost Coefficient Increase Decrease

$B$4

Production Qty Dress

Shoes 131.42 0 20 10 7.5

$C$4

Production Qty Short

Boots 28.57 0 30 18 10

$D$4 Production Qty High Boots 0 -25.71 40 25.71 1E+30

Constraints

Final Shadow Constraint Allowable Allowable

5

Cell Name Value Price R.H. Side Increase Decrease

$F$8

Leather (square inches)

Used 5000 0.28 5000 4600 1000

$F$9

Rubber (cubic inches)

Used 800 2.57 800 200 383.33

c. Are there any resources remaining after production? If so, what are they and how much

remains of each? Explain how you arrived at this conclusion.

d. Would the company be willing to purchase extra rubber? If so, what is the highest price the

company would be willing to pay per cubic inch, and how much more rubber would the

company be willing to purchase? Explain how you arrived at this conclusion.

e. From the Sensitivity Report, we can see that high boots are not profitable enough to be

produced. How high would the profit of a pair of high boots need to be in order to get

produced? Explain how you arrived at this conclusion.

f. Assume the profit of dress shoes drops from $20 to $15. How many of each product does the

company produce? What is the company’s total profit in this case? Explain how you arrived

at this conclusion.

g. Consider that the values of the parameters remain all unchanged at the exception of the profit

per dress (set equal to $20 above). For which value(s) of the profit per dress, can you obtain

multiple optimal solutions? Explain how you arrived at this conclusion.