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