《怎样把事情做到好》由会员分享，可在线阅读，更多相关《怎样把事情做到好（70页珍藏版）》请在金锄头文库上搜索。
1、OPERATIONS RESEARCH 运筹学 怎样把事情做到最好 郝英奇 OR11 第一章 绪论 w 1.1题解 Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本运用学 港台作业研究 中国大陆运筹学 Operational Research原来名称，意为军事行动研究 历史渊源 OR12 绪论 w 1.2 运筹学的历史 早期运筹思想：田忌赛马 丁渭修宫 沈括运粮 Erlang 1917 排队论 Harris 1920 存储论 Levinson 1930 零售贸易 康脱洛维奇 1939 LP OR13 绪论 w 1.2运筹学的历史 军事运
2、筹学阶段 德军空袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队 OR14 绪论 w 1.2运筹学的历史 管理运筹学阶段 战后人员三分:军队、大学、企业 大学：课程、专业、硕士、博士 企业：美国钢铁联合公司 英国国家煤炭局 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题 OR15 1.3学科性质 应用学科 Morse饲料II x2kg;饲料III x3kg w 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5 w 约束条件：3x2+2x2+x3+6x4+18x5 700 营养要求： x1+0.5x2+0.2x3+
3、2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200 用量要求： x1 50,x2 60,x3 50,x4 70,x5 40 非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0 OR116 例题3：人员安排问题 w 医院护士24小时值班，每次值班8小时。 不同时段需要的护士人数不等。据统计： 序号时段最少人数安排人数 1061060X1 2101470X2 3141860X3 4182250X4 5220220X5 6020630x6 OR117 例题3建模 w 目标函数：min Z=x1+x2+x3+x4+x5+x6 w 约束条件： x1+x2 70
4、 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 非负性约束：xj 0,j=1,2,6 OR118 归纳：线性规划的一般模式 w 目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn w 约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn 非负性约束：x1 0,x2 0,xn 0 OR119 2.1.2线性规划图解法 w 由中学知识可知：y=ax+b是一条直线，同 理：Z=70x1+120x2x2=70/120x
5、1-Z/120也是 一条直线，以Z为参数的一族等值线。 9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。 所有半平面的交集称之为可行域，可行域 内的任意一点，就是满足所有约束条件的 解，称之为可行解。 OR120 例1图示 . 90 80 60 40 20 0 20 40 60 80 100 x1 x2 9x1+4x2 360 4x1+5x2 200 3x1+10x2 300 A B C DEF G H I Z=70x1+120x2 OR121 概念 w 概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条
6、件的交 集，也就是各半平面的公共部分。满足所有约束 条件的解的集合，称为可行域。 3、基解：约束条件的交点称为基解（直观） 4、基可行解：基解当中的可行解。 5、凸集：集合内任意两点的连线上的点均属于这 个集合。如：实心球、三角形 OR122 结论 w 可行域是个凸集 w 可行域有有限个顶点 w 最优值在可行域的顶点上达到 w 无穷多解的情形 w 无界解情形 w 无解情形 OR123 2.1.3线性规划的标准型 w 代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0
7、 j=1,2,n OR124 线性规划的标准型 w 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n j=1 n n j=1 OR125 线性规划的标准型 w向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) T n j=1 OR126 线性规划的标准型 w 矩阵式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn OR127 标准型的特征 w 目标函数极大化 w
8、约束条件为等式 w 决策变量非负 OR128 非标准型转化为标准型 w 目标函数极小化转为极大化： minZ=max(Z) ，一个数的极小化等价于其相反数的 极大化。 w 不等式约束的转化： aijxjbi 加入松弛变量 aijxjbi 减去剩余变量 w 非正变量：即xk 0 则令xk = xk 自由变量：即xk无约束，令xk= xkx”k OR129 非标准型转化举例之一 maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5
9、=300 X10 X20 Xj0 j=1,2,5 OR130 非标准型转化举例之二 minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 OR131 2.1.4基可行解 w 基的概念：如前所述LP标准型 和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX
10、 AX=b X 0 约束方程的系数矩阵A的秩为m，且m0 =bL/ aLk 。 这时原基变量XL=0，由基变量变成非基变量， aLk处在变量转换的交叉点上，称之为枢轴元素 j 0 OR140 单纯形法解题举例 单纯形表的格式： CjC1 C2 Cn i CBXBb x1 x2 . xn C1 C2 Cm x1 x2 xm b 1 b2 bm a11 a12 a1n a21 a22 a2n am1 am2 amn 1 2 m j 1 2 n OR141 CjC1 C2 Cn CBXBb X1 X2 X3 X4 X5j 0 0 0 X3 X4 X5 360 200 300 9 4 1 0 0 4
11、5 0 1 0 3 10 0 0 1 90 40 30 j0 70 120 0 0 0 0 0 120 X3 X4 X2 240 50 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.1 30.76 20 100 j 3600 34 0 0 0 -12 70 120 0 X3 X1 X2 84 20 24 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16 j4280 0 0 0 -13.6 -5.2 OR142 2.2.3单纯形法的计算步骤 w 找到初始可行基，建立单纯形表 w 计算检验数，若所有j 0
12、则得最优解，结束。否 则转下步 w 若某K 0而PK 0 ，则最优解无界，结束。否则 转下步 w 根据max j = K 原则确定XK 进基变量；根据 规则 ： = min bi / aik aik 0 = bL/ aLk 确定XL为 出基变量 w 以aLk 为枢轴元素进行迭代，回到第二步 OR143 2.3单纯形法的进一步探讨 w 2.3.1极小化问题直接求解：检验数的判别 由所有j 0 即为最优，变为所有j 0则为 最优。 w 人工变量法之一：大M法 人工变量价值系数M 例 w 人工变量法之二：构造目标函数，分阶段求解 例 w 2.3.2无穷多最优解情形：非基变量检验数 j= 0 w 2.
13、3.3退化解的情形：有两个以上 值相等 OR144 2.3.4单纯形法的计算机求解 w 程序说明 w 应用举例 例题1 例题2 OR145 2.5LP应用举例之一 w 例13合理下料问题 料长7.4米，截成2.9、2.1、1.5米各200根。 如何截取余料最少？关键：设变量。 方案 料型 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合计 残料 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4 OR146 应用
14、举例之二 w 例14混合配方问题 A、B、C、D四种原料配制三种产品，三类 约束：技术要求、原料限量、市场容量。 已知产品价格和原料价格，求利润最大的 配方。关键：设变量。 OR147 应用举例之三 w 例15.滚动投资问题 兹有100万元闲钱，投资方向有四： 第四年第一年第二年第三年 A项目110% B项目135% C项目125% D项目104% 第五年 各年投资什么项目，使第五年末资本总额为最大 ？ OR148 应用举例之四 w 例16动态生产计划问题 工厂做n个月的生产计划，第j月需求量dj、 正常生产能力aj、加班生产能力bj、正常生产成 本cj、加班生产成本ej、库存能力为I、库存费用 hj，设期初、期末库存为零。求费用最小的生产 计划。 设第月正常生产xj件，加班生产件yj，存储zj 件。则： 本期生产+上期
