简单的线性规划问题

来自：查字典高考网 2009-08-31

简单的线性规划问题

　近年来，各级各类数学竞赛中频频出现线性规划问题。所谓线性规划，是指求线性函数在线性(不等式或等式)约束下达最(小或大)值的问题。线性规划广泛应用于工农业、军事、交通运输、决策管理与规划、科学实验等领域。本文拟通过竞赛试题介绍常用的解题思路和方法。

一、运用数量关系解题　

　例1某家电生产企业根据市场调查分析，决定调整产品生产方案，准备每周(按120个工时计算)生产空调器、彩电、冰箱共360台，且冰箱至少生产60台。已知生产这些家电产品每台所需工时和每台产值如下表：

简单的线性规划问题2

问每周应生产空调器、彩电、冰箱各多少台，才能使产值最高？最高产值是多少(以千元为单位)？

(1997，第十二届江苏省初中数学竞赛)

解：设每周生产空调器、彩电、冰箱分别为x台、y台、z台，每周产值为f元，则

f=4x+3y+2z.

其中x、y、z满足

简单的线性规划问题3

由①、②得y=3603x，z=2x.

则由

简单的线性规划问题4

得30120.

故f=3(x+y+z)+xz=1080x.

当x=30时，fmax=108030=1050.

从而，y=270，z=60.

即每周生产空调器30台，彩电270台，冰箱60台，才能使产值最高，最高产值为1050千元。

二、运用图表作业解题　

　例2A市、B市和C市分别有某种机器10台、10台和8台。现在决定把这些机器支援给D市18台、E市10台。已知从A市调运一台机器到D市、E市的运费分别为200元和800元；从B市调运一台机器到D市、E市的运费分别为300元和700元；从C市调运一台机器到D市、E市的运费分别为400元和500元。

⑴设从A市、B市各调x台机器到D市,当28台机器全部调运完毕后,求总运费W(元)关于x(台)的函数式,并求W的最小值和最大值；

⑵设从A市调x台到D市，B市调y台到D市，当28台机器全部调运完毕后，用x、y表示总运费W(元)，并求W的最小值和最大值。

(1998，全国初中数学竞赛)

解：⑴⑵这两问都可以运用数量关系解题，具体解法参见《中等数学》1998年第3期第34页或1999年第4期第3页文。

下面以第⑵问为例说明运用图表作业解题。

⑵(表上作业法)

由题意，易得W(x，y)=17200500x300y.

Ⅰ.求最小总运费Wmin.

表中对于D市、E市可供货的A、B、C三地进行比较，逐次选取较小运费地，尽可能的调运，得调运方案如表1所示：

简单的线性规划问题5

即当x=10，y=8时，最小总运费Wmin=9800(元)。

Ⅱ.求最大总运费Wmax.

类似地，可得调运方案如表2所示：

简单的线性规划问题6

即当x=0，y=10时，最大总运费Wmax=14200(元)。

(图上作业法)

由题意，易得W(x，y)=17200500x300y.

Ⅰ.求最小总运费Wmin.

图中所标运费可以看作是单位运量。供量用正数表示，需量则用负数表示，对于D市、E市可供货的A、B、C三地进行比较，逐次选取单位运量较小的，尽可能的调运，得调运方案如图1所示：

简单的线性规划问题7

即当x=10，y=8时，最小总运费Wmin=9800(元)。

Ⅱ.求最大总运费Wmax.

类似地，可得调运方案如图2所示：

简单的线性规划问题8

即当x=0，y=10时，最大总运费Wmax=14200(元)。

三、运用图象性质解题

　例3某工厂制造A、B两种产品，制造产品A每吨需用煤9吨，电力4千瓦，3个工作日；制造产品B每吨需用煤5吨，电力5千瓦，10个工作日。已知制造产品A和B每吨分别获利7千元和12千元，现在该厂由于条件限制，只有煤360吨，电力200千瓦，工作日300个可以利用，问A、B两种产品各应生产多少吨才能获利最大？最大利润是多少？

解：设A、B两种产品分别生产x吨、y吨，利润为f千元，则

f=7x+12y.

其中x、y满足

简单的线性规划问题9

如图3所示，阴影部分即为这个线性规划问题的可行区域。

