线性规划，例题（中等）

(a) 区域由四条直线围成：坐标轴 $x=0$ 与 $y=0$、直线 $x+y=8$，以及直线 $y=3x$。两两求解这些边界来找顶点，只保留满足每个不等式的交点。

$$y=3x,\; y=0 \;\Rightarrow\; (0,0)$$

$$x+y=8,\; y=0 \;\Rightarrow\; (8,0)$$

$$y=3x,\; x+y=8 \;\Rightarrow\; x+3x=8,\; 4x=8,\; x=2,\; y=6$$

所以区域是以 $O(0,0)$、$B(8,0)$ 与 $C(2,6)$ 为顶点的三角形。

(b) 在每个顶点求 $k=5x+4y$：

$$\text{在 } O(0,0):\quad k=5(0)+4(0)=0$$

$$\text{在 } B(8,0):\quad k=5(8)+4(0)=40$$

$$\text{在 } C(2,6):\quad k=5(2)+4(6)=10+24=34$$

(a) 逐条翻译。「总共最多 12」限制总和；「派最多为蛋糕的两倍」把 $y$ 限于 $2x$；「至少 2 个蛋糕」为 $x$ 设下下限。

$$x+y\le 12,\qquad y\le 2x,\qquad x\ge 2$$

(b) 这个区域的顶点是边界直线 $x=2$、$y=0$、$y=2x$ 与 $x+y=12$ 两两相交之处。求解每一对，并保留满足所有约束的点：

$$x=2,\; y=0 \;\Rightarrow\; (2,0)$$

$$x=2,\; y=2x \;\Rightarrow\; y=4,\quad (2,4)$$

$$y=2x,\; x+y=12 \;\Rightarrow\; 3x=12,\; x=4,\; y=8,\quad (4,8)$$

$$x+y=12,\; y=0 \;\Rightarrow\; (12,0)$$

现在在每个顶点求利润 $P=5x+9y$：

$$\text{在 }(2,0):\; P=5(2)+9(0)=10$$

$$\text{在 }(2,4):\; P=5(2)+9(4)=10+36=46$$

$$\text{在 }(4,8):\; P=5(4)+9(8)=20+72=92$$

$$\text{在 }(12,0):\; P=5(12)+9(0)=60$$

两个 $\ge$ 约束把区域推离原点，于是它向右上方无上界地延伸，没有最大值，但在某个顶点有最小值。两两配对边界来找顶点，只保留同时满足两个不等式的点。

$$x+2y=8,\; y=0 \;\Rightarrow\; (8,0)$$

$$2x+y=10,\; x=0 \;\Rightarrow\; (0,10)$$

两条斜线也会相交。从第一式取 $x=8-2y$，代入第二式：

$$2(8-2y)+y=10 \;\Rightarrow\; 16-3y=10 \;\Rightarrow\; y=2,\; x=4$$

所以区域的顶点是 $(8,0)$、$(4,2)$ 与 $(0,10)$。另外两个坐标轴交点各自违反了它并非由之得出的那个约束：$(5,0)$ 使 $x+2y=5<8$，$(0,4)$ 使 $2x+y=4<10$，因此都不是顶点。

现在求 $C=3x+2y$：

$$\text{在 }(8,0):\; C=3(8)+2(0)=24$$

$$\text{在 }(4,2):\; C=3(4)+2(2)=12+4=16$$

$$\text{在 }(0,10):\; C=3(0)+2(10)=20$$

一个点只有同时满足每一个不等式，才算落在可行区域内，只满足其中一个是不够的。把每个点分别代入 $2x+y\le 10$ 与 $x+3y\le 12$ 来检验，三个点都已经满足 $x\ge 0$ 与 $y\ge 0$。

$$A(3,2):\quad 2(3)+2=8\le 10, \qquad 3+3(2)=9\le 12$$

两个限制对 $A$ 都成立，所以它满足每一个约束，落在区域内。

$$B(5,3):\quad 2(5)+3=13>10 \qquad C(1,4):\quad 1+3(4)=13>12$$

$B$ 已经违反第一个约束；$C$ 满足第一个约束($2(1)+4=6\le 10$),却违反第二个，所以两点都不可行。

(a) 利用两个截距来建立方程：该直线在 $x$ 轴上的截距为 $4$，在 $y$ 轴上的截距为 $6$，所以写成截距式，再消去分数。

$$\frac{x}{4}+\frac{y}{6}=1 \;\Rightarrow\; 3x+2y=12$$

(b) 由于原点位于区域内，把 $(0,0)$ 代入左边，并与 $12$ 比较。

$$3(0)+2(0)=0, \quad 0<12$$

把该顶点与给定的最大值代入目标函数，即得一个关于 $q$ 的方程。

$$3(6)+q(4)=38$$

$$18+4q=38 \;\Rightarrow\; 4q=20 \;\Rightarrow\; q=5$$

(a) 该区域由坐标轴、直线 $x=8$ 与直线 $x+2y=12$ 围成。两两配对这些边界来求各顶点。

$$x=0,\;y=0 \;\Rightarrow\;(0,0) \qquad x=8,\;y=0 \;\Rightarrow\;(8,0)$$

$$x=8,\;x+2y=12 \;\Rightarrow\; y=2,\;(8,2) \qquad x=0,\;x+2y=12 \;\Rightarrow\; y=6,\;(0,6)$$

(b) 在每个顶点求 $K=x+2y$。

$$K(0,0)=0,\quad K(8,0)=8,\quad K(8,2)=8+4=12,\quad K(0,6)=0+12=12$$

$K$ 在 $(8,2)$ 与 $(0,6)$ 两处都等于 $12$，这并非巧合。$K=x+2y$ 的斜率与边界直线 $x+2y=12$ 完全相同，所以这条边上的每一点本来就满足 $x+2y=12$，这意味着 $K=12$ 沿整条边都成立，而不只是在两个端点。

(a) 逐条翻译。「总共至少 12 箱」为总和设下下限；「卫生用品箱数至少为食物箱数的一半」把 $y$ 的下限定为 $\frac{x}{2}$；「食物箱最多 16」为 $x$ 设上限。

$$x+y\ge 12,\qquad x\le 2y,\qquad x\le 16$$

(b) 这个区域的顶点是 $x+y=12$、$x=2y$ 与 $x=16$ 两两相交之处，再加上坐标轴 $x=0$。求解每一对相关的边界：

$$x=0,\;x+y=12 \;\Rightarrow\;(0,12) \qquad x+y=12,\;x=2y \;\Rightarrow\; 2y+y=12,\;y=4,\;x=8,\;(8,4)$$

$$x=2y,\;x=16 \;\Rightarrow\; y=8,\;(16,8)$$

现在在每个顶点求成本 $C=8x+5y$：

$$C(0,12)=8(0)+5(12)=60,\quad C(8,4)=64+20=84,\quad C(16,8)=128+40=168$$