[2018年必威体育精装版整理]30运输问题.pptVIP

* 第三章 运输问题 第一节 运输问题典例及数学模型 例： 三个产地四个销地的运输问题示意图 运输问题的线性规划模型 需求约束 供应约束 上述模型是根据上图的具体问题写出的。一般运输问题的模型形式基本类似。当产销平衡时，约束中的不等号可改为等号。 运输问题的线性规划模型的系数矩阵的列向量都是由两个单位坐标向量叠加构成。从上例中模型的系数矩阵A就很容易看出这个特点。 表上作业法与单纯形法的关系 运输问题的模型形式实际上是一种系数矩阵仅含0，1元素的线性规划模型。所以可以利用单纯形法求解。由于模型的特点，使单纯形法求解的过程可用表上作业法这一简洁形式表现出来，但表上作业法的单纯形法实质没有丝毫改变：表上作业法中的“位势法”实质上是在求单纯表中的检验数；调运方案表中的有效数字实质上就是单纯形法中基变量的值；调运方案表上的“闭回路调整法”实质上是在做单纯表上的换基迭代。 产销平衡运输问题的表上作业法步骤: （1）在运价表上用Vogel法求出调运方案表； （2）在运价表上用位势法求非基变量的检验数； （3）检验方案是否最优。是，停止；否，继续（4）； （4）在调运方案表上用闭回路调整法得到新的调运方案； （5）重复（2）。 例:某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的生产量分别为:A1－7吨， A2－4吨，A3－9吨。拟把这些糖果运往四个门市销售，各门市的每日销量为B1－3吨， B2－6吨，B3－5吨，B4－6吨。运价表如下，问：如何运送使总运费最小？ 5 10 4 7 A3 8 2 9 1 A2 10 3 11 3 A1 B4 B3 B2 B1 表1：单位运价表 门市 加工厂 9 A3 4 A2 7 A1 产量 B4 B3 B2 B1 表2：产销平衡表 销地 产地 6 5 6 3 销量 一、初始方案的确定： 在运价表上用Vogel法求出调运方案表 0 0 0 0 6 1 0 0 0 5 3 0 0 0 4 3 5 0 0 3 3 5 0 3 2 6 5 0 3 1 调整次 序 销 地 剩 余 量 6 5 6 3 销 量 8 6 2 5 2 1 4 2 1 2 3 3 1 2 2 Vogel法求初始调运方案 a. 求出各行、各列最小两元素的差值； b. 在运价表中找出最小差值对应的行或列的最小元的位置，并用“[ ]”或“○”标记； c. 画“[ ]”元对应的产地的产品尽可能多地调往画“[ ]”元对应的销地，并将调运量填入调运方案表中的相应位置，同时，产或销地调运后的剩余量记入本表右上角相应位置。 d. 若该产地的产量被全部调运完，则该产地在运价表中的行用一条虚线划去；若该销地的需求量被全部满足，则该销地在运价表中的列用一条虚线划去；凡是被划去的行或列不再予以考虑。 e. 若运价表中所有行和列都被划去，停止。否则，回到步骤a. 。 3 1 5 2 1 调整次 序 同列 最小 两元 素的 差 0 0 0 0 0 3 9 2 1 [5] 10 [4] 7 A3 0 1 1 1 4 4 4 8 8 6 1 1 1 [8] 2 9 [1] A2 0 0 2 7 7 7 7 10 7 0 0 0 [10] [3] 11 3 A1 6 5 4 3 2 1 6 5 4 3 2 1 调整次序 调整次序 产地剩余量 产量 同行最小两元素的差 B4 B3 B2 B1 产地 销地 运价 Vogel法求调运方案 销地 6 5 6 3 销 量 9 3 6 A3 4 1 3 A2 7 2 5 A1 产量 B4 B3 B2 B1 方案 产地 表3 ：初始调运方案 调运方案表中出现的数字被称为有效数字，它们分别对应此时基变量的值，空格单元的对应变量即是此时的非基变量，其值为0。本表中，基变量x13=5, x14=2, x21=3, x24=1, x32=6, x34=3, 非基变量x11= x12= x22= x23= x31= x32=0. 二、最优性检验与方案的调整： (在运价表上用位势法求非基变量的检验数。) v4 =10 v3 =3 v2 =9 v1 =3 v 12 9 [5] 10 [4] 7 u3=-5 -2 -2 A3 1 2 [8] 2 9 [1] u2 =-2 1 7 A2 2 0 [10] [3] 11 3 u1 =0 9 3 A1 u B4 B3 B2 B1 产地 销地 方案 位势法求非基变量的检验数 表4 *首先将运价置于各单元格的中央，有效数字（基变量）对应的运价要画上“[ ]”。 *在 u 所在列的第一个位置填上u1=0。 *然后由等式 ui+vj =[cij ] 求出所有ui，vj 的值。其中，[cij ]对应表4