运输问题悖论及其出现的条件①

《运输问题悖论及其出现的条件①》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2O卷第1期‘新疆师范大学学报，(自然科学版)v0J．20，No．18001年3月JournofXinjbmgNormalUniversityMar．2001(NaturslSciencesEdition)运输问题悖论及其出现的条件①文平(新一时蛏学院基柚每．乌●术齐．830012)摘要车丈提出了运糟同题的奇特理簟——运糟问置悖论，井筑退化运■问厦和非退化运输同曩悖论出现的基件进行了讨论摹■词运■问置蕞盈墓壹量中圈分类号[oz21]文献标识码：A文章编号：1008．9659(2001)．01—0016—041问题的提出先看一个例子例1．最优运输计划

2、表如下B1B2B3l32Al2×31l4×46249最优值为∑∑。一36现将产地A1的产量增加2个单位，销地B2的销量增加2个单位，则最优运输计划表为BlB2B3i32Al72×53l4×64269①收薯日期．2∞O一9—28第1期文平运输问题悖论及其出现的条件·17·‘最优值为∑∑：34从上面例子可以看劐；在产地、销地、单位运价均相同的情况下，运输总量增加了2个单位，但总运价却减少了2个单位，这种奇特的现象称为运辖问题悖论。2非退化运输问题悖论出现的条件弓l理l设】【io是一个非基变量，则一定可以找到若干个基变量再_I，xi，⋯x，与构成一个闭回路

3、。§I理2设是一非基变量。和基变量IJl，xt⋯¨构成一个闭回赂，当第个产地增加产量Y，第j。个销地增加销量Y，且Y满足Y≤min~x。_)，是闭圆路上的奇点t则原来的基变量仍是基变量t原来的非基变量仍是非基变量。证明：设xj是运输问题的最优解，则存在常数u，u“u’v_，v：⋯v。满足。∑xa。(i1，2⋯．．m)、2]5x，b，(j1，2⋯⋯n)(u。+v)一≤OXi1-o(i—l，2⋯⋯n)现在x所在闭回赂的偶点上加Y，在奇点是减Y，而其它值不变，这样就构成了一组新的x(i1，2⋯⋯m．j=l'2⋯⋯n)且xI．满足。]厶x=a．(i≠i0ti

4、1．2⋯⋯)]厶xa。0+Y(i=i0)]厶x=b(j≠，ilt2⋯⋯m)]厶x：b+Y(jj0)(u．+j)-C≤0(i1，2⋯⋯triot．j—l'2⋯⋯n)又Y-~<．min{xlj)，，是Xioj~所在闭路上的奇点故x≥O，(il'2⋯⋯m．j1，2⋯⋯n)所以最优解只发生值的变化。但其变量仍是其变量非其变量仍是非基变量。定理1．设x．，是运辖问题的最优解涵上一非基变量，若。+≤O，则当a”blo同时增加Y，总运价不会增加。特别当~iojo+c<0时，总运价减少，其中Y≤rain{)，是闭回路上的奇点。证明0j0是一个非基变量，由引理1，存在

5、若干变量”，⋯Xi~ik与之构成闭回赂，当a，bjo同时增加Y时t让闭回路上的偶点增加Y，奇点(不包括x。)减少Y，由引理2，原来的基变量仍是基变量，只不过值发生变化而已，现在来看总运价：∑∑一∑∑一∑∑．，Y一∑∑Y■目■±∞■^■目鼻±f直=(+)Y新疆师范大学学报(自然科学版)∞O1年故当0j0+c≤O时，总运费不增。特别+c．0j0

6、2××2525A2513133最优值为∑∑c'ix．。一18由定理一可知，产地A1的产量，销地B2的销量同增1个单位，则最优化运输计划表为B1B2B324lA13I××3525A2514O43最优值为∑∑。，一16现考察两个非基变量，均不满足定理一的条件，我们自然要阅，悖论还会出现吗?请看下例。倒3．产地A1的产量，销地B2的销量同增1个单位，则最优化运输计兜『表为B1B2B3A1I。40l34525A25×5×53最优值为∑∑ci一15从例3可知悖论还会出现定理2设运输表是一最优运输计划，非基变量满足第l期文平运输问题悖论及其出现的条件·l9·1)

7、m+e㈣>O同时增加Y使总运价增加了eioloY，现又通过改变基变量使总运价减少了IlY因为_I>c所以总运价减少

8、。参考文献1蕾答．睦性规捌．山东大学出版杜2运筹学．清华大学出版杜ResearchontheContradi