宝典数学建模计划题目标经典案例

1、建立优化模型的一般步骤1.确定决策变量2.确定目标函数的表达式3.寻找约束条件例1：设某厂生产电脑和手机两种产品，这两种产品的生产需要逐次经过两条装配线进行装配。电脑在第一条装配线每台需要2小时，在第二条装配线每台需要3小时；手机在第一条装配线每台需要4小时，在第二条装配线每台需要1小时。第一条装配线每天有80个可用工时，第一条装配线每天有60个可用工时，电脑和手机每台的利润分别为100元和80元。问怎样制定生产计划？分析： 目标是利润l；而利润是由电脑的产量x和手机的产量y决定yxl80100 2.4,案例假设：1、两种产品的销量不受限制2、原材料供应不受限制约束条件：装配线1的工时限制装配

2、线2的工时限制8042yx603 yx0 , 0 yx变量约束建立模型yxl80100max 0 ,06038042 s.t.yxyxyx模型求解：8042 yx603 yxcyx 801001243657例2：最短路线问题的数学建模实例1415121013209128810变量变量 否则否则的路通过的路通过到到从从01jixij模型模型)(1210898131012151420min6757564745363425241312总路程总路程xxxxxxxxxxxz . .ts.111312出发的一辆车出发的一辆车考虑从节点考虑从节点 xx; 0252412 xxx; 047453424 xxx

3、x; 0675636 xxx1675747 xxx; 057564525 xxxx; 0363413 xxx. 7 , 2 , 1,10 ji，xij或或取取12436579810例3：最短路线问题算例1001502001751254002503002002751752752003501501009-101008-101506-9-103005-8-104007-8-102752-6-106004-6-105003-5-106001-4-10650最短路线为:1-4-6-9-10，长度：650沿该弧的运量沿该弧的运量到到表示节点表示节点设设jixij1243657141512101320912

4、8810变量变量模型模型例4：最小费用流问题)(1210898131012151420min6757564745363425241312总运费总运费xxxxxxxxxxxz . .ts.1312考虑从产地出发的运量考虑从产地出发的运量qxx ; 0252412 xxx; 047453424 xxxx; 0675636 xxxqxxx 675747; 057564525 xxxx; 0363413 xxx. 7 , 2 , 1,0 ji，xij例5：最大流量问题变量变量。网络的最大通车量网络的最大通车量求通过该公路求通过该公路.1沿该弧的车流量沿该弧的车流量到到为从为从发出的车流量发出的车流量表

5、示从节点表示从节点用用jixvij模型模型vmax. .ts.1312vxx ; 0252412 xxx; 047453424 xxxx; 0675636 xxxvxxx 675747; 057564525 xxxx; 0363413 xxx0. v各段上的流量限制各段上的流量限制12436571415121013209128810模型模型vmax. .ts.1312vxx ; 0252412 xxx; 047453424 xxxx; 0675636 xxxvxxx 675747; 057564525 xxxx; 0363413 xxx0. v各段上的流量限制各段上的流量限制工厂定期订购原料，

6、存入仓库供生产之用；车间一次加工出一批零件，供装配线每天生产之用；商店成批购进各种商品，放在货柜里以备零售；水库在雨季蓄水，用于旱季的灌溉和发电。存贮模型存贮量多少合适？存贮量过大，存贮费用太高；存贮量太小，会导致一次性订购费用增加，或不能及时满足需求。问题1,不允许缺货的存贮模型,配件厂为装配线生产若干种部件，轮换生产不同的部件时因更换设备要付生产准备费（与生产数量无关），同一部件的产量大于需求时因积压资金、占用仓库要付存贮费。今已知某一部件的日需求量100件，生产准备费5000元，存贮费每日每件1元。如果生产能力远大于需求，并且不允许出现缺货，试安排该产品的生产计划，即多少天生产一次（称为

7、生产周期），每次产量多少，可使总费用最小。问题分析若每天生产一次，每次100件，无存贮费，生产准备费5000元，每天费用5000元；若10天生产一次，每次1000件，存贮费900+800+100=4500元，生产准备费5000元，总计9500元，平均每天费用950元；若50天生产一次，每次5000件，存贮费4900+4800+100=122500元，生产准备费5000元，总计127500元，平均每天费用2550元；寻找生产周期、产量、需求量、生产准备费和存贮费之间的关系，使每天的费用最少。模型假设1,连续化，即设生产周期,t,和产量,q,均为连续量；2,产品每日的需求量为常数,r,；3,每次生

8、产准备费,c1，每日每件产品存贮费,c2；4,生产能力为无限大（相对于需求量），当存贮量,降到零时，q件产品立即生产出来供给需求，即,不允许缺货。模型建立总费用与变量的关系总费用=生产准备费+存贮费存贮费=存贮单价*存贮量存贮量=？设,t,时刻的存贮量为,q(t),，t,=,0时生产,q,件，存贮量,q(0),=,q,q(t),以需求速率,r,线性递减，直至q(t),=,0，如图。q(t),=,q-,r,t，,q,=,r,t,。otqqtra不允许缺货模型的存贮量不允许缺货模型的存贮量q(t) 存贮量的计算一个周期内存贮量dttqt0)(一个周期内存贮费dttqct02)(2qt (a的面积)

9、一个周期的总费用dttqccct 021)(2222121rtccqtcc 每天平均费用2)(21rtctctctc 2)(min 21rtctctct 满足满足求求模型求解用微分法02)(221 rctctcrcct212 212crcrtq 每天平均最小费用rccc212 思考建模中未考虑生产费用（这应是最大一笔费,用），在什么情况下才可以不考虑它？建模时作了“生产能力无限大”的简化假设，如,果生产能力有限，是大于需求量的一个常数，如何建模？结果解释rcct212 212crcrtq rccc212 当准备费,c1,增加时，生产周期和产量都变大；当存贮费,c2,增加时，生产周期和产量都变小

10、；当日需求费,r,增加时，生产周期变小而产量变大。这些定性结果符合常识，而定量关系（平方根，系数2,等）凭常识是无法得出的，只能由数学建模得到。rcct212 rccc212 1000 10 ,100 , 1 ,5000 21 ctrcc，得得当当这里得到的费用c与前面计算得950元有微小差别，你能解释吗？在本例中敏感性分析讨论参数rcc, 21有微小变化时对生产周期t,影响。由相对变化量衡量对参数的敏感程度。t,对c1,的敏感程度记为),(1cts111),(ccttcts tcdcdt11 tcrccrc12122221 2121),(2 cts21),( rts意义是当准备费增加1%时，

11、生产周期增加0.5%,；而存贮费增加1%时，生产周期减少0.5%,；日需求量增加1%时，生产周期减少0.5%,。21),(1 cts21),(2 cts21),( rts当rcc, 21有微小变化对生产周期影响不太大。模型假设1,连续化，即设生产周期,t,和产量,q,均为连续量；2,产品每日的需求量为常数,r,；3,每次生产准备费,c1，每日每件产品存贮费,c2；4,生产能力为无限大（相对于需求量），允许缺,货，每天每件产品缺货损失费c3,，但缺货数量需,在下次生产（订货）时补足。问题2,允许缺货的存贮模型模型建立总费用=生产准备费+存贮费+缺货损失费存贮费=存贮单价*存贮量缺货损失费=缺货单

12、价*缺货量存贮量=？，缺货量=？因存贮量不足造成缺货，因此,q(t),可取负值，,q(t),以需求速率,r,线性递减，直至q(t1),=,0，如图。q(t),=,q-r,t，,q,=,r,t1,。otqqtra允许缺货模型的存贮量允许缺货模型的存贮量q q( (t t) ) rt1b一个周期内缺货损失费一个周期内存贮费dttqct 102)(212qtc 一个周期的总费用rqrtcrqccc2)(223221 每天平均费用dttqctt 1)(32)(13ttqrtc rqrtc2)(23 rqc222 rtqrtcrtqctcqtc2)(2),(23221 ,满足满足求求qt模型求解用微分法

13、,令332212cccrcct 323212ccccrcq 每天平均最小费用),(qtcc rtqrtcrtqctcqtc2)(2),(min23221 0),( , 0),( qqtctqtc每个周期的供货量trr 332212cccrccrr 332ccc 与不允许缺货模型相比较，有qrqqtt ,/ ,qrqqtt ,/ ,结果解释qrqqtt , , , 1 即允许缺货时，周期和供货量增加，周期初的存贮量减少。2）缺货损失费愈大，,愈小，,愈接近,，,愈接近,。1）ttrq , q332ccc 3），时，时，当当13 cqrqqtt , ,不允许缺货模型可视为允许缺货模型的特例。企业生

14、产计划奶制品的生产与销售,空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题本节课题,一奶制品加工厂用牛奶生产a1、a2两种奶制品，一桶牛奶可以在甲类设备上用12小时加工成3公斤a1，或者在乙类设备上用8个小时加工成4公斤a2。根据市场需求，生产的a1，a2全部都能售出，且每公斤a1获利24元，每公斤a2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正

15、式工人总的劳动时间为480小时，并且甲类设备每天之多能加工100公斤a1，乙类设备没有加工能力限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论一以下3个附加问题：例1,加工奶制品的生产计划,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,a1的获利增加到,30元/公斤，应否改变生产计划？,例1,加工奶制品的生产计划1桶桶牛奶牛奶 3公斤公斤a1 12小时小时 8小时小时 4公斤公斤a2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤 50桶牛奶,时间480小时,至多加工100公斤a1,制订生产计划，使每天获利最大,35元

16、可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,a1的获利增加到,30元/公斤，应否改变生产计划？,每天：1桶桶牛奶牛奶 3公斤公斤a1 12小时小时 8小时小时 4公斤公斤a2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤 x1桶牛奶生产a1,x2桶牛奶生产a2,获利,243x1,获利,164,x2,原料供应,5021 xx劳动时间,48081221 xx加工能力,10031x决策变量,目标函数,216472xxzmax每天获利约束条件非负约束,0,21xx线性规划模型(lp)时间480小时,至多加工100公斤a1,50桶牛奶桶牛奶

17、每天每天模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,a1,a2每公斤的获利是与各自产量无关的常数每桶牛奶加工出a1,a2的数量和时间是与各自产量无关的常数a1,a2每公斤的获利是与相互产量无关的常数每桶牛奶加工出a1,a2的数量和时间是与相互产量无关的常数加工a1,a2的牛奶桶数是实数,线性规划模型模型求解,图解法,x1x20abcdl1l2l3l4l55021 xx48081221 xx10031 x0,21 xx约约束

18、束条条件件50:211 xxl480812:212 xxl1003:13 xl0:, 0:2514 xlxl216472xxzmax 目标函数,z=0z=2400z=3600z=c,(常数),等值线c在b(20,30)点得到最优解目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,objective,function,value,1),3360.000,variable,value,reduced,cost,x1,20.000000,0.000000,x2,30.000000,0.000000,row,slack,or,su

