线性规划常见题型及解法

线性规划常见题型及解法

线性规划是新教材中新增的内容之一，由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。

一、求线性目标函数的取值范围

⎧x ≤2⎪

例1、 若x 、y 满足约束条件⎨y ≤2 ，则z=x+2y的取值范围是 （ ）

⎪x +y ≥2⎩

A 、[2,6] B 、[2,5] C 、[3,6] D 、（3,5]

解：如图，作出可行域，作直线l ：x+2y＝0，将

l 向右上方平移，过点A （2,0）时，有最小值 2，过点B （2,2）时，有最大值6，故选A

二、求可行域的面积

⎧2x +y -6≥0⎪

例2、不等式组⎨x +y -3≤0表示的平面区域的面积为 （ ）

⎪y ≤2⎩

A 、4 B 、1 C 、5 D 、无穷大

解：如图，作出可行域，△ABC 的面积即为所求，由梯形OMBC

的面积减去梯形OMAC 的面积即可，选B

三、求可行域中整点个数

例3、满足|x|＋|y|≤2的点（x ，y ）中整点（横纵坐标都是整数）有（ ）

A 、9个 B 、10个 C 、13个 D 、14个

⎧x +y ≤2⎪x -y ≤2⎪

解：|x|＋|y|≤2等价于⎨

⎪-x +y ≤2⎪⎩-x -y ≤2

(x ≥0, y ≥0)

(x ≥0, y 0)

(x 0, y ≥0) (x 0, y 0)

作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选D

四、求线性目标函数中参数的取值范围

⎧x +y ≥5⎪

例4、已知x 、y 满足以下约束条件⎨x -y +5≤0 ，使z=x+ay(a>0)

⎪x ≤3⎩

取得最小值的最优解有无数个，则a 的值为 （ ） A 、－3 B 、3 C 、－1 D 、1

解：如图，作出可行域，作直线l ：x+ay＝0，要使目标函数

z=x+ay(a>0)取得最小值的最优解有无数个，则将l 向右上方平移后与直线x+y＝5重合，故a=1，选D

五、求非线性目标函数的最值

⎧2x +y -2≥0⎪

例5、已知x 、y 满足以下约束条件⎨x -2y +4≥0 ，则z=x2+y2的最大值和最小值分别是

⎪3x -y -3≤0⎩

（ ）

A 、13，1 B 、13，2

C 、13，

4 D

、

， 55

2

2

解：如图，作出可行域,x +y是点（x ，y ）到原

平方，故最大值为点A （2,3）到原点的距离的平|AO|2=13，最小值为原点到直线2x ＋y －2=0的距即为

点的距离的方，即离的平方，

4

，选C 5

六、求约束条件中参数的取值范围 例6、已知|2x－y ＋m|＜3表示的平面区域包含点（0,0）和（－1,1），则m 的取值范围是 （ ） A 、（-3,6） B 、（0,6） C 、（0,3） D 、（-3,3） 解：|2x－y ＋m|＜3等价于⎨

⎧2x -y +m +3>0

⎩2x -y +m -3

⎧m +3>3

由右图可知⎨ , 故0＜m ＜3，选C

m -3

线性规划的实际应用

在科学研究、工程设计、经济管理等方面，我们都会碰到最优化决策的实际问题，而解决这类问题的理论基础是线性规划。利用线性规划研究的问题，大致可归纳为两种类型：第一种类型是给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大，的效益最大，第二种类型是给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源量最小。

例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m 3，第二种有56m 3，假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示. 每生产一只圆桌可获利6元, 生产一个衣柜可获利10元.

⎧0. 18x +0. 09y ≤72⎪0. 08x +0. 28y ≤56⎪

解：设生产圆桌x 只, 生产衣柜y 个, 利润总额为z 元, 那么⎨ 而z =6x +10y .

⎪x ≥

0⎪⎩y ≥0

如上图所示, 作出以上不等式组所表示的平面区域, 即可行域.

作直线l :6x +10y =0,即l :3x +5y =0,把直线l 向右上方平移至l 1的位置时, 直线经过可行域上点M, 且与原点距离最大, 此时

⎧0. 18x +0. 09y =72

z =6x +10y 取最大值解方程组⎨, 得M 点坐标(350,100).答:应生产圆桌350只, 生产衣柜100个, 能使

