一、问题的提出
在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财
力等资源，以便得到最好的经济效果。
例1 若需在长为4000mm的圆钢上 ，截出长为698mm和518mm两种毛坯，问怎样
截取才能使残料最少？
初步分析 可以先考虑两种“极端”的情况：
（1）全部截出长为698mm的甲件，一共可截出 EQ F(4000,698) »5件，残料长为510mm。
（2）全部截出长为518mm的乙件，一共可截出 EQ F(4000,518) »7件，残料长为374mm。
由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少？把截
取条件数学化地表示出来就是：
698x + 518y £ 4000
x，y都是非负整数
目标是使：z = EQ F(698x + 518y,4000) （材料利用率）尽可能地接近或等于1。（尽可能地大）
该问题可用数学模型表示为：
目标函数 ： max z =EQ F(698x + 518y,4000)
满足约束条件： 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的产量时，要考虑不超过设备的有效台数，即可用不等式表示为：
x1 + 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 2x2 + …+ c nx n
a11x 1+ a12x 2 +….+ a13x n £ (= , ³) b 1
a21x1 + a22x 2 +…. + a23x n £ (= , ³) b2
满足约束条件： … …
a m1x1 + a m2x 2 +….+ a m3x n £ (= , ³) b m
x 1 ,x2 ,…, 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 + 2x2 £ 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为参数、– EQ F(2,3) 为斜率的一族平行直线 ：
x 2 = – EQ F(2,3) x1 + EQ F(z,3)
位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x 2= – EQ F(2,3) x1 + EQ F(z,3) 沿其法线方向（法线方向是指与直线垂直的方向）向上方移动。当移动到Q2点时，使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 | 28．1 |
| 1984 | 5 | 1990 | 11．5 | 1996 | 29 |
| 1985 | 6 | 1991 | 13．5 | ||
| 1986 | 6 | 1992 | 16．6 | 2000 | ？ |