《运输问题(0)》由会员分享，可在线阅读，更多相关《运输问题(0)（44页珍藏版）》请在金锄头文库上搜索。
1、本章重点第三章 运输问题产销平衡运输问题的数学模型产销平衡运输问题的表上作业法 本章内容运输问题的数学模型表上作业法运输问题的扩展Date1一、一、 运输问题模型运输问题模型对某种物资，设有m个产地A1, A2, , Am，称它们为 发点，其对应产量为a1, a2, , am，称它们为产量；另有n 个销地B1, B2, , Bn，称它们为收点，其对应销量为b1, b2, , bn，称它们为销量。又知，从产地（发点）Ai运至 销地（收点）Bj，该种物资每单位的运价为ci j（ci j0）。试问：应如何安排调运方案，在满足一定要求的前提 下，使总运费最低？ Date21 1、运输问题模型运输问题模
2、型根据上述参量的意义列出产销运价，如表1所示。 表1 产销运价表 销销地 产产地 B1 B2 Bn 产产量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 Am cm1 cm2 cmn am 销销量 b1 b2 bn aibj Date3表的右下角 ai表示各产地产量的总和，即 总产量或总发量； bj表示各销地销量的总和， 即总销量或总收量。这里有两种可能： （1） ai bj（总产量总销量），即产销平衡 问题。 （2） ai bj（总产量总销量），即产销不 平衡问题。它又可分为两种情况：产大于销， 即 ai bj ；销大于产，即 ai bj。下面先讨论产销平衡问题，再
3、讨论产销不 平衡问题。 Date4令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可 以列出产销平衡表如表2所示。表2 产销平衡表 销 地 产 地 B1 B2 Bn 产 量 A1 x11 x12 x1n a1 A2 x21 x22 x2n a2 Am xm1 xm2 xmn am 销量 b1 b2 bn Date5 将表1和表2两个表合在一起，得到的一个新表， 被称为运输表（或称为产销矩阵表），如表3所示 。Date6数学模型： 设从Ai到Bj的物资运量为xij ，产销平衡运输问题的数学模型。Ai的产品全部 供应出去Bj的需求全 部得到满足Date7 约束条件系数矩阵的元素等于0或1
4、 约束条件系数矩阵的每一列有两个非零 元素，这对应于每一个变量在前 m个约 束方程中出现一次，在后n个约束方程中 也出现一次。 对产销平衡运输问题，除上述两个特点外，还有 以下特点: 所有约束条件都是等式约束； 各产地产量之和等于各销地销量之和。运输问题的特点Date8 根据运输问题的数学模型求出的运输问题的解 X(xij) ，代表着一个运输方案，其中每一个变量xij的值表示 由Ai调运数量为xij 物品给Bj。前已指出运输问题是一 种线性规划问题，可设想用迭代法进行求解，即先找 出它的某一个基可行解，再进行解的最优性检验，若 它不是最优解，就进行迭代调整，以得到一个新的更 好的解，继续检验和
5、调整改进，直至得到最优解为止 。 为了能按上述思路求解运输问题，要求每步得到的解 X(xij)都必须是基可行解，这意味着：(l)解X必须满 足模型中的所有约束条件；(2)基变量对应的约束方程 组的系数列向量线性无关；(3)解中非零变量xij的个数 不能大于(m+n-l)个，原因是运输问题中虽有(m+n)个 结构约束条件，但由于总产量等于总销量，故只有 (m+n-l)个约束条件是线性独立的；(4)为使迭代顺利进 行，基变量的个数在迭代过程中保持为(m+n-1)个。 运输问题的解Date9例1 某公司经销甲产品。它下设三个加工厂。每日的产量分 别为：A1-7吨，A2-4吨，A3-9吨。该公司把这些
6、产品分别 运往四个销售点。各销售点每日销量为：B1-3吨，B2-6吨 ，B3-5吨，B4-6吨。已知从各工厂到各销售点的单位产品 的运价为表所示。问该公司应如何调运产品，在满足各销售 点的需要量的前提下，使总运费为最少。 解 先画出这问题的产销平衡表和单位运价表， B1B2B3B4产量/tA13113107A219284A3741059销量/t3656销地运费 产地Date101.决策变量 xij表示第i产地运到第j个销地的产品数量2.目标函数 z为总费用3.约束条件Date11第二节 运输问题的表上作业法从上面的运输问题的数学模型中可以看到 ，它包含mn个变量，mn个约束条件。如 果用单纯形
7、法求解，应先在每个约束方程 中引进一个人工变量。这样一来，即使是 m3，n4这样简单的运输问题，变量数就 有12个，显然计算起来非常繁杂；而用表 上作业法来求解运输问题则比较简便。Date122 表上作业法计算步骤： (1) 找出初始调运方案。即在(mn)产销平衡表上 给出m+n-1个数字格。(最小元素法或差值法）(2) 求检验数。（闭回路法或位势法） 判别是否 达到最优解。如已是最优解，则停止计算，否则 转到下一步。(3) 对方案进行改善，找出新的调运方案。（表上 闭回路法调整）确定m+n-1个基变量(4) 重复（2）、（3），直到求得最优调运方案。空格Date13举例说明表上作业法例2、某
8、部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：4122854396111110销量产量销地 产地Date14第一步：确定初始基可行解最小元素法 最小元素法思路：从单价中最小 运价确定供应量 ，逐步次小，直 至得到m+n-1个 数字格。Date15 基本思想：应优先考虑单位运价最小(或运距最短)的供 销业务，最大限度地满足其供销量。即对所有 i和j找出 ，的物品量由A i0供应给B j0. 若x i0 j0 a i0，则产地A i0的可供物品已用完，以后不再 继续考虑这个产地，且B j0的需求量由b j0减少为b j0-a i0 ; 如果x i0 j0 bj0 ，则销地B j
9、0的需求已全部得到满足，以 后不再考虑这个销地，且A i0的可供量由a i0减少为a j0-b i0 。然后，在余下的供、销点的供销关系中，继续按上 述方法安排调运，直至安排完所有供销任务，得到一个 完整的调运方案(完整的解)为止。这样就得到了运输问 题的一个初始基可行解(初始调运方案)。Date16最小元素法举例4122854396111110销量产量销地 产地822010100614868000060Date17最小元素法举例4122854396111110销量产量销地 产地82101468最小元素法缺点：会出现顾此失彼（运费差额问题）考虑运 价差Date18第二步：解的最优性检验 闭回路
10、法：以xij为拐角点，其间用水平或铅直线 连接而成的回路。思路：计算空格（非基变量）的检验数 若令 则如何求检 验数？分析：运费的增量即 增加1个单位的检验数=相 应的运费增量Date194122854396111110销量产量销地 产地82101468从初始表分析：要保证产销平衡，则称为闭回路 +1-1+1-1Date204122854396111110销量产量销地 产地821014682 1Date21检验数表4122854396111110销量产量销地 产地821014682 11 -1 1012表中的解不是最优解。Date22第三步：解的调整调整位置（2，4）非空，回路角上的格 至少为
11、空，且保证数字的非负性。4122854396111110销量产量销地 产地82101468-1 （-2）（-2）（+2）（+2）Date23 调整后的解为：4122854396111110销量产量销地 产地821214482 2091 12此时的解为最优解。有无穷多 最优解Date24几点说明： 当检验数为的负的变量超过两个，选择 最小者对应的变量换入； 在最优解的表中，若有检验数=0，则该 运输问题有无穷多最优解； 迭代过程中，若某一格填数时需同时划 去一行和一列，此时出现退化。为保证 m+n-1个非空格，需在上述的行或列中 填入数字0。Date25Date26第三节 运输问题的进一步讨论上
12、节给出产销平衡运输问题的表上 作业法，本节以下问题进一步讨论：二、有转运的运输问题一、产销不平衡的运输问题并附有运输问题的思考题及练习题Date27一、产销不平衡的运输问题 （）若总产量大于总销量，即令假象销地的销量为：Date28决策变量 表示由 到 的物品数量。销地产地销量产量注意：用最小元素法求初始调运方案时， 最后一列的零运价最后考虑。Date29原产大于销平衡问题的数学模型Date30修改后产大于销平衡问题的数学模型Date31 （）若总产量小于总销量，即令假象产地的销量为：仿照上述类似处理。Date32举例说明 某部门三个工厂生产同一产品的产量、 四个销售点的销量及单位运价如下表：
13、4122854396111110销量产量销地 产地Date33应用问题举例 例1、水泥调运的产销不平衡情况及运价 如下表，求最好的调运方案。21110783592143销量产量销地 产地Date34最优方案为：21110783592143销量产量销地 产地000Date35 例2、某农场有土地900亩，分为三类， 计划种植三种作物，情况如下表，求使 作物总产量最多的布局方案。500销量产量销地 产地700700850480600300400500Date36 解：目标函数最大，可用最大元素法， 即是按产量高的优先安排的原则。500销量产量销地 产地70070085048060030040050
14、0100300100400050Date37调整：500销量产量销地 产地7007008504806003004005001002002004000可验证此时为最优解。Date38运输问题讨论Date39一、概念题（判断）1、运输问题是一种LP问题，其求解结果 有四种情况。 2、在运输问题中，只要给出一组含（m+n -1）个非零的 ，且满足就可以作为一个初始基可行解。Date403、按最小元素法（或伏格尔法）给出的初 始基可行解，从每一空格出发可以找出 而且仅能找出唯一的闭回路。 4、当所有产地产量和销地销量均为整数值 ，运输问题的最优解也为整数值。 5、如果运输问题单位运价表的某一行（或 某一列）元素分别加上一个常数k，最优 调运方案将不会发生变化。 6、如果.分别乘上一个常k,.不会发 生变化。Date41三、运输问题的灵敏度分析已知某运输问题的供需关系及单价表如下表，销量产量销地 产地245353312要求（1）用表上作业法找出最优调运方案。（2）分别讨论 使最优方案不变的变化范围 Date42四、求解线性规划问题可可转化为转化为 运输问题运输问题 来求解来求解 Date43练习： 下表给出一个运输问题及它的一个解，411374611562销量产量销地 产地853231Date44
