运筹学教案

第一讲 绪论

一、运筹学概况

在20 世纪30 年代末, 称之为“运用研究”( oper -ational research ),在英、美的军队中成立了一些专门小组, 开展了护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时, 如何使船队损失最少的问题的研究:

1、研究了反潜深水炸弹的合理爆炸深度后, 使德国潜艇被摧毁数增加到400% ; 2、研究了船只在受敌机攻击时, 提出了大船应急转向和小船应缓慢转向的逃避方法。 3、研究结果使船只在受敌机攻击时, 中弹数由47%降到29%。

到20 世纪60 年代, 除军事方面的应用研究以外, 相继在工业、农业、经济和社会问题等各领域都有应用. 并形成了运筹学的许多分支。如数学规划(线性规划、非线性规则、整数规划、目标规划、动态规划、随机规划等) 、图论与网络、排队论( 随机服务系统理论) 、存储论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等。

在20 世纪50 年代中期钱学森、许国志等教授将运筹学由西方引入我国, 并结合我国的特点在国内推广应用

二、运筹学的含义

在资源不足的情况下，如何最好地分配资源，为决策者提供最佳解决方案的一门应用性学科。

三、运筹学的特点

是一门以数学为主要工具、寻求各种实际问题最优解决方案的学科； 是从系统的角度，用科学方法研究寻求整体行、全局性的最优解决方案； 是一门实践性和应用性强烈的学科； 是一门多学科交叉的学科；

四、运筹学的应用

1、市场销售。主要应用在广告预算和媒介的选择、竞争性定价、新产品开发、销售计划的制定等方面。如美国杜邦公司、通用电力公司等；

2、生产计划。在总体计划方面主要用于总体确定生产、存储和劳动力的配合, 以适应波动的需求计划；生产作业计划、日程表的编排等；还有在合理下料、配料问题、物料管理等方面的应用。

3、库存管理。主要应用于多种物资库存量的管理, 确定某些设备的能力或容量, 如停车场的大小、新增发电设备的容量大小、电子计算机的内存量、合理的水库容量等。

4、运输问题。如航班、飞行机组人员服务时间安排、汽车调度计划、公路网的设计和分析, 市内公共汽车路线的选择和行车时刻表的安排, 出租汽车的调度和停车场的设立等；

5、财政和会计。这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是统计分析、数学规划、决策分析。此外还有盈亏点分析法、价值分析法等。

6、人事管理。这里涉及六个方面, 首先是人员的获得和需求估计; 第二是人才的开发, 即进行教育和训练; 第三是人员的分配, 主要是各种指派问题; 第四是各类人员的合理利用问题;

第五是人才的评价; 第六是工资和津贴的确定等。

7、设备维修、更新和可靠性、项目选择和评价。

8、工程的优化设计。这在建筑、电子、光学、机械和化工等领域都有应用。

9、计算机和信息系统。可将运筹学用于计算机的内存分配, 研究不同排队规则对磁盘工作性能的影响。

10、城市管理。各种紧急服务系统的设计和运用, 如救火站、救护车、警车等分布点的设立。美国曾用排队论方法来确定纽约市紧急电话站的值班人数。加拿大曾研究一城市的警车的配置和负责范围, 出事故后警车应走的路线等。此外有城市垃圾的清扫、搬运和处理; 城市供水和污水处理系统的规划

五、运筹学的解题步骤

①提出问题；②搜集数据、③建立模型；④求解；⑤验证；⑥实施

第二讲 线性规划

物流运筹学的研究对象是经济管理活动中的决策优化问题。一般说来，资源与需求间存在着矛盾。为解决这些矛盾，可从两个方面入手：一、努力增加资源；二、充分合理使用资源。物流运筹学便是通过合理地选择、使用资源，使物流效益达到最大的一门科学。为此，须解决三方面的问题：

1、存在若干待选措施、方案 2、要有衡量好坏的评价标准

3、要给出系统中不同因素间的相互关系，如不同资源的配比等。

一般说来，要对上面三个方面都进行量化是很困难的。为了简化问题，决策者常使用各种简单函数来近似复杂的数量描述。线性函数便是最简单的一种。

一、问题的提出

例1：原料混合

已知有浓度为75%和95%的硫酸，如何得到浓度为85%的硫酸？ 例2：生产计划安排

某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品, 已知生产单位产品所需的设备台时及A 、B 两种原材料的消耗, 如表1-1 所示。

