Description
Problem 1 (25pts). A company produces two kinds of products. A product of the first type
requires 1/8 hours of assembly labor, 1/4 hours of testing, and $1.2 worth of raw materials. A
product of the second type requires 1/2 hours of assembly, 1/6 hours of testing, and $0.9 worth
of raw materials. Given the current personnel of the company, there can be at most 90 hours of
assembly labor and 80 hours of testing each day. Products of the first and second type have a
market value of $9 and $8 respectively.
(a) Formulate a linear optimization that maximizes the daily profit of the company. (For simplicity,
you do not need consider the completeness of products. That is, the variables may take float
values.)
(b) Write the standard form of the LP you formulated in part (a).
(c) Consider the following modification to the original problem: Suppose that up to 40 hours of
overtime assembly labor can be scheduled, at a cost of $8 per hour. Can it be easily incorporated
into the linear optimization formulation and how?
(d) Solve the LP using MATLAB (for the original problem).
Problem 2 (25pts). The China Railroad Ministry is in the process of planning relocations of
freight cars among 5 regions of the country to get ready for the fall harvest. Table1a shows the
cost of moving a car between each pair of regions. Table1b shows the current number of cars in
each region and the number needed for harvest shipping.
From/To 1 2 3 4 5
1 − 20 13 11 28
2 20 − 18 8 46
3 13 18 − 9 27
4 11 8 9 − 20
5 28 46 27 20 −
(a) Cost of moving a car
1 2 3 4 5
Present 110 335 400 420 610
Need 150 200 600 200 390
(b) Number of current and needed cars
S T
7
3
2 6
5
4
4
3
5
7
1
2
2
5
2
3
1
Figure 1: The graph of the shortest path problem
Write down a linear optimization to compute the least costly way to move the cars such us the
need is met. Solve the problem using MATLAB.
Problem 3 (20pts). Write a MATLAB code to use linear optimization to solve the shortest path
problem. Suppose the input of the problem will be an n × n matrix of W, where wij is the length
of the path from i to j (in general, wij does not necessarily equal wji). In our implementation,
we always use 1 to denote the source node (the s node in the lecture slides), and n to denote the
terminal node (the t node in the lecture slides).
In addition, we assume for any i and j, there is a
path, i.e., the set of E is all pairs of nodes. This is without loss of generality since one can set wij
to be an extremely large number if there is no edge between i and j, effectively eliminating it from
consideration.
After writing the code, you are asked to solve the concrete problem in the lecture slides, with the
given labeling shown in Figure 1. Basically, you need to input the W matrix for this case, then
solve it, and then report your solution (the optimal path).
Problem 4 (30pts). Reformulate the following problems as linear programming problems
2
(a)
min 2x + 3|y − x|
s.t. |x + 2| + |y| ≤ 5
where x, y ∈ R.
(b)
min c
⊤x + f(d
⊤x)
s.t. Ax ≥ b
where x, c, d ∈ R
n
, A ∈ R
m×n
, b ∈ R
m, f(α) = max{α, 0, 2α − 4} for α ∈ R,
(c)
min c
⊤x
s.t. ∥Ax − b∥∞ ≤ δ
x ≥ 0
where x ∈ R
n
, A ∈ R
m×n
, b ∈ R
m.