IE11_OR12 转运问题补充 and CH4 整数规划2

1、第1页运筹学运筹学CH4 CH4 整数规划整数规划|4.14.1整数规划问题的数学模型及解的特点整数规划问题的数学模型及解的特点|4.2 4.2 分支定界法分支定界法 （第二章习题讲解）（第二章习题讲解）|4.3 4.3 0-10-1整数规划整数规划|4.4 4.4 指派问题指派问题|4.5 4.5 应用举例应用举例第2页运筹学运筹学第3页运筹学运筹学例例2、某公司有、某公司有A1、 A2、 A3三个分厂生产某种物资，分别供三个分厂生产某种物资，分别供应应B1、 B2、 B3、 B4四个地区的销售公司销售。假设质量四个地区的销售公司销售。假设质量相同，有关数据如下表：相同，有关数据如下表： 试

2、求总费用为最少的调运方案。试求总费用为最少的调运方案。假设：假设： 1.每个分厂的物资不一定直接发运到销地，可以从其中几每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；个产地集中一起运； 2.运往各销地的物资可以先运给其中几个销地，再转运给运往各销地的物资可以先运给其中几个销地，再转运给其他销地；其他销地； 3.除产销地之外，还有几个中转站，在产地之间、销地之除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。间或在产地与销地之间转运。B1B2B3B4产量A13113107A219284A3741059销量3656和=20运价如下表：解：解：把此转运问题

3、转化为一般运输问题： 1、把所有产地、销地、转运站都同时看作产地和销地； 2、运输表中不可能方案的运费取作M，自身对自身的运费为0； 3、Ai： 产量为 20+原产量， 销量为 20； Ti ： 产量、销量均为 20； Bi： 产量为 20， 销量为 20 +原销量，其中20为各点可能变化的最大流量； 4、对于最优方案，其中 xi i 为自身对自身的运量，实际上不进行运作。A1A2A3T1T2T3T4B1B2B3B4A1132143311310A21-35-21928A33-1-2374105T12311322846T215-1114527T34-23121824T43232121-26B13

4、172411142B21194858-121B332104222423B410856746213 扩大的运输问题产销平衡与运价表： A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4 产量 A1 0 1 3 2 1 4 3 3 11 3 10 27 A2 1 0 M 3 5 M 2 1 9 2 8 24 A3 3 M 0 1 M 2 3 7 4 10 5 29 T1 2 3 1 0 1 3 2 2 8 4 6 20 T2 1 5 M 1 0 1 1 4 5 2 7 20 T3 4 M 2 3 1 0 2 1 8 2 4 20 T4 3 2 3 2 1 2 0 1 M 2 6 20

