运筹学表上作业法PPT学习教案

1、会计学11.运输问题模型及其求解思路运输问题模型及其求解思路2.确定初始基本可行解确定初始基本可行解3.最优性检验最优性检验4.方案调整方案调整第1页/共43页1总运费最小第2页/共43页 销地产地B1B2Bn产量A1A2 :Amc11c21:cm1c12c22:cm2:c1nc2n:cmna1a2:am销量b1b2bnv 已知有m个产地Ai（i=1,2， ， m ）可供应某种物资，其供应量（产量）分别为ai ，有n个销地Bj （j=1,2， ， n）其销量（需求量）分别为bj ，从A到B的单位物资运价为cij 。第3页/共43页ijxnjjmiiba11ijmnjijxcz11mini011

2、ijjmiijinjijxbxaxs.t.(i=1，2，m； j=1，2，n)矩阵形式：CXzmin0XAXbs.t. 1.运输问题模型及其求解思路运输问题模型及其求解思路第4页/共43页 1 1 11 1 11 1 11 1 11 1 1 A=m 行n 行 1.运输问题模型及其求解思路运输问题模型及其求解思路系数矩阵第5页/共43页2 1.运输问题模型及其求解思路运输问题模型及其求解思路对于产销平衡的运输问题，对于产销平衡的运输问题，若产地为若产地为m个，销地为个，销地为n个，个，则则 变量个数为变量个数为mn个，个，约束条件个数为约束条件个数为m+n，其中包含：总产量总销售其中包含：总产量

3、总销售故线性无关的约束条件个数为故线性无关的约束条件个数为m+n-1，基本解中的基变量个数为基本解中的基变量个数为m+n-1。第6页/共43页 1.运输问题模型及其求解思路运输问题模型及其求解思路第7页/共43页第8页/共43页1）最小元素法）最小元素法第9页/共43页甲甲乙乙丙丙丁丁产量产量A3113107B19284C741059销量销量36562.确定初始基本可行解确定初始基本可行解第10页/共43页34333231242322211413121151047829103113minxxxxxxxxxxxxz06563947342414332313322212312111343332312

4、423222114131211ijxxxxxxxxxxxxxxxxxxxxxxxxxs.t2.确定初始基本可行解确定初始基本可行解ijxv 若设 代表从第i个产地到第j个销售地的运输量（i=1,2,3；j=1,2,3,4)第11页/共43页B1B2B3B4产量产量A13113107A219284A3741059销量销量36563431632.确定初始基本可行解确定初始基本可行解Z=43+310+31+12+64+35=86第12页/共43页2.确定初始基本可行解确定初始基本可行解注意：注意：第13页/共43页B1B2B3B4产量产量A13113108A219283A3741059销量销量365

5、63530632.确定初始基本可行解确定初始基本可行解第14页/共43页2.确定初始基本可行解确定初始基本可行解第15页/共43页B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之差两最小元素之差2.确定初始基本可行解确定初始基本可行解0112513第16页/共43页B1B2B3B4两最小元素之差两最小元素之差A13113100A219281A3741052两最小元素之两最小元素之差差2132.确定初始基本可行解确定初始基本可行解第17页/共43页B1B2B3B4两最小元素之差两最小元素之差A13113100A219281A374105两最小元素

6、之两最小元素之差差2122.确定初始基本可行解确定初始基本可行解第18页/共43页B1B2B3B4两最小元素之差两最小元素之差A13113107A219286A374105两最小元素之两最小元素之差差122.确定初始基本可行解确定初始基本可行解第19页/共43页B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之两最小元素之差差22.确定初始基本可行解确定初始基本可行解第20页/共43页B1B2B3B4两最小元素之差两最小元素之差A1311310A21928A374105两最小元素之两最小元素之差差2.确定初始基本可行解确定初始基本可行解第21页/

7、共43页B1B2B3B4产量产量A1527A2314A3639销量销量36562.确定初始基本可行解确定初始基本可行解Z=53+210+31+18+64+35=85第22页/共43页第23页/共43页第24页/共43页B1B2B3B4产量产量A13113 410 37A21 392 184A374 6105 39销量销量3656v 若让若让x111，则总运费变化：，则总运费变化：31+231 。 11 =1v 若让若让x311，则总运费变化：，则总运费变化：75+103+2-110 。 31 =10第25页/共43页3.最优性检验最优性检验63 24 = -13B49 33 = 126 31

8、= 10A3563销量销量41 22= 13A274 12 = 2A1产量产量B3B2B1 11 = 1v最优标准：所有检验数最优标准：所有检验数 ij 0第26页/共43页3.最优性检验最优性检验第27页/共43页B1B2B3B4uiA13 11 3 410 3A21 39 2 18A37 4 6105 3vju1 u2u3v1v2v3v40103-1-5293.最优性检验最优性检验第28页/共43页B1B2B3B4uiA13 11 3 410 30A21 39 2 18-1A37 4 6105 3-5vj29310 ij=Cij-（Ui+Vj） 11=C11-（U1+V1）=3-(0+2)

9、=1 12=C12-（U1+V2）=11-(0+9)=2(1)(2)3.最优性检验最优性检验第29页/共43页B1B2B3B4产量产量A1437A2314A3639销量销量36563.最优性检验最优性检验 33=12 11=1 22=1 31=10 24= -1 12=2当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案为最，说明现行方案为最优方案，否则目标成本还可以进一步减小。优方案，否则目标成本还可以进一步减小。第30页/共43页当存在非基变量的检验数当存在非基变量的检验数 ij 0，说明现行方案为，说明现行方案为最优方案，否则目标成本还可以进一步减小。最优方案，否则目标

10、成本还可以进一步减小。第31页/共43页第32页/共43页第33页/共43页B1B2B3B4产量产量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39销量销量3656最小检验数最小检验数原则，确定原则，确定进基变量进基变量最小偶点原则最小偶点原则，确定出基变，确定出基变量和调整量量和调整量+1-1+1-1 13 , 1minmin14,23 xx第34页/共43页B1B2B3B4产量产量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39销量销量bj3656v 得到新的基变量：得

11、到新的基变量：x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3。重新计算检验数。重新计算检验数。（1）（2）（2）（1）（9）（12）第35页/共43页第36页/共43页第37页/共43页njjmiiba11ijmnjijxcz11mini011ijjmiijinjijxbxaxs.t.(i=1，2，m； j=1，2，n)njjmiinbab1110111ijjmiijinjijxbxaxs.t.(i=1，2，m； j=1，2，n+1)ijmnjijxcz111mini第38页/共43页 销地产地B1B2B3产量A1646300A2655300销量150150200 销地产地B1B2B3B4 (虚销地）虚销地）产量 A16460300A26550300销量150150200100第39页/共43页njjmiiba11ijmnjijxcz11mini011ijjmiijinjijxbxaxs.t.(i=1，2，m； j=1，2，n)miinjjmaba1110111ijjmiijinjijxbxaxs.t