运筹学知识点总结

1运筹学考试时间：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：0018周周一周三上午8：00-11：00地点：基础楼2012线性规划如何建立线性规划的数学模型；线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？如何用单纯形方法求解线性规划问题？如何确定初始可行基或如何求初始基本可行解？（两阶段方法）如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件）对偶单纯形方法适合解决什么样的问题？如何求解？对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？31、建立线性规划的数学模型：特点：（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它也是变量的线性函数。2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？目标求极小；约束为等式；变量为非负。minb0TzCXAXX例：把下列线性规划化为标准形式：121212112max2328120,0zxxxxxxxxx解：令13245,,xxxxx标准型为：,3453456345738min23()2()8()x1+x20,3,4,5,6,7,8izxxxxxxxxxxxxi43、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？例：参看ppt（唯一最优解、无穷多最优解、无界解、无解）线性规划解的性质：（基、基本解、基本可行解、凸集、顶点）定理1线性规划的可行域是凸集。定理2X是线性规划基可行解的充分必要条件是X是可行域的顶点。定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。4、如何用单纯形方法求解线性规划问题？（单纯形表）单纯形法的基本法则法则1最优性判定法则（检验数全部小于等于零时最优）法则2换入变量确定法则（谁最正谁进基）法则3换出变量确定法则（最小比值原则）法则4换基迭代运算法则121231242512345min25285220412,,,,0zxxxxxxxxxxxxxxxx1x2x3x4x5RHSz2500005x3x4x515022[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问题的最优解12312312313123min321142321,,0zxxxxxxxxxxxxxx用两阶段法来求解它的第一阶段是先解辅助问题：66712341235613717min21142321,,0gxxxxxxxxxxxxxxxx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第二阶段:7x1x2x3x4x5RHSz-311000x4x2x330-2010001100-2-101211z-10001-2x4x2x330-2010001100-2-101211原问题无界。6、如何写出原问题的对偶问题？如果已知原问题的最优解，如何求解对偶问题的最优解？例写出下面线性规划问题的对偶问题minmax..1,,..01,,001,,01,,TTTiiiTiiiTjjjTjjjcxbwstaxbipstwaxbipmwxjqAwcxjqnAwc123412341342341234min235352244600zxxxxxxxxxxxxxxx,xx,x,8解：原问题的对偶问题为：7、对偶单纯形方法适合解决什么样的问题？如何求解？例：123234123512345min1524562521,,,,0zxxxxxxxxxxxxxxx对偶单纯形法的基本法则法则1最优性判定法则（检验数全部小于等于零时最优）法则2换出变量确定法则（谁最负谁出基）法则3换入变量确定法则（最小比值原则）法则4换基迭代运算法则x1x2x3x4x5RHSz-15-24-5000x4x50-5[-6]-2-1-11001-2-1z-150-1-408x2011/6-1/601/31231213123123123max54622332541,0,0y9x5-50[-2/3]-1/31-1/3z-15/200-7/2-3/217/2x2x3-5/415/21001-1/41/21/4-3/21/41/2写出对偶问题并求解？（利用互补松紧条件）8、对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？例：线性规划1212121212max5439028045,0zxxxxxxxxxx已知最优表：x1x2x3x4x5RHSz000-1-3-215x3x1x201000110021-1-5-12253510（1）确定x2的系数c2的变化范围，使原最优解保持最优；（2）若c2=6，求新的最优计划。10解（1）将上表中的第0行重新计算检验数，得到：x1x2x3x4x5RHSz5c20000x3x1x201000110021-1-5-12253510z000c2－55－2c2-175-10c2x3x1x201000110021-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=10，原最优解失去最优性，在表中修改第0行后，用单纯形法容易求得新的最优表如下：x1x2x3x4x5RHSz0001-7-235x3x1x2010001100[2]1-1-5-12253510z00-1/20-9/2-495/2x4x101001/2-1/210-5/23/225/245/211x2011/20-1/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=12-50110-12（1）由B－139080b=12-50110-1239080b=333250-5b80b802b≥0解得40≤b3≤50，即当b3∈[40，50]时，最优基B不变，最优解为：*3*1*2xxx=333250-5b80b802b，x4*=x5*=0，z*=5×（80－b3）+4×（－80+2b3）=80+3b3（2）当b3=55时，333250-5b80b802b=252530，以它代替表的b列，用对偶单纯形法继续求解。x1x2x3x4x5RHSz000-1-3-245x30012[-5]-2512x1x21001001-1-122530z00-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。13整数线性规划0-1规划如何建立整数线性规划的数学模型？如何用图解法求解两个变量的整数线性规划问题？割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？如何建立0-1规划问题的数学模型？如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？141、如何建立整数线性规划的数学模型？2、如何用图解法求解两个变量的整数线性规划问题？3、割平面方法的基本思想？如何用割平面方法求解整数线性规划问题？例考虑纯整数规划问题12maxzxx1212122645200,0xxxxxx且为整数解先不考虑整数条件，求得其松弛问题的最优单纯形表为：x1x2x3x4RHSz00-1/6-1/6-13/3x1x210015/6-2/3-1/61/35/38/3由第二行可以生成割平面：13x3+13x4=23引入松弛变量s1后得：－13x3－13x4+s1＝－23将此约束条件加到表中继续求解如下：x1x2x3x4s1RHSz00-1/6-1/60-13/3x1x210015/6-2/3-1/61/3005/38/315s100[-1/3]-1/31-2/3z0000-1/2-4x1x2x3100010001-1115/2-2-3042所以原问题的最优解为：x1*=0，x2*=4，最优值z*=4。4、分支定界方法的基本思想？如何用分支定界方法求解整数线性规划问题？例求解下面整数规划12max32zxx1212122923140,0xxxxxx且为整数值(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=3165、如何建立0-1规划问题的数学模型？6、如何用隐枚举法求解0-1规划和匈牙利法求解指派问题？例123max543zxxx1231232312332527352253270,3jxxxxxxxxxxxxj或1=1,2①②③④1235434xxx◎（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）√××17动态规划了解基本概念（如多阶段决策问题、阶段、策略）；了解最优性原理；如何用动态规划方法求解最短路问题？（图上作业、公式求解）如何用动态规划方法求解旅行售货员问题？如何求解多阶段的资源分配问题？18网络分析了解图的基本概念（如无向图、有向图、点、边、关联、邻接、次、关联矩阵、邻接矩阵、握手定理）；树，支撑树，如何找最小树？（破圈法、避圈法、反圈法；）最短路问