简单的线性规划

三步定区域: ① 画出边界直线 Ax+By+C=0(先当作等号画一条直线);② 判断边界是实线还是虚线:不等式含「=」(≥、≤)→实线(包含边界);不含「=」(>、<)→虚线(不包含边界);③ 取一个不在直线上的特殊点(最常用原点 (0,0),若直线过原点则换 (1,0) 或 (0,1))代入不等式左边,成立就说明这一侧就是所求区域,不成立就取另一侧。

快速判断哪一侧: 若原点不在直线上,把 (0,0) 代入 Ax+By+C:结果与「0」的大小关系和不等式方向一致的那一侧,就是原点所在的一侧;否则是另一侧。例如 x+y−2≤0,代入原点:0+0−2=−2≤0 成立,所以原点所在的一侧(直线左下方)就是所求区域。

⚠ 忘记判断实线虚线是最常见的丢分点;直线过原点时不能再用原点代入判断,必须换一个点,如 (1,0) 或 (0,1)。

把变量 x、y 要满足的一组二元一次不等式(或方程)叫线性约束条件。每条不等式画出一个半平面,把它们的阴影叠在一起,重叠(交集)部分就是可行域——所有约束同时满足的点 (x,y) 的集合。可行域通常是一个凸多边形(有界)或一片延伸到无穷的区域(无界)。

画可行域标准流程: ① 逐条画出每条边界直线,标出实线/虚线;② 逐条判断阴影方向(代点);③ 找出所有阴影都覆盖到的公共区域,就是可行域;④ 求出可行域各顶点坐标(通常联立相邻两条边界直线方程求交点)。

⚠ 可行域是交集不是并集——每一条约束都要同时满足,少判断一条约束、多画一块阴影,整个可行域就错了。顶点坐标一定要联立方程组算准,不能只在图上估读。

目标函数 z=ax+by 里,(x,y) 是可行域里的点,z 是要求最值的量。把它变形成斜率截距式 y=−(a/b)x+z/b:斜率 −a/b 是固定的(由 a、b 决定),截距 z/b 随 z 变化——这说明对每一个 z 的取值,y=−(a/b)x+z/b 都是一条与原直线平行的直线,z 变化就是这条直线在平行移动。

操作步骤: ① 画出可行域;② 把目标直线 ax+by=0 画出来(作为「参照斜率」的虚拟直线);③ 保持斜率不变,平行移动这条直线,让它扫过可行域;④ 直线最后一次与可行域「擦边」接触的位置(通常是顶点),就是最值点。

⚠ 平移方向不能凭直觉猜——必须先看 b 的正负号,再确定「z 变大对应截距变大还是变小」。b<0 时,直线往上移 z 反而在减小,这是最容易搞反的地方。

因为目标函数的等值线是一族平行直线,而可行域是凸多边形,平移直线扫过凸多边形时,最先或最后接触到的点只能是顶点(或顶点间的整条边,此时边上所有点都取到最值)。这就是顶点法的道理:不用画图慢慢平移,直接把可行域每个顶点坐标代入 z=ax+by,比较大小即可。

什么时候最值在整条边上(无穷多最优解)? 当目标直线的斜率 −a/b 恰好等于可行域某条边界的斜率时,平移到贴合该边界的瞬间,这条边上所有点的 z 值都相等,边的两端点(两个顶点)和边上其他点都是最优解。

⚠ 顶点法只对线性目标函数成立(z=ax+by),因为只有线性目标的等值线才是直线。顶点坐标必须联立方程组精确求解,不能读图估值,否则比较大小会出错。

目标函数不总是 ax+by 这种线性式,还可能带平方或分式,这时顶点法直接失效,要靠几何意义转化。

距离类: z=(x−a)²+(y−b)² 中,√z 是点到 (a,b) 的距离,所以先找「可行域内离 (a,b) 最近/最远的点」,最近点若不在顶点,常是 (a,b) 向可行域边界作垂线的垂足;最远点几乎总在顶点(离得越远,顶点往往越占优)。

斜率类: z=y/x 是可行域内的点与原点连线的斜率,把这条连线想象成绕原点转动的「动直线」,转到与可行域边界相切或经过顶点的位置,斜率取得最大或最小。斜率类目标函数不能用顶点法直接代入比大小当作唯一判据——还要注意连线是否会被可行域「挡住」,一般结论是最值仍在顶点取得,但方向感要靠画图配合验证。

⚠ 非线性目标函数绝不能套用「等值线是平行直线」的平移图像;距离类看到的是圆在扩大缩小,斜率类看到的是直线绕定点旋转。混用平移法会得到完全错误的答案。

实际问题(比如「安排多少辆车」「生产多少件产品」)里,x、y 往往必须是非负整数。这时约束条件不变,但可行域内的候选点只能是整点(格点)——普通线性规划求出的最优解如果坐标不是整数,就不能直接用,必须在附近重新找整点。

