CSC 445/545 - SUMMER 2021
OPERATIONS RESEARCH: LINEAR PROGRAMMING
ASSIGNMENT 4
UNIVERSITY OF VICTORIA
Due: Friday, July 23rd, 2021 at 11:59pm Victoria time (PDT). Late assignments will not be
accepted.
Submit one PDF file containing your solution to each question (in order). Please clearly
label each question. You are encouraged to discuss conceptual aspects of the questions
with your peers, but your submissions must be entirely your own work. Do not share
(send or receive) your answers with anyone.
Question 1 [4 marks]. Consider the LP below, which has two optimization variables x1 and x2
and four constraints (besides the non-negativity constraints).
max. −x1 − x2
s.t. x1 − x2 ≤ 9 −4x1 + 2x2 ≤ 4 x1 ≤ 5 x2 ≤ 10
x1, x2 ≥ 0
When this LP is put into equational form, there will be four slack variables x3, x4, x5, x6 and any
basis will have size 4. Compute the following parameters of the linear algebraic Simplex Method
using the LP above and the basis x1, x3, x4, x6.
(a) The matrix AB.
(b) The vector xB = (x1, x3, x4, x6).
(c) The vector cB = (c1, c3, c4, c6).
(d) The vector zN = (z2, z5).
1
Question 2 [8 marks]. In the normal minimum cost network flow problem, we require “global
balance” of supply and demand: the sum of all vertex supply values must equal zero (and we do
not consider an input valid otherwise).
Suppose that we generalize the problem to allow the global sum of supply to equal any value (so
there is no requirement for global equilibrium), and, we specify that
❼ If the graph is balanced or has a global surplus (that is, the total supply is greater than or
equal to the total demand), an optimal flow is any flow that satisfies the demand at each
vertex (and any extra supply is simply discarded).
❼ If the graph has a global shortage (that is, the total demand exceeds the total supply), there
is no solution (the problem is considered infeasible).
(a) Describe a process for converting an instance G of the generalized problem (where global
supply and demand may not be equal) to an instance G0 of the minimum cost network
flow problem (such that the resulting optimal flow meets the criteria above). The converted
instance G0 must have a global balanace of supply and demand, and:
❼ If G has a global shortage, G0 must be infeasible for the minimum cost flow problem.
❼ Otherwise, computing an optimal flow for G0 will produce an optimal flow for G.
You may want to add extra vertices or edges to produce G0 from G, but you should describe
how to recover the optimal flow for G from the optimal flow for G0 .
(b) Using your conversion from part (a), construct the graph G0 corresponding to the instance G
of the generalized problem below.
a7 b4 c0d
-1
e
-2
f
-3
1 7 3 5 4 2 1
Question 3 [4 marks]. Construct a minimum cost network flow instance (that is, a network with
a supply value for each vertex and a cost for each arc) where no possible basis is either primal or
dual feasible. Recall that, to be a valid input, the global sum of supply values must be zero.
2
Question 4 [12 marks]. Consider the input network shown on the right below. Starting from the
basis shown on the right (with vertex a as the root of the spanning tree), use a two phase method
(dual first, primal second) to compute an optimal flow for this network.
In the dual phase, when choosing a leaving arc at each step, always choose the arc with the smallest
negative primal flow value. In the primal phase, when choosing the entering arc at each step, choose
the arc with the smallest negative dual slack value.
Clearly indicate the beginning of each phase, and, at each step:
❼ Draw the graph with the basis, flow values, dual optimization variables and dual slack values
(in a similar manner as the examples in the lecture slides).
❼ Clearly indicate when the optimal solution is reached in each phase. When a pivot is necessary,
clearly write the entering and leaving arcs (please write these explicitly in text instead of
annotating the graph).
Supply/Cost Flow
a5 b
-5
c0d5 e
-5
f
-2
g 4 h -2
1 7 3 4 5 23 10
11 1 3 a b cd e f gh 3