HW2_Solutions
pdf
keyboard_arrow_up
School
Michigan State University *
*We aren’t endorsed by this school
Course
1740
Subject
Industrial Engineering
Date
Dec 6, 2023
Type
Pages
6
Uploaded by MateWombat395
IOE 310 – Optimization and Computational Methods (Fall 2023)
Homework
№
2
IOE
: H
№
S
Due:
September 13th (by 11:59PM ET)
Problem 2
(5 points) (You will have one question like this in
almost
every homework assignment to ensure that
everyone fully reads the Syllabus.)
When and where should you go if you want help on your weekly
problem set?
Solution:
Office Hours, Piazza, IOE Computing Help Desk.
Problem 3
(8 points)
Are the following optimization problems linear programs (LPs)? Justify your answer.
(a)
max
x,y,z
x
+
y
-
z
s.t.
x
+ 2
y
≤
7
x
+ 2
z
≥
7
x, y, z
≥
0
.
Solution:
Yes. Objective function and constraints are linear.
(b)
max
x,y,z
xy
-
z
s.t.
x
+ 2
y
≤
7
x
+ 2
z
≥
7
x, y, z
≥
0
.
Solution:
No. Objective function term
xy
is not linear.
(c)
max
x,y,z
x
+
y
-
z
s.t.
x
+ 2
y
≤
7
x
+ 2
1
z
≤
7
x, y, z
≥
0
.
Solution:
No. Constraint term
1
z
is not linear (2nd constraint).
(d)
max
x,y,z
x
+
e
y
-
sin(
z
)
s.t.
x
+ 2
y
≤
7
x
+ 2
z
≤
7
x, y, z
≥
0
.
IOE Department – University of Michigan
Page 1 / 6
IOE 310 – Optimization and Computational Methods (Fall 2023)
Homework
№
2
Solution:
No. Objective function terms
e
y
and
sin(
z
)
are not linear.
Problem 4
(30 points)
Washtenaw Dairy makes ice cream for hungry students. They have the choice of making
4 flavors (Chocolate, Mint Chocolate Chip, Triple Chocolate, and Vanilla). Each scoop of flavor
requires different quantities of milk, sugar and chocolate (in ounces), and different processing times
(in hours, including freezing time). The requirements for each flavor are listed below.
Table 1: Per scoop requirements for different flavors
Chocolate
Mint
Chocolate Chip
Triple
Chocolate
Vanilla
Milk
(oz.)
4
3
2
2
Sugar
(oz.)
3
4
3
2
Cocoa
(oz.)
1
2
4
0
Processing
Time
(hours)
2
3.5
3
2
Washtenaw Dairy would like to produce as much ice cream as possible in order to maximize the
amount of revenue; however, they only have a limited amount of each ingredient in their inventory–
350 ounces of milk, 500 units of sugar, and 200 units of cocoa–and 600 hours of processing time.
One scoop of Chocolate, Mint Chocolate Chip, Triple Chocolate, and Vanilla sells for
$1
.
5
,
$2
,
$3
,
and
$1
, respectively.
(a)
(15 points)
Formulate a linear programming model (
note, only the model is required, not
the solution to the model
) to determine the number of scoops of each flavor to make in order
to maximize the total profit (fractional scoops are acceptable i.e., the decision variables may
be continuous).
Make sure you explicitly state the parameters, the variables, the objective, the constraints,
and the variable restrictions!
Solution: Parameters:
price of ice-cream (per scoop), quantity of ingredient (milk, sugar, coca)
per scoop of ice-cream, processing time per scoop of ice-cream, total amount of resources
(milk, sugar, cocoa, time).
Decision variables:
number of scoops of each ice-cream produced:
x
c
=
# scoops of chocolate ice-cream
x
mcc
=
# scoops of mint chocolate chip ice-cream
x
tc
=
# scoops of triple chocolate ice-cream
x
v
=
# scoops of vanilla ice-cream
Objective function:
maximize the amount of revenue from ice-cream:
max
x
c
,x
mcc
,x
tc
,x
v
1
.
5
x
c
+ 2
x
mcc
+ 3
x
tc
+ 1
x
v
IOE Department – University of Michigan
Page 2 / 6
IOE 310 – Optimization and Computational Methods (Fall 2023)
Homework
№
2
Constraints:
limitations due to ingredients and time budget:
4
x
c
+ 3
x
mcc
+ 2
x
tc
+ 2
x
v
≤
350
milk
3
x
c
+ 4
x
mcc
+ 3
x
tc
+ 2
x
v
≤
500
sugar
1
x
c
+ 2
x
mcc
+ 4
x
tc
+ 0
x
v
≤
200
cocoa
2
x
c
+ 3
.
5
x
mcc
+ 3
x
tc
+ 2
x
v
≤
600
time
Full (data dependent) model:
max
x
c
,x
mcc
,x
tc
,x
v
1
.
5
x
c
+ 2
x
mcc
+ 3
x
tc
+ 1
x
v
s.t.
4
x
c
+ 3
x
mcc
+ 2
x
tc
+ 2
x
v
≤
350
3
x
c
+ 4
x
mcc
+ 3
x
tc
+ 2
x
v
≤
500
x
c
+ 2
x
mcc
+ 4
x
tc
≤
200
2
x
c
+ 3
.
5
x
mcc
+ 3
x
tc
+ 2
x
v
≤
600
x
c
, x
mcc
, x
tc
, x
v
≥
0
(b)
(15 points)
Write a data independent (generic) version of the model in (a). Make sure to ex-
plicitly define all sets, parameters, the variables, the objective, the constraints, and the variable
restrictions!
Solution: Data Independent model:
Sets:
–
I
= set of ice-cream types (
I
=
{
chocolate, mintchocolatechip, triplechocolate, vanilla
}
)
–
J
= set of ingredients and other limiting factors (
J
=
{
milk, sugar, coca, time
}
)
Decision variables:
–
x
i
= # of scoops of ice-cream
i
∈ I
Parameters (data):
–
π
i
= revenue per scoop of ice-cream
i
∈ I
–
b
j
= total amount of resource
j
∈ J
–
a
ij
= amount of resource
j
∈ J
required for a scoop of ice-cream
i
∈ I
Model:
max
x
X
i
∈I
π
i
x
i
s.t.
X
i
∈I
a
ij
x
i
≤
b
j
,
∀
j
∈ J
x
i
≥
0
,
∀
i
∈ I
OR
max
x
π
T
x
s.t.
Ax
≤
b,
x
≥
0
IOE Department – University of Michigan
Page 3 / 6
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
IOE 310 – Optimization and Computational Methods (Fall 2023)
Homework
№
2
Problem 5
(26 points + 3 points bonus)
A farmer in Michigan must decide how many acres of corn and wheat
to plant this year. The farmer has 17 acres of land and 90 hours per week of labor. An acre of corn
yields 7 bushels of corn and requires 7 hours of labor per week. An acre of wheat yields 9 bushels
of wheat and requires 10 hours of labor per week. Government regulations require that a minimum
of 10 bushels of corn and 10 bushels of wheat be produces during the current year. All wheat can
be sold at
$2
a bushel, and all corn can be sold at
$5
a bushel.
(a)
(13 points)
Let
x
1
=
number of acres of corn planted, and
x
2
=
number of acres of wheat
planted. Using these decision variables, formulate the above as a linear optimization problem.
Solution: Decision variables:
x
1
=
number of acres of corn planted, and
x
2
=
number of acres
of wheat planted.
Objective Function:
maximize profit.
–
1 acre of corn
⇒
7 bushels of corn;
$
5/bushel of corn
⇒
$35
/acre of corn
–
1 acre of wheat
⇒
9 bushels of wheat;
$
2/bushel of wheat
⇒
$18
/acre of wheat
max
x
35
x
1
+ 18
x
2
Constraints:
–
Land:
x
1
+
x
2
≤
17
–
Labor:
7
x
1
+ 10
x
2
≤
90
–
Government:
7
x
1
≥
10
,
9
x
2
≥
10
–
Nonegativity:
x
1
, x
2
≥
0
Full Model:
max
x
35
x
1
+ 18
x
2
s.t.
x
1
+
x
2
≤
17
7
x
1
+ 10
x
2
≤
90
7
x
1
≥
10
9
x
2
≥
10
x
1
, x
2
≥
0
(b)
(13 points)
Using the variables
x
1
=
number of bushels of corn produced and
x
2
=
number
of bushels of wheat produced, reformulate the farmers LP.
Solution: Decision variables:
x
1
=
number of bushels of corn produced and
x
2
=
number of
bushels of wheat produced.
Objective Function:
maximize profit.
–
$5
bushel of corn;
$2
bushel of wheat
max
x
5
x
1
+ 2
x
2
Constraints:
IOE Department – University of Michigan
Page 4 / 6
IOE 310 – Optimization and Computational Methods (Fall 2023)
Homework
№
2
–
Land:
x
1
7
+
x
2
9
≤
17
–
Labor:
7
x
1
7
+
10
x
2
9
≤
90
–
Government:
x
1
≥
10
,
x
2
≥
10
–
Nonegativity:
x
1
, x
2
≥
0
Full Model:
max
x
5
x
1
+ 2
x
2
s.t.
x
1
7
+
x
2
9
≤
17
x
1
+
10
x
2
9
≤
90
x
1
≥
10
x
2
≥
10
x
1
, x
2
≥
0
BONUS
Will the two LPs yield the same solution? Decision variables? and Objective function value?
Why?
Solution:
Same minimizer. If
f
*
a
and
f
*
b
are the optimal function values of the problems from
(
a
)
and
(
b
)
, respectively, then,
f
*
a
=
f
*
b
. The optimal decision variables are not the same
(since the units are different). However,
x
*
a,
1
=
x
*
b,
1
7
and
x
*
a,
2
=
x
*
b,
2
9
.
Problem 6
(26 points)
Ford manufactures two types of trucks: 1 and 2. Each truck must go through the painting
shop and assembly shop. If the painting shop were completely devoted to painting Type 1 trucks,
then 800 per day could be painted; if the painting shop were completely devoted to painting Type
2 trucks, then 700 per day could be painted. If the assembly shop were completely devoted to
assembling truck 1 engines, then 1,500 per day could be assembled; if the assembly shop were
completely devoted to assembling truck 2 engines, then 1,200 per day could be assembled. Each
Type 1 truck contributes
$300
to profit; each Type 2 truck contributes
$500
to profit. Ford’s goal
is to maximize profit. Formulate the above as a linear optimization problem.
Solution: Decision variables:
x
1
=
number of Truck 1 produced per day and
x
2
=
number of Truck 2
produced per day.
Objective Function:
maximize profit.
–
$300
Type 1;
$500
Type 2
max
x
300
x
1
+ 500
x
2
Constraints:
–
Paint:
7
x
1
+ 8
x
2
≤
5600
–
Assembly:
12
x
1
+ 15
x
2
≤
18000
–
Nonegativity:
x
1
, x
2
≥
0
IOE Department – University of Michigan
Page 5 / 6
IOE 310 – Optimization and Computational Methods (Fall 2023)
Homework
№
2
Full Model:
max
x
300
x
1
+ 500
x
2
s.t.
7
x
1
+ 8
x
2
≤
5600
12
x
1
+ 15
x
2
≤
18000
x
1
, x
2
≥
0
IOE Department – University of Michigan
Page 6 / 6
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help