运筹学绪论、第一章 2.ppt

OR1 operations research 1 课程简介 要求 考勤：旷课按考勤次数从平时成绩中逐级扣分；有事请请假. 课堂：认真听讲，做好笔记. 成绩：平时30%（包括考勤和平时作业）+期末考试70%. 绪论 内容提要 一、运筹学简介 二、运筹学发展简史 三、主要研究内容 四、运筹学的工作步骤 五、运筹学的性质与特点 六、如何学好运筹学 运筹学的称谓 美国：Operations Research 英国：Operational Research 缩写： OR 日本译作“运用学”， 香港、台湾译为“作业研究”， 我国学者从古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，充分体现了这门学科运心筹谋、 策略取胜的精髓。译作“运筹学”。 北美：Management Science 管理科学 1938年7月，波德塞(Bawdsey)雷达站的负责人罗伊(A．P．Rowe)提出立即进行整个防空作战系统运行的研究，用“operational research” 一词作为这方面研究的描述，这就是O.R.（运筹学)这个名词的起源。 3、寻找改进的基可行解 约束方程组的系数矩阵： 初始基 ， 变量 换入, 换出， 新可行解 对应向量： 是线性无关的， 故 是基可行解。 s.t. 单纯形法的求解思路 确定一个初始基可行解 是否最优 改进为新的基可行解 最优解 是 否 循 环 结束 化标准形 ？ 步骤简单总结 经过何种运算可转到第③步，实现循环迭代？ ① 将线性规划问题化成标准形式; ② 找出或构造一个m阶单位矩阵作初始可行基，得到初始基可行解; ③ 计算各非基变量xj的检验数?j，若所有?j≤0，则问题已得到最优解，停止计算，否则转入下步; ④ 若存在某个?s0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步; ⑤ 根据max {?j | ?j＞0} = ?k 原则，确定xk为入基变量，再按? = min {bi /aik | aik＞0} = bl /alk 规则，确定xl为出基变量，得到改进的基可行解。 将其化为单位矩阵， 则LP问题形式为 s.t. 4、迭代运算 初始基 ， 变量 换入, 换出， 新可行基： s.t. 4、迭代运算 ① 主元素 所在行 ： ② 其余行 ： 4、迭代运算 新检验数 s.t. 整理后可得 ① 将线性规划问题化成标准形式; ② 找出或构造一个m阶单位矩阵作初始可行基，得到初始基可行解; ③ 计算各非基变量xj的检验数?j，若所有?j≤0，则问题已得到最优解，停止计算，否则转入下步; ④ 若存在某个?s0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步; ⑤ 根据max {?j | ?j＞0} = ?k 原则，确定xk为入基变量，再按? = min {bi /aik | aik＞0} = bl /alk 规则，确定xl为出基变量； ⑥ 以alk为主元素进行迭代，利用初等行变换将xk所在列化 为单位向量，即alk化为1，其它元素化为0，得到改进的 可行基，转入第③步。 计算步骤总结 (四)单纯形表格法——单纯形表 s.t. …… max x1, x2 ≥0 s.t. 2x1 + 2x2 ≤ 12 z = 2x1 + 3x2 4x1 ≤ 16 5x2 ≤ 15 例题：用单纯形法求解线性规划问题 + 0x4 + 0x3 max z = 2x1 + 3x2 s.t. 引入变量 得到标准形式 解： + 0x5 5x2 + x5 = 15 4x1 + x4 = 16 2x1 + 2x2 + x3 = 12 x1, x2, x3, x4, x5 ≥0 + 0x4 + 0x3 max z = 2x1 + 3x2 s.t. 引入变量 得到标准形式 解： + 0x5 5x2 + x5 = 15 4x1 + x4 = 16 2x1 + 2x2 + x3 = 12 x1, x2,