第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划

Presentation on theme: "第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划"— Presentation transcript:

1 第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划
二、线性规划与目标规划 第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划 清华大学出版社

2 第1节 运输问题的数学模型 第2节 表上作业法 第3节 产销不平衡的运输问题及其求解方法 第4节 MATLAB解法 第5节 应用举例
第4章 运输问题 第1节 运输问题的数学模型 第2节 表上作业法 第3节 产销不平衡的运输问题及其求解方法 第4节 MATLAB解法 第5节 应用举例 清华大学出版社

3 第1节 运输问题的数学模型 已知有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，这些数据可汇总于产销平衡表和单位运价表中，见表3-1，表3-2。有时可把这两表合二为一。 销地 产地 ┉ n 产量 1 2 ┆ m A 1 A2 Am 销量 B1 B2 ┈ BNn 清华大学出版社

4 第1节 运输问题的数学模型 若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案的数学模型为 清华大学出版社

5 第1节 运输问题的数学模型 这就是运输问题的数学模型。它包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。
第1节 运输问题的数学模型 这就是运输问题的数学模型。它包含m×n个变量，(m+n)个约束方程，其系数矩阵的结构比较松散，且特殊。 清华大学出版社

6 第1节 运输问题的数学模型 该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即
第1节 运输问题的数学模型 该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即 Pij=(0,… ,1,0,…,0,1,0,…,0)T=ei+em+j 对产销平衡的运输问题，由于有以下关系式存在： 清华大学出版社

7 第2节 表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：
第2节 表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为： (1) 找出初始基可行解。即在(m×n)产销平衡表上用西北角法或最小元素法，Vogel法给出m+n-1个数字，称为数字格。它们就是初始基变量的取值。 。 (2) 求各非基变量的检验数，即在表上计算空格的检验数，判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。 (3) 确定换入变量和换出变量，找出新的基可行解。在表上用闭回路法调整。 (4) 重复(2)，(3)直到得到最优解为止。 清华大学出版社

8 第2节 表上作业法 例1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表4-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。 清华大学出版社

9 第2节 表上作业法 解：先作出这问题的产销平衡表和单位运价表，见表4-3，表4-4 表4-4 产销平衡表 表4-3 单位运价表
第2节 表上作业法 解：先作出这问题的产销平衡表和单位运价表，见表4-3，表4-4 表4-4 产销平衡表 表4-3 单位运价表 清华大学出版社

10 2.1 确定初始基可行解 与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有
2.1 确定初始基可行解 与一般线性规划问题不同，产销平衡的运输问题总是存在可行解。因有 必存在xij≥0，i=1，…，m，j=1，…，n，这就是可行解。又因0≤xij≤min(aj，bj)，故运输问题必存在最优解。 清华大学出版社

11 2.1 确定初始基可行解 确定初始基可行解的方法很多，有西北角法，最小元素法和伏格尔(Vogel)法。一般希望的方法是既简便，又尽可能接近最优解。下面介绍两种方法： 1.    最小元素法 基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。以例1进行讨论。 第一步：从表3-3中找出最小运价为1，这表示先将A2的产品供应给B1。因a2＞b1，A2除满足B1的全部需要外，还可多余1吨产品。在表3-4的(A2，B1)的交叉格处填上3。得表3-5。并将表3-3的B1列运价划去。得表3-6。 清华大学出版社

12 2.1 确定初始基可行解 表 3-5 和表3-6 清华大学出版社

13 2.1 确定初始基可行解 第二步：在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。
2.1 确定初始基可行解 第二步：在表3-6未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3，并给出表3-7，表3-8。 清华大学出版社

14 2.1 确定初始基可行解 第三步：在表3-8未划去的元素中再找出最小运价3；这样一步步地进行下去，直到单位运价表上的所有元素划去为止，最后在产销平衡表上得到一个调运方案，见表3-9。这方案的总运费为86元。 清华大学出版社

15 2.1 确定初始基可行解 用最小元素法给出的初始解是运输问题的基可行解，其理由为：
2.1 确定初始基可行解 用最小元素法给出的初始解是运输问题的基可行解，其理由为： (1) 用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素，并比较产量和销量。当产大于销，划去该元素所在列。当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划(n+m)条直线。但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。即给出了(m+n-1)个基变量的值。 清华大学出版社

