运筹学(Operations Research).ppt

1 1 运 筹 学 (Operations Research) 西安建筑科技大学管理学院 绪 论 运筹学的定义 运筹学的特点 运筹学的工作步骤 运筹学的模型 运筹学的模型 运筹学的模型 运筹学的模型 运筹学的分支 运筹学的应用 线性规划 线性规划问题 资源利用问题 资源利用问题 投资计划问题 投资计划问题 投资计划问题 线性规划标准形式 模型转换 模型转换实例 模型转换实例 线性规划解的概念 线性规划解的概念 线性规划解的基本定理 线性规划的图解法 线性规划的图解法 线性规划的图解法 线性规划的图解法 线性规划的图解法 单纯形法基本思想 单纯形法 单纯形法 单纯形法 单纯形法 单纯形法 单纯形法 单纯形法 单纯形表 单纯形表 单纯形表 单纯形表 单纯形表 单纯形表 单纯形法的进一步讨论 单纯形法的进一步讨论 单纯形法的进一步讨论 大M法 大M法 大M法 两阶段法 两阶段法 两阶段法 两阶段法 线性规划小结 线性规划小结 将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基本可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基本可行解，当目标函数达到最大时，得到最优解。 例 1 变成标准型 约束方程的系数矩阵 为基变量 为非基变量 I 为单位矩阵且线性独立 令： 则： ∴ 基本可行解为（0 ,0 ,12, 8, 16 ,12） 此时，Z = 0 然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。 注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。 找出一个初始可行解 是否最优 转移到另一个目标函数 （找更大的基本可行解） 最优解 是 否 循 环 直到找出为止，核心是：变量迭代 结束 当 时， 为换入变量 确定换出变量 为换出变量 接下来有下式： 用高斯法，将 的系数列向量换为单位列向量，其步骤是： 结果是： 代入目标函数： 有正系数表明：还有潜力可挖，没有达到最大值； 有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当 时，即不再利用这些资源。 此时：令 得到另一个基本可行解 （0，3，6，2，16，0） 如此循环进行，直到找到最优为止。 本例最优解为： (4，2，0，0，0，4） 判定标准： 若求 或 例 2 0 -Z 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1 12 8 16 12 x3 x4 x5 x6 0 0 0 0 x1 x2 x3 x4 x5 x6 b xB cB 2 3 0 0 0 0 cj 2 3 0 0 0 0 12/2 8/2 － 12/4 -Z 4 0 0 0 1 0 16 x3 x4 x5 0 0 0 x1 x2 x3 x4 x5 x6 b xB cB 2 3 0 0 0 0 cj, 3 x2 3 0 1 0 0 0 1/4 2 6 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 -9 -Z 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4 6 2 16 3 x3 x4 x5 x2 0 0 0 3 x1 x2 x3 x4 x5 x6 b xB cB 2 3 0 0 0