运筹学讲义影子价格-灵敏度分析-运输问题

影子价格1精选课件对偶最优解的经济含义――影子价格

代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率；其经济含义是为约束条件所付出的代价。

当B是原问题的最优基时，Y=CBB-1就是影子价格向量。2精选课件ABC拥有量工时1113材料1479单件利润233影子价格举例3精选课件

y*1=5/3,y*2=1/3

即工时的影子价格为5/3，材料的影子价格为1/3。分析：1.y1=5/3说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来5/3元的利润；如果要出售该资源，其价格至少在本钱价上加5/3元。如果y1为0，那么表示增加第一种资源不会增加利润，因为第一种资源还没有用完。4精选课件影子价格是根据资源在生产中作出的奉献而作出的估价，这种估价不是资源的市场价格。它反映了在最优经济结构中，在资源得到最优配置前提下，资源的边际使用价值。单纯形表中松弛变量所对应的检验数的相反数是在该经济结构中的影子价格，也可以说对偶问题的最优解向量是结构中的影子价格。5精选课件定理1：在某项经济活动中，在资源得到最优配置条件下，

此定理的经济意义：〔1〕假设生产一个单位第j种产品按消耗资源的影子价格计算的支出等于销售一个单位该产品所得收入，那么可生产此产品。〔2〕如果生产一个单位的第j种产品按所消耗资源的影子价格计算的支出大于销售一个单位该产品得到的收入，那么不宜生产此产品。6精选课件定理2：在某项经济活动中，在资源得到最优配置条件下，〔1〕假设第种资源供大于求，即那么该项资源的影子价格为0〔2〕假设第种资源供求平衡，即那么该项资源的影子价格大于等于0。影子价格越大，说明这种资源越是相对紧缺〔根据影子价格确定资源采购,当市场价格低于影子价格，就买进资源，当市场价格高于影子价格，就卖出资源〕影子价格越小，说明这种资源相对不紧缺如果最优生产方案下某种资源有剩余，这种资源的影子价格一定等于07精选课件例ABC拥有量工时1113材料1479单件利润233y*1=5/3,y*2=1/3即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，那么企业可以购进材料来扩大生产，反之可以卖掉局部材料。如果有客户以高于5/3的价格购置工时，那么可以出售一些工时，反之那么反8精选课件和市场价格的比较市场价格影子价格商品的价值的货币表现资源最优利用时的边际价值随着市场的供求情况和有关方针，政策的变化而变化。随着经济结构的变化而变化，同一资源在不同的经济结构中影子价格不同。它的制定含定价者的主观因素它的形成完全由经济结构的客观条件确定。它的制定是个比较复杂的过程，不存在统一的计算公式。它的计算是比较容易的。用单纯形法求得9精选课件继续比较任何一种商品的市场价格都不可能为0影子价格可以为0，当资源过剩是，其影子价格为0市场价格为已知数，相对比较稳定。影子价格则有赖于资源利用情况，是未知数。因企业生产任务，产品的结构等情况发生变化，资源的影子价格也随之改变。10精选课件例(生产决策问题)某工厂可以用A，B两种原料生产I,II,III三种产品，每种产品需要同时用两种原料，有关数据如下表(单位消耗与资源限制)：产品I产品II产品III现有原料/t原料A2127原料B13211单位产品利润/万元231求：(1)假设目前市场上原料A的实际价格为0.5万元/t，工厂应如何决策？(2)假设目前市场上原料B的实际价格为0.8万元/t，工厂应如何决策？解：建立模型，设x1,x2,x3分别表示I，II，III的生产量，那么模型如下：对偶问题11精选课件模型讨论：假设把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，假设生产产品I只能赚2万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y2≥2,也就是一定比生产产品I赚得多。产品II，III同理。亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。如果把资源A的量由7增加到8，会导致什么结果呢？影子价格：在最有情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售局部资源以获得更大利润，否那么，那么从市场买进该资源。12精选课件影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。程序编写：执行结果如下：13精选课件说明：从红框局部知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束。影子价格是对应最优基来说的，如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了。通过对右端项的灵敏性分析：14精选课件在最优基不变时，A,B的右端项变化范围分别为(4.67,22)和(3.5,21)对问题(1)0.5<0.6,应该购进原料A，扩大生产能力，最大购进15t，利润增加(0.6-0.50*15=1.5万元对于问题(2),0.8>0.6，应该售出局部原料将使利润更大，最大售出量为3.33t,利润将会增加(0.8-0.6)*3.33=0.66万元15精选课件例(奶制品的加工问题)1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产方案，使每天获利最大(1)35元可买到1桶牛奶，买吗？假设买，每天最多买多少?(2)可聘用临时工人，付出的工资最多是每小时几元?(3)A1的获利增加到30元/公斤，应否改变生产方案？每天：16精选课件1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供给劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天17精选课件max72x1+64x2st2〕x1+x2<503〕12x1+8x2<4804〕3x1<100end

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。模型求解18精选课件模型求解reducedcost值表示当该非基变量增加一个单位时〔其他非基变量保持不变〕目标函数减少的量(对max型问题)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量19精选课件OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2〕x1+x2<503〕12x1+8x2<4804〕3x1<100end三种资源“资源〞剩余为零的约束为紧约束〔有效约束〕结果解释20精选课件OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000结果解释最优解下“资源〞增加1单位时“效益〞的增量时间加1单位,利润增2影子价格35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！21精选课件RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系数范围(64,96)

x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产方案x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释22精选课件结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶？(目标函数不变)注意:充分但可能不必要23精选课件灵敏度分析24精选课件在生产方案问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产方案和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最正确的生产方案，而在方案实施前或实施中上述状况发生了改变，那么决策者所关心的是目前所执行的方案还是不是最优，如果不是应该如何修订原来的最优方案。25精选课件更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反响，即所谓“方案不如变化快〞，企业应当预先了解，当各项因素变化时，应当作出什么样的反响。26精选课件设线性规划问题：maxZ=CXs.t.AX=bA代表企业技术状况b代表企业资源状况C代表企业产品市场状况〔利润)这些因素不变的情况下，企业最优生产方案和最大利润由线性规划的最优解和最优值决定。27精选课件最优化后分析，可归为以下两类问题：1〕当系数A，b，C发生改变时，目前最优基是否还最优？2〕为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化灵敏度分析包括以下五种：①目标系数C变化基变量系数发生变化；非基变量系数发生变化；②右端常数b变化③增加一个变量④增加一个约束⑤技术系数A发生变化28精选课件CBXBcjCBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N假设B是最优基，那么最优表形式如下灵敏度分析总是在最优表上进行29精选课件例2线性规划CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/330精选课件灵敏度分析CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/331精选课件CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/33-2*〔-1〕-3*2=-132精选课件CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3价值系数CN发生改变C3C3-4如果C3>4,那么目前解不再是最优解,应该用单纯形方法继续求解,否那么解不变。即对于C3而言,使最优解不变的条件是C3≤4。33精选课件CBXBcj23500

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/3∞3x22012-1/31/31－Ｚ-8001-5/3-1/3价值系数CN发生改变2x1211/207/6-1/65x3101/21-1/61/6－Ｚ-90-0.50-3/2-1/234精选课件CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3价值系数CB发生改变C1-3C1C11-4/3C11/3C1-1C1-3≤0,1-4/3C1≤0,1/3C1-1≤0¾≤C1≤3假设C1<3/4那么x4进基，x1出基假设3<C1那么x3或x5进基，x2出基35精选课件CBXBcj1/23300

