数学建模线性规划模型
数学建模教案,线性规划模型
一、问题的提出
在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。
例1 若需在长为4000mm的圆钢上，截出长为698mm和518mm两种毛坯，问怎样截取才能使残料最少,
初步分析可以先考虑两种“极端”的情况:
(1)全部截出长为698mm的甲件，一共可截出 EQ F(4000,698) ?5件，残料长为510mm。
(2)全部截出长为518mm的乙件，一共可截出 EQ F(4000,518) ?7件，残料长为374mm。
由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少,把截取条件数学化地表示出来就是:
698 x + 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, x分别表示在计划期内产品I、II 的产量。
1 2
因为设备的有效台数为8 ，这是一个限制产量的条件，所以在确定I 、II的产量时，要考虑不超过设备的有效台数，即可用不等式表示为:
x + 2x ? 8 . 1 2同理，因原材料A 、B的限量，可以得到以下不等式:
4 x ? 16 1
4 x ? 12. 2
该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x、x以得到最大 1 2的利润。
若用 z 表示利润，这时z = 2x + 3 x。
综上所述，该计划问题可用数学模型表 1 2
示为:
目标函数 : max z = 2x + 3 x 1 2
满足约束条件: x + 2x ? 8 1 2
4 x ? 16 1
4 x ? 12. 2
x ，x ? 0 1 2
该模型的特征是:
(1)有一组决策变量(x ,x ,…,x )表示某一方案;这组决策变量的值就代表一个具体 1 2n
方案。
一般这些变量取值是非负的。
(2)存在一定的约束条件，这些约束条件可用一组线性等式(不等式)来表示。
(3)有一个要求达到的目标，它可用决策变量的线性函数(称为目标函数)来表示。
按问题的不同，要求实现目标函数最大化或最小化。
满足以上三个条件的数学模型称为线性规划模型。
其一般形式为: 目标函数 : max(min) z = c x + c x + …+ c x 1122nn
ax + ax +….+ ax ? (= , ?) b 11 112213 n1
ax + ax +…. + ax ? (= , ?) b 21 122223 n2
满足约束条件: … …
ax + a x +….+ a x ? (= , ?) b m1 1m22m3 nm
x ,x ,…, x ? 0 1 2 n
二、穷举法
以例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是材料利用率最高的截料方法。
在以x、x为坐标轴的直角坐标系中，非负条件x, x ? 0 是指第一象限(及x 轴正半轴、 1212
y轴正半轴)。
每一个约束条件都表示一个半平面。
若约束条件 x + 2x? 8 是代表以直线 1 2
x + 2x = 8为边界的左下 1 2
方的半平面。
x4x = 16 2 1
若同时满足x + 2x ? 8，4 x ? 16， 1 21x + 2x = 8 4x =12 1 22
4 x ? 12和x ，x ? 0约束的点， QQ 2 1 24 3
必然在由这三个半平面围成的区域内。
3 Q 2
由例1的所有约束条件为半平面围成 2
的区域见右图阴影部分。
阴影区域中 1
的每一个点(包括边界点)都这个线 Q x 11性规划问题的解。
o
再分析目标函数max z = 2x + 3 x，在这坐标平面上，它表示以 z为参
数、– EQ 1 2
F(2,3) 为斜率的一族平行直线 :
x = – EQ F(2,3) x + EQ F(z,3) 21
位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。
当z 值由小变大时，
直线x = – EQ F(2,3) x + EQ F(z,3) 沿其法线方向(法线方向是指与直线垂直的方向)21
向上方移动。
当移动到Q点时，使z值在可行域(阴影部分)边界上实现最大化，这就得 2
到了例 1 的最优解Q，Q点的坐标为(4，2)。
于是算得z =14。
22
这说明该厂的最优生产计划方案是:生产产品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 ,。