典型例题运筹学运输问题

1、典型例题运筹学运输问题3.1 运输问题的典例和数学模型一、典例： 某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A17吨， A2 4吨， A3 9吨销售量：B1 3吨，B2 6吨，B3 5吨，B4 6吨产地单位运价销地B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 1052021/112调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产

2、地销地2021/113二、建立模型设 xij第i产地到第j销地之间的调运量，那么有Min z = 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=62021/114一般模型表示： 设有个m产地、n个销地，其中第i个产地的产量为ai，第j个销地的销量为bj，且ai=bj。假设第i个产地到第j个销地每调运单位物资的运费为cij，那么使总费用最少的调运模型为

3、：Min z = cij xijni=1j=1m2021/115三、模型的特点1.变量数：mn个2.约束方程数：m+n个 最大独立方程数：m+n-13.系数列向量构造：Pij=0110第i个分量第m+j个分量2021/116x11 x12 x1n x21 x22 x2n , xm1 xm2 xmn1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1i=1i=2i=mj=1j=2j=n2021/117 3.2 运输问题的表上作业算法和程序求解表上

4、作业法步骤: 初始方案最优性检验改进方案一、初始方案确实定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。2021/118产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 6343133 6 5 67 4 93 6 5 67 4 9产量销量363521(1)(2)(1)(-1)(10)(12)z=c11-c13+c23-c21=1=11z=c12-c14+c24-c22=2=12(0)(2)(2)

5、(9)(1)(12)单位运价表产销平衡表2021/119产地销地A1 A2 A3B1 B2 B3 B47 4 9产量销量3 6 5 6635213产地销地A1 A2 A3B1 B2 B3 B4行两最小元素之差列两最小元素之差3 11 3 10 1 9 2 8 7 4 10 5 0 1 12 5 1 3 0 1 22 - 1 30 1 -2 - 1 27 6 - - 1 2Vogel法:产销平衡表2021/1110产地销地A1 A2 A3B1 B1 B3 B4 3 10 1 8 4 5 位势法:(3)(9)(7)(-2)(1)(-2)2.计算行位势和列位势；令u1=1，那么依cij=ui+vj

6、计算各ui和vj 3.计算空格处位势；ij=ui+vj行位势列位势 12-1-42894.计算空格处检验数：ij=cij- ij1.数字格处上添上对应的运价；销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表位势表:2021/1111产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 6635213(0)(2)(2)(9)(1)(12)检验数表2021/1112程序求解：(1) 使用LINDO程序求解: 同求解LP模型。(2) 使用EXCEL求解： 2021/11133.3 产销不平衡运输问题及其应用Min z

7、= cij xijni=1j=1m一、产销不平衡问题1产销Min z= cijxij+0 xi,n+1ni=1j=1mi=1m2021/1114产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 产销问题单位运价表销量产量b1b2bna1 a2 amaibj2021/1115Min z= cij xijni=1j=1m2销产Min z= cijxij +0 xm+1,jni=1j=1mj=1n2021/1116产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnAm+1销产问题单位运价表0 0 0销量

8、产量b1b2bna1 a2 ambjai2021/1117 例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。该厂的生产能力及生产每台柴油机的本钱如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位本钱(万元/台)二、应用模型2021/1118模型：设 xij第i季度生产，用于第j季度交货的数量。obj. min z= cij xiji=1j=1 4 4x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x

9、4410 x11 =10 x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20 xij 0 ,(i=1,4;j=1,4)供给：需求：2021/1119单位费用表： M 11.10 11.25 M M 11.00 M MM 单位：万元供给需求2021/1120例二： 某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用本钱。每条新餐巾需要1元的

10、费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？2021/1121建立模型：设 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第二天送洗：y2

11、3+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200 xj0，yij0，zij0，i=1,4；j=1,5Min z=xj+ij+ij2021/1122新 购 第一天第二天第三天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供给需求产量销 量5200 1000 700 800 1200MMM0.20.101000700800120015003700产销平衡表2021/1123例三： 有A、B、C三个化肥厂供给四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区

12、最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A1A2A3B1 B2 B3 B4产量销量16 13 22 17 14 13 19 15 19 20 23 单位运价表50 60 5030-50 70 0-30 10-单位：万元/万吨设 xij-第i工厂调至第j需求地区的化肥数量2021/1124A B C D 161613221717 14141319151519192023 M MM0M0M0供给需求产量销 量50 60 50 50 302070301050产销平衡表2021/1125三、

13、扩大的运输问题例：在前面的例题中，假设既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.转运量可定位总的产量之和；3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为Cij=0；4.实际产地产量为转运量与该产地实际产量之和，实际销地 销量为转运量与实际销量之和。2021/1126A1 A2 A3T1 T2 T3 T4B1 B2 B3 B4A1 A2 A3T1 T2 T3 T4B1 B2 B3 B40 1 3 1 0 - 3 - 02 1 4 3 3 5 - 2 1 - 2 33 11 3 10 1 9 2 8 7 4 10 52 3 1 1 5 - 4 - 2 3 2 33 1 7 11 9 4 3 2 10 10 8