《运筹学》复习参考资料知识点和习题

./第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行〔解域。定义：达到目标的可行解为最优解。㈡图解法：图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件〔取等号用直线绘出；2、确定可行解域；3、绘出目标函数的图形〔等值线,确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。㈢参考例题：〔只要求下面这些有唯一最优解的类型例1：某厂生产甲、乙两种产品,这两种产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工所需的工时不同,这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：品产耗消备设品产耗消备设ABC利润〔万元甲乙3599537030有效总工时540450720——问：该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大？〔此题也可用"HYPERLINK单纯形法"或化"HYPERLINK对偶问题"用大M法求解解：设x1、x2为生产甲、乙产品的数量。⑴maxz=70x1+30x⑴⑵⑵⑸、⑹⑸、⑹⑷⑶可行解域为oabcd0,最优解为b点。由方程组解出x1=75,x2=15∴X*==〔75,15T∴maxz=Z*=70×75+30×15=5700例2：用图解法求解⑴maxz=6x1+4x⑴⑵⑵⑸、⑹⑸、⑹⑷⑶解：可行解域为oabcd0,最优解为b点。由方程组解出x1=2,x2=6∴X*==〔2,6T∴maxz=6×2+4×6=36例3：用图解法求解⑴minz=－3x1+x⑴s.t.⑵⑵⑶⑷⑸⑹、⑺解：可行解域为bcdefb,最优解为b点。由方程组解出x1=4,x2=∴X*==〔4,T∴minz=－3×4+=－11二、标准型线性规划问题的单纯形解法：㈠一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验,检验其是否为最优解,若是,停止迭代,否则转入3；3、根据θL规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验,若是最优解,则停止迭代,否则转入3,直至最优解。㈡具体做法〔可化归标准型的情况：设已知maxz=c1x1+c2x2+…+cnxns.t.对第i个方程加入松弛变量xn+i,i=1,2,…,m,得到列表计算,格式、算法如下：CBXBbc1c2…cn+mθLx1x2…xn+mcn+1xn+1b1a11a12…a1n+mcn+2xn+2b2a21a22…a2n+m…………cn+mxn+mbnam1am2…amn+mz1z2…zn+mσ1σ2…σn+m注①：zj=cn+1a1j+cn+2a2j+…+cn+mamj=,〔j=1,2,…,σj=cj－zj,当σj≤0时,当前解最优。注②：由max{σj}确定所对应的行的变量为"入基变量"；由θL=确定所对应的行的变量为"出基变量",行、列交叉处为主元素,迭代时要求将主元素变为1,此列其余元素变为0。例1：用单纯形法求解〔本题即是本资料P2"HYPERLINK图解法"例1的单纯形解法；也可化"HYPERLINK对偶问题"求解maxz=70x1+30x2s.t.解：加入松弛变量x3,x4,x5,得到等效的标准模型：maxz=70x1+30x2+0x3+0x4+0x5s.t.列表计算如下：CBXBb7030000θLx1x2x3x4x50x354039100540/3=1800x445055010450/5=900x5720〔93001720/9=800000070↑300000x33000810-1/3300/8=37.50x4500〔10/301-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3↑00－70/90x3180001－12/5130x2150103/10-1/670x175100-1/101/6570070300220/3000-2－20/3∴X*=〔75,15,180,0,0T∴maxz=70×75+30×15=5700例2：用单纯形法求解maxz=7x1+12x2s.t.解：加入松弛变量x3,x4,x5,得到等效的标准模型：maxz=7x1+12x2+0x3+0x4+0x5s.t.列表计算如下：CBXBb712000θLx1x2x3x4x50x336094100360/4=900x420045010200/5=400x53003〔10001300/10=3000000712↑0000x324078/10010-2/5240/78/10=2400/780x450〔5/2001-1/250/5/12x2303/101001/1030/3/18/512006/517/5↑000－6/50x384001－78/2529/257x1201002/5-1/512x224010－3/254/28428712034/2511/35000－34/25－11/35∴X*=〔20,24,84,0,0T∴maxz=7×20+12×24=428三、非标准型线性规划问题的解法：1、一般地,对于约束条件组：若为"≤",则加松弛变量,使方程成为"＝"；若为"≥",则减松弛变量,使方程成为"＝"。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值,则为非标准型。可作如下处理：由目标函数minz=变成等价的目标函数max〔－z=令－z=z/,∴minz=－maxz/2、等式约束——大M法：通过加人工变量的方法,构造人造基,从而产生初始可行基。人工变量的价值系数为－M,M是很大的正数,从原理上理解又称为"惩罚系数"。〔课本P29类型一：目标函数仍为maxz,约束条件组≤与＝。例1：maxz=3x1+5x2s.t.解：加入松弛变量x3,x4,得到等效的标准模型：maxz=3x1+5x2s.t.其中第三个约束条件虽然是等式,但因无初始解,所以增加一个人工变量x5,得到：maxz=3x1+5x2－Mx5s.t.单纯形表求解过程如下：CBXBb3500－MθLx1x2x3x4x50x34〔101004/1=40x41202010——－Mx5183200118/3=6－3－200－M3M＋35＋20003x1410100——0x4120201012/2=6－Mx560〔2－3016/2=33－23＋30－M05↑－3－3003x14101004/1=40x4600〔31－16/3=25x2301－3/201/23/<－2/3>=－9/235－9/205/2009/2↑0－M－5/2305x12100－1/31/3x320011/3－1/3x260101/20363503/21000－3/2－M－1∴X*=〔2,6,2,0T∴maxz=3×2+5×6=36类型二：目标函数minz,约束条件组≥与＝。例2：用单纯形法求解minz=4x1+3x2s.t.解：减去松弛变量x3,x4,并化为等效的标准模型：maxz/=－4x1－3x2s.t.增加人工变量x5、x6,得到：maxz/=－4x1－3x2－Mx5－Mx6s.t单纯形表求解过程如下：CBXBb－400－M－MθLx1x2x3x4x5x6－Mx5162〔4－101016/4=4－Mx612320－10112/2=6－5－6MM－M－M5M－6M－3－M－M00－3x241/21－1/401/404/1/2=8－Mx64〔201/2－1－1/214/2=2－2M－33/4－M/2MM/2－3/4－M2M－5/20M/2－3/4－M3/4－3M0－3x2301－3/81/43/8－1/4－4x12101/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,0T∴minz=－maxz/=－〔－17=17四、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下,作出最大的贡献；2、完成给定的工作,所消耗的资源最少。引例〔与本资料P2例1"HYPERLINK图解法"、P7例1"HYPERLINK单纯形法"同：某工厂生产甲、乙两种产品,这些产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工时需要不同的工时,这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：品产耗消备设品产耗消备设ABC利润〔万元甲乙3599537030有效总工时540450720——问：该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大？解：原问题——设x1、x2为生产甲、乙产品的数量。maxz=70x1+30x2s.t.将这个原问题化为它的对偶问题——设y1、y2、y2分别为设备A、B、C单位工时数的加工费。minw=540y1+450y2+720y3s.t.用大M法,先化为等效的标准模型：maxw/=－540y1－450y2－720y3s.t.增加人工变量y6、y7,得到：maxz/=－540y1－450y2－720y3－My6－My7s.t大M法单纯形表求解过程如下：CBXBb－540－450－72000－M－MθLy1y2y3y4y5y6y7－My670359－101070/3－My730〔9530－10130/9=10/3－12－10－12MM－M－M12M－54010M－4512M－72－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/3-8M－－M－M/3+60－MM/3－600-150+10/38M-540MM/3－600－M/3+60－720y315/205/121－1/81/241/8－1/2415/2/5/12=18－540y15/61〔5/1201/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－720－450y320/3－1011/61/61/6－1/6y2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴该对偶问题的最优解是y*=〔0,2,,0,0T最优目标函数值minw=－〔－5700=5700五、运输规划问题：运输规划问题的特殊解法——"表上作业法"解题步骤：1、找出初始调运方案。即在<m×n>产销平衡表上给出m+n-1个数字格。〔最小元素法2、〔对空格求检验数。判别是否达到最优解。如已是最优解,则停止计算,否则转到下一步。〔闭回路法3、对方案进行改善,找出新的调运方案。〔根据检验结果选择入基变量,用表上闭回路法调整——即迭代计算,得新的基本可行解4、重复2、3,再检验、再迭代,直到求得最优调运方案。类型一：供求平衡的运输规划问题〔又称"供需平衡"、"产销平衡"引例：某钢铁公司有三个铁矿和四个炼铁厂,铁矿的年产矿石量分别为100万吨、80万吨和50万吨,炼铁厂年需矿石量分别为50万吨、70万吨、80万吨和30万吨,这三个铁矿与四个炼铁厂的距离如下：矿铁厂铁离距炼矿铁厂铁离距炼B1B2B3B4A1A2A3152033070814201232015问：该公司应如何组织运输,既满足各炼铁厂需要,又使总的运输费用为最小〔按吨.公里计？解：用"表上作业法"求解。⑴先用最低费用法〔最小元素法求此问题的初始基础可行解：地产用费地销地产用费地销B1B2B3B4产量

