《运筹学知识点总结》由会员分享，可在线阅读，更多相关《运筹学知识点总结（31页珍藏版）》请在金锄头文库上搜索。
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）每个行方案可用一量（X,，X）的表示，些量一般取非；1n（ 2 ） 量的 化要受某些限制， 些限制条件用一些 性等式或不等 式表示；（ 3 ）有一个需要 化的目 ，它也是 量的 性函数。2、线性规划的标准形有哪些限制怎样把一般的线性规划化为标准形式目 求极小； 束 等式； 量 非
3、 。min z C T XAX bX0例：把以下 性 划化准形式：maXz 2X1 3 X 2X12 X28X1X2 1X12X10, X20解：令X1X3 , X2X4 X5 , 准型minz,2X 3 3(X4 X5 )X32( X4 X5 )X6 8X3( X4 X 5 )X 7 1X3+X 28xi 0,i 3,4,5,6,7,83、怎样用图解法求解两个变量的线性规划问题由图解法总结出线性规划问题的解有哪些性质例：参看ppt （独一最优解、无量多最优解、无界解、无解）线性规划解的性质：（基、基本解、基本可行解、凸集、极点）定理1线性规划的可行域是凸集。定理2 X是线性规划基可行解的充足
4、必需条件是x是可行域的极点。定理3线性规划假如有可行解，则必定有基可行解；假如有最优解， 则必定有基可行解是最优解。4、怎样用纯真形方法求解线性规划问题（纯真形表）纯真形法的基本法例法例1最优性判断法例（查验数所有小于等于零时最优）法例2换入变量确立法例（谁最正谁进基）法例3换出变量确立法例（最小比值原则）法例4换基迭代运算法例min z2X15x2x12x2X385 X2 X2X4204 X2X512X1 ,X2，X3，X4，X50X1X2X3X4X5RHSz250000X3121008x45201020x50400112z2000-5/4-15x31010-1/22x45001-1/214
5、x201001/43z00-20-1/4-19x11010-1/22x400-5124x201001/43最优解 X*= (2, 3, 0, 4, 0) T, z*=-2 X2-5 X3=-19。5、怎样确立初始可行基或怎样求初始基本可行解 （两阶段方法）例求以下LP问题的最优解I3x1 x2x3x12 x2x34Xx22x32x1x,1130，X3xi，X2用两阶段法来求解 它的第一阶段是先解协助问题:mmg x6 x7xi2x2x4114X1 x22X3X52x1x71x1 ,L , x70x1x2x3x4x5x6x7RHSg00000-1-10x41-21100011x6-4120-11
6、03x7-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-201001min cT xs.t .aiTxb.i i1,L , pa xTi入b.iip 1,L , mxj0j1,L
7、, qxj0jq 1,L , n求解对偶问题的最优解s.t .例写出下边线性规划问题的对偶问题maxbT ww.iw.iwwmin z 2 x 1 3x?5x3x1 x23x32X2x34x4x2x1 , x2,x30, x4原问题无界。6、怎样写出原问题的对偶问题假如已知原问题的最优解，怎样解：原问题的对偶问题为:maxy5 w 14 w 26 w 3w 12 w 22w 1w333 w 12 w 2w35w 14 w 2w31w 1 , w2w307、对偶纯真形方法合适解决什么样的问题怎样求解例:minz 15 x 124 x 2 5 x 36 x 2 x 3 x 425X 2 x2 x
8、3X5 1x1 , x2 , x3 , x4 , x5 0对偶纯真形法的基本法例法例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 5 X 4x?X13x2902 X1X280X1X245X1 ,X2 0已知最优表:X1X2X3X4X5RHSz000-1-3-215X30012-525X11001-135X2010-1210(1)确立X的系数c的变化范围，使原最优解保持最优;2 2(2 )若c =6，求新的最优计划。2解(1)将上表中的第0行从头计算查验数，获得:x1x2x3x4x5RHSz5c20000x30012-525x11001-135x2010-1210z000c 525 2c2-175 -10 c2x3001
10、2-525x11001-135x2010-1210令 c 5 WO, 5 2c WO，解得 5/2 W c W5，即当 c 在区间5/2 ,2 2 2 25中变化时，最优解X*= (35 , 10, 25 , 0, 0) t保持不变。(2)当c =6时，c 5=10，原最优解失掉最优性，在表中改2 2正第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故新的最优解为X =45/2 , x =45/2 , x =25/2 , x = x =0，最优12435值 z* =495/2 ,例 关于上例中的线性规划作以下剖析:(1)b在什么范围内变化，原最优基不变3(2)若b =55，求出新的最优解。3解原最优基为B
