Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

ISE 530 Optimization Methods for Analytics

Homework 4

Question 1 (duality and optimality conditions)

Consider the following investment problem. Given $ 100 to invest, you need to allocate this money into six possible investments. The returns of each investment is given in Table 1.

Table 1: Returns (per dollar invested)

In addition to the budget constraint, you have the following diversiication constraints:

. You cannot allocate more than 30 dollars in investments 1 and 2.

. Investment 5 is very risky, while investment 6 is risk-free. Thus, for every dollar in excess of $10 that you allocate to investment 5, you need to allocate one dollar to investment 6. For example, if you invest $13 dollars in investment 5, then you need to invest $3 in investment six.

. You can allocate at most $50 in investments 3, or 4.

Letting xi  be the money  allocated to investment  i,  the investment problem can be formulated as

max 1.5x1 + 2x2 + 1.2x3 + 1.3x4 + 2x5 + 1.1x6

s.t. x1 + x2 + x3 + x4 + x5 + x6 = 100                           (y1)

x1 ≤ 30                                                                        (y2)

x2 ≤ 30                                                                        (y3)

x3 + x4 ≤ 50                                                                 (y4)

x6 − x5 ≥ −10                                                               (y5)

x1, x2, x3, x4, x5, x6 ≥ 0.

Let y1 , . . . , y5 be the dual variables associated with each constraint. Answer the following questions.

1. Formulate the dual problem.

2. Write the optimality conditions.

3. An optimal dual solution vector is y1(*)   =  1.55, y2(*)   = 0, y3(*)   = 0.45, y4(*)   = 0 and y5(*) = -0.45. Compute an optimal solution for the primal.

Question 2 (duality and optimality conditions)

Given nonnegative vectors c, a 2 Rn+ and scalar b ≥ 0, consider the optimization problem

Question 3 (Simplex method)

Solve the following problem by the simplex method (show your work).

max 4x1 + x2 - x3

s.t. x1 + 3x3  ≤ 6

3x1 + x2 + 3x3  ≤ 9

x1 ; x2 ; x3  ≥ 0:

Start from solution x1 = x2 = x3  = 0.

Question 4 (Simplex method)

Solve the following problem by the simplex method (show your work).

max 4x1 + x2 - x3

s.t. x1 + 3x3  ≤ 6

3x1 + x2 + 3x3  ≤ 9

x1 + x2 - x3  ≤ 2

x1 ; x2 ; x3  ≥ 0:

Start from solution x1 = x2 = x3  = 0.

Question 5 (Simplex method)

Solve the following problem by the simplex method (show your work).

max x1 + 2x2 + x3

s.t. x1 + x2  ≤ 3

x2 + x3  ≤ 4

x1 + x3  ≤ 5

x1 ; x2 ; x3  ≥ 0:

Start from solution x1 = x2 = x3  = 0.