《运筹学讲义影子价格-灵敏度分析-运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学讲义影子价格-灵敏度分析-运输问题.ppt（112页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、影子价格影子价格 1对偶最优解的经济含义对偶最优解的经济含义影子价格影子价格 代表着当第代表着当第i i个右端常数增加一个个右端常数增加一个单位时，最优目标函数值的相应增量。单位时，最优目标函数值的相应增量。其含义是在目前已给定的情况下，最其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率；优目标值随资源数量变化的变化率；其其经济含义经济含义是为约束条件所付出的代是为约束条件所付出的代价。价。当当B B是原问题的最优基时，是原问题的最优基时，Y=CBB-1就是影子价格向量就是影子价格向量。2ABC拥有量工 时1113材 料1479单件利润233影子价格举例影子价格举例3 y*1=5
2、/3,y*2=1/3 即工时的影子价格为即工时的影子价格为5/3，材料的影子价格为，材料的影子价格为1/3。分析分析：1.y1=5/3说明在现有的资源限量的条件下，说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来增加一个单位第一种资源可以给企业带来5/3元元的利润；如果要出售该资源，其价格至少在成本的利润；如果要出售该资源，其价格至少在成本价上加价上加5/3元。元。如果如果y1为为0，则表示增加第一种资源不会增加利，则表示增加第一种资源不会增加利润，因为第一种资源还润，因为第一种资源还 没有用完。没有用完。4影子价格是根据资源在生产中作出的贡献而作出的估价，这种估价不是资源的
3、市场价格。它反映了在最优经济结构中，在资源得到最优配置前提下，资源的边际使用价值。单纯形表中松弛变量所对应的检验数的相反数是在该经济结构中的影子价格，也可以说对偶问题的最优解向量是结构中的影子价格。5定理1：在某项经济活动中，在资源得到最优配置条件下，此定理的经济意义：（1）若生产一个单位第j种产品按消耗资源的影子价格计算的支出等于销售一个单位该产品所得收入，则可生产此产品。（2）如果生产一个单位的第j种产品按所消耗资源的影子价格计算的支出大于销售一个单位该产品得到的收入，则不宜生产此产品。6定理2：在某项经济活动中，在资源得到最优配置条件下，（1）若第种资源供大于求，即则该项资源的影子价格为
4、0（2）若第种资源供求平衡，即则该项资源的影子价格大于等于0。影子价格越大，说明这种资源越是相对紧缺（根据影子价格确定资源采购,当市场价格低于影子价格，就买进资源，当市场价格高于影子价格，就卖出资源）影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于07例例ABC拥有量工 时1113材 料1479单件利润233 y*1=5/3,y*2=1/3 即工时的影子价格为即工时的影子价格为5/3，材料的，材料的影子价格为影子价格为1/3。如如果果目目前前市市场场上上材材料料的的价价格格低低于于1/3，则则企企业业可可以以购购进进材材料料来来扩扩大大生产，反之
5、可以卖掉部分材料。生产，反之可以卖掉部分材料。如果有客户以高于如果有客户以高于5/3的价格购的价格购买工时，则可以出售一些工时，买工时，则可以出售一些工时，反之则反反之则反8和市场价格的比较市场价格影子价格商品的价值的货币表现资源最优利用时的边际价值随着市场的供求情况和有关方针，政策的变化而变化。随着经济结构的变化而变化，同一资源在不同的经济结构中影子价格不同。它的制定含定价者的主观因素它的形成完全由经济结构的客观条件确定。它的制定是个比较复杂的过程，不存在统一的计算公式。它的计算是比较容易的。用单纯形法求得9继续比较任何一种商品的市场价格都不可能为0影子价格可以为0，当资源过剩是，其影子价格
6、为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的生产
7、量，则模型如下：对偶问题11模型讨论：若把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，若生产产品I只能赚2万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y22,也就是一定比生产产品I赚得多。产品II，III同理。亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。如果把资源A的量由7增加到8，会导致什么结果呢？影子价格：在最有情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格
8、做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源。12影影子子价价格格的的经经济济意意义义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。程序编写：执行结果如下：13说明：从红框部分知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束。影子价格是对应最优基来说的，
9、如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了。通过对右端项的灵敏性分析：14在最优基不变时，A,B的右端项变化范围分别为(4.67,22)和(3.5,21)对问题(1)0.50.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)可聘用临时工人，付出的工资最
10、多是每小时几元?(3)A1的获利增加到 30元/公斤，应否改变生产计划？每天：161桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)时间480小时 至多加工100公斤A1 50桶牛奶 每天17max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VAL
11、UE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。模型求解 18模型求解 reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)OBJECTIVE FUNCTION VALUE 1)3360.000
12、 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量19 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.0
13、00000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000原料无剩余时间无剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释 20 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.
14、000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000结果解释 最优解下“资源”增加1单位时“效益”的增量 时间加1单位,利润增2 影子价格 35元可买到1桶牛奶，要买吗？35 4,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变。即对于C3而言,使最优解不变的条件是C34。33 CB XB cj23500 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1
15、 4/3-1/33x22012-1/31/31-8001-5/3-1/3价值系数CN发生改变 2x1211/20 7/6-1/65x3101/21-1/61/6-90-0.50-3/2-1/234 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3价值系数CB发生改变 C1-3C1C11-4/3C11/3C1-1C1-3 0,1-4/3C10,1/3C1-10 C13若C13/4 则x4进基，x1出基若3 C1 则x3或x5进基，x2出基35 CB XB c
16、j1/23300 xj b x1x2x3x4x50 x43111 100 x59147011/2x1110-1 4/3-1/33/43x22012-1/31/3-13/200-5/21/3-5/6价值系数CB发生改变 0 x43/43/40-3/4 1-1/43x29/41/417/401/4-27/4-1/40-9/40-3/436 CB XB cj43300 xj b x1x2x3x4x50 x43111 100 x59147014x1110-1 4/3-1/33x22012-1/31/33/2-10001-13/31/3价值系数CB发生改变 4X13111 100X56036-11-12
17、0-1-1-4037右端常数b发生改变 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3b14b1/3-33-b1/39/4b1 9-3-5b1/338 CB XB cj23300 xj b x1x2x3x4x50 x42111 100 x59147012x1-1/310-1 4/3-1/33x27/3012-1/31/3-19/300-1-5/3-1/3右端常数b发生改变 0X51-303-413X2211110-6-100-30最小比值1 139右端常
18、数b发生改变 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/3b24-b2/3b2/3-13b2 12-b2/3-540增加一个变量增加一个变量若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而
19、找出新的最优解。41灵敏度分析例2 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33/53x22012-1/31/36-800-1-5/3-1/35x623x65/31/32/35x63/53/50-3/5 4/5-1/513x29/5-1/5111/5-3/52/50-42/5-2/50-3/5-11/5-1/50 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/3-800-1-5/3-1/342增
20、加一个约束增加一个约束在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，所以需要增加约束条件。1）若把目前的最优解代入新增加的约束，能满足约束条件，则说明该增加的约束对最优解不构成影响，即不影响最优生产计划的实施。2)若当前最优解不满足新增加的约束，则应把新的约束添到原问题的最优表内新的一行中去，用对偶单纯形方法来进行迭代，求出新的最优解。43灵敏度分析例增加约束 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147010 x65221002x1110-1 4/3-1/33x22012-1/31/
21、30 x6522100-800-1-5/3-1/30 x60010010 CB XB cj23300 xj b x1x2x3x4x50 x43111 100 x59147012x1110-1 4/3-1/33x22012-1/31/344灵敏度分析增加约束 CB XB cj233000 xj b x1x2x3x4x5x62x1110-1 4/3-1/303x22012-1/31/300 x652210012x1110-1 4/3-1/303x22012-1/31/300 x6-100-1-201-800-1-5/3-1/30最小比值15/645灵敏度分析A中元素改变中元素改变如果N中数据改变，
22、可以用增加一个变量来处理如果B中元素改变，则情况较复杂，一般需要修改问题后重新求解46运输问题 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。47例 某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？单位运费B1B2B3产量A1646200A2655300销量15015020048解：产销平衡问题：总产量=总销量500 设 xij 为从
23、产地Ai运往销地Bj的运输量，得到下列运输量表：B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200Min C=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1、2；j=1、2、3）49运输规划问题的数学模型运输问题的一般形式：产销平衡A1、A2、Am 表示某物资的表示某物资的m个产地；个产地；B1、B2、Bn 表示表示某物质的某物质的n个销地；个销地；ai 表示产地表示产地Ai
24、的产量；的产量；bj 表示销地表示销地Bj 的销量；的销量；cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型：50变化：变化：1）有时目标函数求最大。如求利润最大或营业额最大）有时目标函数求最大。如求利润最大或营业额最大等；等；2）当某些运输线路上的能力有限制时，在模型中直接）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束加入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于
25、产时）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。或销地（产大于销时）。定理:设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。51表上作业法表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。步骤描述方法第一步 求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数ij全都非负时得到最优解，若存在检验数ij 0，说明还没有达到最优，转第三步。闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步52表上作业法例例2 2 某运输资料如下表所示：某运输资
26、料如下表所示：单位 销地 运价 产地产量311310719284741059销量3656问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？53解：第1步 求初始方案方法方法1：最小元素法：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调运）基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。，然后次小，直到最后供完为止。B1B2B3B4产量A17A2 4A39销量365631131019274105834163354总的运输费总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元元元素差额法对最小元素法进行
27、了改进，考虑到产地到销地元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是总运费是z=108+52+151=105最小元素法：最小元素法：5585102120151551510总运费总运费z=105+152+51=85后一种方案考虑到后一种方案考虑到C11与与C21之间之间的差额是的差额是82=6，如果不先调运，如果不先调运x21，到后来就有可
28、能，到后来就有可能x110，这，这样会使总运费增加较大，从而先样会使总运费增加较大，从而先调运调运x21，再是，再是x22，其次是，其次是x12用元素差额法求得的基本可行解更接近最优解，所用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。以也称为近似方案。56方法方法2：Vogel法法 元素差额法元素差额法1）从运价表中分别计算出各行和各列的最小运费和次最小运）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额行差额A177 7A2 41 1A391 1销量3656列差列差额额2
29、25 51 13 3311310192741058572）再从差值最大的行或列中找出最小运价确定供需关系和）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。时，划去运价表中对应的行或列。重复重复1)和和2)，直到找出初始解为至。，直到找出初始解为至。B1B2B3B4产量行差额行差额A177 7A2 41 1A3 91 1销量3656列差列差额额2 25 51 13 33113101927410585 558单位 销地 运价 产地产量行差额311310719284
30、741059销量3656列差额7113521559单位 销地 运价 产地产量行差额311310719284741059销量3656列差额7135275360单位 销地 运价 产地产量行差额311310719284741059销量3656列差额11351536312该方案的总运费该方案的总运费:(13)(46)(35)(210)(18)(35)85元元61第第第第2 2步步步步 最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）最优解的判别（检验数的求法）求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判
31、断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输问题的最优判别准则是：输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优求检验数的方法求检验数的方法有两种：有两种：闭回路法闭回路法 位势法（位势法（）62n闭回路的概念为一个闭回路为一个闭回路，集合中的变量称为回路的顶点，相邻两个变，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。如下表量的连线为闭回路的边。如下表63例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点，这8个顶点间用水平
32、或垂直线段连接起来，组成一条封闭的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一条回路中的顶点数一定是偶数，回路遇到顶点必须转一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表度与另一顶点连接，表33中的变量中的变量x 32及及x33不是闭回路不是闭回路的顶点，只是连线的交点。的顶点，只是连线的交点。64闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组例如变量组 不能构成一条闭回路，不能构成一条闭回路，但但A中包含有闭回路中包含有闭回路 变量组变量组 变量数是奇数，显然不是变量数是奇数，显然不
33、是闭回路，也不含有闭回路；闭回路，也不含有闭回路；65 可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。下表中用虚线画出以非基变量 x22 为起始顶点的闭回路。66表 以非基变量 x22 为起始顶点的闭回路销地产地B1B2B3B4产量3 11 3 410 371 39 2 18 47 4 610 5 39销量365620(产销平衡)A1A2A367 可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 2+3
34、10+5 4 1 即总的运费增加 1 个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。68 这个过程就是寻找一个以非基变量 x24 为起始顶点的闭回路 x24，x14，x13，x23，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为 8 10+3 2 -1，即总的运费减少 1 个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。69 这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也
35、称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为 24=-1，22=1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。70 如果规定作为起始顶点的非基变量为第 1 个顶点，闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点，那么就有 ij=(闭回路上的奇数次顶点单位运费之和)-(闭回路上的偶数次顶点单位运费之和)其中 ij 为非基变量的下角指标。71 按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图所示。销地产地B1B2B3B4产量A13 111 23 410 37A21 39 12 18-14A37 104 610125
36、39销量365620(产销平衡)表 初始基本可行解及检验数72 显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。73用位势法对初始方案进行最优性检验：用位势法对初始方案进行最优性检验：1）由）由 ij=Cij-（Ui+Vj）计算位势）计算位势Ui，Vj，因对基变量而言有，因对基变量而言有 ij=0，即即Cij-（Ui+Vj）=0，令，令U1=0即参照系即参照系2）再由）再由 ij=Cij-（Ui+Vj）计算非基变量的检验数计算非基变量的检
37、验数 ijB1B2B3B4UiA1A2A3Vj3113101927410584363130 0-1-1-5-53 310102 29 9（1 1）（2 2）（1 1）（-1-1）（1010）（1212）当存在非基当存在非基变量的检验变量的检验数数 kl 0，说，说明现行方案明现行方案为最优方案，为最优方案，否则目标成否则目标成本还可以进本还可以进一步减小。一步减小。74当存在非基变量的检验数kl 0 且kl=minij时，令Xkl 进基。从表中知可选X24进基。第第3步步 确定换入基的变量确定换入基的变量第第4步步 确定换出基的变量确定换出基的变量以进基变量以进基变量xik为起点的闭回路中，标
38、有负号的最小运量作为为起点的闭回路中，标有负号的最小运量作为调整量调整量，对应的基变量为出基变量，并打上对应的基变量为出基变量，并打上“”以示换以示换出作为非基变量。出作为非基变量。求求 =MinMinxijxij xijxij对应闭回路上的对应闭回路上的偶数标号格偶数标号格=xpqxpq 那么确那么确定定 xpqxpq为出基变量，为出基变量，为调整量；为调整量；75B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3()()()()调整步骤为：调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量在进基变量的闭回路中标有正号
39、的变量加上调整量，标有负号的变量减去调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。基可行解。然后求所有非基变量的检验数重新检验。1 12 25 576当所有非基变量的检验数均非负时，则当前调运方案即为最当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费：优方案，如表此时最小总运费：Z=(13)(46)(35)(210)(18)(35)85元元B1B2B3B4UiA1A2A3Vj3113101927410585363120 0-2-2-5-53 310103 39 9（0 0）（2
40、 2）（2 2）（1 1）（1212）（9 9）77表上作业法的计算步骤：分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案（最小确定初始调运方案（最小元素法或元素法或Vogel法）法）求检验数（位势法）求检验数（位势法）所有检验数所有检验数0找出绝对值最大的负检验数，用闭合找出绝对值最大的负检验数，用闭合回路调整，得到新的调运方案回路调整，得到新的调运方案得到最优方案，得到最优方案，算出总运价算出总运价78表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：表上作业法计算中的问题：（1）若运输问题的某一基可行解有多个非基变量的检验
41、数）若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代时，取它们中任一变量为换入变量均可使为负，在继续迭代时，取它们中任一变量为换入变量均可使目标函数值得到改善，但通常取目标函数值得到改善，但通常取ij0中最小者对应的变量为中最小者对应的变量为换入变量。换入变量。（2）无穷多最优解）无穷多最优解产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0，则该问题有无穷多最优解。，则该问题有无穷多最优解。79 退化解：退化解：表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运个数字格。但有时在分配运量时则需要同时划去一行和一列，
42、这时需要补一个量时则需要同时划去一行和一列，这时需要补一个0，以保，以保证有证有(m+n-1)个数字格作为基变量。一般可在划去的行和列个数字格作为基变量。一般可在划去的行和列的任意空格处加一个的任意空格处加一个0即可。即可。利用进基变量的闭回路对解进行调整时，标有负号的利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过最小运量（超过2个最小值）作为调整量个最小值）作为调整量，选择任意一个最，选择任意一个最小运量对应的基变量作为出基变量，并打上小运量对应的基变量作为出基变量，并打上“”以示作为以示作为非基变量。非基变量。80 销地产地B1B2B3B4产量A116A210A322销量81
43、412141241148310295116(0)(2)(9)(2)(1)(12)8 812124 42 28 81414如下例中如下例中11检验数是检验数是 0，经过调整，可得到另一个最优解。，经过调整，可得到另一个最优解。81 销地产地B1B2B3B4产量A17A24A39销量365620114431377821063 34 41 16 6 06 6在在x12、x22、x33、x34中任选一个变量作为基变量，例如选中任选一个变量作为基变量，例如选x34例例3：用最小元素法求初始可行解：用最小元素法求初始可行解82运输问题的应用1.求极大值问题2.目标函数求利润最大或营业额最大等问题。83求解
44、方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C，用一个较大的数M（Mmaxcij）去减每一个cij得到矩阵C，其中C=（Mcij）0,将C作为极小化问题的运价表，用表上用业法求出最优解。84例3 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.销地产地B1B2B3产量A12 25 58 89 9A29 910107 71010A36 65 54 41212销量8 814149 985 销地产地B1B2B3产量A12 25 58 89 9A29 910107 71010A36 65 54 41212销量8 814149 9得到新的最小化运
45、输问题，用表上作业法求解即可。得到新的最小化运输问题，用表上作业法求解即可。862.产销不平衡的运输问题产销不平衡的运输问题3.当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。当产大于销时，即：当产大于销时，即：数学模型为：数学模型为：87由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1，bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：具体求
46、解时具体求解时,只在只在运价表右端增加运价表右端增加一列一列B Bn n+1+1，运价，运价为零为零,销量为销量为b bn n+1+1即可即可88 当销大于产时，即：数学模型为：数学模型为：由于总销量大于总产由于总销量大于总产量量,故一定有些需求地故一定有些需求地不完全满足不完全满足,这时虚设这时虚设一个产地一个产地Am+1，产量，产量为：为：89销大于产化为平衡问题的数学模型为销大于产化为平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。，运价为零。产量为产量为am+1即可。即可。90例4 求下列表中极小化运输问题的最优解。B1B2
47、B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有：因为有：91所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj206035452018092下表为计算结果。可看出：产地A4还有20个单位没有运出。B1B2B3B4B5AiA1352560A24040A3102030A42010205
48、0Bj2060354520180933.生产与储存问题例例5 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用每积压一个季度需储存、维护等费用0.15万元。试求在完成合同万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。的情况下，使该厂全年生产总费用为最小的决策方案。季度生产
49、能力/台单位成本/万元2510.83511.130111011.394解：设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那么应满足：交货：x11 =10 生产：x11+x12+x13+x14 25 x12+x22=15 x22+x23+x24 35 x13+x23+x33=25 x33+x34 30 x14+x24+x34+x44 =20 x44 10把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产厂的产量；把第个生产厂的产量；把第 j 季季度交货的柴油机数目看作第度交货的柴油机数目看作第 j 个销售点的销量；设个销售点的销量；设cij是第是第i季度
50、生季度生产的第产的第j季度交货的每台柴油机的实际成本，应该等于该季度单位季度交货的每台柴油机的实际成本，应该等于该季度单位成本加上储存、维护等费用。可构造下列产销平衡问题：成本加上储存、维护等费用。可构造下列产销平衡问题：95 ji产量10.810.9511.111.2525M11.1011.2511.4035MM11.0011.1530MMM11.3010销量10152520 10070由于产大于销，加上一个虚拟的销地由于产大于销，加上一个虚拟的销地D，化为平衡问题，化为平衡问题，即可应用表上作业法求解。即可应用表上作业法求解。96该问题的数学模型：该问题的数学模型：Min f=10.8 x