找整点最优解的常用方法: ① 先用顶点法求出「理论最优点」(可能不是整点);② 若不是整点,则以该点为中心,在可行域内部沿目标直线方向平移检验,找出附近满足约束的整点,逐一代入 z 比较;③ 也可以直接在可行域内逐个枚举整点(若整点数量不多)。

⚠ 千万不能把「非整数最优点」直接四舍五入当作答案——四舍五入后的点可能已经跑出可行域,必须验证是否满足所有约束条件,再比较 z 值。

题型A — 画区域 / 判断点是否在区域内

触发信号:给出一个或多个二元一次不等式,要求画出所表示的平面区域,或判断某点是否满足。

标准动作:画边界直线 → 定实虚线(含等号实线,不含虚线)→ 代特殊点(通常原点)判方向。判断点是否满足直接代入不等式检验真假。

示例(带解):画出 2x−y−2≥0 表示的区域。边界 2x−y−2=0(实线,过(1,0)、(0,−2))。代原点:2×0−0−2=−2≥0 不成立,所以原点不在区域内,区域在直线的右下方(不含原点一侧)。

陷阱:忘记实线虚线;直线过原点时仍用原点代入(必须换点,如(1,0));把「不成立」误判为「原点所在一侧就是区域」。

题型B — 画可行域并求顶点坐标

触发信号:给出一组线性约束条件(通常3条及以上,常含x≥0,y≥0),要求画出可行域。

标准动作:逐条画边界定方向 → 找公共阴影部分 → 相邻边界直线联立方程组求交点坐标(顶点)。

示例(带解):约束 x≥0,y≥0,x+y≤6,2x+y≤8。四条边界交出一个四边形,顶点为(0,0)、(4,0)(由2x+y=8与y=0联立)、(2,4)(由x+y=6与2x+y=8联立)、(0,6)(由x+y=6与x=0联立)。

陷阱:漏掉某条约束导致可行域画大;顶点坐标只在图上估读不联立方程组算,造成后续比较 z 值出错。

题型C — 线性目标函数求最值(顶点法)

触发信号:目标函数形如 z=ax+by,要求在可行域内求最大值或最小值。

标准动作:求出可行域各顶点坐标 → 逐一代入 z=ax+by → 比较得最大/最小值;或变形 y=−(a/b)x+z/b 平移直线找触边点,两法结果一致,顶点法更快更准。

示例(带解):沿用题型B的可行域,z=x+2y。代入顶点:(0,0)→0;(4,0)→4;(2,4)→2+8=10;(0,6)→0+12=12。最大值 z=12,在顶点(0,6)取得;最小值 z=0,在(0,0)取得。

陷阱:漏代某个顶点;b为负时平移方向理解反了;把最大值和最小值对应的顶点弄混。

题型D — 已知最值反求参数

触发信号:给出目标函数含参数(如 z=ax+y),已知在某点取最大/最小值,要求参数取值范围或具体值。

标准动作:把「该点是最优解」翻译成「该点对应的 z 值不小于(或不大于)其余所有顶点的 z 值」,列不等式组解参数;也可从斜率角度:目标直线斜率需落在该顶点相邻两条边界斜率之间。

示例(带解):可行域顶点同上,z=ax+y 在(2,4)处取最大值,求a的范围。需 2a+4 ≥ 0(顶点(0,0))、2a+4 ≥ 4a(顶点(4,0))、2a+4 ≥ 6(顶点(0,6))。由第二式 a≤2;由第三式 a≥1。结合需为最大值(非最小)进一步验证方向,范围为 1≤a≤2。

陷阱:不等号方向弄反(最大值要「≥所有其他顶点」,最小值要「≤」);漏掉某个顶点的比较条件;混淆求最大值和求最小值时不等式方向。

题型E — 非线性目标函数(距离/斜率型)

触发信号:目标函数形如 z=(x−a)²+(y−b)²、z=y/x、z=(y−b)/(x−a),不是简单的 ax+by。

标准动作:先识别几何意义(距离平方 / 斜率),再画出对应的圆或动直线,结合可行域图形找临界位置(垂足或顶点),必要时用点到直线距离公式或联立方程求切点、交点。

示例(带解):可行域同上,求 z=x²+y² 的最小值。z 是点到原点距离的平方,可行域是第一象限内的四边形,离原点最近的点是顶点(0,0)本身(它在可行域内),所以最小值 z=0。若要最大值,比较各顶点到原点距离平方:(4,0)→16,(2,4)→20,(0,6)→36,最大值为 36,在(0,6)取得。

陷阱:把距离类目标函数当线性目标函数硬套顶点法比大小(顶点法对距离类"求最大值"凑巧常对,但求最小值经常不在顶点,需要判断垂足是否落在可行域内);斜率类忘记讨论分母为0或点与参照点共线的特殊情况。

