线性规划，例题（KBAT）

(a) 把每个上限读成不等式。银线：每件用 1 单位，最多 10 单位，所以 $x+y\le 10$。

珠子：每条手链 $1$ 包、每条项链 $2$ 包，最多 14 包，所以 $x+2y\le 14$。陈列规则给出 $x\ge 2$ 与 $y\ge 1$。

$$x+y\le 10,\quad x+2y\le 14,\quad x\ge 2,\quad y\ge 1$$

(b) 边界为 $x+y=10$、$x+2y=14$、$x=2$ 与 $y=1$。两两求解，并保留满足整组约束的交点。

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

$$y=1,\; x+y=10 \;\Rightarrow\; x=9,\quad (9,1)$$

$$(x+2y)-(x+y)=14-10 \;\Rightarrow\; y=4,\; x=6,\quad (6,4)$$

$$x=2,\; x+2y=14 \;\Rightarrow\; 2y=12,\; y=6,\quad (2,6)$$

所以区域是以 $(2,1)$、$(9,1)$、$(6,4)$ 与 $(2,6)$ 为顶点的四边形。

(c) 在每个顶点求利润 $P=3x+5y$：

$$\text{在 }(2,1):\; P=3(2)+5(1)=6+5=11$$

$$\text{在 }(9,1):\; P=3(9)+5(1)=27+5=32$$

$$\text{在 }(6,4):\; P=3(6)+5(4)=18+20=38$$

$$\text{在 }(2,6):\; P=3(2)+5(6)=6+30=36$$

先钉住顶点。边界为 $x=1$、$y=2$ 与 $x+y=8$；两两求解。

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

$$x=1,\; x+y=8 \;\Rightarrow\; y=7,\quad (1,7)$$

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

所以区域是以 $(1,2)$、$(1,7)$ 与 $(6,2)$ 为顶点的三角形。在每个顶点求 $k=5x+5y$：

$$\text{在 }(1,2):\; k=5(1)+5(2)=5+10=15$$

$$\text{在 }(1,7):\; k=5(1)+5(7)=5+35=40$$

$$\text{在 }(6,2):\; k=5(6)+5(2)=30+10=40$$

两个顶点在顶端并列，都是 $k=40$。这提示目标函数与连接它们的那条边平行。

把目标函数改写成 $k=5(x+y)$：它只依赖 $x+y$，而从 $(1,7)$ 到 $(6,2)$ 的那条边恰好是直线 $x+y=8$，也就是 $x+y$ 在区域中能取到的最大值。

(a) 两两求解边界。原点、两个相关的坐标轴交点，以及两条斜线的交点，给出四个顶点。

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

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

$$3x+2y=18,\; y=0 \;\Rightarrow\; x=6,\quad C(6,0)$$

对最后一个顶点，用第二式减去第一条斜线的式子：

$$(3x+2y)-(x+2y)=18-10 \;\Rightarrow\; 2x=8,\; x=4,\; \text{再由 } 4+2y=10 \;\Rightarrow\; y=3$$

即 $B(4,3)$。四个顶点为 $O(0,0)$、$A(0,5)$、$B(4,3)$ 与 $C(6,0)$，其中 $C$ 就是正 $x$ 轴上的顶点。

(b) 把 $p$ 当作未知，在每个顶点求 $k=px+y$：

$$k_O=0,\quad k_A=5,\quad k_B=4p+3,\quad k_C=6p$$

要使最大值出现在 $C$，值 $k_C=6p$ 必须不小于其余每个顶点的值。由于 $p>0$，$6p$ 已经超过 $k_O=0$。

把它与 $A$、$B$ 比较：

$$6p\ge 5 \;\Rightarrow\; p\ge \tfrac{5}{6}$$

$$6p\ge 4p+3 \;\Rightarrow\; 2p\ge 3 \;\Rightarrow\; p\ge \tfrac{3}{2}$$

两个条件中较强的是 $p\ge\tfrac{3}{2}$，它也自动保证了 $p\ge\tfrac{5}{6}$。

与在封闭区域内求最大利润不同，这个区域对 $x+y$ 没有上限，所以先找出边界 $x+y=12$ 与 $y=2x$ 的交点，这个顶点正是寻找最小值的自然起点，因为沿任一边界继续往外走只会增加成本。

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

直线 $x+y=12$ 也与只订钢笔的边 $y=0$ 在第二个顶点相交：

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

所以该区域的两个有限顶点是 $(4,8)$ 与 $(12,0)$；在其余地方，区域沿 $y=2x$（$x$ 增大）或沿 $y=0$（$x$ 超过 12 继续增大）无限延伸。在这两个顶点求成本，并检查沿每个方向会发生什么。

$$\text{在 }(4,8):\; C=8(4)+5(8)=32+40=72$$

$$\text{在 }(12,0):\; C=8(12)+5(0)=96$$

$$\text{沿 }y=2x,\; x\ge 4:\; C=8x+5(2x)=18x,\text{ 随 }x\text{ 增大而增大}$$

$$\text{沿 }y=0,\; x\ge 12:\; C=8x,\text{ 随 }x\text{ 增大而增大}$$

沿这两个方向，成本只会随 $x$ 增大而升高，所以继续往外走不会打败任何一个顶点；最小值必定落在两个顶点中较便宜的那一个。

(a) 把牛奶限制与非负条件 $y\ge 0$ 结合：由于 $y$ 不可能为负，$2x$ 不可能超过 $2x+y$，所以单凭牛奶限制就已经迫使 $x\le 15$ 成立。