16 2.1 确定初始基可行解 用最小元素法给出的初始解是运输问题的基可行解，其理由为：
2.1 确定初始基可行解 用最小元素法给出的初始解是运输问题的基可行解，其理由为： (2) 这(m+n-1)个基变量对应的系数列向量是线性独立的。证若表中确定的第一个基变量为它对应的系数列向量为: 因当给定 的值后，将划去第i1行或第j1列， 即其后的系数列向量中再不出现ei1或em+j1， 因而 不可能用解中的其他向量的线性组合表示。 类似地给出第二个，…，第(m+n-1)个。 这(m+n-1)个向量都不可能用解中的其他向量的线性组合表示。故这(m+n-1)个向量是线性独立的。 清华大学出版社

17 2.1 确定初始基可行解 用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列。这时就出现退化。关于退化时的处理将在2.4节中讲述。 清华大学出版社

18 2.1 确定初始基可行解 2. 伏格尔法 最小元素法的缺点是：为了节省一处的费用，有时造成在其他处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。 清华大学出版社

19 2.1 确定初始基可行解 伏格尔法的步骤是： 第一步：在表3-3中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行，见表3-10。 清华大学出版社

20 2.1 确定初始基可行解 第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。在表3-10中B2列是最大差额所在列。B2列中最小元素为4，可确定A3的产品先供应B2的需要。得表3-11 清华大学出版社

21 2.1 确定初始基可行解 同时将运价表中的B2列数字划去。如表3-12所示。 清华大学出版社

22 2.1 确定初始基可行解 第三步：对表3-12中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。用此法给出例1的初始解列于表3-13。 清华大学出版社

23 2.1 确定初始基可行解 由以上可见：伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。 本例用伏格尔法给出的初始解就是最优解。 清华大学出版社

24 2.2 最优解的判别 判别的方法是计算空格(非基变量)的检验数cij−CBB-1Pij，i,j∈N。因运输问题的目标函数是要求实现最小化，故当所有的cij−CBB-1Pij≥0时，为最优解。下面介绍两种求空格检验数的方法。 1.闭回路法； 2.位势法 清华大学出版社

25 2.2 最优解的判别 1.闭回路法 在给出调运方案的计算表上，如表3-13，从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。闭回路如图3-1的(a),(b),(c)等所示。 清华大学出版社

26 2.2 最优解的判别 从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字格(基变量)对应的系数向量是一个基。任一空格(非基变量)对应的系数向量是这个基的线性组合。如Pij, i,j∈N可表示为 其中Pik,Plk,Pls,Pus,Puj∈B。而这些向量构成了闭回路(见图3-2)。 清华大学出版社

27 2.2 最优解的判别 清华大学出版社

28 2.2 最优解的判别 闭回路法计算检验数的经济解释为：在已给出初始解的表3-9中，可从任一空格出发，如(A1，B1)。若让A1的产品调运1吨给B1。为了保持产销平衡，就要依次作调整： 在(A1，B3)处减少1吨，(A2，B3)处增加1吨，(A2，B1)处 减少1吨，即构成了以(A1，B1)空格为起点，其他为数字格的闭回路。如表3-14中的虚线所示。在这表中闭回路各顶点所在格的右上角数字是单位运价。 清华大学出版社

29 2.2 最优解的判别 可见这调整的方案使运费增加 (+1)×3+(−1)×3+(+1)×2+(− 1)×１=1(元) 这表明若这样调整运量将增加运费。将“1”这个数填入(A1，B1)格，这就是检验数。按以上所述，可找出所有空格的检验数， 见表3-15。 清华大学出版社

30 2.2 最优解的判别 当检验数还存在负数时，说明原方案不是最优解，要继续改进，改进方法见2.3小节。 清华大学出版社

31 2.2 最优解的判别 2. 位势法 用闭回路法求检验数时，需给每一空格找一条闭回路。当产销点很多时，这种计算很繁。下面介绍较为简便的方法——位势法。 设u1，u2，…，um;v1，v2，…，vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa的(m+n)×(m+n)初始基矩阵。人工变量xa在目标函数中的系数ca=0，从线性规划的对偶理论可知： 清华大学出版社

