5-2运筹学课件.ppt

运筹学 1 29 5 1目标规划求解方法 一 图解法 二 单纯形方法 三 用LINGO软件求解 运筹学 2 29 图解法同样适用两个变量的目标规划问题 但其操作简单 原理一目了然 同时 也有助于理解一般目标规划的求解原理和过程 图解法解题步骤如下 1 确定各约束条件的可行域 即将所有约束条件 包括目标约束和绝对约束 暂不考虑正负偏差变量 在坐标平面上表示出来 2 在目标约束所代表的边界线上 用箭头标出正 负偏差变量值增大的方向 一 图解法 运筹学 3 29 3 求满足最高优先等级目标的解 4 转到下一个优先等级的目标 再不破坏所有较高优先等级目标的前提下 求出该优先等级目标的解 5 重复4 直到所有优先等级的目标都已审查完毕为止 6 确定最优解和满意解 例1用图解法求解目标规划问题 s t 运筹学 4 29 0 12345678 123456 A x2 x1 B C B 0 6250 4 6875 C 0 5 2083 B C线段上的所有点均是该问题的解 无穷多最优解 s t 图5 1 运筹学 5 29 在图解法求解两个变量的目标规划问题时 第一级目标的最优解可以在绝对约束确定的可行域中寻找 而第二级目标的最优解只能在第一级目标的最优解集合中寻找 这样才能保证优先级在前的目标先达到最优 在例1中 BC线段上的所有点使两级目标都达到最优 因此此时Z 0 但一般来说 这是很难实现的 因此通常只能找到问题的满意解 一 图解法 运筹学 6 29 二 单纯形方法 目标规划模型仍可以用单纯形方法求解 但要注意 因为目标函数都是求最小值 所以 最优判别检验数为 后一等级目标的最优解只能在前一等级最优解的最优解集合中寻找 因此如果前一等级目标的最优解是唯一解 不是无穷大个 则后一等级目标的解只能是满意解 迭代就结束了 运筹学 7 29 例2试用单纯形法求解目标规划问题 运筹学 8 29 解 首先将这一问题化为标准形式 取 为初始基变量 列出初始单纯形表 运筹学 9 29 检验数的计算 以P1行检验数为例 此时第一级目标函数为 即价值系数向量为 0 0 0 0 1 0 0 0 0 T 表中第一列 CB列 均为0 因此P1行检验数为 0 0 0 0 1 0 0 0 0 检查P1行检验数 因该行无负检验数 第一级目标有无穷多个最优解 故可在第一级目标最优解结合中求第二级目标的最优解 表1 运筹学 10 29 检查P2检验数 有两个负的检验数 1 2 因为有min 1 2 2 实质上还是最大检验数原则 所以x2为换入变量 计算最小比值 所以为换出变量 进行换基运算 得到新的单纯行表 表2 以此类推 直至得到最终单纯形表 表3 为止 运筹学 11 29 表2 运筹学 12 29 表3 由表3可知 为满意解 此时也是最优解 检查检验数行 发现非基变量的检验数为0 这表明该问题存在多重解 运筹学 13 29 表4 从表4可以看出 也是该问题的满意解 在表3中 以非基变量为换入变量 为换出变量 经迭代得到表4 运筹学 14 29 三 用LINGO软件求解 运筹学 15 29 1 求解方法概述 LINGO 或LINDO 不能直接求解目标规划问题 但可以通过逐级求解线性规划的方法 求得目标规划问题的满意解 三 用LINGO软件求解 运筹学 16 29 2 示例 例3用LINGO求解目标规划问题 运筹学 17 29 解 首先对应于第一优先等级 建立线性规划问题 用LINGO求解 得最优解 0 最优值为0 具体求解过程如下 运筹学 18 29 启动LINGO软件 窗口如图5 2所示 图5 2 运筹学 19 29 在LINGO工作区中录入以下程序 参见图5 3 model min d1 10 x1 15 x2 d1 d1 40 END其中x1 x2分别代表决策变量 d1 d1分别代表偏差变量 运筹学 20 29 图5 3 运筹学 21 29 在菜单LINGO下点选 Solve 或按复合键 Ctrl S 进行求解 LINGO弹出求解结果报告 参见图5 4 详细信息如下 图5 4 运筹学 22 29 对应于第二优先等级 将 0作为约束条件 建立线性规划问题 用LINGO求解 得最优解 0 最优值为6 具体LINGO程序及输出信息如下 LINGO程序为参见图5 5 运筹学 23 29 图5 5 运筹学 24 29 LINGO运算后输出为 参见图5 6 图5 6 运筹学 25 29 对应于第三优先等级 将 0 作为约束条件 建立线性规划问题 用LINGO求解 得最优解是 最优值为7 具体LINGO程序 参见图5 7 及输出信息 参见图5 8 如下 运筹学 26 29 图5 7 运筹学 27 29 LINGO运算后输出为 参见图5 8