线性规划(扩展)

数学学习 · 爱知数学讲义

18
本章目录 · 12 节

学习目标

会画出二元一次不等式(组)表示的平面区域;会求线性目标函数在可行域上的最大值与最小值;能把简单实际问题列成线性规划并求解。

1 二元一次不等式表示的平面区域

一元一次不等式的解集是数轴上的射线。多一个未知数以后,解集变成平面上的一块区域。

方程 ( 不同时为 )的图象是一条直线,它把平面分成两侧。不等式 表示其中一侧, 表示另一侧。含等号时,边界直线也算进去,画实线;不含等号时边界取不到,画虚线。

判断哪一侧:在直线外任取一点代入(常用原点,但原点若在直线上就换别的点)。不等式成立,就取该点所在的那一侧;不成立,就取另一侧。

xyO x+y=4 x+y<4 x+y>4 直线把平面分成两侧。把原点代入 0+0<4,故原点所在一侧是 x+y<4
蓝线是 。原点代入得 ,所以原点这一侧(浅蓝)是 ,另一侧是 。

【例1】画出不等式 表示的平面区域。原点在哪一侧?

解:

先画直线 ,即 。不等式是严格的,画虚线。

原点 :,成立,故原点所在一侧(直线下方)就是所求区域,不含边界。

说明:直线过 、。不要把“”理解成“在 轴上方”——那是一次函数 的说法,这里看的是代入后的符号。

【例2】不等式 和 各表示什么区域?

解:

是水平直线 及其上方的半平面,含边界,画实线。

是竖直线 左侧的半平面,不含边界,画虚线。

先把等式画成直线,再拿一点(常用原点)代入,看这一侧满不满足不等式。

1.1 小结

本节抓住「二元一次不等式表示的平面区域」。一元一次不等式的解集是数轴上的射线。对照例题把公式用一遍。

2 不等式组与可行域

几个二元一次不等式同时成立,解集是各半平面的公共部分,叫做这个不等式组的平面区域。线性规划里把这块区域叫做可行域,区域里的点叫做可行解。

边界直线的交点叫做顶点。有界的可行域通常是凸多边形(含边界时是闭的);某一侧没有限制时,可行域可以无界。

xyO x+y=4 x+2y=6 (0,0) (4,0) (2,2) (0,3) 绿区是可行域:x≥0,y≥0,x+y≤4,x+2y≤6。红点是顶点
绿多边形是可行域。四条边界:、、、。红点是四个顶点。

【例3】画出不等式组 ,,, 的平面区域,并求出所有顶点。

解:

、 是第一象限(含坐标轴)。 与两轴交于 、; 与两轴交于 、。

两条斜线的交点:由 与 相减得 ,再得 ,交点 。

可行域是凸四边形,顶点为 、、、。 不在 内(), 不在 内,都不是顶点。

【例4】若把上题的 改成 ,可行域怎样变?还有没有顶点 、?

解:

边界 改画虚线,这条边上的点都取不到。

、 落在这条直线上,不再属于可行域。区域变成“缺掉这条边”的开的一块,只剩下顶点 、。

记住:可行域是半平面的公共部分,顶点必须同时满足每一条约束,含等号的边界才能当顶点。

2.1 小结

本节抓住「不等式组与可行域」。几个二元一次不等式同时成立,解集是各半平面的公共部分,叫做这个不等式组的平面区域。对照例题把公式用一遍。

3 目标函数与最优解

在可行域上求线性函数 ( 是常数,不影响谁大谁小)的最大值或最小值,叫做简单线性规划。 叫做目标函数。使 取到最大或最小的可行解叫做最优解,对应的 叫做最优值。

把 改写成 (设 ),这是一簇平行直线,斜率相同,截距随 变。在图上平移这簇直线,看它即将离开可行域的那个位置: 在那里取到最大或最小。

3.1 最优解在顶点取到

定理(最优解在顶点取到)线性目标函数在凸多边形可行域(含边界)上的最大值、最小值,一定在某个顶点处取到。若目标函数的等值线与某条边平行,则这条边上每一点都是最优解,最优值相同。

证明:直观:等值线 是平行直线。平移时,与凸多边形的第一次、最后一次接触一定发生在顶点,或者贴着一整条边滑过。

因此实际做法是:先求出可行域的全部顶点,再把每个顶点代入目标函数,比较大小。这比在图上平移更稳,也方便检查。

xyO z=2 z=4 z=6 目标函数 z=x+2y 是一簇平行线。平移到 z=6 时与边界重合,整条红边上 z 都最大
绿区仍是上节的可行域。蓝虚线是 的等值线。平移到红线 时与边 重合,这条边上每一点都使 最大。