xj

bx1x2x3x4x50x43111100x59147011/2x1110-14/3-1/33/43x22012-1/31/3∞－Ｚ-13/200-5/21/3-5/6价值系数CB发生改变0x43/43/40-3/41-1/43x29/41/417/401/4－Ｚ-27/4-1/40-9/40-3/436精选课件CBXBcj43300

xj

bx1x2x3x4x50x43111100x59147014x1110-14/3-1/3∞3x22012-1/31/33/2－Ｚ-10001-13/31/3价值系数CB发生改变4X13111100X56036-11－Ｚ-120-1-1-4037精选课件右端常数b发生改变CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3b14b1/3-33-b1/39/4≤b1≤9-3-5b1/338精选课件CBXBcj23300xj

bx1x2x3x4x50x42111100x59147012x1-1/310-14/3-1/33x27/3012-1/31/3－Ｚ-19/300-1-5/3-1/3右端常数b发生改变0X51-303-413X2211110－Ｚ-6-100-30最小比值1139精选课件右端常数b发生改变CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3b24-b2/3b2/3-13≤b2≤12-b2/3-540精选课件增加一个变量假设企业在方案期内，有新的产品可以生产，那么在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。假设检验数非正，那么原最优解仍为最优，原生产方案不变，不生产这种新产品；否那么，当检验数为正时，那么应以该变量进基，作单纯形迭代，从而找出新的最优解。41精选课件灵敏度分析例2CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33/53x22012-1/31/36－Ｚ-800-1-5/3-1/35x623x65/31/32/35x63/53/50-3/54/5-1/513x29/5-1/5111/5-3/52/50－Ｚ-42/5-2/50-3/5-11/5-1/50CBXBcj23300xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/342精选课件增加一个约束在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产方案造成影响，所以需要增加约束条件。1〕假设把目前的最优解代入新增加的约束，能满足约束条件，那么说明该增加的约束对最优解不构成影响，即不影响最优生产方案的实施。2)假设当前最优解不满足新增加的约束，那么应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。43精选课件灵敏度分析例增加约束CBXBcj23300xj

