运筹学上课02线性规划解法VIP

1、1.求解线性规划问题时，解的情况有：唯一解；无穷多最优解；无界解；无可行解。2.若线性规划问题的可行域存在，则可行域是一个凸集。3.若线性规划问题的最优解存在，则最优解或最优解之一（有无穷多最优解）一定是可行域的凸集的某个顶点。4.解题思路是，先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。线性规划问题的求解线性规划问题的求解一、仿射尺度法2、仿射尺度法基本原则、仿射尺度法基本原则3、仿射尺度算法二、单

2、纯形法如何改善？如何判断没有有限最优解？单纯形法的步骤：（1）建立实际问题的线性规划数学模型；（2）把一般的线性规划问题化为标准型；（3）确定初始基本可行解；（4）检验所得到的基本可行解是否为最优解；（5）迭代，求得新的基本可行解。线性规划问题的代数运算形式例：用单纯形法的代数运算形式求解下列线性规划问题00155164122232max21212121xxxxxxxxz、求解步骤（1）化为标准型（2）找一个初始基本可行解X（0）100500100400122A0013P0104P1005P121231425max23221241651501,2,5jzxxxxxxxxxxjL ， B0为一个

3、可行基， x3 、 x4 、 x5为关于可行基B0的基变量， x1 、 x2 为关于可行基B0的非基变量，为求初始基本可行解，令非基变量x1 = x2 =0。从而有x3 =12， x4 =16， x5 =15，于是得到初始基本可行解：1000100015430PPPBX （0） =（0，0，12，16，15） T 其对应的目标函数值 z0=20+30=0（3）检验X（0）是否为最优解。由目标函数的表达式：z =2x1 +3x2 可知，非基变量x1 和 x2 的系数为正，如果把非基变量x1 或x2转换为基变量，则会使目标函数的值增加。可见 X（0）不是最优解（4）第一次迭代。 每一次迭代，得到一

4、个新的基本可行解。因此，哪些变量作为基变量，哪些非基变量，就要发生变化。 由于目标函数中x2的系数大于x1的系数，因此，可以选择x2使它作为基变量，而且让它取尽可能大的值，同时， x1仍作为非基变量取值为零。从原来的基变量x3 、 x4 、 x5中选出一个作为非基变量。 x2的取值不能任意地增加，它要受到约束方程的限制：2x1 +2x2 + x3 = 124x1 + x4 = 16 5x2 + x5 = 15x3 = 12 2x1 2x2 x4= 16 4x1 x5 = 15 5x2 将x1 = 0， x2 = 代入上面约束方程，为了让取尽可能大的值，同时又要考虑到x3 、 x4 、 x5必须

5、满足非负约束，从而的值应满足：x3 = 12 2 0 x4 = 16 0 x5 = 15 5 0即：x2 = =min12/2，15 /5=3相应地有：x3 = 12 2 3=6x4 = 16x5 = 15 5 3=0 可见，从原来的基变量x3 、 x4 、 x5中选出x5作为非基变量，得第一次迭代后的基本可行解：X （1） =（0，3，6，16，0） T 其对应的目标函数值：z1=20+33=9（5）检验X （1） 是否为最优解 将约束方程组改为用非基变量x1 、 x5来表示基变量x2、 x3 、 x4的表达式。可用高斯消去法得到：2x1 + x3 2 /5x5 = 64x1 + x4 =

6、16 x2 + 1 /5 x5 = 3移项后得到：x3 = 6 2x1 + 2/5x5 x4 = 16 4x1x2 = 3 1/5 x5 将上式代入目标函数，得目标函数用非基变量x1 、 x5表示的表达式z =9+2x1 3/5x5 由于非基变量x1的系数是正数，如果把非基变量转换为基变量，则会使目标函数的值增加。可见X （1）不是最优解。（6）第二次迭代 和第一次迭代同样的道理，应选取非基变量x1使它成为基变量，而且让它取尽可能大的值，同时， x5仍作为非基变量取值为零。从原来的基变量x2 、 x3 、 x4中选出一个作为非基变量。 x1的取值也按同样的方法确定：x3 = 6 2x1 + 2

7、/5x5 x4 = 16 4x1x2 = 3 1/5 x5 将x1 = ， x5 = 0代入：x3 = 6 2 0 x4 = 16 4 0 x2 = 3 0即：x1 = =min6/2，16 /4 ，=3相应地有： 可见，从原来的基变量x2 、 x3 、 x4中选出x3作为非基变量，得第二次迭代后的基本可行解：X （2） =（3，3，0，4，0） T x3 = 6 2 3 =0 x4 = 16 4 3=4x2 = 3其对应的目标函数值：z1=23+33=15（7）检验X （2） 是否为最优解 将约束方程组改为用非基变量x3 、 x5来表示基变量x1、 x2 、 x4的表达式。可用高斯消去法得到