【例5】在例3的可行域上,求 的最大值和最小值。

解:

顶点代入:,,,。

最大值 ,在 取到;最小值 ,在 取到。

等值线 即 ,斜率 ,与四条边都不平行,所以最优解都是唯一顶点。

【例6】同一可行域上,求 的最大值。最优解是否唯一?

解:

,,,。

最大值是 ,在 与 都取到。等值线 正好就是约束边界,所以连接这两点的整条线段上都有 。

最优解不唯一:线段 上每一点都是最优解。

【例7】某工厂生产甲、乙两种产品。生产一件甲耗原料 单位、原料 单位,利润 万元;生产一件乙耗 单位、 单位,利润 万元。原料 不超过 单位, 不超过 单位。设甲、乙分别生产 、 件(),怎样安排利润最大?

解:

约束:,,,。目标: 最大。

顶点:,( 且 ),( 与 联立),。

,,,。最大利润 万元,此时甲 件、乙 件。

【例8】在例3的可行域内,若 、 必须是整数,求 的最大值。

解:

先看连续情形最大值在 ,已经是整点,。

为稳妥把可行域内整点列出:,,,。

逐个算 仍是 最大。若最优顶点不是整点,就要在附近整点里再比较,不能直接把顶点坐标四舍五入。

说明:先画出可行域,再把目标函数看成一簇平行线去平移;最优解一定在顶点(或一条边上)取到。整点问题先找连续最优,再检查格子点。

3.2 小结

本节抓住「目标函数与最优解」。在可行域上求线性函数 ( 是常数,不影响谁大谁小)的最大值或最小值,叫做简单线性规划。对照例题把公式用一遍。

本章总结

这一章一共 3 节。合上书应能用自己的话答出下面各节的要点,再去做练习。

1 二元一次不等式表示的平面区域:本节抓住「二元一次不等式表示的平面区域」。一元一次不等式的解集是数轴上的射线。对照例题把公式用一遍。

2 不等式组与可行域:本节抓住「不等式组与可行域」。几个二元一次不等式同时成立,解集是各半平面的公共部分,叫做这个不等式组的平面区域。对照例题把公式用一遍。

3 目标函数与最优解:本节抓住「目标函数与最优解」。在可行域上求线性函数 ( 是常数,不影响谁大谁小)的最大值或最小值,叫做简单线性规划。对照例题把公式用一遍。

贯通全章:先画直线再代点定侧。可行域看公共部分,最值看顶点。等值线与边平行时整条边都最优。

把各节小结连起来复述一遍,对照学习目标查缺,再进入易错与练习。

易错

误:用 那种“上方下方”去套 。正:代入一个点看符号,不要凭图的上下猜测。

误:原点在直线上仍用原点判断。正:换一个不在直线上的点。

误:严格不等式的边界也当成可行解。正:、 画虚线,边界点不是可行解。

误:最优解一定唯一。正:等值线与边界平行时,整条边上都是最优解。

误:只看一个顶点。正:每个顶点都要代入目标函数再比较。

误:实际问题里件数直接用非整顶点。正:件数是整数时要在可行域的整点上再比一次。

误:把 当成 且 的顶点。正:还要同时满足另一条约束。

练习

先独立完成,再对照答案。看错在概念、运算、图形还是推理。

1. 二元一次不等式的解集是什么?

2. 怎样判断取直线的哪一侧?

3. 实线与虚线的差别?

4. 可行域、可行解、最优解各指什么?

5. 线性目标函数的最值在何处取到?

6. 例3可行域的四个顶点。

7. 在该区域上 的最大值。

8. 为什么 的最大值不唯一?

9. 目标函数里的常数项影响最优解吗?

10. 实际问题里 、 表示件数时要注意什么?

11. 无界可行域上线性目标函数一定有最大值吗?

12. 写出例7的约束与目标。

答案与解析

显示答案

1. 平面上由直线分出的一侧(含等号时连同这条直线)。

2. 取直线外一点代入,常用原点;成立就取该侧。

3. 含等号画实线,边界可取;不含等号画虚线,边界不可取。

4. 可行域是不等式组的公共区域;其中的点是可行解;使目标函数最优的可行解是最优解。

5. 凸多边形可行域的顶点;与边平行时,该边上每一点都可以。

6. 、、、。

7. ,在 取到。

8. 等值线与边 重合,这条边上 都是 。

9. 不影响谁大谁小,只整体平移最优值。

10. 先按连续线性规划做,再限制在可行域的整点上比较。

11. 不一定。等值线能沿无界方向一直平移时,最大值可以不存在。

12. ,,; 最大。最优 ,。