运输模型解析课件

第5章运输模型5.1运输问题及其数学模型5.2表上作业法5.2.1初始方案的确定5.2.2最优性检验5.2.3非最优方案的调整5.2.4产销不平衡问题的解法5.3运输模型的应用第5章运输模型5.1运输问题及其数学模型运输模型是线性规划诸多模型中较早引起人们关注的一类模型，由美国学者希奇柯克（Hitchcock，1941）和库普曼（Koopmans，1947）提出。中国——“图上作业法”（1958年）1975年康托洛维奇和库普曼因资源配置理论研究获得诺贝尔经济学奖（丹茨格）（24、12、4）（日内瓦国际应用系统分析研究所）运输模型是线性规划诸多模型中较早引起人们关注的一类模型，由美运输模型是线性规划诸多模型中的特例，其约束方程组对应的系数矩阵具有特殊的结构，使得有可能找到比单纯形法更为简便的求解方式。运输问题的专门求解方法不仅适用于运输问题本身，还适用于其他相当多的应用问题（如指派问题），更使其得到人们的高度重视和深入的系统研究。运输模型是线性规划诸多模型中的特例，其约束方程组对应的系数矩

在经济建设中经常会碰到大宗物资的调运问题。如煤、铁、木材、粮食等大宗物资，在全国有若干生产基地，根据现已有的交通网络，应该如何制定调运方案，将这些物资运往各消费地点。1）“产地”——货物发出的地点2）“销地”——货物接收的地点3）“产量”——各产地的可供货量4）“销量”——各销地的需求数量在经济建设中经常会碰到大宗物资的调运问题。如【运输问题的描述】运输问题就是研究如何组织调运，在满足各销地需求的前提下，追求总的运费（或里程、时间等）达到最少？运输问题所建立的模型就称为运输模型。【运输问题的描述】5.1运输问题及其数学模型【例1】某饮料集团在国内有3个生产工厂，分布在城市

A1，A2，A3；其一级分销商有4个，分布在城市B1，B2，B3，

B4。现已知每月各生产工厂的产量、各分销商的需求量；以及从Ai到Bj的每吨饮料的运费cij（见下表）。5.1运输问题及其数学模型

销地产地B1B2B3B4产量A163255A275842A332973销量2314为发挥集团优势，公司需要统一筹划运销问题，求使运费最小的调运方案。销地B1B2B3B4产量A163255A275842解：建立该运输问题的LP模型如下解：建立该运输问题的LP模型如下运输模型解析课件运输问题的一般提法：

设某种物资有m个产地，其产量分别为；有n个销地，其销量分别为；从到的单位运价为。问应该如何组织调运才能使总的运费最少？运输问题的一般提法：设

为把这种物资从Ai运到Bj的数量，简称为Ai至Bj的运量；设z为总运费，则一般运输问题及其数学模型可以简洁地表示为下表这种形式，称为表格形式的一般运输模型，简称表式运输模型。p136设为把这种物资从Ai运到Bj的数量，简称p136表式运输模型

销地产地A1A2…Am产量a1a2…amB1B2…Bn销量b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn表式运输模型销地A1A2…Am产量a1a2…amB产销平衡产销平衡产大于销产大于销产小于销产小于销【运输模型系数矩阵】m行n行【运输模型系数矩阵】mn【讨论】运输模型系数矩阵的特征？[表面]任意一个运输模型系数矩阵同一个与之规模相当的普通LP模型的系数矩阵相比都大为简洁，且其中只含有0和1这两个元素，且0的个数远远多于1的个数，一般我们把这样的矩阵称为稀疏阵。[深层次]对任意产销平衡的运输模型来说，其系数阵的前m行之和等于后n行之和。意味着？【讨论】运输模型系数矩阵的特征？意味着？可以证明：平衡模型的系数阵和增广阵的秩均为m+n-1，这也意味着平衡模型的基本可行解所含基变量的个数必为m+n-1个。【结论】m+n-1可以证明：平衡模型的系数阵和增广阵的秩均为m+n-1，这也意【讨论】上述运输问题所建立的LP模型如果用传统的单纯形法进行求解会出现什么情况？【友情提示】1）表上作业法仅仅适用于产销平衡的运输问题

2）表上作业法基于一种作业表——“产销平衡及运价表”特征？5.2表上作业法【讨论】上述运输问题所建立的LP模型如果用传统的特征？5.2用单纯形法求解LP式运输模型，必须删掉一个函数约束，而且计算量很大，但表上作业法不必如此费力，而是另辟蹊径。表上作业法是一种专门求解运输问题的特殊方法，其实质仍是单纯形法，只是具体计算和术语有所区别。与一般的LP问题不同的是，平衡运输问题总是存在最优解。用单纯形法求解LP式运输模型，必须删掉一个函数约束，而且计算

