运输与指派模型问题

运输与指派模型问题第一页，共三十页，2022年，8月28日2023/3/1017.1运输模型

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

ModelofTransportationProblems7.1.1数学模型产地销地

A110

A2

8

A35

B43

B38

B27

B15354231682329图7.1第三页，共三十页，2022年，8月28日2023/3/103【例7.1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表7－1所示.问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表7－1第四页，共三十页，2022年，8月28日2023/3/104设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，则运输费用为：地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323第五页，共三十页，2022年，8月28日2023/3/105地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323从产粮区运出去的量第六页，共三十页，2022年，8月28日2023/3/106运给需求地的量地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323第七页，共三十页，2022年，8月28日2023/3/107运量应大于或等于零（非负要求），即这样得到下列运输问题的数学模型：第八页，共三十页，2022年，8月28日2023/3/108

有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型【例7.2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件(三种零件)，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如下表所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150第九页，共三十页，2022年，8月28日2023/3/109

【解】设xij

(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，零件机床B1B2B3生产任务A152350A264160A373440需要量703050150则总的加工时间为第十页，共三十页，2022年，8月28日2023/3/1010则此问题的数学模型为第十一页，共三十页，2022年，8月28日2023/3/1011运输问题的一般数学模型设有m个产地（记作A1，A2，A3,…,Am），生产某种物资，其产量分别为a1,a2，…，am；有n个销地（记作B1，B2，…，Bn），其需要量分别为b1,b2，…，bn；且产销平衡，即

。从第i个产地到j个销地的单位运价为cij，在满足各地需要的前提下，求总运输费用最小的调运方案。设xij(i=1,2,…，m；j=1,2,…,n)为第i个产地到第j个销地的运量，则数学模型为：第十二页，共三十页，2022年，8月28日2023/3/1012则数学模型为：第十三页，共三十页，2022年，8月28日2023/3/1013设数学模型为

最大值问题第十四页，共三十页，2022年，8月28日2023/3/1014第一种方法：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C′=（C′ij）m×n

，其中C/ij=M－Cij≥0,将C/作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为第十五页，共三十页，2022年，8月28日2023/3/1015

当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。1.当产大于销时,即7.1.3不平衡运输问题

BjAiB1B2B3产量A1659120

A212107100A3698130销量10010080第十六页，共三十页，2022年，8月28日2023/3/10161.当产大于销时数学模型为即第十七页，共三十页，2022年，8月28日2023/3/1017由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，…，m），总的库存量为第十八页，共三十页，2022年，8月28日2023/3/1018bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为：具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可第十九页，共三十页，2022年，8月28日2023/3/10192.当销大于产时,即

BjAiB1B2B3产量A1659120

A212107100A3698130销量200100150第二十页，共三十页，2022年，8月28日2023/3/10202.当销大于产时,即数学模型为第二十一页，共三十页，2022年，8月28日2023/3/1021由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为xm+1,j是Am+1运到Bj的运量，也是Bj不能满足需要的数量。Am+1到Bj的运价为零,即Cm+1,j=0(j=1,2,…,n)第二十二页，共三十页，2022年，8月28日2023/3/1022销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。第二十三页，共三十页，2022年，8月28日2023/3/1023上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210需求量不确定的运输问题第二十四页，共三十页，2022年，8月28日2023/3/1024先作如下分析：

（1）总产量为180，B1，…，B4的最低需求量

20+50+35+45=150<180，这时属产大于销；（2）B1，…，B4的最高需求是60+70+35+45=210>180，这时属销大于产;B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210第二十五页，共三十页，2022年，8月28日2023/3/1025（3）虚设一个产地A5，产量是210－180=30，

A5的产量只能供应B1或B2。B1B2B3B4aiA1592360A2--47840A3364230A448101150bj20～6050～703545180150～210第二十六页，共三十页，2022年，8月28日2023/3/1026（4）将B1与B2各分成两部分的需求量是20，的需求量是40，的需求量分别是50与20，因此必须由A1，…，A4供应，可由A1、…、A5供应。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210第二十七页，共三十页，2022年，8月28日2023/3/1027（5）上述A5不能供应某需求地的运价用大M表示，A5到、的运价为零。得到下表的产销平衡表。B3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210第二十八页，共三十页，2022年，8月28日2023/3/1028中转问题产地销地

A120

A230

A350

A920

A815

A7