运筹学胡运权第一章

1、 胡运权 清华大学出版社运筹学 施泉生 中国电力出版社, 2004.7运筹学习题集(第三版) 胡运权,清华大学出版社,2002.9 “运筹学” O.R. Operations Research (美国) Operational Research (英国) 在现有的条件下，如何科学地设 计和操作某复杂系统，使其在某 种意义上达到最优。本 课 程 内 容规划论：线性规划、非线性规划、整数规划、动态规划、网络规划、多目标规划、随机规划、图与网络分析：关键路线、最短路、最大流、最小树、各种模型与问题：运输问题、分派问题、存贮论、排队论、决策论、对策论、软 件 Excel Matlab Lindo, L

2、ingo 名称由来： 二次大战 课程设置： 1948年麻省理工学院 学术团体： 1957年 英国牛津大学 第一届国际运筹学会议 1959年 “国际运筹学联合会” 学术刊物： 1950年 英国“运筹学季刊” 我国大陆译作 “运筹学”，是借用了 史记-汉高祖本纪 “运筹于帷幄之中，决胜于千里之外” 一语中“运筹”二字，既显示其军事的起 源，也表明它在我国已早有萌芽。 本课程的研究方法从现实生活场合抽出本质的要素来构造数学模型，因而可寻求一个跟决策者的目标有关的解；探索求解的结构并导出系统的求解过程；从可行方案中寻求系统的最优解法。 本 课 程 的 特 点被广泛用于工程建设、企业管理、军事部门、，具

3、有很强的实践性。是一门优化技术，提供的是解决各类问题 的优化方法。是数学模型竞赛中使用的主要工具。运筹学解决问题的步骤提出问题：用自然语言描述问题。建立模型：用变量、函数、方程描述问题。求解：用数学方法求出模型的最优解、次优解、满意解，复杂模型求解要用计算机。解的检验：检查模型和求解步骤有无错误，检查解是否反映现实问题。决策实施：决策者根据自己的经验和偏好，对方案进行选择和修改，作出实施的决定。运筹学的应用市场销售、生产计划、资本运营、 库存管理、运输问题、财政和会计、 人事管理、设备维修和更新、 项目评价和选择、工程优化设计、 计算机和信息系统、城市管理、发展战略、 本 课 程 要 求 熟练

4、掌握各种模型及其求解方法。 掌握与基本模型有关的基本概念及基本原理。 领会原理、掌握方法、强化应用， 提高解决实际问题的能力。 中国： 都江堰水利工程 (公元前250年)丁谓修开封皇宫 (北宋年间)齐王赛马 (齐王与田忌) 外国： 哥尼斯堡七桥问题 (1736) 欧拉 二战期间： 反潜艇问题 (英吉利海峡) 渡大西洋船队规模问题 德国“飞弹”袭击伦敦问题 线性规划：LP求有线性约束的线性函数的最优解。第一章 线性规划及单纯形法 线性规划是运筹学的重要内容。本章介绍 (1) 线性规划数学模型; (2) 线性规划的基本理论; (3) 求解线性规划的基本算法单纯形法。G.B.Dantzig 于194

5、7年提出了求解线性规 划问题的单纯形法。单纯形法至今还是求解线性规划最有效的方法。 解：将这个问题化为线性规划模型:1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大 max (50 x1+30 x2)3确定约束条件： 4x1+3x2 120（木工工时限制） 2x1+x2 50 （油漆工工时限制）4变量取值限制：决策变量只取正值（非负值） x1 0, x2 0 数学模型 max (50 x1+30 x2) s.t. 4x1+3x2 120 2x1+ x2 50 x1, x2 0线性规划数学模型三要素： 决策变量、约束条件、目标函数 每一个线性规

6、划问题都有一组决策变量 (x1, x2, , xn) , 这组决策变量的值就代 表一个具体方案。 有使用各种资源的的约束条件。 有一个要达到的目标，是决策变量的线性函数。 一般形式 矩阵形式 标准形式 将一般线性规划化成标准形线性规划问题的一般形式：max(min) Z = c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )b2 . am1x1+am2x2+.+amnxn (=, )bm x1, x2, ., xn 0线性规划的矩阵形式： max Z = CTX s.t. AX=b X 0a11

7、a12 . a1n b1 A = a21 a22 . a2n b = b2 . am1 am2 . amn bmc1 x1 0 c2 x2 0C = X = 0 = . cn xn 0线性规划问题的标准形式：max Z = c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn = b1 a21x1+a22x2+.+a2nxn = b2 . am1x1+am2x2+.+amnxn = bm x1, x2, ., xn 0其中：bi 0, i=1, 2,., m.四点要求:将一般线性规划化成标准形 求max 等式约束 bi 0 xi 0(1) 若目标函数是求最小值: m

