数学建模优化模型选讲-课件.ppt

1、 数学建模培训系列讲座数学建模培训系列讲座 最优化与离散模型最优化与离散模型数学建模：最优化问题数学建模：最优化问题最优化问题大体分两类：最优化问题大体分两类：一类是求函数在一定约束条件下的极值一类是求函数在一定约束条件下的极值;另一类是求泛函的极值另一类是求泛函的极值.l 这里的函数我们称之为这里的函数我们称之为目标函数目标函数.目标函数中的变量称之为目标函数中的变量称之为决策变量决策变量.约束条件约束条件是指问题对决策变量的限制条件是指问题对决策变量的限制条件,即决策变量的取值即决策变量的取值范围范围.约束条件常用一组关于决策变量的等式与不等式给出约束条件常用一组关于决策变量的等式与不等式

2、给出.如果目标函数有明显的表达式如果目标函数有明显的表达式,一般可用微分法一般可用微分法,变分法或动态规划等分析方变分法或动态规划等分析方法来求解法来求解(间接求优间接求优);如果目标函数的表达式过于复杂甚至根本没有明显的表如果目标函数的表达式过于复杂甚至根本没有明显的表达式达式,则可用数值方法或则可用数值方法或“试验最优化试验最优化”方法等直接方法来求解方法等直接方法来求解(直接求优直接求优).求函数极值的数值方法或试验化方法有时称为求函数极值的数值方法或试验化方法有时称为数学规划数学规划.数学规划除了数学规划除了线性规划线性规划外统称为外统称为非线性规划非线性规划.求解数学规划的软件求解数

3、学规划的软件:LINDO,LINGOLINDO(Linear INteractive and Discrete Optimizer)交互式的线性和离散优化求解器交互式的线性和离散优化求解器 LINGO(Linear INteractive and General Optimizer)交互式的线性和通用优化求解器交互式的线性和通用优化求解器模型实例模型实例:存贮模型存贮模型问问 题题配件厂为装配线生产若干种产品，轮换产品时因更换设配件厂为装配线生产若干种产品，轮换产品时因更换设备要付生产准备费，产量大于需求时要付贮存费。该厂备要付生产准备费，产量大于需求时要付贮存费。该厂生产能力非常大，即所需数

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元元平均每天费用平均每天费用50

6、00元元 周期短，产量小周期短，产量小 周期长，产量大周期长，产量大贮存费少，准备费多贮存费少，准备费多准备费少，贮存费多准备费少，贮存费多存在最佳的周期和产量，使平均费用（二者之和）最小存在最佳的周期和产量，使平均费用（二者之和）最小 这是一个优化问题，关键在建立目标函数。这是一个优化问题，关键在建立目标函数。显然不能用一个周期的总费用作为目标函数显然不能用一个周期的总费用作为目标函数目标函数目标函数每天总费用的平均值每天总费用的平均值模模 型型 假假 设设1.产品每天的需求量为常数产品每天的需求量为常数 r；2.每次生产准备费为每次生产准备费为 c1,每天每件产品贮存费为每天每件产品贮存费

7、为 c2；3.T天生产一次（周期）天生产一次（周期）,每次生产每次生产Q件，件，当贮存量当贮存量 为零时，为零时，Q件产品立即到来（生产时间不计）；件产品立即到来（生产时间不计）；建建 模模 目目 的的设设 r,c1,c2 已知，求已知，求T,Q 使每天总费用的平均值最小。使每天总费用的平均值最小。4.为方便起见，时间和产量都作为连续量处理。为方便起见，时间和产量都作为连续量处理。模模 型型 建建 立立0tq贮存量表示为时间的函数贮存量表示为时间的函数 q(t)TQrt=0生产生产Q件，件，q(0)=Q,q(t)以以需求速率需求速率r递减，递减，q(T)=0.一周期一周期总费用总费用TQccC

