重庆工商大学：《管理运筹学》课程教学课件（讲稿）第三章 运输问题

运输问题基本性质运输问题是线性规划问题，但它具有一些特殊的性质。这些性质是运输问题特殊解法的基础下面给出几个主要性质：性质1：运输问题模型的系数矩阵每列（Pi）只有第行和第m行两个元素为1，其余均为0。性质2：系数矩阵A的秩为m+n,-因此运输问题的基变量一定是个m+n-1性质3：产销平衡运输问题一定存在最优解性质4：若各产地的产量和各销地的销量都为整数，则有可行解的运输问题必有整数最优解运输问题

运输问题 运输问题是线性规划问题，但它具有一些特殊 的性质。这些性质是运输问题特殊解法的基础。 下面给出几个主要性质：  性质1: 运输问题模型的系数矩阵每列（Pij）只有第 行和第 行两个元素为1，其余均为0。  性质2: 系数矩阵A的秩为 ，因此运输问题的基 变量一定是个 。  性质3: 产销平衡运输问题一定存在最优解。  性质4: 若各产地的产量和各销地的销量都为整 数， 则有可行解的运输问题必有整数最优解。 i m j  m n  1 m n  1 运输问题基本性质

X11 Xi2 ... Xin X21 X22 ... X2n ... XmlXm2..mn11m01P12Ram=二111011n0001

  1 1 1 1 1 1 1 1 11 1 . 1 1 1 . 1 1 1 . 1 O O O OO n n m m mn x x . x x x . x . x x . x 11 12 1 21 22 2 1 2 mn  P12 P2n 

(0).01一i0x,的列向量Py =..=e; +em+j0一mtj100.0...1ei=其中00..0

   0 .010 .010 .0 ij Pij x 的列向量 i m+j i m j e e       0 .010 .0 i 其中 e

【定理3.1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。【证】因为产销平衡，即α，=b，将前m个约束方程两边相i=1=1加得mmnZZx,=Zai=1i=lj=lmZZCx,=b再将后n个约束相加得j=l i=lj=l显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵

【证】因为产销平衡，即 ，将前m个约束方程两边相 加得      m i n j ai bi 1 1       m i n j m i ij i x a 1 1 1 再将后n个约束相加得       n j m i n j ij j x b 1 1 1 显然前m个约束方程之和等于后n个约束方程之和，m+n个 约束方程是相关的，系数矩阵 【定理3.1】设有m个产地n个销地且产销平衡的运输问题，则 基变量数为m+n-1

Xi1 Xi2 --- Xin X21 X22-..X2n...XmlXm2-..Xmmn11：m行A=n行中任意m+n阶子式等于零，取第一行到m+n一1行与Xin,X2n...,Xmn,Xi1,Xi2..., Xi,n-1对应的列（共m+n-1列）组成的m+n一1阶子式

中任意m+n阶子式等于零，取第一行到m+n－1行与 对应的列（共m+n-1列）组成的m+n－1阶子式 1 2 11 12 1, 1 . , , ,., n n mn n x ，x ，x x x x m 行 n 行 11 12 1 21 22 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 n n m m mn x x x x x x x x x A                     ＝