第三讲运输及指派问题.ppt

190 30 50 65 45 bj 30 × 10 × 40 5 14 12 10 A3 × 50 × 30 80 7 4 6 3 A2 × × 55 15 70 2 9 8 5 A1 ai B4 B3 B2 B1 Bj Ai x14出基，调整运量得到： 再求非基变量的检验数： λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=4 运输单纯形法 Transportation Simplex Method 再求非基变量的检验数： λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=4 所有检验数λij ≥0因而得到最优解 最小运费 运输单纯形法 Transportation Simplex Method 设数学模型为 最大值问题 运输单纯形法 Transportation Simplex Method 方法一：将极大化问题转化为极小化问题。设极大化问题的运价表为C=（Cij）m×n，用一个较大的数M（M≥max{Cij}）去减每一个Cij得到矩阵C’=（C’ij）m×n ，其中C’ij=M－Cij≥0,将C’作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为 例如，下列矩阵C是Ai（i=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大. 8 14 9 运输单纯形法 Transportation Simplex Method 用最小元素法求初始方案得 λ11=8, λ12=4, λ21=2, λ23=2全部非负,得到最优运输方案X,最大利润Z=8×9+10×10+6×8+5×4=240 方法二:所有非基变量的检验数λij≤0时最优. 求初始运输方案可采用最大元素法. 如上例,用最大元素得到 的初始运输方案: 8 14 9 求检验数:λ11=－8,λ12=－4,λ21=－2,λ23=－2,全部非正, 得到最优解运输方案,结果与第一种方法相同. 运输单纯形法 Transportation Simplex Method 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。 1.当产大于销时,即 数学模型为 不平衡运输问题 运输单纯形法 Transportation Simplex Method 由于总产量大于总销量，必有部分产地的产量不能全部运送 完，必须就地库存，即每个产地设一个仓库，库存量为 xi，n+1 （i=1，2，…，m），总的库存量为 运输单纯形法 Transportation Simplex Method bn+1作为一个虚设的销地Bn+1的销量。各产地Ai到Bn+1的运价为零，即Ci，n+1=0,（i=1，…，m）。则平衡问题的数学模型为： 具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可 运输单纯形法 Transportation Simplex Method 2.当销大于产时,即 数学模型为 运输单纯形法 Transportation Simplex Method * 运筹学 Operations Research 第三讲 运输与指派问题 实际工作中常碰到很多线性规划问题，由于他们约束条件变量的系数矩阵具有特殊的结构，很可能找到比单纯形法更为简便的方法进行求解，从而可节约时间和费用, 运输问题就是其中之一。运输问题的一般提法是:某种物资有若干个产地和销地，若已知各产地地产量、各销地的销量，以及各产地到各销地的单位运价(或运输距离)，问应如何组织调运才能使总运费(或总运输量)最省？ 【例1】现有A1，A2，A3三个产粮区，可供应 粮食分别为10，8，5(万吨)，现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如表1所示，问如何安排一个运输计划，使总的运输费用最少。 23 3 8 7 5 需要量 5 9 2 1 4 A3 8 2 8 3 5 A2 10 3 6 2 3 A1 产量 B4 B3 B2 B1 地区 产粮区 运价表(元/吨) 表1 运输模型 Model of Transportation Problems 设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型： 【解】 运输模型 Model of Transportation Problems 【例2】有三台机床加工三种零件，计划第i台的生产任务为a i (i=1,2,3)个零件，第j种零件的需要量为bj (j=1,2,3)，第