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

《2022年《运筹学》复习参考资料知识点及习题.docx》由会员分享，可在线阅读，更多相关《2022年《运筹学》复习参考资料知识点及习题.docx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：概念预备： 定义：满意全部约束条件的解为可行解；可行解的全体称为可 行（解）域；定义：达到目标的可行解为最优解；图解法：图解法采纳直角坐标求解：号）用直线绘出；2、确定可行解域；x1横轴； x2竖轴； 1、将约束条件（取等3、绘出目标函数的图形（等值线） ,确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求微小值沿价值系数向量的反向移动；4、确定最优解及目标函数值；参考例题：（只要求下面这些有唯独最优解的类型）例 1：某厂生产甲、乙

2、两种产品,这两种产品均需在A、B、C 三种不同的设备上加工,每种产品在不同设备上加工所需的工时不同,这些产品销售后所能获得利润以及这三种加工设 备因各种条件限制所能使用的有效加工总时数如下表所示：产消设备A B C 利润（万元）品耗3 5 9 70 甲乙9 5 3 30 有效总工时540 450 720 问：该厂应如何组织生产, 即生产多少甲、 乙产品使得该厂的总利润为最大？（此题也可用“单纯形法 ” 或化“对偶问题 ” 用大 M 法求解） 第 1 页,共 27 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师

3、归纳总结 精品学习资料 - - - - - - - - - - - - - - -解：设 x1、x2 为生产甲、乙产品的数量；max z = 70x1+30x2 s.t. 3x 19x205405x 15x24509x 13x7202x 1,x 2、可行解域为 oabcd0,最优解为 b 点；由方程组X*=5x 15x2450T 解出 x1=75,x2=15 9x 13x2720x 1=（75,15）x2max z =Z*= 70 75+3015=5700 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 27 页 - - - - - -

4、- - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -例 2：用图解法求解max z = 6x1+4x2 s.t. 2x 1x 210x 1x28x 27x 1,x 20、解：可行解域为 oabcd0,最优解为 b 点；由方程组X*=x 12x 1x210解出 x1=2,x2=6 8x 1x2=（2,6）Tx2max z = 6 2+4 6=36 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - -

5、- - - - - - - -例 3：用图解法求解 min z =3x1+x2 s.t. x 1x 2432x 15x212x 12x 28x 1,x 20、解：可行解域为 bcdefb,最优解为 b 点；由方程组x 14x2124 解出 x1=4,x2= 5 第 4 页,共 27 页 52x 1X*=x 14 =（4, 5）Tx24min z =34+ 51 =11 5细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -二、标准型线性规

6、划问题的单纯形解法：一般思路：1、用简洁易行的方法获得初始基本可行解；2、对上述解进行检验,检验其是否为最优解,如是,停止迭代,否就转入 3；3、依据 L规章确定改进解的方向；4、依据可能改进的方向进行迭代得到新的解；5、依据检验规章对新解进行检验,如是最优解,就停止迭代,否就转入 3,直 至最优解；详细做法（可化归 标准型 的情形）：设已知max z = c1x1+ c2x2+ + cnxn s.t. a 11x 1ja 12x2.a 1 nxnb 1a21x 1a22x2.a2nxnb 2.amnxnb mam 1x 1am2x 2x0,j1,2,.,n对第 i 个方程加入放松变量xn+i

7、,i =1,2, ,m,得到a 11x 1a 12x2.a 1 nxnxn1b 1n2b 2x nmb ma21x 1a22x2.a2nxn,nx.am 1x 1am2x 2.amnxnxj0,j1,2,.列表运算,格式、算法如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -CBXBb c1c2cn+mLxn+mx1x2cn+1xn+1b1a11a12a1 n+m对c n+2xn+2b2a21a22a2

8、n+m. . . . . . . . cn+mxn+mbnam1am2am n+mz1z2zn+m12n+mm注： zj =cn+1 a1j+ cn+2 a2j + + cn+m amj=i1cnaij,（j=1,2, ,n+m）j =cj zj , 当j 0 时,当前解最优；注： 由 maxj 确定所对应的行的变量为“ 入基变量” ；由L=min ib iaik0确定所对应的行的变量为“ 出基变量” ,行、列交aik叉处为主元素,迭代时要求将主元素变为1,此列其余元素变为0；例 1：用单纯形法求解 （此题即是本资料P2“ 图解法 ” 例 1 的单纯形解法 ；也可化“偶问题 ” 求解）max

