线性规划问题单纯形法.ppt

1、第五章,单纯形法 与单纯形表,线性规划 Linear Programming（LP）,图解法的启示 线性规划问题解的可能情况 a.唯一最优解 b.无穷多最优解 c.无解（没有有界最优解，无可行解） 若线性规划问题的可行域非空，则可行域是一个凸集； 若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。,线性规划 Linear Programming（LP）,单纯形法 单纯形方法是G.B.Danzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。,线性规划 Linear Pro

2、gramming（LP）,单纯形法 给定线性规划问题（标准形式）,max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s .t. am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n）,线性规划 Linear Programming（LP）,单纯形法 一、线性规划问题的解的概念 可行解 最优解 基 基解（基本解） 基可行解 可行基,线性规划 Linear Programming（LP）,单纯形法 二、凸集及其顶点 凸集 顶点（极点）,凸集,凹集,线性规划

3、 Linear Programming（LP）,1,2,3,4,5,6,7,8,线性规划 Linear Programming（LP）,单纯形法 三、线性规划基本定理 基本定理 1 线性规划所有可行解组成的集合S= X | AX = b，X 0 是凸集。 基本定理 2 X是线性规划问题的基本可行解的充要条件为是 X 是凸集S= X | AX = b，X 0 的极点。 基本定理 3 给定线性规划问题， A是秩为 m 的 mn 矩阵， （i） 若线性规划问题存在可行解，则必存在基本可行解 （ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解。,线性规划 Linear Programmi

4、ng（LP）,单纯形法 单纯形法迭代原理及其思路 单纯形法的初步讨论 例1.8 求解LP问题,化为标准型,线性规划 Linear Programming（LP）,单纯形法 此线性规划问题转化为了一个含有四个变量的标准形线性规划问题，X3，X4为松弛变量。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使 Z 取得Max的X1，X2，X3，X4的值，由此分析如下-,线性规划 Linear Programming（LP）,单纯形法 确定初始基可行解： 通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此 取 X3，X4为基变量；X1，X2为

5、非基变量。则（1.18）可变为：,线性规划 Linear Programming（LP）,单纯形法 典式 （1.19）或（1.18）称为关于基的典式 1、等式约束条件中显含基可行解 2、目标函数中不含基变量,线性规划 Linear Programming（LP）,单纯形法 在典式（1.19）中令： X1=X2 =0， 我们得到一个基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ， 其对应的目标函数值 Z1 = 50X1 + 30X2 = 0,线性规划 Linear Programming（LP）,单纯形法 最优性检验： 基本可行解 X1 是最优解吗？显然不是。

6、应寻找更好的解。从问题的数学角度分析，在典式（1.19）的目标函数中，非基变量X1，X2前的系数都为正，而此时的X1，X2均取零值，表明只要增加其值，则目标函数值有增加的可能。因此，将目标函数中系数为正的某一非基变量与某一基变量地位对换。,线性规划 Linear Programming（LP）,单纯形法 换基迭代： 进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足： 新的解仍是基本可行解； 目标函数值将得到改善。,线性规划 Linear Programming（LP）,单纯形法 选择入基变量： 由于在目标函数 Z1 =50X1+30X2 中X1，X2的系

7、数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。 选择出基变量： X1入基后，其值从零增加并由于约束条件的原因会引起其他变量的变化。由典式（1.19）以及变量必须取正值（可行）的条件，我们可以得到下列不等式关系： X3 = 120 - 4X1- 3X2 0 X4= 50 - 2X1- X2 0,线性规划 Linear Programming（LP）,单纯形法 因为迭代后X2仍为非基变量（仍会令其取值为零），则上式可简化为： 120 - 4X1 0 ，且 50 - 2X1 0 ， 由此可以看出，虽然我们希望X1入基后

8、取正值，取值越大目标值增加越大，但是 X1又得受到以上约束（保证其可行）。 显然，当取 X1 =min（120/4，50/2）=25时，才能使上述不等式成立，且此时恰使基变量X4变为零，这正好满足非基变量必须取值零的条件，所以可令X4 出基，这样，新的基变量变为X3 ，X1 ，而 X2 ，X4 成了非基变量，则,线性规划 Linear Programming（LP）,单纯形法 约束方程变为： 4X1+ X3 =120 - 3X2 2X1 = 50 - X2 - X4 化简后得：新的典式方程 X3 = 20 - X2 + 2X4 X1 = 25 -0.5X2 -0.5X4,线性规划 Linear

9、 Programming（LP）,单纯形法 代入目标函数可得： Z2 =1250+5X2-25X4 令非基变量X2 =X4 = 0，即可得一个新的基本可行解 X2 =（ 25，0，20，0）T ，其对应的目标函数值Z2 =1250，并完成了第一次迭代。由于目标函数 Z2 =1250+5X2-25X4中X2的系数仍为正，该解X2仍不是最优解。重复上述迭代过程得到：X2入基，X3出基，则新的典式方程变为： X1 = 15 +0.5X3 - 1.5X4 X2 =20 - X3 + 2X4 Z3 =1350 -5X3 - 15X4,线性规划 Linear Programming（LP）,单纯形法 第三