19、rplus,dual,prices,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,no.,iterations=,2模型求解,软件实现,lindo,6.1,max,72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100enddo,range,(sensitivity),analysis?,no20桶牛奶生产a1,30桶生产a2，利润3360元。,objective,function,value,1),3360.000,variable,value,reduced,cost,x1,20

20、.000000,0.000000,x2,30.000000,0.000000,row,slack,or,surplus,dual,prices,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,no.,iterations=,2：结果解释,objective,function,value,1),3360.000,variable,value,reduced,cost,x1,20.000000,0.000000,x2,30.000000,0.000000,row,slack,or,surplus,dual,price

21、s,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,no.,iterations=,2原料无剩余时间无剩余加工能力剩余40max,72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”,剩余为零的约束为紧约束（有效约束）,结果解释,objective,function,value,1),3360.000,variable,value,reduced,cost,x1,20.000000,0.000000,x2,30.000000,0.000000,row,slack

22、,or,surplus,dual,prices,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,no.,iterations=,2最优解下“资源”增加1单位时“效益”的增量,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润影子价格,35元可买到1桶牛奶，要买吗？35,48,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！ranges,in,which,the,basis,is,unchanged:,obj,coefficient,ranges,variable,curren

23、t,allowable,allowable,coef,increase,decrease,x1,72.000000,24.000000,8.000000,x2,64.000000,8.000000,16.000000,righthand,side,ranges,row,current,allowable,allowable,rhs,increase,decrease,2,50.000000,10.000000,6.666667,3,480.000000,53.333332,80.000000,4,100.000000,infinity,40.000000最优解不变时目标函数系数允许变化范围,d