bx1x2x3x4x50x43111100x59147010x65221002x1110-14/3-1/33x22012-1/31/30x6522100－Ｚ-800-1-5/3-1/30x60010010CBXBcj23300xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/344精选课件灵敏度分析增加约束CBXBcj233000xj

bx1x2x3x4x5x62x1110-14/3-1/303x22012-1/31/300x652210012x1110-14/3-1/303x22012-1/31/300x6-100-1-201－Ｚ-800-1-5/3-1/30最小比值15/645精选课件灵敏度分析A中元素改变如果N中数据改变，可以用增加一个变量来处理如果B中元素改变，那么情况较复杂，一般需要修改问题后重新求解46精选课件运输问题问题的提出一般的运输问题就是要解决把某种产品从假设干个产地调运到假设干个销地，在每个产地的供给量与每个销地的需求量，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。47精选课件例某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？单位运费B1B2B3产量A1646200A2655300销选课件解：产销平衡问题：总产量=总销量＝500设xij为从产地Ai运往销地Bj的运输量，得到以下运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1、2；j=1、2、3〕49精选课件运输规划问题的数学模型运输问题的一般形式：产销平衡A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物质的n个销地；ai表示产地Ai的产量；bj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量，得到以下一般运输量问题的模型：50精选课件变化：1〕有时目标函数求最大。如求利润最大或营业额最大等；2〕当某些运输线路上的能力有限制时，在模型中直接参加约束条件〔等式或不等式约束)；3〕产销不平衡时，可参加假想的产地〔销大于产时〕或销地〔产大于销时〕。定理:设有m个产地n个销地且产销平衡的运输问题，那么基变量数为m+n-1。51精选课件表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数σij全都非负时得到最优解，若存在检验数σij<0，说明还没有达到最优，转第三步。闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步52精选课件表上作业法例2某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656问：应如何调运可使总运输费用最小？53精选课件解：第1步求初始方案方法1：最小元素法根本思想是就近供给，即从运价最小的地方开始供给〔调运〕，然后次小，直到最后供完为止。B1B2B3B4产量A17A2

4A39销量365631131019274105834163354精选课件总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元 元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否那么会增加总运费。例如下面两种运输方案。85102120151515510总运费是z=10×8+5×2+15×1=105最小元素法：55精选课件85102120151551510总运费z=10×5+15×2+5×1=85后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12用元素差额法求得的根本可行解更接近最优解，所以也称为近似方案。56精选课件方法2：Vogel法元素差额法1〕从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额A177A2

41A391销量3656列差额251331131019274105857精选课件2〕再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供给完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。B1B2B3B4产量行差额A177A2

41A3

91销量3656列差额2513311310192741058558精选课件单位销地运价产地产量行差额311310719284741059销量3656列差额71135215××59精选课件单位销地运价产地产量行差额311310719284741059销量3656列差额7135275×××3×60精选课件单位销地运价产地产量行差额311310719284741059销量3656列差额113515×××3×631××2该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元61精选课件第2步最优解的判别〔检验数的求法〕 求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij由第一章知，求最小值的运输问题的最优判别准那么是：所有非基变量的检验数都非负，那么运输方案最优求检验数的方法有两种：闭回路法位势法〔▲〕62精选课件闭回路的概念为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表63精选课件例下表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表3－3中的变量x32及x33不是闭回路的顶点，只是连线的交点。64精选课件闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组不能构成一条闭回路，但A中包含有闭回路

变量组变量数是奇数，显然不是闭回路，也不含有闭回路；65精选课件可以证明，如果对闭回路的方向不加区别〔即只要起点及其他所有顶点完全相同，而不区别行进方向〕，那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。下表中用虚线画出以非基变量x22为起始顶点的闭回路。66精选课件表以非基变量x22为起始顶点的闭回路销地产地B1B2B3B4产量3[]11[]341037139[]218[]47[]4610[]539销量365620(产销平衡)A1A2A367精选课件可以计算出以非基变量x22为起始顶点的闭回路调整使总的运输费用发生的变化为9–2+3–10+5–4＝1即总的运费增加1个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有假设干个基变量的取值受其影响。68精选课件这个过程就是寻找一个以非基变量x24为起始顶点的闭回路——{x24，x14，x13，x23}，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为8–10+3–2＝-1，即总的运费减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。69精选课件这样，利用单位产品变化〔运输的单位费用〕可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为24=-1，22=1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。70精选课件如果规定作为起始顶点的非基变量为第1个顶点，闭回路的其他顶点依次为第2个顶点、第3个顶点……，那么就有

