《数学规划模型清华大学学习教案.pptx》由会员分享，可在线阅读，更多相关《数学规划模型清华大学学习教案.pptx（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学规划数学规划(guhu)模型清华大学模型清华大学第一页，共93页。数学规划数学规划(guhu)(guhu)模型模型 实际问题实际问题(wnt)中中的优化模型的优化模型x决策决策(juc)变量变量f(x)目标函数目标函数gi(x)0约束条件约束条件多元函数多元函数条件极值条件极值 决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大 最优解在可行域最优解在可行域的边界上取得的边界上取得 数数学学规规划划线性规划线性规划非线性规非线性规划划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析第1页/共93页第二页，共93页。企业企业(qy)生生产计划产计划4.1
2、 奶制品的生产奶制品的生产(shngchn)与销售与销售 空间空间(kngjin)层次层次工厂级：根据外部需求和内部设备、人力、原料等条件，工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产
3、计划。，否则应制订多阶段生产计划。本节课题本节课题第2页/共93页第三页，共93页。例例1 加工加工(ji gng)奶制品的生奶制品的生产计划产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶(ni ni)时间时间(shjin)480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利
4、增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：第3页/共93页第四页，共93页。1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶桶牛奶(ni ni)生产生产A1 x2桶牛奶桶牛奶(ni ni)生产生产A2 获利获利(hu l)243x1 获利获利 164 x2 原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每每
5、天天第4页/共93页第五页，共93页。模型分析模型分析(fnx)(fnx)与与假设假设 比比例例(bl)性性 可可加加性性 连续性连续性 xi对目标对目标(mbio)函数的函数的“贡献贡献”与与xi取值成正比取值成正比 xi对约束条件的对约束条件的“贡献贡献”与与xi取值成取值成正比正比 xi对目标函数的对目标函数的“贡贡献献”与与xj取值无关取值无关 xi对约束条件的对约束条件的“贡贡献献”与与xj取值无关取值无关 xi取值连续取值连续 A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时的数量和时间是与各自产量无关的
6、常数间是与各自产量无关的常数A1,A2每公斤的获利是与相互产每公斤的获利是与相互产量无关的常数量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时的数量和时间是与相互产量无关的常数间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数 线性规划模线性规划模型型第5页/共93页第六页，共93页。模型模型(mxng)(mxng)求解求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标(mbi(mbio)o)函函数数 Z=0Z=2400Z=3600z=c(常数常数(chngsh)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函
7、数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多最优解一定在凸多边形的某个顶点取边形的某个顶点取得。得。第6页/共93页第七页，共93页。模型模型(mxng)(mxng)求求解解 软件软件(run(run jin)jin)实现实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST
8、 X1 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=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产(shngchn)A1,30桶生产桶生产(shngchn)A2，利润，利润3360元。元。第7页/共93页第八页，共93页。结果结果(ji(ji gu)gu)解释解释 OBJECTIVE FUNCTIO
9、N VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 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原料原料(yunlio)无剩余无剩余时间时间(shjin)无无剩余剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三
10、种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）第8页/共93页第九页，共93页。结果结果(ji(ji gu)gu)解释解释 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 PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATION
11、S=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益(xioy)”的增量的增量 原料增加原料增加1单位单位,利润利润(lrn)增增长长48 时间增加时间增加1单位单位,利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！第9页/共93页第十页，共93页。RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIA
12、BLE CURRENT 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最优解不变时目标函最
13、优解不变时目标函数系数允许变化数系数允许变化(binhu)范围范围 DO RANGE(SENSITIVITY)ANALYSIS?Yesx1系数系数(xsh)范范围围(64,96)x2系数系数(xsh)范围范围(48,72)A1获利增加到获利增加到 30元元/千克，应否改变生产计划千克，应否改变生产计划 x1系数由系数由24 3=72增增加加为为30 3=90，在在允许范围内允许范围内 不变！不变！(约束条件不变约束条件不变)第10页/共93页第十一页，共93页。结果结果(ji(ji gu)gu)解释解释 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ CO
14、EFFICIENT RANGES VARIABLE CURRENT 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 INFINI
15、TY 40.000000影子价格有意义时约束右端的影子价格有意义时约束右端的(dund)允许允许变化范围变化范围 原料原料(yunlio)最多增加最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)第11页/共93页第十二页，共93页。例例2 奶制品的生产销售奶制品的生产销售(xioshu)计划计划 在例在例1基础基础(jch)上深加工上深加工1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/公公斤斤 获利获利16元元/公斤公斤 0.8千
16、克千克B12小时小时,3元元1千千克克获利获利44元元/千千克克 0.75千克千克B22小时小时,3元元1千千克克获利获利32元元/千千克克 制订生产制订生产(shngchn)(shngchn)计划，使每天计划，使每天净利润最大净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投资？现小时时间，应否投资？现投资投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小时小时 至多至多100公斤公斤A1 B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？第12页/共93页第十三页，共93页。1桶桶牛奶牛奶 3千克千
17、克 A1 12小时小时 8小时小时 4千克千克 A2 或或获利获利24元元/千克千克 获利获利16元元/kg 0.8千克千克 B12小时小时,3元元1千克千克获利获利44元元/千克千克 0.75千克千克 B22小时小时,3元元1千克千克获利获利32元元/千克千克 出售出售(chshu)x1 千克千克 A1,x2 千克千克 A2，X3千克千克(qink)B1,x4千千克克(qink)B2原料原料(yunlio)供供应应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 x5千克千克 A1加工加工B1，x6千克千克 A2加工加工B2附
18、加约束附加约束 第13页/共93页第十四页，共93页。模型模型(mxng)(mxng)求求解解 软件软件(run(run jin)jin)实现实现 LINDO 6.1 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 DU
19、AL 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=2DO RANGE(SENSITIVITY)ANALYSIS?No第14页/共93页第十五页，共93页。OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001
20、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结果结果(ji(ji gu)gu)解释解释每天销售每天销售168 千克千克(qink)A2和和19.2 千克千克(qink)B1，利润利润3460.8（元
21、）（元）8桶牛奶桶牛奶(ni ni)加工成加工成A1，42桶牛奶桶牛奶(ni ni)加加工成工成A2，将得到的将得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均为紧约束为紧约束第15页/共93页第十六页，共93页。结果结果(ji(ji gu)gu)解释解释 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.
22、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增加增加1桶牛奶使利润桶牛奶使利润(lrn)增长增长3.1612=37.92增加增加(zngji)1小时小时时间使利润增长时间使利润增长3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应小时时间，应否投资？现投资否投资？现投资1
23、50元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，桶牛奶，可赚回可赚回189.6元。（大于元。（大于增加时间的利润增长）增加时间的利润增长）第16页/共93页第十七页，共93页。结果结果(ji(ji gu)gu)解释解释B1,B2的获利有的获利有10%的波动，对计划有无的波动，对计划有无(yu w)影影响响 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000
24、 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获利下降获利下降10%，超，超出出X3 系数允许系数允许(ynx)范围范围B2获利上升获利上升10%，超，超出出X4 系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产
25、计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，计算，会发现结果有很大变化。会发现结果有很大变化。第17页/共93页第十八页，共93页。4.2 自来水输送自来水输送(sh sn)与与货机装运货机装运生产生产(shngchn)、生活物资从若干供应点运送到一些、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；需求点，怎样安排输送方案使运费最小，或利润最大；运输运输(ynsh)问题问题各种类型的货物装箱，由于受体积、重量等限制，如何各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。搭配装载，使获利最高
26、，或装箱数量最少。第18页/共93页第十九页，共93页。其他费用其他费用:450:450元元/千吨千吨(qin dn)(qin dn)应如何分配水库供水量，公司应如何分配水库供水量，公司(n s)(n s)才能获才能获利最多？利最多？若水库供水量都提高一倍，公司利润可增加若水库供水量都提高一倍，公司利润可增加(zngji)(zngji)到多少？到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例例例1 1 自来水输送自来水输送自来水输送自来水输送收入：收入：900元元/千吨千吨 支支出出A：50B：60C：50
27、甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本本用用水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）第19页/共93页第二十页，共93页。总供水量：总供水量：160确定确定(qudng)送水方案使送水方案使利润最大利润最大问题问题(wnt)分分析析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40 总需求量总需求量(300)每个水库每个水库(shuk)(shuk)最大供水量都最大供水量都提高一倍提高一倍利润利润(lrn)=收入收入(900)其它费
28、用其它费用(450)引水管引水管理费理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C 类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变第23页/共93页第二十四页，共93页。求解求解(qi(qi ji)ji)OBJECTIVE FUNCTION VALUE 1)88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.0
29、00000 40.000000 X14 0.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 这类问题一般这类问题一般(ybn)称为称为“运运输问题输问题”(Transportation Problem)总总利利润润(lrn)(lrn)8870088700（元）（元）A(100)B(120)C
30、(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030第24页/共93页第二十五页，共93页。如何装运如何装运(zhungyn)，使本次，使本次飞行获利最飞行获利最大？大？三个货舱最大载重三个货舱最大载重(zizhng)(吨吨),最大容最大容积积(米米3)例例例例22货机货机货机货机(hu(huj)j)装运装运装运装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实
31、际载重必须与其最大载载重成比例重成比例 前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第25页/共93页第二十六页，共93页。决策决策(ju(juc)c)变量变量 xij-第第i 种货物种货物(huw)装入第装入第j 个货舱的重量个货舱的重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型模型(mxng)(mxng)假设假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；
32、多种货物可以混装，并保证不留空隙；模型建立模型建立 第26页/共93页第二十七页，共93页。货舱货舱(hucng)容容积积 目标函目标函数数(hnsh(hnsh)()(利利润润)约束约束条件条件货机货机(hu(hu j)j)装运装运模型建立模型建立 货货舱舱重重量量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第27页/共93页第二十八页，共93页。约约束束条条件件平衡平衡(pnghng)要要求求 货物货物(huw)供应供应 货机货机(hu j)(hu j)装运装运模型建立模型建立 10；680016；87008；5300 xi
33、j-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第28页/共93页第二十九页，共93页。OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.0000006
34、50.000000X423.0526320.000000X430.000000650.000000货物货物(huw)2(huw)2：前仓：前仓10,10,后后仓仓5 5；货物货物(huw)3:(huw)3:中仓中仓13,13,后仓后仓3 3；货物；货物(huw)4:(huw)4:中仓中仓3 3。货机货机(hu(hu j)j)装运装运模型模型(mxng)(mxng)求解求解 最大利润约最大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题的扩展运输问题的扩展第29页/共93页第三十页，共93页。如果生产某一类型汽车如果生产某一类型汽车(qch)
35、(qch)，则至少要生产，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例例例11汽车厂生产汽车厂生产汽车厂生产汽车厂生产(shngchn)(shngchn)计划计划计划计划 汽车厂生产三种汽车厂生产三种(sn zhn)类型的汽车，已知各类型每类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。量。小型小型 中型中型 大型大型 现有量现有量钢材（吨）钢材（吨）1.5 3 5 600劳动时间（小时）劳动时间（小时）280 250 400 60000利润（万元）利润（万元）2 3 4
36、 制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。4.3 汽车生产与原油采购汽车生产与原油采购第30页/共93页第三十一页，共93页。设每月生产小、中、大型汽设每月生产小、中、大型汽车的数量车的数量(shling)(shling)分别为分别为x1,x2,x3x1,x2,x3汽车厂生产汽车厂生产(shngchn)(shngchn)计计划划 模型模型(mxng)(mxng)建立建立 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4 线线性性规规划划模模型型(LP)第31页/共93页第三十二
37、页，共93页。模型模型(mx(mxng)ng)求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3 均为整数，重新均为整数，重新(chngxn)求解。求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果结果(ji gu)为小数，怎么办为小数，怎么办？1）舍去小数：取）舍去小数：取
38、x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值最优值632.2581相差不大。相差不大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通过比较可能得到更优的解。，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？第32页/共93页第三十三页，共93页。IP可用可用LINDO直接直接(zhji)求解求解整数整数(zhngsh)(zhngsh)规划规划(Integer(Integer Programming,Programming,简记简记IP)IP
39、)“gin 3”表示表示(biosh)“前前3个变个变量为整数量为整数”，等价于：，等价于：gin x1gin x2gin x3 IP 的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632 max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解模型求解 IP 结
40、果输出结果输出第33页/共93页第三十四页，共93页。其中其中3 3个子模型应去掉，然后逐一个子模型应去掉，然后逐一求解，比较求解，比较(bjio)(bjio)目标函数值，目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解：分解(fnji)为为8个个LP子模型子模型 汽车厂生产汽车厂生产(shngchn)(shngchn)计划计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0 或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610第34页/共93页第三十五页，共93页。LINDO
41、中中对对0-1变变量量(binling)的的限定：限定：int y1int y2int y3 方法方法2：引入：引入0-1变量变量(binling)，化为整，化为整数规划数规划 M为大的正数为大的正数(zhngsh)，可取，可取1000 OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则至
42、少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前 第35页/共93页第三十六页，共93页。NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解(qi ji)(如如LINGO,MATLAB)，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。方法方法(fngf)3：化为非线：化为非线性规划性规划 非线性规划非线性规划(guhu)(guhu)（Non-Linear ProgrammingNon-Linear Programming，简记，简记NLPNLP）实实践践表表明明，本本例
43、例仅仅当当初初值值非非常常接接近近上上面面方方法法算算出出的最优解时，才能得到正确的结果。的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第36页/共93页第三十七页，共93页。应如何安排原油的采购应如何安排原油的采购(cigu)(cigu)和加工和加工？例例例例22原油原油原油原油(yunyu)(yunyu)采采采采购与加工购与加工购与加工购与加工 市场上可买到不超过市场上可买到不超过15001500吨的原油吨的原油(yunyu)A(yunyu)A：购买量不超
44、过购买量不超过500500吨时的单价为吨时的单价为1000010000元元/吨；吨；购买量超过购买量超过500500吨但不超过吨但不超过10001000吨时，超过吨时，超过500500吨的吨的 部分部分80008000元元/吨；吨；购买量超过购买量超过10001000吨时，超过吨时，超过10001000吨的部分吨的部分60006000元元/吨。吨。售价售价4800元元/吨吨 售价售价5600元元/吨吨库存库存500吨吨 库存库存1000吨吨 汽油甲汽油甲(A 50%)原油原油A 原油原油B 汽油乙汽油乙(A 60%)第37页/共93页第三十八页，共93页。决策决策(ju(juc)c)变量变量
45、目标目标(mbi(mbio)o)函函数数问题问题(wn(wnt)t)分析分析 利润：销售汽油的收入利润：销售汽油的收入 -购买原油购买原油A的支出的支出 难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/吨吨 5.6千元千元/吨吨原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？第38页/共93页第三十九页，共93页。原油原油(yunyu)供应供应 约束约束条件条件
46、x 500吨单价吨单价(dnji)为为10千元千元/吨；吨；500吨吨 x 1000吨，超过吨，超过500吨的吨的8千元千元/吨；吨；1000吨吨 x 1500吨，超过吨，超过1000吨的吨的6千元千元/吨。吨。目标目标(mb(mbio)io)函数函数购买购买x ABx11x12x21x22库存库存500吨吨 库存库存1000吨吨 第39页/共93页第四十页，共93页。目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段对于用分段(fn dun)函数定义的函数定义的c(x)，一般的非线性规划软，一般的非线性规划软件也难以输入和求解；件也难以输入和求解；
47、想办法将模型化简，用现成的软件求解。想办法将模型化简，用现成的软件求解。汽油含原油汽油含原油(yunyu)A的的比例限制比例限制 约束约束条件条件甲甲(A 50%)A B 乙乙(A 60%)x11x12x21x22第40页/共93页第四十一页，共93页。x1,x2,x3 以价格以价格(jig)10,8,6(千元千元/吨吨)采购采购A的吨数的吨数目标目标(mb(mbio)io)函数函数 只有只有(zhyu)(zhyu)当以当以1010千元千元/吨的价格购买吨的价格购买x1=500(x1=500(吨吨)时，才时，才能以能以8 8千元千元/吨的价格购买吨的价格购买x2x2方法方法1 非线性规划模型非
48、线性规划模型，可以用，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元/吨吨增加约束增加约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3 第41页/共93页第四十二页，共93页。方法方法(fngf)1：LINGO求解求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12x+500;x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500
49、)*x3=0;x1500;x2500;x30;x110;x120;x210;x220;x10;x20;x30;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000
50、000E+00LINGO得到得到(d do)的是局部最优解，的是局部最优解，还能得到还能得到(d do)更好的解吗？更好的解吗？用库存用库存(kcn)(kcn)的的500500吨原油吨原油A A、500500吨原油吨原油B B生产汽油甲，不购买新的生产汽油甲，不购买新的原油原油A A，利润为，利润为4,8004,800千元。千元。第42页/共93页第四十三页，共93页。y1,y2,y3=1 以价格以价格(jig)10,8,6(千元千元/吨吨)采购采购A增增加加(zngji)约约束束方法方法(fng(fngf)2 f)2 0-1线性规划模型线性规划模型，可用，可用LINDO求解求解y1,y2,y