24、o,range(sensitivity),analysis?,yesx1系数范围(64,96),x2系数范围(48,72),a1获利增加到,30元/千克，应否改变生产计划,x1系数由24,3=72增加为303=90，在允许范围内,不变！(约束条件不变)结果解释,ranges,in,which,the,basis,is,unchanged:,obj,coefficient,ranges,variable,current,allowable,allowable,coef,increase,decrease,x1,72.000000,24.000000,8.000000,x2,64.000000,8

25、.000000,16.000000,righthand,side,ranges,row,current,allowable,allowable,rhs,increase,decrease,2,50.000000,10.000000,6.666667,3,480.000000,53.333332,80.000000,4,100.000000,infinity,40.000000影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)例2,奶制品的生产销售计划,例1给出的a1、a2两种奶制品的生产条件、利润、及

26、工厂的“资源”限制都不变，为增加工厂的获利，开发了奶制品的深加工技术：用2小时和3元加工费可将1公斤a1加工成0.8公斤的高级奶制品b1，也可将1公斤a2加工成0.75公斤的高级奶制品b2，每公斤b1能获利44元，每公斤b2能获利32元。试为该厂制定一个生产销售计划，使每天的净利润最大，并讨论以下问题：,若投资30元可增加1桶牛奶，投资3元可增加1小时劳动时间，应否应做这些投资？现每天投资150元，可赚回多少？,b1，b2的获利经常有10%的波动，对定制的计划有无影响？若每公斤b1的获利下降10，计划应该变化吗？例2,奶制品的生产销售计划,在例1基础上深加工1桶桶牛奶牛奶 3千克千克a1 12

