Solve each of the following transportation problems
(a)
\(7\)
\(4\)
\(7\)
\(5\)
\(4\)
\(2\)
\(6\)
\(20\)
\(5\)
\(4\)
\(6\)
\(10\)
\(15\)
\(10\)
\(10\)
(b)
\(4\)
\(3\)
\(7\)
\(10\)
\(2\)
\(1\)
\(4\)
\(20\)
\(3\)
\(2\)
\(4\)
\(10\)
\(15\)
\(20\)
\(5\)
(c)
\(2\)
\(4\)
\(1\)
\(25\)
\(4\)
\(5\)
\(4\)
\(5\)
\(5\)
\(10\)
\(15\)
(d)
\(5\)
\(9\)
\(5\)
\(6\)
\(7\)
\(10\)
\(7\)
\(8\)
\(25\)
\(30\)
\(10\)
(e)
\(4\)
\(7\)
\(3\)
\(5\)
\(8\)
\(2\)
\(9\)
\(10\)
\(6\)
\(10\)
\(8\)
\(7\)
\(6\)
\(12\)
(f)
\(1\)
\(7\)
\(10\)
\(10\)
\(5\)
\(4\)
\(1\)
\(2\)
\(3\)
\(16\)
\(2\)
\(3\)
\(4\)
\(6\)
\(3\)
\(5\)
\(9\)
\(4\)
\(6\)
(g)
\(3\)
\(5\)
\(7\)
\(14\)
\(5\)
\(4\)
\(7\)
\(7\)
\(6\)
\(7\)
\(11\)
\(5\)
\(8\)
\(9\)
\(12\)
\(4\)
\(5\)
\(7\)
\(18\)
(h)
\(5\)
\(7\)
\(9\)
\(7\)
\(8\)
\(6\)
\(8\)
\(5\)
\(4\)
\(15\)
\(4\)
\(5\)
\(6\)
\(7\)
\(8\)
\(6\)
\(6\)
\(8\)
\(5\)
\(11\)
\(10\)
\(11\)
\(8\)
\(13\)
(i)
\(4\)
\(4\)
\(6\)
\(4\)
\(5\)
\(4\)
\(5\)
\(6\)
\(4\)
\(14\)
\(6\)
\(7\)
\(7\)
\(6\)
\(4\)
\(7\)
\(8\)
\(8\)
\(7\)
\(6\)
\(8\)
\(6\)
\(10\)
\(5\)
2.
In Exercise 6.4.1, looking at the final talbeau of the Transportation Algorithm, determine which of these have a unique optimal solution.
3.
In Exercise 6.4.1, for each problem without a unique optimal solution, find an alternative solution and show that it is feasible and gives the same objective value.
4.
True or False for a valid choice of \(a_i, b_j\) in Definition 6.2.3 step 2, then for a fixed real number \(Z\text{,}\)\(a_i-Z, b_j+Z\) is also a valid choice.
5.
Suppose \(Z\) were an absurdly large number. Solve the transportation problem:
\(3\)
\(4\)
\(Z\)
\(8\)
\(4\)
\(7\)
\(4\)
\(6\)
\(Z\)
\(4\)
\(4\)
\(7\)
\(5\)
\(4\)
\(3\)
\(10\)
\(10\)
\(9\)
\(12\)
6.
Solve the following transportation problems:
(a)
\(4\)
\(6\)
\(5\)
\(6\)
\(8\)
\(6\)
\(6\)
\(4\)
\(7\)
\(19\)
\(6\)
\(5\)
\(4\)
\(5\)
\(14\)
\(4\)
\(6\)
\(3\)
\(7\)
\(14\)
\(15\)
\(20\)
\(20\)
\(10\)
(b)
\(3\)
\(5\)
\(6\)
\(5\)
\(15\)
\(3\)
\(4\)
\(3\)
\(5\)
\(5\)
\(3\)
\(3\)
\(3\)
\(5\)
\(15\)
\(3\)
\(6\)
\(5\)
\(5\)
\(10\)
\(10\)
\(7\)
\(9\)
\(12\)
7.
On the planet Zeltros, a luxury resort is preparing for a multi-day celebration they are hosting. One of the requested activities by the guests is hoverbike riding. Over the three day event, they will require \(500\) hoverbikes on the first day, \(300\) hoverbikes on the second and \(800\) hoverbikes on the final day.
Brand new hoverbikes are \(1000\) credits. After use they undergo a maintanence procedure which costs \(250\) credits and takes two days, before they may be used again. A rush job that takes one day is possible but costs \(400\) credits.
The resort naturally wishes to minimize their costs. They wish to know how many bikes to purchase and what maintanence schedule would achieve this.
Model this as a transportation problem where the “warehouses” are the number of brand new hoverbikes purchased before day 1, used hoverbikes from day 1 and used hoverbikes from day 2. Can we make educated guesses on what these capacities should be? What should the “markets” represent and what are their demands? Then solve the problem.
Some of the problems in Exercise 6.4.9 have multiple solutions. Identify them and identify all the optimal solutions.
11.
Consider a general balanced transportation problem. Let \(w_1, \ldots, w_n\) denote the supply of the \(n\) warehouses, and \(m_1, \ldots, m_m\) denote the demand of the \(m\) markets. Then let \(c_{ij}\) denote the cost to ship from warehouse \(i\) to market \(j\text{.}\)
(a)
Write out a non-canonical minimization problem which models this problem (there should be some equality constraints).
(b)
State the dual problem to the transportation problem.
(c)
Prove that in Definition 6.2.3, for a valid choice of \(a_i, b_j\) in step 2 that
How does this relate to the dual problem to the transportation problem?
(d)
Consider the non-negativity condition in step 4 of Definition 6.2.3. How does this relate to the constraints of the dual problem to the transportation problem?
12.
Consider an \(n\times n\) assignment problem treated as a transportation problem. Apply VAM Definition 6.1.4 to this initial tableau. Show that the resulting basis generated has \(n-1\) selected entries where the shipment along those entries (\(x_{ij}\)) is zero.
13.
Prove that the Transportation Algorithm Definition 6.2.3 will lead to an optimal solution after a finite number of steps if the algorithm is applied to a problem with all data rational.
14.
Consider the following network:
where the labels on each edge denote the “distance” from \(v_i\) to \(v_j\text{.}\)
(More about directed weighted networks may be found in Definition 7.3.2)
(a)
Consider an “assignment” problem with “sources” and “sinks” \(v_0,\ldots, v_5\) such that the “cost” of from shipping from \(v_i\) to \(v_j\) is the label on the \(v_iv_j\) edge. Let the cost from shipping from \(v_5\) to \(v_1\) be 0. For each \(i, 1\leq i\leq 4\text{,}\) let the cost of shipping from \(v_i\) to itself be 0. Let every other cost be an absurdly high \(Z\text{.}\)
Solve this assignment problem.
(b)
For your optimal solution, if \(v_i\) “ships” to \(v_j\text{,}\) highlight the corresponding edge on network above. If a vertex \(v_k\) ships to itself, highlight that vertex. Disregard the case when \(v_5\) ships to \(v_1\text{.}\) What can you say about the highlighted edges? What may be reasonable conjectures about these edges?
15.
Consider a general directed weighted network with vertices \(v_0, \ldots, v_n\) with a unique source \(v_0\) and sink \(v_n\text{,}\) and all weights on edges are positive such as Exercise 6.4.14 (see Definition 7.3.2 for more information).
We will be considering assignment problems where “warehouses” and “markets” are the vertices \(v_0, \ldots, v_n\text{.}\) Throughout this problem, let \(Z\) be an absurdly large number.
(a)
Consider an assignment problem where the cost of shipping from \(v_i\) to \(v_j\) is the weight on that edge if it exists and \(Z\) otherwise. Show that any solution to the assignment problem (not neccesarily optimal) is bijective with the set of possible unions of disjoint cycles on the network.
(b)
Suppose we adjust the previous assignment problem where the cost of shipping from \(v_n\) to \(v_0\) is 0. Show that solutions to this assignment problem are bijective with the union of disjoint cycles and path from \(v_0\) to \(v_n\) on this network.
(c)
Suppose we then further adjust this assignment problem by setting the cost to ship from \(v_i\) to itself for any \(1\leq i\leq n-1\) to be 0. Show that an optimal solution to this problem must be a shortest path from \(v_0\) to \(v_n\text{.}\)
