工程数学教材.pdf
《工程数学教材.pdf》由会员分享,可在线阅读,更多相关《工程数学教材.pdf(102页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、(注意:本文件的显示、打印需要公式编辑器的支持。)工 程 数 学山东大学软件学院2012年01月、乙 X 刖 S先修课程要求:高等数学、离散数学、数据结构课程内容与学时分配:1.运筹学共1 4学时线性规划6学时整数规划2学时动态规划4学时网络分析2学时2.组合数学共1 2学时排列组合2学时鸽巢原理及应用 2学时容 斥 原 理 及 其 应 用2学时母函数方法 2学时递推关系 2学时P o l y a计数定理 2学时参考文献:1 .刁在筠等,运筹学,高等教育出版社,2 0 0 12 .叶 惠 民,工程数学,东南大学出版社,2 0 0 33 .邹述超,概率论与数理统计,高等教育出版社,2 0 0 3
2、4 .R i ch ar d A.B r u al di,I n t r o du ct o r y Co m bi n at o r i cs,P r i n t i ceH al l,I n c.,1 9995 .卢开澄,组合数学,清华大学出版社,1 9996 .曹汝成,组合数学,华南理工大学出版社,2 0 0 07 .朱大铭,算法设计与分析,高教出版社。目 录第一篇 运筹学.1第一章 线性规划.1 1 线性规划问题及数学模型.12 图解法.7 3 单纯形法解L P问题.9 4 对偶线性规划.14第二章 整数规划.18 1 整数线性规划问题.18 2 整数线性规划问题解法.20第三章 动态
3、规划.221 最优化原理.22 2 用最优化原理解非线性规划问题.23 3 动态规划算法设计.26第四章 网络分析.331 图及网络.332 网络上的优化问题.34第二 篇 组 合 数 学.46第五章 排列组合.46 1 和、积的原则.46 2 排列.473 重复排列.49 4 组合.54 5 组合等式及意义.57 6 排列与组合的生成.57第六章 容斥原理与鸽巢原理.601 容斥原理.60 2 鸽巢原理.65 3 有重复元素的圆排列问题.70第七章 母函数与递推关系.75 1 用母函数解递推关系.75 2 用母函数解整数拆分问题.80 3 用指数型母函数解错排问题.83第八章 Polya计数
4、定理.861 Burnside 弓|理.862 Polya 定理.93V .刖 s本文只是部分运筹学与组合数学的摘要汇编,在缺少讲解的情况下,可能需要读者查阅其他教材或文献以了解详细内容。第一篇运筹学第一章线性规划 1 线性规划问题及数学模型生产及生活中有一大批问题的数学模型可以用相对简单的线性方程组表示出来。由下面的两个例子,理解这类问题的相似结构,进而总结线性规划问题的一般模型,给出常用解法。例 1设要从甲地调出物资2000吨,从乙地调出物资1100吨,分别供给A 地 1700吨、B 地供0 0 吨、C 地 200吨、D 地 100吨。已知不同地点间每吨运费如下表所示,运费与运量成正比,求
5、解运费最省的供给方案。运销产ABCD甲2125715乙51513715解:设甲、乙运往A、B、C、D 的物资量分别为孙,的2,砧,为4,必,X 22,尤23,尤24吨,则由题意,我们需要去求211+25尤1 2+7X13+15X4+51%21+5 1尤22+37123+15124的最小值。显然X|,XX13,X14,X21,X22,X23,X24不能任意取值,我们还有“甲地调出物资2000吨”、“供给A 地 1700吨”等条件限制。总结需求及条件限制,得到下面的完整数学模型:min/=21xn+25x12+7xl3+15x14+51X21+5 lx22+37X23+15X24S.t.+X2+苞
6、3 +X4=2000,x2l+x22+x23+x24=1 100,0,/=l,2J=l,2,3,4该模型的现实含意为:在X|+X|2+X|3+X|4=2000等条件下,求/=21X11+25X|2+7X13+15X14+51X21+51X22+37123+15X24的最小值。(这里先做出数学模型,以后再考虑求襁方法)例 2某工厂用3 种原料PI,P2,P3生产3 种产品Qi,Q2,Q30已知单位产品需要的原料数、单位产品的利润、原料总量等条件如下表所示,制定出总利润最大的生产计划。单 位 产 品 产料 kgA?i原 米QiQ2Q3原料可用量(kg/日)Pi2301500P2024800P332
7、52000单位产品利润(千元)354解:设三种产品的生产量分别为用,切,1 3时可以得到最大利润3闪+5检+4工3,则由题意,我们可以得到完整的模型为max z=3+5x2+4x3s.t.2 x+3X2 1500,2X2+4X3 800,3须 +2X2+5X3 0,7=1,2,3总结这两个例子,可以看到其共同点:都是在对未知量做出线性约束的前提下,求未知量线性组合的最值。我们将最大、最小值统一为最小值,假设线性约束有等式、有不等式,未知量有些必须非负、有些不受限制,可以得到下面的一般线性规划模型:线 性 规 划(LP)问题的一般形式min z-qX+c2x2 H-F cnxns.t.+ai2x
8、2+ainxn=b,i=I,-,p/+aj2x2 H-F ainxn 2如 i=p +匕任意,/=4 +1,-,、J(等式不都在前面怎么办?非负变量不都在前面怎么办?调一调。)L P模型中的术语:目标函数(指标函数、指标):z=C1X+。2+q,x”价值系数:eg,价值向量:c =q,C 2,cj决策变量:xi,x2,-,xn,决策向量:x xx,x2,-,xn上述记法可以使指标写成:z=J x+ai 2x2+ai nxn=耳,i =1,,p约束:a,1%,+ai 2x2+ai nxn bt,i=p +1,XjX j 任意,/=4 +l,约束矩阵:a a2 an4/x a2 a22 a2nA
9、=(4.)*=::Jm 0 m2 _ jnxn右端向量:b=bi,b2,-,bm 非负约束:Xj 0,j =1,2,(?自由变量:Xj,j q +.,n可行解、可行点:即满足约束的点,也就是满足约束的一组未知量的取值,该组值不一定能使得指标达到最小值。可行域D:可行解集合最优解:使得指标最小的可行解(不一定唯一,甚至不一定存在)。利用上面的一些记法,在某些条件下,可以得到LP模型的特殊形式,至少在形式上显得简炼一些,实际上今后的许多分析是基于这些简炼形式的。LP问题的规范形式,般形式中p=0,时,称为规范形式。m i n cTxs.t.A x hx 0一般形式与规范形式的转化将 ai Xxx+
10、aj2x2+ai nxn=b.化为a.xx a.2x ai nxnb.-ai xi-ai 2x2-ai nxn -b.令X j=总xj,x j 0 xj 0,j =(7 +1,.例:将下面的线性规划转化为规范形式m a x z=-X j +x2-2x3W.2 玉-x2=-2xl-2X2 0.自由解:m i ns.t.Z =-工2+2%32X 1 Xj+0 43 N 2-2xt+x2-0 x3 2-X 1 +2A 2 N-3,x2 0人自由m i nz =x 1 -x2 4-2x4-2X52XJ 工2+0 1 4-0氏5 N 一2-2xl+x2-0 x4+0 x5 2-X +2X2+0 x4-0
11、 x5 -3Xpx2,x4,x5 0c=1,-1,2,-27,x =X j,x2,x4,x57,2-100A=-2 1 0 0,b=-2,2,-37-1 2 0 0LP问题的标准形式一般形式中/?=m,q=时,称为标准形式。min cTx0一般形式与标准形式的转化对即+bt即 再 +ai2x2 +4力 相 一 x:=,x 0,i=p+L,根.令 /=x;-xj,4;之 0 x;2 0,/=q+1,.这里的其称为剩余变量。例:将下面的线性规划转化为标准形式max z=-x,+x2-2x3s1 2玉-x2=-2 再-2X2 0刍自由解:m i n z =X -9+2x32工 x9+2-%)+2x0
12、 2-3xpx2 0X 3自由m i ns.t.z=xi-x2+2X4-2X52XJ 4 +0工4+。二5 二 2-%+2X2+0 x4+O x5 -3m i n z=xi-x2+2x4-2xs+0 x6s.t.2x,-x2+0 x4+0 x5+0 x6=-2 X +2x,+0 x4+0%5 入6=-32-1000-12 0 0 -1-12-20 2图解法例1用图解法解线性规划m a x z=一 为 +x2s j-2xl-x2-2x-2X2 2xl+x2 0z在(1,4)点达到最大值3。例 2用图解法解线性规划min z=x-5x2 +2X2 4例3用图解法解线性规划min z-2x+x2W.
13、x,+x2 1%1 3%2 3%1,x2 0无最优解关于可行域。与最优解的讨论:0=0,无解、不可行;。工0,无界;Dr 0,有最优解。3 单纯形法解LP问题1.单纯形方法考虑标准形式的L P问题(Tmin z=c x0设A的前机列为线性无关。(注意各向量、矩阵的维数)将A分为左右两块,左边?列为可逆方阵B,右边记为N。(左面加列是不是一定可逆?)对应将价值向量C和决策向量x的前m行与后n-m行分开,A=B,N,c=,/二解,可,SN./v 丁T Tx=,x =xB,x,v_XN _ XR1,Ax=bB,N=b=BXB+NXN=b_*N _xB=B-b-B-NxNZ=CTx=crB,cTN X
14、R=CTBXB+CTNXN.XN _cB-b-B-N xN)+cxN9=以3 -0,0,0,c;3-W-4 4_XN _令r=0,0,0,c-W-或,则2=或8-八,且=一 斤方或犷卬-或,或o=cj6T 8,N-,c jB-A-c7原 LP问题变形为min z=cB b-x0若取乐=0,则4 =8-8 得一个满足等式约束的解_ B-bX=,0 _其对应的指标值为 2=crx=cBB-b oB 称为基,B 的列称为基向量,天=B 1 称为基本解,0R-1卜x=2 0 时称为基本可行解,此时B 称为可行基0B”0 时称x 为非退化的基本可行解。下面假设我们要讨论的LP问题对所有的可行基6,都有B
15、-b 0。定 理 若 标 准LP问题有可行解,则必有基本可行解;若有最优解,则一定存在一个基本可行解是最优解。(证明略)定 理 若0WO,则亍是最优解。证 V x 0,0,rx cB7B-h 0定理 若二的第左个分量媒 0,且&=夕儿 o,(下面说明止匕X是可行解,且其指标值要多小有多小。)A c)=A j+A ek=B,N+4 =。A x=A(x +08)=Ax +0A 8=A x=bx 0,z =4 5 _ C=C gB b-4T(X+68=c1sB-%-骋5=crBB-b-Ok0,且4=少儿中存在正分量,则武2 0,使得4攵=6且c,攵 0 但不能任意取。)1)可以适当取6 0 使得 为
16、可行解:由A 8=A-4o+A e*=B,N一夕40+Ak=0知道4 =4 叵+防)=4 亍+。4 6 =4 亍=匕;要使得 2 0,即B b0+6(+e*)2 0 ,只需B-b0+0一 4 0,B-b-0B AkO设田与=瓦由乐NO等知道取6 =1 1 1 皿|生|纵 0,,=1,2 -,加 即可。4 2)z=4B%_qT玄=c11tB-%/短+%=以8-纥茯=43-/尹,4 板=clB-b-0k bii=p+wi 0i=p+1,,加%0j=1,2,qA:w%j=1,2,(7与自由j=q+,-,nAw=Cjj=q+l,-,n可是约束矩阵A 的第i 行,为是约束矩阵A 的第,歹 U。min c
17、Txmax bTw规范形式,s/.Ar 2 b 的对偶问题为,s/.Arw0w 0min cTxmax bTw标准形式,sf.Ax=6 的对偶问题为.W.AT w 0w 自由2.对偶理论定 理 如果一个L P问题有最优解,则它的对偶问题也有最优解,且它们的最优解值相等。定理 对偶的对偶为原始的LP问题。3.对 偶LP的来历将一般形式min cTxsL a;x=bi bi%0.自由i=l,,Pi=+j=q+l,,几 八 不m in c x化为标准形式 0wTAcT,即:卬3,展开为夕c=q,r c .N g N q+l,%+l,c“,一c,0,o ,日X1,.,,X g,K+l,K+l,,X/,
18、Xj,x吁 p,A =4,,4 4+|,-4+-一 1-m P Jxg+2(-g)+Lpa11an aq i.,+l f+i -ain 0 0 aplaP2%ap.q+-/M+l ap.q+ap.n ap+1.1品+1.2 .Qp+l.qap+,q+l-ap+l.q+l aP+i,q+-ap+t,n T .am la,n2 a,nqam.q+t-am.q+am,q+l-am.n 0-1人 人 TqBA-CT 0,令wT=c J B-,则 J,M O改写为Awc4卬4%4+产 W c*-4+产 A:卬-Anw0,i=p+第二章整数规划 1 整数线性规划问题要求变量值取整数值的线性规划问题称为整数
19、线性规划,其中变量只取0 或 1 的线性规划称为0-1规划。投资决策问题 总金额B万元,个项目,第J项目所需资金的 利润c r应该选哪些项目使总利润最大。maxj=iJ 1s.t.bFj W Bj=i房产投资 地产面积3000 M2,甲类房产每幢250M2,可收利润10万元,可建设不超过8 幢,乙类房产每幢400M2,可收利润 20万元,可建设不超过4 幢,应该建设甲乙各几幢使得利润最大?max z=10 x+20ys.t.250 x+400y3000 x8y4x,y&N货朗问题从心出发,恰好经过力,也,V各一次回到V 0,从均到V/路程为四,(公 充 分 大),怎么走最近?min z=Z d
20、uxui.j=Os.t.超=1,i=0Z%,尸。ui-j+nXq n l,Xu=0?r 1,%为实数,j=0,i=0,,及1 zj ni,j=0,i=1,,背包问题个物品,体积分别为中,也,为,价值分别为 P1,2,P”,一个容积为V 的包,取哪些物品放入包内,使包内物品总价值最高。例:1)V=100,vl=pl=49,v2=p2=51,v3=p3=522)V=100,vl=pl=49,v2np2=51,v3=52,p3=52.1算法:穷举,共 2 种物品的组合。max z=Z PRi=l_ S.t.Z匕 外4Vi=l=0,1 2 整数线性规划问题解法1.图解法图解法求解下面的I L P问题m
21、 i n z =-5x2s.t,X +2X2 4420且为整数2.分枝定界法m i n z=-xx-x2s.t,4%1 +2%1 4%j +2X9 1 1_ 2x?-12。且为整数m i n z =-%)-x2s,t,-4%1 +2 x2 4 -14%j +2尤2 1 1一 2 X2 Xj 1斗2 2 0且为整数m i n z=-x-x2s/.4 玉 +2 x2 14$+2X2 2X1,%N O且为整数第三章动态规划动态规划是多阶段决策问题,相对地,线性规划、非线性规划问题称为静态规划问题。1 最优化原理全局最优,则局部最优。(如何理解)最短路问题g6货郎问题设/(匕 W)表示从火出发,经 过
22、 V中的所有点恰一次后回到丫 0 的最佳路线总长度,则所求的就是/(%,匕,为,,匕)4+(%,眩,3-,匕,),/(%,匕,岭,匕 J)=m i n 少2 +/(彩,匕,匕,匕 ),4.+/(匕,2 2,,*)./(匕,匕,匕,,匕)=m i n d2+f(v2,v3,v4,-,vn),九+八匕乂彩,!,,匕 J),*94“+/(乙,鱼,匕,3 )./(v,.,V)=m i n +/(vy,V -vy)例:%+/(4,%,%),/(v0,v,v2,v3)=m i n 0+/(匕,%,%),.九+八匕,匕,修),九+/(%,%),/(v1,v2,v3)=m i n ,dl3+f(v3,v2)2
23、 用最优化原理解非线性规划问题就下面的非线性规划问题,讨论最优化原理解题思想,并具体求解该题m ax F=4%j2-x;+2xj+1 2 s.t.3西 +2X2+x3 0/3(9)=m ax 2 x32+1 2 +/2(9-x3)f2(y)=m ax -力+工(,一2%)0 2x2 y/1(Z)=m ax 4 x 12解得:(2)=4 ,故9,、(2 4 (y-2 x,)2.)=黑 黑 一+4-J 2 16 4 2 1m ax -yx7+y o p 2 0 9 9 2 9fm ax 一7(z x8 丁 4 2 17 y)一H y 0 2 x20/,/)=0,i 0,j=0012 j0/1111
24、01/23/4201/41/2i02.划分问题用动态规划思想,设计填表法,求解下面的划分问题在集合A=ai,做,an)上定义正整数函数s,令8 =25(),问是否存在4 1,/(/-1,J-5(,)=TF,o th e r s3.背包问题背 包 问 题“个物品,体积分别为力,V 2,,为,价值分别为Pl,P 2,Pn,一个容积为V的包,取哪些物品放入包内,使包内物品总价值最高。m ax z=Z Pixi/=iJ s.t.Z v,xf V=ix,=O,l设 P i 9 H 9,对i位数组(x g,厮),构造有序对,其中i j=ZP JZ,匕=目 J=I由于(XB%2,备)有2,种不同的取值,所以
25、对应有2 i个不同的有序对,将这些有序对组成集合不),但有两种情况对应的有序对不放入s(i):1)W V;2)两个有序对和,满足尸0/,Vi Vj,1.e 则不放入 S(i)o不)构造完成后,如下构造型+21)c S(i+1);2)I wS 且 Vi+vi+iV c 5(i+,)04.排工问题“个工件,每个工件都要按顺序经过A、B两个机床进行加工,工件i 在 A、B两个机床上加工时间分别为即bi,确定n个工件的加工顺序,使得总加工时间最短。例:N 1N 2A42B13先加工N 1,所需总时间为4+2+3=9,先加工N 2,所需总时间为2+4+1=7。定理 最优加工方案当工件在A、B机床上加工顺
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工程 数学 教材
限制150内