(完整版)《运筹学》复习参考资料知识点及习题最新（精华版）

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

2、需的工时不同，这些产品销售后所能获得利润以及这三种加工设设消备abc利润（万元）产耗品问：该厂应如何组织生产， 即生产多少甲、 乙产品使得该厂的总利润为最大？（此题也可用“ 单纯形法 ”或化“ 对偶问题 ”用大 m 法求解）备因各种条件限制所能使用的有效加工总时数如下表所示：甲35970乙95330有效总工时540450720第 28 页 共 27 页解：设 x1、x2 为生产甲、乙产品的数量。max z = 70x1+30x2s.t.3x1 5x1 9x19 x2 5x2 3x2540450720x1， x20、可行解域为 oabcd0，最优解为 b 点。由方程组x15x15x24509x1

3、3x2720解出 x1=75，x2=15 x*=x2=（75，15）t max z =z* = 70 75+3015=5700例 2：用图解法求解max z = 6x1+4x2s.t.2 x1x210x1x28x27x1， x20解：、可行解域为 oabcd0，最优解为 b 点。由方程组x12x1x210x1x28解出 x1=2，x2=6x* =x2=（ 2， 6）t max z = 6 2+46=36例 3：用图解法求解min z =3x1+x2s.t.x12 x1 x14x235x2122x28x1， x20解：、可行解域为 bcdefb，最优解为 b 点。由方程组x1x1 2x145x2

4、12t44解出 x1=4， x2= 5x* =x2=（ 4， 5 ）41 min z =34+ 5 = 11 5二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据 l 规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。具体做法（可化归 标准型 的情况）： 设已知max z = c1x1+ c2x2+ + cnxns.t.a11 x1 a21 x1a12 x2 a22 x2.a1n xnb1

5、a2n xnb2.am1 x1am2 x2.amn xnbmx j0，j1，2，. ， n对第 i 个方程加入松弛变量 xn+i， i =1， 2， ， m，得到a11 x1 a21 x1a12 x2 a22 x2.a1n xn a2n xnxn 1b1xn 2b2.am1 x1am2 x2.amn xnxn mbmx j0， j1，2，. ， n列表计算，格式、算法如下：cbxbbx1x2xn+mcn+1x n+1b1a11a12a1 n+mc n+2x n+2b2a21a22a2 n++mxn+mbnam1am2am n+mz1z2zn+m12n+mmc1c2cn+m l注： zj

6、=cn+1a1j+ cn+2a2j+cn+mamj=cni aij，（j=1， 2，n+m）i1j=cj zj, 当j 0 时，当前解最优。注： 由 maxj 确定所对应的行的变量为“入基变量”；由l=minbiaikaik0确定所对应的行的变量为“出基变量”，行、列交i叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为 0。例 1：用单纯形法求解 （本题即是本资料 p2“图解法”例 1 的单纯形解法 ；也可化“ 对偶问题”求解）max z =70x1+30x2s.t.3x19x25405x15x24509x13x2720x1， x20解：加入松弛变量 x3，x4， x5，得到等效的标准

7、模型：max z =70x1+30x2+0 x3+0 x4+0 x5s.t.3x19x2x35405x19x15x23x2x4450x5720x j0, j1,2,.,57030000cbxbbx 1x2x3x4x5 l5700列表计算如下：0x354039100540/3=1800x445055010450/5=900x5720（9）3001720/9=800000070300000x33000810- 1/3300/8=37.50x4500（10/3 ）01- 5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/30070/90x31

8、8000112/5130x2150103/10- 1/670x175100- 1/101/670300220/3000-220/3x * =（ 75， 15， 180， 0，0） t max z =70 75+30 15=5700例 2：用单纯形法求解max z =7x1+12x2s.t.9x1 4x1 3x14x2 5x2 10x2360200300x1，x20解：加入松弛变量 x3，x4， x5，得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t.9x14x2x33604x15x2x42003x110x2x5300x j0, j1,2,.,5列表计算如下

9、：712000cbx bbx1x2x3x4x5 l0x336094100360/4 =900x420045010200/5 =400x53003（ 10）001300/10 =30000007120000x324078/10010- 2/5240/78/10 =2400/780x450（ 5/2 ）001- 1/250/5/2 =2012x2303/101001/1030/3/10 =10018/512006/517/5 0006/50x38400178/2529/257x1201002/5- 1/512x224010 3/254/28712034/2511/3500034/2511/3542

10、8x * =（ 20， 24， 84， 0，0） t max z =7 20+12 24=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“”，则加松弛变量，使方程成为“” ； 若为“”，则减松弛变量，使方程成为“” 。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为 非标准型 。可作如下处理：由目标函数 min z=nc j x jj 1n变成等价的目标函数 max（ z） =(j1c j x j )令 z=z/， min z= max z/ 2、等式约束大 m 法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数

