《OPERATIONSRESEARCH运筹学怎样把事情做到最好(1)精编版》由会员分享，可在线阅读，更多相关《OPERATIONSRESEARCH运筹学怎样把事情做到最好(1)精编版（71页珍藏版）》请在金锄头文库上搜索。
1、OPERATIONS RESEARCH 运筹学,怎样把事情做到最好,OR1,1,第一章 绪论,1.1题解 Operations 汉语翻译 工作、操作、行动、手术、运算 Operations Research 日本运用学 港台作业研究 中国大陆运筹学 Operational Research原来名称，意为军事行动研究历史渊源,OR1,2,绪论,1.2 运筹学的历史 早期运筹思想：田忌赛马 丁渭修宫 沈括运粮 Erlang 1917 排队论 Harris 1920 存储论 Levinson 1930 零售贸易 康脱洛维奇 1939 LP,OR1,3,绪论,1.2运筹学的历史 军事运筹学阶段 德军空
2、袭 防空系统 Blackett 运输船编队 空袭逃避 深水炸弹 轰炸机编队,OR1,4,绪论,1.2运筹学的历史 管理运筹学阶段 战后人员三分:军队、大学、企业 大学：课程、专业、硕士、博士 企业：美国钢铁联合公司 英国国家煤炭局 运筹学在中国：50年代中期引入 华罗庚推广 优选法、统筹法 中国邮递员问题、运输问题,OR1,5,1.3学科性质,应用学科 Morse饲料II x2kg;饲料III x3kg 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5 约束条件：3x2+2x2+x3+6x4+18x5 700 营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 30
3、 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,OR1,16,例题3：人员安排问题,医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：,OR1,17,例题3建模,目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 非负性约束：xj 0,j=1,2,6,OR1,18,归纳：线性规划的一般模式,目标函数：max(min)Z
4、=c1x1+c2x2+c3x3+cnxn 约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn 非负性约束：x1 0,x2 0,xn 0,OR1,19,2.1.2线性规划图解法,由中学知识可知：y=ax+b是一条直线，同理：Z=70 x1+120 x2x2=70/120 x1-Z/120也是一条直线，以Z为参数的一族等值线。 9x1+4x2 360 x1 360/9-4/9x2 是直线 x1=360/9-4/9x2 下方的半平面。所有半平面的交集称之为可
5、行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。,OR1,20,例1图示,.,90 80 60 40 20,0 20 40 60 80 100,x1,x2,9x1+4x2 360,4x1+5x2 200,3x1+10 x2 300,A,B,C,D,E,F,G,H,I,Z=70 x1+120 x2,OR1,21,概念,概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。 3、基解：约束条件的交点称为基解（直观） 4、基可行解：基解当中的可行解。 5、凸集：集合内任意两点的连
6、线上的点均属于这个集合。如：实心球、三角形,OR1,22,结论,可行域是个凸集 可行域有有限个顶点 最优值在可行域的顶点上达到 无穷多解的情形 无界解情形 无解情形,OR1,23,2.1.3线性规划的标准型,代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n,OR1,24,线性规划的标准型,和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n,j=1,n,n,j=1,OR1,25,线性规划的标准型,向量式：maxZ=C
7、X 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,OR1,26,线性规划的标准型,矩阵式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn,OR1,27,标准型的特征,目标函数极大化 约束条件为等式 决策变量非负,OR1,28,非标准型转化为标准型,目标函数极小化转为极大化： minZ=max(Z) ，一个数的极小化等价于其相反数的极大化。 不等式约束的转化： aijxjbi 加入松弛变量 aijxjb
8、i 减去剩余变量 非正变量：即xk 0 则令xk = xk 自由变量：即xk无约束，令xk= xkx”k,OR1,29,非标准型转化举例之一,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 =300 X10 X20 Xj0 j=1,2,5,OR1,30,非标准型转化举例之二,minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+
9、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,OR1,31,2.1.4基可行解,基的概念：如前所述LP标准型 和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A的秩为m，且mn。设A=B+N ，B是A中mm阶非奇异子矩阵，则称B是LP的一个基，即：B是A中m个线性无关向量组。,n,j=1,n,j=1,OR1,32,基解的概念,不失一般性,设B是A的前m列
10、,即B=(p1,p2,pm）,其相对应的变量XB=(x1,x2,xm)T,称为基变量；其余变量XN=(Xm+1,Xn)T称为非基变量。令所有非基变量等于零,则X=（x1,x2,xm,0,0)T称为基解 。,OR1,33,基可行解的概念,基可行解：基解可正可负，负则不可行（违背非负性约束条件），称满足所有约束条件的基解为基可行解。 退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。 基解的数目：最多Cmn=n!/m!(n-m)!,OR1,34,例题6 基可行解说明,maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+
11、5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj0 j=1,2,5 这里m=3,n=5。 Cmn=10,OR1,35,例题6 基可行解说明,基（p3,p4,p5） ，令非基变量x1,x2=0，则基变量x3=360, x4=200, x5=300, 可行解 基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=250,x5=600. 非可行解 基（ p2,p3,p4 ），令非基变量x1,x5=0，则基变量x2=30, x3=240, x4=50,可行解（P21图）,OR1,36,2.2单纯形法,2.2.1初始基可
12、行解的确定 从系数矩阵中找到一个可行基B，不妨设B由A的前m列组成，即B=(P1,P2,Pm)。进行等价变换约束方程两端分别左乘B1 得 X1+ +a1m+1xm+1+a1nxn=b1 x2+ +a2m+1xm+1+a2nxn=b2 . xm+amm+1xm+1+amnxn=bm 令非基变量为0，得基可行解 X(0)=(b1，b2，bm，0，0）T z0=cibi,OR1,37,2.2单纯形法,2.2.2最优性检验：LP经过若干步迭代，成为如下形式： X1+ +a1m+1xm+1+a1nxn=b1 x1=b1- a1jxj x2+ +a2m+1xm+1+a2nxn=b2 x2=b2- a2jx
13、j . . xm+amm+1xm+1+amnxn=bm xm=bm- amjxj,OR1,38,单纯形法,一般性表示：xi=bi- aijxj i=1,2,m 将xi代入目标函数得：Z= cjxj = cixi+ cjxj = ci（ bi- aijxj ） + cjxj = cibi+ (cj- ciaij)xj 令：j= cj- ciaij z0=cibi 则Z=z0+ j xj j判别准则 ： j 0 时,达到最优解,OR1,39,单纯形法,2.2.2基变换 若存在j 0，则取 maxj = K ，相应之非基变量XK若取非零，将使Z增加,故令XK 进基。令XK0 ，其余非基变量保持为零。
14、 XK 原是非基变量，取零值， 若 XK 0 将迫使某个原基变量为零，当XK取值超过任意bi / aik 时,将破坏非负性条件,于是令 = min bi / aik aik 0 =bL/ aLk 。 这时原基变量XL=0，由基变量变成非基变量， aLk处在变量转换的交叉点上，称之为枢轴元素,j 0,OR1,40,单纯形法解题举例,单纯形表的格式：,OR1,41,OR1,42,2.2.3单纯形法的计算步骤,找到初始可行基，建立单纯形表 计算检验数，若所有j 0 则得最优解，结束。否则转下步 若某K 0而PK 0 ，则最优解无界，结束。否则转下步 根据max j = K 原则确定XK 进基变量；根据规则 ： = min bi / aik aik 0 = bL/ aLk 确定XL为出基变量 以aLk 为枢轴元素进行迭代，回到第二步,OR1,43,2.3单纯形法的进一步探讨,2.3.1极小化问题直接求解：检验数的判别由所有j 0 即为最优，变为所有j 0则为最优。 人工变量法之一：大M法 人工变量价值系数M例 人工变量法之二：构造目标函数，分阶段求解例 2.3.2无穷多最优解情形：非基变量检验数 j= 0 2.3.3退化解的情形：有两个以上 值相等,OR1,44,2.3.4单纯形法的计算机求解,程序说明 应用举例 例题1 例题2,OR1,4