0. 08x +0. 28y =56⎩

利润总额达到最大.

指出:资源数量一定, 如何安排使用它们, 使得效益最好, 这是线性规划中常见的问题之一

例2、某养鸡场有1万只鸡, 用动物饲料和谷物饲料混合喂养. 每天每只鸡平均吃混合饲料0.5kg, 其中动物饲料不能少于谷物饲料的

1

. 动物饲料每千克0.9元, 谷物饲料每千克0.28元, 饲料公司每周仅保证供应谷物饲料50000kg , 问饲5

料怎样混合, 才使成本最低.

⎧x +y ≥35000⎪1⎪y ≥x ⎪

解:设每周需用谷物饲料x kg , 动物饲料y kg , 每周总的饲料费用为z 元, 那么 ⎨, 而5

⎪0≤x ≤50000⎪⎪⎩y ≥0

z =0.28x +0.9y

如下图所示, 作出以上不等式组所表示的平面区域, 即可行域.

作一组平行直线0.28x +0.9y =t , 其中经过可行域内的点且和原点最近的直线, 经过直线x +y =35000和直线y =的交点A (

1x 5

[***********]00

, ) , 即x =, y =时, 饲料费用最低. 3333

所以, 谷物饲料和动物饲料应按5:1的比例混合, 此时成本最低.

指出:要完成一项确定的任务, 如何统筹安排, 尽量做到用最少的资源去完成它, 这是线性规划中最常见的问题之一

.

(例3图) (例4图)

例3

营养师想购这三种食物共10千克, 使之所含维生素A 不少于4400单位, 维生素B 不少于4800单位, 问三种食物各购多少时, 成本最低? 最低成本是多少?

解:设所购甲、乙两种食物分别为x 千克、y 千克, 则丙种食物为(10-x -y ) 千克. x 、y 应满足线性条件为

⎧400x +600y +400(10-x -y ) ≥4400⎧y ≥2

, 化简得⎨ ⎨

800x +200y +400(10-x -y ) ≥48002x -y ≥4⎩⎩

作出可行域如上图中阴影部分

目标函数为z =7x +6y +5(10-x -y )=2x +y +50,令m =2x +y , 作直线l :2x +y =0,则直线2x +y =m 经过可行域中A(3,2)时, m 最小, 即m min =2⨯3+2=8，∴z min =m min +50=58答: 甲、乙、丙三种食物各购3千克、2千克、5千克时成本最低, 最低成本为58元.

⎧y ≥2

指出:本题可以不用图解法来解, 比如, 由⎨得

2x -y ≥4⎩

z =2x +y +50=(2x -y )+2y +50≥4+2⨯2+50=58,当且仅当y =2,x =3时取等号

总结：(1)设出决策变量, 找出线性规划的约束条件和线性目标函数;

(2)利用图象, 在线性约束条件下找出决策变量, 使线性目标函数达到最大(或最小).

⎧a 11x 1+a 12x 2+ +a 1m x m ≤b 1⎪a x +a x + +a x ≤b ⎪2112222m m 2

2. 线性规划问题的一般数学模型是:已知⎨(这n 个式子中的“≤”也可以是“≥”或

⎪⎪⎩a n 1x 1+a n 2x 2+ +a nm x m ≤b n

“=”号)

其中a ij (i =1,2,„, n , j =1,2,„, m ), b i (i =1,2,„, n ) 都是常量, x j (j =1,2,„, m ) 是非负变量, 求z =c 1x 1+c 2x 2+„+c m x m 的最大值或最小值, 这里c j (j =1,2,„, m ) 是常量.

(3)线性规划的理论和方法主要在以下两类问题中得到应用:一是在人力、物力资金等资源一定的条件下, 如何使用它们来完成最多的任务；二是给一项任务, 如何合理安排和规划, 能以最少的人力、物力、资金等资源来完成该项任务.

线性规划中整点最优解的求解策略

在工程设计、经营管理等活动中，经常会碰到最优化决策的实际问题，而解决此类问题一般以线性规划为其重要的理论基础。然而在实际问题中，最优解 (x,y) 通常要满足x,y ∈N ，这种最优解称为整点最优解，下面通过具体例子谈谈如何求整点最优解 .

