第5章线性规划

《第5章线性规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章线性规划5.1线性规划问题的标准形式5.2线性规划问题的几何解释5.3定义和定理5.4单纯形算法5.5应用实例5.1线性规划问题的标准形式线性规划问题的标准形式为(5.1)(5.2)(5.3)上式中，为已知常数，xi为决策变量。标准形式的线性规划具有如下特征：（1）目标函数是极小化形式。（2）所有的约束条件都是等式。（3）所有的决策变量都是非负的。任何一种线性规划问题都可采用下面的变换将其化为标准形式：（1）极小化函数和极大化该函数的负值等价。例如，等价于因此，任何一个线性规划问题，其目标函数都可写成极小化的形式。（2）大多数工程优化问题中，决策变量都代表某些物理

2、量。（3）如果有一个约束条件是“小于等于”的不等式，即5.3定义和定理对n维线性规划问题的求解，已不能使用图解法。为了用代数方法求解，我们需要相应的概念和定理，首先给出线性规划标准形式的矩阵表示。（5.4）下面是基本解，基矩阵，基变量，非基变量，基本可行解的定义。设的A秩为m，且A=[BN]，其中B是m阶可逆矩阵。如果A的前m列线性相关，则可通过列调换，使前m列线性无关。因此，关于B可逆的假设不失一般性。设，其中的XB分量与B中的列对应，XN的分量与N中的列对应。于是，可以把AX=b写成从而，BXB+NXN=b。对该式两端左乘B-1，可得到XB=B-1b-B-1NXN。

3、XN的分量就是“线性代数”中所说的自由分量。它们取不同的值，就会得到方程组不同的解。令XN＝0，则得到称其为AX=b的一个基本解。B称为基矩阵。XB的各分量称为基变量。XN的各分量称为非基变量。当B-1b≥0时，则称X为满足约束条件AX=b，X≥0的基本可行解。5.4单纯形算法由定理1我们已经知道，最优解必从基本可行解中得到。因此，需要构造一种计算方法：只考察基本可行解序列，且这一序列的目标值应逐渐减小，直到达到最优值为止。表5-2是依据问题(5.5)的目标函数和等式约束条件得到的。在单纯形表中，将-f加入约束方程AX=b中，对应系数取为0；AX=b已经进行初等变

4、换，将基矩阵B变换为单位矩阵；最后一行是对公式(5.5)中的目标函数f=CTX进行初等变换的结果，即将基变量xi(i=1,…,m)的系数ci(i=1,…,m)变换为0。这样，从单纯形表立即可以得到以下信息：(1)基变量xi=bi(i=1,…,m)。(2)非基变量xi=0(i=m+1,…,n)。(3)目标值f=f0。[例4]求它的单纯形表解：本题已是线性规划的标准形式。取z1,z2,z3为基变量，因目标函数f(x,y)=-50x-100y中无基变量，说明基变量对应的系数为0。这样，无须对AX=b和f(x,y)=-50x-100y进行初等变换，直接可得单纯形表(表5-3

5、)。表5-3例4的单纯形表由表5-3可知：(1)基变量z1=2500,z2=2000,z3=450。(2)非基变量x=y=0。(3)目标值f=0。［定理2］如果单纯形表中最后一行(判别行)非基变量列的Ci(i=m+1,…,n)都是非负的，则此时基本可行解就是最优解，f0为最小目标值。［例6］(有无界解)求最优解。解：设k为单纯形表的变换次数。标准形式为k=0时的单纯形表如表5-9所示。表5－9k=0时的初始单纯形表初始基本可行解：X(0)=［0016］T;初始目标值：f(0)=0；基变量：z1,z2。由于c1=-3，我们让x

6、1入基，得到k=1时的单纯形表(表5-10)。表5-10k=1时的单纯形表由表5-10可知：X(1)=-［1003］T，f(1)=-3，基变量：x1,z2。由于c2=-5,我们让x2入基，得到k=2时的单纯形表(表5-11)。第3列系数均为负，则有无界解，与图解(留为作业)结论一致。表5－11k=2时的单纯形表［例8］求最优解。解：标准形式为设k为单纯形表的变换次数。由目标函数和约束条件得到表5－15。表5－15例7表1表5－15还不是初始单纯形表，但我们在例5已得到它的初始单纯形表1(见表5－5)。由初始单纯形表1得到初始基本可行

7、解：X(0)=［01010］T初始目标值：f(0)=-2基变量：x1,x4由于c3=-1，我们让x3入基，得到k=1时的单纯形表。表5-16k=1时的单纯形表1判别系数ci≥0,得到最优解X(1)=［01100］Tf(1)=-3,s*=3。从例5我们还得到了初始单纯形表2(如表5-17所示)，现从此出发进行计算。表5-18k=1时的单纯形表2判别系数ci≥0，得到最优解X(1)=［01100］Tf(1)=-3,s*=35.5应用实例［例10］中国石化总公司规划院罗建强等在《软件世界》1994年第11期上发