Description
Problem 1 (20pts). Reformulate NLP as LP
Reformulate the following problems as linear programming
minimize 2×2 + |x1 − x3|
s.t. |x1 + 2| + |x2| ≤ 5
x
2
3 ≤ 1
Please also write down its standard form.
Problem 2 (35pts). Basic solutions and basic feasible solutions
Consider the following linear optimization problem:
maximize x1 + 2×2 + 4×3
s.t. x1 + x3 ≤ 8
x2 + 2×3 ≤ 15
x1, x2, x3 ≥ 0
(a) Transform it into standard form;
(b) Argue without solving this LP that there must exist an optimal solution with no more than 2
positive variables;
(c) List all the basic solutions and basic feasible solutions (of the standard form);
(d) Find the optimal solution by using the results in step (c).
Problem 3 (45pts). A Robust LP Formulation
In this exercise, we consider the following optimization problem:
min
x∈Rn
c
>x subject to kAx − bk∞ ≤ δ, x ≥ 0 (1)
where A ∈ Rm×n
, b ∈ Rm, c ∈ Rn, and δ ≥ 0 are given and kyk∞ = max1≤i≤p |yi
| denotes the
maximum norm of a vector y ∈ Rp
.
In the case δ = 0, problem (1) coincides with the standard
form for linear programs. The choice δ > 0 can be useful to model situations where A and/or b are
not fully or exactly known, e.g., when A and/or b contains certain uncertainty (can be caused by
noise). In this case, problem (1) belongs to the so-called robust optimization.
(a) Rewrite the optimization problem (1) as a linear problem.
(b) We now consider a specific application of problem (1).
The fruit store in Pandora is producing two different fruit salads A and B. The smaller fruit
salad A consists of “1/4 mango, 1/8 pineapple, 3 strawberries”; the larger fruit salad B consists
of “1/2 mango, 1/4 pineapple, 1 strawberry”. The profits per fruit salad and the total number
of fruits in stock are summarized in the following table:
Mango Pineapple Strawberry Net profit
Fruit salad A 1/4 1/8 3 10 RMB
Fruit salad B 1/2 1/4 1 20 RMB
Stock / Resources 25 10 120
Suppose all fruits need to be processed and completely used to make the fruit salads A and B.
Given these constraints, formulate a linear program to maximize the total profits of the fruit
store. Show that this program can be expressed in standard form
min
x∈Rn
c
>x subject to Ax = b, x ≥ 0,
with n = 2 and m = 3. In addition, is this linear programming solvable?
Note: Since we want to produce “complete fruit salads”, the variables x1 and x2 should
actually be modeled as integer variables: x1, x2 ∈ Z. However, since we do not know how to
deal with these integer constraints in general at this moment, you may just ignore them for
now.
(c) One of the employee found some additional fruits in a storage crate and the manager of the fruit
shop decides to determine the production plan by using the robust formulation (1). Consider
the robust variant of the problem in part (b) with δ = 5.
• Sketch the feasible set of this problem.
• Solve the problem graphically, i.e., Calculate the optimal value and the optimal solution
set.
• Which constraints are active in the solution?
• Find one integer solution of this problem.