The routes are \(s,a,t\) with time \(3+4=7\) ; \(s,b,t\) with time \(1+5=6\) ; and \(s,a,b,t\) with time \(3+1+5=9\) . Dijkstra’s algorithm settles \(s\) , then \(b\) with label \(1\) , then \(a\) with label \(3\) , then \(t\) with label \(\min\{3+4,\ 1+5\}=6\) . The fastest route is \(s,b,t\) , taking \(6\) .

The labels \(d(s)=0\) , \(d(a)=3\) , \(d(b)=1\) , \(d(t)=6\) are a feasible potential: on \((s,a)\) , \(3\le 0+3\) ; on \((s,b)\) , \(1\le 0+1\) ; on \((a,b)\) , \(1\le 3+1\) ; on \((a,t)\) , \(6\le 3+4\) ; on \((b,t)\) , \(6\le 1+5\) . By Theorem 2.3 no walk from \(s\) to \(t\) is shorter than \(d(t)=6\) .

If the time on \((a,b)\) were \(-3\) , the route \(s,a,b,t\) would take \(3-3+5=5\) and become the fastest. Dijkstra’s algorithm is no longer justified, since it would settle \(b\) at label \(1\) before discovering the label \(0\) through \(a\) . The network has no cycle, so distances exist; the Bellman–Ford recursion gives \(d(a)=3\) , \(d(b)=0\) , \(d(t)=5\) , and the proof is again that these labels satisfy the inequality on every arc.

Send \(4\) units on \((s,a)\) and \(3\) on \((s,b)\) ; from \(a\) send \(3\) on \((a,t)\) and \(1\) on \((a,b)\) ; then \(b\) receives \(3+1=4\) and sends \(4\) on \((b,t)\) . Conservation holds at \(a\) and \(b\) , no capacity is exceeded, and the value is \(7\) .

The cut \(S=\{s\}\) has leaving arcs \((s,a)\) and \((s,b)\) of capacity \(4+3=7\) . By Lemma 3.3 no flow exceeds \(7\) , so the flow is maximum.

There is a second minimum cut: \(S=\{s,a,b\}\) has leaving arcs \((a,t)\) and \((b,t)\) , of capacity \(3+4=7\) . Because of this, enlarging a single arc cannot raise the maximum flow. Enlarging an arc out of \(s\) leaves the cut around \(t\) at \(7\) , enlarging an arc into \(t\) leaves the cut around \(s\) at \(7\) , and enlarging \((a,b)\) changes neither. At least one arc in each of the two cuts must be enlarged; for example raising \((s,b)\) to \(4\) and \((b,t)\) to \(5\) gives a maximum flow of \(8\) .

Apply the Hungarian method. Row minima \(2,3,4,3\) give \(p=(2,3,4,3)\) ; the column minima of what remains are \(2,0,0,1\) , so \(q=(2,0,0,1)\) . The reduced costs are

A maximum matching among the zeros has three pairs, for instance \((1,1)\) , \((2,2)\) , \((3,3)\) ; row \(4\) is free, since rows \(2\) and \(4\) both have their only zero in column \(2\) . From row \(4\) the search reaches column \(2\) and row \(2\) : \(S=\{2,4\}\) , \(T=\{2\}\) , \(\delta=1\) . After the update, \(S=\{1,2,4\}\) , \(T=\{1,2\}\) , and \(\delta=3\) . The prices become \(p=(5,7,4,7)\) , \(q=(-1,-4,0,1)\) , with reduced costs

which contain the perfect matching \((1,3)\) , \((2,2)\) , \((3,4)\) , \((4,1)\) .

The assignment is: tutor 1 with student 3, tutor 2 with student 2, tutor 3 with student 4, tutor 4 with student 1, with total \(5+3+5+6=19\) . The prices total \(5+7+4+7-1-4+0+1=19\) , so by Lemma 4.9 no assignment takes less. The optimum is not unique; tutor 1 with student 1, tutor 2 with student 2, tutor 3 with student 4, tutor 4 with student 3 also totals \(19\) .

The relaxation’s optimum is where both constraints are active: \(x=(1.7,2.2)\) with value \(13.9\) , so \(z^\star\le 13\) .

