数学建模公选课第二讲

数学建模公选课第二讲第一页，共五十九页，编辑于2023年，星期三引例：某商业规划处在商场内要装修I、II两种经营不同商品的铺位各若干个，已知装修一个铺位所需的人数及A、B两种装修材料的消耗，如下表所示。

III现有数量设备128人原材料A4016kg原材料B0412kg该商场每个铺位I可获利2万元，每个铺位II可获利3万元，问应如何安排装修计划使商场获利最大？第二页，共五十九页，编辑于2023年，星期三

这问题可以用以下的数学模型来描述：设x1,x2分别表示在计划期内装修I、II的数量。因为可调动的人数为8人，这是一个限制装修数量的条件，所以在确定I、II的数量时，要考虑不超过可调动人数，即可用不等式表示为：x1+2x28.同理，因装修材料A、B的限量，可以得到以下不等式：4x116，4x212. 该商场的目标是在不超过所有资源限量的条件下，如何确定数量x1、x2以得到最大的利润。若用z表示利润，这时z=2x1+3x2。

第三页，共五十九页，编辑于2023年，星期三综上所述，该计划问题可用数学模型表示为：

目标函数：Maxz=2x1+3x2

满足约束条件：第四页，共五十九页，编辑于2023年，星期三图解法

图解法简单直观，有助于了解线性规划问题求解的基本原理。现进行图解。在以x1、x2为坐标轴的直角坐标系中，非负条件x1,x20是指第一象限（及x轴正半轴、y轴正半轴）。每一个约束条件都表示一个半平面。若约束条件x1+2x28是代表以直线x1+2x2=8为边界的左下方的半平面，同时满足x1+2x28，4x116，4x212和x1，x20约束的点，必然在由这三个半平面围成的区域内。所有约束条件为半平面围成的区域见右下图阴影部分。阴影区域中的每一个点（包括边界点）都这个线性规划问题的解。第五页，共五十九页，编辑于2023年，星期三再分析目标函数Q1Q2x1x2Q4Q3x1+2x2=84x1=164x2=12123o在这坐标平面上，它表示以z为参数、为斜率的一族平行直线：第六页，共五十九页，编辑于2023年，星期三x2=–x1+z位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x2=–x1+z沿其法线方向（法线方向是指与直线垂直的方向）向上方移动。当移动到Q2点时，使z值在可行域（阴影部分）边界上实现最大化，这就得到了最优解Q2，Q2点的坐标为（4，2）。于是算得Max=14。 这说明该商场的最优装修计划方案是：装修铺位I4间，装修铺位II2间，可得到最大利润为14万元。

第七页，共五十九页，编辑于2023年，星期三线性规划模型形式线性规划模型的矩阵式目标函数：max，min约束条件：≥,=,≤变量符号：：≥0线性规划的标准形式目标函数：min约束条件 ：=变量符号 ：≥0第八页，共五十九页，编辑于2023年，星期三线性规划的简写式第九页，共五十九页，编辑于2023年，星期三线性规划的向量式其中：C=(c1,c2,…,cn)------价值向量X=(x1,x2,…,xn)T------决策向量Pj=(a1j.a2j,…,amj)T------系数向量B=(b1,b2,…,bn)T------资源向量第十页，共五十九页，编辑于2023年，星期三线性规划问题的一般形式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)第十一页，共五十九页，编辑于2023年，星期三基本概念1。可行解(可行点):满足所有约束条件的向量。2。可行域（可行集）：所有可行解构成的集合。3。最优解：满足所有约束条件和目标函数的向量。4。最优值：最优解的目标函数值。第十二页，共五十九页，编辑于2023年，星期三

