Ch5运输与指派问题

运筹学OperationsResearchChapter5运输与指派问题TransportationandAssignmentProblem5.1运输模型MathematicalModelofTransportationProblems5.2运输单纯形法TransportationSimplexMethod5.3运输模型的应用AplicationofTransportationModel5.4指派问题Assignmentproblem5.1运输模型MathematicalModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]3Chapter5运输与指派问题T&AProblem2020年1月18日星期六人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。5.1运输模型ModelofTransportationProblems5.1.1数学模型产地销地A110A28A35B43B38B27B15354231682329图5.1制作与教学武汉理工大学管理学院熊伟[e-mail]4Chapter5运输与指派问题T&AProblem2020年1月18日星期六【例5-1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表5-15.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]5Chapter5运输与指派问题T&AProblem2020年1月18日星期六设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx运量应大于或等于零（非负要求），即4,3,2,13,2,1,0jixij；5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]6Chapter5运输与指派问题T&AProblem2020年1月18日星期六有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型看一个例子：【例5-2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij，如表5－2所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表5－25.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]7Chapter5运输与指派问题T&AProblem2020年1月18日星期六【解】设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为3,2,13,2,1,050307040605043746325min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxZij；5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]8Chapter5运输与指派问题T&AProblem2020年1月18日星期六运输问题的一般数学模型设有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个销地的运量，则数学模型为：njjmiiba115.1运输模型ModelofTransportationProblemsnjijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,,1;,,1,0,,1,,111制作与教学武汉理工大学管理学院熊伟[e-mail]9Chapter5运输与指派问题T&AProblem2020年1月18日星期六niijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,,1;,,1,0,,1,,111设平衡运输问题的数学模型为：5.1.2模型特征5.1运输模型ModelofTransportationProblems1.运输问题存在可行解，也一定存在最优解2.当供应量和需求量都是整数时，则一定存在整数最优解3.有m+n个约束，mn个变量4.有m+n－1个基变量制作与教学武汉理工大学管理学院熊伟[e-mail]10Chapter5运输与指派问题T&AProblem2020年1月18日星期六【证】因为产销平衡，即，将前m个约束方程两边相加得minjiiba11minjmiiijax111再将后n个约束相加得njminjjijbx111显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方程是相关的，系数矩阵5.1运输模型ModelofTransportationProblems【定理5.1】设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。制作与教学武汉理工大学管理学院熊伟[e-mail]11Chapter5运输与指派问题T&AProblem2020年1月18日星期六中任意m+n阶子式等于零，取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式1,1121121,,,,nmnnnxxxxxx，，，m行n行5.1运输模型ModelofTransportationProblems111212122212111111111111111111nnmmmnxxxxxxxxxA＝制作与教学武汉理工大学管理学院熊伟[e-mail]12Chapter5运输与指派问题T&AProblem2020年1月18日星期六0111111111故r(A)=m+n－1所以运输问题有m+n－1个基变量。为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]13Chapter5运输与指派问题T&AProblem2020年1月18日星期六),,,,,,(,,,,,,2121132222111互不相同；称集合ssjijijijijijijjjiiixxxxxxsss为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表5－3及表5－4中的变量组构成两个闭回路。x25x23B1B2B3B4B5A1A2A3x35A4x43x11x12x31x42表5－3表5－3中闭回路的变量集合是{x11,x12,x42,x43,x23,x25,x35,x31}共有8个顶点，这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]14Chapter5运输与指派问题T&AProblem2020年1月18日星期六x11x12x32x33x41B1B2B3A1A2A3A4x43表5－4一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度与另一顶点连接，表5－3中的变量x32及x33不是回闭路的顶点，只是连线的交点。表5－4中闭回路是123233434111,,,,,xxxxxx;,,,,,121131352521xxxxxxA;,,,,2111123233xxxxxB例如变量组A不能组成一条闭回路，但A中包含有闭回路;,,,31352521xxxxB的变量数是奇数，显然不是闭回路，也不含有闭回路；5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]15Chapter5运输与指派问题T&AProblem2020年1月18日星期六333211122321,,,,,xxxxxxCC是一条闭回路，若把C重新写成就不难看出C仍是一条闭回路。111232332321,,,,,xxxxxxC【定理5.2】若变量组B包含有闭回路，则B中的变量对应的列向量线性相关。12111,,,jijijisxxxC【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即11122210sijijijijPPPP－因而C中的列向量线性相关，所以B中列向量线性相关。5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]16Chapter5运输与指派问题T&AProblem2020年1月18日星期六由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。求运输问题的一组基变量，就是要找到m+n－1个变量，使得它们对应的系数列向量线性无关，由定理2，找这样的一组变量是很容易的，只要m+n－1个变量中不包含闭回路，就可得到一组基变量。因而有：【定理3】m+n－1个变量组构成基变量的充要条件是它不包含任何闭回路。定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。5.1运输模型ModelofTransportationProblems制作与教学武汉理工大学管理学院熊伟[e-mail]17Chapter5运输与指派问题T&AProblem2020年1月18日星期六表5-5BjAiB1B2B3B4aiA1c11c12c13c14a1x11x