## 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.

1

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.

3