$$y\ge 0 \text{ 且 } 2x+y\le 30 \;\Rightarrow\; 2x\le 2x+y\le 30 \;\Rightarrow\; x\le 15$$

所以烧水的限制并未带来任何新东西；这个区域完全由 $x+y\le 20$、$2x+y\le 30$、$x\ge 0$ 与 $y\ge 0$ 四者决定。(b) 用这四条边界求出每个顶点。

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

$$2x+y=30,\; y=0 \;\Rightarrow\; x=15,\quad A(15,0)$$

$$(2x+y)-(x+y)=30-20 \;\Rightarrow\; x=10,\; y=10,\quad B(10,10)$$

$$x+y=20,\; x=0 \;\Rightarrow\; y=20,\quad C(0,20)$$

检查 $C(0,20)$ 是否满足牛奶限制：$2(0)+20=20\le 30$，所以它确实是该区域的一个顶点。四个顶点为 $O(0,0)$、$A(15,0)$、$B(10,10)$ 与 $C(0,20)$。

(c) 在每个顶点求 $P=3x+2y$：

$$\text{在 }O:\;P=0,\quad\text{在 }A:\;P=3(15)=45$$

$$\text{在 }B:\;P=3(10)+2(10)=30+20=50,\quad\text{在 }C:\;P=2(20)=40$$

(a) “布料与纽扣都被用尽”意味着在 $(4,5)$ 处两个限制都取等号。先检查布料：$4+5=9$，正好与 $x+y\le 9$ 相符，正如预期。

把该点代入纽扣的等式以求 $m$。

$$2(4)+5=m \;\Rightarrow\; m=13$$

(b) 当 $m=13$ 时，区域的四条边界为 $x=1$、$y=1$、$x+y=9$ 与 $2x+y=13$。两两求解得出其余顶点。

$$x=1,\; y=1 \;\Rightarrow\; (1,1)$$

$$y=1,\; 2x+y=13 \;\Rightarrow\; 2x=12,\; x=6,\quad (6,1)$$

检查 $(6,1)$ 是否满足布料限制：$6+1=7\le 9$，所以它确实是一个顶点。

$$x=1,\; x+y=9 \;\Rightarrow\; y=8,\quad (1,8)$$

检查 $(1,8)$ 是否满足纽扣限制：$2(1)+8=10\le 13$，同样确实是顶点。四个顶点为 $(1,1)$、$(6,1)$、$(4,5)$ 与 $(1,8)$。

在每个顶点求 $P=4x+3y$，以核实所给方案胜出。

$$P(1,1)=4+3=7,\quad P(6,1)=24+3=27$$

$$P(4,5)=16+15=31,\quad P(1,8)=4+24=28$$

(a) “至少 40% 是豪华礼篮”意味着 $y$ 至少是礼篮总数 $x+y$ 的 40%。

$$y\ge 0.4(x+y)$$

展开后把 $y$ 项归到同一边。

$$y\ge 0.4x+0.4y \;\Rightarrow\; 0.6y\ge 0.4x \;\Rightarrow\; y\ge \tfrac{0.4}{0.6}x=\tfrac{2}{3}x$$

(b) 三条边界为 $x=3$、$x+y=20$ 与 $y=\tfrac{2}{3}x$（等价于 $3y=2x$）。非负条件 $y\ge 0$ 在这里从未起作用，因为只要 $x\ge 3$，就有 $y\ge\tfrac{2}{3}x\ge 2$。

两两求解这三条边界。

$$x=3,\; y=\tfrac{2}{3}(3)=2,\quad (3,2)$$

$$x=3,\; x+y=20 \;\Rightarrow\; y=17,\quad (3,17)$$

$$x+y=20,\; 3y=2x \;\Rightarrow\; 3y=2(20-y) \;\Rightarrow\; 5y=40,\; y=8,\; x=12,\quad (12,8)$$

三个顶点为 $(3,2)$、$(3,17)$ 与 $(12,8)$。(c) 在每个顶点求 $P=6x+4y$：

$$P(3,2)=18+8=26,\quad P(3,17)=18+68=86,\quad P(12,8)=72+32=104$$

先按常规方法求出区域的顶点，暂时把 $x$ 与 $y$ 当作可以是任意非负数来处理。

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

$$3x+5y=30,\; x=0 \;\Rightarrow\; y=6,\quad (0,6)$$

用 $3x+5y=30$ 减去 $3$ 倍的 $x+y=9$，求出这两条斜线真正的交点。

$$(3x+5y)-3(x+y)=30-27 \;\Rightarrow\; 2y=3,\; y=1.5,\; x=7.5,\quad (7.5,1.5)$$

在四个顶点（包括原点）求 $P=4x+5y$：

$$P(0,0)=0,\quad P(9,0)=36,\quad P(7.5,1.5)=30+7.5=37.5,\quad P(0,6)=30$$

最高值 RM37.50 出现在 $(7.5,1.5)$，但工具套装只能整套计算，所以这个顶点无法精确实现。真正的最佳方案必须是它附近的一个整数点，因此直接检验附近可能的整数点。

$$(8,1):\; 3(8)+5(1)=29\le 30,\; 8+1=9\le 9 \;\Rightarrow\; \text{可行},\; P=32+5=37$$

$$(7,1):\; 3(7)+5(1)=26\le 30 \;\Rightarrow\; \text{可行},\; P=28+5=33$$

$$(6,2):\; 3(6)+5(2)=28\le 30 \;\Rightarrow\; \text{可行},\; P=24+10=34$$

在这些整数点中，$(8,1)$ 给出的利润最高，甚至高于整数顶点 $(9,0)$ 的 RM36。