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

（优选）运筹学讲义影子价格灵敏度分析运输问题目前一页\总数一百一十一页\编于十九点对偶最优解的经济含义――影子价格

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

当B是原问题的最优基时，Y=CBB-1就是影子价格向量。目前二页\总数一百一十一页\编于十九点ABC拥有量工时1113材料1479单件利润233影子价格举例目前三页\总数一百一十一页\编于十九点

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

即工时的影子价格为5/3，材料的影子价格为1/3。分析：

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

此定理的经济意义：（1）若生产一个单位第j种产品按消耗资源的影子价格计算的支出等于销售一个单位该产品所得收入，则可生产此产品。（2）如果生产一个单位的第j种产品按所消耗资源的影子价格计算的支出大于销售一个单位该产品得到的收入，则不宜生产此产品。目前六页\总数一百一十一页\编于十九点定理2：在某项经济活动中，在资源得到最优配置条件下，（1）若第种资源供大于求，即则该项资源的影子价格为0（2）若第种资源供求平衡，即则该项资源的影子价格大于等于0。影子价格越大，说明这种资源越是相对紧缺（根据影子价格确定资源采购,当市场价格低于影子价格，就买进资源，当市场价格高于影子价格，就卖出资源）影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0目前七页\总数一百一十一页\编于十九点例ABC拥有量工时1113材料1479单件利润233

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

即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则反目前八页\总数一百一十一页\编于十九点和市场价格的比较市场价格影子价格商品的价值的货币表现资源最优利用时的边际价值随着市场的供求情况和有关方针，政策的变化而变化。随着经济结构的变化而变化，同一资源在不同的经济结构中影子价格不同。它的制定含定价者的主观因素它的形成完全由经济结构的客观条件确定。它的制定是个比较复杂的过程，不存在统一的计算公式。它的计算是比较容易的。用单纯形法求得目前九页\总数一百一十一页\编于十九点继续比较任何一种商品的市场价格都不可能为0影子价格可以为0，当资源过剩是，其影子价格为0市场价格为已知数，相对比较稳定。影子价格则有赖于资源利用情况，是未知数。因企业生产任务，产品的结构等情况发生变化，资源的影子价格也随之改变。目前十页\总数一百一十一页\编于十九点例(生产决策问题)某工厂可以用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的生产量，则模型如下：对偶问题目前十一页\总数一百一十一页\编于十九点模型讨论：若把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，若生产产品I只能赚2万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y2≥2,也就是一定比生产产品I赚得多。产品II，III同理。亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。如果把资源A的量由7增加到8，会导致什么结果呢？影子价格：在最有情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源。目前十二页\总数一百一十一页\编于十九点影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。程序编写：执行结果如下：目前十三页\总数一百一十一页\编于十九点说明：从红框部分知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束。影子价格是对应最优基来说的，如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了。通过对右端项的灵敏性分析：目前十四页\总数一百一十一页\编于十九点在最优基不变时，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万元目前十五页\总数一百一十一页\编于十九点例(奶制品的加工问题)1桶牛奶3公斤A1

12小时8小时4公斤A2

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

制订生产计划，使每天获利最大(1)35元可买到1桶牛奶，买吗？若买，每天最多买多少?(2)可聘用临时工人，付出的工资最多是每小时几元?(3)A1的获利增加到30元/公斤，应否改变生产计划？每天：目前十六页\总数一百一十一页\编于十九点1桶牛奶3公斤A1

12小时8小时4公斤A2

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

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

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

50桶牛奶每天目前十七页\总数一百一十一页\编于十九点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元。模型求解目前十八页\总数一百一十一页\编于十九点模型求解reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量目前十九页\总数一百一十一页\编于十九点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三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释目前二十页\总数一百一十一页\编于十九点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元！目前二十一页\总数一百一十一页\编于十九点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，在允许范围内不变！(约束条件不变)结果解释目前二十二页\总数一百一十一页\编于十九点结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶？(目标函数不变)注意:充分但可能不必要目前二十三页\总数一百一十一页\编于十九点灵敏度分析目前二十四页\总数一百一十一页\编于十九点

在生产计划问题的一般形式中，A代表企业的技术状况，b代表企业的资源状况，而C代表企业产品的市场状况，在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。目前二十五页\总数一百一十一页\编于十九点更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。目前二十六页\总数一百一十一页\编于十九点

设线性规划问题：

maxZ=CXs.t.AX=bA代表企业技术状况b代表企业资源状况C代表企业产品市场状况（利润)

这些因素不变的情况下，企业最优生产计划和最大利润由线性规划的最优解和最优值决定。目前二十七页\总数一百一十一页\编于十九点最优化后分析，可归为以下两类问题：1）当系数A，b，C发生改变时，目前最优基是否还最优？2）为保持目前最优基还是最优，系数A，b，C的允许变化范围是什么？假设每次只有一种系数变化灵敏度分析包括以下五种：①目标系数C变化基变量系数发生变化；非基变量系数发生变化；②右端常数b变化③增加一个变量④增加一个约束⑤技术系数A发生变化目前二十八页\总数一百一十一页\编于十九点CBXBcjCBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N若B是最优基，则最优表形式如下灵敏度分析总是在最优表上进行目前二十九页\总数一百一十一页\编于十九点例2线性规划CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3目前三十页\总数一百一十一页\编于十九点灵敏度分析CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3目前三十一页\总数一百一十一页\编于十九点CBXBcj23300