1．平移找解法

作出可行域后，先打网格，描出整点，然后平移直线l ，直线l 最先经过或最后经过的那个整点便是整点最优解. 例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m 3，第二种有56m 3，假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示. 每生产一只圆桌可获利6元, 生产一个衣柜可获利10元. 木器厂在现有木料条件下, 圆桌和衣柜各生产多少, 才使获得利润最

⎧0. 18x +0. 09y ≤72⎪0. 08x +0. 28y ≤56⎪

解：设生产圆桌x 只, 生产衣柜y 个, 利润总额为z 元, 那么⎨ 而z =6x +10y . 如图所示, 作出

x ≥0⎪⎪⎩y ≥0

以上不等式组所表示的平面区域, 即可行域.

作直线l :6x +10y =0,即l :3x +5y =0,把直线l 向右上方平移至l 1的位置时, 直线经过可行域上点M, 且与原点距离最大,

⎧0. 18x +0. 09y =72

此时z =6x +10y 取最大值。解方程组⎨, 得M 点坐标(350,100).答：应生产圆桌350只, 生产衣柜100

0. 08x +0. 28y =56⎩

个, 能使利润总额达到最大. 点评：本题的最优点恰为直线0.18x +0.09y =72和0.08x +0.28y =56的交点M 。

例 2 有一批钢管，长度都是4000mm ，要截成500mm 和600mm 两种毛坯，且这两种毛坯按数量比不小于怎样截最合理？

解：设截500mm 的钢管x 根，600mm 的y 根，

1

配套，3

总数为z 根。根据题意，得

目标函数为

，

，

作出如图所示的可行域内的整点，

作一组平行直线x+y=t，经过可行域内的点且和原点距离最远的直线为过B （8，0）的直线，这时x+y=8.由于x,y 为正整数，知（8，0）不是最优解。显然要往下平移该直线，在可行域内找整点，使x+y=7，可知点（2，5），（3，4），（4，3），（5，2），（6，1）均为最优解．答：略．

点评：本题与上题的不同之处在于，直线x+y=t经过可行域内且和原点距离最远的点B （8，0）并不符合题意，此时必须往下平移该直线，在可行域内找整点，比如使x+y=7，从而求得最优解。

从这两例也可看到，平移找解法一般适用于其可行域是有限区域且整点个数又较少，但作图要求较高。 二、整点调整法

先按“平移找解法”求出非整点最优解及最优值，再借助不定方程的知识调整最优值，最后筛选出整点最优解．

y

l 1 2x -y -3>0⎧

例3．已知x , y 满足不等式组⎨2x +3y -6

⎪

⎪3x -5y -15

⎩

A

O

l 3

C

x , y ．

解：不等式组的解集为三直线l 1：2x -y -3=0，l 2：2x +3y -6=0，l 3：

x l

2

3x -5y -15=0所围成的三角形内部（不含边界），设l 1与l 2，l 1与l 3，l 2与l 3交

点分别为A , B , C ，则A , B , C 坐标分别为A (

1537512

, ) ，B (0,-3) ，C (, -) ， 841919

作一组平行线l ：x +y =t 平行于l 0：x +y =0，当l 往l 0右上方移动时，t 随之增大， ∴当l 过C 点时x +y 最大为

6375

，但不是整数解，又由0

1919

当x =1时，代入原不等式组得y =-2， ∴x +y =-1；当x =2时，得y =0或-1， ∴x +y =2或1；

⎧x =2⎧x =3

x =3当时，y =-1， ∴x +y =2，故x +y 的最大整数解为⎨或⎨．

y =-1y =0⎩⎩

3. 逐一检验法

由于作图有时有误差，有时仅有图象不一定就能准确而迅速地找到最优解，此时可将若干个可能解逐一校验即可见分晓．

例4 一批长4000mm 的条形钢材，需要将其截成长分别为518mm 与698mm 的甲、乙两种毛坯，求钢材的最大利用率．

解：设甲种毛坯截 x 根，乙种毛坯截 y 根，钢材的利用率为

P ，则

①，目标函数为

②，线性约束条件①表示的可行域是

