2.4 在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解并代入目标函数，确定哪一个是最优解。(1)max z=2x_(1)+3x_(2)+4x_(3)+7x_(4)}2x_(1)+3x_(2)-x_(3)-4x_(4)=8x_(1)-2x_(2)+6x_(3)-7x_(4)=-3x_(1),x_(2),x_(3),x_(4)geqslant0(2)max z=5x_(1)-2x_(2)+3x_(3)-6x_(4)}x_(1)+2x_(2)+3x_(3)+4x_(4)=72x_(1)+x_(2)+x_(3)+2x_(4)=3x_(1),x_(2),x_(3),x_(4)geqslant0

本题主要考查线性规划中基解、基可行解以及最优解的概念和求解方法。解题的关键思路是先根据约束条件确定基矩阵，通过令非基变量为 0 求解基变量，得到基解，再根据变量非负的条件判断基可行解，最后将基可行解代入目标函数确定最优解。

（1）对于线性规划问题 $\max z = 2x_{1}+3x_{2}+4x_{3}+7x_{4}\begin{cases}2x_{1}+3x_{2}-x_{3}-4x_{4}=8\\x_{1}-2x_{2}+6x_{3}-7x_{4}=-3\\x_{1},x_{2},x_{3},x_{4}\geqslant0\end{cases}$

约束条件的系数矩阵 $A=\begin{pmatrix}2&3& - 1&-4\\1&-2&6&-7\end{pmatrix}$，$m = 2$，$n = 4$，从 $n$ 个变量中选取 $m$ 个变量作为基变量，共有 $C_{4}^{2}=\frac{4!}{2!(4 - 2)!}=\frac{4\times3}{2\times1}=6$ 种选法。

• 选 $x_1,x_2$ 为基变量：
  令 $x_3 = 0,x_4 = 0$，则约束方程组变为 $\begin{cases}2x_{1}+3x_{2}=8\\x_{1}-2x_{2}=-3\end{cases}$
  由第二个方程 $x_{1}=2x_{2}-3$，代入第一个方程得：
  $2(2x_{2}-3)+3x_{2}=8$
  $4x_{2}-6 + 3x_{2}=8$
  $7x_{2}=14$
  $x_{2}=2$
  将 $x_{2}=2$ 代入 $x_{1}=2x_{2}-3$，得 $x_{1}=2\times2 - 3 = 1$
  所以基解 $X^{(1)}=(1,2,0,0)^T$，满足 $x_{1},x_{2},x_{3},x_{4}\geqslant0$，是基可行解。
  将 $X^{(1)}$ 代入目标函数 $z = 2x_{1}+3x_{2}+4x_{3}+7x_{4}$，得 $z_1=2\times1 + 3\times2+4\times0 + 7\times0=2 + 6=8$。
• 选 $x_1,x_3$ 为基变量：
  令 $x_2 = 0,x_4 = 0$，则约束方程组变为 $\begin{cases}2x_{1}-x_{3}=8\\x_{1}+6x_{3}=-3\end{cases}$
  由第二个方程 $x_{1}=-3 - 6x_{3}$，代入第一个方程得：
  $2(-3 - 6x_{3})-x_{3}=8$
  $-6-12x_{3}-x_{3}=8$
  $-13x_{3}=14$
  $x_{3}=-\frac{14}{13}$
  不满足 $x_{3}\geqslant0$，不是基可行解。
• 选 $x_1,x_4$ 为基变量：
  令 $x_2 = 0,x_3 = 0$，则约束方程组变为 $\begin{cases}2x_{1}-4x_{4}=8\\x_{1}-7x_{4}=-3\end{cases}$
  由第二个方程 $x_{1}=7x_{4}-3$，代入第一个方程得：
  $2(7x_{4}-3)-4x_{4}=8$
  $14x_{4}-6 - 4x_{4}=8$
  $10x_{4}=14$
  $x_{4}=\frac{7}{5}$
  将 $x_{4}=\frac{7}{5}$ 代入 $x_{1}=7x_{4}-3$，得 $x_{1}=7\times\frac{7}{5}-3=\frac{49 - 15}{5}=\frac{34}{5}$
  所以基解 $X^{(3)}=(\frac{34}{5},0,0,\frac{7}{5})^T$，满足 $x_{1},x_{2},x_{3},x_{4}\geqslant0$，是基可行解。
  将 $X^{(3)}$ 代入目标函数 $z = 2x_{1}+3x_{2}+4x_{3}+7x_{4}$，得 $z_3=2\times\frac{34}{5}+3\times0 + 4\times0+7\times\frac{7}{5}=\frac{68 + 49}{5}=\frac{117}{5}$。
