《运筹学》总结复习计划参考材料知识点总结及试题

精选文档第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠见解准备：定义：知足所有拘束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。㈡图解法：图解法采纳直角坐标求解：x1——横轴；x2——竖轴。1、将拘束条件（取等号）用直线绘出；2、确立可行解域；3、绘出目标函数的图形（等值线），确立它向最优解的搬动方向；注：求极大值沿价值系数向量的正向搬动；求极小值沿价值系数向量的反向搬动。4、确立最优解及目标函数值。㈢参照例题：（只需求下边这些有唯一最优解的种类）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同样的设施上加工，每种产品在不同样设施上加工所需的工时不同样，这些产品销售后所能获取收益以及这三种加工设备因各样条件限制所能使用的有效加工总时数以下表所示：消设备收益ABC（万元）耗产品甲35970乙95330有效总工时540450720——问：该厂应怎样组织生产，即生产多少甲、乙产品使得该厂的总收益为最大？（本题也可用“纯真形法”或化“对偶问题”用大M法求解）.精选文档解：设x1、x2为生产甲、乙产品的数目。maxz=70x1+30x2⑴s.t.3x19x2540⑵5x15x2450⑶9x13x2720⑷x1，x20⑸、⑹可行解域为oabcd0，最优解为b点。由方程组5x15x2450解出x1=75，x2=159x13x2720x1∴X*=x2=（75，15）T∴maxz=Z*=70×75+30×15=5700.精选文档例2：用图解法求解maxz=6x1+4x2⑴s.t.2x1x210⑵x1x28⑶x27⑷x1，x20⑸、⑹解：可行解域为oabcd0，最优解为b点。由方程组2x1x210解出x1=2，x2=6x1x28x1∴X*=x2=（2，6）T∴maxz=6×2+4×6=36.精选文档例3：用图解法求解minz=－3x1+x2⑴s.t.x14⑵x23⑶2x15x212⑷x12x28⑸x1，x20⑹、⑺解：可行解域为bcdefb，最优解为b点。由方程组x1442x15x212解出x1=4，x2=5∴X*x1（，4=x2=）T4541minz=－3×4+5=－115.精选文档二、 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型线性规划问题的纯真形解法：㈠一般思路：1、用简单易行的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 获取初始基本可行解；2、对上述解进行查验，查验其可否为最优解，若是，停止迭代，不然转入3；3、依据θL规则确立改良解的方向；4、依据可能改良的方向进行迭代获取新的解；5、依据查验规则对新解进行查验，若是最优解，则停止迭代，不然转入3，直至最优解。㈡详细做法（可化归标准型的状况）：设已知maxz=c1x1+c2x2++cnxns.t.a11x1a12x2...a1nxnb1a21x1a22x2...a2nxnb2............am1x1am2x2...amnxnbmxj0，j1，2，...，n对第i个方程加入废弛变量xn+i，i=1，2，，m，获取a11x1a12x2...a1nxnxn1b1a21x1a22x2...a2nxnxn2b2............am1x1am2x2...amnxnxnmbmxj0，j1，2，...，n列表计算，格式、算法以下：.精选文档CBXBbc1c2cn+mθLx1x2xn+mcn+1xn+1baaa111121n+mcn+2xn+2baaa221222n+m......⋯⋯⋯⋯...cn+mxn+mbaaanm1m2mn+mzz2zn+m1σ1σ2σn+mm注①：zj=cn+11j+cn+22jn+mmjcniaij，（j=1，2，，n+m）aa++ca=i1j=cj－zj,当σj≤0时，目前解最优。注②：由max{σj}确立所对应的行的变量为“入基变量”；由θL=minbiaik0确立所对应的行的变量为“出基变量”，行、列交iaik叉处为主元素，迭代时要求将主元素变为1，此列其他元素变为0。例1：用纯真形法求解（本题即是本资料P2“图解法”例1的纯真形解法；也可化“对偶问题”求解）maxz=70x1+30x2s.t.3x19x25405x15x24509x13x2720x1，x20解：加入废弛变量x3，x4，x5，获取等效的标准模型：maxz=70x1+30x2+0x3+0x4+0x5.精选文档s.t.3x19x2x35405x15x2x44509x13x2x5720xj0,j1,2,...,5列表计算以下：CBXB7030000bx1x2x3x4x5θL0x354039100540/3=1800x445055010450/5=900x5720（9）3001720/9=800000070↑300000x33000810-1/3300/8=37.50x4500（10/3）01-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3↑00－70/90x3180001－12/5130x2150103/10-1/670x175100-1/101/670300220/3570000-2－20/30X*=（75，15，180，0，0）Tmaxz=70×75+30×15=5700.精选文档例2：用纯真形法求解maxz=7x1+12x2s.t.9x14x23604x15x22003x110x2300x1，x20解：加入废弛变量x3，x4，x5，获取等效的标准模型：maxz=7x1+12x2+0x3+0x4+0x5s.t.9x14x2x33604x15x2x42003x110x2x5300xj0,j1,2,...,5列表计算以下：.精选文档712000CBXBbx1x2x3x4x5θL0x336094100360/4=900x420045010200/5=400x53003（10）001300/10=3000000712↑0000x324078/10010-2/5240/78/10=2400/780x450（5/2）001-1/250/5/2=2012x2303/101001/1030/3/10=10018/512006/517/5↑000－6/50x384001－78/2529/257x1201002/5-1/512x224010－3/254/28428712034/2511/35000－34/25－11/35X*=（20，24，84，0，0）Tmaxz=7×20+12×24=428三、非标准型线性规划问题的解法：1、一般地，对于拘束条件组：若为“≤”，则加废弛变量，使方程成为“＝”；若为“≥”，则减废弛变量，使方程成为“＝”。我们在前面标准型中是规定目标函数求极大值。若是在实责问题中碰到的是求极小值，则为非标准型。可作以下办理：.精选文档nn由目标函数minz=cjxj变为等价的目标函数max（－z）=(cjxj)j1j1令－z=z/，∴minz=－maxz/2、等式拘束——大M法：经过加人工变量的方法，结构人造基，进而产生初始可行基。人工变量的价值系数为－M，M是很大的正数，从原理上理解又称为“处分系数”。（课本P29）种类一：目标函数仍为maxz，拘束条件组≤与＝。例1：maxz=3x1+5x2s.t.x142x2123x12x218x，x201解：加入废弛变量x3，x4，获取等效的标准模型：maxz=3x1+5x2s.t.x1x342x2x4123x12x218xj0,j1,2,3,4此中第三个拘束条件固然是等式，但因无初始解，因此增添一个人工变量x5，获取：maxz=3x12－Mx5+5xx1x342x2x412s.t.3x12x2x518xj0,j1,2,...,5.精选文档纯真形表求解过程以下：3500－MCBXBx3x4－Mx5x1x4－Mx5x1x4x2x1x3x2bx1x2x3x4x5θL4（1）01004/1=41202010——183200118/3=6－3M－2M00－M3M＋↑5＋2M0003410100——120201012/2=660（2）－3016/2=33MM0－M－23＋305↑33M00－－4101004/1=4600（3）1－16/3=2301－3/201/23/(－2/3)=－9/235－9/205/2009/2↑0－M－5/22100－1/31/320011/3－1/360101/203503/2136000－3/2－M－1.精选文档X*=（2，6，2，0）Tmaxz=3×2+5×6=36种类二：目标函数minz，拘束条件组≥与＝。例2：用纯真形法求解minz=4x1+3x2s.t.2x14x2163x12x212x1，x20解：减去废弛变量x3，x4，并化为等效的标准模型：maxz/=－4x1－3x2s.t.2x14x2x3163x12x2x412xj0,j1,2,3,4增添人工变量x5、x6，获取：maxz/=－4x1－3x2－Mx5－Mx6s.t2x14x2x3x5163x12x2x4x612xj0,j1,2,...,6纯真形表求解过程以下：.精选文档CBXB－Mx5－Mx63x2－Mx63x24x1b－400－M－MθLx1x2x3x4x5x6162（4）－101016/4=412320－10112/2=6－5M－6MMM－M－M5M－46M－3↑－M－M0041/21－1/401/404/1/2=84（2）01/2－1－1/214/2=2－2M－3/2－33/4－M/2MM/2－3/4－M2M－5/2↑0M/2－3/4－M3/4－3M/20301－3/81/43/8－1/42101/4－1/2－1/41/2－17－4－31/85/4－1/8－5/400－1/8－5/4－M＋1/8－M＋5/4∴X*=（2，3，0，0）T∴minz=－maxz/=－（－17）=17.精选文档四、对偶问题的解法：什么是对偶问题？1、在资源必然的条件下，作出最大的贡献；2、达成给定的工作，所耗资的资源最少。引例（与本资料P2例1“图解法”、P7例1“纯真形法”同）：某工厂生产甲、乙两种产品，这些产品均需在A、B、C三种不同样的设施上加工，每种产品在不同样设施上加工时需要不同样的工时，这些产品售后所能获取的收益值以及这三种加工设备因各样条件下所能使用的有效总工时数以下表：消设备收益ABC（万元）耗产品甲35970乙95330有效总工时540450720——问：该厂应怎样组织生产，即生产多少甲、乙产品使得该厂的总收益为最大？解：原问题——设x1、x2为生产甲、乙产品的数目。maxz=70x1+30x2s.t.3x19x25405x15x24509x13x2720x，x201将这个原问题化为它的对偶问题——.精选文档设y1、y2、y2分别为设施A、B、C单位工时数的加工费。minw=540y1+450y2+720y3s.t.3y15y29y3709y15y23y330yi，i，，0123用大M法，先化为等效的标准模型：maxw/=－540y1－450y2－720y3s.t.3y15y29y3y4709y15y23y3y530yj0,j1,2,...,5增添人工变量y6、y7，获取：maxz/=－540y1－450y2－720y3－My6－My7s.t3y15y29y3y4y6709y15y23y3y5y730yj0,j1,2,...,5大M法纯真形表求解过程以下：.精选文档CBXBb－540－450－72000－M－MθLy1y2y3y4y5y6y7－My670359－101070/3－My730（9）530－10130/9=10/3－12M－10M－12MMM－M－M12M－540↑10M－45012M－720－M－M00－My660010/3（8）－11/31－1/360/8=2.5－540y110/315/91/30－1/901/910/3/1/3=10-300+10/3M-8M－180－M－M/3+60－MM/3－600-150+10/3M8M-540↑MM/3－600－M/3+60－720y315/205/121－1/81/241/8－1/2415/2/5/12=18－540y15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720y320/3－1011/61/61/6－1/6－450y2212/5101/10－3/10－1/103/10－360－450－7207515－75－155700－18000－75－1575－M15－M20∴该对偶问题的最优解是y*=（0，2，3，0，0）T最优目标函数值minw=－（－5700）=5700.精选文档五、运输规划问题：运输规划问题的特别解法——“表上作业法”解题步骤：1、找出初始调运方案。即在(m×n)产销平衡表上给出m+n-1个数字格。（最小元素法）2、（对空格）求查验数。鉴别可否达到最优解。如已经是最优解，则停止计算，不然转到下一步。（闭回路法）3、对方案进行改良，找出新的调运方案。（依据查验结果选择入基变量，用表上闭回路法调整——即迭代计算，得新的基本可行解）4、重复2、3，再查验、再迭代，直到求得最优调运方案。种类一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例：某钢铁企业有三个铁矿和四个炼铁厂，铁矿的年产矿石量分别为100万吨、80万吨和50万吨，炼铁厂年需矿石量分别为50万吨、70万吨、80万吨和30万吨，这三个铁矿与四个炼铁厂的距离以下：炼距铁厂B1B2B3B4离铁矿A11520330A27081420A31232015问：该企业应怎样组织运输，既知足各炼铁厂需要，又使总的运输花费为最小（按吨.公里计）？解：用“表上作业法”求解。⑴先用最低花费法（最小元素法）求此问题的初始基础可行解：.精选文档费销用地B1B2B3B4产地A11520－67330－6520×80×A27081444203020×30A312533203325－10×50××销量dj50708030∴初始方案：20B130B1A120B2A350A2B280B330B3Z=15×20+3×80+70×30+8×20+20×30+3×50=3550（吨.公里）⑵对⑴的初始可行解进行迭代（表上闭回路法），求最优解：产量Si1008050230230.精选文档费销产量用地B1B2B3B4S产地iA11520－14330－122080100××A270－53814－92080×50×30A312320－2025－10302050××销量230dj50708030230用表上闭回路法调整后，从上表可看出，所有查验数σ＜0，已得最优解。∴最优方案：20B150B230B1A1A2A380B330B420B2Z=15×20+3×80+8×50+20×30+12×30+3×20=1960（吨.公里）解法解析：①怎样求查验数并由此确立入基变量？有数字的空格称为“基格”、打×的空格称为“空格”，标号为偶数的极点称为偶点、标号为奇数的极点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的查验数ijcijcij，一定ij≤0，才获取最优奇点偶点解。不然，应选所有中正的最大者对应的变量xj为入基变量进行迭代（调整）。②查验后调整运输方案的方法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。③重复以上两步，再查验、再调整，直到求得最优运输方案。种类二：供求不平衡的运输规划问题.精选文档mnBn+1，令若sidj，则是供大于求（供过于求）问题，可设一虚销地i1j1mnmnci,n+1=0，dn+1=sidj，转变为产销平衡问题。若sidj，则是供小i1j1i1j1nm于求（求过于供）问题，可设一虚产地转变为产销平衡问题。（，2，，m；，2，，n）六、工作指派问题：Am+1，令cm+1,j=0，sm+1=djsi，j1i1工作指派问题的数学模型——假设有n项工作需要达成，恰巧有n个人每人可去达成此中一项工作，收效要好。工作指派问题的特别解法——“匈牙利法”（考！！）解题步骤：1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法：①行约简—系数矩阵各行元素减去所内行的最小元素，②列约简—再从所得矩阵的各列减去所在列最小元素。2、试求最优解。如能找出n个位于不同样行不同样列的零元素，令对应的xij=1，其他xij=0，得最优解，结束；不然下一步。作法：由独立0元素的行（列）开始，独立0元素处画（）标志，在有（）的队列中划去（也可打*）其他0元素；再在节余的0元素中重复此做法，直至不能够标志（）为止。3、作能覆盖所有0元素的最少量直线会合。作法：①对没有（）的行打√号；②对已打√号的行中所有0元素的所在列打√号；③再对打有√号的列中0元素的所内行打√号；④重复②、③直到得不出新的打√号的行(列)为止；⑤对没有打√号的行画一横线，对打√号的列画一纵线，这就获取覆盖所有0元素的最少直线数。⑥未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij。4、重复2、3，直到求得最优解。种类一：求极小值的匈牙利法：（要点掌握这类基本问题）.精选文档例1：有甲、乙、丙、丁四个人，要派去达成A、B、C、D四项工作，他们达成的工时以下表：任工务时人ABCD甲612134乙1031214丙7141316丁881210试问：应怎样分派任务可使总工时为最少？解：用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为：612134289010312行约简709列约简1411（cij）=141316076978812100042ABCD甲285(0)28507(0)511705标号乙11(0)7290729丙0002丁0*0*(0)2∴使总工时为最少的分派任务方案为：甲→D，乙→B，丙→A，丁→C此时总工时数W=4+3+7+12=26例2：求效率矩阵.精选文档109785877的最优解。5465234510978行约简3201列约简解：587703225465102123450123320032(0)0*(0)321032标号11(0)20*所画（）0元素少于n，未102001220*122获取最优解，需要连续变换矩阵（求能覆盖所有0元素的最少量直线会合）：√32(0)0*(0)321√1(0)20*0*122√未被直线覆盖的最小元素为cij=1,在未被直线覆盖处减去1,在直线交叉处加上1。标号2(0)0*42004(0)210*021020*2（0）202000110*（0）110010∴得最优解：100000010100种类二：求极大值的匈牙利法：minz=－max（－z）.精选文档（cij）→（M－cij）=（bij），（cij）中最大的元素为Mmaxz=cijxij=(Mcij)xijijij=(Mcij)xij－cijxijijij第一部分到此结束.精选文档第二部分动向规划只需求掌握动向规划的最短路问题——用“图上标号法”解决：详细解题步骤请参看教材P103（这是本套资料少见的与教材完整同样的算法种类之一，务必看书掌握）学员们只有完整理解了这类作法（思路：逆向追踪）才有可能做题，考试时数字不论如何变化都能作出正确求解！第二部分到此结束.精选文档第三部分网络解析一、求最小生成树（最小支撑树、最小树）问题：破圈法——任取一个圈，从圈中去掉一条权最大的边（若是有两条或两条以上的边都是权最大的边，则随意去掉此中一条）。在余下的图中，重复这个步骤，直到获取一个不含圈的图为止，这时的图即是最小树。参照例题：例：求以下列图的最小生成树：v24v41510387v6v129v36v5.精选文档解：用“破圈法”求得最小生成树为：v24v415v6v129v3v5已得最小树，此时权w=1+2+4+5+9=21为最小。二、最短路问题：（有向图）TP标号法（狄克斯托算法）——详细解题步骤请参看教材P125（这是本套资料少见的与教材完整同样的算法种类之一，务必看书掌握）学员们只有完整理解了这类作法（思路：顺向追踪）才有可能做题，考试时数字不论如何变化都能作出正确求解！参照例题：例：教材P124图4—8的例子（略）三、网络最大流问题：追求网络最大流的标号法（福特—富克尔逊算法）——详细解题步骤请参看教材P130。（教材用有序数对（fij，cij）表示（流量，容量），但我们解题算法格式按南邮要求，用大部分《运筹学》书本中的标准格式，即用有序数对（cij，fij）表示（容量，流量）。解法实质是同样的。）学员们只有完整理解了这类作法（思路：标号检查、迭代调整）才有可能做题，考试时数字不论怎样变化都能作出正确求解！参照例题：《运筹学参照综合习题》（我站采集信息自编，非南邮综合练习题，仅供参照。另挂于网上）第三部分到此结束.精选文档第四部分储藏论（简介）随机储藏模型参照例题：例：一食品店要决定每日牛奶的进货量，该店依据过去的销售经验，知道需求量的概率散布以下：需求x（箱）25262728p（x）0.10.30.50.1若进货每箱80元，售价100元，又若当日不能够售出因牛奶变质而所有损失，试确立每日进货量。解法一：已知C=80，p=100，g=0，需求x（箱）25262728概率p（x）0.10.30.50.1累计概率0.10.40.91依据单周期随机型储藏模型（“报童模型”）之失散型随机储藏模型公式，可得p(xQ*)pCs1008000.2pgs10000即能够确立进货26箱，赢利的希望值最大。解法二：k=100－80=20，h=80.k20k=100=0.2P{x=25}=0.1＜0.2≤P{x=25}+P{x=26}=0.4∴能够确立进货26箱，赢利的希望值最大。。注：该问题即“报童问题”（对于报童进报纸问题的数学模型），即是相当于将上题的进“牛奶”改为进“报纸”等等，解法思路是完整一致的，请注意！第四部分到此结束.