CSE524 Homework 4- Duality Solution

(Submit a single pdf image of your Jupyter notebook via Canvas.)
(Please denote the start of each question in your Julia workbook using a LARGEFONT.)
1. Max-Flow / Min-Cost. Here’s a story from Harry Potter. Ollivander, the famous wand maker of Diagon Alley, has a logistics problem. He produces wands of seven different types for which he must arrange delivery to a favored customer, using five owls. There’s a limit to the total number of wands that each owl can carry, shown in the following table.
Owl 1 2 3 4 5
Max Wands That Can Be Carried 6 5 4 2 10
Each owl can carry at most one wand of each type. Ollivander wants to deliver as many total wands to his customer as possible.
(a) Formulate and solve in Julia a max-flow problem to determine the maximum number of wands that can be delivered.
NB: There are various ways to formulate this problem, but you need to formulate it as a max-flow problem.
Have your code output clearly the optimal objective value (the maximum total number of wands delivered), together with the number of wands to be carried by each of the five owls, and the number of each type of wand that can be shipped.
Hint: Your network should have the following nodes: one source node (Ollivander’s store), a layer of 7 nodes in which each node represents one of the types of wands, a layer of 5 nodes in which each node represents an owl, and a destination node (the customer). (14 nodes in total!) You need to define the edges (arcs) and the capacities on each each edge to fill out the definition of the max-flow problem.
(b) As you know, the dual of max-flow is min-cut. Min-cut can be viewed as partitioning the network into two subsets of nodes, one subset containing the source and the other containing the destination, by removing a subset of edges in such a way that the sum of the maximum capacities on the edges removed is minimized. For Ollivander’s problem above, at the solution of the min-cut version, what is the subset of nodes containing the destination (customer) node? Explain.
2. Stigler’s supplement. Consider Stigler’s diet problem from Homework 2. To help further lower the cost of your diet, a friend offers to sell you calcium supplements. Each calcium pill contains 500 mg (that’s half a gram) of calcium.
(a) What is the most you would be willing to pay per pill? Hint: use duality!
(b) Suppose you can buy calcium pills at a cost $0.01 each. Add this new “food” to your basic diet problem formulation and re-solve to obtain a new optimal diet. How much money does it save compared to the original optimal diet that didn’t have access to the calcium supplement?
3. Dual interpretation. Suppose t ∈ [0,2π] is a parameter. Consider the following LP:
min
p,q,r,s p + q + r + s
subject to: p − r = cos(t)
q − s = sin(t) p,q,r,s ≥ 0
1 of 2
(b) Write out the dual LP. Interpret and solve the dual LP graphically. Does your solution agree with the solution found in part a)?
2 of 2