《运筹学》深刻复习参备考资料知识点及知识题

1、第一部分 线性规划问题的求解一、两个变量的线性规划问题的图解法:概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可 行（解）域。定义：达到目标的可行解为最优解。图解法:图解法采用直角坐标求解：xi横轴；X2竖轴。1、将约束条件（取等 号）用直线绘出;2、确定可行解域;3、绘出目标函数的图形（等值线），确定它向最优解的移动方向;注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例1:某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时

2、不同，这些产品销售后所能获得利润以及这三种加工设（此题也可用“单纯形法”或化“对偶问题”用大M法求解）解：设XI、X2为生产甲、乙产品的数量。max z =70x 1+30X 2s.t.3x19x25405x15x24509x13x2720Xi,x20、,最优解为b点。可行解域为oabcdO由方程组5x1 5x29x1 3x2450720解出 xi=75，X2=15XiX2(75 ,15) Tmax z =Z *= 70 X75+30 x15=5700/.X*=例2:用图解法求解max z = 6x i +4x 2s.t.2x12xiX210XiX2X2Xi,X2、解:可行解域为由方程组Xix

3、210x28解出 xi=2 , X2=6X二XiX2（2，6）max z = 6X2+4 X6=36例3:用图解法求解min z = 3xi+X2s.t.Xi2x1XiX25x22x243128Xi,X20、解:可行解域为由方程组0/04bcdefb，最优解为b点。x-,42为 5x212解出X1 =4 ,X2 =XiX2min z =43 X4+ 匚二115二、标准型线性规划问题的单纯形解法: 一般思路:1、用简单易行的方法获得初始基本可行解;2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3;3、根据0L规则确定改进解的方向;4、根据可能改进的方向进行迭代得到新的解;5、

4、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。具体做法（可化归 标准型的情况）：设已知s.t.max z=c 1X1 +c 2X2+ + CnXna11 X1a12 X2.a1nXnbla21X1a22 X2.a2nXnb2am1X1am2 X2.amn Xnbm0，j1,2 ,.nXj对第i个方程加入松弛变量Xn+i ,i =1 , 2，m ,得到a11 X1a21X1a12X2a22X2a1nXnXn 1 Da2n XnXn 2b2am1X1Xjam2X20, jamn Xn2，nXn mbm1,列表计算，格式、算法如下:C1C2Cn+mCBXbBlX1X2X

5、n+mCn+1C n+2Cn+mXn+1xn+2Xn+mbib2bnaiiai2ai n+ma2 n+mamiam2am n+mz1z2Zn+mO1O2（jn+mm注： Zj = Cn+1 a1j+ Cn+2 a2j + + Cn+m amj =Cn i aij , （j = 1 , 2，n + m ）i 1d = Cj Zj，当O <0时，当前解最优。注：由max oj确定所对应的行的变量为“入基变量”；b由 0L= mjn 二冰0确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1,此列其余元素变为0。例1：用单纯形法求解（本题即是本资料P2 “图解法”

6、例1的单纯形解法；也可化“对偶问题”求解）max z =70x 1+30x2S.t.3x19x25405x15x24509x13x2720X1,x20解：加入松弛变量X3 , X4 , X5，得到等效的标准模型:max z =70x1 +30X 2+0 X 3+0 X 4+0 X 5s.t.3x19x2X35405为5x2x44509x13x2X5720Xj0，j1,2,5列表计算如下:7030000CBXBbX1X2X3X4X5Bl0X354039100540/3=1800X445055010450/5=900X5720（9）3001720/9=800000070 T300000X33000

7、810-1/3300/8=37.50X4500(10/3 )01-5/950/10/3=1570X18011/3001/980/1/3=2407070/30070/9020/3 T0070/90X318000112/5130X2150103/10-1/670X175100-1/101/6570070300220/3-2 20/3X*= (75 , 15, 180, 0, 0) Tmax z =70 X75+30 X15=57OO例2:用单纯形法求解max :z =7xi+12x 2s.t.9x14X23604X-15x22003x110x2300Xi,x20解：加入松弛变量X：3，X4，X5，

8、得到等效的标准模型max :z =7xl+12x 2 + 0 X 3+0 X 4+0 X 5s.t.9x14x2X33604xi5x2x42003x110X2x5300Xj0，jI2,5列表计算如下:712000CBXBbx1x2x3x4x5eL0x336094100360/4 =900x420045010200/5 =400x53003(10)001300/10 =3000000712 T000240/78/100X324078/10010-2/5=2400/780X450（5/2）001-1/250/5/2 =2012X2303/101001/1030/3/10 =10018/512006