8、：x1 + 1/2 x3 1/5x5 = 3 2 x3 + x4 + 4/5x5 = 4 x2 + 1/5 x5 = 3移项后得到：x1 = 3 1/2 x3 + 1/5x5 x4 = 4 + 2 x3 4/5x5 x2 = 3 1/5 x5 将上式代入目标函数，得目标函数用非基变量x3 、 x5表示的表达式z =15 x3 1/5x5 这时,目标函数中非基变量的系数都不大于零，可见目标函数的值不可能再继续增大,目标函数已经取得最大值15 ，故为X （2）最优解。总 结 通过以上例题的分析，可以归纳出单纯形法的步骤：（1）建立实际问题的线性规划数学模型；（2）把一般的线性规划问题化为标准型；（

9、3）确定初始基本可行解；（4）检验所得到的基本可行解是否为最优解；（5）迭代，求得新的基本可行解。单纯形法的三个关键部分：（1）初始基本可行解的确定；（2）最优性检验；（3）如何进行迭代: 确定入基变量,出基变量单纯形法一般步骤1.初始基本可行解的确定（观察法）；12100010(,)001nnn mBpppLLLMMMLnjjjxcZ1max1. .01,2,njjjjx pbstxjnLmnnjjnjjjxxcZ110max11 112211121 12222221 12212. .,0nnnnnnmmmnnn mmn ma xa xa xxba xa xa xxbsta xaxaxxbx

10、xxLLMMMLL基本可行解12(0,0,0,)mXb bbLL基2.从约束中解出基变量；11,2,nn iiijjjxba ximL（）mnnjjnjjjxxcZ110max11 112211121 12222221 12212. .,0nnnnnnmmmnnn mmn ma xa xa xxba xa xa xxbsta xaxaxxbxxxLLMMMLL3.代入目标消去基变量，得到非基变量xj的检验数 jmiiinbcZ10miininnjjjxcxcZ1111,2,nn iiijjjxba xim（）LnjjijimiinnjjjxabcxcZ1111111mnmnn iijjn ii

11、jjijijcbc xca x111()mnmn iijn iijjijicbccax1mjn iijizcanjjjjxzcZZ10)(jjjzc 01njjjZx4.判断最优；最优性判别定理：若是对应于B的基本可行解， j是用非基变量表示目标函数的表达式 中非基变量xj的检验数，若对于一 切非基变量的角指数j均有j 0 则当前基本可行解为最优解。010ZxZZnjjj对于任意可行解X，对于基本可行解X0，0ZZ 012X( 0 , 0 , 0 ,)mbbbLL无穷多最优解的判定?若对于一 切非基变量的角指数j均有j 0, 并且存在一个j =0, 则线性规划问题有无穷多最优解5.没有有限最优

12、解的判断；无最优解判别定理：若是对应于B的基本可行解， 非基变量x k的检验数k 0 , 且对于i=1,2,m 均有aik 0, 则原问题没有有限最优解。(0)12(0,0,0,)mXb bbLL该证明留作课后练习6.改进目标 若k 0，则选xk进基;用最小比值法确定xk的最大值，使基变量xl取0值，其它基变量非负；lklikikiabaab0min01,2,n iiikkxba ximL即xl出基，换基过程若不存在, 则Z，没有有限最优解。7.主元变换（枢变换或旋转变换） xk进基， xl出基，解出新的基变量111211112121000.1001kniiikinimmmkmnmaaaaba

13、aaabaaaabLLLMMMMMMMLLLMMMMMMMLLLljlkikijijlkljljaaaaaaaa表格单纯形法标准型：mnmnnnnnxcxcxcxcxcZ112211max0,. .1212211222222121111212111mnnnmmnnmnmmnnnnnnxxxxxbxxaxaxabxxaxaxabxxaxaxats0. .1122112211222222121111212111mnmnnnnnmmnnmnmmnnnnnnxcxcxcxcxcZbxxaxaxabxxaxaxabxxaxaxats表格单纯形法标准型：mnmnnnnnxcxcxcxcxcZ112211m

14、ax0,. .1212211222222121111212111mnnnmmnnmnmmnnnnnnxxxxxbxxaxaxabxxaxaxabxxaxaxatsbxxxxxxZmnnnn212101100001000010212121222221111211nmnnnmmnmmnnccccccbaaabaaabaaa表格单纯形法bxxxxxxZmnnnn212101100001000010212121222221111211nmnnnmmnmmnnccccccbaaabaaabaaa022112122222111121121210001100001000010ZZcZcZcbaaabaaab

15、aaabxxxxxxZnnmnmmmnnmnnnnmiiinbcZ10njacZmiijinj,.2 , 11表格单纯形法miiinbcZ10njacZmiijinj,.2 , 11基变量检验数最小比值列 基变量系数右端常数表格单纯形法例5 用单纯形法求解线性规划问题0,52426155.2max212121221xxxxxxxtsxxz解 先将上述问题化成标准形式有0,52426155. .0002max543215214213254321xxxxxxxxxxxxxtsxxxxxzcj21000CB基 b x1x2x3x4x50 x315051000 x424620100 x5511001cj-zj21000表1-701/602/614x120-1/301/30cj-zj1-1/604/601x500015015x30 x5x4x3x2x1b 00012