建模分析第一步：决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：约束条件。并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。第十三页，共五十九页，编辑于2023年，星期三第三步：目标函数。确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。讨论：这三步的顺序可以颠倒吗?为什么？第十四页，共五十九页，编辑于2023年，星期三几类典型的LP问题有大量的实际问题可以归结为线性规划问题来研究，这些问题背景不同，表现各异，但数学模型却有着完全相同的形式。尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。第十五页，共五十九页，编辑于2023年，星期三例1：人力资源分配问题公交线路需要24小时值班，每次值班8小时。不同时段需要的人数不等。序号时段最少人数106—1060210—1470314—1860418—2250522—0220602—0630问题：如何安排，所需人数最少？第十六页，共五十九页，编辑于2023年，星期三设xi为第i班次开始上班的人数目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1+x6≥60非负性约束：xj

≥0,j=1,2,…6第十七页，共五十九页，编辑于2023年，星期三例2：生产计划问题：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120问题：如何安排生产计划，使得获利最多？第十八页，共五十九页，编辑于2023年，星期三步骤：1.确定决策变量：设生产A产品x1kg,B产品x2kg2.确定目标函数：maxZ=70x1+120x23.确定约束条件：人力约束9x1+4x2≤360设备约束4x1+5x2≤200原材料约束3x1+10x2≤300非负性约束x1≥0,x2≥0第十九页，共五十九页，编辑于2023年，星期三设生产A产品x1kg,B产品x2kg,则得线性规划模型:第二十页，共五十九页，编辑于2023年，星期三例题3：任务分配问题某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？第二十一页，共五十九页，编辑于2023年，星期三第二十二页，共五十九页，编辑于2023年，星期三设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：

第二十三页，共五十九页，编辑于2023年，星期三应用总结市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料,“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)第二十四页，共五十九页，编辑于2023年，星期三要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件第二十五页，共五十九页，编辑于2023年，星期三用MATLAB优化工具箱解线性规划minz=cX

1、模型：命令：x=linprog（c，A，b）

2、模型：minz=cX

命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].第二十六页，共五十九页，编辑于2023年，星期三3、模型：minz=cX

VLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）

[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）

注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点4、命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.第二十七页，共五十九页，编辑于2023年，星期三引例解：编程序如下：f=[-2-3];A=[12;40;04];b=[8;16;12];Aeq=[];beq=[];[xf]=linprog(f,A,b,Aeq,beq)得结果：Optimizationterminatedsuccessfully.x=4.00002.0000f=-14.0000第二十八页，共五十九页，编辑于2023年，星期三目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1+x6≥60非负性约束：xj≥0,j=1,2,…6例1c=[1;1;1;1;1;1];A=[-1-10000;0-1-1000;00-1-100;000-1-10;0000-1-1;-10000-1];b=[-70;-60;-50;-20;-30;-60];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)解:编写M文件xxgh2.m如下：第二十九页，共五十九页，编辑于2023年，星期三第三十页，共五十九页，编辑于2023年，星期三Optimizationterminatedsuccessfully.x=41.917628.082435.049414.95069.860620.1394fval=150.0000结果如下:第三十一页，共五十九页，编辑于2023年，星期三解编写M文件xxgh1.m如下：c=[-70;-120];A=[94;45;310];b=[360;200;300];Aeq=[];beq=[];Vlb=[0;0];Vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,Vlb,Vub)ToMatlab(xxgh1)例2：第三十二页，共五十九页，编辑于2023年，星期三Optimizationterminatedsuccessfully.x=20.000024.0000fval=-4.2800e+003

结果如下:第三十三页，共五十九页，编辑于2023年，星期三例3解:编写M文件xxgh2.m如下：f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

第三十四页，共五十九页，编辑于2023年，星期三Optimizationterminatedsuccessfully.x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004第三十五页，共五十九页，编辑于2023年，星期三第三十六页，共五十九页，编辑于2023年，星期三企业生产计划生产与销售计划

