Homework 2: More linear programs

CS/ECE/ISyE 524 Introduction to Optimization 
Homework 2: More linear programs

See the course website for instructions and submission details.
1. [10 pts] Stigler’s diet. True story! In 1945, American economist (and future Nobel laureate) George
Stigler published a paper investigating the composition of an optimal diet; minimizing total cost while
meeting the recommended daily allowance (RDA) of several nutrients. To answer this question, Stigler
tabulated a list of 77 foods and their nutrient content for 9 nutrients: calories, protein, calcium, iron,
vitamin A, thiamine, riboflavin, niacin, and ascorbic acid. Here is what the first few rows and columns
of his table looked like:
Calories (1000) Protein (g) Calcium (g) Iron (mg) . . .
Wheat Flour (Enriched) 44.7 1411 2 365 . . .
Macaroni 11.6 418 0.7 54 . . .
Wheat Cereal (Enriched) 11.8 377 14.4 175 . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
To make calculations easier, Stigler normalized his data so each row shows the nutrients contained in
$1’s worth of the given food item. Back then, $1 could buy you quite a lot!
When Stigler posed his diet problem, the simplex method had not yet been invented. In his paper,
he wrote: “...the procedure is experimental because there does not appear to be any direct method
of finding the minimum of a linear function subject to linear conditions.” Nevertheless, through a
combination of “trial and error, mathematical insight, and agility”, he eventually arrived at a solution:
a diet costing only $39.93 per year. Though he confessed: “There is no reason to believe that the
cheapest combination was found, for only a handful of the [many] possible combinations of commodities
were examined.”
a) Formulate Stigler’s diet problem as an LP and solve it. To get you started, Stigler’s original data
is provided in stigler.csv, and the IJulia notebook stigler.ipynb imports the data and puts it
into a convenient array format. How does your cheapest diet compare in annual cost to Stigler’s?
What foods make up your optimal diet?
b) Suppose we wanted to find the cheapest diet that was also vegan and gluten-free. How much
would that cost per year, and what foods would be used?
2. [10 pts] Construction with constraints. During the next 4 months, a construction firm must
complete three projects. Each project has a deadline as well as labor requirements. Project 1 must be
completed no later than 3 months from now and requires 8 worker-months of labor. Project 2 must
be completed no later than 4 months from now and requires 10 worker-months of labor. Project 3
must be completed no later than 2 months from now and requires 12 worker-months of labor. Each
month, 8 workers are available. During a given month, no more than 6 workers can work on a single
job. Determine whether all three projects can be completed on time.
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Lessard, Spring 2017
3. [10pts] Museum site planning. A site is being investigated as a potential location for a new
museum. An aerial plan of the site is shown in the figure below (in feet). The museum will have a
circular footprint and law mandates that there be at least 50 feet of clearance between the building
and any road. If we want the largest possible museum, where should it be located? What is its optimal
radius? Re-plot the figure below along with the optimally designed museum.
4. [15 pts] Electricity grid with storage. The town of Hamilton buys its electricity from the Powerco
utility, which charges for electricity on an hourly basis. If less than 50 MWh is used during a given
hour, then the cost is $100 per MWh. Any excess beyond 50 MWh used during the hour is charged at
the higher rate of $400 per MWh. The maximum power that Powerco can provide in any given hour is
75 MWh. Here is what the average daily electricity demand looks like for Hamilton during the month
of January:
Hour of day (AM) 1 2 3 4 5 6 7 8 9 10 11 12
Demand (MWh) 43 40 36 36 35 38 41 46 49 48 47 47
Hour of day (PM) 1 2 3 4 5 6 7 8 9 10 11 12
Demand (MWh) 48 46 45 47 50 63 75 75 72 66 57 50
The mayor of Hamilton is concerned because the high electricity use during evening hours is costing
the city a lot of money. There is also risk of black-outs at around 7pm because the average demand is
dangerously close to Powerco’s 75 MW limit.
To address these issues, the mayor purchased a large battery with a storage capacity of 30 MWh. The
idea is that extra electricity could be purchased early in the day (at the lower rate), stored in the
battery, and used later in the day when demand (and prices) are high.
a) How much money can the town of Hamilton save per day thanks to the battery? Assume that
the battery begins the day completely drained. Also, to be safe from possible black-outs, limit
the amount of electricity purchased every hour to a maximum of 65 MWh.
b) How much money would be saved if the battery had an infinite capacity? In this scenario, how
much of the battery’s capacity is actually used?
c) Make a plot that shows (i) the typical energy demand vs time of day (ii) the electricity purchased
using the strategy found in part a) vs time of day, and (iii) the battery capacity used as a function
of time (draw all three plots on the same axes).
d) Comment on whether the solutions you found are unique. Are other solutions possible? Why?
Suggest a way of finding another optimal solution.
2 of 2