27、小时小时 8小时小时 4公斤公斤a2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤 0.8千克千克b12小时小时,3元元1千克千克获利获利44元元/千克千克 0.75千克千克b22小时小时,3元元1千克千克获利获利32元元/千克千克 制订生产计划，使每天净利润最大,50桶牛奶,480小时,至多100公斤a1,若投资30元可增加1桶牛奶，投资3元可增加1小时劳动时间，应否应做这些投资？现每天投资150元，可赚回多少？,b1，b2的获利经常有10%的波动，对定制的计划有无影响？若每公斤b1的获利下降10，计划应该变化吗？1桶桶牛奶牛奶 3千克千克 a1 12小时小时 8小时小时 4千

28、克千克 a2 或或获利获利24元元/千克千克 获利获利16元元/kg 0.8千克千克 b12小时小时,3元元1千克千克获利获利44元元/千克千克 0.75千克千克 b22小时小时,3元元1千克千克获利获利32元元/千克千克 出售x1,千克,a1,x2,千克,a2，,x3千克,b1,x4千克,b2原料供应,劳动时间,加工能力,决策变量,目标函数,利润约束条件非负约束,0,61xx x5千克,a1加工b1，,x6千克,a2加工b26543213332441624xxxxxxzmax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加约束,5380 x.x647

29、50 x.x 模型求解,软件实现,lindo,6.1,5043) 26251xxxx48022)(2)(4)3656251xxxxxx,objective,function,value,1),3460.800,variable,value,reduced,cost,x1,0.000000,1.680000,x2,168.000000,0.000000,x3,19.200001,0.000000,x4,0.000000,0.000000,x5,24.000000,0.000000,x6,0.000000,1.520000row,slack,or,surplus,dual,prices,2),0.

30、000000,3.160000,3),0.000000,3.260000,4),76.000000,0.000000,5),0.000000,44.000000,6),0.000000,32.000000,no.,iterations=,2600334) 26521xxxx44804624) 36521xxxxdo range (sensitivity) analysis? no,objective,function,value,1),3460.800,variable,value,reduced,cost,x1,0.000000,1.680000,x2,168.000000,0.000000

31、,x3,19.200001,0.000000,x4,0.000000,0.000000,x5,24.000000,0.000000,x6,0.000000,1.520000row,slack,or,surplus,dual,prices,2),0.000000,3.160000,3),0.000000,3.260000,4),76.000000,0.000000,5),0.000000,44.000000,6),0.000000,32.000000,no.,iterations=,2结果解释每天销售168,千克a2和19.2,千克b1，,利润3460.8（元）8桶牛奶加工成a1，42桶牛奶加工

