线性规划常见题型及解法Word格式.doc
《线性规划常见题型及解法Word格式.doc》由会员分享，可在线阅读，更多相关《线性规划常见题型及解法Word格式.doc（9页珍藏版）》请在冰点文库上搜索。
x＋y–3=0
C
M
例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等价于
作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选D
四、求线性目标函数中参数的取值范围
x+y=5
x–y+5=0
x=3
例4、已知x、y满足以下约束条件 ，使z=x+ay（a>
0）取得最小值的最优解有无数个，则a的值为 （ ）
A、－3 B、3 C、－1 D、1
x+ay＝0，要使目标函数z=x+ay（a>
0）取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故a=1，选D
五、求非线性目标函数的最值
2x+y-2=0=5
x–2y+4=0
3x–y–3=0
例5、已知x、y满足以下约束条件 ，则z=x2+y2的最大值和最小值分别是 （ ）
A、13，1 B、13，2
C、13， D、，
如图，作出可行域,x2+y2是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x＋y－2=0的距离的平方，即为，选C
六、求约束条件中参数的取值范围
2x–y=0
2x–y+3=0
例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等价于
由右图可知,故0＜m＜3，选C
线性规划的实际应用
在科学研究、工程设计、经济管理等方面，我们都会碰到最优化决策的实际问题，而解决这类问题的理论基础是线性规划。
利用线性规划研究的问题，大致可归纳为两种类型：
第一种类型是给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量最大，的效益最大，第二种类型是给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源量最小。
例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有56m3，假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产一个衣柜可获利10元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?
产品
木料（单位m3）
第一种
第二种
圆桌
0.18
0.08
衣柜
0.09
0.28
设生产圆桌x只,生产衣柜y个,利润总额为z元,那么而z=6x+10y.
如上图所示,作出以上不等式组所表示的平面区域,即可行域.
作直线l:
6x+10y=0,即l:
3x+5y=0,把直线l向右上方平移至l1的位置时,直线经过可行域上点M,且与原点距离最大,此时z=6x+10y取最大值解方程组,得M点坐标（350,100）.答:
应生产圆桌350只,生产衣柜100个,能使利润总额达到最大.
指出:
资源数量一定,如何安排使用它们,使得效益最好,这是线性规划中常见的问题之一
例2、某养鸡场有1万只鸡,用动物饲料和谷物饲料混合喂养.每天每只鸡平均吃混合饲料0.5kg,其中动物饲料不能少于谷物饲料的.动物饲料每千克0.9元,谷物饲料每千克0.28元,饲料公司每周仅保证供应谷物饲料50000kg,问饲料怎样混合,才使成本最低.
解:
设每周需用谷物饲料xkg,动物饲料ykg,每周总的饲料费用为z元,那么,而z=0.28x+0.9y
如下图所示,作出以上不等式组所表示的平面区域,即可行域.
作一组平行直线0.28x+0.9y=t,其中经过可行域内的点且和原点最近的直线,经过直线x+y=35000和直线的交点,即,时,饲料费用最低.
所以,谷物饲料和动物饲料应按5:
1的比例混合,此时成本最低.
要完成一项确定的任务,如何统筹安排,尽量做到用最少的资源去完成它,这是线性规划中最常见的问题之一.
（例3图）（例4图）
例3、下表给出甲、乙、丙三种食物的维生素A、B的含量及成本:
甲
乙
丙
维生素A（单位/千克）
维生素B（单位/千克）
成本（元/千克）
400
800
7
600
200
6
5
营养师想购这三种食物共10千克,使之所含维生素A不少于4400单位,维生素B不少于4800单位,问三种食物各购多少时,成本最低?
最低成本是多少?
设所购甲、乙两种食物分别为x千克、y千克,则丙种食物为（10-x-y）千克.x、y应满足线性条件为
化简得
作出可行域如上图中阴影部分
目标函数为z=7x+6y+5（10-x-y）=2x+y+50,令m=2x+y,作直线l:
2x+y=0,则直线2x+y=m经过可行域中A（3,2）时,m最小,即mmin=2´
3+2=8，∴zmin=mmin+50=58答:
甲、乙、丙三种食物各购3千克、2千克、5千克时成本最低,最低成本为58元.
本题可以不用图解法来解,比如,由得
z=2x+y+50=（2x-y）+2y+50³
4+2´
2+50=58,当且仅当y=2,x=3时取等号
总结：
（1）设出决策变量,找出线性规划的约束条件和线性目标函数;
（2）利用图象,在线性约束条件下找出决策变量,使线性目标函数达到最大（或最小）.
2.线性规划问题的一般数学模型是:
已知（这个式子中的“£
”也可以是“³
”或“=”号）
其中aij（i=1,2,…,n,j=1,2,…,m）,bi（i=1,2,…,n）都是常量,xj（j=1,2,…,m）是非负变量,求z=c1x1+c2x2+…+cmxm的最大值或最小值,这里cj（j=1,2,…,m）是常量.
（3）线性规划的理论和方法主要在以下两类问题中得到应用:
一是在人力、物力资金等资源一定的条件下,如何使用它们来完成最多的任务；
二是给一项任务,如何合理安排和规划,能以最少的人力、物力、资金等资源来完成该项任务.
线性规划中整点最优解的求解策略
在工程设计、经营管理等活动中，经常会碰到最优化决策的实际问题，而解决此类问题一般以线性规划为其重要的理论基础。
然而在实际问题中，最优解（x,y）通常要满足x,y∈N，这种最优解称为整点最优解，下面通过具体例子谈谈如何求整点最优解.
1．平移找解法
作出可行域后，先打网格，描出整点，然后平移直线l，直线l最先经过或最后经过的那个整点便是整点最优解.
例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有56m3，假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产一个衣柜可获利10元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?
设生产圆桌x只,生产衣柜y个,利润总额为z元,那么而z=6x+10y.如图所示,作出以上不等式组所表示的平面区域,即可行域.
3x+5y=0,把直线l向右上方平移至l1的位置时,直线经过可行域上点M,且与原点距离最大,此时z=6x+10y取最大值。
解方程组,得M点坐标（350,100）.答：
应生产圆桌350只,生产衣柜100个,能使利润总额达到最大.点评：
本题的最优点恰为直线0.18x+0.09y=72和0.08x+0.28y=56的交点M。
例2有一批钢管，长度都是4000mm，要截成500mm和600mm两种毛坯，且这两种毛坯按数量比不小于配套，怎样截最合理？
设截500mm的钢管x根，600mm的y根，总数为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，从而求得最优解。
从这两例也可看到，平移找解法一般适用于其可行域是有限区域且整点个数又较少，但作图要求较高。
二、整点调整法
先按“平移找解法”求出非整点最优解及最优值，再借助不定方程的知识调整最优值，最后筛选出整点最优解．
例3．已知满足不等式组，求使取最大值的整数．
不等式组的解集为三直线：
，：
所围成的三角形内部（不含边界），设与，与，与交点分别为，则坐标分别为，，，
作一组平行线：
平行于：
，当往右上方移动时，随之增大，
∴当过点时最大为，但不是整数解，又由知可取，
当时，代入原不等式组得，∴；
当时，得或，∴或；
当时，，∴，故的最大整数解为或．
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三种规格，每张钢板可同时截得三种规格小钢板的块数如下：
每张钢板的面积，第一种为1m2，第二种为2m2，今需要A、B、C三种规格的成品各12，15，17块，问各截这两种钢板多少张，可得所需三种规格成品，且使所用钢板面积最小．
3．某人承揽一项业务，需做文字标牌2个，绘画标牌3个，现有两种规格的原料，甲种规格每张3m2，可做文字标牌1个，绘画标牌2个，乙种规格每张2m2，可做文字标牌2个，绘画标牌1个，求两种规格的原料各用多少张，才能使总的用料面积最小．
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张，所用钢板面积zm2．
目标函数z=x＋2y， 线性约束条件：
作出可行域． 作一组平行直线x＋2y=t．
的整点中，点（4，8）使z取得最小值．
应截第一种钢板4张，第二种钢板8张，能得所需三种规格的钢板，且使所用钢板的面积最小．
3．设用甲种规格原料x张，乙种规格原料y张，所用原料的总面积是zm2，目标函数z=3x＋2y，
线性约束条件，
作出可行域．作一组平等直线3x＋2y=t．
A不是整点，A不是最优解．在可行域内的整点中，点B（1，1）使z取得最小值． z最小=3×
1＋2×
1=5，
用甲种规格的原料1张，乙种原料的原料1张，可使所用原料的总面积最小为5m2．
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．
作出可行域．
即M（350，100）．当直线6x＋10y=0即3x＋5y=0平移到经过点M（350，100）时，z=6x＋10y最大
9
升级会员 