8、in Z = CTX 令 Z = Z, 则化成 max Z= CTX注意: 因为 min Z = max(Z ) 所以变换后的最优解不变，最优值变号。(2) 若约束条件是不等式i)若约束条件是“ ” 不等式， 则不等式左边 “加上” 非负的松驰变量；ii)若约束条件是“ ” 不等式， 则不等式左边 “减去” 非负的松驰变量。(3) 若约束条件右面的某一常数项 bi0, 这时只要在 bi 相对应的约束方程两边乘 1。(4) 若变量 xj 无非负限制 引进两个非负变量 xj xj” 0 令 xj= xj xj（可正可负）任何形式的线性规划总可以化成标准型例 将下列问题化成标准型: min Z =

9、x1+ 2x2 3x3 s.t. x1+ x2 + x3 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制例 将下列问题化成标准型: max ( x1 2x2 + 3x3) s.t. x1+ x2 + x3 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制例 将下列问题化成标准型: max ( x1 2x2 + 3x3) s.t. x1+ x2 + x3 + x4 = 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制例 将下列问

10、题化成标准型: max ( x1 2x2 + 3x3) s.t. x1+ x2 + x3 + x4 = 7 x1 x2 + x3 x5 = 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制max ( x1 2x2 + 3x3 3x3) s.t. x1+ x2 + x3 x3 + x4 = 7 x1 x2 + x3 x3 x5 = 2 3x1 + x2 + 2x3 2x3 = 5 x1 0, x2 0, x30, x30 令 x3 = x3 x30, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxx

11、f不限不限原非标准型原非标准型0, ,20040065300432.423)(min:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非标准型原非标准型 0,2004006653004432.0004423)(max:65433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf标准型标准型 P43 1.2， 先画可行域(满足约束条件的X的全体)两个变量LP问题的图解法 再画法线方向 求 max，沿法线方向推； 求 min，沿负法线方向推。 最后的交点为顶点。例 max Z = 50 x1+30 x2

12、s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 0 x240302010102030 x1 由 4x1+3x2 120 x1 0, x2 0 围成的区域50 由 2x1+x2 50 x1 0, x2 0 围成的区域x240302010102030 x1 由 4x1+3x2 120 2x1+x2 50 x1 0, x2 0 围成的区域 (可行域)50可行域x240302010102030 x1 该问题的可行域是由 Q1，Q2，Q3，Q4 作为顶点的凸多边形50可行域Q1(0, 0)Q2(25, 0)Q4(0, 40)Q3(15, 20)x240302010102030 x1

13、目标函数 Z = 50 x1+30 x2 是一组平行线50可行域x240302010102030 x1 此组平行线沿其 法线方向 (50, 30) 右上方 函数值 Z 增加50可行域x240302010102030 x1当该直线移到 Q3(15, 20)点时，Z 值达到最大： max Z=5015+3020=1350此时最优解 X*=（15，20）50Q3(15, 20) 最优解必定能在某一个顶点上取得。 P43 1.1LP问题最优解的归类 可行解：满足约束条件（包括非负条件）的 一组变量值，称可行解。 可行域：可行解的全体。 最优解：使目标函数达到最大的可行解。 最优值：将最优解代入目标函数

14、得到的值。 可行域为空集无可行解 可行域非空，则有三种情况：i) 有唯一解 (顶点)ii) 有无穷多个解 (两个顶点间的连线)iii) 无最优解 (无界解)无最优解x240302010102030 x1 当目标函数由 max Z=50 x1+30 x2 变成 max Z=40 x1+30 x2 目标函数是同约束条件 4x1+3x2 120 平行的直线 Q2与Q3之间都是最优解50Q3(15, 20)Q2(25, 0)无界解若可行域无界， 且目标函数值可增加(减少)到正无穷(负无穷)， 称这种无最优解的情况为无界解。注意 可行域无界，不一定无最优解； 可行域非空有界，则必定有最优解。定义 (凸集)LP问题解的性质设 D Rn 若任对 X1, X2 D，对一切 0 0 中找最大者， j* = maxj ; j 0 选中者对应的变量称为进基变量， xj* 第 j* 列称为主列.换基迭代确定离基变量：如果有* *min0 =iiijiiji jbbaaa则xi* 为离基变量第 i* 行称为主行换基