销地产地B1B2B3B4产量A163255A275842A332973销量231410销地B1B2B3B4产量A163255A275842■表上作业法的基本思想及基本步骤【基本思想】类似于单纯形法，只是叫法不同而已，如基本

可行解称为“方案”；迭代称为“调整改进”等。【基本步骤】1）确定初始方案；

2）对初始方案进行最优性检验；

3）调整、改进非最优方案；

4）直至得到最优方案（惟一方案或多重方案）■表上作业法的基本思想及基本步骤【基本思想】类似于单纯形法运输问题求解思路确定初始方案（初始基本可行解）

输出最优方案改进调整（换基迭代）判断是否最优结果是否确定初始方案输出最优方案改进调整判断是否最优结果是否5.2.1初始方案的确定

确定初始方案的方法有很多，原理各不相同——左上角法（西北角法、阶梯法）最小元素法最大差额法Russell概算法5.2.1初始方案的确定确定初始方案的方法有很多，原理各销地产地B1B2B3B4产量A163255A275842A332973销量231410②左上角法销地B1B2B3B4产量A163255A275842A332最小元素指？最小元素法的基本思想？？最小元素法“最小运价”“就近运给”最小元素指？最小元素法的基本思想？？最小元素法“最小运价”“先给作业表中最小运价那格安排运量，然后划去该运价所在的行或列；继续这样做，每次总在表中剩余运价的最小元素那格确定运量，直至求出初始方案为止。先给作业表中最小运价那格安排运量，然后划去该运价所在的行或列销地产地B1B2B3B4产量A163255A275842A332973销量231410①③(0)②②②初始方案：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=38销地B1B2B3B4产量A163255A275842A332【结论】最小元素法确定初始方案的4条原则运量选择时必须遵循产、销量比较取其小的原则确定某格的运量后，其所在行或列其余格运量为0，并划去满足约束的行或列，同时满足只能划去其中之一中间遇到0运量也必须画上最后一个格产地、销地同时满足，同时划去【结论】最小元素法确定初始方案的4条原则运量选择时必须遵循产最小元素法确定的有效的初始方案满足——初始作业表中有m+n-1

个画圈数字（运量）画圈数字（运量）恰好符合产销平衡运输问题的约束条件作业表中不存在以画圈数字为顶点的闭回路【闭回路】从表中任一画圈数字所在格出发，沿水平或垂直方向前进，当碰到另一个画圈数字后，可沿原方向继续前进，也可以转90°继续前进，如此进行下去最终回到出发点。注意：用最小元素法得到的初始方案肯定不会形成闭回路！！！最小元素法确定的有效的初始方案满足——初始作业表中有m+销地产地B1B2B3B4产量A163255A275842A332973销量231410①②①①③②销地B1B2B3B4产量A163255A275842A332B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43B1B2B3B4B5A1X11X12A2X23X25A3X3最大差额法“差额”——行差和列差“最大差额”——两最小元素之差（正值）不能按最小运费就近供应，就考虑次小运费差额越大，说明当不能按最小运费调运时，运费增加的越多最大差额法5.2.2最优性检验确定初始方案后，就要对它进行最优性检验，即检验初始基本可行解对应的目标函数值是否达到最优。运输问题要求目标函数求最小值，故当检验数时，表示该方案为最优。计算检验数的方法有——A位势法B闭回路法5.2.2最优性检验1、位势法A两个位势量：产地的位势量；销地的位势量B两个基本公式：1）该公式仅仅适用于基变量所在格（基格）2）决策变量的检验数计算公式：1、位势法销地产地B1B2B3B4产量uiA162

321

52

50A2758422-1A330

23