11、为 m ，m 是很大的正数， 从原理上理解又称为 “惩罚系数”。（课本 p29）类型一：目标函数仍为 max z，约束条件组与。例 1： max z =3x1+5x2s.t.x1 3x142x2122x218x1， x20解：加入松弛变量 x3，x4，得到等效的标准模型： max z =3x1+5x2s.t.x1x342x2x4123x12x218x j0, j1,2,3,4其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x5，得到：max z =3x1+5x2 m x5s.t.x1 2x2 3x1x34x42 x212x518x j0, j1,2,.,5单纯形表求解过程如下：

12、3500 mcbxbb lx1x 2x3x4x50x34（1）01004/1 =40x41202010mx5183200118/3 =63m2m00 m3m35 2m0003x14101000x4120201012/2 =6mx560（2）3016/2 =332m3 3m0 m0533m003x14101004/1 =40x4600（ 3）116/3 =25x23013/201/23/(2/3) = 9/2359/205/2009/2 0m 5/23x121001/31/30x320011/31/35x260101/203503/21360003/2 m1 x* =（ 2， 6， 2， 0）

13、t max z =3 2+5 6=36类型二：目标函数 min z，约束条件组与。例 2：用单纯形法求解min z =4x1+3x2s.t.2x1 3x14x2162 x212x1，x20解：减去松弛变量 x3，x4，并化为等效的 标准模型：max z/ = 4x13x2s.t.2x1 3x14x2 2 x2x316x412x j0, j1,2,3,4增加人工变量 x5、x6，得到：max z/ = 4x13x2 mx 5 mx 6s.t2x1 3x14 x2x32x2x4x516x612x j0, j1,2,.,6单纯形表求解过程如下：400mmcbxbb lx1x2x3x4x5x6mx51

14、62（4）101016/4=4mx612320 10112/2=6 5m6mmmmm5m46m3mm00 3x241/211/401/404/1/2=8mx64（ 2）01/2 1 1/214/2=22m3/22m 5/2303/4 m/2m/2 3/4mmm/2 3/43/43m/2m0 3x23013/81/43/8 1/4 4x12101/41/2 1/41/2 1740301/81/85/45/4 1/8 5/4m 1/8 m 5/4x * =（ 2， 3， 0， 0）t min z = max z / =（ 17） =17四、对偶问题的解法： 什么是对偶问题？1、在资源一定的条件下，

15、作出最大的贡献；2、完成给定的工作，所消耗的资源最少。产品，这些产品均需在 a、b、c 三种不同的设备上加工，每种产品在不同设备上加工时需要不同的工时，这些产品售后所能获得的利润值以及这三种加工设备因各种条件下所能使用的有效总工时数如下表：设消备abc利润（万元）产耗品引例（与本资料 p2 例 1 “ 图解法”、p7 例 1 “单纯形法 ”同）：某工厂生产甲、乙两种甲35970乙95330有效总工时540450720问：该厂应如何组织生产， 即生产多少甲、 乙产品使得该厂的总利润为最大？ 解：原问题设 x1、x2 为生产甲、乙产品的数量。max z = 70x1+30x2s.t.3x1 5x1

16、 9x19x2 5x2 3x2540450720x1， x20将这个原问题化为它的对偶问题设 y1、y2、y2 分别为设备 a 、b、c 单位工时数的加工费。min w = 540y1+450y2+720y3s.t.3 y15 y29 y3709 y1yi5 y20， i3y31，2，330用大 m 法，先化为等效的 标准模型：max w/ = 540y1450y2720y3s.t.3y1 9 y15y25 y29 y3y4 3y370y530y j0, j1,2,.,5增加人工变量 y6、y7，得到：max z/ = 540y1 450y2 720y3 my 6 my 7s.t3y1 9 y

17、15 y25y29 y3y43 y3y670y5y730y j0, j1,2,.,5大 m 法单纯形表求解过程如下：cbx bb54045072000mm ly1y2y3y4y5y6y7my670359 101070/3my730（9）53010130/9=10/312m 10m 12mmm mm12m 540 10m 45012m 720m m00my660010/3（8） 11/311/360/8=2.510/3/1/3540y110/315/91/301/901/9-300+10/3 m-8 m 180m m/3+6 0 mm/3 600-150+10/3 m 8m -540 mm/3

18、600 m/3+6 0=10720y315/205/1211/81/241/8 1/24540y15/61（5/12 ）01/241/81/241/8540572720 135/2475/12 135/2 75/201250135/2475/12135/2 m75/2 m720y320/31011/61/61/61/6450y2212/5101/103/101/103/10 57003604507207515 75151800075 1575m15 m15/2/5/12=185/6/5/12=2该对偶问题的最优解是y*=（ 0，2，20， 0， 0） t3最优目标函数值min w = （ 57

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

