MATH 340 Homework 1 Due Friday, January 22th Only part of the problems may be graded. But, you have to submit all the problems.
1.
Submit only pdf files and submit one file for each of the three problems. We consider the following linear programming problem.
9 marks
subject to
minimize x1 − 3×2 − x3 x1 +x2 +x3 = 3
−x1 + x2 ≤ 1 x1 ≥ 0
x2 unconstrained x3 ≥ 0.
(a) Put the linear programming problem in standard form.
Solution:
“minimize x1 − 3×2 − x3” ⇔ “maximize − x1 + 3×2 + x3”.
“x1 +x2 +x3 =3”⇔“x1 +x2 +x3 ≤3and−x1 −x2 −x3 ≤−3”.
Also, let x2 = x+2 − x−2 , with x+2 ,x−2 ≥ 0. Substituting in x+2 − x−2 for x2 the problem becomes:
maximize − x1 + 3x+2 − 3x−2 + x3 subject to x1 +x+2 −x−2 +x3 ≤ 3
−x1 −x+2 +x−2 −x3 ≤−3 − x 1 + x +2 − x −2 ≤ 1
x1,x+2 ,x−2 ,x3 ≥ 0.
2.
(b) Solve the linear program in standard form using PuLP in Python. Download the Jupyter notebook output as a .pdf and submit.
(c) Express the optimal solution and optimal value of the original linear program.
We will consider the unit ball in two dimensions B = {⃗x ∈ R2 : ∥⃗x∥ ≤ 1}. Page 1 of 3
Solution: See file HW1 Jupyter.pdf
Solution: The optimal solution in standard form was x1 = 1, x+2 = 2, x−2 = 0, and x3 = 0 with optimal value of 5. For the original problem, the optimal solutionisx1 =1,×2 =2,×3 =0withoptimalvalueof−5.
8 marks
MATH 340 Homework 1 Due Friday, January 22th
(a)
Consider the optimization problem to maximize the function f(⃗x) = ⃗c·⃗x for a given nonzero vector ⃗c ̸= ⃗0 ∈ R2, over points ⃗x ∈ B. Express the optimal solution ⃗x in terms ⃗c. Justify that it is optimal. (Hint: Recall the Cauchy-Schwarz inequality.)
Solution: We know from the Cauchy-Schwarz inequality ⃗c · ⃗x ≤ ∥ ⃗c ∥ ∥ ⃗x ∥
where the equality holds when and only when ⃗c and ⃗x are parallel, that is, ⃗x = t⃗c for some scalar t > 0. The largest value on the unit ball is obtained from t = 1/∥⃗c∥, so ⃗x∗ = ⃗c/∥⃗c∥, with value f(⃗x∗) = ∥⃗c∥. The Cauchy-Schwarz inequality implies that this is optimal because ∥⃗x∥ ≤ 1 for ⃗x in B so f(⃗x) ≤ ∥⃗c∥.
(b)
Express B as the feasible region for an infinite number of linear inequalities.
Solution: For each unit-vector ⃗v ∈ R2 with ∥⃗v∥ = 1, we consider the inequality
⃗v · ⃗x ≤ 1 .
If ⃗x ∈ B then ⃗x satisfies all the inequalities by the Cauchy-Schwartz inequality.
If ⃗x ̸∈ B then ⃗x fails to satisfy the inequality for the unit-vector ⃗v = ⃗x/∥⃗x∥, because
⃗v · ⃗x = ∥ ⃗x ∥ > 1 .
3.
From Introduction to Operations Research by Frederick Hillier, Exercise 3.1-7.
8 marks
The Whitt Window Company, a company with only three employees, makes two differ- ent kinds of hand-crafted windows: a wood-framed and an aluminum-framed window. The company earns $300 profit for each wood-framed window and $150 profit for each aluminum-framed window. Doug makes the wood frames and can make 6 per day. Linda makes the aluminum frames and can make 4 per day. Bob forms and cuts the glass and can make 48 square feet of glass per day. Each wood-framed window uses 6 square feet of glass and each aluminum-framed window uses 8 square feet of glass.
The company wishes to determine how many windows of each type to produce per day to maximize total profit.
1. Formulate a linear programming model for this problem. Explain what each deci- sion variable and constraint represents.
Solution: Decision variables:
x1: quantity of wood-framed windows
Page 2 of 3
MATH 340 Homework 1 Due Friday, January 22th
x2: quantity of aluminum-framed windows Maximize total profit 300×1 + 150×2. Constraints
Doug (wood): x1 ≤ 6 Linda (aluminum) : x2 ≤ 4 Bob (glass) : 6×1 + 8×2 ≤ 48.
2. Graph the feasible region and use the graphical method to solve for the optimal solution.
Solution:
From the graph it is best to use x1 = 6. Then solving for the glass constraint we have x2 = (48 − 36)/8 = 3/2. The total profit is 2025.
Page 3 of 3