Homework Assignment 2: Due 4:00pm Thursday, Oct 16, 2014

MS&E 211
Fall 2014
Linear and Nonlinear Optimization
Oct 9, 2014
Homework Assignment 2: Due 4:00pm Thursday, Oct 16, 2014
There is a homework collection box in the basement of Huang Engineering Center. Please
make sure your submissions are legible and on time - late submissions will not be accepted!
Problem 1
max
x1 + 3x2
s.t
x1 + 0.1x2
≤2
0.4x1 + 2x2 ≤ 3 .
x1 + 1.1x2
≤3
x1 , x2
≥0
a) List all basic feasible solutions of the above LP.
b) Plot the feasible region and show each BFS on the plot.
c) Find the optimal solution.
Problem 2 Consider the region described by the constraints below and answer the questions that follow.
x
≥0
y
≥0
x
≤5
y
≤8
x+y
≥4
7x + y ≤ 36
a) Plot the feasible region described by the above constraints and identify its extreme
points.
b) What value(s) of (x, y) maximizes the function f (x, y) = x+y? What value(s) of (x, y)
minimizes the function f (x, y)?
c) How would the answers to part (b), as well as the maximum and minimum value of
f (x, y), be affected if the non-negativity constraints are removed?
Edge Capacity
Cost
Failure Prob.
AC
5
$7000
0.4
AD
4
$4000
0.9
AB
1
$100
1
CD
3
$1000
0.2
CB
1
$2000
0.8
DB
2
$6000
0.1
Figure 1: Pipeline network
Problem 3 Consider the following optimization problem with absolute values:
min
cT x + d T y
s.t
Ax + By ≤ b
yi = |xi |
∀i.
a) First assume that all entries of B and d are non-negative and provide a linear pogromming formulation of the above problem.
b) Provide an example to show that if B has negative entries then the above optimization
problem may have a local minimum which is not a global minimum.
Problem 4 Consider the oil pipeline network exhibited in Figure 1. The table gives the
capacity of each pipeline (in million gallons per hour), the cost per million gallons of sending
oil over a pipeline, and the failure probability.
For each of the following, provide and solve LP (by using excel) whose solution gives the
desired information. Please specify the decision variable, objective function and constraints.
a) The cheapest way of sending 2 millions gallons per hour from A to B.
b) The most reliable path to send 1 million gallons per hour from A to B (assuming each
probability is independent).
(Hint: ln(xy) = ln(x) + ln(y), x, y > 0)
Problem 5 You are given an N × N matrix A such that each entry of the matrix is a
non-negative number. Further assume that the sum of the entries in any row or column is
an integer. You are allowed to round each fractionally entry in the matrix i.e. to change
each non-integer entry to either the next higher or next lower integer. Prove that there is a
way of rounding each entry such that the row and column sums remain unchanged.
Hint: Consider a min-cost flow problem with 2N nodes, one for each row and one for each
column. Then, apply the integrality theorem from class.
Problem 6 Let g : Rn → R be a convex function and let c be some constant. Show that
the set S = {x ∈ Rn |g(x) ≤ c} is convex.
`