973-3销量2314vj6525-2217105非基变量x12的检验数12=c12–u1–v2=-2，即让非基变量x12从0增到1，可使总运费减少2百元。销地B1B2B3B4产量uiA1632550A275842-2、闭回路法这里的闭回路是指以非基变量的格子为始点和终点，而其余顶点均为画圈数字（基变量）的一条封闭回路，用水平或者垂直线向前画，每碰到一数字格转90度后继续前进，直到回到始点。偶点（+）奇点（-）结论1：闭回路都是唯一的。结论2：任一非基变量的检验数都等于它的闭回路上所有偶点运价的总和与所有奇点的运价总和之差。2、闭回路法5.2.3非最优方案的调整当作业表中出现负检验数时，表明此方案仍不是最优方案，需要进行调整，调整时仍用闭回路法。5.2.3非最优方案的调整（1）进基变量的确定若同时有多个负检验数一样最小，则选其中最小运价所对应的那个进基。（2）离基变量的确定在进基变量的闭回路上，按确定离基变量，同时也确定了调整量t。若有多个奇点的运量值一样，则选其中最大运价所对应的那个离基。（3）非最优方案的调整所有偶点的运量+t所有奇点的运量-t（1）进基变量的确定x12进基最小调整量为2，即t=2，x11离基销地产地B1B2B3B4产量A1623x1221525A2758422A33023973销量2314+-+-x12进基销地B1B2B3B4产量A163255A27销地产地B1B2B3B4产量A16

321525A2758422A33

2

973销量2314

调整后新方案：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=34

221销地B1B2B3B4产量A163255A275842A3定理1(惟一最优解的判定定理)

如果在表上作业法得到的最终表中,非基变量的检验数全都大于零,则该运输问题存在惟一最优解。

定理2(多重最优解的判定定理)对于一个运输问题,在得到的第一个最优解的最终表中,若至少存在一个检验数为零的非基变量,并且在以这个非基变量为出发点的闭回路上,在需要减少运输量的顶点中,最小运量不等于零,那么该运输问题存在多重最优解。

运输问题的多重解定理1(惟一最优解的判定定理)

如果在表上作业法得到的最终表运输问题多重解B1B2B3B4产量A13113107A219284A3741059销量3656

运输问题多重解B1B2B3B4产量A13113107A2195.2.4产销不平衡问题的解法A产大于销

虚设销地（经济意义：贮存）B产小于销

虚设产地（经济意义：脱销）5.2.4产销不平衡问题的解法虚设的产地的产量或销地的销量等于产销量之差的绝对值，且其运价全部为0。用最小元素法确定初始方案时，尽管虚设产地或销地对应的运价为0，均为最小，但我们先不考虑它，先给有实际运输任务的其他产销地之间安排运量，这样处理往往能获得较好的初始方案，减少调整的次数（为什么？）。虚设的产地的产量或销地的销量等于产销量之差的绝对值，且其运价5.3运输模型的应用短缺资源的分配问题转运问题生产调度问题（***）5.3运输模型的应用这里所说的生产调度问题是指对某产品在一个总的计划周期内的某项既定总生产指标（总产量），应怎样分解到各个生产周期，才能既保证在总计划期内完成该项总生产指标，又能使总生产费用最少。这里所说的生产调度问题是指对某产品在一个总的计划周期内的某项[案例]拖拉机生产调度问题前进拖拉机厂与农机供销站签订了一项生产100台某种小型拖拉机的合同。按合同规定，该厂要在今后4个月的每月内各交付一定台数的拖拉机。为此，该厂生产计划科根据本厂实际情况列出了一个生产调度数据表。根据此表第二栏（生产能力）的数据，该厂能够提前完成合同总数，但生产出来的拖拉机若当月不交货，每台存储一个月，由于维修保养和积压资金等缘故，另需费用100元，问该厂应如何拟订最经济的生产进度？[案例]拖拉机生产调度问题月份合同规定交付台数/台生产能力/台单台成本/元115305000225355200335455100425205300合计100130月份合同规定生产能力/台单台成本/元11530500022512345/虚产量1505152530302M5253540353MM51520454MMM53020销量152535253012345/虚产量1505152530302M5253540第5章运输模型5.1运输问题及其数学模型5.2表上作业法5.2.1初始方案的确定5.2.2最优性检验5.2.3非最优方案的调整5.2.4产销不平衡问题的解法5.3运输模型的应用第5章运输模型5.1运输问题及其数学模型运输模型是线性规划诸多模型中较早引起人们关注的一类模型，由美国学者希奇柯克（Hitchcock，1941）和库普曼（Koopmans，1947）提出。中国——“图上作业法”（1958年）1975年康托洛维奇和库普曼因资源配置理论研究获得诺贝尔经济学奖（丹茨格）（24、12、4）（日内瓦国际应用系统分析研究所）运输模型是线性规划诸多模型中较早引起人们关注的一类模型，由美运输模型是线性规划诸多模型中的特例，其约束方程组对应的系数矩阵具有特殊的结构，使得有可能找到比单纯形法更为简便的求解方式。运输问题的专门求解方法不仅适用于运输问题本身，还适用于其他相当多的应用问题（如指派问题），更使其得到人们的高度重视和深入的系统研究。运输模型是线性规划诸多模型中的特例，其约束方程组对应的系数矩