5、 B1 3 1 7 2 4 1 1 0 1 4 2 20 B2 11 9 4 8 5 8 M 1 0 2 1 20 B3 3 2 10 4 2 2 2 4 2 0 3 20 B4 10 8 5 6 7 4 6 2 1 3 0 20 销量 20 20 20 20 20 20 20 23 26 25 26 240 第6页运筹学运筹学4.1 4.1 整数规划问题的数学模型及解的特点整数规划问题的数学模型及解的特点max(min)zc xc xc xnn1122mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(. .22112222212111212111中部分或全部

6、取整数nxxx,11例例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。解：解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 为整数。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140 第8页运筹学运筹学全整数线性规划全整数线性规划混合整数线性规划混

7、合整数线性规划0-10-1整数线性规划整数线性规划第9页运筹学运筹学当放弃整数约束时得到的线性规当放弃整数约束时得到的线性规划称为整数规划的划称为整数规划的松弛问题松弛问题。整数规划的可行域是松弛问题的整数规划的可行域是松弛问题的可行域，反之不成立。可行域，反之不成立。第10页运筹学运筹学4.2 4.2 分支定界法分支定界法分枝：分枝：当当 不符合整数要求时，构造不符合整数要求时，构造两个约束条件：两个约束条件：iibx 1 iiiibxbx和加入松弛问题分别形成两个子问题（分枝）加入松弛问题分别形成两个子问题（分枝）定界：定界：当子问题获得整数规划的一个可行当子问题获得整数规划的一个可行解，

8、则它的目标函数值就构成一个界限解，则它的目标函数值就构成一个界限例例1 1取整数2121212121, 0,3121451149x . .xz maxxxxxxxxtsx132X254X1 231)310,23(AS解解S得：得：941 310,23 :21zxxA29/6132X254X1 231)310,23(AS2对对S分枝：分枝：构造约束：构造约束：21x和和11x形成分枝问题形成分枝问题S1和和S2，得解，得解B和和CS1)37, 1 (C)923, 2(B941923);(2, :zB31037);(1, :zCSA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=

9、7/3Z=10/3S1B:x1=2,x2=23/9Z=41/911x21x132X254X1 231)310,23(AS2对对S1分枝：分枝：构造约束：构造约束：32x和和22x形成分枝问题形成分枝问题S11和和S12，得解，得解DS12)2 ,(1433D14611433);,2( :zDS11无可行解无可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21x132X254X1 231)310,23(AS2对对S12

10、分枝：分枝：构造约束：构造约束：31x和和21x形成分枝问题形成分枝问题S121和和S122，得解，得解E和和FS121) 1 , 3(E4);(3,1 :zES122)2 , 2(F4);(2,2 :zFSA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/1411x32x22x21xS122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=431x21x0 1 2 3 44 3 2 1x1x20 1 2 3 44 3 2 1x1x2X

11、1 2X2 2X1 1X2 3P1:(1,9/4)Z=43/4P4: (0,3) Z=9P2:(2,1/2) Z=19/2P3: (1,2) Z=10P:(6/5,21/10) Z=111/10第26页运筹学运筹学|第二章习题讲解（由助教完成）第二章习题讲解（由助教完成）第27页运筹学运筹学4.3 0-14.3 0-1整数规划整数规划变量只能取变量只能取0 0或或1 1的整数线性规划的整数线性规划第28页运筹学运筹学 资金需求资金需求(1000$) 项项 目目 估计现值估计现值 第一年第一年 第二年第二年 第三年第三年 第四年第四年 工厂扩建工厂扩建 90 15 20 20 15 销售网点扩建

12、销售网点扩建 40 10 15 20 5 新生产流水线新生产流水线 10 10 0 0 4 新产品研究新产品研究 37 15 10 10 10 可用资金可用资金 40 50 40 35 第29页运筹学运筹学模型模型变量假设变量假设:项目没有选中如果第选中目项第果如iixi 0 1max z= 90 x1+40 x2+10 x3+37x4s.t.15x1+10 x2+10 x3+15x44020 x1+15x2 + 10 x45020 x1+20 x2+ 10 x44015x1+5x2+4x3+10 x435x1, x2, x3, x4, =0,1模型模型:第30页运筹学运筹学第31页运筹学运筹

13、学第32页运筹学运筹学第33页运筹学运筹学第34页运筹学运筹学第35页运筹学运筹学生产厂生产厂顾客需求顾客需求销售点销售点45DCBA7IIIII213I工厂工厂- -销售点配置问题销售点配置问题- -问题描述问题描述IIIIII生产能力生产能力1 18008001,0001,0001,2001,20030030035,00035,0002 240040050050070070020020045,00045,0003 380080060060050050030030040,00040,0004 450050060060070070020020042,00042,0005 57007006006

14、0050050040040040,00040,000ABCDI404080809090505040,00040,000II707040406060808020,00020,000III808030305050606060,00060,000需求量需求量200200300300150150250250运输成本运输成本: 工厂工厂-销售点销售点开设的固开设的固定成本定成本开设的固开设的固定成本定成本运输成本运输成本: 销售点销售点-客户客户问题问题: 为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?工厂工厂- -销售点配置问题销售点配置问题- -销售点不开设第销售点开设第厂不开设第厂开设第jjviiuji 0 1 0 1 客户运输量销售点到第第销售点运输量厂到第第客户需求量第厂供应能力第销售点开设成本第厂开设成本第客户运价销售点到第第销售点运价厂到第第kjyjixkDiBjcickjcjicjkijkijijkij 工厂工厂- -销售点配置问题销售点配置问题- - KkDy,N,jvyxMiuBxStvcucycxcZMinkNjjkKkjjkMiijiiNjijjNjjiNjMiijkKkjkMiijNjij, 2 , 1 , 21 , )( , 2 , 1 , 1111111111客户需求：供销平衡：供应能力：第39页运筹学运筹学第40页运筹学