9、z =70x1+30x2s.t. 3 x 1 9 x 2 5405 x 1 5 x 2 4509 x 1 3 x 2 720x 1,x 2 0解：加入放松变量 x3,x4,x5,得到等效的标准模型：max z =70x1+30x2+0 x3+0 x4+0 x5细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -s.t. 3x 19x 2x35405x 15x 2x 44509x 13x 2x 57200,xjj,

10、12 ,., 5列表运算如下：70 30 0 0 0 LCBXBb x1x2x3x4x50 x3540 3 9 1 0 0 540/3 =180 0 x4450 5 5 0 1 0 450/5 =90 0 x5720 （9）3 0 0 1 720/9 =80 0 0 0 0 0 300/8 =37.5 7030 0 0 0 0 x3300 0 8 1 0 - 1/3 0 x450 0 （10/3 ）0 1 - 5/9 50/10/3 =15 70 x180 1 1/3 0 0 1/9 80/1/3 =240 70 70/3 0 0 70/9 0 20/30 0 70/90 x3180 0 0

11、1 12/51 30 x215 0 1 0 3/10 - 1/6 70 x175 1 0 0 - 1/10 1/6 5700 70 30 0 2 20/3 0 0 0 -2 20/3X*=（75,15,180,0,0）Tmax z =70 75+30 15=5700细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -例 2：用单纯形法求解max z =7x1+12x2s.t. 9 x 1 4 x 2 3604 x

12、 1 5 x 2 2003 x 1 10 x 2 300x 1,x 2 0解：加入放松变量 x3,x4,x5,得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t. 9x 14x 22x33603004x 15x 22,1x 42003x 110xx 5xj,0j,., 5列表运算如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -CBXBb 7 12 0 0 0 Lx1x

13、2x3x4x50 x3360 9 4 1 0 0 360/4 =90 0 x4200 4 5 0 1 0 200/5 =40 0 x5300 3 （10）0 0 1 300/10 =30 0 0 0 0 0 240/78/10 =2400/78 7 120 0 0 0 x3240 78/10 0 1 0 - 2/5 0 x450 （5/2 ）00 1 - 1/2 50/5/2 =20 12 x230 3/1010 0 1/10 30/3/10 =100 18/5 12 0 0 6/5 17/5 00 0 6/50 x384 0 0 1 78/2529/25 7 x120 1 00 2/5 -

14、1/5 12 x224 0 1 0 3/25 4/28 428 7 12 0 34/25 11/35 0 0 0 34/25 11/35X*=（20,24,84,0,0）T max z =7 20+12 24=428 三、非标准型线性规划问题的解法：1、一般地,对于约束条件组：如为“ ” ,就加放松变量,使方程成为“ ”；如为“ ” ,就减放松变量,使方程成为“ ”；我们在前面标准型中是规定目标函数求极大值；假如在实际问题中遇到的是求 微小值,就为 非标准型 ；可作如下处理：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页,共 27 页 - -

15、 - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -由目标函数 min z=jn1cjxj变成等价的目标函数max（ z）=jn1cjxj令 z=z /,min z=max z /2、等式约束大 M 法：通过加人工变量的方法,构造人造基,从而产生初始可行基；人工变量的价值系数为 M,M 是很大的正数, 从原理上懂得又称为 “ 惩处系数” ；（课本 P29）类型一：目标函数仍为 max z,约束条件组与；例 1：max z =3x1+5x2s.t. x 1 42 x 2 123 x 1 2 x 2 18x 1,x 2 0解：加入放松

16、变量 x3,x4,得到等效的标准模型：max z =3x1+5x2s.t. x 1x34x5,2x2x4123x 12x 218xj,0j,12,3,4其中第三个约束条件虽然是等式,但因无初始解,所以增加一个人工变量得到：max z =3x1+5x2M x5x 1x 342x 2x412s.t. 3x 12x2x518xj0 ,j,12, . . . ,单纯形表求解过程如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 10 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - -

17、 - - - -CBXBb 3 5 0 0 MLx1x2x3x4x50 x34 （1）0 1 0 0 4/1 =4 0 x412 0 2 0 1 0 Mx518 3 2 0 0 1 18/3 =6 3 3M2M0 0 M3M352M0 0 0 x14 10 1 0 0 0 x412 020 1 0 12/2 =6 Mx56 0（2）3 0 1 6/2 =3 3 3 2M33M0 M4/1 =4 0 533M0 0 x14 1 0 1 0 0 0 x46 00（3）1 1 6/3 =2 5 x23 0 13/2 0 1/2 3/2/3 =9/2 3 3 5 9/2 0 5/2 第 11 页,共

