运筹学知识点总结-标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII运筹学考试时间：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：00 18周周一周三上午8：00-11：00地点：基础楼201线性规划如何建立线性规划的数学模型；线性规划的标准形有哪些要求如何把一般的线性规划化为标准形式如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？如何用单纯形方法求解线性规划问题？如何确定初始可行基或如何求初始基本可行解（两阶段方法）如何写出一个线性规划问题的对偶问题如果已知原问题的最优解如何求解对偶问题的最优解（对偶的性质，互补松紧条件）对偶单纯形方法适合解决什么样的问题如何求解对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基如果不是，如何进一步求解1、建立线性规划的数学模型：特点：（1）每个行动方案可用一组变量（x 1，…，x n ）的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它也是变量的线性函数。

2、线性规划的标准形有哪些限制如何把一般的线性规划化为标准形式目标求极小；约束为等式；变量为非负。

min b 0T z C X AX X ==⎧⎨≥⎩例：把下列线性规划化为标准形式：121212112max 2328 1 20,0z x x x x x x x x x =++≤⎧⎪-+≥⎪⎨≤⎪⎪≤<>⎩解：令13245,,x x x x x =-=-标准型为：,3453456345738min 23()2()8 () x 1 +x 20,3,4,5,6,7,8iz x x x x x x x x x x x x i =-+--+-+=⎧⎪++--=⎪⎨-=⎪⎪≥=⎩ 3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？例：参看ppt （唯一最优解、无穷多最优解、无界解、无解） 线性规划解的性质：（基、基本解、基本可行解、凸集、顶点） 定理1 线性规划的可行域是凸集。

定理2 X 是线性规划基可行解的充分必要条件是X 是可行域的顶点。

定理3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。

4、如何用单纯形方法求解线性规划问题？（单纯形表） 单纯形法的基本法则法则1 最优性判定法则（检验数全部小于等于零时最优） 法则2 换入变量确定法则（谁最正谁进基） 法则3 换出变量确定法则（最小比值原则） 法则4 换基迭代运算法则121231242512345min 25 2 852 204 12,,,,0z x x x x x x x x x x x x x x x =--++=⎧⎪++=⎪⎨+=⎪⎪≥⎩最优解X *=（2，3，0，4，0）T ，z *=-2×2-5×3=-19。

5、如何确定初始可行基或如何求初始基本可行解（两阶段方法）例 求下列LP 问题的最优解12312312313123min 3 2114232 1,,0z x x x x x x x x x x x x x x =---+≤⎧⎪-++≥⎪⎨-+=⎪⎪≥⎩用两阶段法来求解它的第一阶段是先解辅助问题：6712341235613717min 2 1142 3 2 1,,0g x x x x x x x x x x x x x x x x =+-++=⎧⎪-++-+=⎪⎨-++=⎪⎪≥第二阶段:原问题无界。

6、如何写出原问题的对偶问题？如果已知原问题的最优解，如何求解对偶问题的最优解？例 写出下面线性规划问题的对偶问题解：原问题的对偶问题为：7、对偶单纯形方法适合解决什么样的问题如何求解 例：minmax ..1,,..01,,001,,01,,TTT i i i T i i i T j j j T j j jc x b w s t a x b i p s t w a x b i p m w x j qA w c x j q n A w c ==<>≥=+≥≥=≤<>=+=123412341342341234min 235 3 52 244 6 00z x x x x x x x x x x x x x x x ,x x ,x =+-++-+≥⎧⎪+-≤⎪⎨++=⎪⎪≥<>⎩,1231213123123123max54622332541,0,0y w w w w w w w w w w w w w w w w =-+-≤⎧⎪+≤⎪⎪--+≤-⎨⎪++=⎪≥<>⎪⎩123234123512345min 15245 6 2 52 1,,,,0z x x x x x x x x x x x x x x x =+++-=⎧⎪++-=⎨⎪≥⎩ 对偶单纯形法的基本法则法则1 最优性判定法则（检验数全部小于等于零时最优） 法则2换出变量确定法则（谁最负谁出基） 法则3换入变量确定法则（最小比值原则） 法则4 换基迭代运算法则写出对偶问题并求解？（利用互补松紧条件）8、对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基如果不是，如何进一步求解例：线性规划1212121212max 54390280 45,0z x x x x x x x x x x =++≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩已知最优表：（1）确定x 2的系数c 2的变化范围，使原最优解保持最优； （2）若c 2=6，求新的最优计划。

解 （1）将上表中的第0行重新计算检验数，得到：令c 2－5≤0，5－2c 2≤0，解得5/2≤c 2≤5，即当c 2在区间[5/2，5]中变化时，最优解X *=（35，10，25，0，0）T 保持不变。