该工厂每生产一件产品Ⅰ可获利2 元, 每生产一件产品Ⅱ可获利3 元, 问应如何安排计划使该工厂获利最多?

例3：合理利用线材问题

现要做100 套钢架, 每套用长为2. 9m, 2. 1m 和1. 5m 的元钢各一根。已知原料长7. 4m, 问应如何下料, 使用的原材料最省。

例4： 配料问题

某工厂要用三种原材料C 、P 、H 混合调配出三种不同规格的产品A 、B 、D 。已知产品的规格要求, 产品单价, 每天能供应的原材料数量及原材料单价, 分别见表1-2和表1-3。该厂应如何安排生产, 使利润收入为最大?

表1-2 表1-3

二、线性规划问题的特点

从上述问题的数学模型中得到线性规划问题的一般特点：

1、要求解的问题的目标或预期目标能用某种效益指标来衡量，并且该目标可以用线性函数来描述；

2、达到这个目标存在多种解决方案；

3、目标要受到一定的资源约束，这些约束条件可以用线性函数描述出来； 在现有各种资源条件的限制下，如何确定方案，使预设目标达到最优；

三、线性规划（LP, Linear programming ）的含义

对于求解的一组变量，使之既满足线性约束条件，又使具有线性表达式的目标函数取得最大值或最小值的一类最优化问题，称之为线性规划问题，简称线性规划。

四、线性规划模型的一般形式

max(或min) z =∑c j x j

j =1

n

⎧n

（或=，≥）b j ; i =1,2,..., m ⎪∑a ij x j ≤

st . ⎨j =1

1、决策变量：问题中要确定的变量；

2、目标函数：决策变量的函数，max 或min ；

3、约束条件：决策变量取值时受到的资源约束，= 或 ≤ 或 ≥；约束条件和目标函数均保持线性关系。 五、线性规划应用案例

1、配料问题

红星动物园饲养了一批珍贵动物。在这些动物的生长过程中，蛋白质、维生素、脂肪和纤维素4种营养成分特别重要。每只动物每天必须至少摄取500g 蛋白质、6g 维生素、10g 脂肪和8g 维生素。动物园准备购入玉米、燕麦、青稞、土豆等4中饲料以帮助满足这些需要。已知每种饲料每千克所含的营养成分和饲料的单价如表1-4所示。如果你是该动物园的管理员，请表述一个可以用最小成本来满足这些动物正常生长的营养方案。

表

1-4

2 配料问题

某糖果厂用原料A,B,C 加工成三种不同牌号的糖果甲，乙，丙。已知某种牌号糖果中A,B,C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下。问该厂每月生产这三种牌号糖果各多少kg ，使其获利最大。

表

1-5

3、劳动力调度问题

某著名景点，因每天游客的流量不同，因此每天所需要提供的导游服务也不尽相同。经过统计分析发现，景点对自有导游的需求量如下表所示。按照规定，导游每周工作五天后，连续休息两天。问应如何安排导游的作息，既能满足工作需要，又使雇佣的导游人数最少？

表

1-6

4、劳动力安排问题

某医院护士值班班次、每班工作时间及各班所需护士数如下表。每班护士值班开始时向病房报到，若护士上班后连续工作8h ，该医院最少需要多少护士，以满足轮班需要。

表1-7

六、线性规划的求解

1、图解法--仅适用于两个变量 （1）求解步骤：

①建立直角坐标系； ②找出可行域；

③图解目标函数和寻求最优解。 （2）图解法举例

max z =2x 1+x 2⎧5x 2≤15

⎪6x +2x ≤24⎪12⎨

⎪x 1+x 2≤5⎪⎩x 1, x 2≥0

min z =6x 1+4x 2⎧2x 1+x 2≥1

⎪

st . ⎨3x 1+4x 2≥1. 5⎪x , x ≥0⎩12

（3）重要结论：

①解的类型：唯一解、多重解、无界解、无可行解； ②当存在可行解时，其解的可行域一定是凸边形；

③当存在唯一最优解时，最优解一定在可行域的某定点上得到； ④存在多重解时，则有两个顶点及其连线上的一切点均取得最优解。 2、线性规划模型标准化 （1）线性规划的一般形式：

