[管理学]ie10_or12ch3运输问题4andch4整数规划

《[管理学]ie10_or12ch3运输问题4andch4整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第12讲目录转运问题(补充证明)CH4整数规划§4.1整数规划问题的数学模型及解的特点§4.2分支定界法§4.30-1整数规划§4.4指派问题§4.5应用举例“转运问题”证明例2、某公司有A1、A2、A3三个分厂生产某种物资，分别供应B1、B2、B3、B4四个地区的销售公司销售。假设质量相同，有关数据如下表：试求总费用为最少的调运方案。假设：1.每个分厂的物资不一定直接发运到销地，可以从其中几个产地集中一起运；2.运往各销地的物资可以先运给其中几个销地，再转运给其他销地；3.除产销地之外，还有几个中转站，在产地之间、销地

2、之间或在产地与销地之间转运。运价如下表：解：把此转运问题转化为一般运输问题：1、把所有产地、销地、转运站都同时看作产地和销地；2、运输表中不可能方案的运费取作M，自身对自身的运费为0；3、Ai：产量为20+原产量，销量为20；Ti：产量、销量均为20；Bi：产量为20，销量为20+原销量，其中20为各点可能变化的最大流量；4、对于最优方案，其中xii为自身对自身的运量，实际上不进行运作。扩大的运输问题产销平衡与运价表：§4.1整数规划问题的数学模型及解的特点整数线性规划问题的一般形式例1.某公司拟用集装箱托运甲、乙两种货

3、物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型目标函数：Maxz=2x1+3x2约束条件：195x1+273x2≤13654x1+40x2≤140x1≤4x1，x2≥0为整数。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140整数线性规划问题的分类全整数线性规划混合整数线性规划0-1整数线性规划整数规划与其松弛问题当放弃整数约束

4、时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域，反之不成立。§4.2分支定界法混合整数规划的求解---分枝定界方法分枝：当不符合整数要求时，构造两个约束条件：加入松弛问题分别形成两个子问题（分枝）定界：当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限例1132X254X1231S解S得：29/6132X254X1231S2对S分枝：构造约束：和形成分枝问题S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x

5、1=2,x2=23/9Z=41/9132X254X1231S2对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/14132X254X1231S2对S12分枝：构造约束：和形成分枝问题S121和S122，得解E和FS121S122SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z

6、=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+4x2124x1+2x29x1,x20整数用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。012344321x1x2分枝：X11,x12P1P2两个子问题：（P1）MaxZ=4x1+3x2s.t.3x1+4x2124x

7、1+2x29x1,x20，x11，整数用单纯形法可解得相应的（P1）的最优解（1，9/4）Z=43/4（P2）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20，x12，整数用单纯形法可解得相应的（P2）的最优解（2，1/2）Z=19/2012344321x1x2再对（P1）分枝：X11（P3）x22（P4）x23P1P2P3P4（P1）两个子问题：（P3）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20,x11,x22整数用单纯形法

8、可解得相应的（P3）的最优解（1，2）Z=10（P1）两个子问题：（P4）MaxZ=4x1+3x2s.t.3x1+4x2124x1+2x29x1,x20,x11,x23整数用单纯形法可解得相应的（P4）的最优解（0，3）Z=9X12X22X11X23P1:(1,9/4)Z=43/4P4:(0,3)Z