32、成a2，将得到的24千克a1全部加工成b1,除加工能力外均为紧约束结果解释,objective,function,value,1),3460.800,variable,value,reduced,cost,x1,0.000000,1.680000,x2,168.000000,0.000000,x3,19.200001,0.000000,x4,0.000000,0.000000,x5,24.000000,0.000000,x6,0.000000,1.520000row,slack,or,surplus,dual,prices,2),0.000000,3.160000,3),0.000000,3.

33、260000,4),76.000000,0.000000,5),0.000000,44.000000,6),0.000000,32.000000增加1桶牛奶使利润增长3.1612=37.925043)26251xxxx600334) 26521xxxx4增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）结果解释b1,b2的获利有10%的波动，对计划有无影响,ranges,in,which,the,basis,is,unchanged:,obj,coeffic

34、ient,ranges,variable,current,allowable,allowable,coef,increase,decrease,x1,24.000000,1.680000,infinity,x2,16.000000,8.150000,2.100000,x3,44.000000,19.750002,3.166667,x4,32.000000,2.026667,infinity,x5,-3.000000,15.800000,2.533334,x6,-3.000000,1.520000,infinity,do range (sensitivity) analysis? yesb1获利

35、下降10%，超出x3,系数允许范围b2获利上升10%，超出x4,系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。,自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。其他费用:450元/千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,元元/千吨千吨甲甲乙乙丙丙丁丁a160130220170b140130190150c190200230/引水管理费引水

36、管理费例1,自来水输送收入：900元/千吨,支出a：50b：60c：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水库供水量水库供水量(千吨千吨)小区基本用水量小区基本用水量(千吨千吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）总供水量：160确定送水方案使利润最大问题分析a：50b：60c：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40,总需求量(300)每个水库最大供水量都提高一倍利润,=,收入(900),其它费用(450),引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁a290320230280b3103

37、20260300c260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxzmax供应限制b,c,类似处理50:a14131211xxxx10014131211xxxx问题讨论,确定送水方案使利润最大需求约束可以不变求解,objective,function,value,1),88700.00,variable,value,reduced,cost,x11,0.000000,20.000000,x12,100.000000,0.000000,x13,0.000000,40.000000,x14,0

38、.000000,20.000000,x21,30.000000,0.000000,x22,40.000000,0.000000,x23,0.000000,10.000000,x24,50.000000,0.000000,x31,50.000000,0.000000,x32,0.000000,20.000000,x33,30.000000,0.000000,这类问题一般称为“运输问题”(transportation,problem)总利润,88700（元）,a(100)b(120)c(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何装

39、运，使本次飞行获利最大？,三个货舱最大载重(吨),最大容积(米3),例2,货机装运 重量（吨）重量（吨）空间空间( 米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大载重成比例,前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡决策变量,xij-第i,种货物装入第j,个货舱的重量(吨）i=1,2,3,4,j=1,2,3,(分别代表前、中、后仓)模型假设,每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多

40、种货物可以混装，并保证不留空隙；,模型建立,货舱容积,目标函数(利润)约束条件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxzmax 680039058065048041312111 xxxx870039058065048042322212 xxxx530039058065048043332313 xxxx货机装运模型建立,货舱重量,1041312111 xxxx1642322212 xxxx843332313 xxxx10；680016；87008；5300 xij-第i,种货物装入第j,个货舱的重量约束条件平衡要求

41、,81610433323134232221241312111xxxxxxxxxxxx 货物供应,18131211 xxx15232221 xxx23333231 xxx12434241 xxx货机装运模型建立,10；680016；87008；5300 xij-第i,种货物装入第j,个货舱的重量,objective,function,value,1),121515.8,variable,value,reduced,cost,x11,0.000000,400.000000,x12,0.000000,57.894737,x13,0.000000,400.000000,x21,10.000000,0.

42、000000,x22,0.000000,239.473679,x23,5.000000,0.000000,x31,0.000000,0.000000,x32,12.947369,0.000000,x33,3.000000,0.000000,x41,0.000000,650.000000,x42,3.052632,0.000000,x43,0.000000,650.000000,货物2：前仓10,后仓5；,货物3:,中仓13,后仓3；货物4:,中仓3。货机装运模型求解,最大利润约121516元货物供应点货舱需求点平衡要求运输运输问题问题运输问题的扩展运输问题的扩展设每月生产小、中、大型汽车的数量

43、分别为x1,x2,x3321432xxxzmax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽车厂生产计划,模型建立, 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4 线性规划模型(lp)模型求解,3）,模型中增加条件：x1,x2,x3,均为整数，重新求解。,objective,function,value,1),632.2581variable,value,reduced,cost,x1,64.516129,0.000000,x2,167.741928

44、,0.000000,x3,0.000000,0.946237,row,slack,or,surplus,dual,prices,2),0.000000,0.731183,3),0.000000,0.003226结果为小数，怎么办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与lp最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？ip可用lindo直接求解整数规划(integer,programming,简记ip)“gin,3”表示“前3个变

