《数学建模优化模型选讲》由会员分享，可在线阅读，更多相关《数学建模优化模型选讲（80页珍藏版）》请在金锄头文库上搜索。
1、数学建模培训系列讲座数学建模培训系列讲座最优化与离散模型最优化与离散模型主讲主讲:()数学建模：最优化问题数学建模：最优化问题最优化问题大体分两类：最优化问题大体分两类：一类是求函数在一定约束条件下的极值一类是求函数在一定约束条件下的极值;另一类是求泛函的极值另一类是求泛函的极值.l这里的函数我们称之为这里的函数我们称之为目标函数目标函数.目标函数中的变量称之为目标函数中的变量称之为决策变量决策变量.约束条件约束条件是指问题对决策变量的限制条件是指问题对决策变量的限制条件,即决策变量的取值即决策变量的取值范围范围.约束条件常用一组关于决策变量的等式与不等式给出约束条件常用一组关于决策变量的等式
2、与不等式给出.如果目标函数有明显的表达式如果目标函数有明显的表达式,一般可用微分法一般可用微分法,变分法或动态规划等分析方变分法或动态规划等分析方法来求解法来求解(间接求优间接求优);如果目标函数的表达式过于复杂甚至根本没有明显的表如果目标函数的表达式过于复杂甚至根本没有明显的表达式达式,则可用数值方法或则可用数值方法或“试验最优化试验最优化”方法等直接方法来求解方法等直接方法来求解(直接求优直接求优).求函数极值的数值方法或试验化方法有时称为求函数极值的数值方法或试验化方法有时称为数学规划数学规划.数学规划除了数学规划除了线性规划线性规划外统称为外统称为非线性规划非线性规划.求解数学规划的软
3、件求解数学规划的软件:LINDO,LINGOLINDO(LinearINteractiveandDiscreteOptimizer)交互式的线性和离散优化求解器交互式的线性和离散优化求解器LINGO(LinearINteractiveandGeneralOptimizer)交互式的线性和通用优化求解器交互式的线性和通用优化求解器模型实例模型实例: :存贮模型存贮模型问问题题配件厂为装配线生产若干种产品，轮换产品时因更换设配件厂为装配线生产若干种产品，轮换产品时因更换设备要付生产准备费，产量大于需求时要付贮存费。该厂备要付生产准备费，产量大于需求时要付贮存费。该厂生产能力非常大，即所需数量可在很
4、短时间内产出。生产能力非常大，即所需数量可在很短时间内产出。已知某产品日需求量已知某产品日需求量100件，生产准备费件，生产准备费5000元，贮存费元，贮存费每日每件每日每件1元。试安排该产品的生产计划，即多少天生产元。试安排该产品的生产计划，即多少天生产一次（生产周期），每次产量多少，使总费用最小。一次（生产周期），每次产量多少，使总费用最小。要要求求不只是回答问题，而且要建立生产周期、产量与不只是回答问题，而且要建立生产周期、产量与需求量、准备费、贮存费之间的关系。需求量、准备费、贮存费之间的关系。第一讲第一讲 简单的优化模型简单的优化模型问题分析与思考问题分析与思考每天生产一次每天生产一
5、次，每次，每次100件，无贮存费，准备费件，无贮存费，准备费5000元。元。日需求日需求100件，准备费件，准备费5000元，贮存费每日每件元，贮存费每日每件1元。元。10天生产一次天生产一次，每次，每次1000件，贮存费件，贮存费900+800+100=4500元，准备费元，准备费5000元，总计元，总计9500元。元。20天生产一次天生产一次，每次，每次2000件，贮存费件，贮存费2900+2800+100=28500元，准备费元，准备费5000元，总计元，总计33500元。元。平均每天费用平均每天费用950元元平均每天费用平均每天费用1675元元平均每天费用平均每天费用5000元元周期短
6、，产量小周期短，产量小周期长，产量大周期长，产量大贮存费少，准备费多贮存费少，准备费多准备费少，贮存费多准备费少，贮存费多存在最佳的周期和产量，使平均费用（二者之和）最小存在最佳的周期和产量，使平均费用（二者之和）最小这是一个优化问题，关键在建立目标函数。这是一个优化问题，关键在建立目标函数。显然不能用一个周期的总费用作为目标函数显然不能用一个周期的总费用作为目标函数目标函数目标函数每天总费用的平均值每天总费用的平均值模模型型假假设设1.产品每天的需求量为常数产品每天的需求量为常数r；2.每次生产准备费为每次生产准备费为c1,每天每件产品贮存费为每天每件产品贮存费为c2；3.T天生产一次（周期
7、）天生产一次（周期）,每次生产每次生产Q件，当贮存量件，当贮存量为零时，为零时，Q件产品立即到来（生产时间不计）；件产品立即到来（生产时间不计）；建建模模目目的的设设 r, c1,c2已知，求已知，求T, Q使每天总费用的平均值最小。使每天总费用的平均值最小。4.为方便起见，时间和产量都作为连续量处理。为方便起见，时间和产量都作为连续量处理。模模型型建建立立0tq贮存量表示为时间的函数贮存量表示为时间的函数q(t)TQrt=0生产生产Q件，件，q(0)=Q,q(t)以以需求速率需求速率r递减，递减，q(T)=0.一周期一周期总费用总费用每天总费用平均值每天总费用平均值（目标函数）（目标函数）离
8、散问题连续化离散问题连续化一周期贮存费为一周期贮存费为A=QT/2模型求解模型求解求求T 使使模型分析模型分析模型应用模型应用c1=5000,c2=1，r=100T=10(天天),Q=1000(件件),C=1000(元元)回答问题回答问题经济批量订货公式经济批量订货公式（EOQ公式公式）每天需求量每天需求量r，每次订货费，每次订货费c1,每天每件贮存费每天每件贮存费c2，这就是经济学中著名的用于订货、供应、存贮情形的这就是经济学中著名的用于订货、供应、存贮情形的以上讨论的是不允许缺货的存贮模型以上讨论的是不允许缺货的存贮模型问：为什么不考虑生产费用？在什么条件下才不考虑？问：为什么不考虑生产费
9、用？在什么条件下才不考虑？ T天订货一次天订货一次(周期周期),每次订货每次订货Q件，当贮存量件，当贮存量降到零时，降到零时，Q件立即到货。件立即到货。总结总结则最优解为则最优解为:允许缺货的存贮模型允许缺货的存贮模型AB0qQrT1t当贮存量降到零时仍有需求当贮存量降到零时仍有需求r,出现缺货，造成损失出现缺货，造成损失原模型假设：贮存量降到零时原模型假设：贮存量降到零时Q件件立即生产出来立即生产出来(或立即到货或立即到货)现假设：允许缺货现假设：允许缺货,每天每件缺货损失费每天每件缺货损失费c3,缺货需补足缺货需补足T一周期一周期贮存费贮存费一周期一周期缺货费缺货费周期周期T, t=T1贮
10、存量降到零贮存量降到零一周期总费用一周期总费用每天总费用每天总费用平均值平均值（目标函数）（目标函数）一周期总费用一周期总费用求求T ,Q 使使为与为与不允许缺货的存贮模型不允许缺货的存贮模型相比，相比，T记作记作T ,Q记作记作Q允许允许缺货缺货模型模型0qQ rT1tT注意：缺货需补足注意：缺货需补足Q 每周期初的存贮每周期初的存贮量量R每周期的生产量每周期的生产量R（或订货量）（或订货量）Q不允许缺货时的产量不允许缺货时的产量(或订货量或订货量)不允不允许缺许缺货模货模型型记记允许允许缺货缺货模型模型不不允允许许缺缺货货下面将进入数学规划模型下面将进入数学规划模型数学规划模型数学规划模型
11、 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x) 0约束条约束条件件多元函数多元函数条件极值条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析第二讲第二讲 数学规划模型数学规划模型 企业生产计划企业生产计划2.1奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条
12、件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。用参数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题例例1加工奶制品的生产计划加工奶制品的生产计划问题问题:一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1,A2两种奶制品两种奶
13、制品,1桶牛奶桶牛奶可以在设备甲上用可以在设备甲上用12小时加工成小时加工成3公斤公斤A1,或者地设备乙上加或者地设备乙上加工成工成4公斤公斤A2.根据市场需求根据市场需求,生产的生产的A1,A2全部能售出全部能售出,且每公且每公斤斤A1获利获利24元元,每公斤每公斤A2获利获利16元元.现在加工厂每天能得到现在加工厂每天能得到50桶牛奶的供应桶牛奶的供应,每天正式工人总的劳动时间为每天正式工人总的劳动时间为480小时小时,并且并且设备甲每天最多能加工设备甲每天最多能加工100公斤公斤A1,设备乙的加工能力没有限制设备乙的加工能力没有限制.试为该厂制定一个生产计划试为该厂制定一个生产计划,使每
14、天获利最大使每天获利最大,并进一步讨并进一步讨论以下论以下3个附加问题个附加问题:1)若用若用35元可以买到一桶牛奶元可以买到一桶牛奶,应否作这项投资应否作这项投资?若投资若投资,每每天最多能购买多少桶牛奶天最多能购买多少桶牛奶?2)若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间,付给临时工人的工付给临时工人的工资最多是每小时几元资最多是每小时几元?3)由于市场需求变化由于市场需求变化,每公斤每公斤A1的获利增加到的获利增加到30元元,应否改变应否改变生产计划生产计划?例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24
15、元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1
16、获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天模型分析与假设模型分析与假设 比比例例性性可可加加性性连续性连续性xi对目标函数的对目标函数的“贡献贡献”与与xi取值成取值成正比正比xi对约束条件的对约束条件的“贡献贡献”与与xi取值成取值成正比正比xi对目标函数的对目标函数的“贡献贡献”与与xj取值无取值无关关xi对约束条件的对约束条件的“贡献贡献”与与xj取值无取值无
17、关关xi取值连续取值连续A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与各自产量无关的常数时间是与各自产量无关的常数A1,A2每公斤的获利是与相每公斤的获利是与相互产量无关的常数互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与相互产量无关的常数时间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数线性规划模型线性规划模型模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600
18、z=c (常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个极点取得。形的某个极点取得。 模型求解模型求解 软件实现软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.0000
19、00X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACK
20、ORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000
21、000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付
22、出的工资最多每小时几元？2元！元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.00000
23、04100.000000INFINITY40.000000最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/千克，应否改变生产计划千克，应否改变生产计划x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABL
24、ECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多
25、增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)问题问题:例例1给出的生产条件给出的生产条件,利润利润,资源均不变资源均不变.为增加赢利为增加赢利,对对A1和和A2进行深加工进行深加工.用用2小时和小时和3元加工费可将元加工费可将A1加工成加工成0.8公斤公斤B1,也可将也可将1公斤公斤A2加工成加工成0.75公斤公斤B2.每公斤每公斤B1获利获利44元元,每公每公斤斤B2获利获利32元元.试为该厂制定一个生产计划试为该厂制定一个生产计划,使每天获利最大使每天获利最大,并讨论以下问题并讨
26、论以下问题:1)若用若用30元可以买到一桶牛奶元可以买到一桶牛奶,投资投资3元可增加元可增加1小时劳动时小时劳动时间间,应否作这项投资应否作这项投资?若每天投资若每天投资150元元,可赚回多少可赚回多少?2)每公斤每公斤B1,B2获利经常有获利经常有10%的波动的波动,对制定的计划有无影对制定的计划有无影响响?若每公斤若每公斤B1获利下降获利下降10%,计划应变化吗计划应变化吗?例例2奶制品的生产销售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4公斤公斤A2或或获利获利24元元/公斤公斤获利获利16元元/公斤公斤0.8千克千克B
27、12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4公斤公斤A2或或获利获利24元元/公斤公斤获利获利16元元/公斤公斤0.8千克千克B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回
28、多少？50桶牛奶桶牛奶,480小时小时至多至多100公斤公斤A1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4千克千克A2或或获利获利24元元/千克千克获利获利16元元/kg0.8千克千克 B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克出售出售x1千克千克A1,x2千克千克A2，X3千克千克B1,x4千克千克B2原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束
29、条件条件非负约束非负约束 x5千克千克A1加工加工B1，x6千克千克A2加工加工B2附加约束附加约束 模型求解模型求解 软件实现软件实现 LINDO6.1MAX24x1+16x2+44x3+32x4-3x5-3x6st2)4x1+3x2+4x5+3x66003)4x1+2x2+6x5+4x64804)x1+x51005)x3-0.8x5=06)x4-0.75x6=0endOBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000
30、X40.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? NoMAX24x1+16x2+44x3+32x4-3x5-3x6st2)4x1+3x2+4x5+3x66003)4x1+2x2+6x5+4x64804)x1+x
31、51005)x3-0.8x5=06)x4-0.75x6=0endOBJECTIVEFUNCTIONVALUE1)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.00000
32、06)0.00000032.000000NO.ITERATIONS=2结果解释结果解释每天销售每天销售168千克千克A2和和19.2千克千克B1，利润利润3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A2，将得到的将得到的24千克千克A1全部全部加工成加工成B1除加工能力外均除加工能力外均为紧约束为紧约束结果解释结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.000
33、0000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000增加增加1桶牛奶使利润增桶牛奶使利润增长长3.1612=37.92增加增加1小时时间使利小时时间使利润增长润增长3.2630元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，小时时间，应否投资？现投资应否投资？现投资150元，可赚回多少？元，可赚回多
34、少？投资投资150元增加元增加5桶牛奶，桶牛奶，可赚回可赚回189.6元。（大于元。（大于增加时间的利润增长）增加时间的利润增长）结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X
35、432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITYDORANGE(SENSITIVITY)ANALYSIS? YesB1获利下降获利下降10%，超，超出出X3系数允许范围系数允许范围B2获利上升获利上升10%，超，超出出X4系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，计算，会发现结果有很大变化。会发现结果有很大变化。2.1 饮料厂的生产与检修饮料厂的生产与检修问题问题:某饮料厂确定了未来
36、四周对该饮料的需求量某饮料厂确定了未来四周对该饮料的需求量,以及未来以及未来四周本厂的生产能力和生产成本四周本厂的生产能力和生产成本(如下表所示如下表所示).每周满足需求后每周满足需求后周次周次需求需求(千箱千箱)生产能力生产能力(千箱千箱)成本成本(千元千元/千箱千箱)115305.0225405.1335455.4425205.5合计合计100135有剩余时有剩余时,要支出存要支出存贮费贮费,为每周每千箱为每周每千箱0.2千元千元.问应如何安问应如何安排生产排生产,在满足市场在满足市场需求的条件下需求的条件下,使四使四周总费用最小周总费用最小?单阶段生产计划单阶段生产计划多阶段生产计划多阶
37、段生产计划企业生产计划企业生产计划外部需求和内部外部需求和内部资源随时间变化资源随时间变化问题分析问题分析除第除第4周外每周的生产周外每周的生产能力超过每周的需求；能力超过每周的需求；生产成本逐周上升；生产成本逐周上升；前几周应多生产一些。前几周应多生产一些。周次周次需求需求能力能力11530225403354542520合计合计100135成本成本5.05.15.45.5 饮料厂在第饮料厂在第1周开始时没有库存；周开始时没有库存； 从费用最小考虑从费用最小考虑, , 第第4周末不能有库存；周末不能有库存； 周末有库存时需支出一周的存贮费；周末有库存时需支出一周的存贮费； 每周末的库存量等于下
38、周初的库存量。每周末的库存量等于下周初的库存量。 模模型型假假设设 目标目标函数函数约束约束条件条件产量、库存与需求平衡产量、库存与需求平衡 决策变量决策变量 能力限制能力限制 非负限制非负限制 模型建立模型建立x1x4：第：第14周周的生产量的生产量y1y3：第：第13周末周末库存量库存量周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5存贮费存贮费: :0.2( (千元千元/ /周周千箱千箱) ) 模型求解模型求解 4周生产计划的总费用为周生产计划的总费用为528(千元千元)最优解：最优解： x1x4：15，40，25，20；y1y3： 0，1
39、5，5.周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5产量产量15402520库存库存01550LINDO求解求解检修计划检修计划0-1变量变量wt：wt=1=1检修安排在第检修安排在第t周周(t=1,2,3,4） 在在4周内安排一次设备检修，占用当周内安排一次设备检修，占用当周周15千箱生产能力，能使检修后每周增千箱生产能力，能使检修后每周增产产5千箱，检修应排在哪一周千箱，检修应排在哪一周? ?检修安排在任一周均可检修安排在任一周均可:周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5能能力力限
40、限制制 产量、库存与需求平衡约束条件不变产量、库存与需求平衡约束条件不变 增加检修约束条件：增加检修约束条件：目标函数不变目标函数不变LINDO求解求解总费用由总费用由528千元降千元降为为527千元千元检修所导致的生产能力提高的作用检修所导致的生产能力提高的作用,需要更长的时间才能得到充分体现。需要更长的时间才能得到充分体现。最优解：最优解： w1= =1,w2,w3,w4=0; x1x4：15, ,45, ,15, ,25；y1y3：0, ,20, ,0.min5.0x1+5.1x2+5.4x3+5.5x4+0.2y1+0.2y2+0.2y3st2)x1-y1=153)x2+y1-y2=2
41、54)x3+y2-y3=355)x4+y3=256)x1+15w130x2+15w2-5w140x3+15w3-5w1-5w245x4+15w4-5w1-5w2-5w320w1+w2+w3+w4=1endintw1intw2intw3intw4例例2饮料的生产批量问题饮料的生产批量问题 安排生产计划安排生产计划,满足每周的需求满足每周的需求,使使4周总费用最小。周总费用最小。存贮费存贮费: :每周每千箱饮料每周每千箱饮料 0.2千元。千元。 饮料厂使用同一条生产线轮流生产饮料厂使用同一条生产线轮流生产多种多种饮料。饮料。若某周开工生产若某周开工生产某种某种饮料饮料,需支出需支出生产准备费生产准
42、备费8千元。千元。某种饮料某种饮料4周的需求量、生产能力和成本周的需求量、生产能力和成本周次周次需求量需求量(千箱千箱)生产能力生产能力(千箱千箱)成本成本(千元千元/千箱千箱)115305.0225405.1335455.4425205.5合计合计100135问问题题:生产批量问题生产批量问题考虑与产量无关的固定费用考虑与产量无关的固定费用给优化模型求解带来新的困难给优化模型求解带来新的困难Min8w1+8w2+8w3+8w4+5x1+5.1x2+5.4x3+5.5x4+0.2y1+0.2y2+0.2y3st2)x1-y1=153)y1+x2-y2=254)y2+x3-y3=355)y3+x
43、4=256)x1-30w107)x2-40w208)x3-45w309)x4-20w40endintw1intw2intw3intw4最优解：最优解：x1x4：15，40，45，0；总费用：总费用：554.0(千元千元)用用LINDO求解求解决策变量决策变量 x1x4：第：第14周周的生产量的生产量y1y3：第：第13周末周末库存量库存量0-1变量变量wt：wt=1=1第第t周周开工生产开工生产(t=1,2,3,4）生产批量问题的一般提法生产批量问题的一般提法ct 时段时段t 生产费用生产费用( (元元/ /件件) )；ht 时段时段t ( (末末) )库存费库存费( (元元/ /件件) )；
44、st 时段时段t 生产准备费生产准备费( (元元) )；dt 时段时段t 市场需求市场需求( (件件) )；Mt 时段时段t 生产能力生产能力( (件件) )。假设初始库存为假设初始库存为0制订生产计划制订生产计划, , 满满足需求足需求, ,并使并使T个时个时段的总费用最小。段的总费用最小。决策变量决策变量 xt 时段时段t 生产量；生产量；yt 时段时段t ( (末末) )库存量；库存量；wt =1时段时段t 开工开工生产生产 ( (wt =0不开工不开工) )。目标目标约束约束混合混合0-1规划模型规划模型 生产批量问题的一般提法生产批量问题的一般提法下面将进入离散模型下面将进入离散模型
45、 离散模型：差分方程、整数规划、离散模型：差分方程、整数规划、图论、对策论、网络流、图论、对策论、网络流、 分析社会经济系统的有力工具分析社会经济系统的有力工具 只用到代数、集合及图论（少许）的知识只用到代数、集合及图论（少许）的知识第三讲第三讲 离散模型离散模型3.1层次分析模型层次分析模型背背景景日常工作、生活中的决策问题日常工作、生活中的决策问题涉及经济、社会等方面的因素涉及经济、社会等方面的因素作比较判断时人的主观选择起相当大作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化的作用，各因素的重要性难以量化Saaty于于1970年代提出层次分析法年代提出层次分析法AHP(An
46、alyticHierarchyProcess)AHP一种一种定性与定量相结合的、定性与定量相结合的、系统化、层次化系统化、层次化的分析方法的分析方法目标层目标层O(选择旅游地选择旅游地)P2黄山黄山P1桂林桂林P3北戴河北戴河准则层准则层方案层方案层C3居住居住C1景色景色C2费用费用C4饮食饮食C5旅途旅途一一. . 层次分析法的基本步骤层次分析法的基本步骤例例. . 选择旅游地选择旅游地如何在如何在3 3个目的地中按照景色、个目的地中按照景色、费用、居住条件等因素选择费用、居住条件等因素选择. .“选择旅游地选择旅游地”思维过程的归思维过程的归纳纳将决策问题分为将决策问题分为3个层次：目标
47、层个层次：目标层O，准则层，准则层C，方案层方案层P；每层有若干元素，；每层有若干元素，各层元素间的关系各层元素间的关系用相连的直线表示。用相连的直线表示。通过相互比较确定各准则对目标的权重，及各方通过相互比较确定各准则对目标的权重，及各方案对每一准则的权重。案对每一准则的权重。将上述两组权重进行综合，确定各方案对目标的将上述两组权重进行综合，确定各方案对目标的权重。权重。层次分析法将定性分析与定量分析结合起来完层次分析法将定性分析与定量分析结合起来完成以上步骤，给出决策问题的定量结果。成以上步骤，给出决策问题的定量结果。层次分析法的基本步骤层次分析法的基本步骤成对比较阵成对比较阵和权向量和权
48、向量元素之间两两对比，对比采用相对尺度元素之间两两对比，对比采用相对尺度设要比较各准则设要比较各准则C1,C2,Cn对目标对目标O的重要性的重要性A成对比较阵成对比较阵A是正互反阵是正互反阵要由要由A确定确定C1,Cn对对O的权向量的权向量选选择择旅旅游游地地成对比较的不一致情况成对比较的不一致情况一致比较一致比较不一致不一致允许不一致，但要确定不一致的允许范围允许不一致，但要确定不一致的允许范围考察完全一致的情况考察完全一致的情况成对比较阵和权向量成对比较阵和权向量成对比较完全一致的情况成对比较完全一致的情况满足满足的正互反阵的正互反阵A称称一致阵一致阵，如，如A的秩为的秩为1，A的唯一非零
49、特征根为的唯一非零特征根为nA的任一列向量是对应于的任一列向量是对应于n 的特征向量的特征向量A的归一化特征向量可作为权向量的归一化特征向量可作为权向量对于不一致对于不一致( (但在允许范围内但在允许范围内) )的成对的成对比较阵比较阵A，建议用对应于最大特征根，建议用对应于最大特征根 的特征向量作为权向量的特征向量作为权向量w ，即，即一致阵一致阵性质性质成对比较阵和权向量成对比较阵和权向量2468比较尺度比较尺度aij Saaty等人提出等人提出19尺度尺度aij 取值取值1,2,9及其互反数及其互反数1,1/2,1/9尺度尺度13579相同相同稍强稍强强强明显强明显强绝对强绝对强aij
50、= 1,1/2,1/9的重要性与上面相反的重要性与上面相反心理学家认为成对比较的因素不宜超过心理学家认为成对比较的因素不宜超过9个个用用13,15,117,1p9p(p=2,3,4,5),d+0.1d+0.9(d=1,2,3,4)等等27种比较尺度对若干实例构造成对比较种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，阵，算出权向量，与实际对比发现，19尺度较优。尺度较优。便于定性到定量的转化：便于定性到定量的转化：成对比较阵和权向量成对比较阵和权向量一致性检验一致性检验对对A确定不一致的允许范围确定不一致的允许范围已知：已知：n 阶一致阵的唯一非零特征根为阶一致阵的唯一非零特征
51、根为n可证：可证：n阶正互反阵最大特征根阶正互反阵最大特征根 n,且且 =n时为一致阵时为一致阵定义一致性指标定义一致性指标:CI 越大，不一致越严重越大，不一致越严重RI0 0 0.58 0.90 1.12 1.24 1.32 1.41 1.45 1.49 1.51n1 234567891110为衡量为衡量CI 的大小，引入的大小，引入随机一致性指标随机一致性指标RI随机模随机模拟得到拟得到aij,形成形成A，计算，计算CI 即得即得RI。定义一致性比率定义一致性比率CR = CI/RI当当CR0.1时，通过一致性检验时，通过一致性检验Saaty的结果如下的结果如下“选择旅游地选择旅游地”中
52、中准则层对目标的权准则层对目标的权向量及一致性检验向量及一致性检验准则层对目标的准则层对目标的成对比较阵成对比较阵最大特征根最大特征根 =5.073权向量权向量( (特征向量特征向量) )w =(0.263,0.475,0.055,0.090,0.110)T一致性指标一致性指标随机一致性指标随机一致性指标RI=1.12(查表查表)一致性比率一致性比率CR=0.018/1.12=0.0163)个顶点的双向连通竞赛图，存在个顶点的双向连通竞赛图，存在正整数正整数r，使邻接矩阵，使邻接矩阵A 满足满足Ar 0，A称称素阵素阵素阵素阵A的最大特征根为正单的最大特征根为正单根根 ，对应正特征向量，对应正特征向量s，且且排名为排名为1，2，4，3用用s排名排名1234(4)1,2,3,4?1234566支球队比赛结果支球队比赛结果排名次序为排名次序为1，3，2，5，4，6
