IE11-OR12转运问题补充andCH4整数规划2

第12讲目录转运问题(补充证明)CH4整数规划§4.1整数规划问题的数学模型及解的特点§4.2分支定界法

（第二章习题讲解）§4.30-1整数规划§4.4指派问题§4.5应用举例“转运问题”证明例2、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：

试求总费用为最少的调运方案。假设：

1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；

2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；

3.除产销地之外，还有几个中转站，在产地之间、销地之间或在产地与销地之间转运。运价如下表：解：把此转运问题转化为一般运输问题：

1、把所有产地、销地、转运站都同时看作产地和销地；

2、运输表中不可能方案的运费取作M，自身对自身的运费为0；

3、Ai：产量为20+原产量，销量为20；Ti

：产量、销量均为20；Bi：产量为20，销量为20+原销量，其中20为各点可能变化的最大流量；

4、对于最优方案，其中xii

为自身对自身的运量，实际上不进行运作。扩大的运输问题产销平衡与运价表：§4.1整数规划问题的数学模型及解的特点

整数线性规划问题的一般形式例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。解：设x1、

x2分别为甲、乙两种货物托运的件数，建立模型目标函数：Maxz=2x1+3x2

约束条件：

195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0为整数。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140

整数线性规划问题的分类全整数线性规划混合整数线性规划0-1整数线性规划整数规划与其松弛问题当放弃整数约束时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域，反之不成立。§4.2分支定界法混合整数规划的求解---分枝定界方法分枝：当不符合整数要求时，构造两个约束条件：加入松弛问题分别形成两个子问题（分枝）定界：当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限例1132X254X1

231S解S得：29/6132X254X1

231S2对S分枝：构造约束：和形成分枝问题S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1

231S2对S1分枝：构造约束：和形成分枝问题S11和S12，得解DS12S11无可行解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/14132X254X1

231S2对S12分枝：构造约束：和形成分枝问题S121和S122，得解E和FS121S122SA: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/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4例2用分枝定界法求解：MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。012344321x1x2分枝：X11,x12P1P2两个子问题：（P1）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

1

，整数用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=43/4（P2）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20，x1

2

，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=19/2012344321x1x2再对（P1）分枝：X11（P3）x22（P4）x23P1P2P3P4（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x22整数用单纯形法可解得相应的（P3）的最优解（1，2）Z=10（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.

3x1+4x2124x1+2x29x1,x20,x1

1,x23整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=9X12X2

2X11X23P1:(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原问题的最优解（1，2）Z=10第二章习题讲解（由助教完成）§4.30-1整数规划

1、0-1整数规划变量只能取0或1的整数线性规划2、0-1规划的应用例1项目投资预算模型变量假设:模型:例2：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。序号1234567物品食品氧气冰镐绳索帐篷相机设备重量55261224重要系数201518148410解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4

+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….7背包问题(KnapsackProblem)一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划:MaxZ=Σcjxjs.t.Σajxjb

xj=0或1例3工厂-销售点配置问题生产厂顾客需求销售点45DCBA7IIIII213I工厂-销售点配置问题-问题描述问题:为使经营成本最低,应开设那些工厂及销售点?工厂-销售点配置问题-模型参数工厂-销售点配置问题-模型