[人力资源管理]21三-24线性规划与单纯形方法.ppt

复习：标准型的化法 (1)min→max ∵ min z = cx = -max(-z) ∴ max(-z) = -min z = -cx 令z’ = -z 则max z’ = -cx min z = -x1+2x2-3x3 x1+ x2+ x3 ≤ 7 ① x1- x2+ x3 ≥ 2 ② -3x1+ x2+2x3 = 5 ③ x1,x2 ≥ 0，x3无约束 min z = -x1+2x2-3x3 x1+ x2+ x3 ≤ 7 ① x1- x2+ x3 ≥ 2 ② -3x1+ x2+2x3 = 5 ③ x1,x2 ≥ 0，x3无约束 三、线性规划问题的解 设线性规划为 max z = CX ① AX = b ② X ≥ 0 ③ A为m × n矩阵, n m, Rank A = m (A为行满秩矩阵） 4.基解：取B = (p1,p2,···,pm) a11,···,a1m x1 a1m+1,···,a1n xm+1 b1 ┆ ┆ ┆ + ┆ ┆ ┆ = ┆ am1,···,amm xm amm+1,···,amn xn bm ↑ ↑ ↑ ↑ 基 基变量 非基 非基变量 令 xm+1 = ··· = xn = 0 (非基变量为0) 则 BXB = b ∴ 5.基可行解 满足③式要求的基解。 7.实例：找出下列线性规划问题的全部基解，基可行解，并找出最优解 一、图解法引例 max z = 2x1 + 3x2 1x1 + 2x2 ≤ 8 ① 4x1 ≤ 16 ② 4x2 ≤ 12 ③ x1，x2 ≥ 0 首先取z = 0，然后，使z逐 渐增大，直至找到最优解所对 应的点。 二、讨论 (1)唯一最优解 max z = z*时，解唯一，如上例。 (3)无界解 max z = 2x1 + 3x2 4x1 ≤ 16 x1，x2 ≥ 0 则x2 → ∞，z → ∞。 即存在无界解。 在实际问题中，可能 是缺少约束条件。 (4)无可行解 max z = 2x1 + 3x2 2x1 + 4x2 ≥ 8 x1 + x2 ≤ 1 x1，x2 ≥ 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错误。 三、由图解法得到的启示 图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的解题思路以及几何上直观得到的一些概念判断，对将要学习的单纯形法有很大启示： (1)求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解。 (2)若线性规划问题的可行域存在，则可行域是一个凸集，顶点个数只有有限个。 (3)若可行域非空且有界则必有最优解，若可行域无界，则可能有最优解，也可能无最优解。 (4)若最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。 先找出凸集的任一顶点，计算顶点处的目标函数值。 比较周围相邻顶点的目标函数值是否比这个大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值大的另一顶点，重复上述过程，直到找到最优解。 第三节 单纯形法 一、基本定理 单纯形法基本思路： 从可行域的一个顶点到另一个顶点迭代求最优解。 2.观察法 max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 ≥ 0 3.人工基 max z = x1 + 2x2 + 3x3 x1 + 3x2 + 2x3 = 3 2x1 + x2 + x3 = 4 x1,x2,x3 ≥ 0 三、从初始基可行解转换为另一基可行解 系数