运筹学知识点总结.docx

运筹学考试时间： 2009-1-410:00-12:00考试地址： 金融1、2：（二）201，会计1、2：（二） 106人资1、2：（二）203，工商1、2：（二） 205林经1、2：（二）306 答疑时间： 17周周二周四上午8:00-11:00 18周周一周三上午8:00-11:00地址：基础楼201 线性规划怎样成立线性规划的数学模型；线性规划的标准形有哪些要求怎样把一般的线性规划化为标准形式怎样用图解法求解两个变量的线性规划问题由图解法总结出线性规划问题的解有哪些性质怎样用纯真形方法求解线性规划问题怎样确立初始可行基或怎样求初始基本可行解（两阶段方法）怎样写出一个线性规划问题的对偶问题假如已知原问题的最优解怎样求解对偶问题的最优解（对偶的性质，互补松紧条件）对偶纯真形方法合适解决什么样的问题怎样求解关于已经求解的一个线性规划问题假如改变价值向量和右端向量原最优解/基能否还是最优解/基假如不是，怎样进一步求解1、成立线性规划的数学模型: 特色: 每个行方案可用一量(X1,???,%)的表示，些量一般取非； 量的化要受某些限制，些限制条件用一些性等式或不等式表示；有一个需要化的目，它也是量的性函数。 2、线性规划的标准形有哪些限制怎样把一般的线性规划化为标准形式目求极小；束等式；量非。 minzctX AXb X0 例:把以下性划化准形式: 例:把以下性划化 准形式: z2x z2xi2x2 max x1 2 x10,x 2 0 解:令 x1x3， x2x4 x5 ,准型： minz，2x 33(x4 x5) x32(x4 x5)x6 8 x3(x4 x5)x7 1 x3 +x 2 1 X1X18x2 xi0,i3,4,5,6,7,8 3、怎样用图解法求解两个变量的线性规划问题由图解法总结出 线性规划问题的解有哪些性质 例：参看ppt（独一最优解、无量多最优解、无界解、无解） 线性规划解的性质：（基、基本解、基本可行解、凸集、极点） 定理1线性规划的可行域是凸集。 定理2X是线性规划基可行解的充足必需条件是x是可行域的极点。 定理3线性规划假如有可行解，则必定有基可行解；假如有最优解， 则必定有基可行解是最优解。 4、怎样用纯真形方法求解线性规划问题（纯真形表） 纯真形法的基本法例 法例1最优性判断法例（查验数所有小于等于零时最优） 法例2换入变量确立法例（谁最正谁进基） 法例3换出变量确立法例（最小比值原则） 法例4换基迭代运算法例 minz 2X] 5x2 x1 2x2 x3 8 5Xi 2x2 x420 4x2 x512 X1， x2,x3 x4x5 0 X 1 X 2 X 3 X 4 X 5 RHS z 2 5 0 0 0 0 X 3 1 2 1 0 0 8  X4 X 5 5 0 2 [4] 0 0 1 0 0 1 20 12 z 2 0 0 0 -5/4 -15 X 3 [1] 0 1 0 -1/2 2 X 4 5 0 0 1 -1/2 14 X 2 0 1 0 0 1/4 3 z 0 0 -2 0 -1/4 -19 X 1 1 0 1 0 -1/2 2 X 4 0 0 -5 1 2 4 X 2 0 1 0 0 1/4 3 最优解X*=(2,3,0,4,0)T,z*=-2X2-5X3=-19。 5、怎样确立初始可行基或怎样求初始基本可行解（两阶段方法） 例求以下LP问题的最优解 minz 3X1X2 X3 X1 2x2 J X3 11 4x1 X2 2x3 3 2x1 X3 1 X],x2,x30 用两阶段法来求解它的第一阶段是先解协助问题: mingx6x7 x1 2x2 J x3x4 11 4x1 x2 2x3x5x 63 2x1 x3 x71 x1,L ,x7 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 RHS g 0 0 0 0 0 -1 -1 0 x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 1 0 0 0 1 1 g -6 1 3 0 -1 0 0 4 x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 [1] 0 0 0 1 1 g 0 1 0 0 -1 0 -3 1 x 4 3 -2 0 1 0 0 -1 10 x 6 0 [1] 0 0 -1 1 -2 1 x 3 -2 0 1 0 0 0 1 1 g 0 0 0 0 0 -1 -1 0 x 4 3 0 0 1 -2 2 -5 12 x 2 0 1 0 0 -1 1 -2 1 x 3 -2 0 1 0 0 0 1 1 第二阶段:  x 1 x 2 x 3 x 4 x 5 RHS z -3 1 1 0 0 0