单纯性解法课件

线性规划(LinearProgramming)线性规划问题的求解方法线性规划的单纯形法单纯形法的进一步讨论线性规划模型的应用目标函数：约束条件：①②③线性规划数学模型的一般形式也可以记为如下形式：目标函数：约束条件：向量形式：矩阵形式：一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但需将一般形式变成标准形式线性规划问题的求解方法

（一）求解方法1、解的概念⑴可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。⑵最优解：使目标函数达到最大值的可行解。⑶基：B是矩阵A中m×m阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj(j=12……m)为基向量。∴Xj

为基变量，否则为非基变量。（二）线性规划问题的解上二组概念间的联系：系数阵A中可找出若干个基B每个基B都对应于一个基本解非负的基本解就是基本可行解几种解之间的关系：可行解基本解非可行解基本可行解问题：基本可行解是可行域中的哪些点？顶点2、特征：⑴目标函数为求极大值，也可以用求极小值；⑵所有约束条件（非负条件除外）都是等式，右端常数项为非负；⑶变量为非负。⑵.约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量2)

不等式约束化为等式约束分析：以下例资源约束为例之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3

，则有X3称为松弛变量。问题：它的实际意义是什么？

——

未被利用的资源练习：请将例1的约束化为标准型解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。⑶.变量的变换

若存在取值无约束的变量，可令其中：例一、将下列线性规划问题化为标准形式为无约束（无非负限制）

解:

用替换，且，将第3个约束方程两边乘以（－1）将极小值问题反号，变为求极大值标准形式如下：引入变量

单纯形法求解线性规划问题引例

例：求解例1-1

首先化为标准型线性方程组的增广矩阵表示第四节单纯形法确定（初始）基本可行解。由于变量x3，x4，x5分别只出现每一个方程中，它们的系数列向量构成单位矩阵，成为线性规划的一个基。于是令x3，x4，x5为基变量，x1，x2是非基变量。若令x1=0，x2

=0，可得x3=1600，x4=2500，x5=400。显然，X（0）=（0，0，1600，2500，400）可作为本问题的一个初始基本可行解。

一般地，初始基本可行解是看出来的，而不是算出来的：找单位阵为初始基，其对应的变量为基变量。令非基变量为零，则方程组右端的常数就依次是几个基变量的取值，于是得到第一个基本可行解。相应的，在后续的计算过程中，为了能够把基本可行解“看”出来，也总是把基变量所对应的“基矩阵”化成单位阵的形式。第四节单纯形法2对当前解进行判别

1确定初始基本可行解第四节单纯形法2对当前解进行判别

1确定初始基本可行解3解的改进

解的改进要遵守的一个原则是：解必须是基本可行解（凸集顶点）

在进行解的最优性判别的时候，检验系数也给出了对目标函数进行优化的方向：选择最大正检验系数对应的非基变量x1为非零可以使得目标函数增加最快，我们称这个过程为x1进基。并且希望x1越大越好。

如何确定该非基变量可能取得的最大值？关键：x1增大不破坏其他变量的可行性。我们称为“最小θ比值原则”——θ的实际意义是什么？第四节单纯形法1确定初始基本可行解

2对当前解进行判别

3解的改进

4迭代运算

为了简便地得到一个新的基本可行解，将新基化为单位阵。方法是，进基变量取代出基变量在基中的位置。可以通过对约束方程组的前二式进行变换，即第三式不变,第一、二式x1的系数变成0.

此时的基变量是？第四节单纯形法继续运算，第二次迭代过程由确定进基变量x2

由得出基变量x4

迭代运算，求出新解第四节单纯形法继续运算，第三次迭代过程由确定进基变量x5

由得出基变量x3

迭代运算，求出新解练习：变成标准型约束方程的系数矩阵为基变量为非基变量I为单位矩阵且线性独立令：则：∴基本可行解为（001281612）

此时，Z=0

然后，找另一个基本可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。

注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。当时，为换入变量确定换出变量为换出变量接下来有下式：

用高斯法，将的系数列向量换为单位列向量，其步骤是：结果是：代入目标函数：

有正系数表明：还有潜力可挖，没有达到最大值；此时：令得到另一个基本可行解

（0，3，6，2，16，0）

有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当时，即不再利用这些资源。如此循环进行，直到找到最优为止。本例最优解为：（4，2，0，0，0，4）三、关于解的最优性检验及检验数的计算设线性规划模型为第四节单纯形法令基为B，并作相应的矩阵分割，从约束条件得代入目标函数得第四节单纯形法令则目标函数可写成所以可用判断是否最优解，称为检验数。第四节单纯形法43000000x3x4x51600250040025122.501000100018005004000-4-3000五、表解形式的单纯形法第四节单纯形法43000004x3x4x180050040000122.50100010-2-5140020016000-3004034x3x2x1400200400001010100-0.80.402-2120040022000001.2-2034x5x2x12006002000010100.51-0.5-0.4-0.40.410026000010.40第四节单纯形法

算法总结Step1确定初始基本可行解，建立初始单纯形表；

Step2最优性检验。若所有的检验数，则已得到最优解，停止运算。否则转下一步；

Step3确定进基变量xk..在所有正检验数中选择最大的正检验数所对应的非基变量为进基变量，即若则相应的xk为进基变量。若有两个或两个以上的非基变量的检验数均为最大，可选其下标最小者，如果进基变量xk所在列的所有系数则该线性规划问题为无界解，停止运算；否则进行下一步；

Step4确定出基变量xs.按最小比值法求出

故xs为出基变量。若出现相同最小比值时，则从相同的最小比值所对应的基变量中，选下标小者作为出基变量，转下一步；

Step5以ask为主元（为明显可标记*号），进行变换，（即进行矩阵的初等行变换）将xk所对应的列向量变为单位列向量

习题P.276，习题4（2）P.277，习题10（1）（四）单纯形表判定标准：若求

或例题：cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001-Z0

23000012/28/2－12/4cj230000cBxBbx1x2x3x4x5x6000x3x4x516

400010

-Z3x23010001/42620100-1/2100100-1/2cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/4-Z-9

20000-3/46/2216/4－cj230000cBxBbx1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412-Z-13000-201/4cj230000cBxBbx1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100-Z-1400-1/2-100000-201/4-13-Z4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cjcj230000cBxBbx1x2x3