18、27 页 0 0 9/2 0 M 5/2 x12 1 0 0 1/3 1/30 x32 0 0 11/3 1/3 5 x26 0 1 0 1/2 0 0 3/2 1 3 5 36 0 3/2 M10 0 细心整理归纳 精选学习资料 X*=（2,6,2,0）T - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -max z =3 2+5 6=36类型二：目标函数 min z,约束条件组与；例 2：用单纯形法求解min z =4x1+3x2s.t. 2 x 1 4 x

19、2 163 x 1 2 x 2 12x 1,x 2 0解：减去放松变量 x3,x4,并化为等效的 标准 模型：max z / =4x13x2s.t. 2x 14x 2x 316123x 12x2x4xj0 ,j,12 3, ,4增加人工变量 x5、x6,得到：max z / =4x13x2Mx 5Mx 6s.t 2x 14x2x3x516123x 12x2,1x4x6xj,0j2 ,., 6单纯形表求解过程如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 -

20、- - - - - - - - - - - - - -CBXBb 4 x20 0 MMLx1x3x4x5x6Mx516 2 （4）1 0 1 0 16/4=4 Mx612 32 0 1 0 1 12/2=6 3 5M6MMMMM4/1/2=8 5M4 6M3MM0 0 x24 1/2 1 1/4 0 1/4 0 Mx64 （2）0 1/2 1 1/2 1 4/2=2 3 2M3/23 3/4M/2MM/2 3/4M2M5/20 M/2 3/4M3/43M/20 x23 0 1 3/8 1/4 3/8 1/4 4 x12 1 0 1/4 1/2 1/4 1/2 17 4 3 1/8 5/4 1/

21、8 5/4 0 0 1/8 5/4 M 1/8 M 5/4 X*=（2,3,0,0）Tmin z =max z/ =（ 17）=17 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 13 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -四、对偶问题的解法：什么是对偶问题？1、在资源肯定的条件下,作出最大的奉献；2、完成给定的工作,所消耗的资源最少；引例（与本资料P2例1 “ 图解法 ” 、P7例1 “ 单纯形法 ” 同）：某工厂生产甲、乙两种 产品,这些产品均

22、需在 A、B、C 三种不同的设备上加工,每种产品在不同设备 上加工时需要不同的工时,这些产品售后所能获得的利润值以及这三种加工设 备因各种条件下所能使用的有效总工时数如下表：产消设备A B C 利润（万元）品耗3 5 9 70 甲乙9 5 3 30 有效总工时540 450 720 问：该厂应如何组织生产, 即生产多少甲、 乙产品使得该厂的总利润为最大？解：原问题设 x1、x2为生产甲、乙产品的数量；max z = 70x1+30x2 s.t. 3x 1x9x 205405x 15x 24509x 13x 2720x 1,2将这个原问题化为它的对偶问题细心整理归纳 精选学习资料 - - - -

23、 - - - - - - - - - - - 第 14 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -设 y1、y2、y2 分别为设备 A、B、C 单位工时数的加工费；min w = 540y1+450y2+720y3s.t. 3y 15y 29y3709y 15y 23y330yi0,i1,用大 M 法,先化为等效的 标准模型：max w / =540y1450y2720y3 s.t. 3y 15y 29y3y4y5709y 15y23y3300,1yj,j2 ,., 5增加人工变量 y6、y7,得

24、到：max z / =540y1450y2720y3My 6My 7s.t 3y 15y 29y3y4y5y670309y 15y23y3y7yj0 ,j,12 ,., 5大 M 法单纯形表求解过程如下：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 15 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -CBXBb 540 450 720 0 0 MMLy1y2y3y4y5y6y7My670 3 5 9 1 0 1 0 70/3 My730 （9）5 3 0

25、1 0 1 30/9=10/3 My660 12M10M12MMMMM60/8=2.5 12M 54010M 45012M 720MM0 0 0 10/3 （8）1 1/3 1 1/3 540 y110/3 1 5/9 1/3 0 1/9 0 1/9 10/3/1/3 =10 720 y315/2 0 -300+10/3 M-8 M 180MM/3+6 0MM/3 6015/2/5/12 -150+10/3 M 8M -540 MM/3 600 M/3+6 00 5/12 1 1/8 1/24 1/8 1/24 =18 540 y15/6 1 （5/12 ）0 1/24 1/8 1/24 1/

