运筹学知识点总结

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、解：令标准型为：3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？例：参看ppt（唯一最优解、无穷多最优解、无界解、无解）线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）定理1 线性规划的可行域是凸集。定理2 X是线性规划基可行解的充分必要条件是X是可行域的顶点。定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。4、如何用单纯形方法求解线性规划问题？（单纯形表）单纯形法的基本法则法则1 最优性判定法则（检验数全部小于等于零时最优）法则2 换入变量确定法则（谁最正谁进基）法则3 换出变量确定法则（最小比值原则）法则

4、4 换基迭代运算法则x1x2x3x4x5RHSz250000x3x4x515022410001000182012z2000-5/4-15x3x4x2150001100010-1/2-1/21/42143z00-20-1/4-19x1x4x21000011-50010-1/221/4243最优解X*=（2，3，0，4，0）T，z*=-2×2-5×3=-19。5、如何确定初始可行基或如何求初始基本可行解？（两阶段方法）例 求下列LP问题的最优解用两阶段法来求解它的第一阶段是先解辅助问题：x1x2x3x4x5x6x7RHSg00000-1-10x4x6x71-4-2-210121

5、1000-100100011131g-6130-1004x4x6x71-4-2-2101211000-100100011131g0100-10-31x4x6x330-2-2100011000-10010-1-211011g00000-1-10x4x2x330-2010001100-2-10210-5-211211第二阶段:x1x2x3x4x5RHSz-311000x4x2x330-2010001100-2-101211z-10001-2x4x2x330-2010001100-2-101211 原问题无界。6、如何写出原问题的对偶问题？如果已知原问题的最优解，如何求解对偶问题的最优解？例 写出下

6、面线性规划问题的对偶问题解：原问题的对偶问题为：7、对偶单纯形方法适合解决什么样的问题？如何求解？例： 对偶单纯形法的基本法则法则1 最优性判定法则（检验数全部小于等于零时最优）法则2换出变量确定法则（谁最负谁出基）法则3换入变量确定法则（最小比值原则）法则4 换基迭代运算法则x1x2x3x4x5RHSz-15-24-5000x4x50-5-6-2-1-11001-2-1z-150-1-408x2x50-5101/6-2/3-1/6-1/3011/3-1/3z-15/200-7/2-3/217/2x2x3-5/415/21001-1/41/21/4-3/21/41/2写出对偶问题并求解？（利用

7、互补松紧条件）8、对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？例：线性规划已知最优表：x1x2x3x4x5RHSz000-1-3-215x3x1x201000110021-1-5-12253510（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。解 （1）将上表中的第0行重新计算检验数，得到：x1x2x3x4x5RHSz5c20000x3x1x201000110021-1-5-12253510z000c2552c2-175-10c2x3x1x201000110021-1-5-12253

8、510令c250，52c20，解得5/2c25，即当c2在区间5/2，5中变化时，最优解X*=（35，10，25，0，0）T保持不变。（2）当c2=6时，c25=1>0，原最优解失去最优性，在表中修改第0行后，用单纯形法容易求得新的最优表如下：x1x2x3x4x5RHSz0001-7-235x3x1x201000110021-1-5-12253510z00-1/20-9/2-495/2x4x1x20100011/2-1/21/2100-5/23/2-1/225/245/245/2故新的最优解为x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，最优值z*=495/

9、2，例 对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。解 原最优基为B=（P3，P1，P2），由表2-6可得：B1=（1）由B1=0解得40b350，即当b340，50时，最优基B不变，最优解为：=，x4*=x5*=0，z*=5×（80b3）+4×（80+2b3）=80+3b3（2）当b3=55时，=，以它代替表的b列，用对偶单纯形法继续求解。x1x2x3x4x5RHSz000-1-3-245x3x1x201000110021-1-5-12-252530z00-3/5-11/50-230x5x1x2010001

10、-1/5-1/52/5-2/53/5-1/510053020故新的最优解为x1*=30，x2*=20，x5*=5，x3*= x4*=0，最优值z*=230。整数线性规划0-1规划如何建立整数线性规划的数学模型？如何用图解法求解两个变量的整数线性规划问题？割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？如何建立0-1规划问题的数学模型？如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？1、 如何建立整数线性规划的数学模型？2、 如何用图解法求解两个变量的整数线性规划问题？3、 割平面方法的基本思想？如何用割平面方法求解

11、整数线性规划问题？例 考虑纯整数规划问题解 先不考虑整数条件，求得其松弛问题的最优单纯形表为：x1x2x3x4RHSz00-1/6-1/6-13/3x1x210015/6-2/3-1/61/35/38/3由第二行可以生成割平面：x3+x4>=引入松弛变量s1后得：x3x4+s1将此约束条件加到表中继续求解如下：x1x2x3x4s1RHSz00-1/6-1/60-13/3x1x2s11000105/6-2/3-1/3-1/61/3-1/30015/38/3-2/3z0000-1/2-4x1x2x3100010001-1115/2-2-3042所以原问题的最优解为：x1*=0，x2*=4，最

12、优值z*=4。4、 分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？例 求解下面整数规划 (P0)x1=3.25x2=2.5z(0)=14.755(P2)x1=2.5x2=3z(2)=13.5(P3)x1=3x2=2z(3)=13(P4)x1=4x2=1z(4)=14(P1)x1=3.5x2=2z(1)=14.5*×X2<=2X1>=4X1<=3X2>=35、如何建立0-1规划问题的数学模型？6、如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？例（x1，x2，x3）满 足 条 件 ？满足所有条件？z值（0，0，0）××（

13、0，0，1）××（0，1，0）4（0，1，1）×（1，0，0）××（1，0，1）8（1，1，0）9（1，1，1）××动态规划了解基本概念（如多阶段决策问题、阶段、策略）；了解最优性原理；如何用动态规划方法求解最短路问题？（图上作业、公式求解）如何用动态规划方法求解旅行售货员问题？如何求解多阶段的资源分配问题？网络分析了解图的基本概念（如无向图、有向图、点、边、关联、邻接、次、关联矩阵、邻接矩阵、握手定理）；树，支撑树，如何找最小树？（破圈法、避圈法、反圈法；）最短路问题？（图上标号法、列表法）最大流问题？（找增广路）1、 树

14、，支撑树，如何找最小树？（破圈法、避圈法、反圈法；）例 设树有7条边，则它有（8）个结点；例 一个由3个分支构成的森林，如果有15个结点，则该森林至少有（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 = 2m m = n15+3+4+2+x = n 解以上三个方程得 x = 19例： 公园路径系统见下图，S 为入口，T 为出口，A、B、C、D、E为 5 个景点。现安装电话线连接各景点，则最小

15、线路安装是什么？如果某游客刚进入入口就急需从出口离开，那么该游客应该如何走最快？2、最短路问题？（图上标号法、列表法）3、最大流问题？（找增广路）从甲地到乙地的公路网纵横交错，每天每条路上的通车量有上限. 从甲地到乙地的每天最多能通车多少辆? (甲) A F (乙) 5 6 6 7 4 4 5 1 3 B E D C 排队论了解排队论模型的基本概念和模型。决策分析了解决策分析的基本概念；（状态集、决策集、报酬函数：基本要素；评价准则）会建立决策分析问题的数学模型；（决策表、决策树）如何求解不确定型决策分析问题；（乐观法；悲观法；乐观系数法；后悔值法；等可能法）如何求解风险型决策分析问题；（最大可能法；期望值法）效用函数的概念；会用效用函数来进行决策（期望效用值）；会计算信息的价值、完全