1、1优化建模实例2如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例1 货机装运货机装运 重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例 前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡3决策决策变量变量 xij-第第i 种货物装入第种货物装入第j
2、个货舱的重量个货舱的重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；模型建立模型建立 4货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312
3、111xxxx870039058065048042322212xxxx530039058065048043332313xxxx货机装运货机装运模型建立模型建立 货舱货舱重量重量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量5约束约束条件条件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx货物货物供应供应 18131211xxx15232221xxx23333231xxx12434241xxx货机装
4、运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量6例例2 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材、劳动时间的需求，利润及工厂每月的现有量。小型小型 中型中型 大型大型 现有量现有量钢材（吨）钢材（吨）1.5 3 5 600劳动时间（小时）劳动时间（小时）280 250 400 60000利润（万元）利润（万元）2 3 4 制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂
5、的利润最大。由于各种条件限制，如果生产某一类型汽车，则至少由于各种条件限制，如果生产某一类型汽车，则至少要生产要生产80辆，那么最优的生产计划应作如何改变。辆，那么最优的生产计划应作如何改变。7设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3321432xxxzMax600535.1.321xxxts60000400250280321xxx123,x x x 非负整数汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型 中型中型 大型大型 现有量现有量钢材钢材 1.5 3 5 600时间时间 280 250 400 60000利润利润 2 3 4
6、 整数整数规划规划模型模型(IP)8其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：80,0,0321xxx0,80,0321xxx80,80,0321xxx0,0,80321xxx0,80,80321xxx80,0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解为：分解为8个个LP子模型子模型 汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。321432xxxzMax600535.1.
7、321xxxts60000400250280321xxxx1,x2,x3=0 或或 80 x1=80，x2=150，x3=0，最优值，最优值z=6109方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划 M为大的正数，为大的正数，可取可取1000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 801,0,80,11111yyxMyx1,0,80,22222yyxMyx1,0,80,33333yyxMyx10NLP虽然可用现成的数学软件求解虽然可用现成的数学软件求解(如如LINGO,M
8、ATLAB)，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。方法方法3：化为非线性规划化为非线性规划 非线性规划（非线性规划（Non-Linear Programming，简记，简记NLP）实践表明，本例仅当初值非常接近上面方法算出实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx11应如何安排计划，在满足每周市场需求的条
9、件下，使应如何安排计划，在满足每周市场需求的条件下，使四周的总费用最小四周的总费用最小？例例3 饮料厂的生产与检修计划饮料厂的生产与检修计划 剩余产品需要支付贮存费，每周剩余产品需要支付贮存费，每周0.20.2千元千元/千箱；千箱；周次周次需求量需求量(千箱千箱)生产能力生产能力(千箱千箱)11530225403354542520合计合计100135成本成本(千元千元/千箱千箱)5.05.15.45.5 12问题分析问题分析 除第除第4周外每周的生产周外每周的生产能力超过每周的需求；能力超过每周的需求；生产成本逐周上升；生产成本逐周上升；前几周应多生产一些。前几周应多生产一些。周次周次需求需求
10、能力能力11530225403354542520合计合计100135成本成本5.05.15.45.5 饮料厂在第饮料厂在第1周开始时没有库存；周开始时没有库存；从费用最小考虑从费用最小考虑,第第4周末不能有库存；周末不能有库存；周末有库存时需支出一周的存贮费；周末有库存时需支出一周的存贮费；每周末的库存量等于下周初的库存量。每周末的库存量等于下周初的库存量。模模型型假假设设 13目标目标函数函数约束约束条件条件产量、库存与需求平衡产量、库存与需求平衡 决策变量决策变量 )(2.05.54.51.50.53214321yyyxxxxzMin1511 yx25212yyx35323yyx2534
11、yx20,4540,304321xxxx能力限制能力限制 非负限制非负限制 0,3214321yyyxxxx模型建立模型建立x1 x4：第：第14周周的生产量的生产量y1 y3：第：第13周末周末库存量库存量周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5存贮费存贮费:0.2(千元千元/周周千箱千箱)14模型求解模型求解 4周生产计划的总费用为周生产计划的总费用为528(千元千元)最优解：最优解：x1 x4：15，40，25，20；y1 y3：0，15，5.周次周次需求需求能力能力11530225403354542520成本成本5.05.15.4
12、5.5产量产量15402520库存库存0155015检修计划检修计划0-1变量变量wt：wt=1=1 检修安排检修安排在第在第t周周(t=1,2,3,4）在在4周内安排一次设备检修，占用当周周内安排一次设备检修，占用当周15千箱生产能力，能使千箱生产能力，能使检修后每周增产检修后每周增产5千箱，检修应排在哪一周千箱，检修应排在哪一周?检修安排在任一周均可检修安排在任一周均可周次周次需求需求能力能力11530225403354542520成本成本5.05.15.45.5约束条件约束条件能能力力限限制制 204540304321xxxx301511wx12254015wwx1233554515ww
13、wx321445552015wwwwx产量、库存产量、库存与需求平衡与需求平衡条件不变条件不变 16增加约束条件：检修增加约束条件：检修1 1次次14321wwww检修计划检修计划目标函数不变目标函数不变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.17问题问题1.如何下料最
14、节省如何下料最节省?例例4 钢管下料钢管下料 问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过规定切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 18按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4米米1根根 6米米1根根 8米米1根根 余料余
15、料3米米 4米米1根根 6米米1根根 6米米1根根 合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米 8米米1根根 8米米1根根 钢管下料钢管下料 19为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少 模式模式 4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下
16、料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小20 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,7)约束约束满足需求满足需求 决策决策变量变量 目标目标1（总余量）（总余量）765432113333xxxxxxxZMin5023454321xxxxx20326542xxxx152753xxx按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米 模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求5020
17、15最优解：最优解：x2=12,x5=15,其余为其余为0；最优值：最优值：27。整数约束：整数约束：xi 为整数为整数21当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 76543212xxxxxxxZMin目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。5023454321xxxxx20326542xxxx152753xxxxi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，
18、共共25根，余料根，余料35米米 虽余料增加虽余料增加8米，但减少了米，但减少了2根根 与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米”相比相比 22钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模
19、式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量23满足需求满足需求50313212111xrxrxr10323222121xrxrxr20333232131xrxrxr15343242141xrxrxr模式合理：每根模式合理：每根余料不超过余料不超过3米米1986541641312111rrrr1986541642322212rrrr1986541643332313rrrr整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函
20、数（目标函数（总根数）总根数）321xxxMin约束约束条件条件整数约束：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数为整数24增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解321xxx原料钢管总根数下界：原料钢管总根数下界：2619158206105504特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需13根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数
21、上界：13+10+8=31 3126321xxx模式排列顺序可任定模式排列顺序可任定 钢管下料问题钢管下料问题2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米25求解整数非线性规划模型求解整数非线性规划模型模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，米钢管，共共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。