图中阴影部分的整点．②表示与直线518x+698y=4000平行的直线系。所以使P 取得最大值的最优解是阴影内最靠近直线518x+698y=4000的整点坐标．如图看到(0，5) ，(1，4) ，(2，4) ，(3，3) ，(4，2) ，(5，2) ，(6，1) ，(7，0) 都有可能是最优解，将它们的坐标逐一代入②进行校验，可知当x=5,y=2时，

．

答：当甲种毛坯截5根，乙种毛坯截2根，钢材的利用率最大，为99.65%．

解线性规划问题的关键步骤是在图（可行域）上完成的，所以作图时应尽可能精确，图上操作尽可能规范，但考虑到作图时必然会有误差，假如图上的最优点并不十分明显易辨时，不妨将几个有可能是最优点的坐标都求出来，然后逐一进行校验，以确定整点最优解.

线性规划的实际应用 习题精选

1．某家俱公司生产甲、乙两种型号的组合柜，每种柜的制造白坯时间、油漆时间及有关数据如下：

问该公司如何安排这两种产品的生产，才能获得最大的利润．最大利润是多少？

2．要将两种大小不同的钢板截成A 、B 、C 三种规格，每张钢板可同时截得三种规格小钢板的块数如下：

每张钢板的面积，第一种为1m ，第二种为2m ，今需要A 、B 、C 三种规格的成品各12，15，17块，问各截这两种钢板多少张，可得所需三种规格成品，且使所用钢板面积最小．

2

3．某人承揽一项业务，需做文字标牌2个，绘画标牌3个，现有两种规格的原料，甲种规格每张3m ，可做文

2

字标牌1个，绘画标牌2个，乙种规格每张2m ，可做文字标牌2个，绘画标牌1个，求两种规格的原料各用多少张，才能使总的用料面积最小．

2

2

4．某蔬菜收购点租用车辆，将100吨新鲜黄瓜运往某市销售，可供租用的大卡车和农用车分别为10辆和20辆，若每辆卡车载重8吨，运费960元，每辆农用车载重2.5吨，运费360元，问两种车各租多少辆时，可全部运完黄瓜，且动费最低．并求出最低运费．

5．某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72立方米，第二种有56立方米，假设生产每种产品都需要两种木料．生产一只圆桌需用第一种木料0.18立方米，第二种木料0.08立方米，可获利润60元，生产一个衣柜需用第一种木料0.09立方米，第二种0.28立方米，可获利润100元，木器厂在现有木料情况下，圆桌和衣柜应各生产多少，才能使所获利润最多． 解答提示：

1．设x ，y 分别为甲、乙两种柜的日产量，

目标函数z=200x＋240y ， 线性约束条件：

作出可行域．

z最大=200×4＋240×8=2720

答：该公司安排甲、乙两种柜的日产量分别为4台和8台，可获最大利润2720元．

2．设需截第一种钢板x 张，第二种钢板y 张，所用钢板面积zm 2

．

目标函数z=x＋2y ， 线性约束条件：

作出可行域． 作一组平行直线x ＋2y=t．

的整点中，点(4，8) 使z 取得最小值．

答：应截第一种钢板4张，第二种钢板8张，能得所需三种规格的钢板，且使所用钢板的面积最小．

2

3．设用甲种规格原料x 张，乙种规格原料y 张，所用原料的总面积是zm ，目标函数z=3x＋2y ，

线性约束条件，

作出可行域．作一组平等直线3x ＋2y=t．

A不是整点，A 不是最优解．在可行域内的整点中，点B(1，1) 使z 取得最小值． z最小=3×1＋2×1=5，

2

答：用甲种规格的原料1张，乙种原料的原料1张，可使所用原料的总面积最小为5m ． 4．设租用大卡车x 辆，农用车y 辆，最低运费为z 元．z=960x＋360y ．

线性约束条件是：

作出可行域．

作直线960x ＋360y=0． 即8x ＋3y=0，向上平移至过点B(10，8) 时，z=960x＋360y 取到最小值． z最小=960×10＋360×8=12480

答：大卡车租10辆，农用车租8辆时运费最低，最低运费为12480元．

5．设圆桌和衣柜的生产件数分别为x 、y ，所获利润为z ，则z=6x＋10y ．

作出可行域．

时，z=6x＋10y 最大

即M(350，100) ．当直线6x ＋10y=0即3x ＋5y=0平移到经过点M(350，100)