简单的线性规划问题10

∵4/57/123/10，

平行直线系f=7x+12y过点A(20，24)即当x=20，y=24时，fmax=720+1224=140+288=428(千元)。

即产品A生产20吨，产品B生产24吨，获利最大，最大利润为428千元。

四、运用枚举验证解题

　例4某人有楼房一幢，室内面积共180m2，拟分隔成两类房间作为旅游客房。大房间每间面积为18m2，可住游客5名，每名游客每天住宿费为40元；小房间每间面积为15m2，可住游客3名，每名游客每天住宿费为50元；装修大房间每间需1000元，装修小房间每间需600元。如果他只能筹款8000元用于装修，且游客能住满客房，他应隔出大房间和小房间各多少间，能获得最大收益？最大收益是多少？

解：设隔出大、小房间分别为x间、y间，收益为f元，则

f=200x+150y.

其中x、y满足

简单的线性规划问题11

如图4所示，由图解法易得f=200x+150y过点A(23/7，63/7)时，目标函数f取得最大值。

简单的线性规划问题12

但x、y必须是整数，还需在可行区域内找出使目标函数f取得最大值的整点。

显然目标函数f取得最大值的整点一定是分布在可行区域的右上侧，则利用枚举法即可求出整点最优解。

这些整点有：(0，12)，(1，10)，(2，9)，(3，8)，(4，6)，(5，5)，(6，3)，(7，1)，(8，0)，分别代入f=200x+150y，逐一验证，可得取整点(0，12)或(3，8)时，fmax=2000+15012=2003+1508=1800(元)。

所以要获得最大收益，有两种方案：

Ⅰ.只隔出小房间12间；

Ⅱ.隔出大房间3间，小房间8间。

最大收益为1800元。

练习题

1.20个农场职工种50公顷田地，这些地可以种蔬菜、棉花或水稻，如果种这些农作物每公顷所需的职工和预计的产值如下：

简单的线性规划问题13

问怎样安排，才能使每公顷地都种上作物，所有职工都工作，而且农作物的预计总产值达到最高？最高预计总产值是多少？

2.今年甲、乙两矿生产相同的矿石，甲、乙每月的产量分别为10万吨和8万吨；又有A、B两工厂每月分别需要矿石6万吨和12万吨。已知甲、乙与A、B的距离由图5标出(单位：千米)，问怎样调运才能使总运输量(单位：万吨千米)最小？最小总运输量是多少？怎样调运总运输量最大？最大总运输量是多少？

简单的线性规划问题14

3.某公司在A、B两地分别有库存机器16台、12台，现要运往甲、乙两地，其中甲地15台，乙地13台。已知从A地运一台机器到甲地的运费为500元，到乙地的运费为400元；从B地运一台机器到甲地的运费为300元，到乙地的运费为600元。问应设计怎样的调运方案，才能使这些机器的总运费最省？此时总运费是多少？

4.甲、乙两个粮库要向A、B两镇运送大米，已知甲库可调出100吨大米，乙库可调出80吨大米，A镇需70吨大米，B镇需110吨大米。两库到两镇的路程和运费如下表：

	路程(千米)		运费(元/吨千米)
	甲库	乙库	甲库	乙库
A镇	20	15	12	12
B镇	25	20	10	8

问：⑴这两个粮库各运往A、B两镇多少吨大米，才能使总运费最省？此时总运费是多少？

⑵最不合理的调运方案是什么？它使国家造成不该有的损失是多少？

5.两个电脑仓库供应三所学校电脑，甲仓库有12台，乙仓库有20台；A校需9台，B校需15台，C校需8台。已知甲仓库到A、B、C三校的距离依次为10公里、5公里、6公里；乙仓库到A、B、C三校的距离依次为4公里、8公里、15公里。若每台每公里的运费为常数a元，则甲仓库供应给A校、B校、C校各多少台，使总运输费用最省？

(1998，上海市初中数学竞赛)

6.某两个煤厂A1、A2每月进煤数量分别为60吨和100吨，联合供应3个居民区B1、B2、B3.3个居民区每月对煤的需求量依次分别为50吨、70吨、40吨，煤厂A1离3个居民区B1、B2、B3的距离依次分别为10千米、5千米、6千米，煤厂A2离3个居民区B1、B2、B3的距离依次分别为4千米、8千米、12千米。问如何分配供煤量使得运输量(单位：吨千米)达到最小？最小运输量是多少?

