运筹学06-运输问题课件

第六章运输问题6.1运输问题的数学模型6.2初始基可行解的确定6.3最优性检验与基可行解的改进6.4其他运输问题第六章运输问题6.1运输问题的数学模型运输问题（纺纱厂）

工厂

123库存仓121350222430

库334210

需求401535运输单价求：运输费用最小的运输方案。运输问题（纺纱厂）解：设xij为i

仓库运到j工厂的原棉数量其中：i

＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31≥40x12+x22+x32≥15x13+x23+x33≥

35xij

0s.t类似的例子：教材P6-P7，例3解：设xij为i仓库运到j工厂的原棉数量MinZ=26.1运输问题的数学模型若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求（或者如前例中类似的问题）。供应节点：这些工厂，它们是运输的起点；需求节点：用户所在点，它们是运输的终点或目的地。同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。这类问题就是运输问题。6.1运输问题的数学模型若一家公司拥有多个工厂，这些工厂(1)运输问题数学模型xij——供应节点i至需求节点j的运输量；ai——供应节点i的可供应量，i=1,2,…,m；bj——需求节点j的需求量，j=1,2,…,n；cij——供应节点i至需求节点j的单位运输成本。(1)运输问题数学模型xij——供应节点i至需求节点j根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。平衡型运输问题：不平衡型运输问题：对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。(2)运输问题的分类根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题的数学模型模型包含变量：m×n个约束方程：m+n个秩：r(A)=m+n-1

