运筹知识点总结

线性规划1、建立线性规划的数学模型：特点：（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它也是变量的线性函数。2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？目标求极小；约束为等式；变量为非负。例：把下列线性规划化为标准形式： 解：令标准型为：3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？例：参看ppt（唯一最优解、无穷多最优解、无界解、无解）线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）定理1线性规划的可行域是凸集。定理2X是线性规划基可行解的充分必要条件是X是可行域的顶点。定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。4、如何用单纯形方法求解线性规划问题？（单纯形表）单纯形法的基本法则法则1最优性判定法则（检验数全部小于等于零时最优）法则2换入变量确定法则（谁最正谁进基）法则3换出变量确定法则（最小比值原则）法则4换基迭代运算法则x1x2x3x4x5RHSz250000x3x4x515022[4]10001000182012z2000-5/4-15x3x4x2[1]50001100010-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-2101211000-100100011131g-6130-1004x4x6x71-4-2-21012[1]1000-100100011131g0100-10-31x4x6x330-2-2[1]00011000-10010-1-211011g00000-1-10x4x2x330-2010001100-2-10210-5-211211第二阶段:x1x2x3x4x5RHSz-311000x4x2x330-2010001100-2-101211z-10001-2x4x2x330-2010001100-2-101211原问题无界。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写出对偶问题并求解？（利用互补松紧条件）8、对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？例：线性规划 已知最优表：x1x2x3x4x5RHSz000-1-3-215x3x1x201000110021-1-5-12253510（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。解（1）将上表中的第0行重新计算检验数，得到：x1x2x3x4x5RHSz5c20000x3x1x201000110021-1-5-12253510z000c2－55－2c-175-10cx3x1x201000110021-1-5-12253510 令c2－5≤0，5－2c2≤0，解得5/2≤c2≤5，即当c2在区间[5/2，5]中变化时，最优解X*=（35，10，25，0，0）T（2）当c2=6时，c2－5=1>0，原最优解失去最优性，在表中修改第0行后，用单纯形法容易求得新的最优表如下：x1x2x3x4x5RHSz0001-7-235x3x1x2010001100[2]1-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/2，例对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。解原最优基为B=（P3，P1，P2），由表2-6可得：B－1=（1）由B－1==≥0解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变，最优解为：=，x4*=x5*=0，z*=5×（80－b3）+4×（－80+2b3）=80+3b3（2）当b3=55时，=，以它代替表的b列，用对偶单纯形法继续求解。x1x2x3x4x5RHSz000-1-3-245x3x1x201000110021-1[-5]-12-252530z00-3/5-11/50-230x5x1x2010001-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规划和匈牙利法求解指派问题？如何建立整数线性规划的数学模型？如何用图解法求解两个变量的整数线性规划问题？割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？例考虑纯整数规划问题解先不考虑整数条件，求得其松弛问题的最优单纯形表为：x1x2x3x4RHSz00-1/6-1/6-13/3x1x210015/6-2/3-1/61/35/38/3由第二行可以生成割平面：x3+x4>=引入松弛变量s1后得：－x3－x4+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，最优值z*=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）××（0，0，1）××（0，1，0）√4（0，1，1）√√√×（1，0，0）√√××（1，0，1）√√√√√√8（1，1，0）√√√√√√9（1，1，1）√××网络分析树，支撑树，如何找最小树？（破圈法、避圈法、反圈法；）例设树有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=2mm=n–15+3+4+2+x=n解以上三个方程得x=19例：公园路径系统见下图，S为入口，T为出口，A、B、C、D、E为5个景点。现安装电话线连接