max(min)z =c 1x 1+c 2x 2+... +c n x n ⎧a 11x 1+a 12x 2+... +a 1n x n ≤(=, ≥) b 1 ⎪a x +a x +... +a x ≤(=, ≥) b 2112222n n 2⎪⎪

.......... .. ⎨

⎪a x +a x +... +a x ≤(=, ≥) b

mn n m

⎪m 11m 22⎪ ⎩x 1, x 2,..., x n ≥0

（2）线性规划的标准形式：

max z =c 1x 1+c 2x 2+... +c n x n ⎧a 11x 1+a 12x 2+... +a 1n x n =b 1 ⎪a x +a x +... +a x =b 2112222n n 2⎪⎪

.......... .. ⎨

⎪a x +a x +... +a x =b

mn n m

⎪m 11m 22⎪ ⎩x 1, x 2,..., x n ≥0

标准型也常写成向量形式：

max z =C T X

⎧AX =b

⎨

X ≥0⎩

⎛11121n ⎫⎛c 1⎫x 1⎫⎛ ⎪ ⎪， ⎪， a 21 a 22 ... a 2n ⎪ x 2⎪ c 2⎪ A = C = ⎪X = ⎪.......... .. ⎪:: a a ... a ⎪⎪ c ⎪⎪ x ⎪⎪

⎝m 1m 2mn ⎭⎝n ⎭⎝n ⎭

a a ... a

⎛b 1⎫

⎪

， b 2⎪ b = ⎪

: b ⎪⎪⎝m ⎭

（3）线性规划标准化的特点

①目标要求化为极大化max ； ②约束条件均为等式形式：

当约束方程为“≤”不等式时，则在不等式的左端加入一个非负的松弛变量； 当约束方程为“≥” 不等式是，则在不等式的左端减去一个非负的松弛变量； ③决策变量都为非负数；

' ' ' ' ' '

若存在取值无约束的变量x k ，可令x k =x k ，其中x k -x k , x k ≥0。

④右端常数均为非负数；

（4）将下面线性规划化为标准型

min z =x 1-2x 2+3x 3

⎧x 1+x 2+ x 3≤7 ⎪x -x + x ≥2 ⎪123

⎨，

⎪3x 1-x 2-2x 3=-5 ⎪x 1, x 2≥0 ⎩

3、单纯形法---适用于标准形式

（1）基本概念

max z =2x 1-5x 2+3x 3⎧x 1+2x 2+ x 3≥17 ⎪2x -3x + x ≤2 ⎪123

⎨

⎪5x 1-6x 2-x 3=-5 ⎪⎩x 1, x 3≥0, x 2

max z =C T X

⎧AX =b

⎨

⎩X ≥0

基：A 中m 个线性无关的列向量称为基。基中的每个列向量称为基向量, 其它为非基向量。若基为单位矩阵，则称为标准基。

基变量：与基向量对应的变量。 非基变量：与非基向量对应的变量。

基解：若B 为A 中的一个基，则其将决策变量分为基变量和非基变量。令所有非基变量等于0，求解A x =b ，得X =X 0，则X 0为A x =b 关于基B 的基解（由定义可知，一个基对应一个基解）。

基可行解: 若X 0还满足X ≥0的要求，则称X 0为关于基B 的基可行解。

最优解：满足目标函数要求的基可行解，成为最优解。最优解对应的基，成为最优基。

退化基可行解好退化基：基可行解中存在零值的基变量，则称该基可行解为退化的基可行解。退化的基可行解对应的基，成为退化基。

min z =5x 1-2x 2+3x 3+2x 4

（2）认识基可行解 ：

⎧x 1+2x 2+3x 3+4x 4=7

⎪

s . t . ⎨2x 1+2x 2+x 3+2x 4=3⎪x ≥0, j =1, 2,... 4⎩j

①如何判定可行域C 中的点是顶点：对任何的X 1∈K, X 2∈K, X 1≠X 2及任意实数α∈(0,1)，都不会使X =αX 1+(1-α)X 2, 则称X ∈K 为K 的顶点。 ②线性规划问题的每个基可行解对应于可行域的一个顶点； ③若线性规划问题有最优解，一定存在一个基可行解是最优解。 （4）单纯形法的求解步骤

max z =CX

⎧AX =b

⎨

⎩X ≥0

设可行基B =(P和X = (X B , X N ) T 1, P 2,..., P n ) ，并记作A =(B,N), C =(CB , C N ) 经计算得到目标函数：Z =C B B b +

