线性规划(扩展)
本章目录 · 12 节
学习目标
会画出二元一次不等式(组)表示的平面区域;会求线性目标函数在可行域上的最大值与最小值;能把简单实际问题列成线性规划并求解。
1 二元一次不等式表示的平面区域
一元一次不等式的解集是数轴上的射线。多一个未知数以后,解集变成平面上的一块区域。
方程 ( 不同时为 )的图象是一条直线,它把平面分成两侧。不等式 表示其中一侧, 表示另一侧。含等号时,边界直线也算进去,画实线;不含等号时边界取不到,画虚线。
判断哪一侧:在直线外任取一点代入(常用原点,但原点若在直线上就换别的点)。不等式成立,就取该点所在的那一侧;不成立,就取另一侧。
【例1】画出不等式 表示的平面区域。原点在哪一侧?
解:
先画直线 ,即 。不等式是严格的,画虚线。
原点 :,成立,故原点所在一侧(直线下方)就是所求区域,不含边界。
说明:直线过 、。不要把“”理解成“在 轴上方”——那是一次函数 的说法,这里看的是代入后的符号。
【例2】不等式 和 各表示什么区域?
解:
是水平直线 及其上方的半平面,含边界,画实线。
是竖直线 左侧的半平面,不含边界,画虚线。
先把等式画成直线,再拿一点(常用原点)代入,看这一侧满不满足不等式。
1.1 小结
本节抓住「二元一次不等式表示的平面区域」。一元一次不等式的解集是数轴上的射线。对照例题把公式用一遍。
2 不等式组与可行域
几个二元一次不等式同时成立,解集是各半平面的公共部分,叫做这个不等式组的平面区域。线性规划里把这块区域叫做可行域,区域里的点叫做可行解。
边界直线的交点叫做顶点。有界的可行域通常是凸多边形(含边界时是闭的);某一侧没有限制时,可行域可以无界。
【例3】画出不等式组 ,,, 的平面区域,并求出所有顶点。
解:
、 是第一象限(含坐标轴)。 与两轴交于 、; 与两轴交于 、。
两条斜线的交点:由 与 相减得 ,再得 ,交点 。
可行域是凸四边形,顶点为 、、、。 不在 内(), 不在 内,都不是顶点。
【例4】若把上题的 改成 ,可行域怎样变?还有没有顶点 、?
解:
边界 改画虚线,这条边上的点都取不到。
、 落在这条直线上,不再属于可行域。区域变成“缺掉这条边”的开的一块,只剩下顶点 、。
记住:可行域是半平面的公共部分,顶点必须同时满足每一条约束,含等号的边界才能当顶点。
2.1 小结
本节抓住「不等式组与可行域」。几个二元一次不等式同时成立,解集是各半平面的公共部分,叫做这个不等式组的平面区域。对照例题把公式用一遍。
3 目标函数与最优解
在可行域上求线性函数 ( 是常数,不影响谁大谁小)的最大值或最小值,叫做简单线性规划。 叫做目标函数。使 取到最大或最小的可行解叫做最优解,对应的 叫做最优值。
把 改写成 (设 ),这是一簇平行直线,斜率相同,截距随 变。在图上平移这簇直线,看它即将离开可行域的那个位置: 在那里取到最大或最小。
3.1 最优解在顶点取到
定理(最优解在顶点取到)线性目标函数在凸多边形可行域(含边界)上的最大值、最小值,一定在某个顶点处取到。若目标函数的等值线与某条边平行,则这条边上每一点都是最优解,最优值相同。
证明:直观:等值线 是平行直线。平移时,与凸多边形的第一次、最后一次接触一定发生在顶点,或者贴着一整条边滑过。
因此实际做法是:先求出可行域的全部顶点,再把每个顶点代入目标函数,比较大小。这比在图上平移更稳,也方便检查。
【例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. ,,; 最大。最优 ,。
