Solution. With \(x_1\) entering, the ratios are \(26/2 = 13\) and \(56/2 = 28\) (the third row has a negative entry), so \(s_1\) leaves: \(A(13, 0)\), \(Z = 130\). In the new tableau the objective row has \(-10\) under \(x_2\), which enters; the ratios are \(13/\frac 12 = 26\) for the \(x_1\) row, \(30/3 = 10\) for the \(s_2\) row (now \(3x_2 - s_1 + s_2 = 30\)) and \(18/\frac 32 = 12\) for the \(s_3\) row, so \(s_2\) leaves, giving \(x_2 = 10\), \(x_1 = 13 - 5 = 8\): the point \(B\), \(Z = 230\), in two pivots.

Solution. Initial basis \(\{s_1, s_2\}\). \(x_1\) enters (coefficient \(-3\)); ratios \(4\) and \(2\), so \(s_2\) leaves: \(x_1 = 2\), \(Z = 6\). Now the \(x_1\) row is \(x_1 - x_2 + s_2 = 2\) and the \(s_1\) row \(2x_2 - s_2 + s_1 = 2\); the objective row has \(-5\) under \(x_2\). \(x_2\) enters, only the \(s_1\) row has a positive entry, so \(x_2 = 1\), \(x_1 = 3\), \(Z = 11\). The objective row is then \(\frac 52\) under \(s_1\) and \(\frac 12\) under \(s_2\), non-negative, so \((3, 1)\) is optimal with \(Z = 11\).

Solution. From the origin, \(x_1\) enters and \(s_1\) leaves: \(x_1 = 1\), with rows \(x_1 - x_2 + s_1 = 1\) and \(s_1 + s_2 = 2\) (adding the rows). The objective row has \(-2\) under \(x_2\), but the column of \(x_2\) is \((-1, 0)\), with no positive entry: by Theorem 3.1.2(i) the problem is unbounded. The direction is \(d = (1, 1)\) in \((x_1, x_2)\): along \((1, 0) + \theta (1, 1)\) both constraints stay satisfied and \(Z = 1 + 2\theta \).

Solution. Standard form: \(x_1 + 2x_2 - s = 4\), \(3x_1 + x_2 = 3\). Phase I: minimise \(a_1 + a_2\) subject to \(x_1 + 2x_2 - s + a_1 = 4\), \(3x_1 + x_2 + a_2 = 3\). Solving, the point \(x_1 = \frac 25\), \(x_2 = \frac 95\) satisfies both equations with \(s = 0\) (\(\frac 25 + \frac {18}5 = 4\), \(\frac 65 + \frac 95 = 3\)), so the basis \(\{x_1, x_2\}\) is feasible and Phase I ends with value \(0\) there. For Phase II, the reduced cost of \(s\) is \(\bar c_s = 0 - c_B^{\mathsf T}B^{-1}(-1, 0)^{\mathsf T} = \frac 25 \geq 0\), so this BFS is already optimal, with cost \(\frac {11}5\).

Solution. The column of slack \(s_i\) in \(A\) is the unit vector \(e_i\) and its cost is \(0\), so its reduced cost (for the minimisation of \(-Z\)) is \(0 - (-c_B)^{\mathsf T}B^{-1}e_i = (c_B^{\mathsf T}B^{-1})_i\): the objective row under the slacks is the row vector \(y^{\mathsf T} = c_B^{\mathsf T}B^{-1}\). In Example 3.2.1, \(c_B = (0, 10, 15)\) for \((s_3, x_1, x_2)\) and the rows of \(B^{-1}\) for \(x_1\) and \(x_2\) give \(y_1 = 10\cdot \frac 23 + 15\cdot (-\frac 13) = \frac 53\) and \(y_2 = 10\cdot (-\frac 16) + 15\cdot \frac 13 = \frac {10}3\), as in the final tableau.

Solution. At most \(\binom {60}{20} = 4.19 \times 10^{15}\). The simplex method typically needs between \(m\) and \(3m\) pivots, that is \(20\) to \(60\); each pivot costs \(O(mn)\) operations, so the whole solve takes well under a million operations, against more than \(10^{15}\) linear systems for enumeration.