运筹学-总复习.ppt

运筹学 复习 求解如下线性规划问题 例1 复习 解 加入松弛变量 标准化得 建立单纯形表如下 复习 复习 解毕 复习 用对偶单纯形法计算 例2 复习 复习 由于初始正则解有负分量 于是取min 3 4 4x5为换出变量 取 x1为换入变量 得新基 x4 x1 51 2为主元 复习 基变换的过程 主元变为1 即用 2去除单纯形表中基变量x5所在的行 主元所在列的其它元变为0 消去非基变量x1所在的列的其余元 1 2 得新基 x4 x1 的单纯形表 复习 基变换的过程 复习 可见正则解的有负分量 由于x4 1 所以取x4为换出变量 取 x2为换入变量 得新基 x2 x1 42 5 2为主元 复习 此时正则解是可行解 也是最优解 X 11 5 2 5 0 0 0 z 28 5 进行基变换 得新正则解的单纯形表 复习 试用对偶原理求解线性规划问题 已知其对偶规划的最优解为 例3 复习 解 该问题的对偶规划为 复习 利用松紧关系 代入对偶规划的约束条件得下列约束是松约束 将最优解 松约束 紧约束 其对偶约束是紧约束 复习 设原问题的最优解为 紧约束 复习 设某种物资有3个产地A1 A2 A3 生产量分别为9 5 7 有4个销地B1 B2 B3 B4 销售量分别为3 8 4 6 已知从Ai到Bj物资的单位运价见下表 求总运费最小的调运方案 例4 复习 存在基变量为0的解称为退化解 在确定初始基可行解的过程中 如果某一步中出现情况 当产地Ai处的余量与销地Bj处的需求量相等时 在格 i j 填入运量后 产地Ai处的余量与销地Bj处的销量同时为0 相应地要划去一行和一列 这时就出现了退化 为了使基变量个数恰好有m n 1个 应在同时划去的一行或一列中的某个格中填入数字0 表示这格中的变量是取值为0的基变量 复习 伏格尔法计算1 用伏格尔法寻找初始基 先算出运价表中各行与各列的最小运费与次小运费的差额 并填入该运价表的最右列和最下行 从行差或列差中选出最大者 并选择其所在行或列的最小元素 A1的行差最大 而其中运价c11最小 令x11为优先运输路线 复习 用伏格尔法寻找初始基 销地B1的销量3全由产地A1供给 所以x21 x31 0 将x11 3填到调运方案表中第1行第1列上 画去运输数据表第一列 A1的产量剩余为9 3 6 得到新的产销平衡与单位运价表 令 伏格尔法计算1 复习 用伏格尔法寻找初始基 再算出运价表中的行差与列差 B4的列差最大 而其中运价c24最小 令x24为优先运输路线 产地A2的产量2全供给销地B4 所以x23 x24 0 画去运输数据表中第2行 B4的销量还要6 5 1 得新表 令 伏格尔法计算1 复习 用伏格尔法寻找初始基 伏格尔法计算1 复习 用伏格尔法寻找初始基 伏格尔法计算1 复习 用伏格尔法寻找初始基 现在只有一个产地两个销地 故令x12 5 x14 1为基变量 将其分别填到调运方案表中1行2列与1行4列上 得到产销平衡运输问题的一个初始方案 伏格尔法计算1 复习 此方案的运费是3 2 5 9 4 7 5 2 3 4 4 2 88 伏格尔法给出的初始解往往更接近于最优解 复习 利用伏格尔法确定的初始解如下表所示 1 写出基可行解对应的位势方程组 2 并计算非基变量的检验数 复习 求解位势及检验数的过程可在一个特殊设计的表上完成 这个表的构造如下 在原单位运价表增加一行与一列 在列中填入ui 在行中填入vj 把运价cij记在每一格的右上角 用框标定 在基变量对应的格中标出0 构成表 复习 由u1 v1 2 u1 v2 9 u1 v4 7 得v1 2 v2 9 v4 7 0 5 5 2 9 7 7 位势表 再由u2 v4 2 u3 v2 4 得u2 5 u3 5 最后由u3 v3 2得v3 7 取u1 0 复习 检验数表 计算所有非基变量的检验数 0 5 5 2 9 7 7 3 4 1 2 11 3 当存在非基变量的检验数 kl 0 说明现行方案为最优方案 否则目标成本还可以进一步减小 复习 伏格尔法的初始方案 3 4 1 2 11 3 x22为换入变量 从x22所在格出发做闭回路L L中有两个偶点x24 x12 取x12为换出变量 调整量为5 复习 伏格尔法的调整方案 在闭回路L上 偶点变量减5 奇点变量加5 0 x22为换入变量 取x12为换出变量 0 6 5 复习 它所对应的位势与检验数为 2 8 6 7 0 5 4 1 4 4 3 10 2 所有检验数都非负 迭代停止 运费为 3 2 6 7 5 3 3 4 4 2 83 复习 P1 充分利用现有工时 必要时可以加班 P2 A B C的最低产量分别为5 5 8台 并依单位工时的利润比例确定权系数 P3 生产线加班时每月不超过20小时 P4 A B C的月销售指标分别定为10 12 10台 依单位工时利润比例确定权系数 试建立目标规划模型 A B C三种计算机 在一条生产线上装配 装配时间分别为5 8 12小时 利润分别为每台1000元 1440元 2520元 生产线每月正常运转170小时 该厂的经营目标为 例5 复习 复习 在5个地点中选3处建生产同一产品的工厂 在这5个地点建厂所需投资 占用农田 建成以后的生产能力等数据如下表所示 现在有总投资800万元 占用农田指标60亩 应如何选择厂址 使建成后总生产能力最大 例6 复习 复习 解 设五个0 1变量x1 x2 x3 x4 x5 其中 i 1 2 3 4 5 建立整数规划模型为 利用割平面算法求解下面的规划问题 例7 复习 解 将约束条件的系数化整 去掉 x1 x2是整数 的条件 得到一个线性规划的标准型 LP1 为 利用单纯形法求解这个线性规划问题 得出最终单纯形表 复习 最优解不是整数解 由最终表得到变量之间的关系 将上面的约束条件当中的变量和系数改写成整数与非负真分数的和 把整数部分放在左边 非整数部分放在右边 下面增加割平面 选真分数最大的一个 由于上式左端是整数 因此右端也应是整数 由于变量都是不小于0的整数 所以上式右端必是一个不大于0 5的整数 即 称这个不等式为一个割平面 引入一个松弛变量 化割平面为 将它作为一个新增加的约束条件加入线性规划LP1中得到一个新的线性规划LP2 或者直接反映到LP1的最终单纯形表中 得LP2单纯形表 割平面的处理 复习 LP2的单纯形表 LP1 LP2 复习 由于不是整数解 找出不满足条件的基变量x1 用对偶单纯型法求解 复习 将它作为一个新增加的约束加到线性规划LP2中又得一个线性规划LP3 构造线性规划LP2的割平面 复习 LP3 LP3的单纯形表 复习 从上表中我们可以看到 已经找到了整数最优解 x1 4 x2 1 故求解结束 用对偶单纯型法求解 复习 有一份资料 要分别译成四种文字 现有甲 乙 丙 丁四人可以承担这项工作 因为各人专长不同 他们翻译成不同文字所需要的时间用效率矩阵C表示 应如何分配工作 使他们完成任务的总时间最短 例8 Step1 先对效率矩阵进行列变换 使其各行各列中都出现0元素 效率矩阵变换方法为 从效率矩阵C的每行元素中减去该行的最小元素 得矩阵B 从矩阵B中每列元素中减去该列的最小元素得矩阵C1 min0050 Step2 确定C1中线性独立的0元素 从第一行开始 若该行只有一个0元素 就对这个0元素加圈 然后划去其所在列的其它0元素 若该行没有其它0元素或有两个以上0元素 已划去的不计 转下一行 直到最后一行为止 然后 从第一列开始 若该列只有一个0元素 就对这个0元素加圈 同样不考虑已划的 再划去其所在行的其它0元素 若该列没有0元素或有两个以上0元素 则转下列直到最后一列为止 重复上述步骤 上述步骤可能出现三种情况 情况一 矩阵每行都有一个打圈的0元素 此时得到问题的最优解 情况二 有多于两行或两列存在两个以上的未处理的0元素 即出现0元素的闭回路 此时 可从中任选一个0元素加圈 划掉其同行同列的0元素 再重复上述两个步骤 情况三 矩阵中所有0元素或被加圈 或被划去 而已加圈的0元素m小于矩阵的行数n 即矩阵中至少存在有一行不含加圈的0元素 转步骤三 Step3寻找能覆盖C1中所有0元素的最小直线数 1 按照从上到下 从左到右的顺序对C1没有加圈的0元行打 号 2 对已打 号的行中未加圈0元的列打 号 3 对已打 号的列中加圈0元的行打 号 4 重复下去 直到找不出打 号的行 列为止 5 对没打 号的行划一横线 对打 号的列划一纵线 这就是覆盖矩阵C1中所有0元素的最小直线数 Step4 改进C1 1 寻找C1没有被直线覆盖的所有元素中的最小元素 例中 2 2 在已打 号的行中减去 3 在已打 号的列中加上 得到一个新矩阵C2 用C2代替C1 返回步骤2 即例题的最优分配方案 确定C2中线性独立的0元素 应用动态规划求解