45、量为整数”，等价于：gin,x1gin,x2gin,x3,ip,的最优解x1=64，x2=168，x3=0，最优值z=632,max,2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin,3,objective,function,value,1),632.0000variable,value,reduced,cost,x1,64.000000,-2.000000,x2,168.000000,-3.000000,x3,0.000000,-4.000000,321432xxxzmax600535 . 1.321xxxts60000

46、400250280321 xxx为非负整数为非负整数321,xxx模型求解,ip,结果输出其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法1：分解为8个lp子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划。321432xxxzmax600535 . 1.321xxxts60000400250280321xxxx1,x2, x3=0 或或

47、80 x1=80，x2=,150，x3=0，最优值z=610lindo中对0-1变量的限定：int,y1int,y2int,y3,方法2：引入0-1变量，化为整数规划,m为大的正数，可取1000,objective,function,value,1),610.0000variable,value,reduced,cost,x1,80.000000,-2.000000,x2,150.000000,-3.000000,x3,0.000000,-4.000000,y1,1.000000,0.000000,y2,1.000000,0.000000,y3,0.000000,0.000000,若生产某类汽

48、车，则至少生产80辆，求生产计划。x1=0,或,80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxmyx1 , 0,80,22222yyxmyx1 , 0,80,33333yyxmyx最优解同前,nlp虽然可用现成的数学软件求解(如lingo,matlab)，但是其结果常依赖于初值的选择。,方法3：化为非线性规划,非线性规划（non-,linear,programming，简记nlp）,实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。,若生产某类汽车，则至少生产80辆，求生产计划。,x1=0,或,80 x2=0 或 80 x3=0 或 80

