运筹学第三章运输问题培训课程课件

运筹学第三章运输问题运筹学第三章运输问题1运筹学第三章运输问题ppt课件运筹学第三章运输问题ppt课件23.1运输问题的典例和数学模型

3.2运输问题的求解方法：表上作业法3.3几类特殊的运输问题3.4运输问题的应用3.1运输问题的典例和数学模型3.2运输问题的运输问题根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。运输问题根据已有的交通网，如何制定运输方案，使得3.1运输问题的典例和数学模型一、典例某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A1——7吨，A2——4吨，A3——9吨销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨产地单位运价销地B1B2B3B4A1A2A3

311 3 10

1 9 2 8

7 4 10 53.1运输问题的典例和数学模型一、典例生产量：A1——调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5二、建立模型设xij——第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,┄,3；j=1,2,┄,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6二、建立模型设xij——第i产地到第j销地之间的调运单位运价表产销平衡表单位运价表产销平衡表一般模型表示

(ai=bj)一般模型表示

(ai=bj)三、模型的特点1.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij=——第i个分量——第m+j个分量0110………三、模型的特点1.变量数：mn个Pij=——第i个分量0…注:表上作业法适用于下列情形已知每天各自的生产量、销售量及调运时的单位运输费用情况。x33+x34302-13为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价A1A2A3214335-21-235151510已知每天各自的生产量、销售量及调运时的单位运输费用情况。2运输问题的求解方法：表上作业法x33+x3430214335-21-23注：位势法求检验数的依据是对偶理论。0011.(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。00······011······1············00······0x11x12······x1nx21x22······x2n,············,xm1xm2······xmn11······100······0············00······000······011······1············00······000······000······0············11······110······010······0············10······001······001······0············01······000······100······1············00······1i=1i=2i=mj=1j=2j=n···························································································································································································注:表上作业法适用于下列情形x11x12······x关于运输模型的几个结论(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。关于运输模型的几个结论初始基可行解新的基可行解最优否？STOPYN

3.2运输问题的求解方法：表上作业法单纯形法求解思路初始基可行解新的基可行解最优否？STOPYN3.2表上作业法步骤:

初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。表上作业法步骤:3产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量311310192874105634133656749单位运价表产销平衡表最小元素法3产地销地A1A2A3B1B2B3B4产地销例产地销地A1A2B1B215151020产量销量2851最小元素法：z=8×10+2×5+1×15=105Vogel法：z=10×5+15×2+5×1=85Vogel法例产地销地A1A2B1B215151020产B1B2B3B42-13(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n1个数字格。x14+x24+x34+x44=2025135151510第二天送洗：y23+z24+z25700为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价T1T2T3T4B1B2B3B4第二天：x2+y12=700(1)任何运输问题都有基可行解，且有最优解；0132101131022120(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。运筹学第三章运输问题ppt课件214335-21-23第一天送洗：y12+z13+z14+z1510002326252623262526产地销地A1A2A3B1B2B3B4749产量销量3656635213产地销地A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法产销平衡表B1B2B3B4产地销地A1A2A3B1针对最小元素法和vogel法，需要说明的几点(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)

若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；针对最小元素法和vogel法，需要说明的几点(1)任何运输例产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量273118469431052030251015201050单位运价表产销平衡表102515100例产地销地A1A2A3B1B2B3B4产地销产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量31131019287410563431336567493656749产量销量363521(1)(2)(1)(-1)(10)(12)△z=c11-c13+c23-c21=1=11△z=c12-c14+c34-c32=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表闭回路法产地销地A1A2A3B1B2B3B4产地销地注:只要求的基变量是正确的，并且数目为m+n1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。注:只要求的基变量是正确的，并且数目为m+n1个，那么每个产地销地A1A2A3B1B1B3B4位势法4132.计算行位势和列位势；令v1=1，则依cij=ui+vj计算各ui和vj3.计算空格处位势；ij=ui+vj行位势ui列位势vj

110-42894.计算空格处检验数：ij=cij-ij1.数字格处上添上对应的运价；销地A1A2A3B1B1B3B4311310192874105产地单位运价表位势表:2105(2)(9)(8)(9)(-3)(-2)产地销地A1A2A3B1B1B3B4位势法4产地销地A1A2A3B1B1B3B4749产量销量36566343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。产地销地A1A2A3B1B1B3B474注:对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n1个数字格。注:1613221714131915192023―x11+x21+x31=351515103665311310192874105T1T2T3T43几类特殊的运输问题x14+x24+x34=63113101928741050011.01······001······0············01······03几类特殊的运输问题不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；214335-21-23507030不限x11+x12+x13+x14=78677(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。A1A2A3注:表上作业法适用于下列情形００┆０5例产地销地A1A2A3B1B1B3B4749产量销量3656635213(0)(2)(2)(9)(1)(12)产地销地A1A2A3B1B1B3B4749产量销量36566331216132217141319154(1)产地销地A1A2A3B1B2B3B4产量销量632233665659(2)(1)(-1)(10)(12)例6产地销地A1A2A3B1B2B3B4产量销量6303366565924(1)产地销地A1A2A3B1B2B3B4练习产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表练习产地销地A1A2A3B1B2B3B4产地最小元素法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表155151000最小元素法产地销地A1A2A3B1B2B3BVogel法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表867792125-6119102-15-6-91013-105100Vogel法产地销地A1A2A3B1B2B3注:表上作业法适用于下列情形cij≥0；minz；产销平衡。表上作业法步骤注:表上作业法适用于下列情形表上作业法步骤3.3几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题3.3几类特殊的运输问题一、产销不平衡问题1产销2Minz=cij·xijni=1j=1m一、产销不平衡问题1产销(ai>bj)Minz=cij·xij+0xi,n+1ni=1j=1mi=1mMinz=cij·xijni=1j=1m一、产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０产＞销问题单位运价表销量产量b1 b2 ┈

bna1a2┊amaibj产地销地A1A2┊AmB1 B2 ┈ BnC11 CMinz=cij·xijni=1j=1m2销产(bj>ai)Minz=cij·xij+0xm+1,jni=1j=1mj=1nMinz=cij·xijni=1j=1m2销产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+1销＞产问题单位运价表0 0 ┈ 0销量产量b1 b2 ┈

bna1a2┊ambjai产地销地A1A2┊AmB1 B2 ┈ BnC11 C例：有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地AⅠ

Ⅱ

Ⅲ

Ⅳ产量最低需求1613221714131915192023―单位运价表5060503070010单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求507030不限例：有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化ABCⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 1714 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供应需求产量销量50605030 20 70 30 10 50产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。ABCⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ16 最优方案需求产地Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20103060C3020050D302050销量302070301050最优方案需求Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20练习产地销地AⅠ

Ⅱ

Ⅲ最高发量467-78单位运价表6040400BC销量708050D最低发量8040不限5054645-练习产地销地AⅠⅡⅢ最高发量467三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量27242920202020202020202020202020202023262526产销平衡表A1A2A3T1T2T3T4B3.4运输问题的应用3.4运输问题的应用

例：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ25353010例：某工厂按合同规定必须于当年的每个季度末分别提供10、1模型：设xij第i季度生产，用于第j季度交货的数量。obj.minz=cijxiji=1j=1

44x11+x12+x13+x1425

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22

=15x13+x23+x33

=25x14+x24+x34+x44=20xij0,(i=1,····,4;j=1,····,4)供应：ⅠⅡⅢⅣⅠⅡⅢⅣ需求：模型：设xij第i季度生产，用于第j季度交货的数量。obMinz=cij·xijM 0 M 0 M 0C11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ Cmn3几类特殊的运输问题x14+x24+x34=62326252601310-3-0B1B2B3B4T1T2T3T4注:表上作业法适用于下列情形11······100······0············00······0B1 B2 ┈ Bnx14+x24+x34=6B1B2B3B4x13+x23+x33=5００┆０2运输问题的求解方法：表上作业法B1B2B3B4T1T2T3T4x11+x21+x31=3单位费用表ⅠⅡⅢⅣⅠ Ⅱ Ⅲ Ⅳ10.8 10.95 11.10 11.25

M

11.1011.25

11.40

M

M 11.00

11.15

M M M

11.30单位：万元供应需求Minz=cij·xij单位费用表ⅠⅡⅢⅣⅠ 例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特第四天送洗：y45120020202020宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。B1B2B3B4M M M 11.0011.zij—第i天送第j天使用慢洗餐巾的数量；27311846943105最小元素法：z=8×10+2×5+1×15=105M M M 11.B1B1B3B4B1B1B3B4302510152运输问题的求解方法：表上作业法销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨x4410x14+x24+x34=6232625262846452718241-26Minz=cij·xij+0xm+1,j新购餐巾：x1+x2+x3+x4+x55200Minz=cij·xij366523115-4-2323x44103113101928741051运输问题的典例和数学模型B1B2B3B4第一天送洗：y12+z13+z14+z151000第四天送洗：y4512002运输问题的求解方法：表上作业法311310192874105zij—第i天送第j天使用慢洗餐巾的数量；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。B1 B2 ┈ Bnb1 b2 ┈ bn2元，慢洗需要两天时间，每条洗涤费用0.Ⅰ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ最小元素法：z=8×10+2×5+1×15=105关于运输模型的几个结论建立模型设xj—第j天使用新毛巾的数量；yij—第i天送第j天使用快洗 餐巾的数量；zij—第i天送第j天使用慢洗餐巾的数量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14+z24+y34=1200第五天：x5+z15+z25+z35+y45=1500需求约束供应约束新购餐巾：x1+x2+x3+x4+x55200第一天送洗：y12+z13+z14+z151000第二天送洗：y23+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200xj0，yij0，zij0，（i=1,┈,4；j=1,┈,5）Minz=∑xj+∑∑0.2yij+∑∑0.1zij第四天送洗：y451200Minz=cij·运筹学第三章运输问题运筹学第三章运输问题48运筹学第三章运输问题ppt课件运筹学第三章运输问题ppt课件493.1运输问题的典例和数学模型

3.2运输问题的求解方法：表上作业法3.3几类特殊的运输问题3.4运输问题的应用3.1运输问题的典例和数学模型3.2运输问题的运输问题根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。运输问题根据已有的交通网，如何制定运输方案，使得3.1运输问题的典例和数学模型一、典例某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A1——7吨，A2——4吨，A3——9吨销售量：B1——3吨，B2——6吨，B3——5吨，B4——6吨产地单位运价销地B1B2B3B4A1A2A3

311 3 10

1 9 2 8

7 4 10 53.1运输问题的典例和数学模型一、典例生产量：A1——调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5二、建立模型设xij——第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,┄,3；j=1,2,┄,4)产量限制销量限制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6二、建立模型设xij——第i产地到第j销地之间的调运单位运价表产销平衡表单位运价表产销平衡表一般模型表示

(ai=bj)一般模型表示

(ai=bj)三、模型的特点1.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij=——第i个分量——第m+j个分量0110………三、模型的特点1.变量数：mn个Pij=——第i个分量0…注:表上作业法适用于下列情形已知每天各自的生产量、销售量及调运时的单位运输费用情况。x33+x34302-13为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价A1A2A3214335-21-235151510已知每天各自的生产量、销售量及调运时的单位运输费用情况。2运输问题的求解方法：表上作业法x33+x3430214335-21-23注：位势法求检验数的依据是对偶理论。0011.(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。00······011······1············00······0x11x12······x1nx21x22······x2n,············,xm1xm2······xmn11······100······0············00······000······011······1············00······000······000······0············11······110······010······0············10······001······001······0············01······000······100······1············00······1i=1i=2i=mj=1j=2j=n···························································································································································································注:表上作业法适用于下列情形x11x12······x关于运输模型的几个结论(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。关于运输模型的几个结论初始基可行解新的基可行解最优否？STOPYN

3.2运输问题的求解方法：表上作业法单纯形法求解思路初始基可行解新的基可行解最优否？STOPYN3.2表上作业法步骤:

初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。表上作业法步骤:3产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量311310192874105634133656749单位运价表产销平衡表最小元素法3产地销地A1A2A3B1B2B3B4产地销例产地销地A1A2B1B215151020产量销量2851最小元素法：z=8×10+2×5+1×15=105Vogel法：z=10×5+15×2+5×1=85Vogel法例产地销地A1A2B1B215151020产B1B2B3B42-13(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n1个数字格。x14+x24+x34+x44=2025135151510第二天送洗：y23+z24+z25700为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价T1T2T3T4B1B2B3B4第二天：x2+y12=700(1)任何运输问题都有基可行解，且有最优解；0132101131022120(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。运筹学第三章运输问题ppt课件214335-21-23第一天送洗：y12+z13+z14+z1510002326252623262526产地销地A1A2A3B1B2B3B4749产量销量3656635213产地销地A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法产销平衡表B1B2B3B4产地销地A1A2A3B1针对最小元素法和vogel法，需要说明的几点(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)

若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；针对最小元素法和vogel法，需要说明的几点(1)任何运输例产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量273118469431052030251015201050单位运价表产销平衡表102515100例产地销地A1A2A3B1B2B3B4产地销产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量31131019287410563431336567493656749产量销量363521(1)(2)(1)(-1)(10)(12)△z=c11-c13+c23-c21=1=11△z=c12-c14+c34-c32=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表闭回路法产地销地A1A2A3B1B2B3B4产地销地注:只要求的基变量是正确的，并且数目为m+n1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。注:只要求的基变量是正确的，并且数目为m+n1个，那么每个产地销地A1A2A3B1B1B3B4位势法4132.计算行位势和列位势；令v1=1，则依cij=ui+vj计算各ui和vj3.计算空格处位势；ij=ui+vj行位势ui列位势vj

110-42894.计算空格处检验数：ij=cij-ij1.数字格处上添上对应的运价；销地A1A2A3B1B1B3B4311310192874105产地单位运价表位势表:2105(2)(9)(8)(9)(-3)(-2)产地销地A1A2A3B1B1B3B4位势法4产地销地A1A2A3B1B1B3B4749产量销量36566343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。产地销地A1A2A3B1B1B3B474注:对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n1个数字格。注:1613221714131915192023―x11+x21+x31=351515103665311310192874105T1T2T3T43几类特殊的运输问题x14+x24+x34=63113101928741050011.01······001······0············01······03几类特殊的运输问题不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；214335-21-23507030不限x11+x12+x13+x14=78677(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。A1A2A3注:表上作业法适用于下列情形００┆０5例产地销地A1A2A3B1B1B3B4749产量销量3656635213(0)(2)(2)(9)(1)(12)产地销地A1A2A3B1B1B3B4749产量销量36566331216132217141319154(1)产地销地A1A2A3B1B2B3B4产量销量632233665659(2)(1)(-1)(10)(12)例6产地销地A1A2A3B1B2B3B4产量销量6303366565924(1)产地销地A1A2A3B1B2B3B4练习产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表练习产地销地A1A2A3B1B2B3B4产地最小元素法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表155151000最小元素法产地销地A1A2A3B1B2B3BVogel法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表867792125-6119102-15-6-91013-105100Vogel法产地销地A1A2A3B1B2B3注:表上作业法适用于下列情形cij≥0；minz；产销平衡。表上作业法步骤注:表上作业法适用于下列情形表上作业法步骤3.3几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题3.3几类特殊的运输问题一、产销不平衡问题1产销2Minz=cij·xijni=1j=1m一、产销不平衡问题1产销(ai>bj)Minz=cij·xij+0xi,n+1ni=1j=1mi=1mMinz=cij·xijni=1j=1m一、产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnBn+1０

０┆０产＞销问题单位运价表销量产量b1 b2 ┈

bna1a2┊amaibj产地销地A1A2┊AmB1 B2 ┈ BnC11 CMinz=cij·xijni=1j=1m2销产(bj>ai)Minz=cij·xij+0xm+1,jni=1j=1mj=1nMinz=cij·xijni=1j=1m2销产地销地A1A2┊AmB1 B2 ┈

BnC11 C12 ┈ C1nC21 C22 ┈ C2n┆ ┊ ┈ ┊Cm1 Cm2 ┈ CmnAm+1销＞产问题单位运价表0 0 ┈ 0销量产量b1 b2 ┈

bna1a2┊ambjai产地销地A1A2┊AmB1 B2 ┈ BnC11 C例：有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化肥，三个工厂每年各自的产量为A--50万吨，B--60万吨，C--50万吨。四个地区的需求量分别是Ⅰ地区最高50万吨，最低30万吨，Ⅱ地区为70万吨，Ⅲ地区为30万吨以下，Ⅳ地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地AⅠ

Ⅱ

Ⅲ

Ⅳ产量最低需求1613221714131915192023―单位运价表5060503070010单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求507030不限例：有A、B、C三个化肥厂供应四个地区Ⅰ、Ⅱ、Ⅲ、Ⅳ的农用化ABCⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ

16 16 13 22 17 1714 14 13 19 15 1519 19 20 23 M MM 0 M 0 M 0供应需求产量销量50605030 20 70 30 10 50产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。ABCⅠ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ16 最优方案需求产地Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20103060C3020050D302050销量302070301050最优方案需求Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20练习产地销地AⅠ

Ⅱ

Ⅲ最高发量467-78单位运价表6040400BC销量708050D最低发量8040不限5054645-练习产地销地AⅠⅡⅢ最高发量467三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量27242920202020202020202020202020202023262526产销平衡表A1A2A3T1T2T3T4B3.4运输问题的应用3.4运输问题的应用

例：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)ⅠⅡⅢⅣ25353010例：某工厂按合同规定必须于当年的每个季度末分别提供10、1模型：设xij第i季度生产，用于第j季度交货的数量。obj.minz=cijxiji=1j=1