线性规划问题总结.doc

《线性规划问题总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、线性规划问题总结　　线性规划问题总结线性规划如何建立线性规划的数学模型；线性规划的标准形有哪些要求？如何把一般的线性规划化为标准形式？如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？如何用单纯形方法求解线性规划问题？如何确定初始可行基或如何求初始基本可行解？（两阶段方法）如何写出一个线性规划问题的对偶问题？如果已知原问题的最优解如何求解对偶问题的最优解？（对偶的性质，互补松紧条件）对偶单纯形方法适合解决什么样的问题？如何求解？对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何

2、进一步求解？　　1、建立线性规划的数学模型特点　　（1）每个行动方案可用一组变量（x1，…，xn）的值表示，这些变量一般取非负值；　　（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；　　（3）有一个需要优化的目标，它也是变量的线性函数。　　2、线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？目标求极小；约束为等式；变量为非负。　　mmnmmmmm?mm?mmmm??例把下列线性规划化为标准形式mmxmm2x1m3x2mx1m2x2m?mmmx1mx2m1mmx1m2mxm??xmm?m12解令x1mmx3?x2mxxmxx?

3、标准型为mmnmmmmm2x3m3mxxmxxmmmmx3m2mxxmxxmmx?m?mmmx3mmxxmxxmmx?m1mmmx3?x?m2mxm??mm3?x?x??????mm?　　3、如何用图解法求解两个变量的线性规划问题？由图解法总结出线性规划问题的解有哪些性质？（唯一最优解、无穷多最优解、无界解、无解）线性规划解的性质（基、基本解、基本可行解、凸集、顶点）定理1线性规划的可行域是凸集。　　定理2m是线性规划基本可行解的充分必要条件是m是可行域的顶点。　　定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。　　x、如

4、何用单纯形方法求解线性规划问题？（单纯形表）单纯形法的基本法则法则1最优性判定法则（检验数全部小于等于零时最优）法则2换入变量确定法则（谁最正谁进基）法则3换出变量确定法则（最小比值原则）法则x换基迭代运算法则mmnmmm2x1mxx2mx1m2x2mx3m?mmxx1m2x2mxxm2?mmxx2mxxm12mx?x?x?x?xm?m123xx最优解m*=（2，3，?，x，?）?，m*=-2×2-x×3=-19。　　x、如何确定初始可行基或如何求初始基本可行解？（两阶段方法）例求下列LP问题的最优解mmnmm3x1mx2mx3mx1m2x2mx3m11mmm

5、xx1mx2m2x3m3mmm2x1mx3m1mx?x?xm?m123用两阶段法来求解它的第一阶段是先解辅助问题mmnmmx?mx?mx1m2x2mx3mxxm11mmmxx1mx2m2x3mxxmx?m3mmm2x1mx3mx?m1mx?m?xm?1?第二阶段:原问题无界。　　?、如何写出原问题的对偶问题？如果已知原问题的最优解，如何求解对偶问题的最优解？mmns.t.cxmmxm?mmmxm?mxcm?xcmm????mmxmm1?m?immim1?m?mcm1?m?icmim1?m?ns.t.?bbmmm?bmm??cbm?cbm???例写出下面线性规划

6、问题的对偶问题mmnmm2x1m3x2mxx3mxxmx1mx2m3x3mxxmxmm2x1m2x3mxxxmxmmx2mx3mxxm?mx?x?xm??xmm?23xm1解原问题的对偶问题为mmxymxb1mxb2m?b3b1m2b2m2mmb1mb3m3mmmm3b1m2b2mb3mmxmb1mxb2mb3m1mmmb1?b2m??b3mm??、对偶单纯形方法适合解决什么样的问题？如何求解？例mmnmm1xx1m2xx2mxx3m?x2mx3mxxm2mmxx1m2x2mx3mxxm1mmx1?x2?x3?xx?xxm?对偶单纯形法的基本法则法则1最优性判

7、定法则（检验数全部小于等于零时最优）法则2换出变量确定法则（谁最负谁出基）法则3换入变量确定法则（最小比值原则）法则x换基迭代运算法则写出对偶问题并求解？（利用互补松紧条件）?、对于已经求解的一个线性规划问题如果改变价值向量和右端向量原最优解/基是否仍是最优解/基？如果不是，如何进一步求解？例线性规划mmxmmxx1mxx2mx1m3x2m9?mm2x1mx2m??mmx1mx2mxxmx?xm?m12已知最优表　　（1）确定x2的系数c2的变化范围，使原最优解保持最优；　　（2）若c2=?，求新的最优计划。　　解　　（1）将上表中的第?行重新计算检验数，得到

8、令c2－x≤?，x－2c2≤?，解得x