线性规划问题的基本理论.ppt

《线性规划问题的基本理论.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的基本理论.ppt（36页珍藏版）》请在装配图网上搜索。

1、第二章 第2节线性规划问题的基本理论,一、线性规划问题的标准化 二、线性规划问题的解 三、线性规划问题的几何意义,一、线性规划问题的标准化,一般形式 目标函数： Max （Min） 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 决策变量： x1 ，x2 ， ，xn () 0,标准形式 目标函数： Max z = c1 x1 + c2 x2 + + cn xn

2、约束条件： 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 ， 则该极小化问

3、题与下面的极大化问题有相同的最优解， 即 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 也具有非负约束，即s0， 这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn+s = bi,当约束条件为 ai1

4、 x1+ai2 x2+ +ain xn bi 时， 类似地令 s=(ai1 x1+ai2 x2+ +ain xn)- bi 显然，s 也具有非负约束，即s0，这时新的约 束条件成为 ai1 x1+ai2 x2+ +ain xn-s = bi 称S为剩余变量。,不等式情况下： 当，引入松弛变量s 当，引入剩余变量s 松弛变量：需要补充的资源 剩余变量：没有使用的资源 如果原问题中有若干个非等式约束，则将其 转化为标准形式时，必须对各个约束引进不 同的松弛变量。,3、右端项有负值的问题： 在标准形式中，要求右端项必须每一个 分量非负。当某一个右端项系数为负时，如 bi0，则把该等式约束两端同时乘以

5、-1，得 到： -ai1 x1-ai2 x2- -ain xn = -bi。,4、决策变量不定： 当Xio 当某一个变量xj没有非负约束时，可以令 xj = xj- xj” 其中 xj0，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

6、 其次考虑约束，有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、解的情况,（1）存在有限最优解： a） 唯一最优解 b）无穷多个最优解

7、（2）不存在最优解 a）无有限最优解（无界解） b）无可行解（可行域空）,判断题： 线性规划问题无有限最优解的充要条件是可 行域为空？,2、几个重要的解概念 （1）可行解、可行域、最优解、最优值 （2）基、基本解 （3）基本可行解（基可行解） （4）可行基,（1）可行解、可行域、最优解、最优值,满足约束条件(1-2)、(1-3)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。 由可行解组成的集合就是可行域（满足约束条件不等式所有点组成的集合），将最优解代目标函数得到的函数值就是最优值。,例：,Max z = 1500 x1 + 2500

8、x2 s.t. 3x1+ 2x2 65 2x1+ x2 40 3x2 75 x1 , x2 0,（2）基、基本解,设B为A中的一个基，令Ax=b，中所有的非基变量（n-m 个）为0，得出的解x，称为是B的基本解。 x1 x2 x3 x4 x5 bi 3 2 1 0 0 65 2 1 0 1 0 40 0 3 0 0 1 75 P1 P2 P3 P4 P5 A=（P1，P2，P3，P4，P5） B=（P1，P2，P3），基变量（ x3 x4 x5 ） 非基变量（ x1 x2 ），B的基本解是（0，0，65， 40，70）,（3）基本可行解,（1）满足非负的基本解，为基本可行解。 （2）可行解满足

9、的条件是：Ax=b和x 0， 而基本解必然满足Ax=b，只需满足X 0。,（4）可行基,对应于基可行解的基，称为可行基。 基本解数目最多是 Cnm个，一般基可行解的 数目要小于基本解的数目。 当基本解中的非零分量的个数小于m时， 该基本解是退化解。,练习： P96 例题1 作业： P96 例题2 （1）找出所有基本解，并指出哪些是基本可 行解？,1、基本概念 2、基本定理 3、几何意义,三、线性规划问题的几何意义,三、线性规划问题的几何意义,1、基本概念： （1）凸集 （2）顶点,（1）凸集 定义：设K是n维欧氏空间的一点集，若任意两 点X(1)K，X(2)K的连线上的所有点 X(1)+(1)

10、X(2)K，(01)，则称K为凸 集。（任何两个凸集的交集是凸集）,（2）顶点 设K是凸集，XK；若X不能用不同的两点 X(1)K和X(2)K的线性组合表示为 X=X(1)+(1)X(2)，(01)，则称X为K 的一个顶点(或极点)。,2、基本定理 定理1：若线性规划问题有可行域，则可行 域必为凸集。 定理2 ：线性规划问题的基可行解X对应于 可行域D的顶点。 定理 3 ：若可行域有界，则最优解一定在 顶点上达到。,定理的意义： 定理1：可行域是凸集。 定理2：基本可行解对应顶点。 定理3：最优解在顶点上找。,几何意义的作用,线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点。 若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的，若采用“枚举法”找所有基可行解，然后一一比较，最终必然能找到最优解。但当n,m较大时，这种办法是行不通的，所以要继续讨论如何有效寻找最优解的方法。本课程将主要介绍单纯形法。 单纯性法实质：从一个顶点向一个顶点迭代，保持最优性，一直到达到最优解。,