（2）当c 2=6时，c 2－5=1>0，原最优解失去最优性，在表中修改第0行后，用单纯形法容易求得新的最优表如下：故新的最优解为x 1*=45/2，x 2*=45/2，x 4*=25/2，x 3*= x 5*=0，最优值z *=495/2，例 对于上例中的线性规划作下列分析： （1）b 3在什么范围内变化，原最优基不变？（2）若b 3=55，求出新的最优解。

解 原最优基为B =（P 3，P 1，P 2），由表2-6可得：B －1= 1 2 -50 1 10 -1 2⎛⎫⎪- ⎪ ⎪⎝⎭（1）由B －139080b ⎛⎫ ⎪ ⎪ ⎪⎝⎭= 1 2 -50 1 10 -1 2⎛⎫⎪- ⎪ ⎪⎝⎭39080b ⎛⎫ ⎪ ⎪ ⎪⎝⎭=333250-5b 80b 802b ⎛⎫⎪-⎪ ⎪-+⎝⎭≥0 解得40≤b 3≤50，即当b 3∈[40，50]时，最优基B 不变，最优解为：*3*1*2x x x ⎛⎫ ⎪ ⎪ ⎪⎝⎭=333250-5b 80b 802b ⎛⎫ ⎪- ⎪ ⎪-+⎝⎭，x 4*=x 5*=0，z *=5×（80－b 3）+4×（－80+2b 3）=80+3b 3 （2）当b 3=55时，333250-5b 80b 802b ⎛⎫ ⎪- ⎪ ⎪-+⎝⎭=252530-⎛⎫ ⎪ ⎪ ⎪⎝⎭，以它代替表的b 列，用对偶单纯形法继续求解。

故新的最优解为x 1*=30，x 2*=20，x 5*=5，x 3*= x 4*=0，最优值z *=230。

整数线性规划0-1规划如何建立整数线性规划的数学模型如何用图解法求解两个变量的整数线性规划问题？割平面方法的基本思想如何用割平面方法求解整数线性规划问题分支定界方法的基本思想如何用分支定界方法求解整数线性规划问题如何建立0-1规划问题的数学模型？如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？1、 如何建立整数线性规划的数学模型？2、 如何用图解法求解两个变量的整数线性规划问题？3、 割平面方法的基本思想如何用割平面方法求解整数线性规划问题 4、例 考虑纯整数规划问题12max z x x =+1212122645200,0x x x x x x +≤⎧⎪+≤⎨⎪≥≥⎩且为整数 解 先不考虑整数条件，求得其松弛问题的最优单纯形表为：由第二行可以生成割平面：13x 3 + 13x 4>=23引入松弛变量s 1后得：－13 x 3 － 13 x4 + s 1＝－23将此约束条件加到表中继续求解如下：x 1 x 2 x 3 x 4 s 1 RHS z0 0 -1/6 -1/6 0 -13/3 x 1 x 2 s 1 1 0 0 0 1 0 5/6 -2/3 [-1/3] -1/6 1/3 -1/3 0 0 1 5/3 8/3 -2/3 z 0 0 0 0 -1/2 -4 x 1 x 2 x 31 0 0 0 1 0 0 0 1 -1 1 1 5/2 -2 -3 04 2所以原问题的最优解为：x 1*=0，x 2*=4，最优值z *=4。

5、 分支定界方法的基本思想如何用分支定界方法求解整数线性规划问题 6、例 求解下面整数规划12max 32z x x =+1212122923140,0x x x x x x +≤⎧⎪+≤⎨⎪≥≥⎩且为整数值5、如何建立0-1规划问题的数学模型？6、如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？例 123max 543z x x x =++()1231232312332527352253270,3j x x x x x x x x x x x x j ⎧++≤⎪++≥⎪⎪+≤⎨⎪-+≤⎪⎪=⎩或1=1,2 ①②③④1235434x x x ++≥ ◎(P 0)x 1=3.25 x 2=2.5 z (0)=14.755(P 2)x 1=2.5x 2=3 z (2)=13.5(P 3)x 1=3 x 2=2 z (3)=13 (P 4)x 1=4 x 2=1 z (4)=14 (P 1)x 1=3.5 x 2=2 z (1)=14.5*×X 2<=2 X 1>=4X 1<=3 X 2>=3动态规划了解基本概念（如多阶段决策问题、阶段、策略）；了解最优性原理；如何用动态规划方法求解最短路问题（图上作业、公式求解）如何用动态规划方法求解旅行售货员问题？如何求解多阶段的资源分配问题？网络分析了解图的基本概念（如无向图、有向图、点、边、关联、邻接、次、关联矩阵、邻接矩阵、握手定理）；树，支撑树，如何找最小树（破圈法、避圈法、反圈法；）最短路问题（图上标号法、列表法）最大流问题（找增广路）1、树，支撑树，如何找最小树（破圈法、避圈法、反圈法；）例设树有7条边，则它有（8）个结点；例一个由3个分支构成的森林，如果有15个结点，则该森林至少有（12）条边。