空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题第三十七页，共五十九页，编辑于2023年，星期三例：一奶制品加工厂用牛奶生产A1、A2两种奶制品。一桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2可以全部售出。每公斤A1获利24元，每公斤A2获利16元。现在每天有50桶牛奶的供应。每天正式工人总的工作时间为480小时，并且甲类设备每天至多能加工100公斤A1，乙类设备的加工能力不受限制。试为该厂制定一个生产计划，使该厂每天获利最大？并进一步讨论以下几个附加问题：1）若用35元可以买到一桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘请临时工以增加劳动时间，付给临时工的工资最多是每小时几元？第三十八页，共五十九页，编辑于2023年，星期三3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？为增加工厂的获利，开发了奶制品的深加工技术：用2小时和3元加工费。可以将1公斤A1加工成0。8公斤高级奶制品B1，也可以将1公斤A2加工成0。75公斤高级奶制品B2，每公斤B1获利44元，每公斤B2获利32元。试为该厂制定一个生产销售计划，使每天的净利润最大。并讨论以下问题：4）若投资30元可以增加供应1桶牛奶，投资3元可以增加1小时劳动时间，应否作这些投资？若每天投资150元，可赚回多少？5）每公斤高级奶制品B1、B2的获利经常有10%的波动，对制定的计划有无影响？若每公斤B1的获利下降10%，计划应该变化吗？第三十九页，共五十九页，编辑于2023年，星期三分析：1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：第四十页，共五十九页，编辑于2023年，星期三1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天第四十一页，共五十九页，编辑于2023年，星期三模型分析与假设

比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型第四十二页，共五十九页，编辑于2023年，星期三模型求解

图解法

x1x20ABCDl1l2l3l4l5约束条件目标函数

Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。第四十三页，共五十九页，编辑于2023年，星期三

MODEL:[FVAL]MAX=72*X1+64*X2;[MILK]X1+X2<=50;[TIME]12*X1+8*X2<=480;[SHOP]3*X1<=100;END第四十四页，共五十九页，编辑于2023年，星期三

Rows=4Vars=2No.integervars=0(allarelinear)Nonzeros=10Constraintnonz=5(2are+-1)Density=0.833Smallestandlargestelementsinabsvalue=1.00000480.000No.<:3No.=:0No.>:0,Obj=MAX,GUBs<=1Singlecols=0Optimalsolutionfoundatstep:1Objectivevalue:3360.000VariableValueReducedCostX120.000000.0000000X230.000000.0000000RowSlackorSurplusDualPrice13360.0001.00000020.000000048.0000030.00000002.000000440.000000.0000000第四十五页，共五十九页，编辑于2023年，星期三选lingo-Ranges即得:Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecrease250.0000010.000006.6666673480.000053.3333380.000004100.0000INFINITY40.00000第四十六页，共五十九页，编辑于2023年，星期三模型求解

软件实现

LINDO6.1

max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。第四十七页，共五十九页，编辑于2023年，星期三结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源“资源”剩余为零的约束为紧约束（有效约束）第四十八页，共五十九页，编辑于2023年，星期三结果解释

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！第四十九页，共五十九页，编辑于2023年，星期三RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)第五十页，共五十九页，编辑于2023年，星期三结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)第五十一页，共五十九页，编辑于2023年，星期三奶制品的生产销售计划

深加工1桶牛奶3千克A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤0.8千克B12小时和3元1千克获利44元/千克0.75千克B22小时和3元1千克获利32元/千克制订生产计划，使每天净利润最大30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？50桶牛奶,480小时至多100公斤A1

B1，B2的获利经常有10%的波动，对计划有无影响？第五十二页，共五十九页，编辑于2023年，星期三1桶牛奶

3千克A1

12小时8小时4千克A2

或获利24元/千克获利16元/kg

0.8千克

B12小时3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克出售x1千克A1,

x2千克A2，

X3千克B1,x4千克B2原料供应

劳动时间

加工能力

决策变量

目标函数

利润约束条件非负约束

x5千克A1加工B1，x6千克A2加工B2附加约束

第五十三页，共五十九页，编辑于2023年，星期三模型求解

软件实现

LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No第五十四页，共五十九页，编辑于2023年，星期三

OBJECTIVEFUNCTIONVALUE1)3460.800

VARIABLEVALUEREDUCEDCOST

X10.0000001.680000

X2168.0000000.000000

X319.2000010.000000

X40.0000000.000000

X524.0000000.000000

X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2结果解释每天销售168千克A2和19.2千克B1，利润3460.8（元）8桶牛奶加