xj

bx1x2x3x4X50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/33-2*（-1）-3*2=-1目前三十二页\总数一百一十一页\编于十九点CBXBcj23300

xj

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3－Ｚ-800-1-5/3-1/3价值系数CN发生改变C3C3-4如果C3>4,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变。即对于C3而言,使最优解不变的条件是C3≤4。目前三十三页\总数一百一十一页\编于十九点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/2目前三十四页\总数一百一十一页\编于十九点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出基目前三十五页\总数一百一十一页\编于十九点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/4目前三十六页\总数一百一十一页\编于十九点CBXBcj43300

xj

bx1x2x3x4x50x43111100x59147014x1110-14/3-1/3∞3x22012-1/31/33/2－Ｚ-10001-13/31/3价值系数CB发生改变4X13111100X56036-11－Ｚ-120-1-1-40目前三十七页\总数一百一十一页\编于十九点右端常数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/3目前三十八页\总数一百一十一页\编于十九点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最小比值11目前三十九页\总数一百一十一页\编于十九点右端常数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-5目前四十页\总数一百一十一页\编于十九点增加一个变量若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。目前四十一页\总数一百一十一页\编于十九点灵敏度分析例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/3目前四十二页\总数一百一十一页\编于十九点增加一个约束在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，所以需要增加约束条件。1）若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。2)若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。目前四十三页\总数一百一十一页\编于十九点灵敏度分析例增加约束CBXBcj23300xj

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

bx1x2x3x4x50x43111100x59147012x1110-14/3-1/33x22012-1/31/3目前四十四页\总数一百一十一页\编于十九点灵敏度分析增加约束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/6目前四十五页\总数一百一十一页\编于十九点灵敏度分析A中元素改变如果N中数据改变，可以用增加一个变量来处理如果B中元素改变，则情况较复杂，一般需要修改问题后重新求解目前四十六页\总数一百一十一页\编于十九点运输问题

问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。目前四十七页\总数一百一十一页\编于十九点例某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？单位运费B1B2B3产量A1646200A2655300销量150150200目前四十八页\总数一百一十一页\编于十九点解：产销平衡问题：总产量=总销量＝500

设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）目前四十九页\总数一百一十一页\编于十九点运输规划问题的数学模型运输问题的一般形式：产销平衡A1、A2、…、Am

表示某物资的m个产地；B1、B2、…、Bn

表示某物质的n个销地；ai

表示产地Ai的产量；bj

表示销地Bj

的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：目前五十页\总数一百一十一页\编于十九点变化：

1）有时目标函数求最大。如求利润最大或营业额最大等；

2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；

3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。定理:

设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。目前五十一页\总数一百一十一页\编于十九点表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数σij全都非负时得到最优解，若存在检验数σij<0，说明还没有达到最优，转第三步。闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步目前五十二页\总数一百一十一页\编于十九点表上作业法例2某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656问：应如何调运可使总运输费用最小？目前五十三页\总数一百一十一页\编于十九点解：第1步求初始方案方法1：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。B1B2B3B4产量A17A2

4A39销量3656311310192741058341633目前五十四页\总数一百一十一页\编于十九点总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元

元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是z=10×8+5×2+15×1=105最小元素法：目前五十五页\总数一百一十一页\编于十九点85102120151551510总运费z=10×5+15×2+5×1=85后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。目前五十六页\总数一百一十一页\编于十九点方法2：Vogel法元素差额法1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额A177A2

41A391销量3656列差额2513311310192741058目前五十七页\总数一百一十一页\编于十九点2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。B1B2B3B4产量行差额A177A2

41A3

91销量3656列差额25133113101927410585目前五十八页\总数一百一十一页\编于十九点单位销地运价产地产量行差额311310719284741059销量3656列差额71135215××目前五十九页\总数一百一十一页\编于十九点单位销地运价产地产量行差额311310719284741059销量3656列差额7135275×××3×目前六十页\总数一百一十一页\编于十九点单位销地运价产地产量行差额311310719284741059销量3656列差额113515×××3×631××2该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元目前六十一页\总数一百一十一页\编于十九点第2步最优解的判别（检验数的求法）

求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为λij由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优求检验数的方法有两种：闭回路法位势法（▲）目前六十二页\总数一百一十一页\编于十九点闭回路的概念为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表目前六十三页\总数一百一十一页\编于十九点例下表中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43

一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表3－3中的变量x32及x33不是闭回路的顶点，只是连线的交点。目前六十四页\总数一百一十一页\编于十九点闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组不能构成一条闭回路，但A中包含有闭回路

变量组变量数是奇数，显然不是闭回路，也不含有闭回路；目前六十五页\总数一百一十一页\编于十九点

可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。下表中用虚线画出以非基变量x22

