Homework 1: Linear programs

CS/ECE/ISyE 524 Introduction to Optimization
Homework 1: Linear programs

See the course website for instructions and submission details.
1. [5 pts] Warm-up. Model the following problem in JuMP.
maximize
x1,x2,x3
5x1 − x2 + 11x3
subject to: 2x1 ≥ x2 + x3
0 ≤ xj ≤ 3, j ∈ {1, 2, 3}
Solve this problem using Clp, ECOS, and SCS solvers. Compare the answers found by each solver: which
solver is more accurate? which is fastest (use the @time macro)? can you speculate as to why?
2. [10 pts] Standard form with equality constraints. Rather than using the standard LP form we
saw in class, some prefer using a form where all variables are nonnegative, all constraints are equality
constraints, and the cost function is a minimization. So a general LP would look like:
minimize c
Tx
subject to: Ax = b
x ≥ 0
(1)
Consider the following LP:
maximize
z1,z2,z3,z4
3z1 − z2
subject to: −z1 + 6z2 − z3 + z4 ≥ −3
7z2 + z4 = 5
z3 + z4 ≤ 2
−1 ≤ z2 ≤ 5, −1 ≤ z3 ≤ 5, −2 ≤ z4 ≤ 2
a) Transform the above LP into the equality-constrained standard form of (1). What are A, b, c,
and x? Be sure to explain how the decision variables of your transformed LP relate to those of
the original LP.
b) Solve both versions of the LP using JuMP and show that you can recover the optimal z and
objective value by solving your transformed version of the LP.
1 of 2
CS/ECE/ISyE 524 Introduction to Optimization L. Lessard, Spring 2017
3. [10 pts] Crop planning. Farmer Jane owns 45 acres of land. She is going to plant each with wheat
or corn. Each acre planted with wheat yields $200 profit; each with corn yields $300 profit. The labor
and fertilizer used for each acre are given in the table below. One hundred workers and 120 tons of
fertilizer are available.
Wheat Corn
Labor 3 workers 2 workers
Fertilizer 2 tons 4 tons
a) How should Jane plant her crops to maximize profit? Model and solve this problem using JuMP.
b) Solve the problem graphically and confirm that you obtain the same solution.
4. [10 pts] Alloy blending. The company Steelco has received an order for 500 tons of steel to be used
in shipbuilding. The steel must have the following characteristics:
Chemical Element Minimum Grade (%) Maximum Grade (%)
Carbon (C) 2 3
Copper (Cu) 0.4 0.6
Manganese (Mn) 1.2 1.65
The company has seven different raw materials in stock that may be used for the production of this
steel. The following table lists the grades, available amounts and prices for all materials:
Raw Material C% Cu% Mn% Availability in tons Cost in $/ton
Iron alloy 1 2.5 1.3 400 200
Iron alloy 2 3 0.8 300 250
Iron alloy 3 0.3 600 150
Copper 1 90 500 220
Copper 2 96 4 200 240
Aluminum 1 0.4 1.2 300 200
Aluminum 2 0.6 250 165
Determine the composition of the steel that minimizes the production cost.
2 of 2