ORF 307 Homework 4 Solutions

Carson M Eisenach
Spring 2016

Problem 1. Problem 5.6

Observing that this problem is dual feasible, one should use the dual simplex method to
solve it.

Problem 2. Problem 5.10

Print out a screenshot, the tool checks your work.

Problem 3. Problem 5.11

Print out a screenshot, the tool checks your work.

Problem 4. Problem 5.13

Each transformation contains two steps: 1. Find the dual of the primal problem 2. Change
the “minimization” on the dual objective to “maximization”. After four transformations, you
arrive back at the original problem and it seems that at each step, the objective value is non-
decreasing.
To see the flaw in the reasoning it is important to note that when a linear programming
problem has a minimum value, it does not necessarily have a maximum value. That means
while the dual problem has a optimal value, the corresponding “maximization” problem can
be unbounded. When the primal problem is unbounded, duality theory tells us that the dual
problem will be infeasible. Now, when you are trying to maximize an infeasible problem,
the objective will be negative infinity. This tells us that during one of the transformations,
the objective value will go from ∞ to −∞ – see the table below for what will happen under
the transformation. Therefore the error in the line of reasoning is that it does not take into
account that a problem can become infeasible.

Problem Step 1 Step 2 Step 3 Step 4 Step 5 (Step 1)

Primal (maximize) optimal optimal unbounded ∞ infeasible −∞ optimal
Dual (minimize) optimal optimal infeasible ∞ unbounded −∞ optimal

The theorem could be “When considering the four transformations listed in the problem
5.13, if at least one transformation increases the objective value strictly, then there must
exist another transformation which will change the objective value from ∞ to −∞, i.e., at
least of the other three transformation will change an unbounded problem to an infeasible
problem”. This does not violate strong duality theory. You can also conclude a theorem
along the lines of “around half of the LP problems have optimal values and 1/4 of the LP
problems are unbounded and 1/4 of the LP problems are infeasible”.
Of course, there are examples where the four inequalities are indeed all equalities. For
example, you can take the trivial LP – let the first objective to be constant 0 and let bi = 0
and aij = 0 as well, then the objective value will never change.

Problem 5. Problem 5.15

1
 Since we have a candidate solution, all we need to check is that it is both primal and dual
feasible and the optimal value is the same. Just plugging in the values for xj shows us that
the β constraint is satisfied. We just need to check then that xj ≤ 1. For j > k, j < k this is
trivial. For j = k notice that by how k is defined the two inequalities are true

β − qk+1 − · · · − qn ≥ 0

and
β − qk − qk+1 − · · · − qn ≤ 0
Using the second inequality, we can move qk to the RHS and divide by qk to get the desired
result. Therefore the solution is primal feasible. The value associated with this solution is
n
β − qk+1 − · · · − qn X
pk + pi
qk
i=k+1

Next, the dual problem is given by

m
X
minimize βy0 + yi
j=1

subject to qi y0 + yi ≥ pi for i = 1, . . . , n
yi ≥ 0

First we check feasibility. Plugging into each of these constraints, for j ≤ k, we get qj pqkk ≥ pj
which is true by the assumption. For j > k, after plugging in, we get
pk pj pk pj
qj + qj ( − ) = qj = qj ≥ qj
qk qj qk qj
verifying that these constraints are also satisfied. All that remains is to compute the value
of the objective function of this dual feasible solution
n n
pk X pj pk β − qk+1 − · · · − qn X
β + qj ( − ) = p k + pi
qk qj qk qk
j=k+1 i=k+1

Thus as the two objective values agree, we see that these primal and dual feasible solutions
are both optimal.
Problem 6. Problem 6.1

(a) The basic variables are x1 , x3 . The nonbasic variables are x2 , x4 , x5 .

(b) The current primal solution is  
2
x∗B =
0

(c) The current dual solution is 


3
∗
zN = −2
0

2
 (d) In this case the matrix B is given as
 
−2 −3
B=
1 2

Therefore      
−1 −2 −3 10 1 0 1 −2 −3
B N= × =
1 2 −7 0 1 −4 1 2

(e) The primal solution is feasible.

(f) The dual solution is not feasible and thus it cannot be optimal.

(g) It is degenerate as one of its entries is 0.

Problem 7. AMPL Problem

The code for all three parts is attached to the end of this document.

(a) The optimal value is 5.4. For each of the students their GPA and aptitudes are

– John GPA: 3.55 Aptitude: 3.625

– Paul GPA: 3.65 Aptitude: 3.325
– George GPA: 3.20 Aptitude: 2.925
– Ringo GPA: 2.71 Aptitude: 2.625
– Yoko GPA: 3.80 Aptitude: 3.625

For each of the courses the course average and easiness scores are

– AST 305 Average: 3.48 Easiness: 0.375

– BIO 201 Average: 3.67 Easiness: 0.375
– COS 127 Average: 2.70 Easiness: -0.225
– ECO 101 Average: 3.50 Easiness: 0.375
– ECO 221 Average: 3.37 Easiness: 0.075
– ECO 307 Average: 3.57 Easiness: 0.075
– HIS 203 Average: 3.08 Easiness: -0.625
– HIS 411 Average: 3.68 Easiness: 0.375
– PHY 211 Average: 3.13 Easiness: 0.075
– PSY 327 Average: 3.90 Easiness: 0.375
– REL 242 Average: 3.58 Easiness: 0.375
– SLA 101 Average: 2.00 Easiness: -1.625