8、221每天总费用平均值每天总费用平均值（目标函数）（目标函数）2)(21rTcTcTCTC离散问题连续化离散问题连续化AcdttqcT202)(一周期贮存费为一周期贮存费为A=QT/22221rTcc rTQ 模型求解模型求解Min2)(21rTcTcTC求求 T 使使0dTdC212crcrTQ212rccT 模型分析模型分析QTc,1QTc,2QTr,模型应用模型应用c1=5000,c2=1，r=100T=10(天天),Q=1000(件件),C=1000(元元)回答问题回答问题经济批量订货公式经济批量订货公式（EOQ公式公式）212rccT 212crcrTQ每天需求量每天需求量 r，每次

9、订货费每次订货费 c1,每天每件贮存费每天每件贮存费 c2，这就是经济学中著名的用于订货、供应、存贮情形的这就是经济学中著名的用于订货、供应、存贮情形的以上讨论的是不允许缺货的存贮模型以上讨论的是不允许缺货的存贮模型 问：为什么不考虑生产费用？在什么条件下才不考虑？问：为什么不考虑生产费用？在什么条件下才不考虑？T天订货一次天订货一次(周期周期),每次订货每次订货Q件，当贮存量件，当贮存量降到零时，降到零时，Q件立即到货。件立即到货。总结总结则最优解为则最优解为:允许缺货的存贮模型允许缺货的存贮模型AB0qQrT1t当贮存量降到零时仍有需求当贮存量降到零时仍有需求r,出现缺货，造成损失出现缺货

10、，造成损失原模型假设：贮存量降到零时原模型假设：贮存量降到零时Q件件立即生产出来立即生产出来(或立即到货或立即到货)现假设：允许缺货现假设：允许缺货,每天每件缺货损失费每天每件缺货损失费 c3,缺货需补足缺货需补足T1rTQ AcdttqcT2021)(一周期一周期贮存费贮存费BcdttqcTT331)(一周期一周期缺货费缺货费周期周期T,t=T1贮存量降到零贮存量降到零2)(2213121TTrcQTccC一周期总费用一周期总费用rTQrTcrTQcTcTCQTC2)(2),(232210,0QCTC每天总费用每天总费用平均值平均值（目标函数）（目标函数）213121)(2121TTrcQT

11、ccC一周期总费用一周期总费用Min),(QTC求求 T,Q 使使332212cccrccT323212ccccrcQ为与为与不允许缺货的存贮模型不允许缺货的存贮模型相比，相比，T记作记作T,Q记作记作Q332212cccrccT323212ccccrcQ允许允许缺货缺货模型模型0qQ rT1tT注意：缺货需补足注意：缺货需补足Q 每周期初的存贮量每周期初的存贮量R每周期的生产量每周期的生产量R（或订货量）或订货量）332212ccccrcTrRQ不允许缺货时的产量不允许缺货时的产量(或订货量或订货量)QR 212rccT 212crcrTQ不允不允许缺许缺货模货模型型QQTT,332ccc

12、记记1QQTT,13cQQTT,332212cccrccT323212ccccrcQ允许允许缺货缺货模型模型不不允允许许缺缺货货3c 下面将进入数学规划模型下面将进入数学规划模型数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(.),(),()(1或x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件多元函数多元函数条件极值条件极值 决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大 最优解在可行域最优解在可行域的边界上取得的边界上取得 数数学学规规划划线性规划线性规划非线性规划非线性规划

13、整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析第二讲第二讲 数学规划模型数学规划模型 企业生产计划企业生产计划2.1 奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。用参数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化

14、，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题例例1 加工奶制品的生产计划加工奶制品的生产计划问题问题:一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1,A2两种奶制品两种奶制品,1桶牛奶桶牛奶可以在设备甲上用可以在设备甲上用12小时加工成小时加工成3公斤公斤A1,或者地设备乙上加或者地设备乙上加工成工成4公斤公斤A2.根据市场需求根据市场需求,生产的生产的A1,A2全部能售出全部能售出,且每公且每公斤斤A1获利获利24元元,每公斤每公斤A2获利获利16元元.现在加工厂每天能得到

15、现在加工厂每天能得到50桶牛奶的供应桶牛奶的供应,每天正式工人总的劳动时间为每天正式工人总的劳动时间为480小时小时,并且并且设备甲每天最多能加工设备甲每天最多能加工100公斤公斤A1,设备乙的加工能力没有限设备乙的加工能力没有限制制.试为该厂制定一个生产计划试为该厂制定一个生产计划,使每天获利最大使每天获利最大,并进一步并进一步讨论以下讨论以下3个附加问题个附加问题:1)若用若用35元可以买到一桶牛奶元可以买到一桶牛奶,应否作这项投资应否作这项投资?若投资若投资,每每天最多能购买多少桶牛奶天最多能购买多少桶牛奶?2)若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间,付给临时工