为起始顶点的闭回路。目前六十六页\总数一百一十一页\编于十九点表以非基变量x22

为起始顶点的闭回路销地产地B1B2B3B4产量3[]11[]341037139[]218[]47[]4610[]539销量365620(产销平衡)A1A2A3目前六十七页\总数一百一十一页\编于十九点

可以计算出以非基变量x22

为起始顶点的闭回路调整使总的运输费用发生的变化为

9–2+3–10+5–4＝1

即总的运费增加1个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。目前六十八页\总数一百一十一页\编于十九点

这个过程就是寻找一个以非基变量x24

为起始顶点的闭回路——{x24

，x14

，x13

，x23}，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为8–10+3–2＝-1，即总的运费减少1个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。目前六十九页\总数一百一十一页\编于十九点

这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为24=-1，22=1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。目前七十页\总数一百一十一页\编于十九点

如果规定作为起始顶点的非基变量为第1个顶点，闭回路的其他顶点依次为第2个顶点、第3个顶点……，那么就有

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

其中ij

为非基变量的下角指标。目前七十一页\总数一百一十一页\编于十九点

按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图所示。

销地产地B1B2B3B4产量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539销量365620(产销平衡)表初始基本可行解及检验数目前七十二页\总数一百一十一页\编于十九点

显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。目前七十三页\总数一百一十一页\编于十九点用位势法对初始方案进行最优性检验：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，说明现行方案为最优方案，否则目标成本还可以进一步减小。目前七十四页\总数一百一十一页\编于十九点当存在非基变量的检验数kl<0且kl=min{ij}时，令Xkl进基。从表中知可选X24进基。第3步确定换入基的变量第4步确定换出基的变量以进基变量xik为起点的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示换出作为非基变量。求=Min{xijxij对应闭回路上的偶数标号格}=xpq那么确定xpq为出基变量，为调整量；目前七十五页\总数一百一十一页\编于十九点B1B2B3B4UiA1A2A3Vj311310192741058436313(＋)(－)(＋)(－)调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。125目前七十六页\总数一百一十一页\编于十九点当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：Z=(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元B1B2B3B4UiA1A2A3Vj3113101927410585363120-2-531039（0）（2）（2）（1）（12）（9）目前七十七页\总数一百一十一页\编于十九点表上作业法的计算步骤：分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或Vogel法）求检验数（位势法）所有检验数≥0找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案得到最优方案，算出总运价目前七十八页\总数一百一十一页\编于十九点表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取σij<0中最小者对应的变量为换入变量。（2）无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。目前七十九页\总数一百一十一页\编于十九点⑵退化解：

※表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。

※利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量θ，选择任意一个最小运量对应的基变量作为出基变量，并打上“×”以示作为非基变量。目前八十页\总数一百一十一页\编于十九点

销地产地B1B2B3B4产量A116A210A322销量81412141241148310295116(0)(2)(9)(2)(1)(12)81242814如下例中σ11检验数是0，经过调整，可得到另一个最优解。目前八十一页\总数一百一十一页\编于十九点

销地产地B1B2B3B4产量A17A24A39销量36562011443137782106×3×416×06×××在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34例3：用最小元素法求初始可行解目前八十二页\总数一百一十一页\编于十九点运输问题的应用

求极大值问题目标函数求利润最大或营业额最大等问题。目前八十三页\总数一百一十一页\编于十九点求解方法： 将极大化问题转化为极小化问题。设极大化问题的运价表为C，用一个较大的数M（M≥max{cij}）去减每一个cij得到矩阵C′，其中C′=（M－cij）≥0,将C′作为极小化问题的运价表，用表上用业法求出最优解。目前八十四页\总数一百一十一页\编于十九点例3下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.

销地产地B1B2B3产量A12589A2910710A365412销量8149目前八十五页\总数一百一十一页\编于十九点

销地产地B1B2B3产量A12589A2910710A365412销量8149得到新的最小化运输问题，用表上作业法求解即可。目前八十六页\总数一百一十一页\编于十九点

产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。

当产大于销时，即：数学模型为：目前八十七页\总数一百一十一页\编于十九点由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可目前八十八页\总数一百一十一页\编于十九点

当销大于产时，即：数学模型为：由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为：目前八十九页\总数一百一十一页\编于十九点销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。目前九十页\总数一百一十一页\编于十九点例4求下列表中极小化运输问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20603545180160因为有：目前九十一页\总数一百一十一页\编于十九点所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180目前九十二页\总数一百一十一页\编于十九点下表为计算结果。可看出：产地A4还有20个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180目前九十三页\总数一百一十一页\编于十九点3.生产与储存问题例5某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。季度生产能力/台单位成本/万元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.3目前九十四页\总数一百一十一页\编于十九点解：设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季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：目前九十五页\总数一百一十一页\编于十九点jiⅠⅡⅢⅣ产量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010销量1015252010070由于产大于销，加上一个虚拟的销地D，化为平衡问题，即可应用表上作业法求解。目前九十六页\总数一百一十一页\编于十九点该问题的数学模型：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.