Full Name:
Student Number:
TOTAL POINTS: /30
Trent University MATH XXXXXXXXXXLinear Programming
Instructor: Aras Erzurumluoğlu
Final Exam (due 23:59 pm on April 18, 2022 Monday)
Show all your work. You may use your notes, but you are not allowed
to copy solutions from one another or from elsewhere (not even partially).
Please familiarize yourself with Trent University’s policies on academic in-
tegrity.
Make sure that your solutions are well-written and follow the terminol-
ogy and notation as we have seen in class.
Problem 1) (5 points) Solve the transportation problem where
C (cost matrix) =
XXXXXXXXXX
8 5 8 7
, s =
7550
60
, and d =
45
50
25
50
.
Problem 2) (4 points) Consider a hallway at Trent with 15 offices num-
ered 101 through 115. The distance from office i to office j (101 ≤ i, j ≤
115) is |j − i|. One desk from each one of the offices 102, 105, 108, 109, and
113 need to be moved to one of the offices 106, 107, 112, 114, and 115. Each
one of the offices 106, 107, 112, 114, and 115 need exactly one desk, and it
does not matter which desk goes to which office.
Use a method from class to find an assignment of the desks that mini-
mizes the total distance over which the desks would need to be moved.
1
Problem 3) (4 points) For the LP problem given below, first find the
extreme points of the set of feasible solutions and then find an optimal so-
lution if it exists.
Maximize z = 3x− y subject to
4x− y ≤ 8
2x + y ≥ 4
x + 2y ≤ 6
x ≥ 0, y ≥ 0.
Problem 4) (3 points) You have 6 favourite songs, and there are a total of
10 CD’s at a store that contain some of these songs. Each one of these 6 songs
is in at least one of the 10 CD’s. Suppose that the ith CD costs ci dollars.
Let aij = 1 if the ith CD contains the jth song (i = 1, . . . , 10; j = 1, 2, . . . , 6);
aij = 0 otherwise.
Write an integer programming model that you could use to determine
the cheapest selection of CD’s to while guaranteeing that you will get each
one of your favourite songs in at least one CD.
Problem 5) (2 points) In the transportation problem (as defined at the
ottom of p. 184 in the lecture notes where total supply equals total de-
mand), show that taking xij =
sidj∑m
i=1 si
satisfies all constraints of the form∑n
j=1 xij = si (for i = 1, . . . ,m).
Problem 6) (2 points) Use one iteration of the simplex method to obtain
the next tableau from the given tableau below.
x1 x2 x3 x4
x XXXXXXXXXX
x XXXXXXXXXX
XXXXXXXXXX
2
Problem 7) (4 points) Apply the two-phase method to the following prob-
lem. to find an optimal solution if it exists. (If no optimal solution exists,
express why.)
Maximize z = 2x1 + 5x2 − x3 subject to
−4x1 + 2x2 + 6x3 = 4
6x1 + 9x2 + 12x3 = 3
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Problem 8) (4 points) Suppose that x1 = 2, x2 = 0, x3 = 4 is an optimal
solution to the LP problem given as follows:
Maximize z = 4x1 + 2x2 + 3x3 subject to
2x1 + 3x2 + x3 ≤ 12
x1 + 4x2 + 2x3 ≤ 10
3x1 + x2 + x3 ≤ 10
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.
Find an optimal solution to the dual problem and determine the value
of the dual objective function at this optimal value. (Hint: Using some
appropriate techniques and theorems will reduce the required work very
significantly.)
Problem 9) (2 points) Suppose that the following tableau was obtained
during an application of the simplex method to an LP problem in standard
form. What can we conclude about the optimal solution of the LP problem?
x1 x2 x3 x4
x XXXXXXXXXX
x XXXXXXXXXX
XXXXXXXXXX
3