《数学建模运输问题附源代码精.ppt》由会员分享，可在线阅读，更多相关《数学建模运输问题附源代码精.ppt（134页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模运输问题附源代码第1页，本讲稿共134页3-1 3-1 运输问题运输问题问题的提出问题的提出 从从m个发点个发点A1,A2,.Am向向n个收点个收点B1,B2.Bn发送某种货物。发送某种货物。Ai发点的发量为发点的发量为ai，Bj收点的收量为收点的收量为bj。由。由Ai 运往运往Bj 单位货物单位货物的运费为的运费为Cij，由由Ai 运往运往Bj 货物的运量为货物的运量为Xij。问如何调配，才能使运费最省？问如何调配，才能使运费最省？第2页，本讲稿共134页 当发点的发量总和为当发点的发量总和为 ai，收收点的收量总和为点的收量总和为 bj相等时，称此相等时，称此运输问题为平衡运输问题
2、。否则称运输问题为平衡运输问题。否则称此运输问题为非平衡运输问题。此运输问题为非平衡运输问题。若若没有特别说明，均假定运输问题为没有特别说明，均假定运输问题为平衡的运输问题。平衡的运输问题。第3页，本讲稿共134页销地产地1 2 m1 2 n销量产量a1a2am b1 b 2 b n c21 c22 c2ncm1 cm2 cmnc11 c12 c1n cij ij 为运价为运价第4页，本讲稿共134页销地产地1 2 m销量产量a1a2am x21 x22 x2nxm1 xm2 xmn x11 x12 x1n xij ij 为运量为运量b1 b 2 b n1 2 n第5页，本讲稿共134页运输问
3、题的数学模型：运输问题的数学模型：Min S=cijxij i ji j xij=ai (i=1,2.m)j xij =bj(j=1,2n)i xij 0(i=1,2.m;j=1,2n)第6页，本讲稿共134页运输问题数学模型系数阵为：运输问题数学模型系数阵为：第7页，本讲稿共134页且共有且共有 m+n 个约束方程。个约束方程。并成立：并成立：所以模型最多只有所以模型最多只有m+n-1个独立约束方程个独立约束方程,系数系数矩阵的秩矩阵的秩 m+n-1第8页，本讲稿共134页运输问题的图表形式运输问题的图表形式第9页，本讲稿共134页运输问题解的结构运输问题解的结构 由于由于 ai =bj成立
4、成立 i j其其m+n个约束方程并不是独立个约束方程并不是独立的。实际上只有的。实际上只有m+n-1个是独个是独立的。即约束方程系数矩阵的立的。即约束方程系数矩阵的秩为秩为m+n-1。第10页，本讲稿共134页3-2 3-2 运输问题的求解运输问题的求解确定初始方案确定初始方案1 1西北角法西北角法2 2例例1 1第11页，本讲稿共134页（1）从图的西北角开始，填入从图的西北角开始，填入a1与与b1较小的较小的值，值，b1=2，即从，即从A1运给运给B1（2吨）吨）B1已经满足，划去已经满足，划去b1列，并将列，并将a1=4-2=2第12页，本讲稿共134页（2）向）向a1，b1较大方向移动
5、一格（或向右，较大方向移动一格（或向右，或向下）此时向右移动一格（或向下）此时向右移动一格（A1，B2）B2需需要要4吨，而吨，而A1只有只有2吨，吨，A1已发完，划去已发完，划去A1行，行，并把并把b2改成（改成（4-2）=2。第13页，本讲稿共134页（3）继续进行）继续进行第14页，本讲稿共134页（4）继续进行）继续进行第15页，本讲稿共134页（5）继续进行）继续进行第16页，本讲稿共134页（6）继续进行）继续进行第17页，本讲稿共134页（7）得到初始方案：）得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，总运费，总运费=6*2+5*2+4*
6、2+7*3+5*1+8*3=80（元）（元）第18页，本讲稿共134页2 2 最小元素法最小元素法第19页，本讲稿共134页（1 1）从最小元素开始（）从最小元素开始（3 3）即）即A A1 1优先满足优先满足B B3 3 3 3个单位，个单位，B B3 3 已已经满足，划去经满足，划去B B3 3列列，第20页，本讲稿共134页（2 2）再从最小元素开始（）再从最小元素开始（4 4）即即A A1 1优先满足优先满足B B4 4 1 1个单位，个单位，A A1 1 已经满足，划去已经满足，划去A A1 1行行，第21页，本讲稿共134页（3 3）再从最小元素开始（）再从最小元素开始（4 4）即
7、）即A A2 2优先满足优先满足B B1 1 2 2个单位，个单位，B B1 1 已已经满足，划去经满足，划去B B1 1列列，第22页，本讲稿共134页（4 4）再从最小元素开始（）再从最小元素开始（4 4）即）即A A2 2优先满足优先满足B B2 2 4 4个单位，个单位，B B2 2 A A2 2已经已经满足，划去满足，划去B B2 2列列A A2 2 行行。第23页，本讲稿共134页（4 4）最后把）最后把A A3 3满足满足B B4 4 3 3个单位，个单位，得到初始方案。得到初始方案。第24页，本讲稿共134页（5 5）得到初始方案：）得到初始方案：X X1313=3=3，X X
8、1414=1=1，X X2121=2=2，X X2222=4=4，X X3232=0=0，X X3434=3=3总运费总运费=3*3+4*1+4*2+4*4+8*3=61=3*3+4*1+4*2+4*4+8*3=61（元）（元）第25页，本讲稿共134页3.3.差值法（伏格法）差值法（伏格法）每次从当前运价表上，计算各行每次从当前运价表上，计算各行各列中两个各列中两个 (最小与次小）运价之差最小与次小）运价之差值（行差值值（行差值hihi，列差值，列差值kjkj），优先取），优先取最大差值的行或列中最小的格来确定最大差值的行或列中最小的格来确定运输关系，直到求出初始方案。运输关系，直到求出初始
9、方案。第26页，本讲稿共134页第27页，本讲稿共134页第28页，本讲稿共134页第29页，本讲稿共134页第30页，本讲稿共134页第31页，本讲稿共134页第32页，本讲稿共134页第33页，本讲稿共134页第34页，本讲稿共134页第35页，本讲稿共134页差值法差值法初始方案如下：初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，费用，费用=3*3+4*1+4*2+4*1+5*3+6*3=58（元）（元）第36页，本讲稿共134页西北角法西北角法得到初始方案：得到初始方案：X11=2，X12=2，X22=2，X23=3，X24=1，X34=3，总运
10、费，总运费=6*2+5*2+4*2+7*3+5*1+8*3=80（元）（元）第37页，本讲稿共134页最小元素法最小元素法得到初始方案：得到初始方案：X X1313=3=3，X X1414=1=1，X X2121=2=2，X X2222=4=4，X X3434=3=3总运费总运费=3*3+4*1+4*2+4*4+8*3=61=3*3+4*1+4*2+4*4+8*3=61（元）（元）第38页，本讲稿共134页西北角法西北角法得到初始方案：得到初始方案：X1111=2，X1212=2，X2222=2，X2323=3，X2424=1，X3434=3，总运费，总运费=6*2+5*2+4*2+7*3+5
11、*1+8*3=80（元）（元）最小元素法最小元素法得到初始方案：得到初始方案：X1313=3，X1414=1，X2121=2，X2222=4，X3434=3，总运费总运费=3*3+4*1+4*2+4*4+8*3=61=3*3+4*1+4*2+4*4+8*3=61（元）（元）差值法差值法初始方案如下：初始方案如下：X1313=3，X1414=1，X2121=2，X2222=1，X2424=3，X3232=3，总运费，总运费=3*3+4*1+4*2+4*1+5*3+6*3=58（元）（元）第39页，本讲稿共134页例：分别用西北角法、最小元素和伏格尔法求产销平衡例：分别用西北角法、最小元素和伏格尔
12、法求产销平衡运输问题的初始基可行解运输问题的初始基可行解 第40页，本讲稿共134页解解（1）西北角法西北角法 Z=399第41页，本讲稿共134页（2）最小元素）最小元素 Z=240第42页，本讲稿共134页（3）伏格尔法）伏格尔法 Z=240第43页，本讲稿共134页求最优方案求最优方案1 1 闭回路闭回路 在初始调运方案表中，从任意在初始调运方案表中，从任意空格出发，沿着纵向或横向行进，空格出发，沿着纵向或横向行进，遇到适当填有数据的方格遇到适当填有数据的方格9090度转弯，度转弯，继续行进，总能回到原来空格。这个封继续行进，总能回到原来空格。这个封闭的曲线称为闭回路。闭的曲线称为闭回路
13、。可以证明：每个空格对应着唯可以证明：每个空格对应着唯一的闭回路。一的闭回路。第44页，本讲稿共134页 第45页，本讲稿共134页如下表：如下表：第46页，本讲稿共134页如下表：如下表：第47页，本讲稿共134页如下表：如下表：第48页，本讲稿共134页第49页，本讲稿共134页第50页，本讲稿共134页第51页，本讲稿共134页第52页，本讲稿共134页第53页，本讲稿共134页第54页，本讲稿共134页第55页，本讲稿共134页第56页，本讲稿共134页第57页，本讲稿共134页第58页，本讲稿共134页第59页，本讲稿共134页第60页，本讲稿共134页求检验数求检验数 要判断一个调
14、运方案是否已是最优，要判断一个调运方案是否已是最优，就要判断方案所对应的基础可行解是否最就要判断方案所对应的基础可行解是否最优。在单纯形法中，根据非基变量（空格）优。在单纯形法中，根据非基变量（空格）的检验数来判别的。若检验数中没有负值，的检验数来判别的。若检验数中没有负值，则已求得最优。则已求得最优。如何根据初始调运表求得检验数？如何根据初始调运表求得检验数？第61页，本讲稿共134页（1 1）闭回路法闭回路法 空格空格X Xij ij的检验数的检验数=（第奇数次拐（第奇数次拐角点运价之和减去第偶数次拐角点运价之和减去第偶数次拐角点运价之和）角点运价之和）第62页，本讲稿共134页空格空格X
15、21的检验数的检验数=4-6+5-4=-1B1B2B3B4产量A16 05 03 4 4A24 -1 4 07 05 0 6A37658 03销量 2 4 3 4第63页，本讲稿共134页空格空格X14的检验数的检验数=4-5+4-5=-2B1B2B3B4产量A16 05 03 4 4A24 -1 4 07 05 06A37658 03销量 2 4 3 4第64页，本讲稿共134页空格空格X31的检验数的检验数=7-6+5-4+5-8=-1B1B2B3B4产量A16 05 03 4 -24A24 -14 07 05 0 6A37658 03销量 2 4 3 4第65页，本讲稿共134页检验数都
16、为负值，原方案不是最优解检验数都为负值，原方案不是最优解B1B2B3B4产量A16 05 03 -54 -2 4A24 -14 07 05 0 6A37 -16 -15 -58 03销量销量 2 4 3 4第66页，本讲稿共134页（2 2）位势法位势法 设变量设变量u ui i和和v vj j(i=1,2,m;j=1,2,n)(i=1,2,m;j=1,2,n)是运是运输问题的输问题的m+nm+n个约束条件的对偶变量，个约束条件的对偶变量，B B是含有一是含有一个人工变量个人工变量x xa a的（的（m+n)(m n)m+n)(m n)初始基矩阵，初始基矩阵，c ca a=0.=0.称称u u
17、i i与与v vj j为相应的各行与各列的位势。为相应的各行与各列的位势。Y=C Y=CB BB B-=(u=(u1 1,u,um m,v,v1 1,v,vn n),p),pijij=e=ei i+e+em+jm+j,C CB BB B-P Pijij=u=ui i+v+vj j，=c=cijij-C-CB BB B-P Pijij=c=cijij-(u-(ui i+v+vj j)当当 为基变量检验数时，为基变量检验数时，u ui i+v+vj j=c cijij对于基变量对于基变量X Xijij有：有：u ui i+v+vj j=C=CijijM+n-1M+n-1个方程，个方程，m+nm+n
18、个未知数，可令个未知数，可令u u1 1=0.=0.第67页，本讲稿共134页（2 2）位势法位势法 对初始调运方案，定义一组新的变量对初始调运方案，定义一组新的变量（对偶）（对偶）u ui i和和v vj j(i=1,2,m;j=1,2,n)(i=1,2,m;j=1,2,n)对于基变量对于基变量X Xijij有：有：u ui i+v+vj j=C=Cijij称称u ui i与与v vj j为相应的各行与各列的位势。为相应的各行与各列的位势。对于非基变量对于非基变量X Xijij有：有：=c cijij-C-CB BB B-P Pijij=c=cijij-（u ui i+v+vj j）第68页
19、，本讲稿共134页例：例：u u1 1+v+v1 1=6 u=6 u1 1+v2=5 u=5 u2 2+v2 2=4 =4 u u2 2+v+v3 3=7 u=7 u2 2+v+v4=5 u=5 u3+v+v4 4=8=8有七个变量，但只有六个方程，有一个自由变量，一般有七个变量，但只有六个方程，有一个自由变量，一般有七个变量，但只有六个方程，有一个自由变量，一般有七个变量，但只有六个方程，有一个自由变量，一般令令令令u1 1=0B1B2B3B4uiA16 05 03 -54 -2 0A24 -14 07 05 0-1A37 -16 -15 -58 02vj 6 5 8 6第69页，本讲稿共1
20、34页调整方案调整方案从一个方案调整到最优方案的过程，从一个方案调整到最优方案的过程，就是单纯形法的过程。就是单纯形法的过程。选择检验数（一般取最小）为负值选择检验数（一般取最小）为负值的空格所对应的变量为进基变量，在进的空格所对应的变量为进基变量，在进基变量的回路中，比较含（基变量的回路中，比较含（-1）拐角点）拐角点的运量，选择一个具有最小运量的基变的运量，选择一个具有最小运量的基变量作为出基变量，量作为出基变量，并调整运量并调整运量=min(含含（-1）的运量）的运量)第70页，本讲稿共134页选择（选择（A1，B3）（检验数最大）调整，最）（检验数最大）调整，最小运量小运量=min(2
21、,3)=2B1B2B3B4产量A16 25 2（-1）3 （+1）4 4A24 4 2（+1）7 3（-1）5 1 6A37658 33销量 2 4 3 4第71页，本讲稿共134页B1B2B3B4产量A16 25 3 24 4A24 4 47 15 1 6A37658 33销量 2 4 3 4第72页，本讲稿共134页 最小运量最小运量=min(2,3)=2,奇数点减去奇数点减去2，偶数点加，偶数点加上上2，得到新的方案。总运费，得到新的方案。总运费=6*2+3*2+4*4+7*1+5*1+8*3=70（元）原方案运费为（元）原方案运费为80（元）（元）B1B2B3B4产量A16 25 3
22、24 4A24 4 47 15 1 6A37658 33销量 2 4 3 4第73页，本讲稿共134页继续求检验数。继续求检验数。B1B2B3B4uiA16 05 5 3 04 3 0A24 -64 07 05 0 4A37 -66 -15 -58 07vj 6 0 3 1第74页，本讲稿共134页继续调整运量。继续调整运量。B1B2B3B4产量A16 2（-1）5 3 2（+1）4 4A24 （+1）4 47 1（-1）5 1 6A37658 33销量 2 4 3 4第75页，本讲稿共134页继续调整运量。最小运量继续调整运量。最小运量=1总运费总运费=6*1+3*3+4*1+4*4+5*1
23、+8*3=64（元）（元）B1B2B3B4产量A16 15 3 34 4A24 1 4 47 5 1 6A37658 33销量 2 4 3 4第76页，本讲稿共134页继续计算检验数。继续计算检验数。B1B2B3B4uiA16 05 -1 3 04 -3 0A24 04 07 6 5 0-2A37 06 -15 18 01vj 6 6 3 7 第77页，本讲稿共134页继续调整运量。最小运量继续调整运量。最小运量=1B1B2B3B4产量A16 15 3 34 4A24 1 4 47 5 1 6A37658 33销量 2 4 3 4第78页，本讲稿共134页得到新的调运方案，总运费得到新的调运方
24、案，总运费=3*3+4*1+4*2+4*4+8*3=61（元）（元）B1B2B3B4产量A16 5 3 34 1 4A24 2 4 47 5 0 6A37658 33销量 2 4 3 4第79页，本讲稿共134页继续计算检验数继续计算检验数B1B2B3B4uiA16 65 5 3 04 0 0A24 04 07 3 5 0 1A37 06 25 -28 04vj 0 0 3 4 第80页，本讲稿共134页B1B2B3B4产量A16 5 3 34 1 4A24 2 4 47 5 0 6A37658 33销量 2 4 3 4继续调整运量。最小运量继续调整运量。最小运量=3第81页，本讲稿共134页
25、B1B2B3B4产量A16 5 3 04 44A24 2 4 47 5 0 6A3765 38 3销量 2 4 3 4总运费总运费=4*4+4*2+4*4+5*3=55（元）（元）第82页，本讲稿共134页计算检验数：空格的检验数全为非负，计算检验数：空格的检验数全为非负，此时是最优解。此时是最优解。最优调运方案：最优调运方案：X21=2，X22=4，X14=4，X33=3。最小运费。最小运费55（元）。（元）。第83页，本讲稿共134页例例2：产销平衡表为：产销平衡表为：销地销地产地产地B1B2B3B4产量产量A13 11 3 10 7A21 9 2 8 4A374105 9销量销量 3 6
26、 5 6第84页，本讲稿共134页 销地产地B1B2B3B4产量A13 11 3 4 10 3 7A21 39 2 18 4A374 6105 39销量 3 6 5 6（1）用最小元素法求初始基可行解）用最小元素法求初始基可行解表表（1）第85页，本讲稿共134页 销地产地B1B2B3B4uiA13 111 23 0 10 0 0A21 09 12 08 -1-1A37 104 010 125 0-5vj 2 9 3 10（2）用位势法求检验数）用位势法求检验数表表（2）第86页，本讲稿共134页（2）检验数）检验数 =-10，用闭回路调节，用闭回路调节 销地产地B1B2B3B4产量A13 1
27、1 3 4+1 10 3-1 7A21 39 2 1-18 （+1）4A374 6105 39销量 3 6 5 6表（表（3）第87页，本讲稿共134页 销地销地产地产地B1B2B3B4产量产量A13 11 3 5 10 2 7A21 39 2 8 1 4A374 6105 39销量销量 3 6 5 6（3）用闭回路调节得）用闭回路调节得表（表（4）第88页，本讲稿共134页（2）用位势法再求表（）用位势法再求表（4）的检验数）的检验数 销地销地产地产地B1B2B3B4uiA13 011 23 0 10 0 0A21 09 22 18 0-2A37 94 010 125 0-5vj 3 9 3
28、 10表（表（5）非基变量）非基变量 ，有无穷多最优解，有无穷多最优解第89页，本讲稿共134页表（表（5）中空格的检验数全为非负，此时是最优中空格的检验数全为非负，此时是最优中空格的检验数全为非负，此时是最优中空格的检验数全为非负，此时是最优解。解。解。解。最优调运方案为最优调运方案为最优调运方案为最优调运方案为表（表（表（表（4），），最小费用为最小费用为最小费用为最小费用为8585元。元。元。元。销地销地产地产地B1B2B3B4产量产量A13 11 3 5 10 2 7A21 39 2 8 1 4A374 6105 39销量销量 3 6 5 6第90页，本讲稿共134页 销地销地产地产地
29、B1B2B3B4产量产量A13（+1）11 3 5 10（-1）2 7A21（-1）39 2 8（+1）1 4A374 6105 39销量销量 3 6 5 6第91页，本讲稿共134页 销地销地产地产地B1B2B3B4产量产量A13 211 3 5 10 7A21 19 2 8 3 4A374 6105 39销量销量 3 6 5 6为另一最优解为另一最优解第92页，本讲稿共134页例例3 某石油公司设有四个炼油厂，它某石油公司设有四个炼油厂，它们生产普通汽油，并为七个销售区服们生产普通汽油，并为七个销售区服务，生产和需求情况如下：务，生产和需求情况如下：第93页，本讲稿共134页从炼油厂运往第
30、从炼油厂运往第j个销售区每公升汽个销售区每公升汽油平均运费（单位：角油平均运费（单位：角/公升），应公升），应如何调运，使运费最省如何调运，使运费最省。销地销地产地产地1234567产量产量1652636335237586922534865585154744747440销量销量25201025101510第94页，本讲稿共134页解：平衡问题，用最小元素法求初解：平衡问题，用最小元素法求初始方案为：始方案为：销地销地产地产地1234567产量产量1652 10 6 3 633523 758692 2534 86558515474 4747440销量销量25201025101510第95页，本讲
31、稿共134页 销地销地产地产地1234567产量产量1652 10 6 3 633523 758692 102534 86558515474 4747440销量销量25201025101510第96页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 3 10633523 758692 102534 86558515474 4747440销量销量25201025101510第97页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 3 10633523 15758692 102534 86558515474 4747440销量销量252010
32、25101510第98页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 3 10633523 15758692 102534 1086558515474 4747440销量销量25201025101510第99页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 3 10633523 15758692 102534 1086558515474 204747440销量销量25201025101510第100页，本讲稿共134页 销地销地销地销地产地产地产地产地1234567产量产量产量产量1652 1010 6 3 1010633523 1
33、515758692 10102534 1010865 5 558515474 20204747440销量销量销量销量25201025101510第101页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 153 10633523 15758692 102534 10865 558515474 204747440销量销量25201025101510第102页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 153 10633523 15758692 102534 10865 558515474 2047 547440销量销量25201025
34、101510第103页，本讲稿共134页 销地销地产地产地1234567产量产量1652 10 6 153 10633523 15758692 102534 10865 558515474 2047 547 15440销量销量25201025101510第104页，本讲稿共134页 销地产地1234567产量1 10 15 10352 15 10253 10 5154 20 5 1540销量25201025101510用最小元素法得初始基可行解为：用最小元素法得初始基可行解为：表（表（1）第105页，本讲稿共134页用位势法计算检验数。用位势法计算检验数。销地销地产地产地1234567 ui1
35、652 0 6 03 063023 0758692 0-234 0865 0585-1474 047 047 041vj5326364第106页，本讲稿共134页 销地销地产地产地1234567 ui16 15 22 0 6 03 06 03 -1023 07 65 58 46 59 52 0-234 08 66 55 05 38 35 2-147 14 04 17 04 07 04 -11vj5326364检验数为：检验数为：检验数检验数 0，故表（，故表（1）不是最优解）不是最优解第107页，本讲稿共134页闭回路调节闭回路调节 销地产地1234567产量1 10 15-1 10 +135
36、2 15+1 10-125310-1 5+1154 20 5 1540销量25201025101510第108页，本讲稿共134页 销地产地1234567产量1 10 5 1010 352 25 0253 15154 20 5 1540销量25201025101510闭回路调节为：闭回路调节为：表（表（2）第109页，本讲稿共134页再用位势法计算表（再用位势法计算表（2）检验数。）检验数。销地产地1234567 ui16 25 22 0 6 03 06 03 0023 07 45 48 36 49 42 0-134 18 66 55 05 38 35 3-147 24 04 17 04 07
37、 04 01vj4326363检验数检验数检验数检验数 0 0，故表（，故表（2）是最优解，）是最优解，）是最优解，）是最优解，总运费总运费=480000（元）（元）第110页，本讲稿共134页最优方案如下，最优方案如下，最小运费最小运费=480000元元第111页，本讲稿共134页有非基变量的检验数有非基变量的检验数=0，有无穷多，有无穷多组解，另外一个解如下：组解，另外一个解如下：第112页，本讲稿共134页 产销不平衡运输问题产销不平衡运输问题当当当当 时，时，时，时，假想一个销地假想一个销地假想一个销地假想一个销地B Bn+1n+1（仓库），销量为（仓库），销量为（仓库），销量为（仓库
38、），销量为 运费运费运费运费C Ci n+1i n+1=0,i=1,2,m=0,i=1,2,m当当当当 时时时时,假想一个产地假想一个产地假想一个产地假想一个产地A An+1n+1，产量为，产量为，产量为，产量为 运费运费运费运费C C n+1 j n+1 j=0,j=1,2,n=0,j=1,2,n第113页，本讲稿共134页销地产地1 2 m销量产量a1a2am c21 c22 c2ncm1 cm2 cmnc11 c12 c1n 1 2 n n+1000b1 b 2 b n b n+1 产大于销产大于销第114页，本讲稿共134页产小于销产小于销产小于销产小于销销地产地1 2 m销量产量a1
39、a2am c21 c22 c2ncm1 cm2 cmnc11 c12 c1n 1 2 nb1 b 2 b n m+10 0 0am+1第115页，本讲稿共134页 销地销地销地销地产地产地产地产地B1B2B3B4产量产量A12 11 3 4 7A210 3 5 9 5A37812 7销量销量 2 3 46 19191515例例4：运输问题产销表运输问题产销表为：为：第116页，本讲稿共134页例例4：产销平衡表为：产销平衡表为：销地销地产地产地B1B2B3B4 B5产量产量A12 11 3 4 0 7A210 3 5 9 0 5A37812 0 7销量销量 2 3 46 4第117页，本讲稿共
40、134页（1）用）用vogel求初始基可行解求初始基可行解 销地销地产地产地B1B2B3B4 B5产量产量A12 211 3 4 0 3 27A210 3 3 5 9 0 25A3781 4 2 0 3 7销量销量 2 3 46 4第118页，本讲稿共134页 销地销地产地产地B1B2B3B4 B5产量产量A1 2 3 27A2 3 25A3 4 3 7销量销量 2 3 46 4初始基可行解为初始基可行解为第119页，本讲稿共134页 销地销地产地产地B1B2B3B4 B5uiA1 2 011 83 04 0 0 00A210 83 05 29 0 5 00A37 78 71 02 0 0 2
41、-2vj 2 3 34 0（2）用位势法求检验数，）用位势法求检验数，第120页，本讲稿共134页检验数均为非负，故初始基可行解即为最检验数均为非负，故初始基可行解即为最优解，如下：优解，如下：销地销地产地产地B1B2B3B4 B5产量产量A1 2 3 27A2 3 25A3 4 3 7销量销量 2 3 46 4第121页，本讲稿共134页 需求地需求地化肥厂化肥厂1234产量产量(万吨）万吨）11613221750214131915603192023M50最低需求量（万吨最低需求量（万吨)3070010最高需求量（万吨最高需求量（万吨)507030不限不限表1-36例例5第122页，本讲稿共
42、134页 需求地需求地化肥厂化肥厂1234产量产量(万吨）万吨）11613221750214131915603192023M50最低需求量（万吨最低需求量（万吨)3070010最高需求量（万吨最高需求量（万吨)50703060例：因总产量为例：因总产量为160，故，故4需求地最多分配需求地最多分配60吨。吨。第123页，本讲稿共134页 需求地需求地1234产量产量 化肥厂化肥厂IIIIII(万吨）万吨）116161322171750214141319151560319192023MM504(虚虚)M0M0M050需求量（万吨需求量（万吨)302070301050不能由假想地供给，其运价为不能
43、由假想地供给，其运价为M，否则为，否则为0。第124页，本讲稿共134页 需求需求地地1234化肥厂化肥厂III15022040330204(虚虚)3020第125页，本讲稿共134页例例6：某厂按合同规定须于当年每个季度末提供：某厂按合同规定须于当年每个季度末提供10，15，25，20台同一规台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。又如果生产出来的柴油机当季不交货，每台每积压一个季度需下表。又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用储存、维护等费用0.15万元，要求在完成
44、合同的情况下，做出使该厂万元，要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。全年生产（包括储存、维护）费用最小的决策。季度季度 生产能力（台）生产能力（台）单位成本（万元）单位成本（万元）25 35 30 10 10.8 11.1 11.0 11.3第126页，本讲稿共134页解：设解：设 为为 季度生产季度生产 季度交货的柴油机数。季度交货的柴油机数。各季度的销量必须满足：各季度的销量必须满足：总销量为总销量为70各季度的产量：各季度的产量：总产量为总产量为100第127页，本讲稿共134页 为单位产品该季度单位成本加上储存、维护等费用，具体数值如下表：季度交货
45、 季度生产 10.8 10.95 11.10 11.10 11.25 11.00 11.25 11.40 11.15 11.30看成是产大于销的运输问题，加上假想地D，当 时，令 M，产销平衡的单位运价表如下：第128页，本讲稿共134页 销地产地 D产量 10.8MMM10.9511.10MM11.1011.2511.00M11.2511.4011.1511.30000025353010销量1015252030用表上作业法得多个最优方案，其中之一为下表：第129页，本讲稿共134页 销售季度生产季度 D产量 10 15 0 5 20 10 10 3025353010销量1015252030第
46、130页，本讲稿共134页运输问题的灵敏度分析运输问题的灵敏度分析例：已知运输问题的运价表、产销平衡表如下例：已知运输问题的运价表、产销平衡表如下 销地销地产地产地B1B2B3B4B5B6产量A12133355042244440A335424160A442212231销量销量305020403011A2第131页，本讲稿共134页求求（1）最优方案；）最优方案；（2）分别在什么范围内变化，上分别在什么范围内变化，上述最优方案不变。述最优方案不变。解解（1）最优方案为：）最优方案为：销地销地产地产地B1B2B3B4B5B6产量A1203050A2202040A310391160A413031销量销量305020403011第132页，本讲稿共134页解解（2）检验数为：）检验数为：销地销地产地产地B1B2B3B4B5B6行差A1 20 10 3 3 3 50A2 4 2 20 40 4 41A3 30 5 4 20 4 101A4 4 2 2 10 2 200列差列差211120第133页，本讲稿共134页检验数：检验数：第134页，本讲稿共134页