运筹学运输问题课件.ppt

《运筹学运输问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划(4)运输问题TransportationProblem中山大学.智能交通研究中心黄敏1什么样的LP问题是运输问题？运输问题的求解有什么特征？运输问题只可以解决调运类的问题吗？2运输问题简介运输问题的数学模型运输问题的性质运输问题的求解方法表上作业法运输问题的建模示例内容提要3运输问题简介问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。4例：某公司经销产品甲。其下设3个加工厂(产地)A1、A2、A2,公司将这些产品分别运

2、往4个销地B1、B2、B3、B4。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？5运输问题的网络图表示法产量＝销量6设由产地i运往销地j的物品数量，则得到如下数学模型:Minf=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6x

3、ij≥0(i=1,2,3,4；j=1,2,3）产量约束销量约束12个决策变量7个约束方程7稀疏矩阵秩为6约束方程系数矩阵每个列向量只有2个分量为1基变量最多有多少个非零分量？8运输问题的数学模型已知设某种物品有m个产地，产地i的产量为设有n个销地，销地j的销量分别为从产地i向销地j运输单位物品的运价是目标问怎样调运这些物品才能使总运费最小？9设由产地i运往销地j的物品数量xij，则得到如下线性规划问题:m*n个决策变量，m+n个约束方程10矩阵形式11运输问题是特殊的线性规划问题!有何性质？如何求解？运输问题是一类模型的抽象12运输问题的性质因此运输问题最多有的独立约

4、束方程数为(1)产销平衡问题有如下关系13m行n行系数矩阵的结构疏松：每一个决策变量所对应的列向量只有2项为1，其余皆为014(2)产销平衡运输问题必有可行解，也必有最优解设令　　　　　，则　　满足约束条件，即有解；因　　　　　　　　　，解有界，即有最优解。15运输问题的求解直接用单纯形法求解？要增加人工变量，致使计算量大大增加分析运输问题模型的特点，寻找简便解法16线性规划问题的求解过程运输问题的求解步骤1何谓基可行解？非0分量个数不大于独立约束方程个数的可行解。对产销平衡的运输问题，在m*n个决策变量中，不为零的个数不大于m+n-1。P973.117产销平衡表示例

5、针对运输问题约束方程系数矩阵的特殊结构，采用一种特殊解法──表上作业法。决策变量值3+4-1=6个值33641318线性规划问题的求解步骤19初始基可行解的确定确定一个基可行解即在表格中填入m+n-1个非负数字，为基变量的取值，其余为非基变量，取值为0，不用填。方法最小元素法差额法(伏格尔法)20初始基可行解的确定(1)最小元素法尽可能将资源分配给整个表格中具有最小成本的变量，划去已满足的行或列。调整所有未划去元素的供求量后，重复尽可能将资源分配给整个表格中具有最小成本的变量这一过程。当正好剩下一行或一列未被划去时，程序完成。21例子B1B2B3B4产量A131131

6、07A219284A3741059销量3656产销平衡表22B1B2B3B4产量A13113107A2139284A3741059销量3656最小元素法(1)划去一列23B1B2B3B4产量A13113107A21392184A3741059销量3656最小元素法(2)划去一行24B1B2B3B4产量A131134107A21392184A3741059销量3656最小元素法(3)划去一列25B1B2B3B4产量A131134107A21392184A37461059销量3656最小元素法(4)划去一列26B1B2B3B4产量A131134107A21392184A3

7、74610539销量3656最小元素法(5)划去一行27B1B2B3B4产量A1311341037A21392184A374610539销量3656最小元素法(6)同时划去一行一列28B1B2B3B4产量A1311341037A21392184A374610539销量3656Z=1*3+2*1+3*4+4*6+5*3+10*3=86最小元素法(7)--得到一个基可行解注意：此时表格中有数字的格数为3+4-1＝6，即有6个基变量29初始基可行解的确定(2)差额法(伏格尔法)计算每一行(列)中最小运费与次最小运费的差额；选取差额最大的行或列，将资源尽可能