1、第三章 运输问题一、运输问题及其数学模型二、表上作业法三、运输问题的进一步讨论四、应用举例第三章2312341一、运输问题及其数学模型s2=27s3=19s1=14供应量供应地 运价d1=22d2=13d3=12d4=13需求量需求地6753842759106引例：运输问题网络图第三章供应地约束需求地约束一、运输问题及其数学模型第三章运输问题的描述：设某种物品有 m个产地 A1,A2,.,Am， 各产地的产量分别是 a1,a2,.,am；有 n个销地 B1,B2,.,Bn， 各销地的销量分别为 b1,b2,.bn。 假定从产地 Ai(i=1,2,m) 向销地出 Bj(j l,2,.n) 运输单
2、位物品的运价是 cij， 问怎样调运这些物品才能使总运费最小 ?一、运输问题及其数学模型第三章运价表销 地产 地 B1 B2 Bn 产 量A1 C11 C12 C1n a1x11 x12 x1nA2 C12 C22 C2n a2x21 x22 x2n . Am C1m C2m Cmn amxm1 xm2 xmn销 量 b1 b2 bm一、运输问题及其数学模型第三章产销平衡运输问题的数学模型表示：（ ）一、运输问题及其数学模型第三章该模型是一个线性规划模型，可以用单纯形法求解。但是变量数目非常多。如 3个产地， 4个销地。变量数目会有 19个之多。因此应该寻求更简便的解法。为了说明适于求解运输问
3、题的更好的解法，先分析运输问题数学模型的特点。一、运输问题及其数学模型第三章运输问题数学模型的特点：1运输问题有有限最优解是 一个可行解。同时，目标函数有下界，且不会趋于负无穷。所以，必存在有限最优解。一、运输问题及其数学模型第三章2运输问题约束条件的系数矩阵A =n 行m 行系数列向量：第 i个 第 m+ j个一、运输问题及其数学模型第三章由此可知，运输问题具有下述特点：(1)约束条件系数矩阵的元素等于 0或 1；(2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前 m个约束方程中出现一次，在后 n个约束方程中也出现一次；对产销平衡运输问题，除上述两个特点外，还有以下特点：(3)所有结构约束条件都是等式约束；(4)各产地产量之和等于各销地销量之和。 秩 ( A) =m+n-1运输问题的基可行解中应包含 m+n-1个基变量 .一、运输问题及其数学模型
