教学课件线性规划.ppt

第二章 线性规划 (Linear Programming) 2.1 线性规划问题的数学模型 1. 规划问题 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为： 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 3. 线性规划建模过程 （1）理解要解决的问题，了解解题的目标和条件； （2）定义决策变量（ x1 ，x2 ，… ，xn ），每一组值表示一个方案； （3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； （4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 其中，ci ——称为价值系数 aij——称为技术系数（或消耗系数） bi——称为资源系数 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 5. 线性规划问题的标准形式 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 2.1 线性规划问题的数学模型 6. 线性规划问题的解 2.1 线性规划问题的数学模型 2.2 图解法 线性规划问题的求解方法 2.2 图解法 max Z = 2X1 + X2 X1 + 1.9X2 ≥ 3.8 X1 - 1.9X2 ≤ 3.8 s.t. X1 + 1.9X2 ≤10.2 X1 - 1.9X2 ≥ -3.8 X1 ，X2 ≥ 0 2.2 图解法 2.2 图解法 2.2 图解法 min Z=5X1+4X2 2.2 图解法 2.2 图解法 2.2 图解法 2.2　图 解 法 学习要点： 3.结论 (1)当线性规划问题的可行域非空时，它是有界或无解凸多边形。 (2)若线性规划问题存在最优解，它一定在可行域的某个顶点获得。 (3)若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。 2.3 单纯形法基本原理 1.单纯形法的基本思路 基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。 2.3 单纯形法基本原理 1.单纯形法的基本概念 基：设A为约束条件②的m×n阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问题的一个基（矩阵）。设： 2.3 单纯形法基本原理 基本解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基本可行解：满足变量非负约束条件的基本解，简称基可行解。 可行基：对应于基本可行解的基称为可行基。 基本最优解： 最优解是基本可行解称为基本最优解。基本最优解对应的基称为最优基。 2.3 单纯形法基本原理 例2.6 求线性规划问题的所有基矩阵。 2.3 单纯形法基本原理 2.3 单纯形法基本原理 2.3 单纯形法的计算步骤 单纯形法的思路 2.3 单纯形法的计算步骤 单纯形表 2.3 单纯形法的计算步骤 例2.7 用单纯形法求下列线性规划的最优解 2.3 单纯形法的计算步骤 2）求出线性规划的初始基可行解，列出初始单纯形表。 2.3 单纯形法的计算步骤 3）进行最优性检验 2.3 单纯形法的计算步骤 用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。 5）重复3）、4）步直到计算结束为止。 2.3 单纯形法的计算步骤 2.3 单纯形法的计算步骤 例2.8 用单纯形法求解 2.3 单纯形法的计算步骤 2.3 单纯形法的计算步骤 2.4 单纯形法的进一步讨论－人工变量法 人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基