运输与整数规划运输与整数规划运输与整数规划运输与整数规划西南交通大学经济管理学院西南交通大学经济管理学院西南交通大学经济管理学院西南交通大学经济管理学院运运筹筹学学Operations ResearchOperations ResearchPDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cnThe Transportation Problem 运输问题运输问题SourcesDestinationsPDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn每一个出发地都有一定的供应量（每一个出发地都有一定的供应量（supply）配送到目）配送到目的地，每一个目的地都有需要从一定的需求量（的地，每一个目的地都有需要从一定的需求量（demand），接收从出发地发出的产品），接收从出发地发出的产品需求假设需求假设（The Requirements Assumption）可行解特性可行解特性（The Feasible Solutions Property）成本假设（成本假设（The Cost Assumption）整数解性质（整数解性质（Integer Solutions Property）运输问题的特征运输问题的特征PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn选择顾客选择顾客w 耐芙迪公司在个工厂中专门生产一种产品耐芙迪公司在个工厂中专门生产一种产品w 这种产品有着优良的品质，所以现在公司接到了许多订单，产这种产品有着优良的品质，所以现在公司接到了许多订单，产品供不应求品供不应求w 主要是由于运输成本的差异，销售一个产品得到的净利润也不主要是由于运输成本的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客同，很大程度上取决于哪个工厂供应哪个顾客w 问题：公司需要向每一位顾客供应的产品数量是多少？每一个问题：公司需要向每一位顾客供应的产品数量是多少？每一个工厂向每一个顾客供应多少单位的货物？工厂向每一个顾客供应多少单位的货物？PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn耐芙迪公司问题中的数据耐芙迪公司问题中的数据8000600090007000Max Purchase0200030007000Min Purchase700035515929 Plant 3500048321837 Plant 2800053464255 Plant 1CapacityC4C3C2C1PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cnNifty Co. Product- Distribution ProblemUnit ProfitCustomer 1Customer 2Customer 3Customer 4 Plant 1$55$42$46$53 Plant 2$37$18$32$48 Plant 3$29$59$51$35TotalProduction ShipmentCustomer 1Customer 2Customer 3Customer 4 ProductionQuantity Plant 17,00001,00008,000=8,000 Plant 20005,0005,000=5,000 Plant 306,0001,00007,000=7,000Min Purchase7,0003,0002,00000 )；0 不生产第不生产第j种产品（即种产品（即 xj= 0 )。令令解解设设xj是是第第j种产品的产量种产品的产量3 , 2 , 1, 103 , 2 , 1010032300432500842200150100654max333222111321321321321321=+=jyjxyMxyMxyMxxxxxxxxxxyyyxxxzjj 或或且且为为整数，整数，其其中中常常数数Mj为为的的xj上上界，界，可取可取M1=100 ，M2=50， M3=100/3PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn多抉多抉择问题择问题r组约束条件中，要求至少有组约束条件中，要求至少有 q 组约束得到满足，组约束得到满足，而其他而其他 r- q 组约束可以满足，也可以不满足组约束可以满足，也可以不满足引入引入0-1变量变量yk，及一个充分大的常数，及一个充分大的常数Mk，则，则yk= 0 对应的约束为起作用约束对应的约束为起作用约束rkbxaxaxaknknkk, 12211LL=+（1）qryrkMybxaxaxakkkknknkk =+ , 12211LLPDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn引入引入0 -1变量变量 yk，及一个充分大的常数，及一个充分大的常数 Mk ，则，则yk= 0 对应的约束为起作用约束对应的约束为起作用约束rkbxaxaxaknknkk, 12211LL=+（2）要要求求一个一个约约束起作束起作用时用时qryrkMybxaxaxakkkknknkk =+ , 12211LL1, 12211 =+ ryrkMybxaxaxakkkknknkkLLPDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn若若整数规划中，整数规划中，变量满足变量满足则则,20k lx 01 11 1222yyyyxk kk kl+= L其中其中y0 、y1 、 、yk取取 0 或或 1离散值离散值的的变量变量设设 xj只能取值只能取值a1，a2， ，ak，则可表示为，则可表示为10111或或= =ikiijkiiiyyxya跳跃变量跳跃变量10或或=yUyxLyjxj的值或者为的值或者为0，或者为，或者为则可表示为则可表示为UxLjPDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn非非线性整数规划问题线性线性整数规划问题线性化化3 , 2, 110332min3215 32231=+=jxxxxxxxxfj或引入引入 0-1 变量变量 y0213232 +yxxyxx当当x2= x3=1 时时，y 1 和和y 1当当 x2 或或 x3 中至少有一个为中至少有一个为0 时，时，y =0y =1 当当 x2 = x3=10 否则否则则则2/ )(21xxy+y=1PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn1010021332max323232131或或或或=+=yxyxxyxxxxxxyxfjPDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn例：某城市有例：某城市有6个区个区, 规划建消防站规划建消防站, 任何区发生火警时消防任何区发生火警时消防车要在车要在15分钟内赶到分钟内赶到, 各区间消防车行驶的时间见下表各区间消防车行驶的时间见下表, 求求设置消防站最少的方案。设置消防站最少的方案。地区地区123456 101016282720 210024321710 316240122721 428321201525 527172715014 620102125140集合覆盖集合覆盖问题举例问题举例PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn解：整数规划问题为：解：整数规划问题为：min: x1 + x2 + x3 + x4 + x5 + x6s.t.x1 + 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设消防站。设消防站。集合覆盖集合覆盖问题举例问题举例PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn固固特特公司的产公司的产品计品计划划固特产品公司的研发部最近开发出了三种新产固特产品公司的研发部最近开发出了三种新产品。这些产品都可以在两个工厂中生产，为了管理品。这些产品都可以在两个工厂中生产，为了管理的方便和防止新生产线的过度多元化，公司的管理的方便和防止新生产线的过度多元化，公司的管理层增加了如下的约束：在三种新产品中，最多只能层增加了如下的约束：在三种新产品中，最多只能选择两种进行生产；两个工厂中必须选出一个专门选择两种进行生产；两个工厂中必须选出一个专门生产新产品。生产新产品。PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cnGOOD产产品品公司数据公司数据(每周数量每周数量)957可销出的数量可销出的数量($thousands)375单位利润单位利润40264工厂工厂230243工厂工厂1产品产品3产品产品 2产品产品1每周可获得的生每周可获得的生 产时间（小时）产时间（小时）单位产品的生产时间单位产品的生产时间 （小时）（小时）PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn数学数学表表达达假设假设xi= 单位星期所生产的单位产品单位星期所生产的单位产品 i 的数量的数量( i = 1, 2, 3),yi= 1 生产产品生产产品 i; yi= 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 binary (i = 1, 2, 3, 4).PDF 文件使用 “pdfFactory Pro“ 试用版本创建 www.fineprint.cn电子电子表表格格模型模型3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21BCDEFGHI Product 1Product 2Product 3 Unit Profit ($thousands)573 Modified HoursHoursHours Hours Used Per Unit ProducedUsedAvailableAvailable Plant 134234.5=1 SFO- DEN0100100100101=1 SFO- SEA0010010010011=1 LAX- ORD0001001011011=1 LAX- SFO1000010001101=1 ORD- DEN0001100010001=