## 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);

1

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

2

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

3