C2LP标准形式及解的概念和解的几何意义

《C2LP标准形式及解的概念和解的几何意义》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、运筹学李健lijian@mail.buct.edu.cn北京化工大学经济管理学院讨论区orppt07@126.comorppt123456上节内容提要绪论运筹学的简史运筹学的性质和特点运筹学的工作步骤运筹学的模型运筹学的应用运筹学的展望线性规划与单纯形法线性规划问题及其数学模型问题的提出图解法9/19/20212北京化工大学经管学院§1.2图解法12345678123456⑵⑶⑷x2x1(42)0唯一最优解9/19/20213北京化工大学经管学院⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2x29/19/20214北京化工大学经管学院⑴⑵x1x2无

2、可行解§2.2图解法图解法直观、简便，适合变量数为三个以下的情形。变量数超过三个时怎么求解？LinearProgramming(LP)解的情况唯一解（例1）无穷解（例2）无界解（例3）无可行解（例4）有最优解无最优解9/19/20216北京化工大学经管学院本节内容提要线性规划与单纯形法线性规划问题及其数学模型问题的提出图解法线性规划问题的标准形式线性规划问题解的概念线性规划问题的几何意义基本概念几个定理9/19/20217北京化工大学经管学院§1.3线性规划问题的标准形式模型的一般数学形式线性规划模型的一般形式为9/19/20218北京化工大

3、学经管学院§1.3线性规划问题的标准形式LP模型的一般形式为LP模型的标准形式为1.目标函数为求极大值；2.所有约束（除非负约束）都是等式，右端常数项为非负；3.变量为非负。9/19/20219北京化工大学经管学院§1.3线性规划问题的标准形式此外，标准型还有向量和矩阵两种表示形式。9/19/202110北京化工大学经管学院向量形式：9/19/202111北京化工大学经管学院§1.3线性规划问题的标准形式LP标准形式的向量表述9/19/202112北京化工大学经管学院矩阵形式：9/19/202113北京化工大学经管学院§1.3线性规划问题的标

4、准形式LP标准形式的矩阵表述线性规划的数学模型一般变换为标准型后求解！如何变换为标准型？9/19/202114北京化工大学经管学院§1.3线性规划问题的标准形式转换方式：⑴目标函数的转换如果是求极小值即，则可将目标函数乘以（－1），可化为求极大值问题。也就是：令，可得到上式。即注意：Min型化为Max型后，最优解不变，但最优值差负号！9/19/202115北京化工大学经管学院⑵.约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量9/19/202116北京化工大学经管学院⑶.变量的变换若存在取值无约束的变量，可令其中：例一、将下列线性

5、规划问题化为标准形式为无约束（无非负限制）9/19/202117北京化工大学经管学院解:用替换，且，将第3个约束方程两边乘以（－1）将极小值问题反号，变为求极大值标准形式如下：引入变量9/19/202118北京化工大学经管学院§1.3线性规划问题的标准形式任何形式的LP模型都可以化为标准型！9/19/202119北京化工大学经管学院练习：将下面线性规划问题化为标准型为无约束解：9/19/202120北京化工大学经管学院内容提要线性规划与单纯形法线性规划问题及其数学模型问题的提出图解法线性规划问题的标准形式线性规划问题解的概念线性规划问题的几何

6、意义基本概念几个定理9/19/202121北京化工大学经管学院⑴可行解：满足约束条件(1-5)(1-6)的解为可行解。所有解的集合为可行解的集或可行域。⑵最优解：使目标函数达到最大值的可行解。⑶基：B是矩阵A中m×m阶非奇异子矩阵(∣B∣≠0），则B是一个基。同时称Pj(j=12……m)为基向量。相应的Xj为基变量，否则为非基变量。§1.4线性规划问题解的概念⑷基解：令非基变量等于0，就可以求出一个基解。满足(1-5)，但不必满足(1-6)的所有基解，最多为个。⑸基本可行解：满足非负约束条件的基解，简称基可行解。⑹可行基：对应于基可行解的基称

7、为可行基。非可行解可行解基解基可行解§1.4线性规划问题解的概念9/19/202123北京化工大学经管学院令非基变量x1＝0，x2＝0则得：X＝(0,0,3,1)T基本解2）：基变量为x2、x3，非基变量为x1、x4令非基变量x1＝0，x4＝0得：X＝(0,－1,5,0)T基本解／不是基本可行解／基本可行解例讨论下述约束方程的解x1＋2x2＋x3＝32x1－x2＋x4＝1系数矩阵为：1）：基变量为x3、x4，非基变量为x1、x23）X＝(1/2,1/2,3/2,1/2)T／不是基本解可行解／不是基本可行解9/19/202124北京化工大学经管

8、学院内容提要线性规划与单纯形法线性规划问题及其数学模型问题的提出图解法线性规划问题的标准形式线性规划问题解的概念线性规划问题的几何意义基本概念几个定理9/19/20