16、人的工付给临时工人的工资最多是每小时几元资最多是每小时几元?3)由于市场需求变化由于市场需求变化,每公斤每公斤A1的获利增加到的获利增加到30元元,应否改变应否改变生产计划生产计划?例例1 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时

17、工人，付出的工资最多是每小时几元?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

18、小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析与假设模型分析与假设 比比例例性性 可可加加性性 连续性连续性 xi对目标函数的对目标函数的“贡献贡献”与与xi取值取值成正比成正比 xi对约束条件的对约束条件的“贡献贡献”与与xi取值取值成正比成正比 xi对目标函数的对目标函数的“贡献贡献”与与xj取值取值无关无关 xi对约束条件的对约束条件的“贡献贡献”与与xj取值取值无关无关 xi取取值连续值连续 A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与各自产量无关的常数时间

19、是与各自产量无关的常数A1,A2每公斤的获利是与相每公斤的获利是与相互产量无关的常数互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和的数量和时间是与相互产量无关的常数时间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数 线性规划模型线性规划模型模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:,0:2514xlxl216472xxzMax目标目标函数函数 Z=0Z=2400Z=3600z=c(

20、常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个极点取得。形的某个极点取得。模型求解模型求解 软件实现软件实现 LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.00

21、0000 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桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润利润3360元。元。结果解释结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.00000

22、0 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原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释 OBJECTIVE FUNCTION

23、 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最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量 原料增加原料增加1单位单位,利润增长利润增长48 时间增加时间增加1单位单位,利润增长利润增长2 加工能力增长不影响利润加工

24、能力增长不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 48,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！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.000000 16.000000 RIGHTHAND SI

25、DE 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最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围 DO RANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到 30元元/千克，应否改变生产计划千克，应否改变生

26、产计划 x1系数由系数由24 3=72增加增加为为30 3=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.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOW

27、ABLE 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桶桶!(目标函数不变目标函数不变)问题问题:例例1给出的生产条件给出的生产条件,利润利润,资源均不变资源均不变.

28、为增加赢利为增加赢利,对对A1和和A2进行深加工进行深加工.用用2小时和小时和3元加工费可将元加工费可将A1加工成加工成0.8公斤公斤B1,也可将也可将1公斤公斤A2加工成加工成0.75公斤公斤B2.每公斤每公斤B1获利获利44元元,每公斤每公斤B2获利获利32元元.试为该厂制定一个生产计划试为该厂制定一个生产计划,使每天获利最大使每天获利最大,并讨论以下问题并讨论以下问题:1)若用若用30元可以买到一桶牛奶元可以买到一桶牛奶,投资投资3元可增加元可增加1小时劳动时小时劳动时间间,应否作这项投资应否作这项投资?若每天投资若每天投资150元元,可赚回多少可赚回多少?2)每公斤每公斤B1,B2获利

29、经常有获利经常有10%的波动的波动,对制定的计划有无影对制定的计划有无影响响?若每公斤若每公斤B1获利下降获利下降10%,计划应变化吗计划应变化吗?例例2 奶制品的生产销售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获利24元元/公斤公斤 获利获利16元元/公斤公斤 0.8千克千克B12小时小时,3元元1千克千克获利获利44元元/千克千克 0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克 1桶桶牛奶牛奶 3千克千克A1 12小时小时 8小时小时 4公斤公斤A2 或或获利获

30、利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%的波动，对计划有无影响？的波动，对计划有无影响？1桶桶牛奶牛奶 3千克千克 A1 12小

31、时小时 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原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 0,61xx x5千克千克 A1加工加工B1，x6千克千克 A2加工加工B26543213332441624xxxxxxzMax5

32、0436251xxxx48022)(2)(4656251xxxxxx10051 xx附加约束附加约束 5380 x.x64750 x.x 模型求解模型求解 软件实现软件实现 LINDO 6.1 5043)26251xxxx48022)(2)(4)3656251xxxxxx600334)26521xxxx44804624)36521xxxx MAX 24x1+16x2+44x3+32x4-3x5-3x6 st2)4x1+3x2+4x5+3x66003)4x1+2x2+6x5+4x64804)x1+x51005)x3-0.8x5=06)x4-0.75x6=0end OBJECTIVE FUNCTI