26、8 5/6/5/12 =2 720 y320/3 540 572 720 135/2 475/12 135/2 75/20 1250 135/2 475/12 135/2 M75/2 M1 0 1 1/6 1/6 1/6 1/6450 y22 12/5 1 0 1/10 3/10 1/10 3/10360 450 720 75 15 75 15 5700 180 0 0 75 15 75M15M该对偶问题的最优解是20 y*=（0,2, 3,0,0）T最优目标函数值min w =（ 5700）=5700 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第

27、 16 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -五、运输规划问题：运输规划问题的特别解法“表上作业法”解题步骤：1、找出初始调运方案；即在 m n产销平稳表上给出 m+n-1 个数字格；（最小元素法）2、（对空格）求检验数；判别是否达到最优解；如已是最优解,就停止运算,否就转到下一步；（闭回路法）3、对方案进行改善,找出新的调运方案； （依据检验结果挑选入基变量,用 表上闭回路法 调整 即迭代运算,得新的基本可行解）4、重复 2、3,再检验、再迭代,直到求得最优调运方案；类型一：供求平稳的运输规

28、划问题（又称“ 供需平稳”、“ 产销平稳” ）引例：某钢铁公司有三个铁矿和四个炼铁厂,铁矿的年产矿石量分别为100万吨、80 万吨和 50 万吨,炼铁厂年需矿石量分别为 和 30 万吨,这三个铁矿与四个炼铁厂的距离如下：距炼铁50 万吨、70 万吨、80 万吨厂B1B2B3B4.公里计）？铁离矿A 115 20 3 30 A 270 8 14 20 A 312 3 20 15 问：该公司应如何组织运输, 既满意各炼铁厂需要, 又使总的运输费用为最小 （按吨解：用“ 表上作业法” 求解；先用最低费用法 （最小元素法） 求此问题的初始基础可行解：细心整理归纳 精选学习资料 - - - - - -

29、- - - - - - - - - 第 17 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -费销产量产用地15B12020B2673B38030B4 65 Si地100A1A270503087020148044 2030 3080123202553 33 10 50A350230 销量dj230 初始方案：20 B130 B150 B2A1A220 B2A380 B330 B3.公里）Z=15 20+3 80+70 30+8 20+20 30+3 50=3550（吨对的初始可行解进行迭代（表上闭回路法

30、）,求最优解：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 18 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -费销产量产用地15B12020B214 3B38030B4 12 Si地100A1A2705053 87050 14809 203030801232025 20 10 50A330 20 230 销量dj230 用表上闭回路法调整后,从上表可看出,全部检验数最优方案： 0,已得最优解；20 B1 50 B2 30 B1A1 A2 A380 B3

31、30 B4 20 B2Z=15 20+3 80+8 50+20 30+12 30+3 20=1960（吨 .公里）解法分析：如何求检验数并由此确定入基变量？有数字的空格称为“ 基格”、打 的空格称为“ 空格” ,标号为偶数的顶点称为偶点、 标号为奇数的顶点称为奇点, 动身点算 0 故为偶点；找出全部空格的闭回路后运算它们的检验数 ij c ij c ij,必需 ij0,才得到最优奇点 偶点解；否就,应选全部 中正的最大者对应的变量 xj 为入基变量进行迭代（调整） ；检验后调整运输方案的方法是：在空格的闭回路中全部的偶点均加上奇点中的最小运量,全部的奇点均减去奇点中的最小运量；重复以上两步,再

32、检验、再调整,直到求得最优运输方案；类型二：供求不平稳的运输规划问题细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 19 页,共 27 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -如ims ijn1dj,就是供大于求（供过于求）问题,可设一虚销地Bn+1,令1mnmn,就是供小,ci,n+1=0,dn+1=i1s ij1dj,转化为产销平稳问题；如i1s ij1dj于求（供不应求）问题,可设一虚产地Am+1,令 cm+1,j=0,sm+1=nmdjs ij1i1转化为产销平稳问题；（ ,2, , m；,2, , n）六、工作指派问题：工作指派问题的数学模型 假定有 n 项工作需要完成,恰好有 n 个人每人可去完成其中一项工作,成效要好；工作指派问题的特别解法 “匈牙利法 ” （考！）解题步骤：1、使系数矩阵（效率矩阵）各行、各列显现零元素；作法：行约简 系数矩阵各行元素减去所在行的最小元素,列约简再从所得矩阵的各列减去所在列最小元素；2、试求最优解；如能找出n 个位于不同行不同列