运筹学 北京邮电大学.ch3-2.ppt

《运筹学 北京邮电大学.ch3-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、设平衡运输问题的数学模型为：9/18/2021【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。【证】因为产销平衡，即，将前m个约束方程两边相加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵9/18/2021中任意m+n阶子式等于零，取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式9/18/2021故r(A)=m+n－1所以运输问题有m+n－1个基变量。为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下

2、面引用闭回路的概念寻找这些基变量。9/18/2021为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表3－3及表3－4中的变量组构成两个闭回路。x23B1B2B3B4B5A1A2A3x35A4x43x11x12x25x31x42表3－3表3－3中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。9/18/2021x11x12x32x33x41B1B2B3A1A2A3A4x43表3－4一条回路中的顶点数一定是偶数，回路遇到顶点必

3、须转90度与另一顶点连接，表3－3中的变量x32及x33不是回闭路的顶点，只是连线的交点。表3－4中闭回路是例如变量组A不能组成一条闭回路，但A中包含有闭回路B的变量数是奇数，显然不是闭回路，也不含有闭回路；9/18/2021C是一条闭回路，若把C重新写成就不难看出C仍是一条闭回路。【定理2】若变量组B包含有闭回路，则B中的变量对应的例向量线性相关。【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即因而C中的列向量线性相关，所以B中列向量线性相关。9/18/2021由定理2可知，当一个变量组

4、中不包含有闭回路，则这些变量对应的系数向量线性无关。求运输问题的一组基变量，就是要找到m+n－1个变量，使得它们对应的系数列向量线性无关，由定理2，找这样的一组变量是很容易的，只要m+n－1个变量中不包含闭回路，就可得到一组基变量。因而有：【定理3】m+n－1个变量组构成基变量的充要条件是它不包含任何闭回路。定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。9/18/2021例如，m=3,n=4，在运价表Cij的格

5、子的右上方填上相应的xij，如表3-5所示。表3－5BjAiB1B2B3B4aiA1x11x12x13x14a1C11C12C13C14A2x21x22x23x24a2C21C22C23C24A3x31x32x2x34a3C31C32C33C34bjb1b2b3b49/18/2021这个运输问题的基变量数目是3+4－1=6。变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。9/18/2021表上作业法作业：P98T3.1本节介绍了具有m个产地

6、n个销地的平衡运输问题时：1.具有m+n－1个基变量2.闭回路的概念3.怎样判断m+n－1个变量是否构成一组基变量Exit9/18/2021