7.某厂拟生产甲、乙两种适销产品，每件销售收入分别为3、2千元/件。甲、乙产品都要在A、B两种设备上加工，所需工时甲在A、B两种设备上分别为1、2台时/件，乙在A、B设备上分别为2、1台时/件。A、B设备每月有效可使用台时数分别为400、500。如何安排生产，使产品销售总收入最大？最大总收入是多少?

(1999，上海市第八届中学生数学知识应用竞赛初赛)

8.某工厂在计划内要安排生产Ⅰ、Ⅱ两种产品，生产每件产品所需机时、工时、获利情况如下表，在不超过总机时100和总工时120的条件下，应如何安排生产使获利最大？最大利润是多少？

	机时	工时	获利(千元)
Ⅰ	2	4	6
Ⅱ	3	2	4

9.投资生产A产品时，每生产一百吨需资金200万元，需场地200m2，可获利润300万元；投资生产B产品时，每生产一百米需要资金300万元，需要场地100m2，可获利润200万元，现某单位可使用资金1400万元，场地900m2，问应作怎样的组合投资，可使所获利润最多？最大利润是多少?

(1998，上海市第七届中学生数学知识应用竞赛初赛)

10.某钢厂用A原料2吨和B原料4吨可产出1吨甲种钢管；用A原料5吨和B原料3吨可产出1吨乙种钢管。这两种钢管在北京、上海、广州三地销售所得单位利润（单位：万元/吨）如下表所示：

	销售甲种钢管的单位利润（万元/吨）	销售乙种钢管的单位利润（万元/吨）
北京	2	6
上海	3	4
广州	4	2

现根据市场供求信息：A、B原料的周供应量分别是10吨、12吨；每周甲种钢管生产不能超过2.5吨，乙种钢管生产不能超过1.5吨，且只能将全部钢管销往同一地方。问这两种钢管分别生产多少吨，销往何地，才能使一周的总利润最大？最大总利润是多少？

(《中等数学》1999年第3期，数学奥林匹克初中训练题38)

11.某运输公司有7辆载重量为6吨的A型卡车与4辆载重量为10吨的B型卡车，有9名驾驶员，在建筑某段高速公路中，此公司承包了每天至少搬运360吨沥青的任务，已知每辆卡车每天往返的次数为A型车8次，B型车6次，每辆卡车每天往返的成本费为A型车160元，B型车252元，每天派出A型车与B型车各多少辆，公司所花的成本费最低？最低成本费是多少?

答案与提示

1.种蔬菜30公顷，不种棉花，种水稻20公顷，预计总产值最高，最高预计总产值为450000元。

2.⑴甲矿不运给A厂，运给B厂10万吨；乙矿运给A厂6万吨，运给B厂2万吨时，总运输量最小，最小总运输量为164万吨千米。

⑵甲矿运给A厂6万吨，运给B厂4万吨；乙矿不运给A厂，运给B厂8万吨时，总运输量最大，最大总运输量为176万吨千米。

3.从A地调往甲地3台，乙地13台；从B地调往甲地12台，乙地0台，可使总运费最省，此时总运费为10300元。

4.⑴甲库运往A镇70吨，运往B镇30吨；乙库不运往A镇，运往B镇80吨时，总运费最省，总运费为37100元；

⑵甲库不运往A镇，运往B镇100吨；乙库运往A镇70吨，运往B镇10吨时最不合理，此时总运费最多，总运费为39200元，使国家造成不该有的损失为2100元。

5.甲仓库供应给A校0台，B校4台，C校8台。

6.A1不运往B1，运往B220吨，运往B340吨；A2运往B150吨，运往B250吨，不运往B3，可使运输量最小，最小运输量为940吨千米。

7.生产甲种产品200件，乙种产品100件，使产品销售收入最大，最大销售总收入为800千元。

8.生产第Ⅰ种产品20件，第Ⅱ种产品20件获利最大，最大利润是200千元。

9.A产品生产13/4百吨，B产品生产3/2百米时，可使所获利润最多，最大利润是1475万元。