Description
P1. (10 points) Consider the following feasible dictionary:
w1 8 −5×1 −4×2 +x5 −2×6 +2w3 −w4
w2 2 −x1 −x5 −x6 −w3
x3 2 +x2 −x5 −x6 −w3 −2w4
x4 3 −x1 −x2 −x5 −x6 +2w3 +w4
w5 4 −x1 −2×2 −4×5 +w4
z 11 −x1 +2×2 +x5 +x6 +3w3 −2w4
(A) Write down all possible entering variables. For each entering variable, write down all possible
leaving variables corresponding to that entering variable. Express your answer as a table such as
the one sample shown below.
Entering Leaving
x2 w1 or w5
.
.
.
.
.
.
(B) Suppose x2 were chosen to be the entering variable and w5 as the leaving variable. Write down
the basic variables, non basic variables and their corresponding solutions in the next dictionary
after pivoting. (It is preferable if you answer this problem withing attempting to actually work out
the next dictionary.) Will this dictionary be a degenerate dictionary?
(C) Write down the choice of the entering variable for which the value of the objective function
in the next dictionary will be the highest? Will the value of the objective function depend on the
choice of the leaving variable as well (yes or no) ?
P2. (15 points) Consider the following feasible dictionary:
xB,1 b1 +a11xN,1 + · · · +a1jxN,j · · · +a1nxN,n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xB,i bi +ai1xN,1 + · · · +aijxN,j · · · +ainxN,n
.
.
.
.
.
.
xB,m bm +am1xN,1 + · · · +amjxN,j · · · +amnxN,n
z c0 +c1xN,1 + · · · +cjxN,j · · · +cnxN,n
(A) Suppose xN,j is chosen to enter and xB,i is the corresponding leaving variable, then show that
the value of xB,k in the next dictionary after pivoting is given by
bk + akj
bi
−aij
.
1
Also write down for each of the constants bk, akj , bi
, aij whether it is known that constant will
be > 0, < 0, ≥ 0, ≤ 0 or nothing may be said about its sign.
(B) Show that if the leaving variable analysis is correct then the value of each basic variable xB,k
in the subsequent dictionary is ≥ 0. In other words:
bk + akj
bi
−aij
≥ 0 .
In other words, we conclude that starting from a feasible dictionary and pivoting yields another
feasible dictionary.
(Hint: Split two cases on the sign of akj . For one case it will be trivially true. For the other,
you have to appeal to the leaving variable analysis as to why xB,i was the leaving variable and not
xB,k).
(C) Using the analysis above, prove that if xB,k and xB,i are both possible leaving variables (i 6= k)
for xN,j entering, then the subsequent dictionary will be degenerate. (Hint: Assume that xB,i is
chosen to leave. Show that even though xB,k did not leave the basis, its value in the next dictionary
will be 0).
P3 (10 points) Provide examples of dictionaries that satisfy the properties stated below. Try to
construct examples that are as small as possible. If no such dictionaries can exist, briefly reason
why.
(A) A degenerate dictionary that is also unbounded. Recall that an unbounded dictionary does
not have a leaving variable for some choice of an entering variable.
(B) A degenerate dictionary D which upon pivoting yields another degenerate dictionary D0
, but
the objective value strictly increases.
(C) A non-degenerate dictionary D which upon pivoting yields another dictionary D0 but the value
of the objective function stays the same.
(D) A dictionary that is feasible but upon pivoting yields an infeasible dictionary.
(E) A dictionary that does not have leaving variable (is unbounded) for one choice of entering
variable but has a leaving variable for a different choice of an entering variable.
P4 (15 points) Consider the polyhedron below:
−x +2y +2z ≤ 2
2x −y +2z ≤ 2
x ≥ 0
y ≥ 0
z ≥ 0
(A) Compute all the vertices and for each vertex write down if it is degenerate or non-degenerate.
(B) Consider the optimization problem:
max 2x +3y −2z
s.t −x +2y +2z ≤ 2 #Slack w1
2x −y +2z ≤ 2 #Slack w2
x ≥ 0
y ≥ 0
z ≥ 0
2
Write down all the dictionaries corresponding to the degenerate vertices. Use slack variables
w1, w2 as indicated.
(C) Draw a graph whose nodes are the vertices described in (A) with edges between adjacent
vertices.
(D, extra credit) Given a polyhedron P, and for each vertex of the polyhedron, can you write
down an objective function that is uniquely maximized only at that vertex and no other vertex of
P?
(E, extra credit) For any polyhedron P, the polyhedral graph (also called its skeleton) is one
where the nodes form the vertices of the polyhedron, and the edges connect adjacent vertices. Prove
that this graph is strongly connected for any P. I.e, given any two vertices v1 and v2 there is a
path between them in this graph.
(F, extra credit) Prove that the graph in part (E) for a d-dimensional polyhedron P has the
property that if any subset of d − 1 or fewer vertices in the graph are removed, it will still remain
strongly connected (This is called Balinski’s theorem).
To illustrate this, draw the skeleton of a cube and remove any two vertices from this skeleton.
You will notice that there is a path in this graph between any pair of remaining vertices.
3