运筹学知识点总结

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、 线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？目标求极小；约束为等式；变量为非负。m

3、in z CTXAX bX0例：把下列线性规划化为标准形式：maX z 2X1 3X2X1 2X28X1X21X12X1 0, X20解：令X1X3, X2X4 x5，标准型为：minz,2X3 3(X4 X5)X3 2(X4 X5 ) X6 8X3 (X4 X5) X7 1X3+X8 2Xi 0,i 3,4,5,6,7,83、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？例：参看ppt （唯一最优解、无穷多最优解、无界解、无解）线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）定理1线性规划的可行域是凸集。定理2 X是线性规划基可行解的充分必要条件是

4、 X是可行域的顶点。定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。4、如何用单纯形方法求解线性规划问题？（单纯形表）单纯形法的基本法则法则1最优性判定法则（检验数全部小于等于零时最优）法则2换入变量确定法则（谁最正谁进基）法则3换出变量确定法则（最小比值原则）法则4换基迭代运算法则min z 2x1 5x2x1 2x2 x385x1 2x2x4204x2x5 12x1 , x2 , x3, x4, x5x1x2乂3x4乂5RHSz250000x3121008x45201020乂50400112z2000-5/4-15x31010-1/22x45001-1

5、/214乂201001/43z00-20-1/4-19x11010-1/22x400-5124x201001/43最优解 X*=(2, 3, 0, 4, 0) z*=-2 X2-5 X3=-19。5、如何确定初始可行基或如何求初始基本可行解？(两阶段方法) 例求下列LP问题的最优解min z 3x1 x2 x3x1 2x2 x3 114x1 x22x12x33x31用两阶段法来求解它的第一阶段是先解辅助问题:min g x6 x7Xi 4X1 2X1 X1,L2x2x2 :,X7 0X3X411312x33X3)X5X6X7XiX2X3X4X5X6X7RHSg00000-1-10X41-211

6、00011X6-4120-1103X7-20100011g-6130-1004X41-21100011X6-4120-1103X7-20100011g0100-10-31X43-20100-110X60100-11-21X3-20100011g00000-1-10X43001-22-512X20100-11-21X3-20100011第二阶段:xix2x3x4x5RHSz-311000x43001-212x20100-11x3-201001z-10001-2x43001-212x20100-11x3-201001原问题无界。6、如何写出原问题的对偶问题？如果已知原问题的最优解，如何求解对偶问题

7、的最优解？max bTws.t.wi0wi 0AT w cj TAj w cj min c xs.t.aTxbii1,L , paT xbiip 1,L,mXj 0 j 1,L ,qXj0jq 1,L,n例 写出下面线性规划问题的对偶问题min z 2x1 3x2 5x3 x4xix23x3x42x12x3 4x4x2x3x4x1, x2,x30, x40解：原问题的对偶问题为:maxy5 w 14 w 26 w 3w 12 w 22w 1w 333 w12 w2w 35w 14 w2w 31w J,w 20, w 307、对偶单纯形方法适合解决什么样的问题？如何求解?例:min z 15x1

8、24x2 5x36 x2 x3 x425x12x2x3x51x1, x2, x3, x4, x5对偶单纯形法的基本法则 法则1最优性判定法则（检验数全部小于等于零时最优）法则2换出变量确定法则（谁最负谁出基）法则3换入变量确定法则（最小比值原则）法则4换基迭代运算法则x1乂2乂3x4XsRHSz-15-24-5000乂40-6-110-2乂5-5-2-101-1z-150-1-408x2011/6-1/601/3乂5-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写出对偶问题并求解？(利用互补松紧条

9、件)8、对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求 解？例：线性规划max z 5x1 4x2x1 3x2902x1 x280x1x2 45x1, x20已知最优表:x1x2x3x4乂5RHSz000-1-3-215乂30012-525x11001-135x2010-1210(1)确定x2的系数C2的变化范围，使原最优解保持最优;(2)若C2=6,求新的最优计划。解(1)将上表中的第0行重新计算检验数，得到:XiX2X3X4X5RHSz5C20000X30012-525Xi1001-135X2010-1210z000C2 55

10、 2c2-175-10C2X30012-525Xi1001-135X2010-1210令 C25W0,52C2W0,解得 5/2 WC2W5,即当 C2在区间5/2 ,T5中变化时，最优解 X= (35, 10, 25, 0, 0)保持不变(2)当C2=6时，C25=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/245/2故新

