线性规划问题本基理论.pptVIP

第二章 第2节线性规划问题的基本理论;一、线性规划问题的标准化;标准形式 目标函数： Max z = c1 x1 + c2 x2 + … + cn xn 约束条件： a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn =b2 …… …… am1 x1 + am2 x2 + … + amn xn =bm 决策变量： bi ≥0 x1 ，x2 ，… ，xn ≥ 0;一般型和标准型的区别;1、极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ， 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - … - cnxn 但必须注意，尽管以上两个问题的最优解相同， 但它们最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z ;2、约束条件不是等式的问题： 设约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与 左边之差（一般称S为松弛变量） s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s 也具有非负约束，即s≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+s = bi ;当约束条件为 ai1 x1+ai2 x2+ … +ain xn ≥ bi 时， 类似地令 s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，这时新的约 束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi 称S为剩余变量。;不等式情况下： 当≤，引入松弛变量s 当≥，引入剩余变量s 松弛变量：需要补充的资源 剩余变量：没有使用的资源 如果原问题中有若干个非等式约束，则将其 转化为标准形式时，必须对各个约束引进不 同的松弛变量。 ;3、右端项有负值的问题： 在标准形式中，要求右端项必须每一个 分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以-1，得 到： -ai1 x1-ai2 x2- … -ain xn = -bi。 ;4、决策变量不定： 当Xi0，令Xi`=-Xi，则Xi``o 当某一个变量xj没有非负约束时，可以令 xj = xj’- xj” 其中 xj’≥0，xj”≥0 即用两个非负变量之差来表示一个无符号限 制的变量，当然xj的符号取决于xj’和xj”的 大小。 ;例：将以下线性规划问题转化为标准形式? Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 ≤6 2 x1 + x3 ≥8 x1 + x2 + x3 = -9 x1 , x2 , x3 ≥ 0?;解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3 其次考虑约束，有2个不等式约束，引进松 弛变量x4，和剩余变量x5 ≥0。 第三个约束条件的右端值为负，在等式两 边同时乘-1。;通过以上变换，可以得到以下标准形式的线 性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 ;练习： P24 习题3 （1）和 （2） 作业： P24 习题3 （3）;二、线性规划问题的解;1、解的情况;判断题： 线性规划问题无有限最优解的充要条件是可 行域为空？;2、几个重要的解概念 （1）可行解、可行域、最优解、最优值 （2）基、基本解 （3）基本可行解（基可行解） （4）可行基 ;（1）可行解、可行域、最优解、最优值;例： ;（2）基、基本解;设B为A中的一个基