《西南交大经管院《运筹学》运输与整数规划.pdf》由会员分享，可在线阅读，更多相关《西南交大经管院《运筹学》运输与整数规划.pdf（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运输与整数规划运输与整数规划运输与整数规划运输与整数规划西南交通大学经济管理学院西南交通大学经济管理学院西南交通大学经济管理学院西南交通大学经济管理学院运筹学运筹学Operations ResearchOperations ResearchThe Transportation Problem运输问题运输问题 SourcesDestinations每一个出发地都有一定的供应量（每一个出发地都有一定的供应量（supply）配送到目的地，每一个目的地都有需要从一定的需求量（）配送到目的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品需求假设），接收从出发地发出的产品需求
2、假设（The Requirements Assumption）可行解特性可行解特性（The Feasible Solutions Property）成本假设（成本假设（The Cost Assumption）整数解性质（）整数解性质（Integer Solutions Property）运输问题的特征运输问题的特征选择顾客选择顾客?耐芙迪公司在个工厂中专门生产一种产品耐芙迪公司在个工厂中专门生产一种产品?这种产品有着优良的品质，所以现在公司接到了许多订单，产品供不应求这种产品有着优良的品质，所以现在公司接到了许多订单，产品供不应求?主要是由于运输成本的差异，销售一个产品得到的净利润也不同，很大
3、程度上取决于哪个工厂供应哪个顾客主要是由于运输成本的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客?问题：公司需要向每一位顾客供应的产品数量是多少？每一个工厂向每一个顾客供应多少单位的货物？问题：公司需要向每一位顾客供应的产品数量是多少？每一个工厂向每一个顾客供应多少单位的货物？耐芙迪公司问题中的数据耐芙迪公司问题中的数据8000600090007000Max Purchase0200030007000Min Purchase700035515929 Plant 3500048321837 Plant 2800053464255 Plant 1CapacityC4C
4、3C2C1Nifty Co.Product-Distribution ProblemUnit ProfitCustomer 1Customer 2Customer 3Customer 4Plant 1$55$42$46$53Plant 2$37$18$32$48Plant 3$29$59$51$35TotalProductionShipmentCustomer 1Customer 2Customer 3Customer 4 ProductionQuantityPlant 17,00001,00008,000=8,000Plant 20005,0005,000=5,000Plant 306,00
5、01,00007,000=7,000Min Purchase7,0003,0002,0000=Total ProfitTotal Shipped7,0006,0002,0005,000$1,076,000=Max Purchase7,0009,0006,0008,000生产进度安排生产进度安排?北方飞机制造公司为全世界的航空公司生产各种商务飞机制造过程最后的一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去北方飞机制造公司为全世界的航空公司生产各种商务飞机制造过程最后的一步是生产喷气发动机并把它们安装到已经完成的飞机框架之中去?问题：每月生产多少发动机的计划，使制造和存储的总成本达到最
6、小问题：每月生产多少发动机的计划，使制造和存储的总成本达到最小1.151.13105204150001.111.101025253150001.121.111530152150001.101.081020101加班时间正常时间加班时间正常时间单位存储成本（美元）单位生产成本（百万美元）最大产量计划安装量月份加班时间正常时间加班时间正常时间单位存储成本（美元）单位生产成本（百万美元）最大产量计划安装量月份Northern Airplane Co.Production-Scheduling ProblemProduction Cost RegularStorage Cost($millions)T
7、imeOvertime($millions per month)Month 11.081.100.015Month 21.111.12Month 31.101.11Month 41.131.15Unit Cost($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.15MaximumUnits Produced1234ProducedProduct
8、ion1(RT)1050520=201(OT)00000=102(RT)0100010=30Month2(OT)00000=15Produced3(RT)0025025=253(OT)0001010=104(RT)00055=54(OT)00000 0)；0 不生产第j种产品（即 0)；0 不生产第j种产品（即 xj=0)。=0)。令令解解设设xj是第是第j种产品的产量种产品的产量3,2,1,103,2,1010032300432500842200150100654max333222111321321321321321=+=+=jyjxyMxyMxyMxxxxxxxxxxyyyxxxzjj或且
9、为整数，或且为整数，其中常数其中常数Mj为的为的xj上界，可取上界，可取M1 1=100，=100，M2 2=50，=50，M3 3=100/3=100/3多抉择问题多抉择问题r组约束条件中，要求至少有组约束条件中，要求至少有 q 组约束得到满足，而其他组约束得到满足，而其他 r-q 组约束可以满足，也可以不满足引入0-1变量组约束可以满足，也可以不满足引入0-1变量yk，及一个充分大的常数，及一个充分大的常数Mk，则，则yk=0 对应的约束为起作用约束对应的约束为起作用约束rkbxaxaxaknknkk,12211LL=+（1）（1）qryrkMybxaxaxakkkknknkk=+,122
10、11LL引入0-1变量引入0-1变量 yk，及一个充分大的常数，及一个充分大的常数 Mk，则，则yk=0 对应的约束为起作用约束对应的约束为起作用约束rkbxaxaxaknknkk,12211LL=+（2）（2）要求一个约束起作用时要求一个约束起作用时qryrkMybxaxaxakkkknknkk=+,12211LL1,12211=+ryrkMybxaxaxakkkknknkkLL若整数规划中，变量满足若整数规划中，变量满足则则,20klx 01111222yyyyxkkkkl+=+=L其中其中y0、y1、yk取 0 或 1取 0 或 1离散值的变量离散值的变量设设 xj只能取值只能取值a1，
11、a2，ak，则可表示为，则可表示为10111或=或=ikiijkiiiyyxya跳跃变量跳跃变量10或或=yUyxLyjxj的值或者为的值或者为0，或者为则可表示为，或者为则可表示为UxLj 非线性整数规划问题线性化非线性整数规划问题线性化3,2,110332min321532231=+=jxxxxxxxxfj或引入 0-1 变量引入 0-1 变量 y0213232+yxxyxx当当x2=x3=1 时，时，y 1 和和y 1当当 x2 或或 x3 中至少有一个为0时，中至少有一个为0时，y=0y=1 当当 x2=x3=10 否则否则则则2/)(21xxy+y=11010021332max323
12、232131或或=+或或=+=yxyxxyxxxxxxyxfj例：某城市有例：某城市有6个区个区,规划建消防站规划建消防站,任何区发生火警时消防车要在任何区发生火警时消防车要在15分钟内赶到分钟内赶到,各区间消防车行驶的时间见下表各区间消防车行驶的时间见下表,求设置消防站最少的方案。求设置消防站最少的方案。地区地区123456101016282720210024321710316240122721428321201525527172715014620102125140集合覆盖问题举例集合覆盖问题举例解：整数规划问题为：解：整数规划问题为：min:x1+x2+x3+x4+x5+x6s.t.x1+
13、x2 1 x1+x2+x6 1 x3+x4 1 x3+x4+x5 1 x4+x5+x6 1 x2 +x5+x6 1 xi=0 或或 1 i=1,.,6最优解最优解 x2=x4=1,在地区在地区2,4设消防站。设消防站。集合覆盖问题举例集合覆盖问题举例固特公司的产品计划固特公司的产品计划固特产品公司的研发部最近开发出了三种新产品。这些产品都可以在两个工厂中生产，为了管理的方便和防止新生产线的过度多元化，公司的管理层增加了如下的约束：在三种新产品中，最多只能选择两种进行生产；两个工厂中必须选出一个专门生产新产品。固特产品公司的研发部最近开发出了三种新产品。这些产品都可以在两个工厂中生产，为了管理的
14、方便和防止新生产线的过度多元化，公司的管理层增加了如下的约束：在三种新产品中，最多只能选择两种进行生产；两个工厂中必须选出一个专门生产新产品。GOOD产品公司数据产品公司数据(每周数量每周数量)957可销出的数量可销出的数量($thousands)375单位利润单位利润40264工厂工厂230243工厂工厂1产品产品3产品产品 2产品产品1每周可获得的生产时间（小时）单位产品的生产时间（小时）每周可获得的生产时间（小时）单位产品的生产时间（小时）数学表达数学表达假设假设xi=单位星期所生产的单位产品单位星期所生产的单位产品 i 的数量的数量(i=1,2,3),yi=1 生产产品生产产品 i;y
15、i=0 不生产不生产(i=1,2,3),y4=1 采用工厂采用工厂2;y4=0 采用工厂采用工厂1Maximize Profit=5x1+7x2+3x3($thousands)辅助变量辅助变量=1 如果产品有最大的销量如果产品有最大的销量:Product 1:x1 7y1Product 2:x2 5y2Product 3:x3 9y3Either plant 1(y4=0)or plant 2(y4=1):Plant 1:3x1+4x2+2x3 30+99y4Plant 2:4x1+6x2+2x3 40+99(1 y4)y1+y2+y32and xi 0(i=1,2,3),yiare bina
16、ry(i=1,2,3,4).电子表格模型电子表格模型3456789101112131415161718192021BCDEFGHIProduct 1Product 2Product 3Unit Profit($thousands)573ModifiedHoursHoursHoursHours Used Per Unit ProducedUsedAvailableAvailablePlant 134234.5=12930Plant 246240=4040Product 1Product 2Product 3Units Produced5.509=Only If Produce709Maximum
17、 Sales759TotalMaximumProducedTo ProduceProduce?1012=2Total Profit($thousands)Which Plant to Use?(0=Plant 1,1=Plant 2)154.5Supersuds 公司的营销计划公司的营销计划Supersuds 公司正在制定下一年的新产品营销计划，并准备在全国电视网上购买公司正在制定下一年的新产品营销计划，并准备在全国电视网上购买5个广告片，以促销个广告片，以促销3种产品。每个广告只针对一种产品，每种产品最多可以有三个广告，最少可以不做广告。问题种产品。每个广告只针对一种产品，每种产品最多可以有
18、三个广告，最少可以不做广告。问题:如何将这如何将这5个广告分配给三种产品个广告分配给三种产品?超级苏兹公司问题的数据超级苏兹公司问题的数据利润利润(百万美元百万美元)43332232-10110000产品产品3产品产品2产品产品1电视广告片数电视广告片数数学规划数学规划假设假设 yij=1 分配给产品分配给产品 i 的广告数为的广告数为 j;0 otherwise(i=1,2,3;j=1,2,3)Maximize Profit=y11+3y12+3y13+2y22+3y23 y31+2y32+4y33Mutually Exclusive:Product 1:y11+y12+y13 1Produ
19、ct 2:y21+y22+y23 1Product 3:y31+y32+y33 1Total available spots:y11+2y12+3y13+y21+2y22+3y23+y31+2y32+3y33 5且且yij是是0，1变量变量(i=1,2,3;j=1,2,3).电子表格模型电子表格模型Profit($millions)Product 1Product 2Product 3Number110-1of2322Spots3334SolutionProduct 1Product 2Product 3TotalNumber1000Profitof2100($millions)Spots30
20、017Total101=1SFO-DEN0100100100101=1SFO-SEA0010010010011=1LAX-ORD0001001011011=1LAX-SFO1000010001101=1ORD-DEN0001100010001=1ORD-SEA0000001101111=1DEN-SFO0101100010001=1DEN-ORD0000100100101=1SEA-SFO0010001100011=1SEA-LAX0000010011111=1TotalNumber123456789101112Sequencesof CrewsFly Sequence?00110000001
21、03=3Total Cost($thousands)18东方公司是一家生产番茄酱的公司，番茄酱将先运至分配中心，再由分配中心运送至分销店。该公司有五个工厂、三个分配中心、四家分销店，这些工厂和分配中心的年固定成本，从各工厂至分配中心的运费与各工厂的生产能力如表图所示。假定各分配中心的库存政策为东方公司是一家生产番茄酱的公司，番茄酱将先运至分配中心，再由分配中心运送至分销店。该公司有五个工厂、三个分配中心、四家分销店，这些工厂和分配中心的年固定成本，从各工厂至分配中心的运费与各工厂的生产能力如表图所示。假定各分配中心的库存政策为“零库存零库存”，即分配中心将从工厂得到的产品均分配给分销店，不留作
22、库存。公司要设计一种番茄酱分配系统，在满足需求的前提下，确定使用哪些工厂与分配中心进行番茄酱的生产与分配，以使得总成本最小。，即分配中心将从工厂得到的产品均分配给分销店，不留作库存。公司要设计一种番茄酱分配系统，在满足需求的前提下，确定使用哪些工厂与分配中心进行番茄酱的生产与分配，以使得总成本最小。工厂 1 工厂5 工厂4 工厂3 工厂2 中心2中心1中心3分店4分店3分店2分店18001000120070070050070080060060050050070060050040 80 90 50 80 60 70 40 60 50 30 80 需求量150 250 300 200 300 20
23、0 300 200 400 生产能力6000020000400004000042000400004500035000年固定成本年固定成本中心中心3中心中心2中心中心1工厂工厂5工厂工厂4工厂工厂3工厂工厂2工厂工厂1单位单位工厂与分配中心的固定成本60000分配中心分配中心320000分配中心分配中心240000分配中心分配中心140000工厂工厂542000工厂工厂440000工厂工厂345000工厂工厂235000工厂工厂1年固定成本单位年固定成本单位解解:xij:从工厂从工厂 i 运至分配中心运至分配中心 j 的产品数量；的产品数量；yij:从分配中心从分配中心 i 运至分销店运至分销店
24、 j的产品数量；的产品数量；Fi:是否使用第是否使用第 i个工厂的个工厂的0-1整数变量整数变量;Di:是否使用第是否使用第 i个分配中心的个分配中心的0-1整数变量整数变量;目标函数目标函数:运输与固定成本最小运输与固定成本最小minf(x)=800 x11+1000 x12+1200 x13+700 x21+500 x22+700 x23+800 x31+600 x32+500 x33+500 x41+600 x42+700 x43+700 x51+600 x52+500 x53+40y11+80y12+90y13+50y14+70y21+40 y22+60 y23+80 y24+80 y
25、31+30 y32+50 y33+60 y34+35000F1+45000F2+40000F3+42000F4+40000F5+40000D1+20000D2+60000D3（1）工厂能力约束）工厂能力约束:x11+x12+x13 300F 1x21+x22+x2 3 200F 2x31+x3 2+x33 300F 3x41+x42+x43 200F 4x51+x52+x53 400F 5模型约束模型约束（2）分配中心的）分配中心的“零库存零库存”约束约束:x11+x21+x31+x41+x51=y11+y12+y13+y14x12+x22+x32+x42+x52=y21+y22+y23+y2
26、4 x13+x23+x33+x43+x53=y31+y32+y33+y34 模型约束模型约束（3）分配中心运出量约束）分配中心运出量约束:y11+y12+y13+y14 900D1y21+y22+y23+y24 900D2y31+y32+y33+y34 900D3（4）需求约束）需求约束:y11+y21+y31 200y12+y22+y32 300y13+y23+y33 150y14+y24+y34 250（5）非负约束）非负约束:xij 0,yij 0,Fi,Di为为 0-1整数变量整数变量模型约束模型约束分配中心分配中心1分配中心分配中心2分配中心分配中心3工厂工厂180010001200
27、80010001200工厂工厂2700500700700500700工厂工厂3800600500800600500工厂工厂4500600700500600700工厂工厂5700600500700600500分配中心分配中心1分配中心分配中心2分配中心分配中心3分销店1分销店1407080407080分销店2分销店2804030804030分销店3分销店3906050906050分销店4分销店4508060508060分配中心分配中心1分配中心分配中心2分配中心分配中心3工厂i是否使用工厂的固定成本工厂工厂i是否使用工厂的固定成本工厂10000=03000350000000=0300035000
28、工厂工厂202000200=20020014500002000200=200200145000工厂工厂300300300=300300100300300=300300140000工厂40000工厂401.25E-1301.25E-13=1.29E-132006.4504E-164200001.25E-1301.25E-13=1.29E-132006.4504E-1642000工厂工厂500400400=4004001400000200700=0200700=090090000400400=4004001400000200700=0200700=20002002.84E-14200=200分销店
29、2分销店200300300=30000300300=300分销店3分销店300150150=15000150150=150分销店4分销店400250250=25090000250250=250900分配中心i是否使用分配中心i是否使用011400002000060000011400002000060000工厂到分配中心成本工厂到分配中心成本450000450000总成本分配中心分销店成本总成本分配中心分销店成本4550070050045500700500工厂的固定成本125000分配中心的固定成本工厂的固定成本125000分配中心的固定成本8000080000动态投资问题模型动态投资问题模型?
30、某电力公司预测明年用电需求将达到某电力公司预测明年用电需求将达到80亿度电，且在亿度电，且在5年内每年增加用电量年内每年增加用电量20亿度。电力公司现有发电能力亿度。电力公司现有发电能力50亿度，可供选择的新电站共有亿度，可供选择的新电站共有4个。请构造整数规划模型，在满足电力需求前提下使电力公司五年内投入的建设投资和运行费用总和最小个。请构造整数规划模型，在满足电力需求前提下使电力公司五年内投入的建设投资和运行费用总和最小。614040电站电站41318060电站电站3816050电站电站21520070电站电站1年运行费年运行费(百万元百万元)建设投资建设投资(百万元百万元)发电量发电量(
31、亿度亿度)解解:yit:第第 t 年是否建第年是否建第 i 个电站的个电站的0-1整数变量整数变量;xit:第第 t 年第年第 i 个电站的发电量个电站的发电量;目标函数目标函数:投资与运行费最小投资与运行费最小min:i Ii t yit+Ci t(6-t)yit=200(y11+y12+y13+y14+y15)+15(5y11+4y12+3y13+2y14+y15)+160(y21+y22+y23+y24+y25)+8 (5y21+4y22+3y23+2y24+y25).动态投资问题模型动态投资问题模型（1）发电量约束）发电量约束:i xit+50 80+20(t-1)tx11+x21+x
32、31+x41 30 x12+x22+x32+x42 50 x13+x23+x33+x43 70 x14+x24+x34+x44 90 x15+x25+x35+x45 110模型约束模型约束（2）发电能力限制约束）发电能力限制约束:xit CAPi tj=1yij i,tx11 70 y11 x12 70(y11+y12)x13 70(y11+y12+y13)x14 70(y11+y12+y13+y14)x15 70(y11+y12+y13+y14+y15)x21 50y21;x22 50(y21+y22);模型约束模型约束（3）电站只能建一次约束）电站只能建一次约束:t yit 1 iy11+
33、y12+y13+y14+y15 1 y21+y22+y23+y24+y25 1 y31+y32+y33+y34+y35 1 y41+y42+y43+y44+y45 1（4）非负约束）非负约束:xit 0,yit为为0-1整数变量整数变量模型约束模型约束解解:yit:第第 t 年是否建第年是否建第 i 个电站的个电站的0-1整数变量整数变量;目标函数目标函数:投资与运行费最小投资与运行费最小min:i Ii t yit+Ci t(6-t)yit=200(y11+y12+y13+y14+y15)+15(5y11+4y12+3y13+2y14+y15)+160(y21+y22+y23+y24+y25
34、)+8 (5y21+4y22+3y23+2y24+y25).动态投资问题模型动态投资问题模型（1）发电量约束）发电量约束:70y11+50y21+60y31+40y41 3070(y11+y12)+50(y21+y22)+60(y31+y32)+40(y41+y42)5070(y11+y12+y13)+50(y21+y22+y23)+60(y31+y32+y33)+40(y41+y42+y43)7070(y11+y12+y13+y14)+50(y21+y22+y23+y24)+60(y31+y32+y33+y34)+40(y41+y42+y43+y44)9070(y11+y12+y13+y14
35、+y15)+50(y21+y22+y23+y24+y25)+60(y31+y32+y33+y34+y35)+40(y41+y42+y43+y44+y45)110模型约束模型约束（3）电站只能建一次约束）电站只能建一次约束:t yit 1 iy11+y12+y13+y14+y15 1 y21+y22+y23+y24+y25 1 y31+y32+y33+y34+y35 1 y41+y42+y43+y44+y45 1（4）非负约束）非负约束:xit 0,yit为为0-1整数变量整数变量模型约束模型约束建设投资年运行费建设投资年运行费(百万元百万元)(百万元百万元)电站电站17020015151515
36、1515电站电站250160888888电站电站360180131313131313电站电站440140666666第第1年第年第2年第年第3年第年第4年第年第5年电站年电站1=1电站电站2=1电站电站3=1电站电站4=30507090110建设投资运行费建设投资运行费54321总费用总费用543215432154321发电量发电量(亿度亿度)一房地产开发商面临一个五年开发规划问题：他目前已经得到三个房地产开发项目的许可，然而由于资金和建设力量的限制，必须确定一个最优的开发计划。三个房地产开发项目的数据如下表。项目收益应在项目建成之后获得，即：若在第一年建设项目一房地产开发商面临一个五年开发规
37、划问题：他目前已经得到三个房地产开发项目的许可，然而由于资金和建设力量的限制，必须确定一个最优的开发计划。三个房地产开发项目的数据如下表。项目收益应在项目建成之后获得，即：若在第一年建设项目A，项目一年建成，则收益在第二年开始获得。建设时间超过一年的项目，其建设投资平均分摊在建设周期内，开发商面临的其他限制为：，项目一年建成，则收益在第二年开始获得。建设时间超过一年的项目，其建设投资平均分摊在建设周期内，开发商面临的其他限制为：1、每年可用于建设的资金不能超过、每年可用于建设的资金不能超过5500万元；万元；2、每年可以使用的建筑工人总数最多为、每年可以使用的建筑工人总数最多为400人；人；3
38、、每年只能允许、每年只能允许1个项目开工，同时施工建设的项目不能超过个项目开工，同时施工建设的项目不能超过2项；请构造一个满足上述约束限制，并使五年内租金收益最大的方案，试建立线性规划模型。项；请构造一个满足上述约束限制，并使五年内租金收益最大的方案，试建立线性规划模型。500万元万元20039000C320万元万元25025000B150万元万元15013000万元万元A建成后每年租金收益每年所需建筑工人建设需要时间建成后每年租金收益每年所需建筑工人建设需要时间(年年)建设所需全部投资项目建设所需全部投资项目项目建设所需全部投资建设需要时间年每年所需建筑工人建成后每年租金收益项目建设所需全部
39、投资建设需要时间年每年所需建筑工人建成后每年租金收益A3000万元万元1150150万元万元30001.每年可用于建设的资金不能超过每年可用于建设的资金不能超过5500万元；万元；B5000万元万元2250320万元万元2500 2.每年可以使用的建筑工人总数最多为每年可以使用的建筑工人总数最多为400人；人；C9000万元万元3200500万元万元3000 3.由于项目管理上的原因，每年只能允许由于项目管理上的原因，每年只能允许1个项第个项第1年第年第2年第年第3年第年第4年年A=1B=1C=1=投资第投资第1年第年第2年第年第3年第年第4年年1111=第第1年第年第2年第年第3年第年第4年年5500550055005500AB工人第工人第1年第年第2年第年第3年第年第4年年C=22224004004004006004503001509606403201000500