Linear Programming Applications
Solve the following optimization problems using the Solver:
Question 1) The demand for ice cream during the three summer months (June, July, and August) at All-Flavors Parlor is estimated at 300, 400, and 500 20-gallon cartons, respectively. Two wholesalers, 1 and 2, supply All-Flavors with its ice cream. Although the flavors from the two suppliers are different, they are interchangeable. The maximum number of cartons either supplier can provide is 270 per month. Also, the prices the two suppliers charge change from one month to the next according to the following schedule.
|
|
Price per carton in month
|
|
|
June
|
July
|
August
|
|
Supplier 1
|
$80
|
$95
|
$102
|
|
Supplier 2
|
$103
|
$89
|
$93
|
To take advantage of price fluctuation, All-Flavors can purchase more than is needed for a month and store the surplus to satisfy the demand in a later month. The cost of refrigerating an ice-cream carton is $2 per month. It is realistic in the present situation to assume that the refrigeration cost is a function of the average number of cartons on hand during the month. Develop a model to determine the optimum schedule for buying ice cream from the two suppliers. Specifically, this will be a written model with well-defined decision variables (for example, look at the model on page 41 in the textbook for an example). Next, find the optimum solution using Excel's Solver tool.
Question 2) A large store operates 7 days per week. The manager estimates that a minimum number of salespersons required to provide prompt service is 14 on Monday, 20 on Tuesday, 23 on Wednesday, 30 on Thursday, 40 on Friday, 36 on Saturday, and 30 on Sunday. Each salesperson works 5 days per week, with two consecutive off-days staggered throughout the week. For example, if 10 salespersons start on Monday, 2 can take their off-days on Tuesday and Wednesday, 5 on Wednesday and Thursday, and 3 on Saturday and Sunday. How many salespersons should be contracted, and how should their off-days be allocated? Develop a model to determine the optimum schedule. Specifically, this will be a written model with well-defined decision variables (for example, look at the model on page 41 in the textbook for an example). Next, find the optimum solution using Excel's Solver tool.
Question 3) The city of Madison is embarking on an urban renewal project that will include lower- and middle-income row housing, upper-income luxury apartments, and public housing. The project also includes a public elementary school and retail facilities. The size of the elementary school (the number of classrooms) is proportional to the number of pupils, and the retail space is proportional to the number of housing units. The following table provides the pertinent data of the situation:
|
|
Lower income
|
Middle income
|
Upper income
|
Public housing
|
School room
|
Retail unit
|
|
Minimum number of units
|
100
|
125
|
75
|
300
|
|
0
|
|
Maximum number of units
|
200
|
190
|
260
|
600
|
|
25
|
|
Lot size per unit (acre)
|
0.05
|
0.07
|
0.03
|
0.025
|
0.045
|
0.1
|
|
Average number of pupils per unit
|
1.3
|
1.2
|
0.5
|
1.4
|
|
|
|
Retail demand per unit (acre)
|
0.023
|
0.034
|
0.046
|
0.023
|
0.034
|
|
|
Annual income per unit ($)
|
7000
|
12,000
|
20,000
|
5000
|
----
|
15,000
|
The new school can occupy a maximum space of 2 acres at the rate of at most 25 pupils per room. The operating annual cost per schoolroom is $10,000. The project will be located on a 50-acre vacant property owned by the city. Additionally, the project can make use of an adjacent property occupied by 200 condemned slum homes. Each condemned home occupies 0.25 acres. The cost of buying and demolishing a slum unit is $7000. Open space, streets, and parking lots consume 15% of total available land.
Develop a model to determine the optimum schedule. Specifically, this will be a written model with well-defined decision variables (for example, look at the model on page 41 in the textbook for an example). Next, find the optimum solution using Excel's Solver tool.
Discrete Optimization
Solve the following problems by first determining the model (on paper; written/typed), and then enter this model into Excel and use the Solver to calculate the optimal solution. Be sure to write/type a short summary explaining what your solution means.
Question 1) Consider the following two groups of words:
|
Group 1
|
|
Group 2
|
|
AREA
|
|
ERST
|
|
FORT
|
|
FOOT
|
|
HOPE
|
|
HEAT
|
|
SPAR
|
|
PAST
|
|
THAT
|
|
PROF
|
|
TREE
|
|
STOP
|
All the words in groups 1 and 2 can be formed from the nine letters A, E, F, H, O P, R, S, and T. Develop a model to assign a unique numeric value from 1 to 9 to these letters such that the difference between the total scores of the two groups will be as small as possible. [Note: The score for a word is the sum of the numeric values assigned to its individual letters.] Hint: Remember to use the AllDifferent constraint in the Solver. Do a google search for ‘AllDifferent Constraint' if you need more help with this time-saving tool. Also, to earn full points on this problem, you must have an objective function that will be minimized. Do not use the Solver to solve for an exact value.
Question 2) You have a 4x4 grid and a total of 10 tokens. Use ILP to place the tokens on the grid such that each row and each column will have an even number of tokens.
Question 3) A widely -circulated puzzle requires assigning a single distinct digit (0 through 9) to each letter in the equation SEND + MORE = MONEY. Formulate the problem as an integer program and then find a solution.
Question 4) Search through puzzle or brain-teaser books, magazines, websites, publications, etc. Find a problem that could be solved with these ILP methods. Clearly explain what the problem is that will be solved and then solve this problem. As with previous problems you will submit a written model, a Solver model, as well as a summary of whether the Solver found the optimal solution. Each group will only need to find and solve one brain-teaser.