10、个基本可行解 X3 =（ 15，20，0，0）T，其对应的目标函数值 Z3 = 1350 。此时松弛变量 都是非基变量（取值为零），这表明资源已用尽；并且目标函数值 Z3 =1350 -5X3 - 15X4中非基变量X3，X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。,线性规划 Linear Programming（LP）,单纯形法小结： 单纯形法是这样一种迭代算法如下图 当 Zk 中非基变量的系数的系数全为负值时，这时的基本可行解 Xk 即是 线性规划问题的最优解，迭代结束。,X1,Z1,保持单调增,保持可行性,保持可行性,保持可行性,保持可行性,保持单调增,保持单调

11、增,保持单调增,X2,X3,.,Xk,Z2,Z3,.,Zk,当 Zk 中非基变量的系数的系数全为负值时，这时的基本可行解 Xk 即是线性规划问题的最优解，迭代结束。,线性规划 Linear Programming（LP）,单纯形表 对于给定的线性规划问题：,max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + + a1nxn b1 a21x1 + a22x2 + + a2nxn b2 s.t. am1x1 + am2x2 + + amnxn bm xj 0 （j=1，2 n）,对此问题添加m个松弛变量后，可得下面线性规划问题并且是典式的形式。,线性规划 Li

12、near Programming（LP）,单纯形表 线性规划的典式,max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn + xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 s.t. am1x1 + am2x2 + amnxn + xn+m = bm xj 0 （j=1，2 n，n+1，n+2，n+m）,线性规划 Linear Programming（LP）,单纯形表： 将上面典式中各变量及系数填写在一张表格中就形成下面的单纯形表,线性规划 Linear Programming（LP）,单纯形表： 上面的单

13、纯形表还可以表示成矩阵的形式,或,线性规划 Linear Programming（LP）,单纯形法 由单纯形表进行迭代步骤： 选择 Xj 入基：当 j 行中 j= max i i 0 选择 Xi 出基：当 i = min bi/aijaij 0 换基迭代：当确定了入基变量 Xj 、出基变量 Xi 后，以 aij 作为主元对单纯形表进行取主运算， 取主运算即采用初等行变换将主元 aij 所在列，除将 aii 变换为1而外，该列中的其余元素都变换为 0。注意这种变换只能采用初等行变换!,线性规划 Linear Programming（LP）,单纯形法 最优解检验： 当迭代进行至某一步时，j 行中所

14、有检验数均小于等于零，则迭代结束。表中当前所指基本可行解即为最优解。 当迭代进行至某一步时，j 行中所有检验数均小于等于零，且此时至少有一个非基变量所对应的检验数k 等于零，则原线性规划问题有无穷多个最优解。 当迭代进行至某一步时，j 行中至少有一个检验数 k 大于零，且该检验数对应的列中a1k ，a2k ， amk ，均小于等于零，则原线性规划问题最优解无界（ max Z +）。,线性规划 Linear Programming（LP）,单纯形方法的矩阵描述： 设线性规划问题 max Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I

15、 式） X 0 X ，XS 0 其中 b 0 ，I 是 mm 单位矩阵。 对上面（I 式）经过迭代，并设最终的最优基矩阵为B（不妨设B 为A 的首m 列，则将（I 式）改写后有,线性规划 Linear Programming（LP）,单纯形方法的矩阵描述：,max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0,max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = B -1b XB ，XN，XS 0,B 式中最优目标函数值Z*= C

16、B B -1 ， 检验数 CN - CB B -1 0 ， - CB B -1 0,单纯形方法迭代,（I 式）,（B 式）,线性规划 Linear Programming（LP）,单纯形方法的矩阵描述：,对应I 式的单纯形表 I 表,对应B 式的单纯形表 B 表,迭代,线性规划 Linear Programming（LP）,单纯形表计算步骤举例 给定线性规划问题,max z = 50X1 + 30X2 s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0,max z = 50X1 + 30X2 s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 5

17、0 X1， X2 ，X3 ，X4 0,线性规划 Linear Programming（LP）,单纯形表计算步骤举例,max z = 50X1 + 30X2 s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0,2,120/4,50/2,X1,1,1/2,0,1/2,25,0,20,1,- 2,0,5,0,- 25,20/1,252,1,1,X2,15,0,- 1/2,3/2,1,0,- 5,- 15,线性规划 Linear Programming（LP）,单纯形法的进一步讨论 人工变量法： 当一般线性规划问题标准化之后，我们或可

18、得到一个显然的基本可行解（如松弛变量作为基变量的一个初始基本可行解），这样我们就可以马上进入单纯形表的运算步骤。然而，并非所有问题标准化之后我们都可得到一个显然的初始基本可行解，这时就需要我们首先确定出一个基本可行解作为初始基本可行解。通常采用的是人工变量法来确定这样的初始基本可行解。这种情况下一般有两种方法： 大M法（罚因子法） 两阶段法,线性规划 Linear Programming（LP）,单纯形法的进一步讨论 1、大 M 法（罚因子法）,线性规划 Linear Programming（LP）,1、大 M 法,线性规划 Linear Programming（LP）,1、大 M 法,线性规划 Linear Programming（LP）,1、大 M 法,线性规划 Linear Programming（LP）,1、大 M 法,线性规划 Linear Programming（LP）,1、大 M 法,线性规划 Linear Programming（LP）,采用大 M 法求解线性规划问题时可能出现的几种情况： 当采用单纯形法求解 LPM 得到最优解时，基变量不含任何人工变量，则所得到的最优解就是原问题的最优解； 当采用单纯形法求解 LPM 得到最优解时，基变量至少含有一个人工变量且非零，则原问题无可行解； 当采用单纯形法求解 LPM 得到最优解时，基变量至少含有一个人