1、Chapter 5 运输问题与指派问题Transportation and Assignment Problem 1运 输 模 型 The Transportation model 2运输问题表上作业法3运输问题网络模型 Transportation Network 4 应用实例物流中的一个普遍问题是如何以尽可能小的成本把货物从一系列起始地（ sources） （如工厂、仓库）运输到一系列终点地（ destinations） （如仓库、顾客）运输问题 The Transportation Problem想想 看！如何分析这类问题1 运输问题模型实例 The P j = 1, 2, 3, 4)一
2、般运输问题的提法：假设 A1、 A2、 、 Am 表示某物资的 m个产地； B1、 B2、 、Bn 表示某物资的 n个销地； ai 表示产地 Ai 的产量； bj 表示销地 Bj 的需求量； cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价。如果 a1 + a2 + + am = b1 + b2 + + bn ， 则称该运输问题为产销平衡问题；否则，称产销不平衡。解：解： 设 xij 为从产地 Ai 运往销地 Bj 的运输量对于产销平衡问题，可得到下列运输问题的模型：B1 B2 Bn aiA1 c11 x11 c12 x12 c1n x1n a1A2 c21 x21 c12 x22
3、c1n x2n a2 Am cm1 xm1 cm2 xm2 cmn xmn ambj b1 b2 bn ai =bj这就是运输问题的数学模型。它包含 mn个变量， (m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。 该系数矩阵中对应于变量 xij的系数向量 Pij，其分量中除第 i个和第 m+j个为 1以外，其余的都为零。即 Pij=(0, ,1,0,0,1,0,0) T= ei+em+j运输问题的特征 Characteristics of Transportation Problems运输问题的假定数学模型为：1、 需求假设： 每一个出发地都有一个固定的供应量，所有的供应量都必须配送到
4、目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足2、 可行解假定 ：当且仅当供应量的 总和 等于需求量的总和时，运输问题才有可行解，且有最优解 3、 成本假设： 从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量4、 整数解性质： 当供应量和需求量都是整数，必存在决策变量均为整数的最优解运输问题解中非零变量的个数不超过 m+n-1个，因为 m+n个约束中只有m+n-1个是独立的。基变量在迭代过程中保持为 m+n-1个 。用单纯形来求解运输问题，需要加 m+n个人工变量，产生一个变量数为mn +m+n的线性规划，求解比较复杂，需要寻求更简便的解法。