32 2.2 最优解的判别 而每个决策变量xij的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj。于是检验数
2.2 最优解的判别 而每个决策变量xij的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj。于是检验数 由单纯形法得知所有基变量的检验数等于0。即 清华大学出版社

33 2.2 最优解的判别 例如，在例1的由最小元素法得到的初始解中x23，x34，x21，x32，x13，x14是基变量。xa为人工变量，对应的检验数是： 基变量 检验数 xa ca−u1= ∵ca=0 ∴u1=0 x23 c23−(u2+v3)=0 即2 − (u2+v3)=0 x34 c34 − (u3+v4)= − (u3+v4)=0 x21 c21 − (u2+v1)= − (u2+v1)=0 x32 c32 − (u3+v2)= − (u3+v2)=0 x13 c13 − (u1+v3)= − (u1+v3)=0 x14 c14 − (u1+v4)= − (u1+v4)=0 从以上7个方程中,由u1=0可求得 u2= − 1,u3= − 5,v1=2,v2=9,v3=3,v4=10 清华大学出版社

34 2.2 最优解的判别 因非基变量的检验数为 这就可以从已知的ui，vj值中求得。这些计算可在表格中进行。
2.2 最优解的判别 因非基变量的检验数为 这就可以从已知的ui，vj值中求得。这些计算可在表格中进行。 以例1说明。 第一步：按最小元素法给出表3-9的初始解，然后做表3-16；即在对应表3-9的数字格处填入单位运价，见表3-16。 清华大学出版社

35 2.2 最优解的判别 第二步：在表3-16上增加一行一列，在列中填入ui，在行中填入vj，得表3-17。
2.2 最优解的判别 第二步：在表3-16上增加一行一列，在列中填入ui，在行中填入vj，得表3-17。 先令u1=0，然后按ui+vj=cij， i，j∈B相继地确定ui，vj。由表3-17可见，当u1=0时，由u1+v3=3可得v3=3，由u1+v4=10可得v4=10；在v4=10时，由u3+v4=5可得u3= − 5，以此类推可确定所有的ui，vj的数值。 清华大学出版社

36 2.2 最优解的判别 第三步：按σij=cij −(ui+vj), i,j∈N计算所有空格的检验数。如 σ11=c11 − (u1+v1)=3 − (0+2)=1 σ12=c12 − (u1+v2)=11 − (0+9)=2 这些计算可直接在表3-17上进行。为方便，特设计计算表3-18如下： 表3-18 中还有负检验数。说明未得最优解，还可以改进。 清华大学出版社

37 2.3 改进的方法——闭回路调整法 当在表中空格处出现负检验数时，表明未得最优解。若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。由表3-18得(2，4)为调入格。以此格为出发点，作一闭回路，如表3-19所示。 清华大学出版社

38 2.3 改进的方法——闭回路调整法 (2，4)格的调入量θ是选择闭回路上具有(-1)的数字格中的最小者。即θ=min(1,3)=1(其原理与单纯形法中按θ规划来确定换出变量相同)。然后按闭回路上的正、负号，加入和减去此值，得到调整方案，如表3-20所示。 清华大学出版社

39 2.3 改进的方法——闭回路调整法 对表3-20给出的解，再用闭回路法或位势法求各空格的检验数，见表3-21。表中的所有检验数都非负，故表3-20中的解为最优解。这时得到的总运费最小是85元。 清华大学出版社

40 2.4 表上作业法计算中的问题 1. 无穷多最优解 2. 退化 清华大学出版社

41 2.4 表上作业法计算中的问题 1. 无穷多最优解 在本章2.1节中提到，产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解? 判别依据与第1章3.3节讲述的相同。即某个非基变量(空格)的检验数为0时，该问题有无穷多最优解。表3-21空格(1，1)的检验数是0，表明例1有无穷多最优解。可在表3-20中以(1，1)为调入格，作闭回路 (1，1)+-(1，4)--(2，4)+-(2，1)--(1，1)+。 确定θ=min(2,3)=2。经调整后得到另一最优解，见表3-22。 清华大学出版社

42 2.4 表上作业法计算中的问题 1. 无穷多最优解 清华大学出版社

