# Solution to the practice problems

Solution 1a. Say the Barracks are Barrack 1 and Barrack 2 and the latter is boosted. Let $x_1, x_2$ be the number of Archers trained from Barrack 1 and Barrack 2 respectively. Define $x_3, x_4$ for Giants and $x_5, x_6$ for Wizards similarly. We can formulate the linear program as follows.

Maximize $$\begin{gathered}(100\times 22 - 400)(x_1+x_2) \\ +(100\times 43 - 940)(x_3+x_4) \\ +(100\times 170 - 3500)(x_5+x_6)\end{gathered}$$ $44(x_1+x_2)+940(x_3+x_4)+156(x_5+x_6)\ge 18800$ Hit points constraint $(x_1+x_2)+5(x_3+x_4)+4(x_5+x_6)\le 220$ Housing space constraint $0.4x_1+2x_3+8x_5 \le 45$ Training time constraint for Barrack 1 $0.1x_2+0.5x_4+2x_6 \le 45$ Training time constraint for Barrack 2 $x_1, \dots, x_6 \ge 0$

Solution 1b. Insert a surplus variable $p_1$ and an artificial variable $a_1$ for the first constraint, and insert slack variables $s_2, s_3, s_4$ for the last three constraints respectively.

Maximize $1800x_1+1800x_2+3360x_3+3360x_4+13500x_5+13500x_6$ $44x_1+44x_2+940x_3+940x_4+156x_5+156x_6 - p_1 + a_1 = 18800$ $x_1+x_2+5x_3+5x_4+4x_5+4x_6 + s_2=220$ $0.4x_1+2x_3+8x_5+s_3=45$ $0.1x_2+0.5x_4+2x_6+s_4=45$ $x_1, \dots, x_6, p_1, a_1, s_2, s_3, s_4 \ge 0$

The artificial objective function is $-a_1 = 44x_1+44x_2+940x_3+940x_4+156x_5+156x_6 - p_1 - 18800$. Therefore we get the initial tableau.

$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $p_1$ $a_1$ $s_2$ $s_3$ $s_4$
44 44 940 940 156 156 -1 1 18800
1 1 5 5 4 4 1 220
0.4 2 8 1 45
0.1 0.5 2 1 45
-1800 -1800 -3360 -3360 -13500 -13500 0
-44 -44 -940 -940 -156 -156 1 -18800

We may choose any variable among $x_1, \dots, x_6$ as the entering variable as their coefficients in the artificial objective function are negative. We choose $x_3$ here. Now the replacement quantities are $18800/940 = 20, 220/5 = 44, 45/2 = 22.5$. So the first entry in column 3 is the pivot. Couple of row operations yield:

$x_1$ $x_2$ $x_3$ $x_4$ $x_5$ $x_6$ $p_1$ $a_1$ $s_2$ $s_3$ $s_4$
11/235 11/235 1 1 39/235 39/235 -1/940 1/940 20
36/47 36/47 0 0 149/47 149/47 1/188 1/188 1 120
72/235 -22/235 -2 1802/235 -78/235 1/470 -1/470 1 5
0.1 0.5 2 1 45
-77208/47 -77208/47 -608292/47 -608292/47 -168/47 -168/47 67200
1 0

Solution 1c. The dual linear program is as follows.

Minimize $19200y_1+220y_2+45y_3+45y_4$ $44y_1+y_2+0.4y_3 \ge 1800$ $44y_1 + y_2 + 0.1y_4 \ge 1800$ $940y_1+5y_2+2y_3 \ge 3360$ $940y_1 + 5y_2+0.5y_4 \ge 3360$ $156y_1 + 4y_2+ 8y_3 \ge 13500$ $156y_1 + 4y_2+2y_4 \ge 13500$ $y_1 \le 0, y_2, y_3, y_4 \ge 0$

Solution 2. Denote the cities by 1, 2, 3, 4. Let $x_{ij}$ denote whether the skiers travel from city $i$ to city $j$. In addition, let $b_1, b_2$ be the binary variables indicating whether they will take the non-stop/one-stop flight and the two-stop flight from Pittsburgh to Jackson respectively. Similarly define $b_3, b_4$ for the flights from Salt Lake City to Aspen.

Maximize $\begin{gathered}Mx_{11}+183x_{12}+(443b_1+335b_2)+328x_{14} \\ +183x_{21}+Mx_{22}+279x_{23}+(323b_3+317b_4) \\ +333x_{31}+279x_{32}+Mx_{33}+409x_{34}+\\ 423x_{41}+356x_{42}+403x_{43}+Mx_{44}\end{gathered}$ $x_{i1}+x_{i2}+x_{i3}+x_{i4} = 1$ for all $i = 1, 2, 3, 4$. $x_{1j}+x_{2j}+x_{3j}+x_{4j} = 1$ for all $j = 1, 2, 3, 4$. $\sum_{i \in D, j\notin D}x_{ij} \ge 1$ for all proper subsets $D$. $b_1 + b_2 \le x_{13}$ $b_3 + b_4 \le x_{24}$