33、ON 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.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.0000

34、00 32.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No MAX 24x1+16x2+44x3+32x4-3x5-3x6 st2)4x1+3x2+4x5+3x66003)4x1+2x2+6x5+4x64804)x1+x51005)x3-0.8x5=06)x4-0.75x6=0end OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000

35、000 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桶桶牛奶加工成牛

36、奶加工成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.000

37、000 3.160000 3)0.000000 3.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元。（大于元

38、。（大于增加时间的利润增长）增加时间的利润增长）结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT 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

39、2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE(SENSITIVITY)ANALYSIS?YesB1获利下降获利下降10%，超，超出出X3 系数允许范围系数允许范围B2获利上升获利上升10%，超，超出出X4 系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6 计算，计算，会发现结果有很大变化。会发现结果有很大变化。2.1 饮料厂的生产与检修饮料厂的生产与检修 问题问题:某饮料厂确

40、定了未来四周对该饮料的需求量某饮料厂确定了未来四周对该饮料的需求量,以及未来以及未来四周本厂的生产能力和生产成本四周本厂的生产能力和生产成本(如下表所示如下表所示).每周满足需求后每周满足需求后周次周次需求需求(千箱千箱)生产能力生产能力(千箱千箱)成本成本(千元千元/千箱千箱)115305.0225405.1335455.4425205.5合计合计100135有剩余时有剩余时,要支出存要支出存贮费贮费,为每周每千箱为每周每千箱0.2千元千元.问应如何安问应如何安排生产排生产,在满足市场在满足市场需求的条件下需求的条件下,使四使四周总费用最小周总费用最小?单阶段生产计划单阶段生产计划多阶段生产

41、计划多阶段生产计划 企业生产计划企业生产计划外部需求和内部外部需求和内部资源随时间变化资源随时间变化问题分析问题分析 除第除第4周外每周的生产周外每周的生产能力超过每周的需求；能力超过每周的需求；生产成本逐周上升；生产成本逐周上升；前几周应多生产一些。前几周应多生产一些。周次周次需求需求能力能力11530225403354542520合计合计100135成本成本5.05.15.45.5 饮料厂在第饮料厂在第1周开始时没有库存；周开始时没有库存；从费用最小考虑从费用最小考虑,第第4周末不能有库存；周末不能有库存；周末有库存时需支出一周的存贮费；周末有库存时需支出一周的存贮费；每周末的库存量等于下

42、周初的库存量。每周末的库存量等于下周初的库存量。模模型型假假设设 目标目标函数函数约束约束条件条件产量、库存与需求平衡产量、库存与需求平衡 决策变量决策变量 )(2.05.54.51.50.53214321yyyxxxxzMin1511 yx25212yyx35323yyx2534 yx20,4540,304321xxxx能力限制能力限制 非负限制非负限制 0,3214321yyyxxxx模型建立模型建立x1 x4：第：第14周周的生产量的生产量y1 y3：第：第13周末周末库存量库存量周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5存贮费存贮费

43、:0.2(千元千元/周周 千箱千箱)模型求解模型求解 4周生产计划的总费用为周生产计划的总费用为528(千元千元)最优解：最优解：x1 x4：15，40，25，20；y1 y3：0，15，5.周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5产量产量15402520库存库存01550LINDO求解求解检修计划检修计划0-1变量变量wt：wt=1=1 检修安排在第检修安排在第t周周(t=1,2,3,4）在在4周内安排一次设备检修，占用当周内安排一次设备检修，占用当周周15千箱生产能力，能使检修后每周增千箱生产能力，能使检修后每周增产产5千箱，检修应排

44、在哪一周千箱，检修应排在哪一周?检修安排在任一周均可检修安排在任一周均可:周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5能能力力限限制制 204540304321xxxx301511wx12254015wwx1233554515wwwx321445552015wwwwx产量、库存与需求平衡约束条件不变产量、库存与需求平衡约束条件不变 增加检修约束条件：增加检修约束条件：14321wwww目标函数不变目标函数不变LINDO求解求解总费用由总费用由528千元降千元降为为527千元千元检修所导致的生产能力提高的作用检修所导致的生产能力提高的作用,需要

45、更长的时间才能得到充分体现。需要更长的时间才能得到充分体现。最优解：最优解：w1=1,w2,w3,w4=0;x1 x4：15,45,15,25；y1 y3：0,20,0.min 5.0 x1+5.1x2+5.4x3+5.5x4+0.2y1+0.2y2+0.2y3st2)x1-y1=153)x2+y1-y2=254)x3+y2-y3=355)x4+y3=256)x1+15w130 x2+15w2-5w140 x3+15w3-5w1-5w245x4+15w4-5w1-5w2-5w320w1+w2+w3+w4=1endint w1int w2int w3int w4例例2 饮料的生产批量问题饮料的生