-1

j =m +1

∑σ

n

j

X j ，其中σj =C j -C B B -1P j , j =m +1

例：min z =x 1+x 2+2x 3+5x 4

-2x 3+x 4=1 ⎧x 1

⎪

⎨x 1+x 2 + x 3 =4

⎪x , x , x , x ≥0 ⎩1234

为什么最后一行是“-C ”？

j

这是因为判别数 中有 。由于按公式手工计算判别数并不方便，因此我们这里提供一种利用行变换来计算判别数的方法：

σj =C T αj -c j B

-c

利用行变换将最后行所有基变量的价格系数变为0，则最后行由-C 变为判别数。这是因为：

对于基变量来说（即而

-c j j =1,..., m ）

，要使得所有变为c

0，须在最后行加上j 。

c j =C T αj B

，因此最后行基变量系数变为

C T αj -c j B

。

而对于非基变量来说（即

-c j j =m +1,..., n ）

，行变换的同时，由也跟着变成了

C T αj -c j B

T

C b ，即成了判别数；相应

项增加了B 。

T

X =[1, 3, 0, 0]此时判别数已全部≤0 ，故得最优解。最优解为，最优值为4 。

由于非基变量取值为0，b 列其实就是基变量的取值。 对于换入列向量来说，由于线性规划标准型中已规定b

≥0，而选主元时选的是比值最小的

那个分量，因此将该列其它分量化为0时，右端项不会出现负数。因此，新得到的基本解一

定是可行的。

由此，总结单纯形算法步骤如下：

（1）选择单位阵为基，构造初始单纯形表

I X B + N X N = b

T

-C T X -C B B N X N =-z

（2）通过行变换将所有基变量价格系数化为0，得判别数；

T

X=0C b X =b N （3）当所有判别数≤0时，得最优解B ，，最优值为B ；当存在判

别数>0时，选判别数>0的最小下标列进基；

（4）进基列向量化为单位列向量，主元选定具有最小比值的分量（若比值相同，选最小下标分量）；若存在

使目标函数任意减小的可行解，即线性规划解无界（无最优解）。 例：用单纯形法求解下列线性规划

max

σj *>0

a ij *≤0(i =1, 2,..., m )

，但其所有分量，那么线性规划存在可

z =x 1+x 2

⎧-2x 1+x 2≤4⎪

⎨ x 1-x 2≤2 ⎪x , x ≥0 ⎩12

作业：

1 用单纯形法求解下列线性规划

z =2x 1+3x 2 m a x

⎧x 1+2x 2≤8⎪x ≤4⎪1

⎨

x 2≤3⎪ ⎪⎩x 1, x 2≥0

（清华P30：最优解为[4, 2, 0, 0, 4]，最优值为14）

4、大M 法

在一个线性规划问题的约束条件中加进人工变量后, 要求人工变量对目标函数取值不受影响, 为此假定人工变量在目标函数中的系数为( - M) ( M 为任意大的正数) , 这样目标函数要实现最大化时, 必须把人工变量从基变量换出。否则目标函数不可能实现最大化。

松弛变量：表示未被充分利用的资源或超出的资源数，尚未转化为价值和利润，在目标函数中系数为0。

T

例8 现有线性规划问题

min z =-3x 1+x 2+x 3

⎧x 1-2x 2+x 3≤11⎪-4x +x +2x ≥3

123 ⎪⎨

⎪-2x 1+x 3=1⎪⎩x 1-3≥0

解：将上述问题化成标准形式，其中x 4, x 5为松弛变量

max z =3x 1-x 2-x 3+0x 4+0x 5

⎧x 1-2x 2+x 3+x 4=11⎪ ⎪-4x 1+x 2+2x 3-x 5=3⎨

⎪-2x 1+x 3=1⎪⎩x 1-5≥0

系数矩阵中不存在E ，为了构建单位阵，在标准形式中加入人工变量x 6 , x 7，变成：

max z =3x 1-x 2-x 3+0x 4+0x 5-Mx 6-Mx 7

⎧x 1-2x 2+x 3+x 4=11⎪ ⎪-4x 1+x 2+2x 3-x 5+x 6=3⎨

⎪-2x 1+x 3+x 7=1⎪⎩x 1-6≥0

解得

T

4,1,9,0,0,0,0]

5、两阶段法

