OR-西安财经学院汇总课件.ppt

1、精品课程运筹学问题的提出问题的提出n一般的运输问题就是要解决把某种产品一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最下，如何确定一个使得总的运输费用最小的方案。小的方案。精品课程运筹学 例例1:1:某公司从两个产地某公司从两个产地A A1 1、A A2 2将物品运往三将物品运往三个销地个销地B B1 1、B B2 2、B B3 3，各产地的产量、各销地各产地的产量、各销地

2、的销量和各产地运往各销地每件物品的运的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运费如下表所示，问：应如何调运可使总运输费用最小？输费用最小？B1 B2 B3 产量产量 A1 6 4 6 200 A2 6 5 5 300 销量销量 150 150 200 精品课程运筹学解：解：产销平衡问题：总产量产销平衡问题：总产量=总销量总销量 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，的运输量，得到下列运输量表：得到下列运输量表：B1 B2 B3 产产 量量 A1 x11 x12 x13 200 A2 x21 x22 x23 300 销销 量量 150 15

3、0 200 精品课程运筹学 min f=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13 =200 x21+x22+x23=300 x11 +x21 =150 x12 +x22 =150 x13 +x23=200 xij0 (i=1,2；j=1,2,3）精品课程运筹学 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系数矩阵精品课程运筹学模型系数矩阵特征模型系数矩阵特征 1.共有共有m+n行，分别表示各产地和行，分别表示各产地和销地；销地；m n列，分别表示各决策变列，分别表示各决

4、策变量；量；2.每列只有两个每列只有两个 1，其余为，其余为 0，分别，分别表示只有一个产地和一个销地被使表示只有一个产地和一个销地被使用。用。精品课程运筹学 一般运输问题的提法：一般运输问题的提法：假设假设 A1,A2,Am 表示某物资的表示某物资的m个产地；个产地；B1,B2,Bn 表示某物资的表示某物资的n个销地；个销地；si表示产地表示产地 Ai 的产量；的产量；dj 表示销地表示销地 Bj 的销量；的销量；cij 表示把物表示把物资从产地资从产地 Ai 运往销地运往销地 Bj 的单位运价。如果的单位运价。如果 s1+s2+sm=d1+d2+dn 则称该运输问题为产销平衡问题；否则，称

5、产则称该运输问题为产销平衡问题；否则，称产销不平衡。销不平衡。精品课程运筹学运输问题数据表运输问题数据表 设设 xij 为从产地为从产地 Ai 运往销地运往销地 Bj 的运输量，的运输量，根据这个运输问题的要求，可以建立运输变根据这个运输问题的要求，可以建立运输变量表。量表。销地销地产地产地B B1 1 B B2 2 B Bn n产量产量A A1 1 A A2 2 A Am mc c1111 c c1212 c c1n1nc c2121 c c2222 c c2n 2n c cm1m1 c cm2m2 c cmnmns s1 1 s s2 2 s sm m销量销量d d1 1 d d2 2 d

6、 dn n 精品课程运筹学运输问题变量表运输问题变量表 销地销地产地产地B1 B2 Bn产量产量A1 A2 Amx11 x12 x1nx21 x22 x2n xm1 xm2 xmns1 s2 sm销量销量d1 d2 dn 精品课程运筹学 m n min f=cij xij （1）i=1 j=1 n s.t.xij si i=1,2,m （2）j=1 m xij(=,)dj j=1,2,n （3）i=1 xij 0(i=1,2,m;j=1,2,n)（4）于是得到下列于是得到下列一般运输问题一般运输问题的模型：的模型：在模型（1）（4）中，式（2）为 m 个产地的产量约束；式（3）为 n 个销地的

7、销量约束。精品课程运筹学 m n min f=cij xij i=1 j=1 n s.t.xij =si i=1,2,m (5)j=1 m xij =dj j=1,2,n (6)i=1 xij 0 (i=1,2,m;j=1,2,n)对于产销平衡问题，可得到下列运输问题的模型：精品课程运筹学 在产销平衡问题在产销平衡问题中，式（中，式（2 2）、（）、（3 3）分别变）分别变为（为（5 5）、（）、（6 6），约束条件成为等式。），约束条件成为等式。在实际问题建模时，还会出现如下一些变化：在实际问题建模时，还会出现如下一些变化：（1 1）有时目标函数求最大，如求利润最大或营）有时目标函数求最大，

8、如求利润最大或营业额最大等；业额最大等；（2 2）当某些运输线路上的能力有限制时，模型）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；中可直接加入（等式或不等式）约束；精品课程运筹学 (3)产销不平衡产销不平衡的情况。当销量大于产量的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，时可加入一个虚设的产地去生产不足的物资，这相当于在式（这相当于在式（2）每一式中加上）每一式中加上 1 个松弛个松弛变量，共变量，共 m 个；当产量大于销量时可加入个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当一个虚设的销地去消化多余的物资，这相当于在式（于在式（

9、3）每一式中加上）每一式中加上 1 个松弛变量，个松弛变量，共共 n 个。个。精品课程运筹学n运输问题是一种特殊的线性规划问题，在求运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，解时依然可以采用单纯形法的思路，如图所如图所示示（下页）。（下页）。n由于运输规划系数矩阵的特殊性，如果直接由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表矩阵特征的基础上建立了针对运输问题的表上作业法。上作业法。n下

10、面主要讨论基本可行解、检验数以及基的下面主要讨论基本可行解、检验数以及基的转换等问题。转换等问题。精品课程运筹学基本可行解是否最优解结束换基是否运输问题的求解思路精品课程运筹学 运输问题求解的有关概念运输问题求解的有关概念 考虑产销平衡问题，由于我们关考虑产销平衡问题，由于我们关心的量均在表（运输问题数据表）心的量均在表（运输问题数据表）与表（与表（运输问题变量表运输问题变量表）中，因此）中，因此考虑把这两个表合成一个表考虑把这两个表合成一个表,如下如下表所示。表所示。精品课程运筹学 销地销地产地产地B1B2Bn产量产量A1 c11 x11c12 x12c1n x1na1 A2 c21 x21

11、c22 x22c2n x2na2 Amcm1 xm1cm2 xm2cmn xmnam销量销量b1b2bn 精品课程运筹学 运输问题的基变量共有运输问题的基变量共有 m+n-1 个，个，A的秩的秩为为 m+n-1。运输问题的运输问题的 m+n-1 个变量构成基变量的个变量构成基变量的充分必要条件是不含闭回路。充分必要条件是不含闭回路。重要概念：重要概念：闭回路、闭回路的顶点闭回路、闭回路的顶点特点特点 运输问题基变量的运输问题基变量的精品课程运筹学定义定义 在上表的决策变量格中，凡是能够排列成下在上表的决策变量格中，凡是能够排列成下列形式的列形式的 xab,xac,xdc,xde,xst,xsb

12、 (7)(7)或或 xab,xcb,xcd,xed,xst,xat (8)(8)其中，其中，a,d,s 各不相同；各不相同；b,c,t 各不相各不相同，我们称之为变量集合的一个闭回路，并将同，我们称之为变量集合的一个闭回路，并将式（式（7 7）、式（）、式（8 8）中的变量称为这个闭回路的）中的变量称为这个闭回路的顶点。顶点。为了说明这个特征，我们不加证明的给出一些概念和结论。下面的讨论建立在表4-5中决策变量格的基础上。精品课程运筹学例如，例如，x13,x16,x36,x34,x24,x23 ；x23,x53,x55,x45,x41,x21；x11,x14,x34,x31等都是闭回路。等都是

13、闭回路。若把闭回路的各变量格看作节点，若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：在表中可以画出如下形式的闭回路：闭回路示意图精品课程运筹学 根据定义可以看出闭回路的一些明显特根据定义可以看出闭回路的一些明显特点：点：(1)(1)闭回路均为一封闭折线，它的每一闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；条边，或为水平的，或为垂直的；(2)(2)闭回路的每一条边（水平的或垂直闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量的）均有且仅有两个闭回路的顶点（变量格）。格）。精品课程运筹学 关于闭回路有如下的一些重要结论：关于闭回路有如下的一些重要结

14、论：(1)设设 xab,xac,xdc,xde,xst,xsb 是一个闭是一个闭回路，那么该闭回路中变量所对应的系数列向回路，那么该闭回路中变量所对应的系数列向量量 pab,pac,pdc,pde,pst,psb 线性相关；线性相关；(2)若变量组若变量组 xab,xcd,xef,xst 中包含一个部中包含一个部分组构成闭回路，那么该变量组所对应的系数分组构成闭回路，那么该变量组所对应的系数列向量列向量 pab,pcd,pef,pst 线性相关。线性相关。根据上述结论以及线性规划基变量的特点，可根据上述结论以及线性规划基变量的特点，可以得到下面重要定理及其推论。以得到下面重要定理及其推论。精品课程运筹学定理定理1 变量组变量组 xab,xcd,xef,xst 所对应的系数所对应的系数列向量列向量 pab,pcd,pef,pst 线性无关的充分线性无关的充分必要条件是这个变量组中不包含闭回路。必要条件是这个变量组中不包含闭回路。推论推论 产销平衡运输问题的产销平衡运输问题的 m+n-1 个变量构成个变量构成基变量的充分必要条件是它不含闭回路。基变量的充分必要条件是它不含闭回路。这个推论给出了运输问题基本解的重要性这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据。质，也为寻求基本可行解提供了依据。精品课程运筹学