在经济建设中经常会碰到大宗物资的调运问题。如煤、铁、木材、粮食等大宗物资，在全国有若干生产基地，根据现已有的交通网络，应该如何制定调运方案，将这些物资运往各消费地点。1）“产地”——货物发出的地点2）“销地”——货物接收的地点3）“产量”——各产地的可供货量4）“销量”——各销地的需求数量在经济建设中经常会碰到大宗物资的调运问题。如【运输问题的描述】运输问题就是研究如何组织调运，在满足各销地需求的前提下，追求总的运费（或里程、时间等）达到最少？运输问题所建立的模型就称为运输模型。【运输问题的描述】5.1运输问题及其数学模型【例1】某饮料集团在国内有3个生产工厂，分布在城市

A1，A2，A3；其一级分销商有4个，分布在城市B1，B2，B3，

B4。现已知每月各生产工厂的产量、各分销商的需求量；以及从Ai到Bj的每吨饮料的运费cij（见下表）。5.1运输问题及其数学模型

销地产地B1B2B3B4产量A163255A275842A332973销量2314为发挥集团优势，公司需要统一筹划运销问题，求使运费最小的调运方案。销地B1B2B3B4产量A163255A275842解：建立该运输问题的LP模型如下解：建立该运输问题的LP模型如下运输模型解析课件运输问题的一般提法：

设某种物资有m个产地，其产量分别为；有n个销地，其销量分别为；从到的单位运价为。问应该如何组织调运才能使总的运费最少？运输问题的一般提法：设

为把这种物资从Ai运到Bj的数量，简称为Ai至Bj的运量；设z为总运费，则一般运输问题及其数学模型可以简洁地表示为下表这种形式，称为表格形式的一般运输模型，简称表式运输模型。p136设为把这种物资从Ai运到Bj的数量，简称p136表式运输模型

销地产地A1A2…Am产量a1a2…amB1B2…Bn销量b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn表式运输模型销地A1A2…Am产量a1a2…amB产销平衡产销平衡产大于销产大于销产小于销产小于销【运输模型系数矩阵】m行n行【运输模型系数矩阵】mn【讨论】运输模型系数矩阵的特征？[表面]任意一个运输模型系数矩阵同一个与之规模相当的普通LP模型的系数矩阵相比都大为简洁，且其中只含有0和1这两个元素，且0的个数远远多于1的个数，一般我们把这样的矩阵称为稀疏阵。[深层次]对任意产销平衡的运输模型来说，其系数阵的前m行之和等于后n行之和。意味着？【讨论】运输模型系数矩阵的特征？意味着？可以证明：平衡模型的系数阵和增广阵的秩均为m+n-1，这也意味着平衡模型的基本可行解所含基变量的个数必为m+n-1个。【结论】m+n-1可以证明：平衡模型的系数阵和增广阵的秩均为m+n-1，这也意【讨论】上述运输问题所建立的LP模型如果用传统的单纯形法进行求解会出现什么情况？【友情提示】1）表上作业法仅仅适用于产销平衡的运输问题

2）表上作业法基于一种作业表——“产销平衡及运价表”特征？5.2表上作业法【讨论】上述运输问题所建立的LP模型如果用传统的特征？5.2用单纯形法求解LP式运输模型，必须删掉一个函数约束，而且计算量很大，但表上作业法不必如此费力，而是另辟蹊径。表上作业法是一种专门求解运输问题的特殊方法，其实质仍是单纯形法，只是具体计算和术语有所区别。与一般的LP问题不同的是，平衡运输问题总是存在最优解。用单纯形法求解LP式运输模型，必须删掉一个函数约束，而且计算

销地产地B1B2B3B4产量A163255A275842A332973销量231410销地B1B2B3B4产量A163255A275842■表上作业法的基本思想及基本步骤【基本思想】类似于单纯形法，只是叫法不同而已，如基本

可行解称为“方案”；迭代称为“调整改进”等。【基本步骤】1）确定初始方案；

2）对初始方案进行最优性检验；

3）调整、改进非最优方案；

4）直至得到最优方案（惟一方案或多重方案）■表上作业法的基本思想及基本步骤【基本思想】类似于单纯形法运输问题求解思路确定初始方案（初始基本可行解）

