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 −4×1 +2×2 ≤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 G′ of the minimum cost network flow problem (such that the resulting optimal flow meets the criteria above). The converted instance G′ must have a global balanace of supply and demand, and:
If G has a global shortage, G′ must be infeasible for the minimum cost flow problem.
Otherwise, computing an optimal flow for G′ will produce an optimal flow for G.
You may want to add extra vertices or edges to produce G′ from G, but you should describe how to recover the optimal flow for G from the optimal flow for G′.
(b) Using your conversion from part (a), construct the graph G′ corresponding to the instance G of the generalized problem below.
-3 -2 -1
f1e4d
725
a1b3c 740
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
-2 -5 5
f1e2d 10 3
h -2 735
g
141
a1b3c 5 -5 0
4
Flow
fed
h
g
abc
3