46、产批量问题 安排生产计划安排生产计划,满足每周的需求满足每周的需求,使使4周总费用最小。周总费用最小。存贮费存贮费:每周每千箱饮料每周每千箱饮料 0.2千元。千元。饮料厂使用同一条生产线轮流生产饮料厂使用同一条生产线轮流生产多种多种饮料。饮料。若某周开工生产若某周开工生产某种某种饮料饮料,需支出需支出生产准备费生产准备费8千元。千元。某种某种饮料饮料4周的需求量、生产能力和成本周的需求量、生产能力和成本周次周次需求量需求量(千箱千箱)生产能力生产能力(千箱千箱)成本成本(千元千元/千箱千箱)115305.0225405.1335455.4425205.5合计合计100135 问问题题:生产批量

47、问题生产批量问题考虑与产量无关的固定费用考虑与产量无关的固定费用给优化模型求解带来新的困难给优化模型求解带来新的困难Min 8w1+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+x4=256)x1-30w107)x2-40w208)x3-45w309)x4-20w40endint w1int w2int w3int w4最优解：最优解：x1 x4：15，40，45，0；总费用：总费用：554.0(千元千元)用用LINDO求解求解决策变量决策变量 x1 x

48、4：第：第14周周的生产量的生产量y1 y3：第：第13周末周末库存量库存量0-1变量变量wt：wt=1=1 第第t周周开工生产开工生产(t=1,2,3,4）生产批量问题的一般提法生产批量问题的一般提法ct 时段时段t 生产费用生产费用(元元/件件)；ht 时段时段t(末末)库存费库存费(元元/件件)；st 时段时段t 生产准备费生产准备费(元元)；dt 时段时段t 市场需求市场需求(件件)；Mt 时段时段t 生产能力生产能力(件件)。假设初始库存为假设初始库存为0制订生产计划制订生产计划,满满足需求足需求,并使并使T个时个时段的总费用最小。段的总费用最小。ttttdyxy1)(min1ttt

49、ttTttyhxcwsz0,00ttTyxyytttttMxxxw,0,0,0,1决策变量决策变量 xt 时段时段t 生产量；生产量；yt 时段时段t(末末)库存量；库存量；wt=1 时段时段t 开工开工生产生产 (wt=0 不开工不开工)。目标目标约束约束混合混合0-1规划模型规划模型 生产批量问题的一般提法生产批量问题的一般提法ttttdyxyts1.)(min1tttttTttyhxcwszTtyxyyttT,2,10,00tttttMxxxw,0,0,0,10tttwMx 下面将进入离散模型下面将进入离散模型 离散模型：差分方程、整数规划、离散模型：差分方程、整数规划、图论、对策论、网

50、络流、图论、对策论、网络流、分析社会经济系统的有力工具分析社会经济系统的有力工具 只用到代数、集合及图论（少许）的知识只用到代数、集合及图论（少许）的知识第三讲第三讲 离散模型离散模型3.1 层次分析模型层次分析模型背背景景 日常工作、生活中的决策问题日常工作、生活中的决策问题 涉及经济、社会等方面的因素涉及经济、社会等方面的因素 作比较判断时人的主观选择起相当作比较判断时人的主观选择起相当大的作用，各因素的重要性难以量化大的作用，各因素的重要性难以量化 Saaty于于1970年代提出层次分析法年代提出层次分析法 AHP(Analytic Hierarchy Process)AHP一种一种定性