最优化方法课件图解法和LP基本定理

3.LP基本定理4.单纯形法

1.图解法5.大M法第二章线性规划（LP）6.LP对偶理论（对偶单纯形法）2.LP标准形17.灵敏度分析及应用确定可行域：

画约束直线，确定满足约束条件的半平面，所有半平面的交集，即为线性规划的可行域。确定目标函数的等值线及优化方向：

画一条目标函数等值线，并确定目标函数优化的方向。平行移动目标函数等值线，通过观察得到线性规划的最优解。图解法的步骤2第一节图解法例1.

用图解法求解线性规划问题二、例题解析3x1x2o-3X1-4X2=-12(≥)

Lo：0=2X1+X2

D此点是唯一最优解，且最优目标函数值

minZ=-7可行域4解：例2.

x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZ（3.8，4）30.6=3X1+5.7X2

蓝色线段上的所有点都是最优解。这种情形为有无穷多最优解，但是最优目标函数值maxZ=30.6是相同的。可行域6例2.

x1x2O10203040102030405050可行域是空集无可行解(即无最优解)maxZ=3x1+4x27例3.

2X1+X2=40(≤)X1+1.5

X2=30(≤)X1+X2=50(≥)线性规划的图解法启示：线性规划问题的解有多种情形；若线性规划的可行域非空，则一定是凸集（区域内任意两点连线都在其中）；线性规划问题若有最优解,则最优解在可行域的某顶点上达到.优缺点简单、直观、便于初学者理解和记忆；仅适用于低维情况，通常适用于含两个或三个变量的情况。9对于高维情况,怎么求解呢?-----单纯形法

第二节线性规划的标准形10线性规划的形式是多种多样的:目标函数求极大(极小);

约束可能有等式约束,也可能有不等式约束;决策变量有的受非负约束,有的是无限制.

为了方便研究,考虑将各种形式的LP化为一种统一的形式,这种形式即被称为LP的标准形式.11一、LP标准形三大特点目标函数：min约束条件：=变量符号：≥0二、化LP为标准型的方法1213例12.举例分析:共有4处不符合标准形的要求.解:14则相应的标准形为15例2分析:共有5处不符合标准形的要求.解:16则相应的标准形为第三节LP基本定理

将LP化为标准形后,如何求最优解呢?有一个定理给出了这个问题的答案,这就是LP基本定理.18

LP标准形的矩阵形式

其中19考虑具有标准形的LP:一、线性规划的基本概念

约束系数矩阵A是m×n矩阵,m≤n，并且r(A)＝m.

当m＝n时，基矩阵唯一;当m<n时，基矩阵就可能有多个，但数目不超过个。1.基矩阵:

若A中的m×m子矩阵B满足r(B)＝m,即则称B是LP问题的一个基矩阵（简称为基）。

于是A中至少有一个m×m子矩阵B，使得：r(B)＝m。约束方程的系数矩阵为：例1

设易看出r（A）=2，2阶子矩阵有=10个，而基矩阵只有9个，202.基向量:

基矩阵对应的列向量称为基向量，其余列向量称为非基向量.

3.基变量:

基向量对应的变量称为基变量，非基向量对应的变量称为非基变量(自由变量)。例如：对于基B2而言，x1,

x4是基变量，x2,

x3,

x5是非基变量。x1

x4思考：基变量的选取唯一吗？取法有多少种？【注】基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。4.基本解:

对于某一确定的基B，令所有的自由变量等于零,求出Ax=b的解，称这组解为LP问题的关于基Ｂ的基本解。5.基可行解:

非负的基本解称为基可行解（基本可行解）.【注】基可行解也被定义为“可行的基本解”。

22注:

基变量的选取方式

有限,

所以基本解的个数也为有限个.可见：求基可行解要先求基本解,然后看是否非负即可。另外，基本可行解也一定为有限个。二、基本解的求法例1

求的一个基本解和一个基本可行解.解:约束方程的增广矩阵x2

x4注意到A是2×4矩阵,r(A)＝2.由于第2列和第4列线性无关,构成一个2阶单位子块，因此可构成一个基矩阵.取为基变量,为自由变量,表示基变量得如下同解方程组:用自由变量又因该解非负，所以又是一个基本可行解。思考:若基变量选为其他变量时,如何求基本解呢?启发:若系数矩阵中含有m阶单位子块很容易求基本解.于是，得一个基本解：赠送精美图标1、字体安装与设置如果您对PPT模板中的字体风格不满意，可进行批量替换，一次性更改各页面字体。在“开始”选项卡中，点击“替换”按钮右侧箭头，选择“替换字体”。（如下图）在图“替换”下拉列表中选择要更改字体。（如下图）在“替换为”下拉列表中选择替换字体。点击“替换”按钮，完成。272、替换模板中的图片模板中的图片展示页面，您可以根据需要替换这