43 2.4 表上作业法计算中的问题 2. 退化 用表上作业法求解运输问题当出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。有以下两种情况： (1) 当确定初始解的各供需关系时，若在(i,j)格填入某数字后，出现Ai处的余量等于Bj处的需量。这时在产销平衡表上填一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格。这时需要添一个“0”。它的位置可在对应同时划去的那行或那列的任一空格处。如表3-23，表3-24所示。因第一次划去第一列，剩下最小元素为2，其对应的销地B2，需要量为6，而对应的产地A3未分配量也是6。这时在产销表(3，2)交叉格中填入6，这时在单位运价表3-24中需同时划去B2列和A3行。在表3-23的空格(1，2)，(2，2)，(3，3)，(3，4)中任选一格添加一个0。 清华大学出版社

44 2.4 表上作业法计算中的问题 2. 退化 表 3-23 表 3-24 清华大学出版社

45 2.4 表上作业法计算中的问题 2. 退化 (2) 在用闭回路法调整时，在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时另一个数字格必须填入一个0，表明它是基变量。当出现退化解后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为0的数字格，这时应取调整量θ=0。 清华大学出版社

46 第3节 产销不平衡的运输问题及其求解方法 前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。 当产大于销时 清华大学出版社

47 第3节 产销不平衡的运输问题及其求解方法 运输问题的数学模型可写成 清华大学出版社

48 第3节 产销不平衡的运输问题及其求解方法 由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。设xi, n+1是产地Ai的储存量，于是有： 清华大学出版社

49 第3节 产销不平衡的运输问题及其求解方法 令 当 i=1,…，m，j=1,…，n时 当 i=1,…，m，j=n+1时 将其分别代入，得到
清华大学出版社

50 第3节 产销不平衡的运输问题及其求解方法 清华大学出版社

51 第3节 产销不平衡的运输问题及其求解方法 由于该模型中有 所以这是一个产销平衡的运输问题。
当产大于销时，只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为 而在单位运价表中从各产地到假想销地的单位运价为， 就转化成一个产销平衡的运输问题。 清华大学出版社

52 第3节 产销不平衡的运输问题及其求解方法 当销大于产时，可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为
在单位运价表上令从该假想产地到各销地的运价， 同样可以转化为一个产销平衡的运输问题。 清华大学出版社

53 第3节 产销不平衡的运输问题及其求解方法 例2 设有三个化肥厂(A，B，C)供应四个地区(Ⅰ，Ⅱ，Ⅲ，Ⅳ)的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表3-25所示。试求出总的运费最节省的化肥调拨方案。 清华大学出版社

54 第3节 产销不平衡的运输问题及其求解方法 解：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第Ⅳ个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分，如地区Ⅰ，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表(表3-26)和单位运价表(表3-27)。 清华大学出版社

55 第3节 产销不平衡的运输问题及其求解方法 产销平衡表(表3-26),单位运价表(表3-27) 清华大学出版社

56 第3节 产销不平衡的运输问题及其求解方法 根据表上作业法计算，可以求得这个问题的最优方案如表3-28所示) 清华大学出版社

57 第4节 MATLAB解法 1. 使用linprog函数 将运输问题数字模型转换为线性规划问题标准型，然后使用linprog函数求解
例4.1 某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表4-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。 清华大学出版社

58 第4节 MATLAB解法 解：设从Ai到Bj的运量为xij (i=1,2,3; j=1,2,3,4) ，则这个运输问题的线性规划模型为 其中 程序ch4_1_1.m x = [ ]; cost = 清华大学出版社

59 第4节 MATLAB解法 2. 使用MATLAB直接利用单位运价表、产量表和销量表生成linprog函数所需的参数。 程序4_2_2.m
计算结果： x = [ ] cost = 清华大学出版社

60 第4节 MATLAB解法 x = 3. 利用表上作业法编写程序计算 程序4_1_3.m NaN NaN 5 2 3 NaN NaN 1
cost = 85 清华大学出版社

61 第5节 应 用 举 例 由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。 清华大学出版社

62 第5节 应 用 举 例 例3 某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3-29所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策。 清华大学出版社

63 第5节 应 用 举 例 解 由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足 清华大学出版社

