西安建筑科技大学精品课程：《运筹学》PPT教学课件_第3章 运输问题

遠输间题 本章内容重点 √运输问题与有关概念 运輪问题的求解—表上作业法 √运輪问题应用—建棋

本章内容重点 ü运输问题与有关概念 ü运输问题的求解—表上作业法 ü运输问题应用—建模

遠输间题 般地,设有某种物资有m个产地联合供应n个销地。 各产地产量、各销地销量以及个产地至各销地草位运价 如下表3-1。如何调运才能使总运费最小? 表3-1运问题教据表 运价销地 产地 B 产量 A CIn 销量 b

一般地，设有某种物资有m个产地联合供应n个销地。 各产地产量、各销地销量以及个产地至各销地单位运价 如下表3-1。如何调运才能使总运费最小？ 运价 销地 产地 B1 B2 … Bn 产量 A1 c11 c12 … c1n a1 A2 c21 c22 … c2n a2 … … … … … … Am cm1 cm2 … cmn am 销量 b1 b2 … bn 表3-1 运输问题数据表

遠输间题 若用x表示从A到B的运量,那么在产销平衡的条件 下,根据运输问题的要求,可以建立运输变量表,如表3-2 表3-2运輪问题数据表 销 产地 B B 产量 x x 12 销量 b b b

若用xij表示从Ai到Bj的运量，那么在产销平衡的条件 下，根据运输问题的要求，可以建立运输变量表，如表3-2 销地 产地 B1 B2 … Bn 产量 A1 x11 x12 … x1n a1 A2 x21 x22 … x2n a2 … … … … … … Am xm1 xm2 … xmn am 销量 b1 b2 … bn 表3-2 运输问题数据表

遠输间题 于是得到下列一般运輪问题的模型 Min z= ∑∑cnxn (3-1) 少=1 1,2 (3-2) =1.2 n (3-3) ≥0,i=1, m,j=1,2,…,n(3-4) 式(3-2)为m个产地的产量约束;式(3-3)为n个销 地的销量约袁

于是得到下列一般运输问题的模型： ïî ï í ì ³ = = - ³ = £ = - £ = - = - å å å å = = = = 0 , 1,2 , , , 1,2 , , (3 4 ) ( , ) , 1,2 , , (3 3 ) , 1,2 , , (3 2 ) (3 1) 1 1 1 1 x i m j n x b j n x a i m st Min z c x ij m i ij j n j ij ij m i n j ij ij L L L L 式(3-2)为 m 个产地的产量约束；式(3-3) 为 n 个销 地的销量约束

遠输间题 对于产销平衡问题,可得到下列运输问题的模型: Min z ∑∑cnx (3-5) ∑xn=b,j=1,2 (3-6) x≥0,i=1,2 ,j=1,2 在产销平衡问题中,式3-2)、(3-3)分别变为(3-5) (3-6)约束条件成为等式

对于产销平衡问题，可得到下列运输问题的模型： ïî ï í ì ³ = = = = - = = - = å å å å = = = = x i m j n x b j n x a i m st Min z c x ij m i ij j n j ij ij m i n j ij ij 0 , 1,2 , , , 1,2 , , , 1,2 , , (3 6 ) , 1,2 , , (3 5 ) 1 1 1 1 L L L L 在产销平衡问题中，式(3-2) 、 (3-3) 分别变为(3-5) 、 (3-6) 约束条件成为等式

遠输间题 在实际问题建模时,还会出现如下一些变化: (1)有时目标函数求最大,如求利涧或营业额最大; (2)当某些运輪线路上的能力有限制肘,模型中可直接加 入(等式或不等式)约柬; (3)产销不平衡的情况。当销量大于产量肘可加入一个虚 设的产地去生产不足的物资,这相当于在式(3-2)每一 式中加上1个松弛变量,共m个;当产量大于销量时 可加入一个虚设的销地去消化多余的物资,这相当于 在式(3-3)每一式中加上1个松弛变量,共n个

在实际问题建模时，还会出现如下一些变化： (1)有时目标函数求最大，如求利润或营业额最大； (2)当某些运输线路上的能力有限制时，模型中可直接加 入(等式或不等式) 约束； (3)产销不平衡的情况。当销量大于产量时可加入一个虚 设的产地去生产不足的物资，这相当于在式(3-2)每一 式中加上1个松弛变量，共m个；当产量大于销量时 可加入一个虚设的销地去消化多余的物资，这相当于 在式(3-3)每一式中加上1个松弛变量，共 n个

遠输间题 x1lx12∴xlnx21x22…x2 L 糸数矩阵由0和1组成,每列有且只有2个1。即变量 x的余数向量P中只有第i个和第m+个为1 糸数矩阵的秩为m+n-1 √任何运輪问题至少有一个最优解

x11 x12 … x1n x21 x22 … x2n … xm1 xm1 … xmn u1 1 1 … 1 u2 1 1 … 1 … … um 1 1 … 1 v1 1 1 1 v2 1 1 1 … … … … vn 1 1 1 ü 系数矩阵由0和1组成，每列有且只有2个1。即变量 xij的系数向量Pij中只有第i个和第m+j个为1。 ü 系数矩阵的秩为m+n-1 ü 任何运输问题至少有一个最优解

遠输间题 考虑产销平衡问题,由于我们头心的量均在表3-1与表 3-2中,因此考虑把表3-1与表3-2合成一个表,如下表3-3 表3-3运輪问题求解作业数据表 销地 产地 B B 产量 C1l C12 11 x12 C21 销量 b b b

考虑产销平衡问题，由于我们关心的量均在表3-1与表 3-2中，因此考虑把表3-1与表3-2合成一个表, 如下表3-3 销地 产地 B1 B2 … Bn 产量 A1 c11 c12 … c1n a1 x11 x12 x1n A2 c21 c22 … c2n a2 x21 x22 x2n … … … … … … Am cm1 cm2 … cmn am xm1 xm2 xmn 销量 b1 b2 … bn 表3-3 运输问题求解作业数据表

森上作业法 表上作业湍:建立在运輪费用矩阵的求解运輪闷题的方湍。 表上作业法求解运輪问题的思想和单纯形法完全类似: 确定一个初始基本可行解一根据最优性判别准则 来检查这个基本可行解是不是录优的? 如果是,则计算结柬; 如果不是,则进行换基。 一直至求出最优解为止

表上作业法: 建立在运输费用矩阵的求解运输问题的方法。 表上作业法求解运输问题的思想和单纯形法完全类似： • 确定一个初始基本可行解 —— 根据最优性判别准则 来检查这个基本可行解是不是最优的？ • 如果是，则计算结束； • 如果不是，则进行换基。 • —— 直至求出最优解为止

森上作业法 单纯形法与表上作业法的关糸: 1)找出初始基可行解 表上给出m十n-1个数字格 (2)求各非基变量的检验数 →计算表中安格检验教 (3)判断是吞最优解 判断方法相 l同 (4)确定换入变量和换出变量找出新的基可行解。 →>表上调整(闭回路调整) (5)重复(2)、(3)直至求出最优解。 (运输问题必有最优解)

单纯形法与表上作业法的关系： (1)找出初始基可行解 (2)求各非基变量的检验数 (3)判断是否最优解 (4)确定换入变量和换出变量找出新的基可行解。 (5)重复(2)、(3)直至求出最优解。 计算表中空格检验数 表上给出m+n-1个数字格 判断方法相同 表上调整(闭回路调整) (运输问题必有最优解)