题型F — 实际应用建模(整点最优解)

触发信号:应用题背景(生产安排、运输调配、原料配比等),要求「安排多少」「至少/至多需要多少」,答案必须是整数。

标准动作:设未知数(通常为非负整数)→ 根据题意列出线性约束条件和目标函数 → 画可行域求理论最优顶点 → 若顶点非整点,在可行域内附近的整点中逐一比较,确定真正的整点最优解,并结合实际意义作答。

示例(带解):某工厂用两种原料生产,约束化简后得可行域顶点之一为(2.5,3),目标利润 z=200x+300y。因x需为整数,检验附近整点(2,3)与(3,2)(需满足原约束)代入比较:z(2,3)=1300,z(3,2)=1200,若(2,3)满足所有约束,则最大利润在x=2,y=3时取得,为1300元。

陷阱:直接对非整数顶点四舍五入而不检验是否仍满足约束;漏写「非负整数」这一隐含约束;实际意义作答时忘记写单位或写反哪个是最大哪个是最小。

① 实线虚线搞反:不等式含等号(≥、≤)边界是实线(包含),不含等号(>、<)边界是虚线(不包含)。

② 代入原点判断方向时,若直线恰好过原点,原点代入两边都得0,无法判断,必须换一个不在直线上的点,如 (1,0) 或 (0,1)。

③ 可行域是所有约束的交集,不是某一条约束单独的区域,更不是并集——漏判一条约束会让可行域画错。

④ z=ax+by 变形为 y=−(a/b)x+z/b 后,z 与截距 z/b 的关系取决于 b 的正负:b>0 时 z 增大截距增大(直线上移z变大);b<0 时 z 增大截距反而减小,平移方向的判断容易搞反。

⑤ 最值不一定只在一个顶点取得——当目标直线斜率与可行域某条边斜率相等时,整条边上都是最优解(无穷多解)。

⑥ 非线性目标函数(距离、斜率型)不能用平移直线找截距的方法,必须先转化成对应的几何图形(圆、动直线)分析。

⑦ 距离类 z=(x−a)²+(y−b)² 的最小值不一定在顶点取得,可能在可行域边界上的垂足处,要判断垂足是否落在边界线段内。

⑧ 整点问题不能把非整数最优解简单四舍五入,必须重新在可行域内部逐一检验附近整点是否满足全部约束。

⑨ 斜率型 z=y/x 或 z=(y−b)/(x−a),分母为 0(x=0 或 x=a)时斜率不存在,要单独讨论或排除这类点。

⑩ 求顶点坐标时联立方程组算错(比如符号、消元出错),会导致后面比较 z 值全盘皆错,建议算完顶点后代回两条边界方程各验证一次。

① 可行域是凸集,这是顶点法成立的根本原因: 若干半平面的交集一定是凸集(凸多边形或凸的无界区域)。线性函数在凸集上取最值,必在极点(顶点)处取得——这是凸优化里最基础的结论,线性规划顶点法就是它在二维、两个约束以下的具体体现。理解这一点,你就明白为什么不需要检验区域内部的点,只需扫顶点。

② 目标函数的等值线族是「解的搜索方向」: z=ax+by 的梯度方向是 (a,b),这个方向就是 z 增长最快的方向。平移直线找最大值,本质是在凸多边形里沿梯度方向"推"到底,推到的最后一个顶点就是解——这也是为什么 b 的正负决定了平移方向:梯度分量 b 为正,直线往上移 z 才在增大。

③ 距离类目标的最值,是「圆与凸域的相切/相离」问题的特例: z=(x−a)²+(y−b)² 的等值线是同心圆,最小值对应「最小的能碰到可行域的圆」——如果圆心 (a,b) 本身在可行域内,最小值就是 0;否则最小值对应圆心到可行域最近点的距离平方,这个最近点要么是垂足(落在某条边内部),要么退化为顶点。带着这套「圆扩张/收缩」的图像去想,就不会死记「最值在顶点」这种对非线性目标不总成立的结论。

④ 斜率类目标是「动直线绕定点旋转」,极值出现在动直线与可行域边界相切(即经过顶点)的瞬间: 把 z=y/x 想象成一条过原点、绕原点匀速旋转的射线,转到贴住可行域「上边缘」或「下边缘」的那一刻,对应的顶点就是最大或最小斜率所在处。这套图像同样能处理"过定点的直线与曲线相切求参数范围"这类更难的题目,是同一根思路的延伸。

⑤ 参数反求问题的本质是「顶点占优」不等式组: 已知在某顶点取最值,等价于该顶点的 z 值不劣于所有相邻顶点(凸多边形只需比相邻顶点,因为凸性保证局部最优即全局最优),由此列出的不等式组,几何意义就是「目标直线斜率落在该顶点两条邻边斜率之间」。会用这条几何捷径,可以跳过繁琐的逐点代入比较,直接夹出参数范围。