20、 万吨和 50 万吨，炼铁厂年需矿石量分别为 50 万吨、70 万吨、80 万吨和 30 万吨，这三个铁矿与四个炼铁厂的距离如下：炼距铁厂b1b2b3b4离铁矿a 11520330a 27081420a 31232015.问：该公司应如何组织运输， 既满足各炼铁厂需要， 又使总的运输费用为最小 （按吨 公里计）？解：用“表上作业法”求解。先用最低费用法 （最小元素法） 求此问题的初始基础可行解：费销产量用产地b1b2b 3b 4地si1520 67330 65a 11002080708144420a 28030203012533203325 10a 35050销量230dj5070803023

21、0初始方案：20b130b1a 1a 220b2a 350b280b330b3.z=1520+380+70 30+820+20 30+3 50=3550（ 吨 公里）对的初始可行解进行迭代（表上闭回路法），求最优解：费销产量si用地b1b2b 3b 4产地1520 14330 12a 120801007053814 920a 280503012320 2025 10a 33020销量50708030dj50230230用表上闭回路法调整后，从上表可看出，所有检验数0，已得最优解。最优方案：20b1a 180b350b2a 230b430b1a 320b2.z=1520+380+8 50+203

22、0+12 30+3 20=1960（ 吨 公里）解法分析：如何求检验数并由此确定入基变量？有数字的空格称为“基格”、打的空格称为“空格”，标号为偶数的顶点称为偶点、 标号为奇数的顶点称为奇点， 出发点算 0 故为偶点。找出所有空格的闭回路后计算它们的检验数ijcij奇点cij偶点，必须 ij 0，才得到最优解。否则，应选所有中正的最大者对应的变量 xj 为入基变量进行迭代（调整） 。检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量，所有的奇点均减去奇点中的最小运量。重复以上两步，再检验、再调整，直到求得最优运输方案。类型二：供求不平衡的运输规划问题m若sii 1nd

23、 j ，则是供大于求（供过于求）问题，可设一虚销地bn+1 ，令j 1mci,n+1 =0， dn+1 =sii 1nmd j ，转化为产销平衡问题。若sij 1i 1nd j ，则是供小j 1n于求（供不应求）问题，可设一虚产地am+1，令 cm+1,j =0， sm+1 =d jj 1msi ，i 1转化为产销平衡问题。（ ，2， m；，2， n）六、工作指派问题：工作指派问题的数学模型 假定有 n 项工作需要完成，恰好有 n 个人每人可去完成其中一项工作，效果要好。工作指派问题的特殊解法 “ 匈牙利法 ”（ 考！）解题步骤：1、使系数矩阵（效率矩阵）各行、各列出现零元素。作法：行约简 系

24、数矩阵各行元素减去所在行的最小元素，列约简再从所得矩阵的各列减去所在列最小元素。2、试求最优解。如能找出 n 个位于不同行不同列的零元素，令对应的xij= 1，其余 xij = 0， 得最优解，结束；否则下一步。作法：由独立 0 元素的行（列）开始，独立0 元素处画（ ）标记 ，在有（ ）的行列中划去（也可打 * ）其它 0 元素； 再在剩余的 0 元素中重复此做法， 直至不能标记 （ ）为止。3、作能覆盖所有 0 元素的最少数直线集合。作法： 对没有（ ）的行打号；对已打号的行中所有0 元素的所在列打号；再对打有号的列中0 元素的所在行打号； 重复、直到得不出新的打号的行 (列) 为止；对没

25、有打号的行画一横线，对打号的列画一纵线，这就得到覆盖所有0 元素的最少直线数。未被直线覆盖的最小元素为cij ,在未被直线覆盖处减去 cij ,在直线交叉处加上cij 。4、重复 2、3，直到求得最优解。类型一：求极小值的匈牙利法： （重点掌握这种基本问题）例 1：有甲、乙、丙、丁四个人，要派去完成a、b、c、d 四项工作，他们完成的工时如下表：任工务abcd人时甲612134乙1031214丙7141316丁881210试问：应如何分配任务可使总工时为最少？解：用“匈牙利法”求解。已知条件可用系数矩阵（效率矩阵）表示为：612134289010312行约简147091171413160769

26、8812100042abcd甲285(0)（cij ） =列约简28507051107290002标号乙丙丁7(0)0*(0)70*51129(0)2使总工时为最少的分配任务方案为： 甲 d，乙 b，丙 a，丁 c 此时总工时数 w=4+3+7+12=26例 2：求效率矩阵10978587754652345的最优解。10978行约简3201587703225465102123450123列约简解：32(0)0(0)3213200032110200122*标号( 0)201221*所画（） 0 元素少于 n，未0*得到最优解，需要继续变换矩阵 （求能覆盖所有 0 元素的最少数直线集合） ：3(0

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