用电子计算机求解含人工变量的线性规划问题时, 只能用很大的数来代替M, 这就可能造成计算上的错误。故介绍两阶段法求线性规划问题。

第一阶段: 不考虑原问题是否存在基可行解; 给原线性规划问题加入人工变量, 并构 造仅含人工变量的目标函数和要求实现最小化。如

min w =x n +1+... +x n +m +0x 1+... +0x n

⎧a 11x 1+... +a 1n x n +x n +1=b 1⎪a x +... +a x +x =b 2112n n n +22

⎪⎪

⎨...

⎪a x +... +a x +x =b

mn n n +m m

⎪m 11⎪⎩x 1, x 2,..., x n +m ≥0

然后用单纯形法求解上述模型, 若得到ω= 0 , 这说明原问题存在基可行解, 可以进行

第二段计算。否则原问题无可行解, 应停止计算。

第二阶段: 将第一阶段计算得到的最终表, 除去人工变量。将目标函数行的系数, 换原问题的目标函数系数, 作为第二阶段计算的初始表。

例子： min z =x 1+x 2+2x 3+5x 4

-2x 3+ x 4=1 ⎧ x 1

⎪ 4 ⎪ x 1+x 2+x 3 = ⎨

4 x 3+2x 4=2⎪2x 1 -

⎪⎩x 1, x 2, x 3, x 4≥0

注意：第三个约束方程是第一个约束方程的2倍，因而是多余的。可现在删除，也可在第

一阶段结束时删除它。

解：第一阶段

u , u 引入人工变量13，构造并求解如下线性规划：

min

w =u 1+u 3

+x 1 -2x 3+ x 4=1 ⎧ u 1

⎪ x 1+x 2+x 3 =4⎪ ⎨

u 3+2x 1 -4x 3+2x 4=2⎪

⎪u , u , x , x , x , x ≥0

⎩131234

*

u 此时，w 已取得最优值w = 0 ，但3依然为基变量。考虑最终表的第三行，除人工变b ，表明第三行约束是多余的，划掉它，此时人工向量从

量外所有原变量系数全为0（包括3）

基中消失。

第二阶段

将第一阶段的最终表列出（人工变量除外），“-C ”行列入原问题的价格系数负值，继续计算单纯形表：

*T *X =[1, 3, 00]此时，判别数全部≤0，得最优解，最优值z =4 。

七、退化的处理

退化——若基本可行解中基变量的取值都大于0，则该解称为非退化的；否则称为退化的。若线性规划的所有基本可行解都是非退化的，则线性规划是非退化的；否则称为退化的。

作业：

1 用两阶段法求解线性规划：

max Z=3x 1-x 2-x 3

⎧ x 1-2x 2+x 3≤11⎪-4x +x +2x ≥3⎪123

⎨

+x 3 =1⎪-2x 1

⎪⎩x 1, x 2, x 3≥0

x x x （第一阶段结束时，2=1，3=1，4=12，其它分量为0，w = 0 。

*

x x x 第二阶段结束时，1=4，2=1，3=9，其它分量为0，z

*

=-2。）

第三讲 运输问题

一、运输问题模型

已知有m 个生产地点Ai , i = 1 , 2 , ⋯ , m。可供应某种物资, 其供应量(产量) 分别为ai , i = 1 , 2 , ⋯ , m, 有n 个销地Bj , j = 1 , 2 , ⋯ , n, 其需要量分别为bj , j = 1 , 2 , ⋯ , n, 从Ai 到Bj 运输单位物资的运价( 单价) 为ci j , 这些数据可汇总于产销平衡表和单位运价表中, 见表3 -1 , 表3 -2。有时可把这两表合二为一。

若用x ij 表示从Ai 到Bj 的运量, 那么在产销平衡的条件下, 要求得总运费最小的调运方案, 可求解以下数学模型：

它包含m × n 个变量, ( m + n) 个约束方程。

二、运输问题的主要性质

1、对产销平衡的运输问题, 由于有以下关系式存在:

所以模型最多只有m + n - 1 个独立约束方程。即系数矩阵的秩≤ m + n - 1。 2、列向量中有且仅有两个位置值为1，其余位置的值为0。

三、运输问题的求解

表上作业法的实质是单纯形法在求解运输问题时的一种运用。其求解步骤如下： 1、找出初始基可行解 最小元素法 伏格尔法