ij=(闭回路上的奇数次顶点单位运费之和)-(闭回路上的偶数次顶点单位运费之和)其中ij

为非基变量的下角指标。71精选课件按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如下图。销地产地B1B2B3B4产量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539销量365620(产销平衡)表初始基本可行解及检验数72精选课件显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。73精选课件用位势法对初始方案进行最优性检验：1〕由ij=Cij-〔Ui+Vj〕计算位势Ui，Vj，因对基变量而言有ij=0，即Cij-〔Ui+Vj〕=0，令U1=0即参照系2〕再由ij=Cij-〔Ui+Vj〕计算非基变量的检验数ijB1B2B3B4UiA1A2A3Vj3113101927410584363130-1-531029〔1〕〔2〕〔1〕〔-1〕〔10〕〔12〕当存在非基变量的检验数kl≥0，说明现行方案为最优方案，否那么目标本钱还可以进一步减小。74精选课件当存在非基变量的检验数

kl<0且kl=min{ij}时，令Xkl进基。从表中知可选X24进基。第3步确定换入基的变量第4步确定换出基的变量以进基变量xik为起点的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×〞以示换出作为非基变量。求

=Min{xij

xij对应闭回路上的偶数标号格}=xpq那么确定xpq为出基变量，

为调整量；75精选课件B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。12576精选课件当所有非基变量的检验数均非负时，那么当前调运方案即为最优方案，如表此时最小总运费：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039〔0〕〔2〕〔2〕〔1〕〔12〕〔9〕77精选课件表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（位势法）所有检验数≥0找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案得到最优方案，算出总运价78精选课件表上作业法计算中的问题：〔1〕假设运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij<0中最小者对应的变量为换入变量。〔2〕无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，那么该问题有无穷多最优解。79精选课件⑵退化解： ※表格中一般要有(m+n-1)个数字格。但有时在分配运量时那么需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。 ※利用进基变量的闭回路对解进行调整时，标有负号的最小运量〔超过2个最小值〕作为调整量θ，选择任意一个最小运量对应的基变量作为出基变量，并打上“×〞以示作为非基变量。80精选课件销地产地B1B2B3B4产量A116A210A322销量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11检验数是0，经过调整，可得到另一个最优解。81精选课件销地产地B1B2B3B4产量A17A24A39销量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34例3：用最小元素法求初始可行解82精选课件运输问题的应用求极大值问题目标函数求利润最大或营业额最大等问题。83精选课件求解方法： 将极大化问题转化为极小化问题。设极大化问题的运价表为C，用一个较大的数M〔M≥max{cij}〕去减每一个cij得到矩阵C′，其中C′=〔M－cij〕≥0,将C′作为极小化问题的运价表，用表上用业法求出最优解。84精选课件例3以下矩阵C是Ai〔I=1，2，3〕到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.销地产地B1B2B3产量A12589A2910710A365412销量814985精选课件销地产地B1B2B3产量A12589A2910710A365412销量8149得到新的最小化运输问题，用表上作业法求解即可。86精选课件

产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。当产大于销时，即：数学模型为：87精选课件由于总产量大于总销量，必有局部产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,〔i=1，…，m〕。那么平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可88精选课件当销大于产时，即：数学模型为：由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：89精选课件销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。90精选课件例4求以下表中极小化运输问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因为有：91精选课件所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj206035452018092精选课件下表为计算结果。可看出：产地A4还有20个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj206035452018093精选课件3.生产与储存问题例5某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。该厂各季度的生产能力及生产每台柴油机的本钱如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。季度生产能力/台单位成本/万元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.394精选课件解：设xij为第i季度生产的第j季度交货的柴油机数目，那么应满足：交货：

x11=10生产：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第j个销售点的销量；设cij是第i季度生产的第j季度交货的每台柴油机的实际本钱，应该等于该季度单位本钱加上储存、维护等费用。可构造以下产销平衡问题：95精选课件jiⅠⅡⅢⅣ产量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010销量1015252010070由于产大于销，加上一个虚拟的销地D，化为平衡问题，即可应用表上作业法求解。96精选课件该问题的数学模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23 +11.4x24+11.0x33+11.15x34+11.3x44

jiⅠⅡⅢⅣD产量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010销选课件jiⅠⅡⅢⅣD产量Ⅰ1015025Ⅱ053035Ⅲ25530Ⅳ1010销量1015252030100100最优生产决策如下表，最小费用z＝773万元。98精选课件例(运输问题)两个粮库A1,A2,向三个粮站B1,B2,B3调运大米，两个粮库现存大米分别为4t，8t，三个两站至少需要大米分别为2t,4t,5t，两个粮库到三个粮站的距离(km)如下表，求使运费最低。B1B2B3库存A1122484A23012248需求245解：(1)问题分析：总需求量为11t，小于总库存量12