运筹学-运输问题的表上作业法(名校讲义)(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第十讲,运输问题的表上作业法,1,运输问题事例,2,运输问题的一般形式,3,表上作业法,1,运输问题事例,（,1,）,已知，有,4,个产地（源点）生产的产品需销售到,4,个需求地（目,的地或汇点），其源点产量和目的地需求量见表,1-5,。,表,1-5,运输问题的需求量及产量,目的地,需求量,源点,产量,1,2,3,4,总计,22,28,17,23,90,1,2,3,4,总计,24,18,12,36,90,其源点到目的地的单位产品的运费价格见图,1-7,。,1,运输问题事例,（,2,）,费 目,用 的,源点 地,1,2,3,4,1,2,3,4,24,18,12,36,22 28 17 23,图,1-7,运输费用矩阵,表格旁边数字为产量和需要求量,2,运输问题的一般形式,r,i,源,i,产量，,a,j,目的地,j,的需求量。,3,表上作业法,（,1,）,与单纯形表格法一样，该法亦分两步进行：,求出初始基础可行解,求出最优解,1,用最小元素法求出满意的初始基础可解,其方法是，按照费用矩阵元素,C,ij,增长顺序逐个选择引入基,本解的变量,x,ij,，非退化情况下，每选择,1,个，就必然排除,1,个源点或目的地，最后一步可一次排除,1,个源点和,1,个目的,地，这样便可得到一个初始基础可行解。,3,表上作业法,（,2,）,以上例考察，观察图,1-7,。,min,c,ij,=,c,22,=1,。故优先分配源,2,和目的地,2,之间的产品,图,1-8,最小元素法第,1,步,18,24,0,12,22,17,10,23,36,18,28,3,表上作业法,（,3,）,余下元素中，最小值为,c,32,=2,。,图,1-9,最小元素法第,2,步,依此类推，最后获初始基础可行解示如图,1-10,中。,18,12,24,0,12,22,17,10,23,36,18,28,0,5,3,表上作业法,（,4,）,图,1-10,初始基础可行解,即基础解为：,x,11,=22,，,x,12,=18,，,x,33,=12,x,42,=8,，,x,43,=5,，,x,44,=23,。,此时总费用为,225,。,22,2,18,12,8,5,23,3,表上作业法,（,5,）,2,求出最优解,这有两种方法：闭回路法和位势法。,闭回路法，其思路是令表中空格（即非基础解），对应的变量由,0,增加,d,单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基础解参与变动，看其费有如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致。,现继上图继续改进基础解，直至达优。,i),参见图,1-11,，分析非基变量,x,32,增加,d,单位以后，其它基础解及费用变化。,3,表上作业法,（,6,）,22,2,24,18,18,+d,12-d,12,8-d,5+d,23,36,22,28,17,23,2,求出最优解,图,1-11,回路法原理,3,表上作业法,（,7,）,为使供求平衡，必须符合：,x,32,+,d,x,42,d,x,43,+,d,x,33,d,变动后，费用增加值为：,8,d,5,d,+4,d,2,d,=5,d,，即费用增加，,x,32,不能进基，为比较，把增加,1,个单位产品所引起的费用增加值填入相应的非基变量表格内，这又称检验值。,注意，在用回路法求解每个非基变量检验值时，在根据供求平衡寻找闭合回路过程中，其回路转折点必须是基础解！,例如，分析非基解,x,31,x,11,x12,x,42,x,43,x,33,x,31,。,3,表上作业法,（,8,）,22,2,24,18,18,12,12,8,5 ,23,36,22,28,17,23,9,6,9,5,-3,7,4,5,-1,对每个非基变量计算后，将其检验值填入图,1-12,中。,图,1-12,回路法计算结果,其中：,内表示费用元素,内表示检验值 表内其它值为基础解。,3,表上作业法,（,9,）,ii),观察表格，或检验值全部,0,，已达最优胜，结束。,否则，选取最负的检验值所对的非基变量，令其进基。图,1-12,中，,x,13,的检验值为最负，故令,x,13,进基，应使,x,13,尽量大，但又必须使其它变量非负观察,x,13,变化规律：,x,13,x,12,x,42,x,43,。,应取下降变量中的最小值作为,x,13,的值。此时,min,x,12,，,x,43,=min2,，,5=2,。故令,x,13,=2,则,x,12,=0,，,x,42,=10,，,x,43,=3,。,将图,1-12,修正后，再求出当前非变量的检验值，示如图,1-13,。,非基础解的检验数合为正，故获最成解，总费用为,249,。,3,表上作业法,（,10,）,22,2 ,24,18,18,12,12,10,3 ,23,36,22,28,17,23,6,3,6,3,5,7,4,5,2,图,1-13,回路法所得最优表格,3,表上作业法,（,11,）,位势法（简捷法）,该法对运输费用矩阵表格每次可确定一组,“,行值,”,和,“,列值,”,。确定原则为使得每个基础变量之费用,c,ij,等于相应得行、列值之和，根据该原则求出行列值之后，用这些值再去求解每个非基本变量的检验数。,结合本例阐述该步骤：（见图,1-14,）,3,表上作业法,（,12,）,图,1-14,用位势法求解实例,22,2,24,18,18,12,12,8,5 ,23,36,22,28,17,23,9,6,9,-3,5,7,4,5,-1,S,1,S,2,S,3,S,4,t,1,t,2,t,3,t,4,3,表上作业法,（,13,）,i),令,s,i,，,t,j,分别为行值和列值,求解方程：,s,i,+,t,j,=,c,ij,x,ij,B,基集,从方程知，共有,m,+,n,1,个方程和,m,+,n,个未知量。由于我们感兴趣的是相对值，故可令任一个行值或列值等于某个固定值，例如令,t,1,=0,，即可求出各行、列值，可见“行”“列”值不是唯一的。,对于本例，令,t,1,=0,后，,解联立方程：,3,表上作业法,（,14,）,ii),根据已得的,s,i,，,t,j,值求出非基础的检验值（或成本变动值）,ij,：,ij,=,c,ij,(,s,i,+,t,j,),例如：图,1-14,中，,13,=,c,13,(,s,1,+,t,3,),5,(3+5)=-3,若13,0,则可进入基，根据此法求出所有非基本变量对应的检验值（成本变动值）后，选取,min,ij,(,ij,0),所对应的变量进入基础解。图,1-14,中得知，,13,=-3,为最小值，令,x,13,进基，采用回路法找出应离开的基变量，重新调整后，仍按上述步骤反复运算，最后得出最优解。,现在看位势法的对偶解释：,结合本例，示如表,1-6,中。,3,表上作业法,（,15,）,表,1-6,位势法的对偶解释,x,11,+,x,12,+,x,13,+,x,14,=24,x,21,+,x,22,+,x,23,+,x,24,=18,x,31,+,x,32,+,x,43,+,x,44,=12,x,41,+x,42,+,x,43,+,x,44,=36,x,11,+,x,21,+,x,31,+,x,41,=22,x,12,+,x,22,+,x,32,+,x,42,=28,x,13,+x,23,+x,33,+x,43,=17,x,14,+,x,24,+,x,34,+,x,44,=23,(,r,1,),s,1,(,r,2,),s,2,(,r,3,),s,3,(,r,4,),s,4,(,a,1,),t,1,(,a,2,),t,2,(,a,3,),t,3,(,a,4,),t,4,c,11,c,12,c,13,c,14,.,c,44,3,表上作业法,（,16,）,表,1-6,列出了本例的供求关系的,8,个约束方程。,（由于 ，故只有,7,个独立约束方程）。,该规划的对偶约束必为：,3,表上作业法,（,17,）,显然，,s,i,，,t,j,即是对偶问题的对偶变量,y,。共,8,个对偶变量，,每次送代时有,7,个基础解变量，可写出,7,平衡方程式：,s,i,+,t,j,=,c,ij,(,x,ij,B,),这与上面分析完全一致。因此，位势法实质每一步都是首,先求解对偶方程的平衡解，这与单纯形法思路相同。,唯一差别是，本文在单纯形法引进的检验数为,z,s,c,s,，而运,输问题引进的检验值,c,s,z,s,，相差一符号，这并无本质差,别，只是判断时注意即可。,