49、0)80(11xx0)80(22xx0)80(33xx应如何安排原油的采购和加工,？,例2,原油采购与加工,市场上可买到不超过1500吨的原油a：,购买量不超过500吨时的单价为10000元/吨；,购买量超过500吨但不超过1000吨时，超过500吨的,部分8000元/吨；,购买量超过1000吨时，超过1000吨的部分6000元/吨。,售价售价4800元元/吨吨 售价售价5600元元/吨吨库存库存500吨吨 库存库存1000吨吨 汽油甲汽油甲(a 50%) 原油原油a 原油原油b 汽油乙汽油乙 (a 60%) 决策变量,目标函数问题分析,利润：销售汽油的收入,-,购买原油a的支出,难点：原油a

50、的购价与购买量的关系较复杂)()(6 . 5)( 8 . 422122111xcxxxxzmax甲甲(a 50%) a b 乙乙(a 60%) 购买购买xx11x12x21x224.8千元千元/吨吨 5.6千元千元/吨吨原油a的购买量,原油a,b生产汽油甲,乙的数量c(x),购买原油a的支出利润(千元)c(x)如何表述？原油供应,约束条件xxx500121110002221 xx1500 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc,x,500吨单价为10千元/吨；,500吨,x,1000吨，超过500吨的8千元/吨；1000吨,x,

51、1500吨，超过1000吨的6千元/吨。,目标函数购买购买x a b x11x12x21x22库存库存500吨吨 库存库存1000吨吨 ,目标函数中c(x)不是线性函数，是非线性规划；,对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；,想办法将模型化简，用现成的软件求解。,汽油含原油a的比例限制,5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 约束条件甲甲(a 50%) a b 乙乙(a 60%) x11x12x21x22x1,x2,x3,以价格10,8,6(千元/吨)采购a的吨数目标函数,只有当以10千元/吨的价格购买x1=50

52、0(吨)时，才能以8千元/吨的价格购买x2方法1,)6810()( 6 . 5)( 8 . 432122122111xxxxxxxzmax0)500(32xx500,0321xxx非线性规划模型，可以用lingo求解模型求解x=,x1+x2+x3,c(x),=,10 x1+8x2+6x3,500吨,x,1000吨，超过500吨的8千元/吨增加约束增加约束0)500(21xxx=,x1+x2+x3,c(x),=,10 x1+8x2+6x3,方法1：lingo求解model:max=,4.8*x11,+,4.8*x21,+,5.6*x12,+,5.6*x22,-,10*x1,-,8*x2,-,6*

53、x3;x11+x12,x,+,500;x21+x22,0;,2*x12,-,3*x22,0;x=x1+x2+x3;,(x1,-,500),*,x2=0;,(x2,-,500),*,x3=0;,x1,500;x2,500;x3,0;x11,0;x12,0;x21,0;x22,0;x1,0;x2,0;x3,0;end,objective,value:,4800.000variable,value,reduced,costx11,500.0000,0.0000000e+00x21,500.0000,0.0000000e+00x12,0.0000000e+00,0.0000000e+00x22,0.0

54、000000e+00,0.0000000e+00,x1,0.1021405e-13,10.00000,x2,0.0000000e+00,8.000000,x3,0.0000000e+00,6.000000,x,0.0000000e+00,0.0000000e+00,lingo得到的是局部最优解，还能得到更好的解吗？,用库存的500吨原油a、500吨原油b生产汽油甲，不购买新的原油a，利润为4,800千元。,y1,y2,y3=1,以价格10,8,6(千元/吨)采购a增加约束方法2,0-1线性规划模型，可用lindo求解112500500yxy223500500yxy33500yx y1,y2,y

55、3,=0或1,objective,function,value,1),5000.000,variable,value,reduced,cost,y1,1.000000,0.000000,y2,1.000000,2200.000000,y3,1.000000,1200.000000,x11,0.000000,0.800000,x21,0.000000,0.800000,x12,1500.000000,0.000000,x22,1000.000000,0.000000,x1,500.000000,0.000000,x2,500.000000,0.000000,x3,0.000000,0.40000

56、0,x,1000.000000,0.000000,购买1000吨原油a，与库存的500吨原油a和1000吨原油b一起，生产汽油乙，利润为5,000千元,。x1,x2,x3,以价格10,8,6(千元/吨)采购a的吨数y=0 x=0 x0 y=1优于方法1的结果b1,b2,b3,b4方法3,b1,xb2，x=,z1b1+z2b2，z1+z2=1，z1,z20,c(x)=,z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2,x,b3，x=,z2b2+z3b3，,z2+z3=1，z2,z3,0,c(x)=,z2c(b2)+z3c(b3).,b3,x,b4，

57、x=,z3b3+z4b4，z3+z4=1，z3,z4,0,c(x)=,z3c(b3)+z4c(b4).,500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc,直接处理处理分段线性函数c(x),ip模型，lindo求解，得到的结果与方法2相同.处理分段线性函数，方法3更具一般性44332211bzbzbzbzx)()()()()(44332211bczbczbczbczxcbkxbk+1yk=1,否则,yk=03432321211,yzyyzyyzyz)4 , 3 , 2 , 1(0, 14321kzzzzzk10, 1321321或yyyyyy

58、方法3,bkxbk+1,x=,zkbk+z,k+1,bk+1zk+zk+1,=1，zk,zk+1,0,c(x)=,zkc(bk)+zk+1,c(bk+1,).c(x)x1200090005000050010001500b1 b2 b3 b4对于k=1,2,3分派问题,接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。丁的蛙泳成绩退步到115”2；戊

59、的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例1,混合泳接力队的选拔, 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j,的比赛，记xij=1,否则记xij=0,0-1规划模型,cij(秒)队员i,第j,种泳姿的百米成绩约束条件每人最多入选泳姿之一,ciji=1i=

60、2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxczmin每种泳姿有且只有1人,5, 1, 141ixjij4, 1, 151jxiij模型求解,最优解：x14,=,x21,=,x32,=,x43,=,1,其它变量为0;成绩为253.2(秒)=413”2,min,66.8x11+75.6x12+87x13+58.6x14,+,+67.4x51+71,x52+83.8x53+62.4x54subject,to,x11+x12+x13+x14,=