西南交大经管院《运筹学》运输与整数规划

运输与整数规划运输与整数规划西南交通大学经济管理学院西南交通大学经济管理学院运筹学OperationsResearchOperationsResearchTheTransportationProblem运输问题SourcesDestinations每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品需求假设（TheRequirementsAssumption）可行解特性（TheFeasibleSolutionsProperty）成本假设（TheCostAssumption）整数解性质（IntegerSolutionsProperty）运输问题的特征选择顾客Š耐芙迪公司在３个工厂中专门生产一种产品Š这种产品有着优良的品质，所以现在公司接到了许多订单，产品供不应求．Š主要是由于运输成本的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客．Š问题：公司需要向每一位顾客供应的产品数量是多少？每一个工厂向每一个顾客供应多少单位的货物？耐芙迪公司问题中的数据8000600090007000MaxPurchase0200030007000MinPurchase700035515929Plant3500048321837Plant2800053464255Plant1CapacityC4C3C2C1NiftyCo.Product-DistributionProblemUnitProfitCustomer1Customer2Customer3Customer4Plant1$55$42$46$53Plant2$37$18$32$48Plant3$29$59$51$35TotalProductionShipmentCustomer1Customer2Customer3Customer4ProductionQuantityPlant17,00001,00008,000=8,000Plant20005,0005,000=5,000Plant306,0001,00007,000=7,000MinPurchase7,0003,0002,0000====TotalProfitTotalShipped7,0006,0002,0005,000$1,076,000====MaxPurchase7,0009,0006,0008,000生产进度安排Š北方飞机制造公司为全世界的航空公司生产各种商务飞机．制造过程最后的一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去．Š问题：每月生产多少发动机的计划，使制造和存储的总成本达到最小1.151.13105204150001.111.101025253150001.121.111530152150001.101.081020101加班时间正常时间加班时间正常时间单位存储成本（美元）单位生产成本（百万美元）最大产量计划安装量月份NorthernAirplaneCo.Production-SchedulingProblemProductionCostRegularStorageCost($millions)TimeOvertime($millionspermonth)Month11.081.100.015Month21.111.12Month31.101.11Month41.131.15UnitCost($millions)12341(RT)1.081.101.111.131(OT)1.101.121.131.152(RT)-1.111.131.14Month2(OT)-1.121.141.15Produced3(RT)--1.101.123(OT)--1.111.134(RT)---1.134(OT)---1.15MaximumUnitsProduced1234ProducedProduction1(RT)1050520=201(OT)00000=102(RT)0100010=30Month2(OT)00000=15Produced3(RT)0025025=253(OT)0001010=104(RT)00055=54(OT)00000=10Installed10152520====TotalCosteduledInstallations10152520($millions)77.4MonthInstalledMonthInstalled北方飞机制造公司的最优生产进度安排02054(RT)100103(OT)525253(RT)515102(RT)1010201(RT)储存量安装量产量月份Š线性规划的一个重要的假设是决策变量可取非整数的连续值。然而这一假设在很多情况下不能满足实际问题的要求；Š对决策变量有整数要求的数学规划问题称为整数规划问题；Š整数规划是数学规划的一个重要分枝，有广泛的应用背景，如指派问题、背包问题、旅行推销商问题都是整数规划问题；Š整数规划又是最难求解的问题之一，至今还没有找到有效算法。整数规划问题邮局排班问题例1：邮局一年365天都要有人值班，每天需要的职工数因业务忙闲而异，据统计邮局每天需要的人数按周期变化，一周内每天需要的人数如下表：排班要符合每周连续工作五天，休息两天的规定。如何排班可使用人最少。11161419151317日六五四三二一邮局排班模型解：设xi为第i天开始上班的人数：min:z=x1+x2+x3+x4+x5+x6+x7s.t.x1+x4+x5+x6+x7≥17x1+x2+x5+x6+x7≥13x1+x2+x3+x6+x7≥15x1+x2+x3+x4+x7≥19x1+x2+x3+x4+x5≥14x2+x3+x4+x5+x6≥16x3+x4+x5+x6+x7≥11xi≥0i=1,2,...,7LP解：x=(1.3,3.3,2,7.3,0,3.3,5)z=22.3整数解：x=(4,4,2,6,0,4,3)z=23固定费用问题例2:服装厂可生产西服、衬衫和羽绒服。生产不同服装要使用不同设备，该厂可从租赁公司租用这些设备（每种设备可租用多台）。服装厂每月可用人工工时为3000小时，该厂如何安排生产可使每月利润最大。市场需求、设备租金和其它经济参数见下表：300243002003000350羽绒服35000.5140302000800衬衫2300354002805000150西服1可用工时/台设备工时人工工时销售价格生产成本租金元/台市场需求服装种类序解：令yi为租赁i类设备的数量;xi为各类服装的生产量,具体模型为：max120x1+10x2+100x3-5000y1-2000y2-1000y3s.t.5x1+x2+4x3≤30003x1-300y1≤00.5x2-500y2≤02x3-300y3≤0x1≤150x2≤800x3≤350xi,yi≥0i=1,2,3服装厂生产模型Š整数规划=相关的线性规划+整数约束Š整数规划是约束得更紧的问题,它的可行域是其相关线性规划问题可行域的一个子集；Š整数解的数目远少于线性规划的解，只要可行域有界，整数解的数目有限；整数规划的求解难度远大于线性规划。Š整数规划分类y纯整数规划：所有决策变量取整数值；y混合整数规划：部分决策变量取整数值；y0-1整数规划：整数变量只能取0或1。整数规划与线性规划的关系04.03.02.01.04.03.02.01.0x1x2maxx1+x2s.t.x1+2x2≤82x1-x2≤4x1,x2取整数整数规划与线性规划的关系整数规划与线性规划的关系Š穷举法：方法简单，只可解小问题，计算量很大；对0-1整数规划，计算量为2n，按指数增长；Š凑整法：解的质量差，有时无法得到可行解Š分枝定界:计算效率高,应用广泛;Š割平面法:有理论意义,但计算效率较低；Š启发算法:效率高,但不能保证找到最优解,可解大规模问题。求解整数规划方法穷举法方法简单，只可解小问题，计算量很大；对0-1整数规划，计算量为2n，按指数增长：1.05秒1.05×1062018分钟1.07×1093013天1.10×10124036年1.73×1015504亿亿年1.27×10301001.02毫秒1.02×10310计算时间计算量nŠ例：max:z=3x1+x2s.t.2x1+x2≤52x1+3x2=5x1,x2为非负整数Š松弛问题解:x=(2.5,0)T,四舍五入得不到可行解;Š整数最优解:x=(1,1)T凑整法凑整法Š例：max:x1+5x2s.t.x1+10x2≤20x1≤2x1,x2为非负整数Š松弛问题解：x=(2,1.8)Tz=11Š四舍五入解：x=(2,2.0)T不是可行解；x=(2,1.0)Tz=7Š整数最优解：x=(0,2.0)Tz=101.002.01.02.0x1x2分枝定界算法举例整数规划问题：max:z=x1+x2s.t.6x1+2x2≤175x1+9x2≤44x1,x2为整数按线性规划求解：x1=1.477,x2=4.068z=5.5455.04.04.03.03.02.02.001.01.0x2x15x1+9x2≤446x1+2x2≤17目标函数线线性规划最优解整数规划最优解5.04.04.03.03.02.02.001.01.0x2x15x1+9x2≤446x1+2x2≤17目标函数线线性规划最优解整数最优解xx11≤≤11xx11≥≥22LPLP松弛松弛zz00=5.545=5.545xx11=1.477=1.477xx22=4.068=4.068SUB3SUB3zz33=5.0=5.0xx11=1.0=1.0xx22=4.0=4.0SUB2SUB2zz22=4.5=4.5xx11=2.0=2.0xx22=2.5=2.5SUB1SUB1zz11=5.333=5.333xx11=1.000=1.000xx22=4.333=4.333SUB4SUB4infeasibleinfeasiblezzUU=5.545=5.545zzLL==--∞∞zzUU=5.33=5.33zzLL=5.00=5.00xx11≥≥22xx11≤≤11SUBSUB11maxmax::xx11++xx22s.ts.t.6.6xx11+2+2xx22≤≤171755xx11+9+9xx22≤≤4444xx11≤≤11xx11,,xx22≥≥00SUBSUB22maxmaxxx11++xx22s.ts.t.6.6xx11+2+2xx22≤≤171755xx11+9+9xx22≤≤4444xx11≥≥22xx11,,xx22SUBSUB33maxmax::xx11++xx22s.ts.t.6.6xx11+2+2xx22≤≤171755xx11+9+9xx22≤≤4444xx11≤≤11xx22≤≤44xx11,,xx22SUBSUB44maxmaxxx11++xx22s.ts.t.6.6xx11+2+2xx22≤≤171755xx11+9+9xx22≤≤4444xx11≤≤11xx22≥≥55xx11,,xx22xx22≥≥55xx22≤≤44zzUU=5.33=5.33zzLL==--∞∞整数规划的图解法Š当整数规划问题中只含有两个决策变量时，其最优解可通过应用图解法求得，只需要在原方法的最后一部分作些改动。因此，与前面一样，首先作出LP放宽的可行域，确定目标函数的斜率，而后以该斜率在可行域内平移直线，增大目标函数值。Š但是，与线性规划不同的一点是，直线平移到可行域内的最后一个整数解即停下来，而不是平移到可行域的边缘。最后平移到的整数解即为最优整数解。TBA航空公司问题设S=购买小型机的数量L=购买大型机的数量最大化利润=S+5L(百万美元)资金约束：5S+50L≤100(百万美元)小型机约束:S≤2且S≥0,L≥0S,L均为整数.整数规划的图解法3210123SLNumberoflargeairplanespurchasedNumberofsmallairplanespurchased(2,1)=Roundeds