m行n行平衡型运输问题的数学模型模型包含m行n行(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。则有所以是运输问题的一个可行解。又由于所以且为极小化问题，故一定存在最优解。则有所以运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个运输问题的基本性质运输问题是一类特殊的线性规划问题运输问题的基本性质例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和19台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分2321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供应量供应节点运输成本需求量需求节点6753842759106海华设备厂运输问题网络图2321341sB=27sC=19d1=22d2=13d3=海华设备厂运输问题的表格表示海华设备厂运输问题的表格表示供应量约束需求量约束海华设备厂运输问题线性规划模型供应量约束需求量约束海华设备厂运输问题线性规划模型不平衡运输问题(1)：供过于求设置虚拟需求节点232131sB=27sC=19d1=22d2=13d3=12sA=14供应量需求量6758425910供应节点运输成本需求节点4d4=13000不平衡运输问题(1)：供过于求232131sB=27sC=1不平衡运输问题(2)：供不应求设置虚拟供应节点221341sB=27d1=22d2=13d3=12d4=13sA=14供应量需求量67538427供应节点运输成本需求节点3sC=190000不平衡运输问题(2)：供不应求221341sB=27d1=26.2初始基可行解的确定两种获得基可行解的常用方法：西北角法最小元素法6.2初始基可行解的确定两种获得基可行解的常用方法：813131466(1)西北角法813131466(1)西北角法(2)最小元素法(0)(2)最小元素法(0)(2)最小元素法(1)(2)最小元素法(1)(2)最小元素法(2)(2)最小元素法(2)(2)最小元素法(3)(2)最小元素法(3)(2)最小元素法(4)(2)最小元素法(4)(2)最小元素法(5)(2)最小元素法(5)(2)最小元素法(6)(2)最小元素法(6)6.3最优性检验与基可行解的改进(1)最优性检验充要条件由于基变量的检验数σij=0,只需确定非基变量的检验数！确定非基变量检验数的常用方法主要是：闭回路法——一个非基变量与某些基变量构成唯一闭回路,基可行解中基变量不含闭回路。位势法——利用对偶变量6.3最优性检验与基可行解的改进(1)最优性检验充要条件定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。或每个顶点都是转角点；每一条边都是水平线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个几何性质定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,

x21转角点转角点(1)x12,x13,x33,x32(2)x23,x1(2)闭回路法(0)(2)闭回路法(0)5(2)闭回路法(1)σ12=c12-c11+c21-c22=7-6+8-4=522136857495210376ABC142719121312341481313665(2)闭回路法(1)σ12=c12-c11+c21-c-55(2)闭回路法(2)σ13=c13-c11+c21-c23=5-6+8-2=5-55(2)闭回路法(2)σ13=c13-c11+c21557(2)闭回路法(3)σ14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=7557(2)闭回路法(3)σ14=c14-c11+c217559σ24=c24-c23+c33-c34=7-2+10-6=9(2)闭回路法(4)7559σ24=c24-c23+c33-c34=7-2+17955-11σ31=c31-c33+c23-c21=5-10+2-8=-11(2)闭回路法(5)7955-11σ31=c31-c33+c23-c21=5-7559-11-3σ32=c32-c33+c23-c22=9-10+2-4=-3(2)闭回路法(6)7559-11-3σ32=c32-c33+c23-c22=平衡型运输问题的对偶问题由于r(A’)=m+n-1，独立的约束方程个数为m+n-1;而变量个数为m+n，则其中有一个自由变量(3)位势法与m个供应约束相对应与n个需求约束相对应平衡型运输问题的对偶问题由于r(A’)=m+n-1，独立的约对偶规划由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-1，可以通过设定自由变量的值得到所有对偶变量。对偶规划由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-(3)位势法(0)(3)位势法(0)选择含基变量最多的行或列，令相应的u或v为零。(3)位势法(1)选择含基变量最多的行或列，令相应的u或v为零。(3)位势法v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(3)位势法(2)v1=c21-u2=8-0=8,v2=c22-u2=4u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(3)位势法(3)u1=c11-v1=6-8=-2,u3=c33-vv4=c34-u3=6-8=-2(3)位势法(4)v4=c34-u3=6-8=-2(3)位势法(4)(3)位势法(5)5σ12=c12-(u1+

v2)=7-(-2+4)=5(3)位势法(5)5σ12=c12-(u1+v2)=5(3)位势法(6)5σ13=c13-(u1+

v3)=5-(-2+2)=55(3)位势法(6)5σ13=c13-(u1+v3)(3)位势法(7)755σ14=c14-(u1+

v4)=3-(-2-2)=7(3)位势法(7)755σ14=c14-(u1+v4)(3)位势法(8)755σ24=c24-(u2+

v4)=7-(0-2)=99(3)位势法(8)755σ24=c24-(u2+v4)(3)位势法(9)7559σ31=c31-(u3+

v1)=5-(8+8)=-11-11(3)位势法(9)7559σ31=c31-(u3+v1(3)位势法(10)7559-11σ32=c32-(u3+

v2)=9-(8+4)=-3-3(3)位势法(10)7559-11σ32=c32-(u3(4)基可行解的改进选择负检验数中绝对值最大的非基变量为进基变量(存在多个时任选一个)确定进基变量确定离基变量选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变量为离基变量。运量调整重复上述步骤直至所有检验数大于零，即获得最优解。(4)基可行解的改进选择负检验数中绝对值最大的非基变量为进9755-11-3确定进基变量选择检验数绝对值最大的非基变量为进基变量9755-11-3确定进基变量选择检验数绝对值最大的非基变量9755-11-3确定闭回路9755-11-3确定闭回路9755-11-3确定离基变量9755-11-3确定离基变量9755-3调整运量6x31=6,x21=8-6=2,x23=6+6=129755-3调整运量6x31=6,x21=8-6=2,-2-4558进一步优化(0)11-2-4558进一步优化(0)11-2-4558进一步优化(1)11x14

进基，x34离基。-2-4558进一步优化(1)11x14进基，x34离基24558进一步优化(2)11所有非基变量的检验数均大于零，即为最优解。注意P13324558进一步优化(2)11所有非基变量的检验数均大于零，(1)产销不平衡的运输问题例：有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。需求地区化肥厂B1B2B3B4产量（万吨）A11613221750A21413191560A3192023---50最低需求（万吨）最高需求（万吨）3050707003010不限运价：万元/万吨6.4其他运输问题(1)产销不平衡的运输问题需求地区B1B2B3B4产量（万分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表——分析：产销平衡表(1)A1A2A3DB'1B''1B2B3B'4B''4

产量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716221340132014196015M19152350M产销平衡表(1)A1B'1B''1产销平衡表(3)

A1A2A3DB'1B''1B2B3B'4B''4UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M16产销平衡表(3)A1B'1B''1产销平衡表(4)A1A2A3DB'1B''1B2B3B'4B''4UiVj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M102000产销平衡表(4)A1B'1B''1产销平衡表(5)A1A2A3DB'1B''1B2B3B'4B''4UiVj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M1010302040产销平衡表(5)A1B'1B''1产销平衡表(6)A1A2A3DB'1B''1B2B3B'4B''4UiVj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM16产销平衡表(6)A1B'1B''1产销平衡表(7)A1A2A3DB'1B''1B2B3B'4B''4UiVj1613502217171414132019151015301930192020230MMM0M030M02016008-1511111315151555722334-1M-23M-23M+44M+2M203030200产销平衡表(7)A1B'1B''1产销平衡表(8)A1A2A3DB'1B''1B2B3B'4B''4UiVj135013201510153019301920200030020007-15121213151515447222241M-22M-22M+33M+2M1622171714141923MMM0MM16产销平衡表(8)A1B'1B''1产销平衡表(9)A1A2A3D1613502217171414132019151015301930192020023MMM0M030M0205060505030207030105016B'1B''1B2B3B'4B''4

产量

销量产销平衡表(9)A116135022171714141320

（2）有转运的运输问题在上面所讨论的问题中，我们都假定物品是由产地直接运送到目的地的，没有经过任何中间转运。然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地。有时，可能经过转运比直接运到目的地更加经济。因此，在决定运输方案时有必要把转运也考虑进去。这样，将使运输问题更加复杂。例：已知A1、A2、A3三个工厂生产同一种产品，用相同的价格供应B1、B2、B3三个销售点，有2个转运站T1、T2。允许产品在各工厂、销售点和转运站间转运，已知各工厂、销售点、转运站之间的单位运价和产销量如下表所示。试求最经济运输方案。（2）有转运的运输问题产地转运站销地产量A1A2A3T1T2B1B2B3产地A1862-410830A2851395910A3654228720转运站T12148463T2-328232销地B149242-5B2105863-4B38973254销量153510产地转运站销地产量A1A2A3T1T2B1B2B3产地A18解：将此转运问题化为等价的运输问题需作如下处理：将所有的产地、转运站和销地都作为产地与销地，则此问题转化为8个产地与8个销地运输问题；对扩大的运输问题建立运价表，没有运输路线的运价设为M，自我运输的运价为0；所有转运站的产量等于销量，且为最大可能调运量，即均为60；在扩大的运输问题中，由于原产地与销地均具有转运功能，所以原产地的产量两于原销地的销量均需加上最大可能调运量，即在原数值上加上60。扩大的运输表如下表所示。解：将此转运问题化为等价的运输问题需作如下处理：产地转运站销地产量A1A2A3T1T2B1B2B3产地A10862M410890A28051395970A36504228780转运站T12140846360T2M328023260销地B1492420M560B2105863M0460B38973254060销量6060606060759570产地转运站销地产量A1A2A3T1T2B1B2B3产地A10产地转运站销地产量A1A2A3T1T2B1B2B3产地A160151590A2551570A3602080转运站T15451060T2402060销地B16060B26060B36060销量6060606060759570最优调运方案如下表所示类运输问题，见P143产地转运站销地产量A1A2A3T1T2B1B2B3产地A16第六章作业题P146-p149:2、3、4(a)、6第六章作业题第六章运输问题6.1运输问题的数学模型6.2初始基可行解的确定6.3最优性检验与基可行解的改进6.4其他运输问题第六章运输问题6.1运输问题的数学模型运输问题（纺纱厂）

工厂

123库存仓121350222430

库334210

需求401535运输单价求：运输费用最小的运输方案。运输问题（纺纱厂）解：设xij为i

仓库运到j工厂的原棉数量其中：i

＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31≥40x12+x22+x32≥15x13+x23+x33≥

35xij

0s.t类似的例子：教材P6-P7，例3解：设xij为i仓库运到j工厂的原棉数量MinZ=26.1运输问题的数学模型若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求（或者如前例中类似的问题）。供应节点：这些工厂，它们是运输的起点；需求节点：用户所在点，它们是运输的终点或目的地。同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。这类问题就是运输问题。6.1运输问题的数学模型若一家公司拥有多个工厂，这些工厂(1)运输问题数学模型xij——供应节点i至需求节点j的运输量；ai——供应节点i的可供应量，i=1,2,…,m；bj——需求节点j的需求量，j=1,2,…,n；cij——供应节点i至需求节点j的单位运输成本。(1)运输问题数学模型xij——供应节点i至需求节点j根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。平衡型运输问题：不平衡型运输问题：对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。(2)运输问题的分类根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题的数学模型模型包含变量：m×n个约束方程：m+n个秩：r(A)=m+n-1

m行n行平衡型运输问题的数学模型模型包含m行n行(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。则有所以是运输问题的一个可行解。又由于所以且为极小化问题，故一定存在最优解。则有所以运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个运输问题的基本性质运输问题是一类特殊的线性规划问题运输问题的基本性质例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和19台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分2321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供应量供应节点运输成本需求量需求节点6753842759106海华设备厂运输问题网络图2321341sB=27sC=19d1=22d2=13d3=海华设备厂运输问题的表格表示海华设备厂运输问题的表格表示供应量约束需求量约束海华设备厂运输问题线性规划模型供应量约束需求量约束海华设备厂运输问题线性规划模型不平衡运输问题(1)：供过于求设置虚拟需求节点232131sB=27sC=19d1=22d2=13d3=12sA=14供应量需求量6758425910供应节点运输成本需求节点4d4=13000不平衡运输问题(1)：供过于求232131sB=27sC=1不平衡运输问题(2)：供不应求设置虚拟供应节点221341sB=27d1=22d2=13d3=12d4=13sA=14供应量需求量67538427供应节点运输成本需求节点3sC=190000不平衡运输问题(2)：供不应求221341sB=27d1=26.2初始基可行解的确定两种获得基可行解的常用方法：西北角法最小元素法6.2初始基可行解的确定两种获得基可行解的常用方法：813131466(1)西北角法813131466(1)西北角法(2)最小元素法(0)(2)最小元素法(0)(2)最小元素法(1)(2)最小元素法(1)(2)最小元素法(2)(2)最小元素法(2)(2)最小元素法(3)(2)最小元素法(3)(2)最小元素法(4)(2)最小元素法(4)(2)最小元素法(5)(2)最小元素法(5)(2)最小元素法(6)(2)最小元素法(6)6.3最优性检验与基可行解的改进(1)最优性检验充要条件由于基变量的检验数σij=0,只需确定非基变量的检验数！确定非基变量检验数的常用方法主要是：闭回路法——一个非基变量与某些基变量构成唯一闭回路,基可行解中基变量不含闭回路。位势法——利用对偶变量6.3最优性检验与基可行解的改进(1)最优性检验充要条件定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。或每个顶点都是转角点；每一条边都是水平线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个几何性质定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,

x21转角点转角点(1)x12,x13,x33,x32(2)x23,x1(2)闭回路法(0)(2)闭回路法(0)5(2)闭回路法(1)σ12=c12-c11+c21-c22=7-6+8-4=522136857495210376ABC142719121312341481313665(2)闭回路法(1)σ12=c12-c11+c21-c-55(2)闭回路法(2)σ13=c13-c11+c21-c23=5-6+8-2=5-55(2)闭回路法(2)σ13=c13-c11+c21557(2)闭回路法(3)σ14=c14-c11+c21-c23+c33-c34=3-6+8-2+10-6=7557(2)闭回路法(3)σ14=c14-c11+c217559σ24=c24-c23+c33-c34=7-2+10-6=9(2)闭回路法(4)7559σ24=c24-c23+c33-c34=7-2+17955-11σ31=c31-c33+c23-c21=5-10+2-8=-11(2)闭回路法(5)7955-11σ31=c31-c33+c23-c21=5-7559-11-3σ32=c32-c33+c23-c22=9-10+2-4=-3(2)闭回路法(6)7559-11-3σ32=c32-c33+c23-c22=平衡型运输问题的对偶问题由于r(A’)=m+n-1，独立的约束方程个数为m+n-1;而变量个数为m+n，则其中有一个自由变量(3)位势法与m个供应约束相对应与n个需求约束相对应平衡型运输问题的对偶问题由于r(A’)=m+n-1，独立的约对偶规划由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-1，可以通过设定自由变量的值得到所有对偶变量。对偶规划由于对偶变量的个数为m+n，而系数矩阵的秩为m+n-(3)位势法(0)(3)位势法(0)选择含基变量最多的行或列，令相应的u或v为零。(3)位势法(1)选择含基变量最多的行或列，令相应的u或v为零。(3)位势法v1=c21-u2=8-0=8,v2=c22-u2=4-0=4,v3=c23-u2=2-0=2(3)位势法(2)v1=c21-u2=8-0=8,v2=c22-u2=4u1=c11-v1=6-8=-2,u3=c33-v3=10-2=8(3)位势法(3)u1=c11-v1=6-8=-2,u3=c33-vv4=c34-u3=6-8=-2(3)位势法(4)v4=c34-u3=6-8=-2(3)位势法(4)(3)位势法(5)5σ12=c12-(u1+

v2)=7-(-2+4)=5(3)位势法(5)5σ12=c12-(u1+v2)=5(3)位势法(6)5σ13=c13-(u1+

v3)=5-(-2+2)=55(3)位势法(6)5σ13=c13-(u1+v3)(3)位势法(7)755σ14=c14-(u1+

v4)=3-(-2-2)=7(3)位势法(7)755σ14=c14-(u1+v4)(3)位势法(8)755σ24=c24-(u2+

v4)=7-(0-2)=99(3)位势法(8)755σ24=c24-(u2+v4)(3)位势法(9)7559σ31=c31-(u3+

v1)=5-(8+8)=-11-11(3)位势法(9)7559σ31=c31-(u3+v1(3)位势法(10)7559-11σ32=c32-(u3+

v2)=9-(8+4)=-3-3(3)位势法(10)7559-11σ32=c32-(u3(4)基可行解的改进选择负检验数中绝对值最大的非基变量为进基变量(存在多个时任选一个)确定进基变量确定离基变量选择包含进基变量的闭回路上距进基变量奇次的变量中运量最小的基变量为离基变量。运量调整重复上述步骤直至所有检验数大于零，即获得最优解。(4)基可行解的改进选择负检验数中绝对值最大的非基变量为进9755-11-3确定进基变量选择检验数绝对值最大的非基变量为进基变量9755-11-3确定进基变量选择检验数绝对值最大的非基变量9755-11-3确定闭回路9755-11-3确定闭回路9755-11-3确定离基变量9755-11-3确定离基变量9755-3调整运量6x31=6,x21=8-6=2,x23=6+6=129755-3调整运量6x31=6,x21=8-6=2,-2-4558进一步优化(0)11-2-4558进一步优化(0)11-2-4558进一步优化(1)11x14

进基，x34离基。-2-4558进一步优化(1)11x14进基，x34离基24558进一步优化(2)11所有非基变量的检验数均大于零，即为最优解。注意P13324558进一步优化(2)11所有非基变量的检验数均大于零，(1)产销不平衡的运输问题例：有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。需求地区化肥厂B1B2B3B4产量（万吨）A11613221750A21413191560A3192023---50最低需求（万吨）最高需求（万吨）3050707003010不限运价：万元/万吨6.4其他运输问题(1)产销不平衡的运输问题需求地区B1B2B3B4产量（万分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表——分析：产销平衡表(1)A1A2A3DB'1B''1B2B3B'4B''4

产量销量171714141319151519192023MMM0M0M0506050503020703010501616221350141901650MM0M070171716221340132014196015M19152350M产销平衡表(1)A1B'1B''1产销平衡表(3)

A1A2A3DB'1B''1B2B3B'4B''4UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M16产销平衡表(3)A1B'1B''1产销平衡表(4)A1A2A3DB'1B''1B2B3B'4B''4UiVj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M102000产销平衡表(4)A1B'1B''1产销平衡表(5)A1A2A3DB'1B''1B2B3B'4B''4UiVj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M1010302040产销平衡表(5)A1B'1B''1产销平衡表(6)A1A2A3DB'1B''1B2B3B'4B''4UiVj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM16产销平衡表(6)A1B'1B''1产销平衡表(7)A1A2A3DB'1B''1B2B3B'4B''4UiVj161350221717141413201915101530193019