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

§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage1of22北京邮电大学运筹学2020/2/23设数学模型为minjijijxCZ11maxnjmixnjbxmiaxijmijijnjiij,,2,1;,2,10,,2,1,,2,111，求极大值问题§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage2of22北京邮电大学运筹学2020/2/23第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C/=（C′ij）m×n，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为minjijijxCZ11'.例如，下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.4567109852C121098149则取ijijijCCCCM10,10max/22654301258/C§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage3of22北京邮电大学运筹学2020/2/23用最小元素法求初始方案得048109Xλ11=8,λ12=4,λ21=2,λ23=2全部非负,得到最优运输方案X,最大利润Z=8×9+10×10+6×8+5×4=240第二种方法:所有非基变量的检验数λij≤0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到的初始运输方案:048109X4567109852C121098149求检验数:λ11=－8,λ12=－4,λ21=－2,λ23=－2,全部非正,得到最优解运输方案,结果与第一种方法相同.§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage4of22北京邮电大学运筹学2020/2/23不平衡运输问题:当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。当产大于销时,即minjjiba11数学模型为minjijijxCZ11minnjmixnjbxmiaxijmijijnjiij,,2,1;,2,10,,2,1,,2,111，§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage5of22北京邮电大学运筹学2020/2/23由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为njjmiimininmnnnbaxxxxb1111,1,1,21,11§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage6of22北京邮电大学运筹学2020/2/23bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为：minjijijxCZ11min,2,1,2,1,01,,2,1,,2,1111jmixnjbxmiaxijmijijnjiij；具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage7of22北京邮电大学运筹学2020/2/23当销大于产时,即minjjiba11数学模型为minjijijxCZ11minnjmixnjbxmiaxijmijijnjiij,,2,1;,,2,1,0,,2,1,,2,111§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage8of22北京邮电大学运筹学2020/2/23由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为nmmmmxxxa,121111，＋，＋＋njmiijnjjmabx1111,xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,…,n)§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage9of22北京邮电大学运筹学2020/2/23销大于产平衡问题的数学模型为：minjijijxCZ11minnjmixnjbxmiaxijmijijnjiji,,2,11,,2,1,0,,2,11,,2,1111；具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage10of22北京邮电大学运筹学2020/2/23B1B2B3B4aiA1592360A2--47840A3364230A448101150bj206035451801604141160180ijjiba因为有：看一个例题：求下列表中极小化运输问题的最优解。§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage11of22北京邮电大学运筹学2020/2/23所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180－160=20，Ci5=0，i=1，2，3，4。表的右边增添一列这样我们可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj2060354520180§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage12of22北京邮电大学运筹学2020/2/23B1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地A4还有20个单位没有运出。需求量不确定的运输问题上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage13of22北京邮电大学运筹学2020/2/23先作如下分析：（1）总产量为180，B1，…，B4的最低需求量20+50+35+45=150，这时属产大于销；（2）B1，…，B4的最高需求是60+70+35+45=210，这时属销大于产；（3）虚设一个产地A5，产量是210－180=30，A5的产量只能供应B1或B2。（4）将B1与B2各分成两部分，的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，…，A4供应，可由A1、…、A5供应。1122122111BBBBB，、及、21B2212BB与1211BB、2221BB、（5）上述A5不能供应某需求地的运价用大M表示，A5到、的运价为零。得到下表的产销平衡表。§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage14of22B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521011B21B12B22B得到这样的平衡表后，即可应用QSB软件计算得到最优方案。§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage15of22北京邮电大学运筹学2020/2/23B3B4aiA1352560A24040A30102030A4203050A5102030bj20405020354511B21B12B22B表3－24中x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage16of22北京邮电大学运筹学2020/2/23【例12】（教材P93例3）季度需求量（台）生产能力（台）单位成本（万元）1102510．82153511．13253011．04201011．3每台每季度的存储费为0.15万元。求全年总费用最小的生产决策。应用§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage17of22北京邮电大学运筹学2020/2/23【解】设xij为第i季度生产的柴油机用于第j季度交货的数量（台），费用表为：ij1234110.810.9511.111.25211.111.2511.4311.011.15411.3§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage18of22北京邮电大学运筹学2020/2/23数学模型为：444342413433323124232221141312113.1115.11114.1125.111.1125.111.1195.108.10minxMxMxMxxxMxMxxxxMxxxxxZ4,,1,010303525202515104434332423221413121144342414332313221211jixxxxxxxxxxxxxxxxxxxxxij、§3.4运输问题的变体VariantsofTransportationProblemsCh3TransportationProblemPage19of22北京邮电大学运筹学2020/2/23这是一个产大于销的运输问题，加一个虚拟销地D，得到平衡运价表：销地产地1234D产量110.810.9511.111.250252M11.111.2511.400353MM1111.150304MMM11.3010销量1015252030§3.4运输问题的变体VariantsofTran