最优化理论运输问题.ppt

*例如在表4-9所表示的运输问题中，用最小元素法得到的初始调运方案如下表所示.销地产地B1B2B3B4uiA131143310u1A2319128u2A37641035u3vjv1v2v3v4在此调运方案中，我们可以根据基变量对应的单位运输费用cij算出ui和vj.计算方程组是：第53页，讲稿共84页，2023年5月2日，星期三*销地产地B1B2B3B4uiA1311433100A2319128-1A37641035-5vj29310该方程组含6个方程和7个未知数，因而有一个未知数是自由变量，通常我们令u1=0，此时可得到所有ui(i=1,2,…m)和vj(j=1,2,…,n)的值，如下表4-29所示.第54页，讲稿共84页，2023年5月2日，星期三*根据ui和vj的值算出所有空格处（即非基变量）的检验数，计算公式为cij-(ui+vj)，计算结果如下表4-30方括号数字所示，这和用闭回路法得到的检验数结果一致.销地产地B1B2B3B4uiA1311433100[1][2]A2319128-1[1][-1]A37641035-5[10][12]vj29310因为检验数，故这个解不是最优解，因此我们再根据闭回路法进行调整，直至得出最优解.第55页，讲稿共84页，2023年5月2日，星期三*表上作业法在计算中可能还会出现一些问题，这里我们需要说明.1.当迭代到运输问题的最优解时，如果有某个非基变量的检验数等于零，则说明该运输问题有无穷多最优解.2.退化(1)当确定供需关系时，如果某个产地的剩余产量等于某个销地的需量，这时就要划去一行和一列，此时需要添加一个0，它的位置可在对应划去的那行或那列的任意处.(2)在用闭回路法调整时，如果闭回路奇数拐弯处具有两个或两个以上相等的最小值，此时经调整后，得到退化解，这时有一个数字格必须填0，以表示它是基变量.第56页，讲稿共84页，2023年5月2日，星期三*4.3产销不平衡的运输问题上一节讲到运输问题的表上作业法，是以总产量等于总销量（即产销平衡）为前提的.实际上，在很多运输问题中，总产量并不等于总销量.为了使用表上作业法求解，我们可以将产销不平衡的运输问题转化为产销平衡运输问题.如果总产量大于总销量，即这时运输问题的数学模型为：（4.5）第57页，讲稿共84页，2023年5月2日，星期三*由于总产量大于总销量，因而要考虑多余物资就地贮存的问题.为借助产销平衡运输问题的表上作业法，可增加一个假想的销地Bn+1，由各产地Ai(i=1,2,…,m)运送到这个销地Bn+1物资的数量设为，实际上就是产地Ai就地贮存物资的数量，显然单位运价.因此假想后原问题的最优总费用与假想之前的最优总费用是一致的.由于总产量剩余为使产销平衡，可假设销地Bn+1的销量此时模型（4.5）可以变为：（4.6）第58页，讲稿共84页，2023年5月2日，星期三*销地产地B1B2…BnBn+1产量A1X11c11X12c12X1nc1nX1，n+10a1A2X21c21X22c22X2nc2nX2，n+10a2…AmXm1cm1Xm2cm2XmncmnXm，n+10am销量b1b2bn可以看出，模型（4.6）是有m个产地，n+1个销地的产销平衡运输问题，因而通过假想销地，可将产大于销的运输问题转化为产销平衡运输问题.和模型（4.6）对应的运输表如下表所示.第59页，讲稿共84页，2023年5月2日，星期三*（2）向a1,b1中较大数方向移动一格（或向右，或向下），这里是向右移动一格，移动到(A1,B2)位置.B2需要6个单位物资，而A1只剩有4个单位，故在(A1,B2)处填4，A1的物资已经全部发完，划去A1行，如下表4-11所示.销地产地B1B2B3B4产量A1334113107A219284A3741059销量3656第21页，讲稿共84页，2023年5月2日，星期三*（3）继续按照上