• 选 $x_2,x_3$ 为基变量：
  令 $x_1 = 0,x_4 = 0$，则约束方程组变为 $\begin{cases}3x_{2}-x_{3}=8\\-2x_{2}+6x_{3}=-3\end{cases}$
  由第一个方程 $x_{3}=3x_{2}-8$，代入第二个方程得：
  $-2x_{2}+6(3x_{2}-8)=-3$
  $-2x_{2}+18x_{2}-48=-3$
  $16x_{2}=45$
  $x_{2}=\frac{45}{16}$
  将 $x_{2}=\frac{45}{16}$ 代入 $x_{3}=3x_{2}-8$，得 $x_{3}=3\times\frac{45}{16}-8=\frac{135 - 128}{16}=\frac{7}{16}$
  所以基解 $X^{(4)}=(0,\frac{45}{16},\frac{7}{16},0)^T$，满足 $x_{1},x_{2},x_{3},x_{4}\geqslant0$，是基可行解。
  将 $X^{(4)}$ 代入目标函数 $z = 2x_{1}+3x_{2}+4x_{3}+7x_{4}$，得 $z_4=2\times0 + 3\times\frac{45}{16}+4\times\frac{7}{16}+7\times0=\frac{135 + 28}{16}=\frac{163}{16}$。
• 选 $x_2,x_4$ 为基变量：
  令 $x_1 = 0,x_3 = 0$，则约束方程组变为 $\begin{cases}3x_{2}-4x_{4}=8\\-2x_{2}-7x_{4}=-3\end{cases}$
  由第一个方程 $x_{2}=\frac{8 + 4x_{4}}{3}$，代入第二个方程得：
  $-2\times\frac{8 + 4x_{4}}{3}-7x_{4}=-3$
  $-16-8x_{4}-21x_{4}=-9$
  $-29x_{4}=7$
  $x_{4}=-\frac{7}{29}$
  不满足 $x_{4}\geqslant0$，不是基可行解。
• 选 $x_3,x_4$ 为基变量：
  令 $x_1 = 0,x_2 = 0$，则约束方程组变为 $\begin{cases}-x_{3}-4x_{4}=8\\6x_{3}-7x_{4}=-3\end{cases}$
  由第一个方程 $x_{3}=-8 - 4x_{4}$，代入第二个方程得：
  $6(-8 - 4x_{4})-7x_{4}=-3$
  $-48-24x_{4}-7x_{4}=-3$
  $-31x_{4}=45$
  $x_{4}=-\frac{45}{31}$
  不满足 $x_{4}\geqslant0$，不是基可行解。

比较 $z_1 = 8$，$z_3=\frac{117}{5}=23.4$，$z_4=\frac{163}{16}=10.1875$，可知 $z_3$ 最大，所以最优解为 $X^{(3)}=(\frac{34}{5},0,0,\frac{7}{5})^T$，最大值为 $\frac{117}{5}$。

（2）对于线性规划问题 $\max z = 5x_{1}-2x_{2}+3x_{3}-6x_{4}\begin{cases}x_{1}+2x_{2}+3x_{3}+4x_{4}=7\\2x_{1}+x_{2}+x_{3}+2x_{4}=3\\x_{1},x_{2},x_{3},x_{4}\geqslant0\end{cases}$

约束条件的系数矩阵 $A=\begin{pmatrix}1&2&3&4\\2&1&1&2\end{pmatrix}$，$m = 2$，$n = 4$，从 $n$ 个变量中选取 $m$ 个变量作为基变量，共有 $C_{4}^{2}=\frac{4!}{2!(4 - 2)!}=\frac{4\times3}{2\times1}=6$ 种选法。

• 选 $x_1,x_2$ 为基变量：
  令 $x_3 = 0,x_4 = 0$，则约束方程组变为 $\begin{cases}x_{1}+2x_{2}=7\\2x_{1}+x_{2}=3\end{cases}$
  由第一个方程 $x_{1}=7 - 2x_{2}$，代入第二个方程得：
  $2(7 - 2x_{2})+x_{2}=3$
  $14-4x_{2}+x_{2}=3$
  $-3x_{2}=-11$
  $x_{2}=\frac{11}{3}$
  将 $x_{2}=\frac{11}{3}$ 代入 $x_{1}=7 - 2x_{2}$，得 $x_{1}=7-2\times\frac{11}{3}=\frac{21 - 22}{3}=-\frac{1}{3}$
  不满足 $x_{1}\geqslant0$，不是基可行解。
