高等学校计算机专业教材：《数值计算方法》课程教学资源（PPT课件）第五章 线性规划

第5章线性规划 5.1线性现题的准形式 5.2线性规划向题的几何解释 5.3定义初定理 5,4单统形算法 5.5应用实例 点击此处结束放映

第5章 线性规划 5.1 线性规划问题的标准形式 5.2 线性规划问题的几何解释 5.3 定义和定理 5.4 单纯形算法 5.5 应用实例

5.1线性规划问题的标准形式 线性规划问题的标准形式为 min fo x,+c,x+…+c.x.(51) s.t. ax, +ax+.ta.x (52) amIx+am2x 2++amnrn=b 0 l,2,…,n (53) 点击此处结束放映

5.1 线性规划问题的标准形式 线性规划问题的标准形式为 (5.1) (5.2) (5.3)

上式中,c,b,a1(i=1,2,…,mj=1,2,…,n 为已知常数,x为决策变量。 标准形式的线性规划具有如下特征: (1)目标函数是极小化形式。 (2)所有的约束条件都是等式。 (3)所有的决策变量都是非负的。 任何一种线性规划问题都可采用下面的变 换将其化为标准形式: 点击此处结束放映

上式中 ， 为已知常数，xi为决策变量。 标准形式的线性规划具有如下特征： （1）目标函数是极小化形式。 （2）所有的约束条件都是等式。 （3）所有的决策变量都是非负的。 任何一种线性规划问题都可采用下面的变 换将其化为标准形式：

(1)极小化函数f(x1,x2…yxn) 和极大化该函数的负值等价。例如, minf(x1,x2,…,xn)=c1x1+c2x2+…+Cnn 等价于 maxf′=-f= 2“2 nn 因此,任何一个线性规划问题,其目 标函数都可写成极小化的形式。 点击此处结束放映

（1）极小化函数 和极大化该函数的负值等价。例如， 等价于 因此，任何一个线性规划问题，其目 标函数都可写成极小化的形式

(2)大多数工程优化问题中,决策变 量都代表某些物理量。 (3)如果有一个约束条件是“小于等 ”的不等式,即 k1x1+ak2x2+…+anxn≤b k 点击此处结束放映

（2）大多数工程优化问题中，决策变 量都代表某些物理量。 （3）如果有一个约束条件是“小于等 于”的不等式，即

5.3定义和定理 对n维线性规划问题的求解,已不能使用图 解法。为了用代数方法求解,我们需要相应的概 念和定理,首先给出线性规划标准形式的矩阵表 示。 min f=c x s.t. aX=b (54) X>0 点击此处结束放映

5.3 定义和定理 对n维线性规划问题的求解，已不能使用图 解法。为了用代数方法求解，我们需要相应的概 念和定理，首先给出线性规划标准形式的矩阵表 示。 （5.4）

下面是基本解,基矩阵,基变量,非 基变量,基本可行解的定义。 设的A秩为m,且在[刷M,其中B是 可逆矩阵。如果的前m列线性相关,则可 通过列调换,使前m线性无关。因此,关 于逆的假设不失一般性。 点击此处结束放映

下面是基本解，基矩阵，基变量，非 基变量，基本可行解的定义。 设的A秩为m，且A=[BN]，其中B是m阶 可逆矩阵。如果A的前m列线性相关，则可 通过列调换，使前m列线性无关。因此，关 于B可逆的假设不失一般性

设X=B,其中的分量与肿 的列对应,的分量与N中的列对应。 于是,可以把Ab写成 B b 点击此处结束放映

设 ，其中的XB分量与B中 的列对应，XN的分量与N中的列对应。 于是，可以把AX=b写成

从而,B+M=b。对该式两端左乘B1,可 得到B4b-B1M。的分量就是“线性代数” 中所说的自由分量。它们取不同的值,就会得到 方程组不同的解。令=0,则得到 xX B 6 称其为AX=b的一个基本解。B称为基矩阵。 X的各分量称为基变量。X的各分量称为非 基变量。当B1b>0时,则称X为满足约束条件 AX=b,X≌0的基本可行解。 点击此处结束放映

从而，BXB+NXN=b。对该式两端左乘B -1 ，可 得到XB=B -1 b-B -1NXN 。XN的分量就是“线性代数” 中所说的自由分量。它们取不同的值，就会得到 方程组不同的解。令XN＝0，则得到 称其为AX=b的一个基本解。B称为基矩阵。 XB的各分量称为基变量。XN的各分量称为非 基变量。当B-1b≥0时，则称X为满足约束条件 AX=b，X≥0的基本可行解

54单纯形算法 由定理1我们已经知道,最优解必从基本 可行解中得到。因此,需要构造一种计算方 法:只考察基本可行解序列,且这一序列的 目标值应逐渐减小,直到达到最优值为止。 表5-2是依据问题5.5)的目标函数和等式 约束条件得到的。 点击此处结束放映

5.4 单纯形算法 由定理1我们已经知道，最优解必从基本 可行解中得到。因此，需要构造一种计算方 法：只考察基本可行解序列，且这一序列的 目标值应逐渐减小，直到达到最优值为止。 表5-2是依据问题(5.5)的目标函数和等式 约束条件得到的