11、的最优解为 x:=45/2, x；=45/2, X4*=25/2 , x；= x；=0,最优值 z*=495/2 ,例 对于上例中的线性规划作下列分析：(1) b3在什么范围内变化，原最优基不变?(2)若h=55,求出新的最优解解原最优基为B= (P3, Pi, P2),由表2-6可得:12-5ET1=0 i 10-12901(1)由 B 1 80 = 0b302-511-1290250-5b380 = 80 b3>0b380 2b3解得40W b3<50,即当b3640, 50时，最优基B不变，最优解为: *X3250-5b 3*x1 = 80 b3, X4=X5=0, z=5X

12、 (80b3)+4X (80+2b3)*x280 2b3=80+3b3(2)当 b3=55时,250-5b 32580 b3= 25，以它代替表的b歹U,用对偶单纯形法继续求解80 2b330X1X2X3X4X5RHSz000-1-3-245X30012-5-25X11001-125X2010-1230z00-3/5-11/50-230X500-1/5-2/515Xi10-1/53/5030X2012/5-1/5020故新的最优解为 Xi =30, X2 =20, X5 =5, X3 = X4 =0,最优值 z =230。整数线性规划0-1规划如何建立整数线性规划的数学模型？如何用图解法求解两

13、个变量的整数线性规划问题？割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？如何建立0-1 规划问题的数学模型？如何用隐枚举法求解0-1 规划和匈牙利法求解指派问题？1、 如何建立整数线性规划的数学模型？2、 如何用图解法求解两个变量的整数线性规划问题？3、 割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？例考虑纯整数规划问题max z x1 x22x1 x2 6 4x1 5x220x10, x20且为整数解 先不考虑整数条件，求得其松弛问题的最优单纯形表为:x1x2x3x4RHSz00-1/6-1/6-13

14、/3x1105/6-1/65/3x201-2/31/38/3由第二行可以生成割平面： 1 x3 + 1 x4> = 1 333引入松弛变量S1后得：一）x3 x4 + S1 = - |333将此约束条件加到表中继续求解如下：x1x2x3x4s1RHSz00-1/6-1/60-13/3x1105/6-1/605/3x201-2/31/308/3S100-1/3-1/31-2/3z0000-1/2-4xi100-15/20x20101-24x30011-32所以原问题的最优解为：Xi =0, X2=4,最优值z =4。4、 分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？例求

15、解下面整数规划max z 3x1 2x22 x 1x 292 Xi3x214x10, x 20 且为整数值5、如何建立0-1规划问题的数学模型?6、如何用隐枚举法求解0-1规划和匈牙利法求解指派问题?max z 5x1 4x2 3x3Xi3 x2 2X352x1 7x22x23x35x325x13x2 2x3xj 0 或 1 j=1,2,35x14x9 3x34I23(xi, 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)VV

16、VVVV9(1, 1, 1)VXX动态规划了解基本概念（如多阶段决策问题、阶段、策略） ；了解最优性原理；如何用动态规划方法求解最短路问题？（图上作业、公式求解）如何用动态规划方法求解旅行售货员问题？如何求解多阶段的资源分配问题？网络分析了解图的基本概念（如无向图、有向图、点、边、关联、邻接、次、关联矩阵、邻接矩阵、握手定理）；树，支撑树，如何找最小树？（破圈法、避圈法、反圈法；）最短路问题？（图上标号法、列表法）最大流问题？（找增广路）1、 树， 支撑树， 如何找最小树？（破圈法、避圈法、 反圈法； ） 例设树有7条边，则它有（8）个结点；例 一个由3个分支构成的森林，如果有15个结点，则该

17、森林至少 有（12）条边。例 一棵树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 - 15+3+4+2+x = n解以上三个方程得x = 19例：公园路径系统见下图，S为入口，T为出口，A、B、C、D E 为5个景点。现安装电话线连接各景点，则最小线路安装是什么？ 如果某游客刚进入入口就急需从出口离开， 那么该游客应该如何走最 快？2、最短路问题？（图上标号法、列表法）3、最大流问题？（找增广路）从甲地到乙地的公路网纵横交错，每天

18、每条路上的通车量有上限.从 甲地到乙地的每天最多能通车多少辆 ？5（甲）A Q（乙）排队论了解排队论模型的基本概念和模型。决策分析了解决策分析的基本概念；（状态集、决策集、报酬函数：基本要素；评价准则）会建立决策分析问题的数学模型；（决策表、决策树）如何求解不确定型决策分析问题；（乐观法；悲观法；乐观系数法；后悔值法；等可能法）如何求解风险型决策分析问题；（最大可能法；期望值法）效用函数的概念；会用效用函数来进行决策（期望效用值）；会计算信息的价值、完全信息的价值。对策论例 A 、 B 两人分别有1 角、 5 分和1 分的硬币各一枚。在双方互不知道的情况下，各出一枚硬币，并规定当和为奇数时， A赢得B所出硬币；当和为偶数时，B赢得A所出硬币。据此写出对策