1.6线性规划ppt课件.ppt

第1章线性规划 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 1 6 2运输问题的算法和原理 1 6 3运输问题的程序流程图 1 6 4运输问题的实例及操作 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 1 运输问题的数学模型一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地 在每个产地的供应量与每个销地的需求量已知 并知道各地之间的运输单价的前提下 如何确定一个使得总的运输费用最小的方案 在这里 我们先以一个示例来简单描述一下运输问题的数学模型 例1 某公司从两个产地A1 A2将产品运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地的单位产品运费如表1 8所示 问如何调运 使得总运输费最小 表1 8产 销 运价关系表 解 从表中可以看到 A1 A2两个产地的总产量为500件 B1 B2 B3三个销地的总销量为500件 因此这是一个产销平衡的运输问题 把A1 A2的产量全部分配给B1 B2 B3 正好满足这三个销地的需要 设xij表示从产地Ai调运到销地Bj的运输量 i 1 2 j 1 2 3 则可以写出此运输问题的数学模型 即 minZ 6x11 4x12 6x13 6x21 5x22 6x23x11 x12 x13 200 x21 x22 x23 300 x11 4x21 150 x12 x22 150 x13 x23 200 xij 0 i 1 2 j 1 2 3 销地 产地 此数学模型当然可用线性规划的常用方法求解 但求解的程序相对复杂 即使利用计算机程序来求解 其输入和解决问题的规模也受到一定的限制 因此 运筹学中有专门的求解运输问题的程序 一般只要输入产点数 各产地的产量 销点数 各销地的销量 以及各产地到各销地的运输单价 立即可得到运输问题的最优解 把本例的相关数据输入运输问题的程序 得到最优解为 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 x11 50 x12 150 x13 0 x21 100 x22 0 x23 200最优值为 minz 2700最优解的表格描述如表1 9所示 表1 9供 需 运价关系表 销地 单位运价 产地 通过上例 我们对运输问题已有了简单的认识 下面我们将给出一般运输问题的数学模型 我们用 A1 Am表示某种物资的m个产地 B1 B2 Bn表示某种物资的n个销地 ai表示Ai产地的产量 bj表示销地Bj的销量 cij表示把物资从Ai产地运到Bj销地的单位运价 并设为xij为从产地Ai运到销地Bj的运输量 则产销平衡的运输问题的线性规划模型如下所示 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 minZ j 1 2 n i 1 2 m xij 0 i 1 2 m j 1 2 n 有时上述问题的一般模型会发生如下一些变化 1 求目标函数值的最大值而不是最小值 有些运输问题中 其目标是找出利润最大或营业额最大的调运方案 这时需要求目标函数的最大值 2 当某些运输线路的运输能力有一定限制时 这时要在线性规划模型的约束条件上加上运输能力限制的约束条件 3 当生产总量不等于销售总量 即产销不平衡时 这时需要通过一个假想销地或假想产地来化成产销平衡的问题 具体做法在后面阐述 2 运输问题的求解方法 表上作业法 直接采用单纯形法求解运输问题明显是不利的 好在运输问题具有特殊的结构 因此可以利用单纯形法的原理 提出一种直接在运输表上计算以求解产销平衡运输问题的简便方法 表上作业法 它大大简化了计算 其原理如下 1 求初始调运方案 初始基可行解 对于有m个产地n个销地的产销平衡的问题 从其线性规划的模型上可知其有m n个约束方程 由于产销平衡 前m个约束方程之和等于后n个约束方程之和 故只有m n 1个独立的约束方程 也就是说运输问题的约束方程组系数矩阵的秩等于m n 1 因此其基可行解中基变量的个数为m n 1 表上作业法中找初始基可行解 就是在产销平衡表上m n个数字格中找出m n 1个数字格 其相应的调运量就是基变量 格子中所填写的值即为基变量的值 2 求表中各空格 对应于非基变量 的检验数以判定当前解是否最优 若已是最优解则停止计算 否则转到下一步 3 如果检验数中有负数 那么就以最小的负检验数所在的空格为调入格 并用这个空格的闭回路来进行调整 得出新的调运方案 4 重复2 3直至得到最优解 上述步骤在表上进行十分方便 下面以例子来说明 示例 某食品公司有三个生产面包的分厂A1 A2 A3 有四个销售分公司B1 B2 B3 B4 其各分厂每日的产量 各分销售公司每日的销量以及各分厂到各分销售公司 的单位运价如表1 10所示 问该公司应如何调运产品在满足各销点的需求量的前提下 总运费最少 表1 10供 需 运价关系表 销地 产地 一 求初始调运方案 最小元素法该方法的基本思想是采用 优先安排单位运价最小的产地与销地之间的运输业务 这个规则来确定初始基可行解 我们直接在运输表中的格子里填数表示基变量 为了把初始基可行解与运价分开 把运价放在每一栏的右上角 每一栏的中间填上初始基可行解 调运量 见表1 12 在表上找到单位运价最小的x21开始分配运输量 并使x21取尽可能大的值 即取x21 min 4 3 3 把x21所在空格里填上3 然后把A2的产量改写为4 3 1 把B1的销量改写为3 3 0 并把B1列划去 在剩下的3 3矩阵里找到运价最小的变量x23 取x23 min 1 5 1 A2的产量改为1 1 0 B3的销量改 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 为5 1 4 并把A2行划去 在剩下的矩阵里找到运价最小的变量x13 取x13 min 7 4 4 A2的产量改为3 B3的销量改为0 并划去B3列 在剩下的矩阵里再找到运价最小的变量x32 取x32 min 9 6 6 A3的产量改为3 B2的销量改为0 并把B2列划去 接着在剩下的表中找到运价最小的变量x34 取x34 min 3 6 3 A3的产量改为0 B4的销量改为3 并把A3行划去 最后在剩下的表中找到运价最小的变量x14 取x14 min 3 3 3 A1的产量改为0 B4的销量改为0 并划去A1行 这就得到一个初始基可行解 有6个基变量 其中x13 4 x14 3 x21 3 x23 1 x32 6 x34 3 其总运费为3 4 10 3 1 3 2 1 4 6 5 3 86 在用最小元素法确定初始基可行解时要注意两个问题 1 当确定xij的值后 会出现Ai的产量与Bj的的销量都改为零的情况 这时只能划去Ai行或Bj列 但不能同时划去Ai行和Bj列 2 最小元素法时 可能会出现只剩一行或一列的所有格均未填数或未被划掉的情况 此时在这一行或列中除去已填的数外均填0 不能按空格划掉 这样可以保证基变量的个数为m n 1个 说明 求初始调运方案的方法具有很多种 例如 西北角法 最小行法 最小列法 混合法 频率法等 其基本原理都和最小元素法大同小异 在此将不再赘述 二 最优解的判别 位势法同单纯形法一样 表上作业法也是用检验数来检验方案的最优性 所谓位势法 即对运输表上的每一行赋予一个数值ui 对每一列赋予一个数值vj 它们的数值是由基变量xij的检验数 ij cij ui vj 0所决定的 则非基变量xij的检验数就可用公式 ij cij ui vj求出 下面用位势法对本例的初始基可行解求检验数 对给出的初始基可行解作一个表 栏中表示调运量 栏中无数值的表示此栏为非基变量 调运量为零 如表1 11所示 1 6 1运输问题的理论基础 1 6运输问题编程算法与编程实践 表1 11运价及供需平衡表 产地 销地 先给u1赋个任意数值 不妨令u1 0 则从基变量x13的检验数 13 c13 u1 v3 0 求得v3 c13 u1 3 0 3 同样 从 14 c14 u1 v4 0 得v4 c14 u1 10 0 10 从 13 c13 u2 3 0 得u2 c13 v3 2 3 1 从 34 c34 u3 v4 0 得v4 c34 u3 5 10 5 从 32 c32 u3 v2 0 得v2 c32 u3 4 5 9 然后 利用求得的ui与vj的值来计算非基变量的检验数 11 c11 u1 v1 3 0 2 1 12 c12 u1 v2 11 0 9 2 22 c22 u2 v2 9 1 9 1 24 c24 u2 v4 8 1 10 1 31 c31 u3 v1 7 5 2 10 33 c33 u3 v3 10 3 5 12 对求出的检验数可表示如表1 12 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 表1 12检验数表 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 该表中 把原来表中的最后一列的产量改为ui值 最后一行的销量改为vj值 表中每一栏的右上角仍表示运价 左下角的数中不带括弧的为基变量的运输单位 带括弧的表示非基变量的检验数 当表中某个非基变量的检验数为负值时 表明未得到最优解 要进行方案调整以得到更好的方案 说明 同求初始可行解一样 检验已得的运输方案是否是最优解的方法有两种 一种是闭回路法 另一种是位势法 为了节省篇章 闭回路法的求解原理 请参阅其它书籍 三 方案的调整首先选取检验数中的最小的负检验数 以它对应的非基变量为入基变量 本例中选非基变量x24为入基变量 并以x24所在格为出发点找一条闭回路 如表1 13所示 表1 13调运方案表 销地 4 产地 闭回路的确定方法为 在给出的调运方案的计算表中 如表1 13 以入基变量所在格为起点 用水平或垂直线向前划 每遇到一数字格则转90度后继续前进 直到回到起始空格为止 可以证明这样的闭回路一定存在而且唯一 在上表中 由于 24 1 表明增加一个单位的x24的运输量使总运输减少1 所以应尽量多增加x24的运输量 但为了保证运输方案的可行性 即所有的调运量必须大于等于零 所以从出发点x24所在空格定点序号为1的闭回路中 找出所有偶数的顶点的调运量 x14 3 x23 1 取其中的最小值为x24的值 即x24 min x14 x23 min 3 1 1 为了使产销平衡 把闭回路上所有偶数顶点的运输量都减少这个值 所有奇数顶点的运输量都增加这个值 即得到了调整后的运输方案 如表1 14所示 表1 14调运方案表 销地 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 对调整后的运输方案 再运用位势法求得检验数如表1 15所示 表1 15检验数表 产地 销地 表中带括弧的数字是非基变量的检验数 可知所有检验数都大于等于零 基变量的检验数都等于零 此解是最优解 这时得到最小总运输费用为85元 具体的运输方案如下 A1分厂运5吨到销售公司B3 运2吨给销售公司B4 A3分厂运3吨给销售公司B1 运1吨给销售公司B4 A3分厂运6吨给销售公司B2 运3吨给销售公司B4 3 对供需不平衡的运输问题的处理前面讲的表上作业法的计算和理论 都是以供需平衡 即以 为前提的 但是实际问题中供需往往是不平衡的 为了应用表上作业法计算 就需要把供需不平衡的问题转化为供需平衡的问题 当供大于需时 即 时 只要增加一个假想的需求单位 实际上是贮存 该需求单位的需求量为 而在里程表里 从各供应站到假想单位的运价为 0 这样原问题就转化为了一个产销平衡的运输问题 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 类似地 当需大于供时 即 时 只要增加一个假想的供应单位的 实际上是贮存 该地的供应量为 而在里程表里 从各供应站到假想单位的运价为 0 同样可以转化为一个产销平衡的运输问题 单位的运价为 0 同样可以转化为一个产销平衡的运输问题 例如 设有A1 A2 A3三个产地生产某种军用物资 其产量分别为7 5 7吨 B1 B2 B3 B4四个销地需要该物资 销量分别为2 3 4 6吨 又知各产销地间的运价如表1 16所示 试决定总运费最小的调运方案 表1 16运价矩阵表 1 6 1运输问题的理论基础 1 6运输问题编程算法与编程实践 销地 解 产地总产量为19吨 销地总需求量为15吨 所以这是一个供大于需的运输问题 按上述方法转化为供需平衡问题 其供需平衡表和单位运价表如表1 17所示 此处将运价表和供需表合在一起来描述 表1 17产销平衡 运价矩阵表 销地 运用表上作业发 可求得最优方案如表1 18所示 表1 18最优分配方案表 销地 最小运费为 minZ 2 2 3 3 3 3 1 1 6 2 35 1 6运输问题编程算法与编程实践 1 6 1运输问题的理论基础 1 6运输问题编程算法与编程实践 1 6 2运输问题的算法和原理 运输问题实质上是一个线性规划问题 其求解也可划分为两个主要阶段 一 初始可行解的确定 即找出初始可行调运方案 二 从这个可行解出发寻找最优解 即依据初始调运方案 找出运费最小的调运方案 从前面的原理中 我们知道求解初始可行方案和寻找最优方案的方法都不是唯一的 在本文里 我们以西北角法来求解初始可行方案 以步进法来寻找最优解方案 并在后文给出这两个算法的程序流程图和程序源代码 1 西北角法的算法原理和求解步骤 假设 下标集合RR和SS定义为RR i 所有供应站的下标的集合 SS j 所有需求站的下标的集合 而且对初始运输矩阵X X m n 有xij对任意i j成立 解题步骤 第一步 确定r min i iRR s min j jSS 第二步 确定 min ar bs 并令xrs ar ar bs bs 第三步 定义集合RR SS 第四步 判断 RR SS 是否成立 若是 则停止计算 矩阵X给出一个可行的运输计划 若否 则转至第一步 2 步进法的算法原理和求解步骤假设 给定运输问题的某一可行解X 求最优 最低运费 的运输计划 定义 ui和vj分别为供应站和需求站的位势 矩阵D mxn 为当前运输矩阵的检验数矩阵 解题步骤 第一步 检验当前解的最优性 计算含有值ui和vj的矩阵D 考察当前的运输矩阵X 若xij 0 则dij 0 第二步 计算基变量的检验数 令v1 0 并计算所有其它的ui和vj 使得ui vj cij对任意dij 0成立 若这样做不可能求出所有的ui和vj 则令dij 0 以便能计算所有的ui和vj 这步计算结果得到至少 m n 1 个元素的检验数dij 0 第三步 计算非基变量的检验数 计算公式 dij cij ui vj 结果求得矩阵所有元素的检验数 第四步 在运输矩阵X中 给使得xij dij 0的所有的xij元素标上符号 若此种情况发生 则问题称为退划的 第五步 确定dij max cij i 1 2 m j 1 2 n 第六步 判断 对任意i j dij 0是否成立 若是 则停止计算 当前的运输计划X为最优 其总运费Z定义为Z 此处略去往返虚设物的运费 若否 则转至第七步 第七步 新解的确定 1 给元素xrs标上 号 2 在r行中找出一个大于零的元素 给此元素标以 号 该元素满足条件 在其相应的列中至少有一个标有 或大于零的元素 1 6运输问题编程算法与编程实践 1 6 2运输问题的算法和原理 3 在这样确定的列中找出一个标有 或大于零的元素 给此元素标以 号 该元素满足条件 在其相应的行中至少有一个大于零的元素 4 判断 在s列中是否有一个元素标以 若是 则转至第八步 1 6运输问题编程算法与编程实践 1 6 2运输问题的算法和原理 若否 则转至 2 继续这种标定过程 第八步 在标以 的元素中 找出绝对值最小的元素 令此元素为xkl 根据以下计算公式更新运输矩阵xij xkl 当xij标定为 号时 xij xij xkl 当xij标定为 号时 xij 在其它情况下 删去所有标记并转至第一步 示例 给定具有 10 4 6 组货单的三个仓库以及要求 5 12 8 组货物的三家用户 每组货物的运费矩阵为 需大于供 加入一虚拟的仓库 按西北角法 求得初始可行解X 1 根据步进法 可求得该运输矩阵的检验数 进一步迭代结果为 对任意i j dij 0 所以X 4 给出了货物运输路线的最佳分配方案 最优方案的表格形式如表1 19 表1 19产销平衡 运价矩阵表 销地 1 6运输问题编程算法与编程实践 1 6 2运输问题的算法和原理 1 6运输问题编程算法与编程实践 1 6 3运输问题的程序流程图 1 西北角法求初始调运方案的程序流程图 开始 是 输出初始可行调运方案X 输入 供应站的数量m 需求站的数量n 输入 运价矩阵C 供应站的供应量A 需求站的需求量B 定义 所有供应站的下标的集合RR i 所有需求站的下标的集合SS j 根据r min i iRR s min j jSS 求待分配元素 确定 min ar bs 并令xrs ar ar bsr bs 更新下标集合 当ar 0时 RR RR r 当br 0时 SS SS s RR为空集 SS为空集 停止 2 步进法求最优调运方案的程序流程图 读取初始可行调运方案X drs 0 s列中有元素标以 是 是 否 输出最优解 停止 开始 在r行中找满足条件的元素标以 计算基变量的检验数 计算位势 计算非基变量的检验数 标定退化元素 求检验数的最大值drs 否 给元素xrs标以 号 在标有 的之中找出绝对最小者 在s行中找满足条件的元素标以 更新运输矩阵 1 6运输问题编程算法与编程实践 1 6 3运输问题的程序流程图 1 6 4运输问题的实例及操作 1 6运输问题编程算法与编程实践 1 实例例1 设中国电子元件公司在上海 武汉 桂林分别设有电容器元件制造厂 它的区域性批发总部在大连 北京 广州和重庆 公司当月在三个产地工厂生产电容器的数量是上海50单位 武汉80单位 桂林120单位 为了满足各批发总部预测市场的需求量 公司必须运送90单位到大连 70单位到北京 40单位到广州 50单位到重庆 公司要求确定一个最优的运输方案 既要满足各批发总部的需求量 又要使运输成本最小 试问 该如何分配运输方案 解 根据数据分析 这是一个平衡运输问题 有关单位产品的运输成本以及需求量和供应量可归结如表1 20所示数据 表1 20供需平衡 运价矩阵表 销地