Linear Programming and Optimization: Difficult Problems with Solutions

Solution:
For every [tex]a[/tex] the origin satisfies all constraints, so the feasible set [tex]D[/tex] is never empty; the question is only whether [tex]z[/tex] is bounded above on [tex]D[/tex].
Case [tex]a\gt 0[/tex]. From [tex]x_1+ax_2\le 3[/tex] and [tex]x_1, x_2\ge 0[/tex] we get
[tex]0\le x_1\le 3,\qquad 0\le x_2\le\frac{3}{a}[/tex]
so [tex]D[/tex] is a bounded closed polygon, and a linear function attains its maximum on it (at a vertex). In fact for [tex]x_1\le 3[/tex] the first two constraints hold automatically ([tex]x_1-2x_2\le 3\lt 4[/tex], [tex]x_1-x_2\le 3\lt 6[/tex]), so [tex]D[/tex] is the triangle with vertices [tex]\left(0 , 0\right)[/tex], [tex]\left(3 , 0\right)[/tex], [tex]\left(0 , \frac{3}{a}\right)[/tex] and
[tex]z_{\max}=\max\left\{6 , \frac{3}{a}\right\}[/tex]
Case [tex]a\le 0[/tex]. Every point [tex]\left(0 , t\right)[/tex] with [tex]t\ge 0[/tex] is feasible, because
[tex]-2t\le 4,\qquad -t\le 6,\qquad at\le 0\le 3[/tex]
Geometrically, the whole positive [tex]x_2[/tex]-axis lies in [tex]D[/tex], and along it [tex]z\left(0 , t\right)=t\to+\infty[/tex], so [tex]z[/tex] has no maximum. (This includes [tex]a=0[/tex], when the third constraint is just [tex]x_1\le 3[/tex].)
The problem has a solution exactly for [tex]a\in\left(0 , +\infty\right)[/tex].

Solution:
Each of [tex]x_1, x_4, x_6[/tex] appears with coefficient [tex]1[/tex] in exactly one equation, so the initial basic feasible solution is [tex]x_1=7[/tex], [tex]x_4=12[/tex], [tex]x_6=10[/tex], the other variables [tex]0[/tex], with [tex]F=14.76[/tex]. The basic variables have zero cost, so the relative estimates of the free variables are their coefficients in [tex]F[/tex]:
[tex]\Delta_2=1,\qquad \Delta_3=-3,\qquad \Delta_5=-2[/tex]
For a minimum, a negative estimate means that [tex]F[/tex] can still decrease. Iteration [tex]1[/tex]: [tex]x_3[/tex] enters (most negative estimate). Ratio test over the positive entries of its column: [tex]\frac{12}{4}=3[/tex] (row [tex]2[/tex]) and [tex]\frac{10}{3}[/tex] (row [tex]3[/tex]); the minimum is in row [tex]2[/tex], so [tex]x_4[/tex] leaves. After pivoting:
[tex]x_3=3+\frac{1}{2}x_2-\frac{1}{4}x_4,\quad x_1=10-\frac{5}{2}x_2-\frac{1}{4}x_4-2x_5,\quad x_6=1+\frac{5}{2}x_2+\frac{3}{4}x_4-8x_5[/tex]
[tex]F=5.76-\frac{1}{2}x_2+\frac{3}{4}x_4-2x_5[/tex]
Iteration [tex]2[/tex]: [tex]x_5[/tex] enters (estimate [tex]-2[/tex]); the ratios are [tex]\frac{10}{2}=5[/tex] and [tex]\frac{1}{8}[/tex], so [tex]x_6[/tex] leaves:
[tex]x_5=\frac{1}{8}+\frac{5}{16}x_2+\frac{3}{32}x_4-\frac{1}{8}x_6,\quad x_1=\frac{39}{4}-\frac{25}{8}x_2-\frac{7}{16}x_4+\frac{1}{4}x_6[/tex]
[tex]F=5.51-\frac{9}{8}x_2+\frac{9}{16}x_4+\frac{1}{4}x_6[/tex]
Iteration [tex]3[/tex]: [tex]x_2[/tex] enters (estimate [tex]-\frac{9}{8}[/tex]). In the expressions of [tex]x_3[/tex] and [tex]x_5[/tex] the coefficient of [tex]x_2[/tex] is positive, so increasing [tex]x_2[/tex] does not make them negative; only the row of [tex]x_1[/tex] limits [tex]x_2[/tex], so [tex]x_1[/tex] leaves:
[tex]x_2=\frac{78}{25}-\frac{8}{25}x_1-\frac{7}{50}x_4+\frac{2}{25}x_6,\qquad F=2+\frac{9}{25}x_1+\frac{18}{25}x_4+\frac{4}{25}x_6[/tex]
All estimates are now non-negative, so the solution is optimal: [tex]x_1=x_4=x_6=0[/tex] and
[tex]x_2=\frac{78}{25}=3.12,\quad x_3=3+\frac{1}{2}\times 3.12=4.56,\quad x_5=\frac{1}{8}+\frac{5}{16}\times 3.12=1.1[/tex]
Check: [tex]3.12-3\times 4.56-2\times 1.1+14.76=2[/tex], and the left-hand sides of the three constraints equal [tex]7[/tex], [tex]12[/tex], [tex]10[/tex]. The minimum cost is [tex]F_{\min}=2[/tex].

