1、第七章第七章 运输问题运输问题Transportation Problem1第七章第七章 运输问题运输问题l运输问题在工商管理中有着广泛的应用，运输问题在工商管理中有着广泛的应用，是一类重要的和特殊的是一类重要的和特殊的线性规划问题线性规划问题。l由于这类线性规划问题在结构上有特殊性，由于这类线性规划问题在结构上有特殊性，所以有专门的解法所以有专门的解法表上作业法表上作业法等，用等，用以简便求解这类问题。以简便求解这类问题。l管理运筹学软件中也为求解这类问题编制管理运筹学软件中也为求解这类问题编制了专门的程序供我们使用。了专门的程序供我们使用。2第七章第七章 运输问题运输问题u7.1 运输问题
2、的模型运输问题的模型37.1 7.1 运输问题的模型运输问题的模型例例1.某公司从两个产地某公司从两个产地 A1、A2 将物品运往三个销地将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问应如何调运运往各销地每件物品的运费如下表所示，问应如何调运可使总运输费用最小？可使总运输费用最小？运费单价运费单价 销地销地产地产地 B1B2B3产产 量量(件件)A1646200A2655300销销 量量(件件)15015020047.1 7.1 运输问题的模型运输问题的模型解：这是一个解：这是一个产销平衡问题产销
3、平衡问题：总产量总产量=总销量总销量=500。设设 xij 为从产地为从产地 Ai 运往销地运往销地 Bj 的运输量，如：的运输量，如：x12 表示从产地表示从产地 A1 运往销地运往销地 B2 的运输数量。于是我们的运输数量。于是我们得到得到新的综合表格新的综合表格：运费单价运费单价 销地销地产地产地 B1B2B3产产 量量(件件)A1646200A2655300销销 量量(件件)15015020057.1 7.1 运输问题的模型运输问题的模型解：这是一个解：这是一个产销平衡问题产销平衡问题：总产量总产量=总销量总销量=500。设设 xij 为从产地为从产地 Ai 运往销地运往销地 Bj 的
4、运输量，如：的运输量，如：x12 表示从产地表示从产地 A1 运往销地运往销地 B2 的运输数量。于是我们的运输数量。于是我们得到得到新的综合表格新的综合表格：运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产 量量(件件)A16x114 x126x13200A26x215x225x23300销销 量量(件件)1501502005005006运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产 量量(件件)A16x114 x126x13200A26x215x225x23300销销 量量(件件)150150200500500min f =6x11+4x12+6x
5、13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1，2；j=1，2，3）。解得：解得：min f =2500，x11=50，x12=150，x13=0，x21=100，x22=0，x23=200。77.1 7.1 运输问题的模型运输问题的模型1.1.一般运输问题的线性规划模型一般运输问题的线性规划模型 假设假设 A A1 1，A A2 2，A Am m 表示某物资的表示某物资的 m m 个产地；个产地；B B1 1，B B2 2，B Bn n 表
6、示某物资的表示某物资的 n n 个销地；个销地；s si i 表示产地表示产地 A Ai i 的产量；的产量；d dj j 表示销地表示销地 B Bj j 的销量；的销量；c cijij 表示把物资从产地表示把物资从产地 A Ai i 运往销地运往销地 B Bj j 的单位运价。的单位运价。如果如果 s s1 1+s s2 2+s sm m =d d1 1+d d2 2+d dn n，称该运输问题是称该运输问题是产销平衡的产销平衡的；否则，称它是；否则，称它是产销不平衡的产销不平衡的。87.1 7.1 运输问题的模型运输问题的模型 销地销地产地产地B1B2Bn产量产量A1 c11 x11c12
7、 x12c1n x1ns1 A2 c21 x21c22 x22c2n x2ns2 Amcm1 xm1cm2 xm2cmn xmnsm销量销量d1d2dn 97.1 7.1 运输问题的模型运输问题的模型 设设 x xijij 为从产地为从产地 A Ai i 运往销地运往销地 B Bj j 的运输量，则对的运输量，则对于产销平衡问题，可得到下列运输问题的模型：于产销平衡问题，可得到下列运输问题的模型：m n min f=c cij ij x xij ij i=1 j=1 n s.t.x xij ij =s si i i i=1,2,=1,2,m m j=1 m x xij ij =d dj j j
8、 j=1,2,=1,2,n n i=1 x xij ij 0 0 (i=1,2,m;j=1,2,n)。10运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产 量量(件件)A16x114 x126x13200A26x215x225x23300销销 量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1，2；j=1，2，3）。117.1 7.1 运输问题的模
9、型运输问题的模型 设设 x xijij 为从产地为从产地 A Ai i 运往销地运往销地 B Bj j 的运输量，则对的运输量，则对于产销平衡问题，可得到下列运输问题的模型：于产销平衡问题，可得到下列运输问题的模型：m n min f=c cij ij x xij ij i=1 j=1 n s.t.x xij ij =s si i i i=1,2,=1,2,m m j=1 m x xij ij =d dj j j j=1,2,=1,2,n n i=1 x xij ij 0 0 (i=1,2,m;j=1,2,n)。127.1 7.1 运输问题的模型运输问题的模型2.2.一般模型的系数矩阵特征一般
10、模型的系数矩阵特征1.共有共有 m+n 行，分别表示各产地和销地；行，分别表示各产地和销地；mn 列，列，分别表示各变量；分别表示各变量；2.每列只有两个每列只有两个 1 1，其余为，其余为 0 0，分别表示只有一个产地，分别表示只有一个产地和一个销地被使用。和一个销地被使用。13运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产 量量(件件)A16x114 x126x13200A26x215x225x23300销销 量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x2
11、1+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1，2；j=1，2，3）。147.1 7.1 运输问题的模型运输问题的模型2.2.一般模型的系数矩阵特征一般模型的系数矩阵特征1.共有共有 m+n 行，分别表示各产地和销地；行，分别表示各产地和销地；mn 列，列，分别表示各变量；分别表示各变量；2.每列只有两个每列只有两个 1 1，其余为，其余为 0 0，分别表示只有一个产地，分别表示只有一个产地和一个销地被使用。和一个销地被使用。157.1 7.1 运输问题的模型运输问题的模型3.一般模型有时会发生一些如下变化：一般模型有时
12、会发生一些如下变化：1）有时求目标函数最大值。如求利润最大或营业额）有时求目标函数最大值。如求利润最大或营业额最大等；最大等；2）当某些运输线路上的能力有限制时，模型中可直）当某些运输线路上的能力有限制时，模型中可直接加入（接加入（等式或不等式等式或不等式）约束；）约束；3）产销不平衡时，可加入虚设的产地（销大于产时）产销不平衡时，可加入虚设的产地（销大于产时）或销地（或销地（产大于销时产大于销时）。）。16第七章第七章 运输问题运输问题u7.1 运输问题的模型运输问题的模型l7.2 运输问题的表上作业法运输问题的表上作业法17 7.2 7.2 运输问题的表上作业法运输问题的表上作业法l表上作
13、业法是一种求解运输问题的特殊方表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。法，其实质是单纯形法。l运输问题都存在最优解。运输问题都存在最优解。18 7.2 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基本可行解找出初始基本可行解。对于有对于有m个产地个产地n个销地的产销平衡问题，则个销地的产销平衡问题，则有有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的个关于销量的约束方程。约束方程。19运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产 量量(件件)A16x114 x126x1
14、3200A26x215x225x23300销销 量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1，2；j=1，2，3）。20 7.2 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基本可行解找出初始基本可行解。对于有对于有m个产地个产地n个销地的产销平衡问题，则个销地的产销平衡问题，则有有m个关于产
15、量的约束方程和个关于产量的约束方程和n个关于销量的个关于销量的约束方程。约束方程。由于产销平衡，其模型最多只有由于产销平衡，其模型最多只有m+n-1个独立个独立的约束方程，即运输问题有的约束方程，即运输问题有m+n-1个基变量。个基变量。21运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产 量量(件件)A16x114 x126x13200A26x215x225x23300销销 量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x2
16、1=150 x12+x22=150 x13+x23=200 xij 0 (i=1，2；j=1，2，3）。22 7.2 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解找出初始基可行解。对于有对于有m个产地个产地n个销地的产销平衡问题，则个销地的产销平衡问题，则有有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的个关于销量的约束方程。约束方程。由于产销平衡，其模型最多只有由于产销平衡，其模型最多只有m+n-1个独立个独立的约束方程，即运输问题有的约束方程，即运输问题有m+n-1个基变量。个基变量。23 7.2
17、7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。即检验除了上述即检验除了上述m+n-1个基变量以外的空格的检验个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。算，否则转到下一步。24 7.2 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的
18、检验数。l3.确定入基变量和出基变量，找出新的基可行解。确定入基变量和出基变量，找出新的基可行解。l4.重复重复2、3直到得到最优解。直到得到最优解。25 7.2 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。26 7.2 7.2 运输问题的表上作业法运输问题的表上作业法 例例.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司有四个销售公司B1，B2，B3，B4，其各分厂每日的产，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所
19、示，在表中产量与销量的单位为吨，运单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元价的单位为百元/吨。问该公司应如何调运产品在满足各吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？销点的需求量的前提下总运费最少？销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656 202027 7.2 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。最小元素法最小元素法 我们很容易的直观想到我们很容易的直观想到,为了减少运费为了减少运费,应优应优先考虑单位运输价格最小先考虑单位运输价格最
20、小(或运输距离最短或运输距离最短)的供销业务的供销业务,最大限度的满足其供销量。最大限度的满足其供销量。28 7.2 7.2 运输问题的表上作业法运输问题的表上作业法 例例.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司有四个销售公司B1，B2，B3，B4，其各分厂每日的产，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元价的单位为百元/吨。问该公司应如何调运产品在满足各吨
21、。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？销点的需求量的前提下总运费最少？销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量3656 202029 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法30 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量
22、 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法31 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法32 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法33 销地销地产地产地B1B2B3B4 产量产量A1311310 7
23、3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法34 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法35 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020
24、最小元素法最小元素法36 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法37 7.2 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。注意两个问题：注意两个问题：1.当我们取定当我们取定xij的值之后，会出现的值之后，会出现Ai的产量与的产量与Bj的销量都改为零的情况，这时只能划去的销量都改为零的情况，这时只能划去Ai行或行或Bj列，但不能同时划去列，但不能同时划去Ai行与行与B
25、j列。列。2.用最小元素法时，可能会出现只剩下一行或一用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格不能按空格划掉。这样可以保证填过数或零的格为为m+n-1个，即保证基变量的个数为个，即保证基变量的个数为m+n-1个。个。38 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6
26、0 5 4 0 6 3 0 2020最小元素法最小元素法39 销地销地产地产地B1B2B3B4 产量产量A1311310 8 3 0 4 3A21928 3 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法40 销地销地产地产地B1B2B3B4 产量产量A1311310 8 3 0 4 3A21928 3 0 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法41 销地销地产地产地B1B2B3B4 产量产量A1311310 8 3 0 4 3
27、A21928 3 0 0 3 0A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020最小元素法最小元素法42 销地销地产地产地B1B2B3B4 产量产量A1311310 8 3 0 5 3A21928 3 0 0 3 0A374105 9 3 0 6 3 销量销量 3 0 6 0 5 5 0 6 3 0 2020最小元素法最小元素法43 7.2 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。注意两个问题：注意两个问题：1.当我们取定当我们取定xij的值之后，会出现的值之后，会出现Ai的产量与的产量与Bj的销量都
28、改为零的情况，这时只能划去的销量都改为零的情况，这时只能划去Ai行或行或Bj列，但不能同时划去列，但不能同时划去Ai行与行与Bj列。列。2.用最小元素法时，可能会出现只剩下一行或一用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格不能按空格划掉。这样可以保证填过数或零的格为为m+n-1个，即保证基变量的个数为个，即保证基变量的个数为m+n-1个。个。44 7.2 7.2 运输问题的表上作业法运输问
29、题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数求各非基变量的检验数45 7.2 7.2 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数所谓所谓闭回路闭回路是在已给出的调运方案的运输表上从一个是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进；代表非基变量的空格出发，沿水平或垂直方向前进；只有遇到代表基变量的填入数字的格才能向左或右转只有遇到代表基变量的填入数字的格才能向左或右转9090度（当然也可以不改变方向）继续前进，度（当然也可以不改变
30、方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。的封闭折线叫做闭回路。一个空格存在唯一的闭回路。一个空格存在唯一的闭回路。46 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路47 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6
31、0 5 4 0 6 3 0 2020闭回路闭回路48 7.2 7.2 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数闭回路闭回路 所谓所谓闭回路闭回路是在已给出的调运方案的运输表上从一是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转只有遇到代表基变量的填入数字的格才能向左或右转9090度（当然也可以不改变方向）继续前进，这样继续度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折下去，直至回到
32、出发的那个空格，由此形成的封闭折线叫做闭回路。线叫做闭回路。一个空格存在唯一的闭回路。一个空格存在唯一的闭回路。49 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路50 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路51 销地销地产地产地B1B2B3B4 产量
33、产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路52 7.2 7.2 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数对于代表非基变量的空格（其调运量为零），把它的对于代表非基变量的空格（其调运量为零），把它的调运量调整为调运量调整为1 1，由于产销平衡的要求，由于产销平衡的要求,我们必须对这我们必须对这个空格的闭回路的顶点的调运量加上或减少个空格的闭回路的顶点的调运量加上或减少1 1。最后我们计算出由这些变化给整个运输方案的总运
34、输最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。费带来的变化。53 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路54 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 +1 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路55 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3
35、0 +1 4-1 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路56 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 +1 4-1 3A21928 4 1 0 3 1+1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路57 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 +1 4-1 3A21928 4 1 0 3-1 1+1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0
36、 6 3 0 2020闭回路闭回路检验数即为检验数即为 3-3+2-1=158 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路59 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0+1 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路60 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0+
37、1 4 3-1A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路61 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0+1 4 3-1A21928 4 1 0 3 1A374105 9 3 0 6 3+1 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路62 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0+1 4 3-1A21928 4 1 0 3 1A374105 9 3 0 6-1 3+1 销量销量 3 0 6 0 5 4 0 6 3
38、0 2020闭回路闭回路检验数即为检验数即为 11-10+5-4=263 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路检验数即为检验数即为 7-5+10-3+2-1=1064 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 012 4 3A21928 4 1 0 31 1-1A374105 9 3 010 612 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路闭回路65 7.3 7.
39、3 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数对于代表非基变量的空格（其调运量为零），把它的调对于代表非基变量的空格（其调运量为零），把它的调运量调整为运量调整为1 1，由于产销平衡的要求，由于产销平衡的要求,我们必须对这个空我们必须对这个空格的闭回路的顶点的调运量加上或减少格的闭回路的顶点的调运量加上或减少1 1。最后我们计算出由这些变化给整个运输方案的总运输费最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。带来的变化。如果所有代表非基变量的空格的检验数都大于等于零，如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解，否则继续
40、迭代找出最优解。则已求得最优解，否则继续迭代找出最优解。66 7.2 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。l3.确定入基变量和出基变量，找出新的基可行解。确定入基变量和出基变量，找出新的基可行解。闭回路调整法闭回路调整法67闭回路调整法闭回路调整法1.1.选取所有负检验数最小的非基变选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。量作为入基变量，以求尽快实现最优。68 销地销地产地产地B1B2B3B4 产量产量A1311310
41、 7 3 012 4 3A21928 4 1 0 31 1-1A374105 9 3 010 612 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路调整法闭回路调整法69闭回路调整法闭回路调整法1.1.选取所有负检验数最小的非基变量选取所有负检验数最小的非基变量x xijij作为作为入基变量，以求尽快实现最优。入基变量，以求尽快实现最优。2.2.在以在以x xijij为出发点的闭回路中，找出所有为出发点的闭回路中，找出所有偶偶数的顶点数的顶点的调运量的调运量,以其中的以其中的最小的变量最小的变量为为换出变量换出变量3.3.将该闭回路上所有的将该闭回路上所有的奇数顶点奇数顶
42、点的调运量增的调运量增加这一数值，所有的加这一数值，所有的偶数顶点偶数顶点的调运量减的调运量减少这一数值。少这一数值。70 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路调整法闭回路调整法71 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 0 4 3A21928 4 1 0 3 1A374105 9 3 0 6 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路调整法闭回路调整法72闭回路调整
43、法闭回路调整法1.1.选取所有负检验数最小的非基变量选取所有负检验数最小的非基变量x xijij作为作为入基变量，以求尽快实现最优。入基变量，以求尽快实现最优。2.2.在以在以x xijij为出发点的闭回路中，找出所有为出发点的闭回路中，找出所有偶偶数的顶点的调运数的顶点的调运量量,以其中的以其中的最小的变量最小的变量为为换出变量换出变量3.3.将该闭回路上所有的将该闭回路上所有的奇数顶点奇数顶点的调运量增的调运量增加这一数值，所有的加这一数值，所有的偶数顶点偶数顶点的调运量减的调运量减少这一数值。少这一数值。73 销地销地产地产地B1B2B3B4 产量产量A1311310 7 4（+1）3（
44、-1）A21928 4 3 1（-1）（+1）A374105 9 6 3 销量销量 3 6 5 6 2020闭回路调整法闭回路调整法74 销地销地产地产地B1B2B3B4 产量产量A1311310 7 5 2A21928 4 3 1A374105 9 6 3 销量销量 3 6 5 6 2020闭回路调整法闭回路调整法75 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 002 5 2A21928 4 1 0 32 11A374105 9 3 09 612 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路调整法闭回路调整法76 7.2 7.2 运输问题的表
45、上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。l3.确定入基变量和出基变量，找出新的基可行解。确定入基变量和出基变量，找出新的基可行解。l4.重复重复2、3直到得到最优解。直到得到最优解。77 7.2 7.2 运输问题的表上作业法运输问题的表上作业法如何找多个最优方案？如何找多个最优方案？l识别是否有多个最优解的方法和单纯形表法一样，识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为只需看最优方案中是否存在非基变量的检验数为零。零。l
46、如在本题中给出的最优运输方案中如在本题中给出的最优运输方案中x11的检验数为的检验数为0，可知此运输问题有多个最优解。，可知此运输问题有多个最优解。l只要把只要把x11作为入基变量，调整运输方案，就可得作为入基变量，调整运输方案，就可得到另一个最优方案。到另一个最优方案。78 销地销地产地产地B1B2B3B4 产量产量A1311310 7 3 002 5 2A21928 4 1 0 32 11A374105 9 3 09 612 3 销量销量 3 0 6 0 5 4 0 6 3 0 2020闭回路调整法闭回路调整法79闭回路调整法闭回路调整法 销地产地 B1 B2 B3 B4A1 (+2)5
47、2(-2)A2 3(-2)1(+2)A3 6 3 销地产地 B1 B2 B3 B4A1 2 5 A2 1 3A3 6 380 销地销地产地产地B1B2B3B4 产量产量A141241016A22103810A385116 22 销量销量8 141214 4848习题习题81 销地销地产地产地B1B2B3B4 产量产量A141241016124A2210381082A385116 22148 销量销量8 141214 4848习题习题82 销地销地产地产地1 12 23 34 4 产量产量A A545449495252646411001100B B575773736969616110001000
48、 销量销量500500300300 550 550650650 2100210020002000P155-5P155-583 销地销地产地产地1 12 23 34 45 5 产量产量A A54544949525264640 011001100B B57577373696961610 010001000 销量销量500500300300 550 550650650100100 2100210021002100P155-5P155-584 销地销地产地产地1 12 23 34 45 5 产量产量A A54544949525264640 011001100250250300300550550B B5
49、7577373696961610 010001000250250650650100100 销量销量500500300300 550 550650650100100 2100210021002100P155-5P155-585 销地销地产地产地1 12 23 3 产量产量甲甲8 87 74 415151515乙乙3 35 59 92525101010105 5丙丙0 00 00 010101010 销量销量20201010 20 20 50505050P155-6P155-686 销地销地产地产地1 12 23 3 产量产量甲甲8 87 74 415151515乙乙3 35 59 9252520205 5丙丙0 00 00 010105 55 5 销量销量20201010 20 20 50505050P155-6P155-687放映放映结束！结束！无悔无愧于昨天，丰硕殷实无悔无愧于昨天，丰硕殷实的今天，充满希望的明天。的今天，充满希望的明天。88
