数学建模优化建模实例课件.ppt

优化建模实例1如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？  三个货舱三个货舱最大最大载载重重( (吨吨),),最大容积最大容积( (米米3 3) ) 例例1  货机装运货机装运 重量（吨）重量（吨）空间空间( 米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例 前仓：前仓：10；；6800中仓：中仓：16；；8700后仓：后仓：8；；5300飞机平衡飞机平衡2决策决策变量变量 xij----第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量( (吨）吨）i=1,2,3,4,  j=1,2,3 (分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙； 模型建立模型建立 3货舱货舱容积容积 目标目标函数函数( (利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；；680016；；87008；；5300xij----第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量4约束约束条件条件平衡平衡要求要求 货物货物供应供应 货机装运货机装运模型建立模型建立 10；；680016；；87008；；5300xij----第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量5例例2  汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。

材、劳动时间的需求，利润及工厂每月的现有量                                         小型小型          中型中型          大型大型           现有量现有量钢材（吨）钢材（吨）                    1.5              3                5                 600劳动时间（小时）劳动时间（小时）       280           250             400             60000利润（万元）利润（万元）                 2                3                4                      • 制订月生产计划，使工厂的利润最大制订月生产计划，使工厂的利润最大• 由由于于各各种种条条件件限限制制，，如如果果生生产产某某一一类类型型汽汽车车，，则则至至少少要生产要生产80辆，那么最优的生产计划应作如何改变辆，那么最优的生产计划应作如何改变6设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1, x2, x3汽车厂生产计划汽车厂生产计划 模型建立模型建立             小型小型     中型中型     大型大型     现有量现有量钢材钢材     1.5          3           5           600时间时间    280       250       400        60000利润利润     2            3           4                      整数整数规划规划模型模型(IP)7其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型 汽车厂生产计划汽车厂生产计划 • 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。

辆，求生产计划x1, ,x2,, x3=0 或或  80   x1=80，，x2= 150，，x3=0，，最优值最优值z=6108方法方法2：：引入引入0-1变量，化为整数规划变量，化为整数规划 M为大的正数，为大的正数，可取可取1000 • 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划x1=0 或 80x2=0 或 80x3=0 或 809NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解( (如如LINGO, , MATLAB) )，，但是其结果常依赖于初值的选择但是其结果常依赖于初值的选择 方法方法3：：化为非线性规划化为非线性规划 非线性规划（非线性规划（Non- Linear Programming，，简记简记NLP）） 实实践践表表明明，，本本例例仅仅当当初初值值非非常常接接近近上上面面方方法法算算出出的最优解时，才能得到正确的结果的最优解时，才能得到正确的结果 • 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划 x1=0 或 80x2=0 或 80x3=0 或 8010应如何安排计划，在满足每周市场需求的条件下，使应如何安排计划，在满足每周市场需求的条件下，使四周的总费用最小四周的总费用最小 ？？  例例3   饮料厂的生产与检修计划饮料厂的生产与检修计划 • 剩余产品需要支付贮存费，每周剩余产品需要支付贮存费，每周0.20.2千元千元/ /千箱；千箱；周次周次需求量需求量(千箱千箱)生产能力生产能力(千箱千箱)11530225403354542520合计合计100135成本成本(千元千元/千千箱箱)5.05.15.45.5 11问题分析问题分析• 除第除第4周外每周的生产周外每周的生产能力超过每周的需求；能力超过每周的需求；• 生产成本逐周上升；生产成本逐周上升；•前几周应多生产一些。

前几周应多生产一些 周次周次需求需求能力能力11530225403354542520合计合计100135成本成本5.05.15.45.5 • 饮料厂在第饮料厂在第1周开始时没有库存；周开始时没有库存； • 从费用最小考虑从费用最小考虑, , 第第4周末不能有库存；周末不能有库存； • 周末有库存时需支出一周的存贮费；周末有库存时需支出一周的存贮费； • 每周末的库存量等于下周初的库存量每周末的库存量等于下周初的库存量 模模型型假假设设 12目标目标函数函数约束约束条件条件产量、库存与需求平衡产量、库存与需求平衡 决策变量决策变量 能力限制能力限制 非负限制非负限制 模型建立模型建立x1~ x4：第：第1~4周周的生产量的生产量y1~ y3：第：第1~3周末周末库存量库存量周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5存贮费存贮费: :0.2 ( (千元千元/ /周周• •千箱千箱) ) 13模型求解模型求解 4周生产计划的总费用为周生产计划的总费用为528 (千元千元) 最优解：最优解： x1~ x4：：15，，40，，25，，20；；                  y1~ y3：： 0，，15，，5 .周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5产量产量15402520库存库存0155014检修计划检修计划0-1变量变量wt ：：wt=1=1~ 检修安排检修安排在第在第t周周(t=1,2,3,4））• 在在4周内安排一次设备检修，占用当周周内安排一次设备检修，占用当周15千箱生产能力，能使千箱生产能力，能使检修后每周增产检修后每周增产5千箱，检修应排在哪一周千箱，检修应排在哪一周? ? 检修安排在任一周均可检修安排在任一周均可周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5约束条件约束条件能能力力限限制制 产量、库存产量、库存与需求平衡与需求平衡条件不变条件不变 15增加约束条件：检修增加约束条件：检修1 1次次检修计划检修计划目标函数不变目标函数不变0-1变量变量wt ：：wt= =1~ 检修检修安排在第安排在第t周周(t=1,2,3,4））总费用由总费用由528千元降千元降为为527千元千元检修所导致的生产能力提高的作用检修所导致的生产能力提高的作用, 需要更长的时间才能得到充分体现。

需要更长的时间才能得到充分体现 最优解：最优解： w1= =1, w2 , w3,  w4=0; x1~ x4：：15, ,45, ,15, ,25；；                  y1~ y3：：0, ,20, ,0 .16问题问题1.  如何下料最节省如何下料最节省 ? 例例4 钢管下料钢管下料 问题问题2.  客户增加需求：客户增加需求：原料钢管原料钢管: :每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种如何下料最节省？种如何下料最节省？5米米10根根 17按照客户需要在一根原料钢管上安排切割的一种组合按照客户需要在一根原料钢管上安排切割的一种组合 切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料 18为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2. 所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1. 原料钢管剩余总余量最小原料钢管剩余总余量最小19xi ~按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,…7) ) 约束约束满足需求满足需求 决策决策变量变量 目标目标1（总余量）（总余量）按模式按模式2切割切割12根根, ,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12, x5=15,                  其余为其余为0；；最优值：最优值：27。

整数约束：整数约束： xi 为为整数整数20当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15,  x5=5,  x7=5, 其余为其余为0；；最优值：最优值：25xi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根 与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米” 相比相比 21钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂根，用枚举法确定合理切割模式，过于复杂决策变量决策变量 xi ~按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i ~ 第第i 种切割模式下，每根原料钢种切割模式下，每根原料钢管生产管生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量22满足需求满足需求模式合理：每根模式合理：每根余料不超过余料不超过3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）约束约束条件条件整数约束：整数约束： xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整数为整数23增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界：原料钢管总根数下界： 特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。

根原料钢管总根数上界：原料钢管总根数上界：13+10+8=31 模式排列顺序可任定模式排列顺序可任定 钢管下料问题钢管下料问题2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米24求解整数非线性规划模型求解整数非线性规划模型模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，米钢管，共共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根原料钢管总根数为原料钢管总根数为28根。