输出最优方案改进调整（换基迭代）判断是否最优结果是否确定初始方案输出最优方案改进调整判断是否最优结果是否5.2.1初始方案的确定

确定初始方案的方法有很多，原理各不相同——左上角法（西北角法、阶梯法）最小元素法最大差额法Russell概算法5.2.1初始方案的确定确定初始方案的方法有很多，原理各销地产地B1B2B3B4产量A163255A275842A332973销量231410②左上角法销地B1B2B3B4产量A163255A275842A332最小元素指？最小元素法的基本思想？？最小元素法“最小运价”“就近运给”最小元素指？最小元素法的基本思想？？最小元素法“最小运价”“先给作业表中最小运价那格安排运量，然后划去该运价所在的行或列；继续这样做，每次总在表中剩余运价的最小元素那格确定运量，直至求出初始方案为止。先给作业表中最小运价那格安排运量，然后划去该运价所在的行或列销地产地B1B2B3B4产量A163255A275842A332973销量231410①③(0)②②②初始方案：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=38销地B1B2B3B4产量A163255A275842A332【结论】最小元素法确定初始方案的4条原则运量选择时必须遵循产、销量比较取其小的原则确定某格的运量后，其所在行或列其余格运量为0，并划去满足约束的行或列，同时满足只能划去其中之一中间遇到0运量也必须画上最后一个格产地、销地同时满足，同时划去【结论】最小元素法确定初始方案的4条原则运量选择时必须遵循产最小元素法确定的有效的初始方案满足——初始作业表中有m+n-1

个画圈数字（运量）画圈数字（运量）恰好符合产销平衡运输问题的约束条件作业表中不存在以画圈数字为顶点的闭回路【闭回路】从表中任一画圈数字所在格出发，沿水平或垂直方向前进，当碰到另一个画圈数字后，可沿原方向继续前进，也可以转90°继续前进，如此进行下去最终回到出发点。注意：用最小元素法得到的初始方案肯定不会形成闭回路！！！最小元素法确定的有效的初始方案满足——初始作业表中有m+销地产地B1B2B3B4产量A163255A275842A332973销量231410①②①①③②销地B1B2B3B4产量A163255A275842A332B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43B1B2B3B4B5A1X11X12A2X23X25A3X3最大差额法“差额”——行差和列差“最大差额”——两最小元素之差（正值）不能按最小运费就近供应，就考虑次小运费差额越大，说明当不能按最小运费调运时，运费增加的越多最大差额法5.2.2最优性检验确定初始方案后，就要对它进行最优性检验，即检验初始基本可行解对应的目标函数值是否达到最优。运输问题要求目标函数求最小值，故当检验数时，表示该方案为最优。计算检验数的方法有——A位势法B闭回路法5.2.2最优性检验1、位势法A两个位势量：产地的位势量；销地的位势量B两个基本公式：1）该公式仅仅适用于基变量所在格（基格）2）决策变量的检验数计算公式：1、位势法销地产地B1B2B3B4产量uiA162

321

52

50A2758422-1A330

23

973-3销量2314vj6525-2217105非基变量x12的检验数12=c12–u1–v2=-2，即让非基变量x12从0增到1，可使总运费减少2百元。销地B1B2B3B4产量uiA1632550A275842-2、闭回路法这里的闭回路是指以非基变量的格子为始点和终点，而其余顶点均为画圈数字（基变量）的一条封闭回路，用水平或者垂直线向前画，每碰到一数字格转90度后继续前进，直到回到始点。偶点（+）奇点（-）结论1：闭回路都是唯一的。结论2：任一非基变量的检验数都等于它的闭回路上所有偶点运价的总和与所有奇点的运价总和之差。2、闭回路法5.2.3非最优方案的调整当作业表中出现负检验数时，表明此方案仍不是最优方案，需要进行调整，调整时仍用闭回路法。5.2.3非最优方案的调整（1）进基变量的确定若同时有多个负检验数一样最小，则选其中最小运价所对应的那个进基。（2）离基变量的确定在进基变量的闭回路上，按确定离基变量，同时也确定了调整量t。若有多个奇点的运量值一样，则选其中最大运价所对应的那个离基。（3）非最优方案的调整所有偶点的运量+t所有奇点的运量-t（1）进基变量的确定x12进基最小调整量为2，即t=2，x11离基销地产地B1B2B3B4产量A1623x1221525A2758422A33023973销量2314+-+-x12进基销地B1B2B3B4产量A163255A27销地产地B1B2B3B4产量A16

321525A2758422A33

2

973销量2314

调整后新方案：x12=2,x13=1,x14