基变量检验数x.ppt

复习 题1：已知线性规划问题： 其最优解为x1=-5,x2=0,x3=-1. （a）求k的值； （b）写出并求其对偶问题的最优解。 题2：对于下述线性规划问题： 已知最优解中的基变量为x3,x1,x5,且已知 求：根据上述信息确定三种资源各自的影子价格 复习 题3：已知线性规划问题： 当t1=t2=0时，求解得最终单纯形表如下表所示： (a)确定c1,c2,c3,a11,a12,a13,a21,a22,a23和b1，b2的值； (b)确定其对偶问题的最优解；(c)当t2=0时，t1在什么范围内变化上述最优解不变；(d)当t1=0时，t2在什么范围内变化上述最优解不变。 x1 x2 x3 x4 x5 x3 5/2 0 ? 1 ? 0 x1 5/2 1 -1/2 0 -1/6 1/3 cj-zj 0 -4 0 -4 -2 本讲内容 什么是运输问题(transportation problem) 平衡运输问题（balanced transportation problem）的解法 产销不平衡问题 什么是运输问题？ 运输问题的一般提法 产销平衡问题 已知：m各产地A1 , …, Am ，产量分别为：a1 , …, am n 个销售地B1,…, Bn ，销量分别是: b1 ,…, bn 产销平衡，即: 由Ai→Bj的运价为cij 问：应如何调运使总运费最省？即求Ai→Bj 的运量xij ，使运费可达极小化。 产销不平衡问题： 此时分为两种情形来考虑： 供不应求：即产量小于销量时有 供过于求：即产量大于销量时有 两种形式都可以转化为 的形式求解。 运输问题的模型 产销平衡问题模型： s.t. 约束方程中：m×n个变量，m+n个约束 模型特点： 变量多（ m×n 个），结构简单 m + n个约束中有一个是多余的（因为其间隐含有一个平衡关系式Σai=Σbj ），所以，R(A)= m + n ?1，即解的m× n个变量中基变量为m + n ?1个。 如何求解运输问题？ 表上作业法 其步骤如下： （1） 确定一个初始可行调运方案。可以通过最小元素法、西北角法、Vogel 法来完成； （2） 检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优； （3）方案调整，从当前方案出发寻找更好方案，常采用闭回路法。 常用解法 最小元素法（确定初始方案）→闭回路法（检验当前方案）→闭回路法（方案调整） 例 1：某食品公司下设3 个加工厂A1，A2，A3，和4 个门市部B1，B2，B3，B4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如表1.1 和1.2 所示。问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？ 表1.1 产销平衡表 单位：吨 表1.2 单位运价表 单位：元/吨 (1)确定初始方案 最小元素法，就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，直到给出初始方案为止: 销地 产地 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 20 3 1 4 6 3 3 从上表可知，x21=3，x32=6，x13=4，x23=1，x14=3，x34=3（有数格） x11=x31=x12=x22=x33=x24=0（空格） 注：（ⅰ）有数格是基变量，共m + n ?1=3+4-1=6 个。空格是非基变量，共划去m + n = 7条线。 （ⅱ）如果填上一个运量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数个对待（此时产生的初始方案实质是退化的基本可行解）。 初始方案运费 Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元) (2)最优性检验 闭回路法:计算空格的检验数 ①找出任意空格的闭回路—除此空格外，其余顶点均为有数格。如可找（ A1B1）→（A1B3）→（A2B3）→（A2B1）→（ A1B1） ； ②计算出空格的检验数—等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的代数和。如σ11＝c11-c13+c13-c21=3-3+2-1＝1; ③计算出所有空格的检验数σij，若σij ≥ 0，则该方案为最优方案，否则转３； 表1.3 初始方案表 闭回路： 注：检验数的经济意义，以σ11为例，空格表示原方案中x11=0，即A1→ B1 的运输量为0。若试着运1单位，则这样所引起的总费用的变化恰是σ11，可见检验数σ