《运筹学知识点归纳.doc》由会员分享，可在线阅读，更多相关《运筹学知识点归纳.doc（30页珍藏版）》请在三一文库上搜索。
1、考试时间：2009-1-4 10:00-12:00考试地点：金融 1、2: （二） 201，会计 1、2 : （二）106人资 1、2 : （二） 203，工商 1、2 : （二）205林经 1、2 : （二） 306答疑时间：17周周二周四上午 8 : 00-11 : 0018周周一周三上午 8 : 00-11 : 00地点：基础楼201线性规划如何建立线性规划的数学模型；线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？如何用单纯形方法求解线性规划问题？如何确定初始可行基或如何求初始基本可行解？（
2、两阶段方法）如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件）对偶单纯形方法适合解决什么样的问题？如何求解？对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？1、建立线性规划的数学模型:特点：(1 )每个行动方案可用一组变量(X1，xn )的值表示，这些变量一般取非负值；(2) 变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；(3) 有一个需要优化的目标，它也是变量的线性函数。2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？目标求极小；
3、约束为等式；变量为非负。min z CTXAX bX 0例：把下列线性规划化为标准形式:max z 2x1 3x2x1 2x28x1 x21x12x1 0, x20解：令x1x3, x2 x4 x5,标准型为：minz'2x3 3（ x4 x5）X32（X4 X5） X68X3 （X4 X5） X71X3+x8 2xi 0,i3,4,5,6,7,83、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？例：参看ppt （唯一最优解、无穷多最优解、无界解、无解）线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）定理1线性规划的可行域是凸集。定理2 X是
4、线性规划基可行解的充分必要条件是 X是可行域的顶点。定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。4、如何用单纯形方法求解线性规划问题？（单纯形表）单纯形法的基本法则法则1最优性判定法则（检验数全部小于等于零时最优）法则2换入变量确定法则（谁最正谁进基）法则3换出变量确定法则（最小比值原则）法则4换基迭代运算法则min z2x15x2xi2x2X385x12x2X4204x2X512Xi，X2，X3，X4, X50X1X2X3X4X5RHSz250000X3121008X45201020X50400112z2000-5/4-15X31010-1/22X4
5、5001-1/214X201001/43z00-20-1/4-19X11010-1/22X400-5124X201001/43最优解 X*= (2, 3, 0, 4, 0) T, z*=-2 X2-5 X3=-19。5、如何确定初始可行基或如何求初始基本可行解？(两阶段方 法)例求下列LP问题的最优解min z 3x1X2X3x1 2x2X3114x1 x22x332x1X31Xl,X2,X30用两阶段法来求解它的第一阶段是先解辅助问题：min g x6 x7x1 2x2 x3 x4114x1 x2 2x3X5X632XiX3X71xj| ,X70X1X2X3X4X5X6X7RHSg00000
6、-1-10X41-21100011X6-4120-1103X7-20100011g-6130-1004X41-21100011X6-4120-1103X7-20100011g0100-10-31X43-20100-110X60100-11-21X3-20100011g00000-1-10X43001-22-512X20100-11-21X3-20100011第二阶段:X1X2X3X4X5RHSz-311000X43001-212X20100-11X3-201001z-10001-2X43001-212X20100-11X3-201001原问题无界。6、如何写出原问题的对偶问题？如果已知原问题的
7、最优解，如何求解对偶问题的最优解？minT c xmaxbTws.t.aTxbi i1,1II,ps.t.wi0aT xbi ip训mwi0Xj0 j1,1llqA：wCjXj0 jq1,nA：wCj例 写出下面线性规划问题的对偶问题min z 2x13x25x3x4x1x23x3x452x12x34x44x2x3x46X1 ,x2, x3ON0解：原问题的对偶问题为：max y 5 w 14 w 26 w 3w 12 w 22w 1w 333 w 12 w 2w 35w 14 w 2w 31w 1 , w2 0,w 307、对偶单纯形方法适合解决什么样的问题？如何求解?例：6 x2 x3 x
8、425x12x2X3Xi, X2, X3, X4, x5X510对偶单纯形法的基本法则 法则1最优性判定法则（检验数全部小于等于零时最优）法则2换出变量确定法则（谁最负谁出基）法则3换入变量确定法则（最小比值原则）法则4换基迭代运算法则X1X2X3X4X5RHSz-15-24-5000X40卜6-110-2X5-5-2-101-1z-150-1-408X2011/6-1/601/3X5-50-2/3-1/31-1/3z-15/200-7/2-3/217/2X2-5/410-1/41/41/4X315/2011/2-3/21/2写出对偶问题并求解？（利用互补松紧条件）8、对于已经求解的一个线性规
9、划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？例：线性规划max z 5x1 4x2x1 3x2902x1 x280x1x2 45x1 , x20已知最优表:X1X2X3X4X5RHSz000-1-3-215X30012-525X11001-135X2010-1210(1 )确定X2的系数C2的变化范围，使原最优解保持最优;(2 )若c2=6，求新的最优计划。解(1)将上表中的第0行重新计算检验数，得到:X1X2X3X4X5RHSz5C20000X30012-525X11001-135X2010-1210z000C2 55 2c2-175 -10C2
10、X30012-525X11001-135X2010-1210令 C2 5<0,5 2c2<0，解得 5/2 <c2<5，即当 C2在区间5/2 ,5中变化时，最优解X*= (35 , 10 , 25 , 0 , 0) T保持不变。(2)当C2=6时，C2 5=1>0，原最优解失去最优性，在表中修改第0行后，用单纯形法容易求得新的最优表如下：X1X2X3X4X5RHSz0001-7-235X30012-525X11001-135X2010-1210z00-1/20-9/2-495/2X4001/21-5/225/2X110-1/203/245/2X2011/20-1
11、/245/2故新的最优解为 xi*=45/2 ,X2*=45/2 , X4*=25/2 , X3*= X5*=0 ,最优值z*=495/2 ,例 对于上例中的线性规划作下列分析：(1) b3在什么范围内变化，原最优基不变?(2)若b3=55，求出新的最优解。解 原最优基为B= (P3, Pi, P2),由表2-6可得:12-5B；=0110-129012-590250-5b 3(1 )由 B 1 80=01180 =:80 b3>0bs0-12b380 2b3解得40 <b3<50 ,即当b3 40 , 50时，最优基B不变，最优解为:*X3250-5b3x； = 80 b3
12、, X4*=X5*=0 , z*=5 x(80 b3) +4 x( x280 2b380+2 b3) =80+3 b3(2)当 b3=55 时，250-5b 32580 ba = 25,以它代替表的b列，用对偶单纯形法继续求80 2bs30解X1X2X3X4X5RHSz000-1-3-245X30012-5-25X11001-125X2010-1230z00-3/5-11/50-230X500-1/5-2/515X110-1/53/5030X2012/5-1/5020故新的最优解为 xi*=30 , X2*=20 , X5*=5 , X3*= X4*=0，最优值 z*=230。整数线性规划0-
13、1规划如何建立整数线性规划的数学模型？如何用图解法求解两个变量的整数线性规划问题? 割平面方法的基本思想？如何用割平面方法求解整数线性规划 问题？分支定界方法的基本思想？如何用分支定界方法求解整数线性 规划问题？如何建立0-1规划问题的数学模型？如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？1、如何建立整数线性规划的数学模型？2、如何用图解法求解两个变量的整数线性规划问题？3、割平面方法的基本思想？如何用割平面方法求解整数线性规划问题?例考虑纯整数规划问题引入松弛变量S1后得:1 13 X3 3X4 + si =maxzX1X22x1X264x15x220X10, X20且为整数解 先不
14、考虑整数条件，求得其松弛问题的最优单纯形表为:X1X2X3X4RHSz00-1/6-1/6-13/3X1105/6-1/65/3X201-2/31/38/31 1 2由第二行可以生成割平面： 3 X3 + - X4>= 将此约束条件加到表中继续求解如下:X1X2X3X4S1RHSz00-1/6-1/60-13/3X1105/6-1/605/3X201-2/31/308/3S100-1/3-1/31-2/3z0000-1/2-4X1100-15/20X20101-24X30011-32所以原问题的最优解为：X1*=0 , X2*=4，最优值z*=4 。分支定界方法的基本思想？如何用分支定界
15、方法求解整数线性规划问题?例求解下面整数规划max z3x1 2x29140 且为整数值X23 x 20, x 22 x 12 x 1Xi如何建立0-1规划问题的数学模型?6、如何用隐枚举法求解 0-1规划和匈牙利法求解指派问题?例 max z 5x1 4x2 3x3Xi3x22x352x17x23X352x2X325x13x22x37Xj0或1j=1,2,35x14x2 3x34(X1 ,X2 , X3)满足条件？满足所有条件？z值(0 ,0,0)XX(0,0,1)XX(0,1 ,0)V4(0,1 ,1)VVVX(1,0,0)VVXX(1,0,1)VVVVVV8(1,1,0)VVVVVV9(
16、1,1,1)VXX动态规划了解基本概念（如多阶段决策问题、阶段、策略）；了解最优性原理；如何用动态规划方法求解最短路问题？（图上作业、公式求解）如何用动态规划方法求解旅行售货员问题？如何求解多阶段的资源分配问题？网络分析了解图的基本概念（如无向图、有向图、点、边、关联、邻接、 次、关联矩阵、邻接矩阵、握手定理）；树，支撑树，如何找最小树？（破圈法、避圈法、反圈法；）最短路问题？（图上标号法、列表法）最大流问题？（找增广路）1、树，支撑树，如何找最小树？（破圈法、避圈法、反圈法；） 例 设树有7条边，则它有（8 ）个结点；例 一个由3个分支构成的森林，如果有15个结点，则该森林至少 有（12 ）
17、条边。例一棵树T有5个度为2的结点，3个度为3的结点，4个度为4 的结点，2个度为5的结点，其余均是度为1的结点，问T有几个 度为1的结点？解设T有x个度为1的结点，则有5 2+3 3+4 4+2 5+x = 2mm = n 5+3+4+2+x = n解以上三个方程得x = 19例：公园路径系统见下图，S为入口，T为出口，A、B、C、D、 E为5个景点。现安装电话线连接各景点，则最小线路安装是什么？ 如果某游客刚进入入口就急需从出口离开， 那么该游客应该如何走最 快？2、最短路问题？（图上标号法、列表法）3、最大流问题？（找增广路）从甲地到乙地的公路网纵横交错， 每天每条路上的通车量有上限.从
18、甲地到乙地的每天最多能通车多少辆？排队论了解排队论模型的基本概念和模型。决策分析了解决策分析的基本概念；（状态集、决策集、报酬函数：基本 要素；评价准则）会建立决策分析问题的数学模型；（决策表、决策树）如何求解不确定型决策分析问题；（乐观法；悲观法；乐观系数法；后悔值法；等可能法）如何求解风险型决策分析问题；（最大可能法；期望值法）效用函数的概念；会用效用函数来进行决策（期望效用值）；会计算信息的价值、完全信息的价值。对策论例A、B两人分别有1角、5分和1分的硬币各一枚。在双方互不 知道的情况下，各出一枚硬币，并规定当和为奇数时，A赢得B所出硬币；当和为偶数时，B赢得A所出硬币。据此写出对策模型， 并说明该游戏对双方是否公平合理。解局中人：A、B或记为1、2 ；策略集：S1=105，1；S2=10，5，1；10 5110-5 -1支付矩阵：H11055 ； H2-1055 =-H1 ；1011-101 1作为纯对策问题H1无解;经过简化矩阵H1 :10511051101H11055101 110110 1 1然后进行混合扩充，得到剧中人1的期望支付:求解该函数的鞍点，即:22y20xE 22x110y可得混合策略的值为：E(x ,y ) 0，因而该对策公平合理。