http://vip.6to23.com/yunyan8 摘
线
性 规 划 模 型
一、问题的提出
在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财
力等资源，以便得到最好的经济效果。
例1 若需在长为4000mm的圆钢上 ，截出长为698mm和518mm两种毛坯，问怎样
截取才能使残料最少？
初步分析 可以先考虑两种“极端”的情况：
（1）全部截出长为698mm的甲件，一共可截出»5件，残料长为510mm。
（2）全部截出长为518mm的乙件，一共可截出»7件，残料长为374mm。
由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少？把截
取条件数学化地表示出来就是：
698 x + 518y £ 4000
x ，y都是非负整数
目标是使：z = （材料利用率）尽可能地接近或等于1。（尽可能地大）
该问题可用数学模型表示为：
目标函数 ： max z =
满足约束条件： 698 x + 518y £ 4000 ， (1)
x ，y都是非负整数 . (2)
例2 某工厂在计划期内要安排生产I 、II两种产品，已知生产单位产品所需的设备台
数及A、B两种原料的消耗，如下表所示。
|
|
I |
II |
|
|
设备 |
1 |
2 |
8台数 |
|
原材料A |
4 |
0 |
16kg |
|
原材料B |
0 |
4 |
12kg |
该工厂每生产一件产品I可获利 2 元，每生产一件产品II可获利 3 元，问应如何安排生产计划使工厂获利最多？
这问题可以用以下的数学模型来描述：设 x 1, x 2分别表示在计划期内产品I、II的产量。因为设备的有效台数为8 ，这是一个限制产量的条件，所以在确定I 、II的产量时，要考虑不超过设备的有效台数，即可用不等式表示为：
x 1 + 2x 2 £ 8 .
同理，因原材料A 、B的限量，可以得到以下不等式：
4 x 1 £ 16
4 x 2 £ 12.
该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x 1、x 2以得到最大的利润。若用 z 表示利润，这时z = 2x 1 + 3 x 2 。综上所述，该计划问题可用数学模型表示为：
目标函数 ： max z = 2x 1 + 3 x 2
满足约束条件： x 1 + 2x 2 £ 8
4 x 1 £ 16
4 x 2 £ 12.
x 1 ，x 2 ³ 0
该模型的特征是：
（1）有一组决策变量（x 1 ,x 2 ,…,x n)表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。
（2）存在一定的约束条件，这些约束条件可用一组线性等式（不等式）来表示。
（3）有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求实现目标函数最大化或最小化。
满足以上三个条件的数学模型称为线性规划模型。其一般形式为：
目标函数 ： max(min) z = c 1x 1 + c 2x 2 + …+ c nx n
a11x 1 + a12x 2 +….+ a13x
n £ (= , ³) b 1
a21x 1 + a22x 2 +…. + a23x
n £ (= , ³) b2
满足约束条件： … …
a m1x 1 + a m2x 2 +….+ a m3x
n £ (= , ³) b m
x 1 ,x 2 ,…, x n ³ 0
二、
穷举法
以例1为例介绍穷举法。
先根据（1）求出x 所有可能的取值为：0、1、2、3、4、5，再由（1）把相应y 的最
大值求出，对应为7、6、5、3、2、0，依此计算住z值如下表：
|
x |
0 |
1 |
2 |
3 |
4 |
5 |
|
y |
7 |
6 |
5 |
3 |
2 |
0 |
|
z |
90.65% |
95.15% |
99.65% |
91.20% |
95.70% |
87.25% |
由表可知，在一根圆钢上截取2个甲件和5个乙件，可以得到最高的材料利用率99.65%。
例2作为课后练习。
三、图解法
1、用二元一次不等式表示平面区域
y
y
y
y
o x o x o x o x
ax + by > c ax +by < c ax +by >c ax +by < c
a>0, b >0 a >0, b<0 a>0, b<0 a>0, b<0
2． 图解法
图解法简单直观，有助于了解线性规划问题求解的基本原理。现对例1进行图解。
条件（1）、（2）对应的恰好是图1中斜线下方和两条坐标轴在第一象限中的三角形AOB
内的整点（即横、纵坐标都是整数的点）。当整点越靠近直线AB，残料就越少（若AB恰好过其中一个整点，则该整点坐标所对应的截料方法一定是无残了的最佳截料方法）。比较C、D、E、F、G、H，知E（2，5）距直线AB最近，故知取x =2，y = 5是材料利用率最高的截料方法。
在以x1、x2为坐标轴的直角坐标系中，非负条件x1, x2 ³ 0 是指第一象限（及x轴正半轴、
y轴正半轴)。每一个约束条件都表示一个半平面。若约束条件 x 1 + 2x 2 £ 8 是代表以直线
x 1 + 2x 2 = 8为边界的左下方的半平面。
x2
4x1 = 16
若同时满足x 1 + 2x 2
£ 8，4 x 1
£ 16，
x 1 + 2x 2 = 8 4x 2=12
4 x 2 £ 12和x 1 ，x 2 ³ 0约束的点， Q4 Q3
必然在由这三个半平面围成的区域内。 3
Q2
由例1的所有约束条件为半平面围成 2
的区域见右图阴影部分。阴影区域中 1
的每一个点（包括边界点）都这个线
Q1
x1
性规划问题的解。 o
再分析目标函数max z = 2x 1 + 3 x 2，在这坐标平面上，它表示以 z为参数、– 为斜率的一族平行直线 ：
x 2 = – x1 +
位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x 2 = – x1 + 沿其法线方向（法线方向是指与直线垂直的方向）向上方移动。当移动到Q 2点时，使z值在可行域（阴影部分）边界上实现最大化，这就得到了例 1 的最优解Q2，Q2点的坐标为（4，2）。于是算得z =14。
这说明该厂的最优生产计划方案是：生产产品I 4件，生产产品更新换代II 2件，可得到最大利润为14元。
练习：
1．某厂生产甲、乙两种产品，生产甲种产品每件要消耗煤9吨，电力4千瓦，使用劳动力3个，获利70元；生产乙种产品每件要消耗煤4吨，电力5千瓦，使用劳动力10个，获利120元。有一个生产日，这个厂可动用的煤是360吨，电力是200千瓦，劳动力是300个，问应该如何安排甲、乙两种产品的生产，才能使工厂在当日的获利最大，并问该厂当日的最大获利是多少？（甲20件，乙24件，获利4280元）
2．电视台为某个广告公司特约播放两套片集。其中片集甲播映时间为20分钟，广告时间为1分钟，收视观众为60万，片集乙播映时间为10分钟，广告时间为1分钟，收视观众为20万。广告公司规定每周至少有6分钟广告，而电视台每周只能为该公司提供不多于80分钟的节目时间。电视台每周应播映两套片集各多少次，才能获得最高的收视率？
3．预测2000年奥运会男子铅球的成绩。（资料来源：1996-08-02《体育报》）
|
届次 |
成绩（米） |
届次 |
成绩（米） |
届次 |
成绩（米） |
|
7 |
14．81 |
15 |
17．41 |
21 |
21．05 |
|
8 |
14．955 |
16 |
18．57 |
22 |
21．35 |
|
9 |
15．87 |
17 |
19．68 |
23 |
21．26 |
|
10 |
16．005 |
18 |
20．33 |
24 |
22．47 |
|
11 |
16．20 |
19 |
20．54 |
25 |
21．70 |
|
14 |
17．12 |
20 |
21．18 |
26 |
？ |
4．预测2000年我国进出口总额。（资料来源：1994年《中国经济统计年鉴》及1997-1-2
《人民日报》）
|
年份 |
进出口总额 |
年份 |
进出口总额 |
年份 |
进出口总额 |
|
1981 |
4 |
1987 |
6．8 |
1993 |
19．6 |
|
1982 |
3．9 |
1988 |
7．9 |
1994 |
24 |
|
1983 |
4 |
1989 |
11．2 |
1995 |