2、求各非基变量的检验数，判别是否达到最优解。如果已经达到最优解，则停止计算，否则转到下一步。

闭回路法 位势法

3、确定换入变量和换出变量，找到新的基可行解。 4、重复第二三步，直到得到最优解。

四、表上作业法

1、初始基可行解的确定

（1）最小元素法 找出运价表中最小元素

c ij

，确定

x ij =min {a i , b i }

，则令

，若

x ij =a i

，则令

b ' j =b j -x ij

，同时

划掉运价表的第i 行；反之，若

x ij =b j

a i ' =a i -x ij

，同时划掉运价表的第j 列。

在运价表剩余元素中重复第一步，直至运价表中所有元素都划去为止，即得初始运输方案。

★注意：当最小元素

c ij

对应的产量

a i 与销量b j 相等时，在产销平衡表中填上x ij =a i ，产

销平衡表第i 行和第j 列同时得到满足。为了保证某变量个数为m+n-1个，除了在产销平衡表上填

x ij =a i

外，必须在表的第i 行或第j 列某空格处（相应运价未被划掉）填一个“0”，然后同

时划去运价表的第i 行与第j 列。

例：

经最小元素法，得到的初始调运方案如下：

（2）伏

格尔法

伏格尔

法德思路是：首先用某一产地产品的次最小运费减去最小运费，得到一个差额。差额越大，说明就近供应不能按最小运费调运时，运费增加最多。因此，需要对差额最大的采用最小运费调运。其运算步骤为：

；

对未划去的元素再分别计算出各行各列的最小运费和次最小运费，重复上述两个步骤，直到给出初始解为止。

2、最优性

检验 --σ≥0时，

方案最优

（1）闭回路法

其基本思路是：假定要确定空格（i,j ）的检验数，可以先找出以该空格为一个顶点，其余顶点全是数字格的闭回路；然后给（i,j ）格一个假定的单位运量，同时调整闭回路上其余数字格的运量，使产销平衡，则闭回路上总运费的变化值等于（i,j ）格的检验数。 ★知识链接

数字格：基变量所在位置（格）； 空 格：非基变量所在位置（格）；

闭回路：从产销平衡表中某空格出发，沿水平或垂直方向前进，遇到合适的数字格后转。

90后继续前进，最后能够回到出发点，这条闭合折线称为闭回路；

从一个非基变量（空格）出发，存在且仅存在一条闭回路。

用

闭回

路法

求检验数时, 需给每一空格找一条闭回路。当产销点很多时, 这种计算很繁。下面介绍较为简便的方法———位势法。 （2）位势法

令u 1, u 2,... u m ; v 1, v 2,... v 3分别为产销平衡表各行和各列的位势，位势法的基本思路为：

✧ 利用数字格（基变量）对应的检验数0=c ij -(u i +v j ) ，确定所有u i , v j 的值； ✧ 判断各空格的检验数σij ：σij =c ij -(u i +v j ) ，计算各个空格的检验数。

3、方案的调整--闭回路法

调整的步骤如下：

（1）先确定最小检验数：min σij σij

（2）找出以空格（L,K ）为一个顶点，其余顶点全是数字格的闭回路；规定空格（L,K ）为闭回路的第一个顶点，闭回路上其他顶点依次为第二顶点，第三顶点，... ，取闭回路上偶数序号顶点的最小运量为调整量θ；

（3）闭回路上偶数序号顶点的运量都减θ，奇数号顶点运量都加θ，不在闭回路上的运量不变。

★注意:若偶数序号顶点中有两个以上数字格运量等于调整量θ，则调整后仅让其中一个数字格变为空格，其他调整后记为0。

{}

五、产销不平衡的运输问题

1、供大于求时

当总产量大于总销量∑a i >∑b j ：时，增加一个虚拟销售地B n +1，该虚拟销售

i =1

j =1

m n

地的总销售量为∑a i -∑b j ，令各地到该虚设销地的单位运价为0。此时，该类

i =1

j =1

m n

问题就转化为一个产销平衡问题，再运用表上作业法求解即可。

2、供不应求时

当总产量小于总销量时∑a i 增加一个虚拟产地A m +1，该虚拟产地的

i =1

j =1

m n

总产量为∑b j -∑a i ，令该虚拟产地到各销地的单位运价为0。此时，该类问题

j =1

i =1

n m

也就转化成一个产销平衡问题，再运用表上作业法求解即可。