北邮运筹学ch3-2 基变量与闭回路.ppt

1、北京邮电大学 运筹学,2020/7/22,设平衡运输问题的数学模型为：,北京邮电大学 运筹学,2020/7/22,【定理1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。,【证】因为产销平衡，即 ，将前m个约束方程两边相加得,再将后n个约束相加得,显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵,北京邮电大学 运筹学,2020/7/22,中任意m+n阶子式等于零，取第一行到m+n1行与 对应的列（共m+n-1列）组成的m+n1阶子式,北京邮电大学 运筹学,2020/7/22,故r(A)=m+n1所以运输问题有m+n1个基变量。,为了在mn个变

2、量中找出m+n1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。,北京邮电大学 运筹学,2020/7/22,为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表33及表34中的变量组构成两个闭回路。,x23,x43,x11,x12,x25,x31,x42,表33,表33中闭回路的变量集合是x11,x12,x42, x 43, x 23, x 25, x 35, x 31共有8个顶点， 这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,北京邮电大学 运筹学,2020/7/22,表34,一条回路中的顶点数

3、一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表33中的变量x 32及x33不是回闭路的顶点，只是连线的交点。,表34中闭回路是,例如变量组,A不能组成一条闭回路，但A中包含有闭回路,B的变量数是奇数，显然不是闭回路，也不含有闭回路；,北京邮电大学 运筹学,2020/7/22,C是一条闭回路，若把C重新写成 就不难看出C仍是一条闭回路。,【定理2】 若变量组B 包含有闭回路 ，则B中的变量对应的例向量线性相关。,【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即,因而C中的列向量线性相关，所以B中列向量线性相关。,北京邮

4、电大学 运筹学,2020/7/22,由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。,求运输问题的一组基变量，就是要找到m+n1个变量，使得它们对应的系数列向量线性无关，由定理2，找这样的一组变量是很容易的，只要m+n1个变量中不包含闭回路，就可得到一组基变量。因而有：,【定理3】m+n1个变量组构成基变量的充要条件是它不包含任何闭回路。,定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。,北京邮电大学 运筹学,2020/7/22,例如，m=3,n=4，在运价表Cij的格子的右上方填上相应的xij，如表3-5所示。,表35,北京邮电大学 运筹学,2020/7/22,这个运输问题的基变量数目是3+41=6。变量组中 有7个变量，显然不能构成一组基变量，又如 中有6个变量，但包含有一条闭回路 故不能构成一组基变量。变量组 有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。,北京邮电大学 运筹学,2020/7/22,表上作业法,作业：P98 T3.1,本节