List the feasible integer points by \(x_1\) . For \(x_1=0\) : \(x_2\le 3\) . For \(x_1=1\) : \(3x_2\le 8\) , so \(x_2\le 2\) . For \(x_1=2\) : \(x_2\le 9-8=1\) . For \(x_1=3\) the second constraint fails. The best point in each column is \((0,3)\) with value \(12\) , \((1,2)\) with value \(11\) , and \((2,1)\) with value \(10\) . So \(x^\star=(0,3)\) and \(z^\star=12\) .

For someone who has not seen the search, two short arguments are available. One is the list just given, which is a three-leaf enumeration: every feasible point has \(x_1\in\{0,1,2\}\) and the best in each case is shown. The other is a valid inequality: every feasible integer point satisfies \(x_1+x_2\le 3\) (see the next problem), and then \(3x_1+4x_2=3(x_1+x_2)+x_2\le 9+x_2\) , with \(x_2\le 3\) from the first constraint; so the value is at most \(12\) , attained at \((0,3)\) . Either argument, together with the feasible point, is a certificate.

Use Proposition 8.2 with multipliers \(\mu=(\tfrac3{10},\tfrac1{10})\) . The combination is

that is, \(x_1+x_2\le 3.9\) . The coefficients are integers, and rounding the right side down gives \(x_1+x_2\le 3\) , valid for all feasible integer points.

At the relaxation optimum \((1.7,2.2)\) the left side is \(3.9>3\) , so the inequality is violated there.

With the cut added, maximize \(3x_1+4x_2\) subject to \(2x_1+3x_2\le 10\) , \(4x_1+x_2\le 9\) , \(x_1+x_2\le 3\) , \(x\ge 0\) . On the line \(x_1+x_2=3\) the objective is \(9+x_2\) , so \(x_2\) should be as large as possible; the first constraint gives \(2(3-x_2)+3x_2\le 10\) , so \(x_2\le 4\) , and nonnegativity of \(x_1\) gives \(x_2\le 3\) . The optimum of the new relaxation is \((0,3)\) with value \(12\) , an integer point. One cut made the relaxation’s optimum integral and solved the problem.

In the first matrix every column has exactly two ones: column 1 in rows \(1,4\) ; column 2 in rows \(1,2\) ; column 3 in rows \(2,3\) ; column 4 in rows \(3,4\) . Split the rows into \(R_1=\{1,3\}\) and \(R_2=\{2,4\}\) . In every column the two ones lie in different classes, so Theorem 6.9 applies and the matrix is totally unimodular. It is the node–edge incidence matrix of a four-cycle, which is bipartite. By Theorem 6.7, programs with this matrix and integer right-hand sides have integral vertices.

After the change the rows are \((1,1,0,0)\) , \((0,1,1,0)\) , \((0,0,1,1)\) , \((1,0,1,0)\) . Rows \(1,2,4\) and columns \(1,2,3\) form the triangle matrix

with determinant \(2\) . The matrix is not totally unimodular, and integral vertices are not guaranteed: with right-hand side \((1,1,1,1)\) and constraints \(Ax\le b\) , \(x\ge 0\) , the point \((\tfrac12,\tfrac12,\tfrac12,\tfrac12)\) is feasible with all four rows active and is a vertex, since the four rows are linearly independent.

Use the table of Theorem 9.1, which takes \(O(nW)\) operations, here \(4\cdot 8\) entries. With profits \((9,7,6,4)\) and weights \((5,4,3,2)\) :

The optimal value is \(F_4(7)=13\) . Backtracking: \(F_4(7)=F_3(7)\) , so item 4 is out; \(F_3(7)=13\ne F_2(7)=9\) , so item 3 is in, leaving capacity \(4\) ; \(F_2(4)=7\ne F_1(4)=0\) , so item 2 is in. The selection is items \(2,3\) , with weight \(7\) and profit \(13\) . Items \(1,4\) give \(13\) as well.

For the relaxation, the ratios are \(1.8\) , \(1.75\) , \(2\) , \(2\) ; taking items \(3\) and \(4\) , with weight \(5\) , and then \(\tfrac25\) of item 1 gives \(10+3.6=13.6\) . Rounded down, the bound is \(13\) , which the table’s answer attains.

