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

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

2、所需的工时不同，这些产品销售后所能获得利润以及这三种加工设 备因各种条件限制所能使用的有效加工总时数如下表所示：设 消备ABC利润 （万元）甲35970乙95330有效总工时540450720问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大?（此题也可用“单纯形法”或化“对偶问题”用大M法求解）s.t.解：设XI、X2为生产甲、乙产品的数量3x19x25405x15x24509x13x2720Xi,x20、max z = 70xi+30x2由方程组5x15x24509x13x2720解出 Xi=75, X2=15* &X =X2=(75,15) Tmax z =Z*= 70

3、75+30 X15=57OOs.t.max z = 6xi+4x2例2:用图解法求解2x1X210XiX28X27Xi,X20、解:Xi可行解域为由方程组2x1Xix210x28解出 Xi=2, X2=6XiX* =X2=（2, 6）max z = 6 2+4&=36例3:用图解法求解min z = 3xi+X2s.t.x14x232x1 5x212x1 2x28Xi,X20、解:-4+匚二11；5 5、标准型线性规划问题的单纯形解法: 一般思路：1、用简单易行的方法获得初始基本可行解；3；3,直2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3、根据0 l规则确定改进解的方

4、向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入 至最优解。具体做法（可化归 标准型的情况）：设已知max z = C1X1+ C2X2+ CnXns.t.a“ Xia2 X2.ai n Xnbia?i Xia?2 X2.a2n Xnb2ami X1am2X2.amn Xnbm0，j1,2，nXj对第i个方程加入松弛变量Xn+i, i =1, 2,，m,得到aii Xi812X2.a1n XnXn 1aa2i Xia22 X2.a2n XnXn 2b2am1 Xiam2X2.amn XnXn mbXj0, j1 , 2 , . ,

