随着10月份的结束
线性规划的课程也落下了帷幕
接下来我们将迎来一个新的专题
运输问题
跟着小编来了解一下吧
教学目标
掌握运输问题的数学模型
了解运输问题的表上作业法
掌握“产销不平衡”运输问题的转化
掌握计算机求解运输问题
了解运输问题在应急管理中的应用
一、TP的基本模型
（一）运输问题
运输问题是一类应用广泛的特殊线性规划问题，在线性规划的一般理论和单纯形法出现以前，Kantrovich和Hitchcock已经研究了运输问题，所以也叫K-H问题。运输问题可以用单纯形法求解，但由于自身模型结构的特殊性，可以找到比单纯形法更有效的专门方法，从而节约计算时间。
运输问题的一般表述为：设某种物资有m个产地Ai，其供应量分别为：ai=1,2,…m；另有n个销地Bi，其物资需求量分别为：bj=1,2,…n。已知，由产地Ai向销地Bi运输单位物资的运费为Cij。
（二）基本模型
二、TP的表上作业法
（一）原理
♘表上作业法
一种求解线性规划问题的特殊方法，实质就是单纯形算法
♘TP问题的两个定理
（1）TP问题一定有最优解
（2）TP的榆树方程组的系数矩阵的秩等于m+n-1
♘表上作业法的计算步骤
（1）找出初始基可行解
（2）求各非基变量的检验数，判别问题是否达到最优
（3）确定入基变量与出基变量，找出新的基本可行解
（4）重复（2）和（3），直至得到最优解
（二）示例
求解如下线性规划问题
♘西北角法
♘最小元素法
（三）最优解判别
1.闭回路法
在已经给出的调运方案中，从一个代表非基变量的空格出发，沿水平或者垂直方向前进，只有碰到代表基变量的填入数字的格才能向左或者向右转90度（也可以不改变方向）继续前进，直至回到出发的空格，由此形成的封闭的折线叫做闭回路。一个空格存在唯一的闭回路。
♘闭回路法原理
对于代表非基变量的空格，将其调运量调整为1，由于产销平衡的要求，则必须对这个空格所在的闭回路的顶点，加上或者减少1，最后，重新计算为此给整个运输方案带来的变化，若所有的非基变量检验数都大于或者等于零，则现有基可行解就是最优解，否则继续迭代。
♘检验数计算
为顶点依次编号，奇数顶点运价之和减去偶数顶点运价之和，结果即为检验数。
♘示例
2.位势法
♘原理
♘位势法步骤
♘示例
在所有负值的检验数中，找最小的负检验数，它对应的非基变量为入基变量，本例中，为λ24=-1，选择X24为入基变量,并且以X24所在格为出发点作一个闭回路。
由于λ24=-1，表明增加1单位的X24的运量，总运输成本减少1，尽量增加X24的运量，但为了保证运输方案的可行性，所以出发点X24所在的空格为1的闭回路顶点序号中，找出所有的偶数的顶点的调运量，取其中的最小值即X24=min（3,1）=1。
为了使得产销平衡，把所有闭回路上的偶数顶点的运输量都减少这个单位，而其他闭回路上为奇数顶点的运输量抖增加这个单位，就可以得到调整以后的运输方案。
三、”产销不平衡“中的TP
处理实际问题的时候，往往无法满足“产销平衡”的约束，有时“供大于求”，有时“供小于求”这样就破坏了运输表的结构。因此，需要对产销不平衡运输问题的运输表进行调整：
✔ 供过于求——虚拟库存
✔ 供不应求——虚拟产地
♘示例
求解如下线性规划问题
由于供大于求，构建一个虚拟库存B5：
QM求解结果如下：
四、TP的求解及其应用
（一）生产计划问题
某机床厂在年初签订了生产一批同型号机床的合同。合同要求该厂分别于当年四个季度末交货。四个季度正常生产的能力与单位成本，以及按照合同应当交货的台数如下表所示。在第三与第四季度可以安排加班生产，加班生产能力为每个季度8台，但单位成本比正常生产时高3万元。另外，如果生产出来的机床当季不交货，则每台每季度需要支付0.12万元的存储保养费用。
做出一个完成交货合同并使全年生产费用最小的生产计划。
解法1：
解法2：
（二）转运问题
转运问题是运输问题的一个补充，在原来的运输问题中的产地、销地之外增加了一个中转点，在运输问题中，假设物品从出发点运往到达点，在转运问题中，假设物品可以从一个出发点运往另一个出发点或者中转点或者到达点，也允许将物品从一个中转点运往另一个中转点或者到达点，还允许将物品从一个到达点运往另一个到达点或者中转点或者出发点。
每个点，都有一定的供给量和需求量，任意两点之间的运费已知，如何进行调运使得总的运输费用最小。
♘转运问题的一般线性规划模型
♘示例
X地政府有两个应急物资合约供应商，分别位于A、B两地，每个合约供应商可以提供400和600单位的应急物资；X地政府的应急物资储备中心位于C、D两地，负责对X地1、2、3、4四个地区提供应急物资保障，四个地区的应急物资需求分别为200、150、350、300，由于B与4所在地区举例较近，根据协议，在应急条件下，可以直接由B对4提供应急物资保障，应急物资的供给关系和运输费用如图所示。
求费用最小的运输方案。