• 选 $x_1,x_3$ 为基变量：
  令 $x_2 = 0,x_4 = 0$，则约束方程组变为 $\begin{cases}x_{1}+3x_{3}=7\\2x_{1}+x_{3}=3\end{cases}$
  由第二个方程 $x_{3}=3 - 2x_{1}$，代入第一个方程得：
  $x_{1}+3(3 - 2x_{1})=7$
  $x_{1}+9 - 6x_{1}=7$
  $-5x_{1}=-2$
  $x_{1}=\frac{2}{5}$
  将 $x_{1}=\frac{2}{5}$ 代入 $x_{3}=3 - 2x_{1}$，得 $x_{3}=3-2\times\frac{2}{5}=\frac{15 - 4}{5}=\frac{11}{5}$
  所以基解 $X^{(2)}=(\frac{2}{5},0,\frac{11}{5},0)^T$，满足 $x_{1},x_{2},x_{3},x_{4}\geqslant0$，是基可行解。
  将 $X^{(2)}$ 代入目标函数 $z = 5x_{1}-2x_{2}+3x_{3}-6x_{4}$，得 $z_2=5\times\frac{2}{5}-2\times0 + 3\times\frac{11}{5}-6\times0=2+\frac{33}{5}=\frac{10 + 33}{5}=\frac{43}{5}$。
• 选 $x_1,x_4$ 为基变量：
  令 $x_2 = 0,x_3 = 0$，则约束方程组变为 $\begin{cases}x_{1}+4x_{4}=7\\2x_{1}+2x_{4}=3\end{cases}$
  由第二个方程 $x_{1}=\frac{3 - 2x_{4}}{2}$，代入第一个方程得：
  $\frac{3 - 2x_{4}}{2}+4x_{4}=7$
  $3 - 2x_{4}+8x_{4}=14$
  $6x_{4}=11$
  $x_{4}=\frac{11}{6}$
  将 $x_{4}=\frac{11}{6}$ 代入 $x_{1}=\frac{3 - 2x_{4}}{2}$，得 $x_{1}=\frac{3-2\times\frac{11}{6}}{2}=\frac{9 - 11}{6}=-\frac{1}{3}$
  不满足 $x_{1}\geqslant0$，不是基可行解。
• 选 $x_2,x_3$ 为基变量：
  令 $x_1 = 0,x_4 = 0$，则约束方程组变为 $\begin{cases}2x_{2}+3x_{3}=7\\x_{2}+x_{3}=3\end{cases}$
  由第二个方程 $x_{2}=3 - x_{3}$，代入第一个方程得：
  $2(3 - x_{3})+3x_{3}=7$
  $6-2x_{3}+3x_{3}=7$
  $x_{3}=1$
  将 $x_{3}=1$ 代入 $x_{2}=3 - x_{3}$，得 $x_{2}=3 - 1 = 2$
  所以基解 $X^{(5)}=(0,2,1,0)^T$，满足 $x_{1},x_{2},x_{3},x_{4}\geqslant0$，是基可行解。
  将 $X^{(5)}$ 代入目标函数 $z = 5x_{1}-2x_{2}+3x_{3}-6x_{4}$，得 $z_5=5\times0-2\times2 + 3\times1-6\times0=-4 + 3=-1$。
• 选 $x_2,x_4$ 为基变量：
  令 $x_1 = 0,x_3 = 0$，则约束方程组变为 $\begin{cases}2x_{2}+4x_{4}=7\\x_{2}+2x_{4}=3\end{cases}$
  第一个方程减去第二个方程的 2 倍得：$0 = 1$，方程组无解。
• 选 $x_3,x_4$ 为基变量：
  令 $x_1 = 0,x_2 = 0$，则约束方程组变为 $\begin{cases}3x_{3}+4x_{4}=7\\x_{3}+2x_{4}=3\end{cases}$
  由第二个方程 $x_{3}=3 - 2x_{4}$，代入第一个方程得：
  $3(3 - 2x_{4})+4x_{4}=7$
  $9-6x_{4}+4x_{4}=7$
  $-2x_{4}=-2$
  $x_{4}=1$
  将 $x_{4}=1$ 代入 $x_{3}=3 - 2x_{4}$，得 $x_{3}=3-2\times1 = 1$
  所以基解 $X^{(6)}=(0,0,1,1)^T$，满足 $x_{1},x_{2},x_{3},x_{4}\geqslant0$，是基可行解。
  将 $X^{(6)}$ 代入目标函数 $z = 5x_{1}-2x_{2}+3x_{3}-6x_{4}$，得 $z_6=5\times0-2\times0 + 3\times1-6\times1=3 - 6=-3$。

比较 $z_2=\frac{43}{5}=8.6$，$z_5=-1$，$z_6=-3$，可知 $z_2$ 最大，所以最优解为 $X^{(2)}=(\frac{2}{5},0,\frac{11}{5},0)^T$，最大值为 $\frac{43}{5}$。