运输与指派模型问题

《运输与指派模型问题》由会员分享，可在线阅读，更多相关《运输与指派模型问题（30页珍藏版）》请在装配图网上搜索。

1、运筹学运筹学Operations ResearchChapter 7 运输与指派问题运输与指派问题Transportation and Assignment Problem7.1运输模型运输模型 Mathematical Model of Transportation Problems7.2 运输单纯形法运输单纯形法 Transportation Simplex Method7.3 运输模型的应用运输模型的应用 Aplication of Transportation Model7.4 指派问题指派问题 Assignment problem 7.1 运输模型运输模型 Mathematical

2、Model of Transportation Problems人们在从事生产活动中，不可人们在从事生产活动中，不可避免地要进行物资调运工作。避免地要进行物资调运工作。如某时期内将生产基地的煤、如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别钢铁、粮食等各类物资，分别运到需要这些物资的地区，根运到需要这些物资的地区，根据各地的据各地的生产量生产量和和需要量需要量及各及各地之间的地之间的运输费用运输费用，如何制定，如何制定一个运输方案，使总的运输费一个运输方案，使总的运输费用最小。这样的问题称为用最小。这样的问题称为运运输问题输问题。7.1 运输模型运输模型 Model of Transpo

3、rtation Problems7.1.1 数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图7.1【例【例7.1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应 粮食分别为粮食分别为10，8，5（万吨），现将粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表71所示所示.问如何安排一个运输计划，使总的运输费用问如何安排一个运输计划，使总的运输费用最少。最少。

4、地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表（元运价表（元/T）表表71设设 xij(i=1,2,3；j=1,2,3,4)为为i个产粮地个产粮地运往运往第第j个需求地个需求地的运量，的运量，21221112132324143132333453822293634xxxxxxxxxZxxx则运输费用为：则运输费用为：地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量

5、578323从产粮区运出去的量从产粮区运出去的量5810343332312423222114131211xxxxxxxxxxxx运给运给需求地需求地的量的量3875342414332313322212312111xxxxxxxxxxxx地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323111213142122232431323334min32635382429Zxxxxxxxxxxxx5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxx

6、xxxxx运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 4,3,2,13,2,1,0jixij；这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型【例【例7.2】有三台机床加工三种零件，有三台机床加工三种零件，计划第计划第i台的生产任务为台的生产任务为a i (i=1,2,3)个零件个零件(三种零件三种零件)，第第 j 种零件的需要量为种零件的需要量为 bj (j=1,2,3)，第第 i 台机床加工第台机床

7、加工第j种零件需要的时间为种零件需要的时间为 cij，如下表所示。如下表所示。问如何安排生产任务使总的加工时间最少？问如何安排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150 【解】【解】设设 xi j (i=1,2,3；j=1,2,3,)为第为第 i 台机床加工第台机床加工第 j 种零件种零件的数量，的数量，11121222321313233364537342Zxxxxxxxxx 零件零件机床机床B1B2B3生产生产任务任务A152350A264160A373440需要需要量量7030501501

8、11213212223313233506040 xxxxxxxxx 则总的加工时间为则总的加工时间为112131122232132333703050 xxxxxxxxx111213212223313233111213212223313233112131122232132333min523647345060407030500,1,2,31,2,3,ijZxxxxxxxxxxxxxxxxxxxxxxxxxxxxij ；则此问题的数学模型为则此问题的数学模型为运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产某种物资，其产），生产某种物资，其

9、产量分别为量分别为a1,a2，am；有；有n个销地（记作个销地（记作B1，B2，Bn），），其需要量分别为其需要量分别为b1,b2，bn；且；且产销平衡产销平衡，即，即 。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij，在满足各地需要的前提，在满足各地需要的前提下，求总运输费用最小的调运方案。下，求总运输费用最小的调运方案。设设 xij (i=1,2,，m；j=1,2,n)为第为第i个产地到第个产地到第j个销地的运量，个销地的运量，则数学模型为：则数学模型为：njjmiiba11njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,1;,

10、1,0,1,111则数学模型为：则数学模型为：设数学模型为设数学模型为 minjijijxCZ11maxnjmixnjbxmiaxijmijijnjiij,2,1;,2,10,2,1,2,111，7.1.2最大值问题最大值问题第一种方法：第一种方法：将极大化问题转化为极小化问题。将极大化问题转化为极小化问题。设极大化问题的运价表为设极大化问题的运价表为C=（Cij）mn，用一个较大的数，用一个较大的数M（MmaxCij）去减每一个）去减每一个Cij得到矩阵得到矩阵C=（Cij）mn，其中，其中C/ij=MCij0,将将C/作为极小化问题的运价表，用表上用业法求作为极小化问题的运价表，用表上用业