Let \(x_i\in\{0,1\}\) say whether machine \(i\) is rented and \(y_i\ge 0\) be its output. Minimize \(10x_1+12x_2+15x_3+2y_1+y_2+y_3\) subject to \(y_1+y_2+y_3=20\) and \(y_1\le 12x_1\) , \(y_2\le 14x_2\) , \(y_3\le 20x_3\) . The constants are the capacities; for machine 3 the capacity \(20\) is also the total demand, so no smaller constant is valid for any of them.

Enumerate the rental decisions. Machine 3 alone: \(15+20=35\) . Machines 1 and 2: capacity \(26\) , fixed cost \(22\) , with \(14\) units on machine 2 at cost \(14\) and \(6\) on machine 1 at cost \(12\) : \(48\) . Machines 1 and 3: \(25+20=45\) . Machines 2 and 3: \(27+20=47\) . All three cost more still, and machine 1 alone or machine 2 alone cannot produce \(20\) units. The optimal plan is to rent machine 3 only and make all \(20\) units on it, at cost \(35\) .

The cables form two triangles, on \(\{1,2,3\}\) and on \(\{3,4,5\}\) , sharing computer \(3\) . The set \(\{2,3,4\}\) meets every cable: \(12\) and \(23\) at \(2\) , \(13\) , \(34\) , \(35\) at \(3\) , and \(45\) at \(4\) .

No set of two computers suffices. If computer \(3\) is chosen, the cables \(12\) and \(45\) remain and have no common endpoint, so two more computers are needed. If \(3\) is not chosen, the cables \(13\) and \(23\) force \(1\) and \(2\) , and the cables \(34\) and \(35\) force \(4\) and \(5\) . So three is the minimum.

König’s theorem could not have been used: the graph contains triangles and is not bipartite, and indeed its largest matching has only two cables, for example \(12\) and \(34\) , since any three disjoint cables would need six computers. The matching bound \(2\) is strictly below the minimum cover \(3\) .

Let \(t_1,t_2\ge 0\) be the start times, so the jobs occupy the machine from \(t_1\) to \(t_1+3\) and from \(t_2\) to \(t_2+5\) . Both must finish by time \(12\) , so \(t_1\le 9\) and \(t_2\le 7\) . With \(x\in\{0,1\}\) , where \(x=0\) means job 1 goes first:

For \(x=0\) the first constraint is the real requirement and the second reads \(t_2+5\le t_1+12\) , which always holds because \(t_2+5\le 12\) and \(t_1\ge 0\) . For \(x=1\) the roles are exchanged. The constant must be at least the largest value of \(t_1+3-t_2\) , which is \(9+3-0=12\) , and at least the largest value of \(t_2+5-t_1\) , which is \(7+5-0=12\) . So \(12\) , the horizon, is the smallest valid constant in both constraints.

With the constant \(1000\) the integer solutions are the same, but the relaxation is far weaker. The first constraint holds for every pair of start times as soon as \(1000x\ge 12\) , and the second as soon as \(1000(1-x)\ge 12\) ; so every \(x\) between \(0.012\) and \(0.988\) switches both constraints off, and the relaxation sees no conflict between the jobs at all. With the constant \(12\) only \(x=1\) switches the first constraint off completely and only \(x=0\) the second, so a fractional \(x\) always leaves part of the requirement in force.

Stations in towns \(2\) and \(5\) reach \(\{1,2,3\}\) and \(\{4,5,6\}\) , all six towns. One station is not enough, since no \(S_i\) contains more than three towns. So two stations is the minimum.

The model minimizes \(x_1+\dots+x_6\) subject to, for each town \(j\) , \(\sum_{i:\,j\in S_i}x_i\ge 1\) . In the constraint matrix, with a row for each town and a column for each station, column \(i\) has ones exactly in the rows of \(S_i\) , and each \(S_i\) is a run of consecutive towns. By Theorem 6.11 the matrix is totally unimodular, and with the integer right-hand side Theorem 6.7 makes every vertex of the relaxation integral. The property is total unimodularity, here in the form of consecutive ones.

A dual certificate confirms the value: towns \(1\) and \(6\) have no station in common, since no \(S_i\) contains both, so assigning price \(1\) to each of them and \(0\) to the others is feasible for the dual, with value \(2\) .