运筹学 解最优性检验.ppt

Ludong University 解的最优性检验 检查当前调运方案是不是最优方案的过程 就是最优性检验。检查的方法:计算非基变量 (未填上数值的格,即空格)的检验数(也称 为空格的检验数),若全部大于等于零,则该 方案就是最优调运方案否则就应进行调整。 Ludong University 1、闭回路法 以确定了初始调运方案的作业表为基础,以一个非 基变量作为起始顶点,寻求闭回路。 该闭回路的特点是:除了起始顶点是非基变量外, 其他顶点均为基变量(对应着填上数值的格) 可以证明,如果对闭回路的方向不加区别,对于每 一个非基变量而言,以其为起点的闭回路存在且唯 m+n-1个变量构成基变量的充要条件是它 们不构成闭回路。 ⑦烹大字 Ludong University 了例设m三3,n=4,决策变量x表示从产地A到销地的 调运量,列表如下,给出闭回路 {x1,x3,x3,x3,x,x21在表中的表示法—用折线 连接起来的顶点变量。 x Ludong University 请给出闭回路 asoa.aasr {x2,x2,x3,x3,x1,x12在表中的表示法。 B 23 31 32 X 34 ⑦烹大字 下面的折线构成的封闭曲线连接的顶点变量 哪些不可能是闭回路? 口个 (a) b) (d) e 表中的折线构成一条封闭曲线,且所有的 边都是水平或垂直的; 表中的每一行和每一列由折线相连的闭回 路的顶点只有两个; Ludong University 约定作为起始顶点的非基变量为偶数次顶点, 其它顶点从1开始顺次排列,那么,该非基变 量x的检验数: (闭回路上偶数次顶点运价之和)·(闭 回路上奇数次顶点运价之和) 现在,在用最小元素法确定上例初始调运方 案的基础上,计算非基变量X2的检验数 Ludong University 的B1B2B3B4产量 A1 16 A2 10 A3 22 销量814121448 Ludong University 非基变量的检验数: G11=cmC21+c23C13=42+3-4=1 O2=C223+e-C4+eu3-C210.5+611+43=1 12=C12C32+c3x4-C1=125+6-11=2 O24=C24-C14+C13-C23=9-11+4-3=-1 10 12 Ludong University 检验数表 B1B2B3B4产量 A11 16 A2 10 A310 12 22 销量814121448 Ludong University 2、位势法(对偶变量法) 原问题 对偶问题 MmZ=∑∑c maxz ∑a4+∑b l1+ s,t st 1.2 xn≥0.i=1 n j=1,2,n ,符号不限