• 运输问题

1. 以产销平衡问题为例解释运输问题：

在运算中，我们会涉及到两个表：运费表和产销平衡表

1. 运输问题的特点：
   1. 1. 1. 运输问题存在可行解，也一定存在最优解
         2. 当供应量和需求量都是整数时，则一定存在整数最优解，但也可能存在非整数最优解
         3. 有m+n个约束，mn个变量
         4. 运输问题系数矩阵的秩为m+n-1；运输问题基变量的个数为m+n-1

1. 求解运输问题的方法(表上作业法)：

1. 第一步个人推荐使用元素差额法：
   求最小运价（成本）时优先选择差额最大的列（或行）的最小值运送；求最大利润时，优先选择差额最小的那列（或行）的最大值运送
2. 第二步闭合回路法和位势法看着用吧，都差不多：

• 闭回路法：

以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。

该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。

可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言， 以其为起点的闭回路存在且唯一

• 闭回路的特点：

每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向；

每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数；

从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点， 但每一顶点和边在闭回路中只经过一次。

σij =（闭回路上奇数次顶点运距或运价之和）- （闭回路上偶数次顶点运距或运价之和）

对调运方案中每一空格按闭回路法求出检验数：

若所有检验数大于等于零，则此方案为最优方案；

若存在检验数小于零，则需对此方案进行调整

Ep:

1. 1. 1. 1. 1. 位势法(别问，就按照下面这样写，问就是我也不知道)：

1. 解的改进，闭回路调整法：

对σij＜0的地方进行调整，找到一个以此格子为起点的闭回路，令θ=min{ 偶数顶点的最小值(最小运量) }

偶数顶点“减去调整量”，奇数顶点“加上调整量”

1. 重新计算检验数查看是否需要再次调整，若检验数均不为负数（因为求的是最小值）则得到最优解，否则循环上述步骤。
2. 若运输问题的某一基可行解有多个非基变量的检验数为负，但通常取σij<0中最小者对应的变量为换入变量。

当迭代到运输问题的最优解时，如果某个非基变量的检验数为0，说明该问题有无穷多最优解。以此格为调入格，作闭回路，经调整后得另一最优解。

用表上作业法求解运输问题出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。

建议写几题试试P113-124

1. 运输问题的其他形式

• 有时目标函数求最大（这个简单，随便写）
• 当某些运输线路上的能力有限制时（在模型中直接加入约束条件）
• 产销不平衡时：产大于销；销大于产（求解方法是将不平衡问题化为平衡问题再按平衡问题求解）

对于产大于销的问题，我们可以设定一个虚拟的销地，这样就可以化为产销平衡问题（送往虚拟销地的运费为0)

对于销大于的产问题，我们可以设定一个虚拟的产地，这样就可以化为产销平衡问题（虚拟产地送往任意销地的运费为0)注意虚拟产地不可送往刚性需求

对于某产地不可送达某销地的问题，只需要将对应的运费设置为一个足够大的数大M即可

销地的需求如果出现区间表示如150~210，看上界（当然也要看题目有没有说明）

开放的区间就转化为有边界的区间（算这个时区间自己看着办，如下）

产地的产量出现区间也取上界（同样也要先看题目有没有额外说明）

1. （港口）调度问题：看PPT吧，没整明白
2. 转运问题
   • 求解思路：把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。
   • 求解转运问题的步骤：
     1. 将产地、转运点、销地重新编排，转运点既作为产地又作销地；
     2. 各地之间的运价在原问题运价表基础上扩展：自身运往自身的单位运价记为零，不存在运输线路的则记为M（一个足够大的正数）；
     3. 由于经过转运点的物资量既是该点作为销地的需求量，又是该点作为产地时的供应量，但事先又无法获取该数量的确切值，因此通常将调运总量作为该数值的上界