《第七章_运输问题(1表上作业).ppt》由会员分享，可在线阅读，更多相关《第七章_运输问题(1表上作业).ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章第七章 运输问题运输问题TransportationProblem2021/9/241第七章第七章 运输问题运输问题l运输问题在工商管理中有着广泛的应用，运输问题在工商管理中有着广泛的应用，是一类重要的和特殊的是一类重要的和特殊的线性规划问题线性规划问题。l由于这类线性规划问题在结构上有特殊性，由于这类线性规划问题在结构上有特殊性，所以有专门的解法所以有专门的解法表上作业法表上作业法等，用等，用以简便求解这类问题。以简便求解这类问题。l管理运筹学软件中也为求解这类问题编制管理运筹学软件中也为求解这类问题编制了专门的程序供我们使用。了专门的程序供我们使用。2021/9/242第七章第七章
2、运输问题运输问题u7.1运输问题的模型运输问题的模型2021/9/2437.1 运输问题的模型运输问题的模型例例1.某公司从两个产地某公司从两个产地A1、A2 将物品运往三个销地将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问应如何调运运往各销地每件物品的运费如下表所示，问应如何调运可使总运输费用最小？可使总运输费用最小？运费单价运费单价销销地地产地产地B1B2B3产产量量(件件)A1646200A2655300销销量量(件件)1501502002021/9/2447.1 运输问题的模型运输问题的模型
3、解：这是一个解：这是一个产销平衡问题产销平衡问题：总产量总产量=总销量总销量=500。设设xij 为从产地为从产地Ai 运往销地运往销地Bj 的运输量，如：的运输量，如：x12表示从产地表示从产地A1 运往销地运往销地B2 的运输数量。于是我们的运输数量。于是我们得到得到新的综合表格新的综合表格：运费单价运费单价销销地地产地产地B1B2B3产产量量(件件)A1646200A2655300销销量量(件件)1501502002021/9/2457.1 运输问题的模型运输问题的模型解：这是一个解：这是一个产销平衡问题产销平衡问题：总产量总产量=总销量总销量=500。设设xij 为从产地为从产地Ai
4、运往销地运往销地Bj 的运输量，如：的运输量，如：x12表示从产地表示从产地A1 运往销地运往销地B2 的运输数量。于是我们的运输数量。于是我们得到得到新的综合表格新的综合表格：运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)1501502005005002021/9/246运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =
5、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）。解得：解得：min f =2500，x11=50，x12=150，x13=0，x21=100，x22=0，x23=200。2021/9/2477.1 运输问题的模型运输问题的模型1.1.一般运输问题的线性规划模型一般运输问题的线性规划模型 假设假设 A A1 1，A A2 2，A Am m 表示某物资的表示某物资的 m m 个产地；个产地；B B1
6、1，B B2 2，B Bn n 表示某物资的表示某物资的 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，称该运输问题是称该运输问题是产销平衡的产销平衡的；否则，称它是；否则，称它是产销不平衡的产销不平衡的。2021/9/2487.1 运输问题的模型运输问题的模型销地销地产地产地B1
7、B2Bn产量产量A1c11x11c12x12c1nx1ns1A2c21x21c22x22c2nx2ns2 Amcm1xm1cm2xm2cmn xmnsm销量销量d1d2dn2021/9/2497.1 运输问题的模型运输问题的模型 设设 x xijij 为为从从产产地地 A Ai i 运运往往销销地地 B Bj j 的的运运输输量量，则则对对于产销平衡问题，可得到下列运输问题的模型：于产销平衡问题，可得到下列运输问题的模型：m nminf=c cij ij x xij ij i=1j=1 ns.t.x xij ij =s si i i i=1,2,=1,2,m m j=1m x xij ij =
8、d dj j j j=1,2,=1,2,n n i=1x xij ij 0 0(i=1,2,m;j=1,2,n)。2021/9/2410运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)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）。2021
9、/9/24117.1 运输问题的模型运输问题的模型 设设 x xijij 为为从从产产地地 A Ai i 运运往往销销地地 B Bj j 的的运运输输量量，则则对对于产销平衡问题，可得到下列运输问题的模型：于产销平衡问题，可得到下列运输问题的模型：m nminf=c cij ij x xij ij i=1j=1 ns.t.x xij ij =s si i i i=1,2,=1,2,m m j=1m x xij ij =d dj j j j=1,2,=1,2,n n i=1x xij ij 0 0(i=1,2,m;j=1,2,n)。2021/9/24127.1 运输问题的模型运输问题的模型2.2
10、.一般模型的系数矩阵特征一般模型的系数矩阵特征1.共有共有 m+n 行，分别表示各产地和销地；行，分别表示各产地和销地；mn 列，列，分别表示各变量；分别表示各变量；2.每列只有两个每列只有两个 1 1，其余为，其余为 0 0，分别表示只有一个产地，分别表示只有一个产地和一个销地被使用。和一个销地被使用。2021/9/2413运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =6x11+4x12+6x13+6x21+5x22+5x23 s.
11、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）。2021/9/24147.1 运输问题的模型运输问题的模型2.2.一般模型的系数矩阵特征一般模型的系数矩阵特征1.共有共有 m+n 行，分别表示各产地和销地；行，分别表示各产地和销地；mn 列，列，分别表示各变量；分别表示各变量；2.每列只有两个每列只有两个 1 1，其余为，其余为 0 0，分别表示只有一个产地，分别表示只有一个产地和一个销地被使用。和一个销地被使用。2021/9/24157.1 运输问题的模型运
12、输问题的模型3.一般模型有时会发生一些如下变化：一般模型有时会发生一些如下变化：1）有时求目标函数最大值。如求利润最大或营业额）有时求目标函数最大值。如求利润最大或营业额最大等；最大等；2）当某些运输线路上的能力有限制时，模型中可直）当某些运输线路上的能力有限制时，模型中可直接加入（接加入（等式或不等式等式或不等式）约束；）约束；3）产销不平衡时，可加入虚设的产地（销大于产时）产销不平衡时，可加入虚设的产地（销大于产时）或销地（或销地（产大于销时产大于销时）。）。2021/9/2416第七章第七章 运输问题运输问题u7.1运输问题的模型运输问题的模型l7.2运输问题的表上作业法运输问题的表上作
13、业法2021/9/2417 7.2 运输问题的表上作业法运输问题的表上作业法l表上作业法是一种求解运输问题的特殊方表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。法，其实质是单纯形法。l运输问题都存在最优解。运输问题都存在最优解。2021/9/2418 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基本可行解找出初始基本可行解。对于有对于有m个产地个产地n个销地的产销平衡问题，则有个销地的产销平衡问题，则有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的约束个关于销量的约束方程。方程。2021/9/241
14、9运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)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）。2021/9/2420 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基本
15、可行解找出初始基本可行解。对于有对于有m个产地个产地n个销地的产销平衡问题，则有个销地的产销平衡问题，则有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的约束个关于销量的约束方程。方程。由于产销平衡，其模型最多只有由于产销平衡，其模型最多只有m+n-1个独立个独立的约束方程，即运输问题有的约束方程，即运输问题有m+n-1个基变量。个基变量。2021/9/2421运费单价运费单价 销地销地产地办产地办 运输量运输量B1B2B3产产量量(件件)A16x114x126x13200A26x215x225x23300销销量量(件件)150150200500500min f =6x11+4x1
16、2+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）。2021/9/2422 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解找出初始基可行解。对于有对于有m个产地个产地n个销地的产销平衡问题，则有个销地的产销平衡问题，则有m个关于产量的约束方程和个关于产量的约束方程和n个关于销量的约束个关于销量的约束方程。方程。由于产销平衡，其模型最多只有由于
17、产销平衡，其模型最多只有m+n-1个独立个独立的约束方程，即运输问题有的约束方程，即运输问题有m+n-1个基变量。个基变量。2021/9/2423 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。即检验除了上述即检验除了上述m+n-1个基变量以外的空格的检验个基变量以外的空格的检验数判别是否达到最优解，如果已是最优，停止计数判别是否达到最优解，如果已是最优，停止计算，否则转到下一步。算，否则转到下一步。2021/9/2424 7.2 运输问题的表上作业
18、法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。l3.确定入基变量和出基变量，找出新的基可行解。确定入基变量和出基变量，找出新的基可行解。l4.重复重复2、3直到得到最优解。直到得到最优解。2021/9/2425 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。2021/9/2426 7.2 运输问题的表上作业法运输问题的表上作业法例例.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司有四个
19、销售公司B1，B2，B3，B4，其各分厂每日的产，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元价的单位为百元/吨。问该公司应如何调运产品在满足各吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？销点的需求量的前提下总运费最少？销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量365620202021/9/2427 7.2 运输问题的表上作业法运输问题的表上作
20、业法1.找出初始基可行解。找出初始基可行解。最小元素法最小元素法我们很容易的直观想到我们很容易的直观想到,为了减少运费为了减少运费,应应优先考虑单位运输价格最小优先考虑单位运输价格最小(或运输距离最或运输距离最短短)的供销业务的供销业务,最大限度的满足其供销量。最大限度的满足其供销量。2021/9/2428 7.2 运输问题的表上作业法运输问题的表上作业法例例.喜庆食品公司有三个生产面包的分厂喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司有四个销售公司B1，B2，B3，B4，其各分厂每日的产，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的量、各销售公司每日的
21、销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元价的单位为百元/吨。问该公司应如何调运产品在满足各吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？销点的需求量的前提下总运费最少？销地销地产地产地B1B2B3B4产量产量A13113107A219284A3741059销量销量365620202021/9/2429销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9
22、/2430销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2431销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2432销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2433销地销地产地产地B1
23、B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2434销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2435销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2436销地销地产地产地B1B2B3B4产量产量A1311
24、31073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2437 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。注意两个问题：注意两个问题：1.当我们取定当我们取定xij的值之后，会出现的值之后，会出现Ai的产量与的产量与Bj的销量都改为零的情况，这时只能划去的销量都改为零的情况，这时只能划去Ai行或行或Bj列，但不能同时划去列，但不能同时划去Ai行与行与Bj列。列。2.用最小元素法时，可能会出现只剩下一行或一用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉
25、的情况，此时在列的所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格不能按空格划掉。这样可以保证填过数或零的格为为m+n-1个，即保证基变量的个数为个，即保证基变量的个数为m+n-1个。个。2021/9/2438销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2439销地销地产地产地B1B2B3B4产量产量A131131083043A21928310
26、31A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2440销地销地产地产地B1B2B3B4产量产量A131131083043A2192830031A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2441销地销地产地产地B1B2B3B4产量产量A131131083043A2192830030A37410593063销量销量30605406302020最小元素法最小元素法2021/9/2442销地销地产地产地B1B2B3B4产量产量A131131083053A2192830030A37410593063销
27、量销量30605506302020最小元素法最小元素法2021/9/2443 7.2 运输问题的表上作业法运输问题的表上作业法1.找出初始基可行解。找出初始基可行解。注意两个问题：注意两个问题：1.当我们取定当我们取定xij的值之后，会出现的值之后，会出现Ai的产量与的产量与Bj的销量都改为零的情况，这时只能划去的销量都改为零的情况，这时只能划去Ai行或行或Bj列，但不能同时划去列，但不能同时划去Ai行与行与Bj列。列。2.用最小元素法时，可能会出现只剩下一行或一用最小元素法时，可能会出现只剩下一行或一列的所有格均未填数或未被划掉的情况，此时在列的所有格均未填数或未被划掉的情况，此时在这一行或
28、者一列中除去已填上的数外均填上零，这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格不能按空格划掉。这样可以保证填过数或零的格为为m+n-1个，即保证基变量的个数为个，即保证基变量的个数为m+n-1个。个。2021/9/2444 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数求各非基变量的检验数2021/9/2445 7.2 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数所谓所谓闭回路闭回路是在已给出的
29、调运方案的运输表上从一个是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进；代表非基变量的空格出发，沿水平或垂直方向前进；只有遇到代表基变量的填入数字的格才能向左或右转只有遇到代表基变量的填入数字的格才能向左或右转9090度（当然也可以不改变方向）继续前进，度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。的封闭折线叫做闭回路。一个空格存在唯一的闭回路。一个空格存在唯一的闭回路。2021/9/2446销地销地产地产地B1B2B3B4产量产量A131131073043
30、A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2447销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2448 7.2 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数闭回路闭回路 所谓所谓闭回路闭回路是在已给出的调运方案的运输表上从一个是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代
31、表基变量的填入数字的格才能向左或右转只有遇到代表基变量的填入数字的格才能向左或右转9090度（当然也可以不改变方向）继续前进，这样继续度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。线叫做闭回路。一个空格存在唯一的闭回路。一个空格存在唯一的闭回路。2021/9/2449销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2450销地销地产地产地B1B2B3B4产量产量A13
32、1131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2451销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2452 7.2 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数对于代表非基变量的空格（其调运量为零），把它的对于代表非基变量的空格（其调运量为零），把它的调运量调整为调运量调整为1 1，由于产销平衡的要求，由于产销平衡的要求,我们必须对这我们必须对这
33、个空格的闭回路的顶点的调运量加上或减少个空格的闭回路的顶点的调运量加上或减少1 1。最后我们计算出由这些变化给整个运输方案的总运输最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。费带来的变化。2021/9/2453销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2454销地销地产地产地B1B2B3B4产量产量A1311310730+143A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2455销地销
34、地产地产地B1B2B3B4产量产量A1311310730+14-13A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2456销地销地产地产地B1B2B3B4产量产量A1311310730+14-13A2192841031+1A37410593063销量销量30605406302020闭回路闭回路2021/9/2457销地销地产地产地B1B2B3B4产量产量A1311310730+14-13A219284103-11+1A37410593063销量销量30605406302020闭回路闭回路检验数即为检验数即为3-3+2-1=12021
35、/9/2458销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2459销地销地产地产地B1B2B3B4产量产量A1311310730+143A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2460销地销地产地产地B1B2B3B4产量产量A1311310730+143-1A2192841031A37410593063销量销量30605406302020闭回路闭回路2021/9/2461销地销地产地产地B1B2B3
36、B4产量产量A1311310730+143-1A2192841031A37410593063+1销量销量30605406302020闭回路闭回路2021/9/2462销地销地产地产地B1B2B3B4产量产量A1311310730+143-1A2192841031A3741059306-13+1销量销量30605406302020闭回路闭回路检验数即为检验数即为11-10+5-4=22021/9/2463销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路闭回路检验数即为检验数即为7-5+10-
37、3+2-1=102021/9/2464销地销地产地产地B1B2B3B4产量产量A13113107301243A21928410311-1A374105930106123销量销量30605406302020闭回路闭回路2021/9/2465 7.3 运输问题的表上作业法运输问题的表上作业法2.求各非基变量的检验数求各非基变量的检验数对于代表非基变量的空格（其调运量为零），把它的调对于代表非基变量的空格（其调运量为零），把它的调运量调整为运量调整为1 1，由于产销平衡的要求，由于产销平衡的要求,我们必须对这个空我们必须对这个空格的闭回路的顶点的调运量加上或减少格的闭回路的顶点的调运量加上或减少1
38、1。最后我们计算出由这些变化给整个运输方案的总运输费最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。带来的变化。如果所有代表非基变量的空格的检验数都大于等于零，如果所有代表非基变量的空格的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。则已求得最优解，否则继续迭代找出最优解。2021/9/2466 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。l3.确定入基变量和出基变量，找出新的基可行解。确定入基变量和出基变量，找出新的基可
39、行解。闭回路调整法闭回路调整法2021/9/2467闭回路调整法闭回路调整法1.1.选取所有负检验数最小的非基变量选取所有负检验数最小的非基变量作为入基变量，以求尽快实现最优。作为入基变量，以求尽快实现最优。2021/9/2468销地销地产地产地B1B2B3B4产量产量A13113107301243A21928410311-1A374105930106123销量销量30605406302020闭回路调整法闭回路调整法2021/9/2469闭回路调整法闭回路调整法1.1.选取所有负检验数最小的非基变量选取所有负检验数最小的非基变量x xijij作为作为入基变量，以求尽快实现最优。入基变量，以求尽
40、快实现最优。2.2.在以在以x xijij为出发点的闭回路中，找出所有为出发点的闭回路中，找出所有偶偶数的顶点数的顶点的调运量的调运量,以其中的以其中的最小的变量最小的变量为为换出变量换出变量3.3.将该闭回路上所有的将该闭回路上所有的奇数顶点奇数顶点的调运量增的调运量增加这一数值，所有的加这一数值，所有的偶数顶点偶数顶点的调运量减的调运量减少这一数值。少这一数值。2021/9/2470销地销地产地产地B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路调整法闭回路调整法2021/9/2471销地销地产地产地
41、B1B2B3B4产量产量A131131073043A2192841031A37410593063销量销量30605406302020闭回路调整法闭回路调整法2021/9/2472闭回路调整法闭回路调整法1.1.选取所有负检验数最小的非基变量选取所有负检验数最小的非基变量x xijij作为作为入基变量，以求尽快实现最优。入基变量，以求尽快实现最优。2.2.在以在以x xijij为出发点的闭回路中，找出所有为出发点的闭回路中，找出所有偶偶数的顶点的调运数的顶点的调运量量,以其中的以其中的最小的变量最小的变量为为换出变量换出变量3.3.将该闭回路上所有的将该闭回路上所有的奇数顶点奇数顶点的调运量增的
42、调运量增加这一数值，所有的加这一数值，所有的偶数顶点偶数顶点的调运量减的调运量减少这一数值。少这一数值。2021/9/2473销地销地产地产地B1B2B3B4产量产量A131131074（+1）3（-1）A21928431（-1）（+1）A374105963销量销量36562020闭回路调整法闭回路调整法2021/9/2474销地销地产地产地B1B2B3B4产量产量A1311310752A21928431A374105963销量销量36562020闭回路调整法闭回路调整法2021/9/2475销地销地产地产地B1B2B3B4产量产量A13113107300252A219284103211A37
43、410593096123销量销量30605406302020闭回路调整法闭回路调整法2021/9/2476 7.2 运输问题的表上作业法运输问题的表上作业法计算过程（假设产销平衡）：计算过程（假设产销平衡）：l1.找出初始基可行解。找出初始基可行解。l2.求各非基变量的检验数。求各非基变量的检验数。l3.确定入基变量和出基变量，找出新的基可行解。确定入基变量和出基变量，找出新的基可行解。l4.重复重复2、3直到得到最优解。直到得到最优解。2021/9/2477 7.2 运输问题的表上作业法运输问题的表上作业法如何找多个最优方案？如何找多个最优方案？l识别是否有多个最优解的方法和单纯形表法一样，
44、识别是否有多个最优解的方法和单纯形表法一样，只需看最优方案中是否存在非基变量的检验数为只需看最优方案中是否存在非基变量的检验数为零。零。l如在本题中给出的最优运输方案中如在本题中给出的最优运输方案中x11的检验数为的检验数为0，可知此运输问题有多个最优解。，可知此运输问题有多个最优解。l只要把只要把x11作为入基变量，调整运输方案，就可得作为入基变量，调整运输方案，就可得到另一个最优方案。到另一个最优方案。2021/9/2478销地销地产地产地B1B2B3B4产量产量A13113107300252A219284103211A37410593096123销量销量30605406302020闭回路
45、调整法闭回路调整法2021/9/2479闭回路调整法闭回路调整法 销地产地 B1 B2 B3 B4A1(+2)52(-2)A23(-2)1(+2)A363 销地产地 B1 B2 B3 B4A12 5A213A3632021/9/2480销地销地产地产地B1B2B3B4产量产量A141241016A22103810A38511622销量销量81412144848习题习题2021/9/2481销地销地产地产地B1B2B3B4产量产量A141241016124A2210381082A38511622148销量销量81412144848习题习题2021/9/2482 销地销地产地产地1 12 23 3
46、4 4 产量产量A A545449495252646411001100B B575773736969616110001000 销量销量500500300300 550 550650650 2100210020002000P155-5P155-52021/9/2483 销地销地产地产地1 12 23 34 45 5 产量产量A A54544949525264640 011001100B B57577373696961610 010001000 销量销量500500300300 550 550650650100100 2100210021002100P155-5P155-52021/9/2484
47、销地销地产地产地1 12 23 34 45 5 产量产量A A54544949525264640 011001100250250300300550550B B57577373696961610 010001000250250650650100100 销量销量500500300300 550 550650650100100 2100210021002100P155-5P155-52021/9/2485 销地销地产地产地1 12 23 3 产量产量甲甲8 87 74 415151515乙乙3 35 59 92525101010105 5丙丙0 00 00 010101010 销量销量20201010 20 20 50505050P155-6P155-62021/9/2486 销地销地产地产地1 12 23 3 产量产量甲甲8 87 74 415151515乙乙3 35 59 9252520205 5丙丙0 00 00 010105 55 5 销量销量20201010 20 20 50505050P155-6P155-62021/9/2487