11、法求出最优解，目标函数值为出最优解，目标函数值为 11mnijijijZxC 当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问题在这类运输问题在实际中常常碰到实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。衡问题求解。1.当产大于销时当产大于销时,即即 7.1.3 不平衡运输问题不平衡运输问题 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量100100801.当产大于销时当产大于销时 11mnijijab数学模型为数学模型为 mi

12、njijijxCZ11minnjmixnjbxmiaxijmijijnjiij,2,1;,2,10,2,1,2,111，即即由于总产量大于总销量，由于总产量大于总销量，必有部分产地的产量不能全部必有部分产地的产量不能全部运送完运送完，必须就地库存，即每个产地设一个仓库，库存量，必须就地库存，即每个产地设一个仓库，库存量为为xi，n+1（i=1，2，m），总的库存量为），总的库存量为 njjmiimininmnnnbaxxxxb1111,1,1,21,11bn+1作为一个作为一个虚设的销地虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，的运价为零，即即Ci，n+1=0,

13、（i=1，m）。则平衡问题的数学模型为：）。则平衡问题的数学模型为：minjijijxCZ11min,2,1,2,1,01,2,1,2,1111jmixnjbxmiaxijmijijnjiij；具体求解时具体求解时,只在运价表右端增加一列只在运价表右端增加一列Bn+1，运价为零，运价为零,销量为销量为bn+1即可即可2.当销大于产时当销大于产时,即即 BjAiB1B2B3产产 量量A1659120 A212107100A3698130销销 量量2001001502.当销大于产时当销大于产时,即即minjjiba11数学模型为数学模型为 minjijijxCZ11minnjmixnjbxmiax

14、ijmijijnjiij,2,1;,2,1,0,2,1,2,111由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时这时虚设虚设一个产地一个产地Am+1，产量为，产量为 nmmmmxxxa,121111，njmiijnjjmabx1111,xm+1,j 是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运价为零的运价为零,即即Cm+1,j=0(j=1,2,n)销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：11mi nmni ji jijZCx 1111,2,11,2,0,1

15、,2,11,2,ni jijmijjiijxaimxbjnximjn ；具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。，运价为零。产量为产量为am+1即可。即可。上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要量是的需要量是50到到70，试求极小化问题的最优解。试求极小化问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502107.1.4需求量不确定的运输问题需求量不确定的运输问题先作如下分析：先作如下分析：（1）总产量为总产量为

16、180，B1，B4的最低需求量的最低需求量 20+50+35+45=150 180，这时属这时属销大于产销大于产;B1B2B3B4aiA1592360A2-47840A3364230A448101150bj206050703545180150210（3）虚设一个产地虚设一个产地A5，产量是，产量是210180=30，A5的产量只能供应的产量只能供应B1或或B2。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj206050703545180150210（4）将将B1与与B2各分成两部分各分成两部分 的需求量是的需求量是20，的需求量是的需求量是40，的

17、需求量分别是的需求量分别是50与与20，因此，因此 必须由必须由A1，A4供应，供应，可由可由 A1、A5供应。供应。1122122111BBBBB，、及、21B2212BB 与1211BB、2221BB、B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj20405020354521011B21B12B22B（5）上述上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到 、的运价为零。得到下表的产销平衡表。的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A3

18、33664230A44488101150A5M0M0MM30bj20405020354521011B21B12B22B7.1.5中转问题中转问题产地销地 A1 20 A2 30 A3 50 A9 20 A8 15 A7 20 A6 45354231682329图图5.2 A4 A522715中转地3413设设xij为为Ai到到Aj的运量，的运量，i，j=1，2，m+n+r则中转运输问题则中转运输问题的数学模型为的数学模型为(,)min1,2,(5.3)01,2,(5.3)1,2,(5.3)0,1,2,ijiji jijijiikjikkijijjjijZc xxxaimAaxxkrAbxxbjnAcxi jmnr流出弧流入弧流出弧流入弧流入弧流出弧对发点中间点对收点产大于销时将式产大于销时将式(5.3a)改为改为“”约束，销大于产时将式约束，销大于产时将式(5.3c)改改为为“”约束约束