64 第5节 应 用 举 例 又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有： 清华大学出版社

65 第5节 应 用 举 例 第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见表3-30。 清华大学出版社

66 第5节 应 用 举 例 设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成： 清华大学出版社

67 第5节 应 用 举 例 显然，这是一个产大于销的运输问题模型。注意到这个问题中当i＞j时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见表3-31)。 清华大学出版社

68 第5节 应 用 举 例 由程序4_2.m可得生产方案如下表所示： 按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。
第5节 应 用 举 例 由程序4_2.m可得生产方案如下表所示： 按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。 清华大学出版社

69 第5节 应 用 举 例 例4 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数 见表3-33。 清华大学出版社

70 第5节 应 用 举 例 假定各条航线使用相同型号的船只，又各城市间的航程天数见表3-34。 清华大学出版社

71 第5节 应 用 举 例 又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求?
第5节 应 用 举 例 又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求? 解 该公司所需配备船只分两部分。 (1) 载货航程需要的周转船只数。例如航线1，在港口E装货1天，E→D航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转船只需57条。各条航线周转所需船只数见表3-35。 以上累计共需周转船只数91条 . 清华大学出版社

72 第5节 应 用 举 例 (2) 各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B。各港口每天余缺船只数的计算见表3-36。 清华大学出版社

73 第5节 应 用 举 例 为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表3-37。
第5节 应 用 举 例 为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表3-37。 单位运价表应为相应各港口之间的船只航程天数，见表3-38。 清华大学出版社

74 第5节 应 用 举 例 运行程序4_3.m，可得如下分配方案： 由表3-39知最少需周转的空船数为
第5节 应 用 举 例 运行程序4_3.m，可得如下分配方案： 由表3-39知最少需周转的空船数为 2×1+13×1+5×1+17×1+3×1=40条。 这样在不考虑维修、储备等情况下，该公司至少应配备40+91=131条船。 清华大学出版社

75 第5节 应 用 举 例 例5 在本章的例1中，如果假定： ①每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；
第5节 应 用 举 例 例5 在本章的例1中，如果假定： ①每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运； ②运往各销地的产品可以先运给其中几个销地，再转运给其他销地； ③除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间转运。已知各产地、销地、中间转运站及相互之间每吨产品的运价如表3-40所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。 清华大学出版社

76 第5节 应 用 举 例 清华大学出版社

77 第5节 应 用 举 例 解：从表3-40中看出，从A1到B2每吨产品的直接运费为11元，如从A1经A3运往B2，每吨运价为3+4=7元，从A1经T2运往B2只需1+5=6元，而从A1到B2运费最少的路径是从A1经A2，B1到B2，每吨产品的运费只需1+1+1=3元。可见这个问题中从每个产地到各销地之间的运输方案是很多的。为了把这个问题仍当作一般的运输问题处理，可以这样做： (1) 由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。 (2) 对扩大的运输问题建立单位运价表。方法将表3-40中不可能的运输方案的运价用任意大的正数M代替。 清华大学出版社

78 第5节 应 用 举 例 (3) 所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。可以规定T1，T2，T3，T4的产量和销量均为20吨。由于实际的转运量 可以在每个约束条件中增加一个松弛变量xii，xii相当于一个虚构的转运站，意义就是自己运给自己。(20−xii)就是每个转运站的实际转运量，xii的对应运价cii=0。 清华大学出版社

79 第5节 应 用 举 例 (4) 扩大的运输问题中原来的产地与销地因为也有转运站的作用，所以同样在原来产量与销量的数字上加20吨，即三个厂每天糖果产量改成27，24，29吨，销量均为20吨；四个销售点的每天销量改为23，26，25，26吨，产量均为20吨，同时引进xii作为松弛变量。 清华大学出版社

80 第5节 应 用 举 例 (下面写出扩大运输问题的产销平衡表与单位运价表(见表3-41)，由于这是一个产销平衡的运输问题，所以可以用表上作业法求解 清华大学出版社

81 第5节 应 用 举 例 运行程序ch4_4.m，可得此问题的解为： 清华大学出版社

82 结束语 随我国物流业的兴起，现已有专门的学科 和专业，从事研究和教学。并有相应的学会和网站。是一个广阔的领域。 清华大学出版社