(运筹学1.pptVIP

运 筹 学( Operations Research ) Chapter1 线性规划 (Linear Programming) 线性规划问题的数学模型 1. 规划问题 线性规划问题的数学模型 例1.1 如图所示，如何截取x使铁皮所围成的容积最大？ 线性规划问题的数学模型 线性规划问题的数学模型 解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为： 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 3. 线性规划问题的标准形式 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 线性规划问题的数学模型 4. 线性规划问题的解 线性规划问题的数学模型 线性规划问题的数学模型 例1.4 求线性规划问题的所有基矩阵。 线性规划问题的数学模型 基解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 XB =B-1b ， XN=0 基可行解：满足变量非负约束条件的基本解，简称基可行解。XB≥0 ， XN=0 可行基：对应于基可行解的基称为可行基。 例4 在下述线性规划问题中，列出全部基、基解、基可行解和指出最优解。 图解法 线性规划问题的求解方法 图解法 1．什麽是图解法？ 线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。 图解法的步骤 1.建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度。 2.对约束条件加以图解，找出可行域。 3.画出目标函数等值线。 4.移动目标函数等值线，求出最优解。 图解法 例1.5 用图解法求解线性规划问题 由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。 图解法 解的几种情况 (1)唯一最优解 max z = z*时，解唯一，如上例，交于Q3。 [eg.] 对eg.1，若目标函数变为 z = 2x1 + x2，此时表示 目标函数的直线与Q2相切。 即最优解落在Q2（4，2）。 (2)无穷多最优解 [eg.] 对eg.1，若目标函数 z = 3x1 + 3x2，此时表示 目标函数的直线与表示 条件①的直线平行， 最优点在线段Q3Q2上。 即存在无穷多最优解。 (3)无界解 [eg.] max z = 2x1 + 3x2 4x1 ≤ 16 x1，x2 ≥ 0 则x2 → ∞，z → ∞。 即存在无界解。 在实际问题中，可能 是遗漏了约束条件。 (4)无可行解 [eg.] max z = 2x1 + 3x2 2x1 + 2x2 ≤ 12 x1 + 2x2 ≥ 14 x1，x2 ≥ 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错。 图解法 图解法 模型求解时，可得到如下几种解的状况： （1）唯一最优解：只有一点为最优解点，简称唯一解； （2）无穷多最优解：有许多点为最优解点，简称无穷多解； （3）无界最优解：最优解取值无界，简称无界解； （4）无可行解：无可行域，模型约束条件矛盾。 图解法 单纯形法基本原理 单纯形法基本原理 顶点——凸集中不成为任意两点连线上的点，称为凸集顶点。 设C是凸集，X?C；若C中不存在两个不同的点X（1） ?C，X（2） ?C 使 X=αX（1）+（1-α）X（2） （0α1） 则称X为C的一个顶点（也称为极点或角点）。 单纯形法基本原理 单纯形法的计算步骤 单纯形法的思路 单纯形法的计算步骤：表格法 1）将问题化为标准型。 2）求出线性规划的初始基可行解（观察法），列出初始单纯形表。 单纯形法的计算步骤 单纯形表 3）进行最优性检验： 最优性判别定理：若 是对应于B的基本可行解， ?j是用非基变量表示目标函数的表达式 中非基变量xj的检验数，若对于一 切非基变量的角指数 j 均有?j ≤0 则当前基本可行解为最优解。 无最优解判别定理：若 是对应于B的基本可行解， 非基变量x k的检验数?k 0 , 且对于i=1,2,……,