课程名称：《运筹学》第_11_讲次运输问题的模型与性质；表上作业法授课题目本讲目的要求及重点难点：【目的要求】通过本讲课程的学习，理解并掌握运输问题的模型与性质，会用表上作业法求解。[重点及难点】表上作业法内容[本讲课程的引入]前两章讨论了一般线性规划问题的求解方法，但在实际工作中，往往碰到有些线性规划问题，它们的约束方程组的系数矩阵具有特殊的结构，这就有可能找到比单纯形法更为简便的求解方法。从而可节约计算时间和费用。本章讨论的运输问题就是属于这样一类特殊的线性规划问题。[本讲课程的内容]一、运输问题的数学模型在经济建设中，经常碰到大宗物资调运问题。如煤、钢材、木材、：粮食等等物资，在全国有如若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而总运费要小。这类问题可用以下数学语言描述。已知有m个生产地点Ai，i=1，2，，m，可供应某种物资，其供应量（产量）分别为ai，i=1，2，，m；有n个销地Bj，j=1，2，，n，其需要量分别为bj，j=1,2，,n；从Ai到Bj运输单位物资的运价（单价）为cij，这些数据可汇总于产销平衡表和单位运价表中。若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求总运费最小的调运方案，可用以下数学模型表示：
课程名称：《运筹学》 第 11 讲次 授课题目 运输问题的模型与性质；表上作业法 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，理解并掌握运输问题的模型与性质，会用表上作业法 求解。 [重点及难点] 表上作业法 内 容 [本讲课程的引入] 前两章讨论了一般线性规划问题的求解方法，但在实际工作中，往往碰到有些线性 规划问题，它们的约束方程组的系数矩阵具有特殊的结构，这就有可能找到比单纯形法 更为简便的求解方法。从而可节约计算时间和费用。本章讨论的运输问题就是属于这样 一类特殊的线性规划问题。 [本讲课程的内容] 一、 运输问题的数学模型 在经济建设中，经常碰到大宗物资调运问题。如煤、钢材、木材、；粮食等等物资，在全国有 如若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而总运费 要小。这类问题可用以下数学语言描述。 已知有 m 个生产地点 Ai ，i ＝ 1，2，.，m ，可供应某种物资，其供应量（产量）分别为 ai ，i ＝ 1，2，.，m ；有 n 个销地 Bj ，j ＝ 1，2，.，n ，其需要量分别为 bj ，j ＝ 1，2，.， n ；从 Ai 到 Bj 运输单位物资的运价（单价）为 cij，这些数据可汇总于产销平衡表和单位运价表中。 若用 xij 表示从 Ai 到 Bj 的运量，那么在产销平衡的条件下，要求总运费最小的调运方案，可 用以下数学模型表示：
内容ZZminz =Cij Xiji=1j=1mZj=b，j=l,2，,ni=1nZ xij = ai,i=1,2,,mj=1xij≥0这就是运输问题的数学模型，它包含mXn个变量，m十n个约束方程。其系数矩阵的结构比较松散，矩阵中对应变量xij的系数列向量Pij=ei+em+j。对产销平衡的运输问题，由于存在以下关系：nmmmnn≥ bj=M(MZ(MXij) =Zxj）=aij=1j=1i=1i=1i=1 j=1所以模型最多只有m十n一1个独立约束方程。即系数矩阵的秩≤m十n一1。例1、某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示销地BiBsB4Bz产量产地37A131110A19284As71059435销量6620（产销平衡)问应如何调运，可使得总运输费最小？解：这是一个产销平衡的运输问题，设xij为从产地Ai运往销地Bj的运输量（i=1，2，3;j=1,2,3,4)所以此运输问题的线性规划模型如下：
内 容 min z ＝ ∑ ∑ cij xij ∑ xij ＝ bj ，j ＝ 1，2，.，n ∑ xij ＝ ai ，i ＝ 1，2，.，m xij ≥ 0 这就是运输问题的数学模型，它包含 m×n 个变量，m＋n 个约束方程。其系数矩阵的结构 比较松散，矩阵中对应变量 xij 的系数列向量 Pij = ei ＋ e m+j 。 对产销平衡的运输问题，由于存在以下关系： ∑ bj = ∑（∑ xij）= ∑（∑ xij）= ∑ ai 所以模型最多只有 m＋n－1 个独立约束方程。即系数矩阵的秩≤m＋n－1。 例 1 某公司从三个产地 A1、A2、A3 将物品运往四个销地 B1、B2、B3、B4，各产地的 产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示 问应如何调运，可使得总运输费最小? 解： 这是一个产销平衡的运输问题，设 xij 为从产地 Ai 运往销地 Bj 的运输量（i = 1，2， 3； j = 1，2，3，4） 所以此运输问题的线性规划模型如下： 销地 产地 B1 B2 B3 B4 产量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量 3 6 5 6 20（产销平 衡） m m m j=1 j=1 i=1 i=1 j=1 i=1 n n n i=1 j=1 m i=1 n j=1
内容Minf=3x11+11x12+3x13+ 10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34s.t.x11+x12+x13+x14=7x21 + x22+ x23 + x24 = 4x31 + x32+ x33 + x24 = 9xl1 + x21 +x31 = 3x12+x22+x32= 6x13+x23+x33=5x14 + x24 +x34= 6xj≥0(i=1、2、3;j=1、2、3、4)其系数矩阵为：011000000A=100OU00UUU共有m+n行，分别表示产地和销地；有mn列分别表示各变量；每列只有两个1，其余为0。运输问题求解的有关概念1、基变量的特点（1）基变量共有m+n-1个（2）产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路定义4.1在表4-5中决策变量格凡是能够排列成下列形式xab, xac,xdc, xde,..,xst, xsb或xab, xcb,xcd, xed,,xst, xat其中，a,d..,s各不相同；b,c..,t各不相同。我们称之为变量集合的一个闭回路，并将上式中的变量称为这个闭回路的顶点
内 容 Min f = 3x11+ 11x12+ 3x13+ 10x14 + x21+ 9x22 + 2x23+ 8x24 + 7x31+ 4x32+ 10x33+ 5x34 s.t. x11+ x12 + x13 + x14 = 7 x21 + x22+ x23 + x24 = 4 x31 + x32+ x33 + x24 = 9 x11 + x21 + x31 = 3 x12 + x22 + x32 = 6 x13 + x23 + x33 = 5 x14 + x24 + x34 = 6 xij ≥ 0 ( i = 1、2、3；j = 1、2、3、4) 其系数矩阵为 ： 共有 m+n 行，分别表示产地和销地；有 mn 列分别表示各变量；每列只有两个 1，其余 为 0 。 运输问题求解的有关概念 1、基变量的特点 （1）基变量共有 m + n -1 个 （2）产销平衡运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路 定义 4.1 在表 4-5 中决策变量格凡是能够排列成下列形式 xab, xac, xdc，xde,., xst, xsb 或 xab, xcb, xcd, xed,., xst, xat 其中，a,d,.,s 各不相同；b,c,.,t 各不相同。我们称之为变量集合的一个闭回路，并将上 式中的变量称为这个闭回路的顶点。 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 A
内容根据定义可以看出闭回路的一些明显特点：：（1）闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的：（2）闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。表上作业法是单纯形法在求解运输问题时的一种简化方法。其实质是单纯形法。但具体计算和术语有所不同。可归纳为：（1）找出初始基可行解。即在（mXn）产销平衡表上给出m十n一1个数字格。（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。（3）确定换入变量和换出变量，在表上用闭回路法调整，找到新的基可行解。重复（2)，（3）直到得到最优解为止。以上运算都可以在表上完成。一、初始基本可行解的确定①在运输问题求解作业数据表中任选一个单元格xij（Ai行Bj列交叉位置上的格），令xij =min (ai, bj)即考虑从Ai向Bj的最大运输量（使行或列在允许的范围内尽量饱和，即使一个约束方程得以满足)，填入xij的相应位置；②从ai或bj中分别减去xij的值，即调整Ai的拥有量及Bj的需求量；③若ai=0，则划去对应的行（把拥有的量全部运走），若bj=0则划去对应的列（把需要的量全部运来)，且每次只划去一行或一列（即每次要去掉且只去掉一个约束)；若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则，在剩下的运输平衡表中选下一个变量，转②。按照上述方法所产生的一组变量的取值将满足下面条件：①所得的变量均为非负，且变量总数恰好为m+n-1个②所有的约束条件均得到满足：①所得的变量不构成闭回路。因此，根据定理4.1及其推论，所得的解一定是运输问题的基本可行解。下面通过例子说明表上作业法的计算步骤
内 容 根据定义可以看出闭回路的一些明显特点:： （1）闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的； （2） 闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。 表上作业法是单纯形法在求解运输问题时的一种简化方法。其实质是单纯形法。但具体计 算和术语有所不同。可归纳为： （1）找出初始基可行解。即在（m×n）产销平衡表上给出 m＋n－1 个数字格。 （2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解。如已是 最优解，则停止计算，否则转到下一步。 （3）确定换入变量和换出变量，在表上用闭回路法调整，找到新的基可行解。 重复（2），（3）直到得到最优解为止。 以上运算都可以在表上完成。 一、初始基本可行解的确定 ① 在运输问题求解作业数据表中任选一个单元格 xij ( Ai 行 Bj 列交叉位置上的格)，令 xij = min { ai , bj } 即考虑从 Ai 向 Bj 的最大运输量(使行或列在允许的范围内尽量饱和，即使一个约束方程 得以满足)，填入 xij 的相应位置； ② 从 ai 或 bj 中分别减去 xij 的值，即调整 Ai 的拥有量及 Bj 的需求量； ③ 若 ai = 0，则划去对应的行（把拥有的量全部运走），若 bj = 0 则划去对应的列（把需 要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）； ④ 若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则，在剩 下的运输平衡表中选下一个变量，转②。 按照上述方法所产生的一组变量的取值将满足下面条件： ① 所得的变量均为非负，且变量总数恰好为 m + n – 1 个； ② 所有的约束条件均得到满足； ① 所得的变量不构成闭回路。 因此，根据定理 4.1 及其推论，所得的解一定是运输问题的基本可行解。 下面通过例子说明表上作业法的计算步骤
内容例1某公司经销甲产品。它下设三个加工厂。每日的产量为：A1一7吨，A2一4吨，A3—9吨。该公司把这些产品分别运往四个销售点。各销售点每日销售量为：B1—3吨，B2—6吨，B3一5吨，B4一6吨。已知从各工厂到各销售点的单位产品的运价为表3-1所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总运费为最少解先画出此问题的产销平衡表和单位运价表，见表3-1，表3-2。表3-1产销平衡表B1B2B3B4产量A174A29A35销量366表3-2单位运价表B1B2B3B4A1311310A2192874A3105(1）最小元素法此方法的基本思想是就近供应，即从单位运价表中逐次地挑选最小元素，并比较其对应的产量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划m十n条直线。但当表中只剩下一个元素时，这时当在产销平衡表上填入这个数字时，在运价表上要同时划去一行和一列。此时运价表上的所有元素都划去了，相应地在产销平衡表上填入了m+1个数字。即给出了m+n1个基变量的值，且这m十n一1个基变量对应的系数列向量是线性独立的。因此用最小元素法给出的初始解是运输问题的基可行解
内 容 例 1 某公司经销甲产品。它下设三个加工厂。每日的产量为：A1—7 吨，A2—4 吨， A3—9 吨。该公司把这些产品分别运往四个销售点。各销售点每日销售量为：B1—3 吨，B2—6 吨，B3—5 吨，B4—6 吨。已知从各工厂到各销售点的单位产品的运价为表 3-1 所示。问该公司 应如何调运产品，在满足各销售点的需要量的前提下，使总运费为最少。 解 先画出此问题的产销平衡表和单位运价表，见表 3-1，表 3-2。 表 3-1 产销平衡表 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 表 3-2 单位运价表 B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5 (1) 最小元素法 此方法的基本思想是就近供应，即从单位运价表中逐次地挑选最小元素，并比较其对应的 产量和销量。当产大于销，划去该元素所在列；当产小于销，划去该元素所在行。然后在未划 去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表 上就划去一行或一列。表中共有 m 行 n 列，总共可划 m＋n 条直线。但当表中只剩下一个元素 时，这时当在产销平衡表上填入这个数字时，在运价表上要同时划去一行和一列。此时运价表 上的所有元素都划去了，相应地在产销平衡表上填入了 m ＋ n — 1 个数字。即给出了 m ＋ n — 1 个基变量的值，且这 m ＋ n — 1 个基变量对应的系数列向量是线性独立的。因此用最小 元素法给出的初始解是运输问题的基可行解