Solution:
Each of the variables [tex]x_1, x_2, x_3, x_5[/tex] appears in only one equation, so we express them through [tex]x_4[/tex] and [tex]x_6[/tex]:
[tex]x_1=13-3x_6,\quad x_2=18+x_4-2x_6,\quad x_3=3+2x_4-x_6,\quad x_5=12+3x_4-x_6[/tex]
Substituting into [tex]z[/tex]:
[tex]z=5\left(13-3x_6\right)+\left(18+x_4-2x_6\right)+2\left(3+2x_4-x_6\right)+4x_4+3\left(12+3x_4-x_6\right)+20x_6=125+18x_4-2x_6[/tex]
For [tex]x_4=x_6=0[/tex] we get a feasible point with [tex]z=125[/tex], but [tex]z[/tex] still decreases when [tex]x_6[/tex] grows. The growth of [tex]x_6[/tex] is limited by [tex]x_3=3+2x_4-x_6\ge 0[/tex], i.e. [tex]x_6\le 3+2x_4[/tex]. Hence on the feasible set, using [tex]x_4\ge 0[/tex],
[tex]z=125+18x_4-2x_6\ge 125+18x_4-2\left(3+2x_4\right)=119+14x_4\ge 119[/tex]
Equality requires [tex]x_4=0[/tex] and [tex]x_6=3[/tex]; then [tex]x_1=4[/tex], [tex]x_2=12[/tex], [tex]x_3=0[/tex], [tex]x_5=9[/tex] are all non-negative, so the point [tex]\left(4 , 12 , 0 , 0 , 9 , 3\right)[/tex] is feasible and
[tex]z=20+12+0+0+27+60=119[/tex]
The least value is [tex]119[/tex].

Solution:
The supply is [tex]20+10+15=45[/tex] tons and the demand is [tex]15+20+15+10=60[/tex] tons, so the problem is unbalanced. We add a fictitious warehouse [tex]A_4[/tex] with [tex]15[/tex] tons and zero costs; what it “delivers” is the unmet demand. Let [tex]x_{ij}[/tex] be the amount (in tons) shipped from [tex]A_i[/tex] to [tex]B_j[/tex].
The minimal-element method (first the zero-cost cells of [tex]A_4[/tex], then the cheapest real cells) gives the initial plan and its cost:
[tex]x_{41}=15,\ x_{12}=20,\ x_{24}=10,\ x_{33}=15,\qquad z=20\times 1+10\times 2+15\times 5=115[/tex]
Along the cycle [tex](A_2B_3)^{+},\ (A_2B_4)^{-},\ (A_3B_4)^{+},\ (A_3B_3)^{-}[/tex] the cost changes by [tex]3-2+3-5=-1[/tex] per ton, and we can move [tex]\theta=\min(10, 15)=10[/tex] tons along it. The new plan ([tex]B_1[/tex] stays unsupplied) and its cost:
[tex]x_{12}=20,\ x_{23}=10,\ x_{33}=5,\ x_{34}=10,\qquad z=20\times 1+10\times 3+5\times 5+10\times 3=105[/tex]
Optimality check by potentials: take [tex]u_1=2,\ u_2=3,\ u_3=5,\ u_4=0[/tex] and [tex]v_1=0,\ v_2=-1,\ v_3=0,\ v_4=-2[/tex]. Then [tex]u_i+v_j=c_{ij}[/tex] in every used cell, and all estimates [tex]c_{ij}-u_i-v_j[/tex] (by rows, the last row for [tex]A_4[/tex]) are non-negative:
[tex]\begin{bmatrix}0&0&2&6\\1&4&0&1\\1&0&0&0\\0&1&0&2\end{bmatrix}[/tex]
Hence, for every admissible plan (all of the supply shipped, [tex]B_j[/tex] receiving [tex]r_j[/tex] tons, not more than it needs), since [tex]c_{ij}\ge u_i+v_j[/tex] for [tex]i=1,2,3[/tex], we have
[tex]\sum_{i,j} c_{ij}x_{ij}\ge\sum_{i,j}(u_i+v_j)x_{ij}=2\times 20+3\times 10+5\times 15-r_2-2r_4\ge 145-20-2\times 10=105[/tex]
because [tex]r_2\le 20[/tex] and [tex]r_4\le 10[/tex]. So no plan is cheaper, and the minimum total cost is [tex]105[/tex] dollars.

Solution:
This is an assignment problem; we use the Hungarian method. Subtracting a constant from a whole row or column changes the total time of every assignment by that same constant, since every assignment uses exactly one entry of each row and of each column.
We subtract the row minima [tex]64, 52, 56, 60[/tex] (sum [tex]232[/tex]) and then the column minima [tex]2, 0, 6, 0[/tex] of the new matrix (sum [tex]8[/tex]):
[tex]\begin{bmatrix}6&16&11&0\\3&0&6&2\\2&0&8&12\\2&0&7&10\end{bmatrix}\ \to\ \begin{bmatrix}4&16&5&0\\1&0&0&2\\0&0&2&12\\0&0&1&10\end{bmatrix}[/tex]
All entries are non-negative, so every assignment takes at least [tex]232+8=240[/tex] minutes. There are four independent zeros: worker [tex]1[/tex] on machine [tex]D[/tex], worker [tex]2[/tex] on [tex]C[/tex], worker [tex]3[/tex] on [tex]A[/tex], worker [tex]4[/tex] on [tex]B[/tex]. This assignment attains the bound:
[tex]64+58+58+60=240[/tex]
(Another optimal assignment is [tex]1\to D,\ 2\to C,\ 3\to B,\ 4\to A[/tex] with [tex]64+58+56+62=240[/tex].) The minimum total time is [tex]240[/tex] minutes.