SiA11520－67330－6510020×80×A2708144420803020×30A312533203325－1050×50××销量dj50708030230230∴初始方案：B2B2203030B1B3A22080B1B3A1BB250A3Z=15×20+3×80+70×30+8×20+20×30+3×50=3550〔吨.公里⑵对⑴的初始可行解进行迭代〔表上闭回路法,求最优解：地产用费地销地产用费地销B1B2B3B4产量

SiA11520－14330－1210020×80×A270－53814－92080×50×30A312320－2025－10503020××销量dj50708030230230用表上闭回路法调整后,从上表可看出,所有检验数σ＜0,已得最优解。∴最优方案：3020B3020B1B2A35030B2B4A22080B1B3A1Z=15×20+3×80+8×50+20×30+12×30+3×20=1960〔吨.公里解法分析：①如何求检验数并由此确定入基变量？有数字的空格称为"基格"、打×的空格称为"空格",标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点,出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数,必须≤0,才得到最优解。否则,应选所有中正的最大者对应的变量xj为入基变量进行迭代〔调整。②检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量,所有的奇点均减去奇点中的最小运量。③重复以上两步,再检验、再调整,直到求得最优运输方案。类型二：供求不平衡的运输规划问题若,则是供大于求〔供过于求问题,可设一虚销地Bn+1,令ci,n+1=0,dn+1=,转化为产销平衡问题。若,则是供小于求〔供不应求问题,可设一虚产地Am+1,令cm+1,j=0,sm+1=,转化为产销平衡问题。〔,2,…,m；,2,…,n六、工作指派问题：工作指派问题的数学模型——假定有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甲乙丙丁61213410312147141316881210试问：应如何分配任务可使总工时为最少？解：用"匈牙利法"求解。已知条件可用系数矩阵〔效率矩阵表示为：列约简行约简〔cij=列约简行约简ABCDABCD标号甲乙丙丁标号甲乙丙丁∴使总工时为最少的分配任务方案为：甲→D,乙→B,丙→A,丁→C此时总工时数W=4+3+7+12=26例2：求效率矩阵的最优解。列约简行约简解：列约简行约简标号所画〔0元素少于n,未得到最优解,需要继续变换矩阵〔求能覆盖所有0元素的最少数直线集合：标号√√√√√√未被直线覆盖的最小元素为cij=1,在未被直线覆盖处减去1,在直线交叉处加上1。标号标号∴得最优解：类型二：求极大值的匈牙利法：minz=－max〔－z〔cij→〔M－cij=〔bij,〔cij中最大的元素为Mmaxz===－HYPERLINK第一部分到此结束第二部分动态规划只要求掌握动态规划的最短路问题——用"图上标号法"解决：具体解题步骤请参看教材P103〔这是本套资料少见的与教材完全相同的算法类型之一,务必看书掌握学员们只有完全理解了这种作法〔思路：逆向追踪才有可能做题,考试时数字无论如何变化都能作出正确求解！HYPERLINK第二部分到此结束第三部分网络分析一、求最小生成树〔最小支撑树、最小树问题：破圈法——任取一个圈,从圈中去掉一条权最大的边〔如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条。在余下的图中,重复这个步骤,直到得到一个不含圈的图为止,这时的图便是最小树。参考例题：例：求下图的最小生成树：6767941510v2v1v3v5v4v632899415v2v1