9、/517/5 T0006/50x38400178/2529/257x1201002/5-1/512X2240103/254/28712034/2511/3542800034/2511/35X = (20, 24 , 84 , 0,max z =7 X20+12 X24=428三、非标准型线性规划问题的解法:般地，对于约束条件组:若为“W”，则加松弛变量，使方程成为“=”若为“A”，则减松弛变量，使方程成为“=” 我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求 极小值，则为非标准型。可作如下处理：nn由目标函数min z=cjxj变成等价的目标函数 max ( z) =(

10、cjxj)j 1j 1令一z=z/ ,.min z= max z/2、等式约束一一大 M法:通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价 值系数为M ,M是很大的正数，从原理上理解又称为“惩罚系数”。(课本P29)类型一：目标函数仍为max z，约束条件组与=。例 1 : max z =3xi+5x 2s.t.Xi3x1 ；Xi，X241218解：加入松弛变量X3 , X4，得到等效的标准模型:max z =3x i +5x 2s.t.Xi2x23x1XjX34X4122X2180,j1,2,3,4其中第三个约束条件虽然是等式，但因无初始解,所以增加一个人工变量X5，得到

11、:max z =3x i +5x 2 M X5Xi X34s.t.2x2x4 12183xi 2x2x5Xj 0, j 1,2,5单纯形表求解过程如下:3500MCbXbbX1X2X3X4X5eL0X34(1 )01004/1 =40X41202010MX5183200118/3 =63M2M00M3M + 3 T5+ 2M0003X14101000X4120201012/2 =6MX560(2)3016/2 =332M3 + 3M0M05 T3 3M003X14101004/1 =40X4600(3)116/3 =23/( 2/3)=5X23013/201/29/2359/205/2009/

12、2 T0M 5/23x121001/31/30x320011/31/35X260101/203503/21360003/2M 16, 2,X*=(2,'max z =3X2+5X6=36类型二：目标函数min z ,约束条件组与=。例2 :用单纯形法求解min z =4x1 +3x 2s.t.16122为 4x23x12 x2x-i, x20解：减去松弛变量X3，X4，并化为等效的标准模型:max z/ =-4x13x2s.t.2x14x2X3163x12x2X4Xj0,j1,2,3,4增加人工变量X5、X6，得到:max z/ -4x13x212s.tMx 5 Mx 62x13x1X

13、j4X2 X32x2x40,j 12.,6X516X612单纯形表求解过程如下:CBXBb4X1X20X30X4MX5MX6eLMX5162(4)101016/4=4MX61232010112/2=65M6MMMMM5M 46M 3 TMM003X241/211/401/404/1/2=8MX64(2)01/211/214/2=22M 3/233/4 M/2MM/2 3/4M2M 5/2 T0M/2 3/4M3/4 3M/203X23013/81/43/81/44X12101/41/21/41/2431/85/41/85/4-17001/85/4M + 1/8M +5/4TX=(2,'

14、min z =max z /(-17 ) =17四、对偶问题的解法:什么是对偶问题?1、在资源一定的条件下，作出最大的贡献;2、完成给定的工作，所消耗的资源最少。引例（与本资料P2例1 “图解法” P7例1 “单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在 A、B、C三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设XI、X2为生产甲、乙产品的数量。max z = 70Xi+30x 2s.t.3x19x25405x15x24509x13x2720X1,x20将这个原问题化为它的对偶问题设yi、y、y分别为设备A、B、C单位工时

15、数的加工费。min w = 540y i+450y 2+720y 3s.t.3% 5y2 9y3709y1 5y2 3y330y 0, i 1,2,3用大M法，先化为等效的标准模型:s.t.max w / = 540y 1 450y 2 720y 33yi9%yj5y25y20,j9y3讨43y31,2,.,570y530增加人工变量y6、y7，得到:5y25y20,jmax z/ = 540y 1 450y 2 720y 3 My 6 My 7s.t9y3 y4y 703y3y5y7 301,2,5大M法单纯形表求解过程如下:54045072000MMCBXBby1y2y3y4y5y6y7e

16、L-My670359101070/330/9=10-My730(9)530101/312M10M12MMMMM12M 12M 540T 10M 450720MM0060/8=2.-My660010/3(8)11/311/3510/3/1/3y110/315/91/301/901/9540=10-300+10/3-8M MM/3+60MM/3 60M180-150+10/30M8M-540 TMM/3 600M/3+6015/2/5/1y315/205/1211/81/241/81/242720=185/6/5/12y15/61(5/12 )01/241/81/241/8540=25405727

17、20135/2475/12135/275/20125 T0135/2475/12135/2 - M75/2 My320/31011/61/61/61/6720y2212/5101/103/101/103/1045036045072075157515570018000751575 M15 - M该对偶问题的最优解是(0, 2,203 ，0，最优目标函数值min w(-5700 ) =5700五、运输规划问题: 运输规划问题的特殊解法一一“表上作业法”解题步骤:1、找出初始调运方案。即在（m Xn）产销平衡表上给出m+n-1个数字格。（最小元素法） 2、（对空格）求检验数。判别是否达到最优解。如已

18、是最优解，则停止计算，否则转到下一步。（闭回路法）3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用 表上闭回路法调 整一一即迭代计算，得新的基本可行解）4、重复2、3，再检验、再迭代，直到求得最优调运方案。类型二：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例：某钢铁公司有三个铁矿和四个炼铁厂， 铁矿的年产矿石量分别为100万吨、80万吨和50万吨，炼铁厂年需矿石量分别为 50万吨、70万吨、80万吨和30万吨，这三个铁矿与四个炼铁厂的距离如下:问：该公司应如何组织运输，既满足各炼铁厂需要，又使总的运输费用为最小（按吨.公里计）？解：用“表上作业法”求解。先用

19、最低费用法（最小元素法）求此问题的初始基础可行解:费销产BiB2B3B4产量SiAi1520673306510020X80XA2708144420803020X30A3125332033251050X50XX销量dj50708030230二初始方案:AiBi30<BiA35B280B330B3Z=15 X20+3X80 +70 X30 +8 X20 +20 X30 +3 X50 =3550（吨公里）对的初始可行解进行迭代 （表上闭回路法），求最优解:费销 产BiB2B3B4产量SiAi1520143301210020X80XA2705381492080X50X30A31232020251

20、0503020XX销量dj50708030230用表上闭回路法调整后,从上表可看出，所有检验数cV0,已得最优解。二最优方案:Ai80Bi30B2Bi20Z=15 X20 +3B3A2A3B4X80+8 X50+20 X30+12 X30+3 X20=1960B2（吨公里）解法分析：如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打X的空格称 为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数 ij cij Cjj ,必须ij o,才得到最优 奇点偶点解。否则，应选所有 中正的最大者对应的变量x为入基变量进行迭代

21、（调整）。检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇 点均减去奇点中的最小运量。重复以上两步，再检验、再调整,类型二：供求不平衡的运输规划问题mn若 Sidj，则是供大于求（供过于求）问题,直到求得最优运输方案。可设一虚销地 Bn+1，令Ci,n+1 =0，d n+1mnSdj，转化为产销平衡问题。i 1 j 1mSi1ndj，则是供 j 1小于求（供不应求）问题，可设一虚产地 Am+1，令Cm+1,j=0，i 1j 1nmSm+1 = djsi，转化为产销平衡问题。j 1i 1（，2，m 2,，n）n个人每人可六、工作指派问题:工作指派问题的数学模

22、型一一假定有n项工作需要完成，恰好有去完成其中一项工作，效果要好。工作指派问题的特殊解法“匈牙利法”（考！ ！）解题步骤:1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法：行约简一系数矩阵各行元素减去所在行的最小元素，列约简一再从所得矩阵 的各列减去所在列最小元素。2、试求最优解。如能找出n个位于不同行不同列的零元素，令对应的 Xij= 1，其余Xij得最优解，结束；否则下一步。的行作法：由独立0元素的行（列）开始，独立 0元素处画（）标记，在有（）列中划去（也可打*）其它0元素；再在剩余的0元素中重复此做法，直至不能标记 （ 止。3、作能覆盖所有0元素的最少数直线集合。作法：对没有（）的

23、行打2号；对已打2号的行中所有0元素的所在列打2号;再对打有"号的列中0元素的所在行打2号；重复、直到得不出新的打2号的行（列） 为止；对没有打2号的行画一横线，对打2号的列画一纵线，这就得到覆盖所有 0元素的最少直线数。未被直线覆盖的最小元素为Cij,在未被直线覆盖处减去Cij,在直线交叉处加上Cij 0 4、重复2、3，直到求得最优解。类型一:求极小值的匈牙利法：（重点掌握这种基本问题）例1:有甲、乙、丙、丁四个人，要派去完成A、B、C、D四项工作，他们完成的工时如下表:试问：应如何分配任务可使总工时为最少?解：用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为:6121

24、3410312147141316881210行约简(Cij)=27008070996401192列约简2857050720 0 001192标号乙2857 (0)5(0)720*0*(0)(0)119使总工时为最少的分配任务方案为:甲7 D，乙7B,丙7 A，丁7 C此时总工时数W=4+3+7+12=26 例2:求效率矩阵109758754623487的最优解。55解:105529843776488 行约简7553010230102221列约简2 13301023010222标号10匚232(0)0(0)3211(0)20*所画()0元素少于n，未0*122得到最优解，需要继续变换矩阵 （求能

25、覆盖所有0元素的最少数直线集合）：32(0)0)321V1(0)20*0*122V未被直线覆盖的最小兀素为Cij=1，在未被直线覆盖处减去1,在直线交叉处加上10标号*4020220001210001(0)2(0)1二得最优解:0100000110000010类型二：求极大值的匈牙利法:min z= max ( z)(Cij )f( MCij)=0(0)max z=iCij Xij =ji(M(M Cij )xij0(0)中最大的元素为MCij) xijCij xij第一部分到此结束第二部分动态规划只要求掌握动态规划的最短路问题一一用“图上标号法”解决：具体解题步骤请参看教材P103 （这是本套资料少见的与教材完全相同的算法类型之一，务 必看书掌握）学员们只有完全理解了这种作法（思路：逆向追踪）才有可能做题，考试时数字无论如何变化都能作出正确求解!第二部分到此结束第三部分网络分析、求最小生成树（最小支撑树、最小树）问题:破圈法任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条 以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步 骤，直到得到一个不含圈的图为止，这时的图便是最小树。参考例题:例：求下图的最小生成树:V6V6V5V3已得最小树，此时权 w = 1+2+4+5+9=21为最小。二、最短路问题