(b) The optimal value is 4.57. For each of the students their GPA and aptitudes are

– John GPA: 3.55 Aptitude: 3.42849

– Paul GPA: 3.65 Aptitude: 3.21237

3
 – George GPA: 3.20 Aptitude: 2.95821
– Ringo GPA: 2.71 Aptitude: 2.38715
– Yoko GPA: 3.80 Aptitude: 3.42849
For each of the courses the course average and easiness scores are
– AST 305 Average: 3.48 Easiness: 0.271505
– BIO 201 Average: 3.67 Easiness: 0.341794
– COS 127 Average: 2.70 Easiness: -0.687153
– ECO 101 Average: 3.50 Easiness: 0.341794
– ECO 221 Average: 3.37 Easiness: 0.271505
– ECO 307 Average: 3.57 Easiness: 0.0876344
– HIS 203 Average: 3.08 Easiness: -0.428495
– HIS 411 Average: 3.68 Easiness: 0.487634
– PHY 211 Average: 3.13 Easiness: -0.0871534
– PSY 327 Average: 3.90 Easiness: 0.487634
– REL 242 Average: 3.58 Easiness: 0.341794
– SLA 101 Average: 2.00 Easiness: -1.42849
(c) The optimal value is 3.79. For each of the students their GPA and aptitudes are
– John GPA: 3.55 Aptitude: 3.45103
– Paul GPA: 3.65 Aptitude: 3.22368
– George GPA: 3.20 Aptitude: 2.91449
– Ringo GPA: 2.71 Aptitude: 2.37477
– Yoko GPA: 3.80 Aptitude: 3.46695
For each of the courses the course average and easiness scores are
– AST 305 Average: 3.48 Easiness: 0.248973
– BIO 201 Average: 3.67 Easiness: 0.385509
– COS 127 Average: 2.70 Easiness: -0.67477
– ECO 101 Average: 3.50 Easiness: 0.385509
– ECO 221 Average: 3.37 Easiness: 0.233054
– ECO 307 Average: 3.57 Easiness: 0.0763198
– HIS 203 Average: 3.08 Easiness: -0.466946
– HIS 411 Average: 3.68 Easiness: 0.47632
– PHY 211 Average: 3.13 Easiness: -0.0747705
– PSY 327 Average: 3.90 Easiness: 0.47632
– REL 242 Average: 3.58 Easiness: 0.385509
– SLA 101 Average: 2.00 Easiness: -1.45103

4
# BEATLES UNIVERSITY − PART A

#FRAMEWORK
s e t STUDENTS;
s e t COURSES;
s e t GRADES w i t h i n {STUDENTS, COURSES} ;
param g r a d e {GRADES} ;
var a p t i t u d e {STUDENTS} ;
var e a s i n e s s {COURSES} ;
var dev {GRADES} >= 0 ;

#MODEL
minimize sum dev : sum { ( s , c ) i n GRADES} dev [ s , c ] ;
s u b j e c t t o d e f p o s d e v { ( s , c ) i n GRADES} : a p t i t u d e [ s ] + e a s i n e s s [ c ]
− g r a d e [ s , c ] <= dev [ s , c ] ;
s u b j e c t t o d e f n e g d e v { ( s , c ) i n GRADES} : −dev [ s , c ] <= a p t i t u d e [ s ]
+ e a s i n e s s [ c ] − grade [ s , c ] ;
s u b j e c t t o n o r m a l i z e d e a s i n e s s : sum { c i n COURSES} e a s i n e s s [ c ] = 0 ;

#DATA
data ;
s e t STUDENTS := John Paul George Ringo Yoko ;
s e t COURSES := AST305 BIO201 COS127 ECO101 ECO221
ECO307 HIS203 HIS411 PHY211 PSY327 REL242 SLA101 ;
param : GRADES: g r a d e :=
[ ∗ , AST305 ] John 3 . 7 Paul 3 . 7 George 3 . 3 Ringo 2 . 7 Yoko 4
[ ∗ , BIO201 ] Paul 3 . 7 George 3 . 3 Yoko 4
[ ∗ , COS127 ] George 2 . 7 Ringo 1 . 7 Yoko 3 . 7
[ ∗ , ECO101 ] John 4 . 0 Paul 3 . 7 George 3 . 3 Ringo 3
[ ∗ , ECO221 ] Paul 3 . 7 Ringo 2 . 7 Yoko 3 . 7
[ ∗ , ECO307 ] John 3 . 7 Paul 3 . 3 George 3 . 7
[ ∗ , HIS203 ] John 3 George 3 Ringo 3 . 3 Yoko 3
[ ∗ , HIS411 ] John 4 Paul 3 . 7 Ringo 3 Yoko 4
[ ∗ , PHY211 ] Paul 3 . 7 George 3 Ringo 2 . 3
[ ∗ , PSY327 ] John 4 Paul 3 . 7 Yoko 4
[ ∗ , REL242 ] John 4 George 3 . 3 Ringo 3 Yoko 4
[ ∗ , SLA101 ] John 2 ;

