北邮运筹学ch3-4 运输问题的变体.ppt

1、北京邮电大学 运筹学,2020/12/9,设数学模型为,求极大值问题,北京邮电大学 运筹学,2020/12/9,第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）mn，用一个较大的数M（MmaxCij）去减每一个Cij得到矩阵C/=（Cij）mn ，其中C/ij=MCij0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为,例如，下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.,8 14 9,北京邮电大学 运筹学,2020/12/9,用最小元素法求初始方案得,11=8,12=4,21=2,23=2全部非负

2、,得到最优运输方案X,最大利润Z=89+1010+68+54=240,第二种方法:所有非基变量的检验数ij0时最优.求初始运输方案可采用最大元素法.,如上例,用最大元素得到 的初始运输方案:,8 14 9,求检验数:11=8,12=4,21=2,23=2,全部非正,得到最优解运输方案,结果与第一种方法相同.,北京邮电大学 运筹学,2020/12/9,不平衡运输问题 : 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。,当产大于销时,即,数学模型为,北京邮电大学 运筹学,2020/12/9,由于总产量大于总销量，

3、必有部分产地的产量不能全部 运送完，必须就地库存，即每个产地设一个仓库，库存量 为xi，n+1（i=1，2，m），总的库存量为,北京邮电大学 运筹学,2020/12/9,bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：,具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可,北京邮电大学 运筹学,2020/12/9,当销大于产时,即,数学模型为,北京邮电大学 运筹学,2020/12/9,由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为,xm+1,j 是Am+

4、1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2, ,n),北京邮电大学 运筹学,2020/12/9,销大于产平衡问题的数学模型为 ：,具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。,北京邮电大学 运筹学,2020/12/9,因为有：,看一个例题：求下列表中极小化运输问题的最优解。,北京邮电大学 运筹学,2020/12/9,所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20，Ci5=0，i=1，2，3，4。表的右边增添一列,这样我们可得新的运

5、价表：,北京邮电大学 运筹学,2020/12/9,下表为计算结果。可看出：产地A4还有20个单位没有运出。,需求量不确定的运输问题,上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,北京邮电大学 运筹学,2020/12/9,先作如下分析：（1）总产量为180，B1，B4的最低需求量20+50+35+45=150，这时属产大于销；,（2）B1，B4的最高需求是60+70+35+45=210，这时属销大于产；,（3）虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,（4）将B1与B2各分成两部分， 的需求量是20， 的需求量是4

6、0， 的需求量分别是50与20，因此 必须由A1，A4供应， 可由 A1、A5供应。,（5）上述A5不能供应某需求地的运价用大M表示，A5到 、 的运价为零。得到下表的产销平衡表。,得到这样的平衡表后，即可应用QSB软件计算得到最优方案。,北京邮电大学 运筹学,2020/12/9,表324中x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,北京邮电大学 运筹学,2020/12/9,【例12】（教材P93例3）,每台每季度的存储费为0.15万元。求全年总费用最小的生产决策。,应用,北京邮电大学 运

7、筹学,2020/12/9,【解】设xij为第i季度生产的柴油机用于第j季度交货的数量（台），费用表为：,北京邮电大学 运筹学,2020/12/9,数学模型为：,北京邮电大学 运筹学,2020/12/9,这是一个产大于销的运输问题，加一个虚拟销地D，得到平衡运价表：,北京邮电大学 运筹学,2020/12/9,最优解如下表（最优方案不唯一），总费用为773万元。,北京邮电大学 运筹学,2020/12/9,用表上作业法求运输问题的最优解要比用单纯法求解简单，另外有些问题可以用图上作业法。,运输问题总有基本可行解而且有最优解，当某个非基变量的检验数等于零时，有无穷多个最优解。运输问题的应用比较广泛。,北京邮电大学 运筹学,2020/12/9,本章介绍了运输模型的特征；,运输模型的