ORF 307 Homework 2 Solutions
Elahe
Spring 2016
Problem 1. Do questions 3.1, 3.3, 3.5, 3.7. For 3.3, make a screenshot for each problem
you generate
• 3.1
pivot 1: Entering variable : x1 , Leaving variable: w2
pivot 2: Entering variable : x3 , Leaving variable: w3
To check the solution, use the pivot tool with Lexicographic label. Enter coefficient 1
for 1 in the first row, 2 in the second row, and 3 in the third row.
optimal value: 1, optimal solution: (x1 = 1, x2 = 0, x3 = 1, x4 = 0) and for the slack
variables (w1 = 2, w2 = 0, w3 = 0)
• 3.3 With seed (0216) the following problem is one example of the 10 problems you are
supposed to solve:
Entering variable : x4 , Leaving variable: w4
• 3.5
The set of constraints lacks non-negativity of all variables. (x2 ≥ 0 is missing), thus
the linear optimization problem is not stated in the standard form, thus the theorem
does not apply to it.
• 3.7
(a) (x2 , x6 ), (x2 , x4 ), (x5 , x4 ), (x5 , x1)
(b) (x5 , x4 ), (x5 , x1)
(c) (x2 , x4 )
Problem 2. Build an AMPL model for exercise 13.2 in the textbook. Solve the AMPL model
using a risk-aversion parameter µ = 0.2. Please submit your AMPL file on blackboard. Your
printed HW should include a print out of the AMPL code and output where applicable. Please
submit a paper copy (only code should be submitted online and on paper).
1
# Using the ample model disscused in the lecture
set Assets; # asset categories
set Dates; # dates
param T := card(Dates);
param mu; # risk aversion parameter
param R {Dates,Assets};
param mean {j in Assets} := ( sum{t in Dates} R[t,j] )/T;
param Rdev {t in Dates, j in Assets} := R[t,j] - mean[j];
var x{Assets} >= 0;
var y{Dates} >= 0;
maximize reward: sum{j in Assets} mean[j]*x[j] ;
s.t. risk_bound: sum{t in Dates} y[t] / T <= mu;
s.t. tot_mass: sum{j in Assets} x[j] = 1;
s.t. y_lo_bnd {t in Dates}: -y[t] <= sum{j in Assets} Rdev[t,j]*x[j];
s.t. y_up_bnd {t in Dates}: sum{j in Assets} Rdev[t,j]*x[j] <= y[t];
data;
set Assets := HairProducts Cosmetics Cash;
set Dates := 2007-01 2007-02 2007-03 2007-04;
param R: HairProducts Cosmetics Cash:=
2007-01 0.5 2.0 1.0
2007-02 2.0 0.5 1.0
2007-03 2.0 2.0 1.0
2007-04 1.0 2.0 1.0;
let mu := 0.2;
solve;
printf {j in Assets: x[j] > 0.001}: "%45s %6.3f \n", j, x[j];
printf: "Reward: %10.7f\n",
sum{j in Assets} mean[j]*x[j];
printf: "Risk: %10.5f\n",
sum{i in Dates} abs(sum{j in Assets} Rdev[i,j]*x[j]) / T;
Output:
ampl: reset;
ampl: model Portfolio;
MINOS 5.51: optimal solution found.
3 iterations, objective 1.4
HairProducts 0.400, Cosmetics 0.400, Cash 0.200
Reward: 1.4000000
Risk: 0.20000
2
Problem 3. Consider the following linear programming problem:
minimize 3x1 + 2x2
subject to 2x1 − x2 ≤ 7
−x1 + 5x2 ≤ 10
x1 − 2x2 ≤ 2
x1 , x2 ≥
(1) Introducing slack variables w1 , w2 , and w3 , write the problem in dictionary form.
minimize ξ = 3x1 + 2x2
subject to w1 = 7 − 2x1 + x2
w2 = 10 + x1 − 5x2
w3 = 2 − x1 + 2x2
x1 , x2 ≥
(2) Using the nonbasic variables, x1 and x2, to define a coordinate system, plot the set
of feasible solutions. Show on your plot the location of the current basic solution and the
location of the optimal solution. Also clearly label which constraint is associated with each
edge of the feasible polygon.
optimal solution
x2
3
- x1 + 5 x2 = 10
2 x1 - x2 = 7
2
x1 - 2 x2 = 2
1
Current basic solution
0
0 1 2 3 4 5 6
x1
3
(3) Do the first pivot. Then, plot the set of feasible solutions in the coordinate system
defined by the new pair of nonbasic variables. Again, label the point corresponding to the
current basic solution and the point corresponding to the optimal solution. And, again,
clearly label each edge of the polygon to make it clear which constraint they correspond to.
Second dictionary obtained by : Entering : x1 , leaving: w3 .
ξ =6 −3w3 +8x2
w1 =3 +2w3 −3x2
w2 =12 −w3 −3x2
w3 =2 −w3 +2x2
4
Optimal solution
x2
3 w3 + 3 x2 = 12
2 -2 w3 + 2 x2 = 3
1 w3 - 2 x2 = 2
Current basic solution
0
0 1 2 3 4 5 6
w3
(4) Continue pivoting and make a graph associated with each dictionary as described in
the proceeding step.
Third dictionary obtained by : Entering : x2 , leaving: w1 .
ξ =14 +7/3w3 −8/3w1
x2 =1 +2/3w3 −1/3w1
w2 =9 −3w3 +w1
w3 =4 +1/3w3 −2/3w1
4
10
6
w3
5
9 = 3 w3 - w1
4 = -1/3 w3 + 2/3 w1
3
Optimal solution
2
1 = -2/3 w3 + 1/3 w1
1
Current basic solution
0
0 1 2 3 4 5 6 7 8 9 10
w1
Fourth dictionary obtained by : Entering : w3 , leaving: w2 .
ξ =21 −7/9w2 −17/9w1
x2 =3 −2/9w2 −1/9w1
w3 =3 −1/3w2 +1/3w1
x1 =5 −1/9w2 −5/9w1
Since all the coefficients of nonbasic variables in the first row, are negative, the fourth
dictionary is optimal.// Optimal value: 21, Optimal solution: x1 = 5, x2 = 3
5
15
10 5 = 1/9 w2 + 5/9 w1
w1
5 3 = 2/9 w2 + 1/9 w1
Optimal solution 3 = 1/3 w2 - 1/3 w1
Current basic solution
0
0 5 10 15
w2