运筹学第三章运输问题演示

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

3.2运输问题的求解方法：表上作业法3.3几类特殊的运输问题3.4运输问题的应用

运输问题：根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。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 5调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地二、建立模型设xij——第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij

0,(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单位运价表产销平衡表一般模型表示

(ai=bj)三、模型的特点1.变量数：m

n个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij=——第i个分量——第m+j个分量0110………x11x12······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···························································································································································································关于运输模型的几个结论：(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n-1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路。初始基可行解新的基可行解最优否？STOPYN

3.2运输问题的求解方法：表上作业法单纯形法求解思路表上作业法步骤:

初始运输方案

最优性检验

改进运输方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。3产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量311310192874105634133656749单位运价表产销平衡表最小元素法例产地销地A1A2B1B215151020产量销量2851最小元素法：z=8×10+2×5+1×15=105Vogel法：z=10×5+15×2+5×1=85Vogel法产地销地A1A2A3B1B2B3B4749产量销量3656635213产地销地A1A2A3B1B2B3B4行两最小元素之差列两最小元素之差31131019287410501125130122-1301-2-1276---12Vogel法产销平衡表针对最小元素法和vogel法，需要说明的几点：(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)

若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；要求在完成合同的情况下，做出使全年生产费用最小的决策。第四天送洗：y451200202020x11x12······x1nx21x22······x2n,············,xm1xm2······xmn例:某餐馆承办宴会，每晚连续举行，共举行五次。生产量：A1——7吨，A2——4吨，A3——9吨1运输问题的典例和数学模型x14+x24+x34=6已知每天各自的生产量、销售量及调运时的单位运输费用情况。507030不限Ⅰ Ⅰ Ⅱ Ⅲ Ⅳ Ⅳ2411858-422267463656B1B2B3B4B1B2B3B4例产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量273118469431052030251015201050单位运价表产销平衡表102515100产地销地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)单位运价表产销平衡表闭回路法注:只要求的基变量是正确的，并且数目为m+n-1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。产地销地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)产地销地A1A2A3B1B1B3B4749产量销量36566343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。B1B2B3B43656x13+x23+x33=5B1B2B3B45151510为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价x11+x21+x31=336562销产(bj>ai)54645-507030不限515151001······001······0············01······0初始运输方案最优性检验改进运输方案2运输问题的求解方法：表上作业法注:对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法：任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n-1个数字格。5例：产地销地A1A2A3B1B1B3B4749产量销量3656635213(0)(2)(2)(9)(1)(12)产地销地A1A2A3B1B1B3B4749产量销量3656633124(1)产地销地A1A2A3B1B2B3B4产量销量632233665659(2)(1)(-1)(10)(12)例：6产地销地A1A2A3B1B2B3B4产量销量630336656592练习产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表最小元素法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表155151000Vogel法产地销地A1A2A3B1B2B3B4产地销地A1A2A3B1B2B3B4产量销量10120111279202141618515151015255单位运价表产销平衡表867792125-6119102-15-6-91013-105100注:表上作业法适用于下列情形：cij≥0；minz；产销平衡。表上作业法步骤3.3几类特殊的运输问题一、产销不平衡问题1

产

销2

销

产二、需求量不确定三、中转问题Minz=cij·xijni=1j=1m一、产销不平衡问题1

产

销(

ai>bj)Minz=cij·xij+

0xi,n+1ni=1j=1mi=1m产地销地A1A2┊AmB1 B2 ┈

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

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

bna1a2┊am

aibjMinz=cij·xijni=1j=1m2

销

产(

bj>ai)Minz=cij·xij+

0xm+1,jni=1j=1mj=1n产地销地A1A2┊AmB1 B2 ┈

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

bna1a2┊am

bj

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

Ⅱ

Ⅲ

Ⅳ产量最低需求1613221714131915192023―单位运价表5060503070010单位：万元/万吨设xij--第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求507030不限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生产地提供。最优方案：需求产地Ⅰ’I’’ⅡⅢⅣ’Ⅳ’’产量A5050B20103060C3020050D302050销量302070301050练习产地销地AⅠ

Ⅱ

Ⅲ最高发量467-78单位运价表6040400BC销量708050D最低发量8040不限5054645-三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。2运输问题的求解方法：表上作业法--12最大独立方程数：m+n-1311 3 1020202020第一天送洗：y12+z13+z14+z151000数字格处上添上对应的运价；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;最大独立方程数：m+n-136563113101928741055151510B1B2B3B4507030不限A1A2A3T1T2T3T4B1B2B3B4A1A2A3T1T2T3T4B1B2B3B401310-3-0214335-21-2331131019287410523115-4-232331711943210108501321011310221202846452718241-262411858-422267460142102142032130产销产量销量27242920202020202020202020202020202023262526产销平衡表3.4运输问题的应用

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

第i季度生产，用于第j季度交货的数量。obj.minz=

cijxiji=1j=1

44x11+x12+x13+x14

25

x22+x23+x2435

x33+x3430

x4410x11=10x12+x22