5、n列表计算，格式、算法如下:CbXbbC1X1C2X2Cn+mXn+me lCn+1Xn+1b1ana12& n+mC n+2Xn+2b2a21a22a2 n+mCn+mXn+mbnam1/2am n+mZ1Z2Zn+mT 1T 2-T n+mm注： 乙 =Cn+1 aij+ Cn+2 a2j + Cn+m amj=Cn i aij , (j = 1 , 2,，n + m)i 1(T j =Cj Zj ,当(T j 0时，当前解最优。注：由max t j确定所对应的行的变量为“入基变量”；由0 L=mjn直应0确定所对应的行的变量为“出基变量”，行、列交iaik叉处为主元素，迭代时要求将主元素

6、变为1,此列其余元素变为0。例1：用单纯形法求解(本题即是本资料P2 “图解法”例1的单纯形解法；也可化“对 偶问题”求解)max z =70x1+30x2s.t.3x19x25405x15x24509x13x2720X1,x20解：加入松弛变量X3 , X4, X5，得到等效的标准模型:max z =70x1+30x2+0 X3+0 X4+0 X5s.t.3xi9x2X35405X5x2x44509x13x2x5720Xj0,j1,2,.,5列表计算如下:7030000CbXbbX1X2X3X4X5eL0X354039100540/3=1800X445055010450/5=900X5720

7、(9)3001720/9=800000070 t300000X33000810-1/3300/8=37.50X4500(10/3 )01-5/950/10/3=1570X18011/3001/980/1/3=2407070/30070/9020/3100-70/90X3180001-12/5130X2150103/10-1/670X175100-1/101/65700703002-220/3000-20/3二X*= (75, 15, 180, 0, 0) T二 max z =70 X 75+30 X 15=5700例2:用单纯形法求解max z =7xi+12x2s.t.9x14x23604X

8、-5x22003x110x2300Xi,X20解：加入松弛变量X3 , X4, X5，得到等效的标准模型:max z =7xi+12x2+0 X3+0 X4+0 X5s.t.9x1 4x2 x33604x!5x2x42003x110x2x5300Xj0,j1,2,5列表计算如下:712000CbXbbX1X2X3X4X5e l0X336094100360/4 =900X420045010200/5 =400X53003(10)001300/10 =3000000712T0000X324078/10010-2/5240/78/10 =2400/780X450(5/2 )001-1/250/5/2

9、 =2012X2303/101001/1030/3/10 =10018/512006/517/5 T0006/50X38400178/2529/257X1201002/5-1/512X2240103/254/28428712034/2511/3500034/2511/35二X*= (20, 24, 84, 0, 0) T max z =7 X 20+12 X 24=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“w”，则加松弛变量，使方程成为“=”；若为“”，则减松弛变量，使方程成为“=”。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求 极小值，则

10、为非标准型。可作如下处理：由目标函数min z=cjxj变成等价的目标函数 max ( z) =( cjxj)j ij i令 z=z/,. min z= max 力2、等式约束一一大M法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价 值系数为M , M是很大的正数，从原理上理解又称为“惩罚系数”。(课本P29) 类型一：目标函数仍为max z,约束条件组w与=。例 1: max z =3xi+5x2s.t.X142x2123x12x218X1,x20解：加入松弛变量X3 , X4,得到等效的标准模型:max z =3xi+5x2s.t.Xi X342x2x4 123x1

11、2x218Xj 0, j 1,2,3,4其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量X5 ,得到：max z =3xi+5x2 M X5Xi X3 42x2x4 12S.t.3x1 2x2x5 18Xj 0, j 1,2,5单纯形表求解过程如下:3500MCBXbbXiX2X3X4X5e l0X34(1)01004/1 =40X41202010-MX5183200118/3 =63M2M00M3M + 3 t5+ 2M0003Xi4101000X4120201012/2 =6-MX560(2)3016/2 =332M3+ 3M0M05t3 3M003Xi4101004/1

12、=40X4600(3)116/3 =25X23013/201/23/( 2/3) = 9/2359/205/2009/2 t0M 5/23Xi21001/31/30X320011/31/35X260101/203503/21360003/2M 1-X = (2, 6, 2, 0) T二 max z =3 x 2+5 x 6=36类型一：目标函数min z,约束条件组与=。例2:用单纯形法求解min z =4xi+3x2s.t.2x- 4x2163x1 2x212X-, x20解：减去松弛变量X3, X4,并化为等效的标准模型:max z/ 二一4xi 3x2s.t.2X-4x2X3163x12

13、x2X4Xj0,j1,2,3,4增加人工变量X5、X6,得到:max z/ = 4xi 3x2 Mx5 Mx6s.t2xi4x2X3X5163x12x2X4X612Xj0,j1,2,.,6单纯形表求解过程如下:400MMCbXbbX1X2X3X4X5X6e lMX5162(4)101016/4=4MX61232010112/2=65M6MMMMM5M 46M 3TMM003X241/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/44X

14、i2101/41/21/41/2431/85/41/85/417001/85/4M + 1/8 -M + 5/4二 X*=(2,3, 0, 0)T二 min z = max z/ =( 17)=仃四、对偶问题的解法:什么是对偶问题？1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例（与本资料P2例1 “图解法” P7例1 “单纯形法”同）:某工厂生产甲、乙两种产品，这些产品均需在 A、B、C三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设设Xi、X2为生产甲、乙产品的数量max z = 70xi+30x

15、2s.t.3x19x25405x15x24509x13x2720&x20将这个原问题化为它的对偶问题设yi、目2、y2分别为设备A、B、C单位工时数的加工费。min w = 540yi+450y2+720y3s.t.3y1 5y2 9y3709y1 5y2 3y330yi 0, i 1,用大M法，先化为等效的标准模型：max w/ 二一540yi 450y2 720y3s.t.3y15y29y3y4709%5y23y3y530yj0,j1,2,.,5增加人工变量y6、y7,得到：max力540yi450y2 720y3My 6 My 7s.t3yi5y29y3y4ye 709yi5y23y3y

16、5y730yj0,j1,2,.,5大M法单纯形表求解过程如下:-540-450-72000-M-MCbXbby1y2y3y4y5y6y7e l-My670359-101070/3-M屮30(9)530-10130/9=10/3-12M-10M-12MMM-M-M12M 540 T10M 45012M 720-M-M00-My660010/3(8)-11/31-1/360/8=2.5540yi10/315/91/30-1/901/910/3/1/3=10-300+10/3 M-8M 180-MM/3+6 0-MM/3 600-150+10/3 M8M -540 TMM/3 600M/3+6 0-

17、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/2012510135/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- M该对偶问题的最优解是y*= (0,2,20o , 0,0) T最优目标函数值

18、 min w = -(- 5700) =5700五、运输规划问题:运输规划问题的特殊解法一一“表上作业法”解题步骤：1找出初始调运方案。即在（m x n）产销平衡表上给出m+n-1个数字格。（最小元素法）2、（对空格）求检验数。判别是否达到最优解。如已是最优解，则停止计算，否则转到下一 步。（闭回路法）3、对方案进行改善，找出新的调运方案。（根据检验结果选择入基变量，用 表上闭回路法调 整一一即迭代计算，得新的基本可行解）4、重复2、3,再检验、再迭代，直到求得最优调运方案。类型一：供求平衡的运输规划问题（又称“供需平衡”、“产销平衡”）引例：某钢铁公司有三个铁矿和四个炼铁厂， 铁矿的年产矿石

19、量分别为100万吨、80万吨和50万吨，炼铁厂年需矿石量分别为 50万吨、70万吨、80万吨解：用“表上作业法”求解先用最低费用法（最小元素法）求此问题的初始基础可行解:费销BiB2B3B4产量SiAi1520673306510020X80XA2708144420803020X30A3125332033251050X50XX销量dj50708030 230230 初始方案：20 BlAi50B2Z=15X20+3X80+70X 30+8X20+2QX 30+3X 50=3550 （吨.公里）对的初始可行解进行迭代 （表上闭回路法），求最优解:费销BiB2B3B4产量SiAi1520143301

20、210020x80xA2705381492080x50x30A312320202510503020xx销量dj50708030 230230 用表上闭回路法调整后，从上表可看出，所有检验数eV 0,已得最优解二最优方案:B430 BiZ=15X 20+3x 80+8x 50+20x 30+12X 30+3x 20=1960 （吨.公里）解法分析：如何求检验数并由此确定入基变量？有数字的空格称为“基格” 、打x的空格称 为“空格”，标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点，出发点算0故为偶点。找出所有空格的闭回路后计算它们的检验数 ij Cij Cij ,必须ij 0,才得到最优 奇点

21、偶点解。否则，应选所有中正的最大者对应的变量x为入基变量进行迭代（调整）。检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇 点均减去奇点中的最小运量。重复以上两步，再检验、再调整，直到求得最优运输方案。类型二：供求不平衡的运输规划问题若 Sidj ,则是供大于求（供过于求）问题，可设一虚销地Bn+1,令i 1j 1mnmncin+1 =0，dn+1= S dj，转化为产销平衡问题。若Sidj，则是供小i 1j 1i 1j 1nm于求（供不应求）问题，可设一虚产地 Am+1，令Cm+1j=0, Sm+1= dj $， j 1i 1转化为产销平衡问题。（,2,

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

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

24、2134行约简2890仏“列约简103121470911 （cij）=7141316/ 07698812100042ABCD285甲285(0)0705标11口号乙7(0)511072c匚丙(0)72990002丁*0*0(0)2使总工时为最少的分配任务方案为： 甲t D，乙t B，丙t A，丁t C此时总工时数W=4+3+7+12=26例2:求效率矩阵解:1095854320032102012109785877的最优解5465234583列约简行约简标号3(0)1*023(0)（0） 02 120*所画（）0元素少于n,未2 2得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合

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