Homework 2: More Linear Programs

Description

1. [2 points] Construction with constraints. During the next 4 months, a construction rm 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.

2. [4 points]

Stigler’s diet. In 1945, American economist (and future Nobel Memorial Prizewinner in Economics) 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, ribo avin, niacin, and ascorbic acid. Here is what the rst 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 nding the minimum of a linear function subject to linear conditions.” Nevertheless, through a combination of what he called \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.”

1. 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? Write out a list of foods and the optimal daily number of units, for just those foods where the optimal diet has more than 0 units.

Note: Remember that the lower bounds are for daily quantities, so you can solve the LP to nd the optimal daily cost of the diet, but remember to multiply by 365 to obtain the optimal annual cost.

2. For the model above, print out the lower bounds for each nutrient alongside the amount of nutrient in the optimal diet and the dual variable corresponding to that constraint. Which of these bounds are active, that is, satis ed by the solution with equality? Verify that complementarity is satis ed for this solution.

CS/ECE/ISyE 524 Introduction to Optimization Steve Wright, Spring 2021

(Remember that the solutions of LPs often contain some roundo error, so the reported nutrient amounts for the optimal solution might be very slightly infeasible, but in such cases we would report them as \active.”

1. 3. Suppose we wanted to nd the cheapest diet that contains no \Liver (Beef)” and at least :01 units of \Milk.” Again, write out the foods that consitute the optimal diet, the amount of each, and the annual cost.

3. [3 points]

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 gure below (in units of feet). The museum will have a circular footprint and law mandates that there be at least 75 feet of clearance between the building and any edge of the site. If we want the largest possible museum, where should it be located? What is its optimal radius?

3. 1. In a markdown cell in your jupyter notebook, write down the mathematical model of this opti-mization problem, including the decision variables, constraints and objective function. Make sure to describe all problem parameters.

3. 2. Solve the problem in Julia/JuMP, nding the optimal location for the museum and the optimal radius. Re-plot the gure below, indicating the footprint of the museum as a red circle. Hint: Use the Julia code in Chebyshev plot figure.ipynb to plot the gure below.

2 of 2