5
# BEATLES UNIVERSITY − PART B

#FRAMEWORK
s e t STUDENTS;
s e t COURSES;
s e t GRADES w i t h i n {STUDENTS, COURSES} ;
param g r a d e {GRADES} ;
var a p t i t u d e {STUDENTS} ;
var e a s i n e s s {COURSES} ;
var dev {GRADES} >= 0 ;

#MODEL
minimize sum dev : sum { ( s , c ) i n GRADES} dev [ s , c ] ˆ 2 ;
s u b j e c t t o d e v i a t i o n { ( s , c ) i n GRADES} : a p t i t u d e [ s ] + e a s i n e s s [ c ]
+ dev [ s , c ] = g r a d e [ s , c ] ;
s u b j e c t t o n o r m a l i z e d e a s i n e s s : sum { c i n COURSES} e a s i n e s s [ c ] = 0 ;

#DATA
data ;
s e t STUDENTS := John Paul George Ringo Yoko ;
s e t COURSES := AST305 BIO201 COS127 ECO101 ECO221
ECO307 HIS203 HIS411 PHY211 PSY327 REL242 SLA101 ;
param : GRADES: g r a d e :=
[ ∗ , AST305 ] John 3 . 7 Paul 3 . 7 George 3 . 3 Ringo 2 . 7 Yoko 4
[ ∗ , BIO201 ] Paul 3 . 7 George 3 . 3 Yoko 4
[ ∗ , COS127 ] George 2 . 7 Ringo 1 . 7 Yoko 3 . 7
[ ∗ , ECO101 ] John 4 . 0 Paul 3 . 7 George 3 . 3 Ringo 3
[ ∗ , ECO221 ] Paul 3 . 7 Ringo 2 . 7 Yoko 3 . 7
[ ∗ , ECO307 ] John 3 . 7 Paul 3 . 3 George 3 . 7
[ ∗ , HIS203 ] John 3 George 3 Ringo 3 . 3 Yoko 3
[ ∗ , HIS411 ] John 4 Paul 3 . 7 Ringo 3 Yoko 4
[ ∗ , PHY211 ] Paul 3 . 7 George 3 Ringo 2 . 3
[ ∗ , PSY327 ] John 4 Paul 3 . 7 Yoko 4
[ ∗ , REL242 ] John 4 George 3 . 3 Ringo 3 Yoko 4
[ ∗ , SLA101 ] John 2 ;

6
# BEATLES UNIVERSITY − PART C

#FRAMEWORK
s e t STUDENTS;
s e t COURSES;
s e t GRADES w i t h i n {STUDENTS, COURSES} ;
param g r a d e {GRADES} ;
var a p t i t u d e {STUDENTS} ;
var e a s i n e s s {COURSES} ;
var dev {GRADES} >= 0 ;

#MODEL
minimize sum dev : sum { ( s , c ) i n GRADES} ( s q r t ( 1 / 9 + dev [ s , c ] ˆ 2 ) − 1 / 3 ) ;
s u b j e c t t o d e v i a t i o n { ( s , c ) i n GRADES} : a p t i t u d e [ s ] + e a s i n e s s [ c ]
+ dev [ s , c ] = g r a d e [ s , c ] ;
s u b j e c t t o n o r m a l i z e d e a s i n e s s : sum { c i n COURSES} e a s i n e s s [ c ] = 0 ;

#DATA
data ;
s e t STUDENTS := John Paul George Ringo Yoko ;
s e t COURSES := AST305 BIO201 COS127 ECO101 ECO221
ECO307 HIS203 HIS411 PHY211 PSY327 REL242 SLA101 ;
param : GRADES: g r a d e :=
[ ∗ , AST305 ] John 3 . 7 Paul 3 . 7 George 3 . 3 Ringo 2 . 7 Yoko 4
[ ∗ , BIO201 ] Paul 3 . 7 George 3 . 3 Yoko 4
[ ∗ , COS127 ] George 2 . 7 Ringo 1 . 7 Yoko 3 . 7
[ ∗ , ECO101 ] John 4 . 0 Paul 3 . 7 George 3 . 3 Ringo 3
[ ∗ , ECO221 ] Paul 3 . 7 Ringo 2 . 7 Yoko 3 . 7
[ ∗ , ECO307 ] John 3 . 7 Paul 3 . 3 George 3 . 7
[ ∗ , HIS203 ] John 3 George 3 Ringo 3 . 3 Yoko 3
[ ∗ , HIS411 ] John 4 Paul 3 . 7 Ringo 3 Yoko 4
[ ∗ , PHY211 ] Paul 3 . 7 George 3 Ringo 2 . 3
[ ∗ , PSY327 ] John 4 Paul 3 . 7 Yoko 4
[ ∗ , REL242 ] John 4 George 3 . 3 Ringo 3 Yoko 4
[ ∗ , SLA101 ] John 2 ;