线性规划常见题型及解法

线性规划常见题型及解法

由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下几种常见题型。

一、约束条件设计参数形式，考查目标函数最值范围问题。

?x?0例、在约束条件?下，当3?s?5时，目标函数 ?y?0??y?x?s??y?2x?4z?3x?2y的最大值的变化范围是（）

A.[6,15] B. [7,15] C. [6,8] D. [7,8] 解析：画出可行域如图3所示,当3?s?4时, 目标函数

z?3x?2y在B(4?s,2s?4)处取得最大值, 即zmax?3(4?s)?2(2s?4)?s?4?[7,8);当4?s?5时, 目标函数 z?3x?2yC

zmaxE(0,处取得最大值,即

?3?0?2?4?8,故z?[7,8],从而选D;

在点

点评：本题设计有新意，作出可行域，寻求最优解条件，然后转化为目标函数Z关于S的函 关系是求解的关键。

二、已知最优解成立条件，探求目标函数参数范围问题。

?1?x?y?4。若目标函数

??2?x?y?2a?0）仅在点(3,1处)取得最大值，则a的取值范围解析：如图5作出可行域，由z?ax?y?y??ax?z其表示为ｚ的平行直线系, 要使目标函数z?ax?y（其中a?0）仅在点则直线y??ax?z过Ａ点且在直线x?y?4,x?3（不含界线）?a??1?a?1.则a的取值范围为(1,??)。

5已知变量x，y满足约束条件?z?ax?y（其中

为 。 斜率为?a，纵截距为

(3,1)处取得最大值。

之

间

。

即

点评：本题通过作出可行域，在挖掘?a与z的几何意义的条件下，借助用数形结合利用各直线间的斜率变化关系，建立满足题设条件的a的不等式组即可求解。求解本题需要较强的基本功，同时对几何动态问题的能力要求较高。

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

?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

y 2 O 2 B y =2 x x + y =2 A x=2 四、求可行域的面积

1

?2x?y?6?0?例2、不等式组?x?y?3?0表示的平面区域的面积为 （ ）

?y?2? A、4 B、1 C、5 D、无穷大

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

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

y x＋y – 3 = 0 M A O B y =2 五、求可行域中整点个数

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

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

C x 2x + y – 6= 0 = 5 ?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)y 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选D

O x 六、求线性目标函数中参数的取值范围

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

?x?3?y x + y = 5 x – y + 5 = 0 取得最小值的最优解有无数个，则a的值为 （ ） A、－3 B、3 C、－1 D、1 O x=3 x 解：如图，作出可行域，作直线l：x+ay＝0，要使目标函数

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

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

?2x?y?2?0?22

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

?3x?y?3?0? A、13，1 B、13，2

y A 425C、13， D、13， 55

22

解：如图，作出可行域,x+y是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即

2

O x – 2y + 4 = 0 3x – y – 3 = 0 x 2x + y - 2= 0 = 5 |AO|=13，最小值为原点到直线2x＋y－2=0的距离的平方，即为

2

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）

y

2x – y + 3 = 0 2x – y = 0 解：|2x－y＋m|＜3等价于??2x?y?m?3?0

?2x?y?m?3?0O 由右图可知??m?3?3 ,故0＜m＜3，选C

?m?3?0九·比值问题

当目标函数形如z?y?a时,可把z看作是动点P(x,y)与定点Q(b,a)连线的斜率，这样目标函数的最值就转化x?b为PQ连线斜率的最值。

??x－y＋2≤0，y例 7 已知变量x，y满足约束条件?x≥1，则 的取值范围是（ ）.

?x＋y－7≤0，x?

99

（A）[，6] （B）（－∞，]∪[6，＋∞）

55（C）（－∞，3]∪[6，＋∞） （D）[3，6] 解析 是可行域内的点M（x，y）与原点O 59y（0，0）连线的斜率，当直线OM过点（，）时，取得

22x9y最小值；当直线OM过点（1，6）时，取得最大值6. 答案A

5x

十、求可行域中整点个数

例8、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（ ） A、9个 B、10个 C、13个 D、14个

yx?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)y 作出可行域如右图，是正方形内部（包括边界），容易得到整

x O 点个数为13个，选D

线性规划的实际应用

在科学研究、工程设计、经济管理等方面，我们都会碰到最优化决策的实际问题，而解决这类问题的理论基础是线性规划。利用线性规划研究的问题，大致

可归纳为两种类型：第一种类型是给定一定数量的人力、物力资源，问怎样安排运用这些资源，能使完成的任务量

3

最大，的效益最大，第二种类型是给定一项任务，问怎样统筹安排，能使完成这项任务的人力、物力资源量最小。

例1、某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有56m3，假设生产每种产品都需要用两种木料，生产一只圆桌和一个衣柜分别所需木料如下表所示.每生产一只圆桌可获利6元,生产一个衣柜可获利10元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多? 产 品 圆 桌 衣 柜 木料(单位m3) 0.18 0.09 第 一 种 0.08 0.28 第 二 种 ?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向右上方平移至l1的位置时,直线经过可行域上点M,且与原点距离最大,此时

?0.18x?0.09y?72z=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?0z=0.28x+0.9y

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

作一组平行直线0.28x+0.9y =t,其中经过可行域内的点且和原点最近的直线,经过直线x+y=35000和直线y?的交点A(1x587500175008750017500,),即x?,y?时,饲料费用最低. 3333所以,谷物饲料和动物饲料应按5:1的比例混合,此时成本最低.

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

4

(例3图) (例4图)

例3、下表给出甲、乙、丙三种食物的维生素A、B的含量及成本: 维生素A(单位/千克) 维生素B(单位/千克) 成本(元/千克) 甲 400 800 7 乙 600 200 6 丙 400 400 5 营养师想购这三种食物共10千克,使之所含维生素A不少于4400单位,维生素B不少于4800单位,问三种食物各购多少时,成本最低?最低成本是多少?

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

?400x?600y?400(10?x?y)?4400?y?2 ,化简得 ??2x?y?4800x?200y?400(10?x?y)?4800??作出可行域如上图中阴影部分

目标函数为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元.

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

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

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

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

?a11x1?a12x2???a1mxm?b1?ax?ax???ax?b?2112222mm22.线性规划问题的一般数学模型是:已知?(这n个式子中的“?”也可以是“?”或

?????an1x1?an2x2???anmxm?bn“=”号)

其中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最先经过或最后经过的那个整点便是整点最优解. 例

5

本文来源：https://www.bwwdw.com/article/uo5v.html