LP图解法概要课件

线性规划的图解法

1.确定可行解集合R，即可行域的图形.2.作出目标函数等值线.3.确定最优解，记为z*.注：图解法仅适应与求解两个决策变量的LP问题线性规划的图解法1.确定可行解集合R，即可行域的1

例1：生产计划问题图解法求解例1：生产计划问题图解法求解2040D501003040040D5010030403解方程组：得最优解：解方程组：得最优解：4雇工问题图解法365465(2,3)

雇工问题图解法3654655图解法求解结果有可能出现以下各种情形：（1）有最优解并且唯一；（2）有最优解但不唯一，有无穷多个；（3）因为可行域无界而不存在最优解；（4）可行域为空集，没有可行解。图解法求解结果有可能出现以下各种情形：6图解法求解（2）图解法求解（2）7图解法求解（3）图解法求解（3）8图解法求解（4）图解法求解（4）9关于可行域与解的性质1.若可行域非空且有界，则可行域是一个凸多边形，其顶点个数为有限个；若可行域非空且无界，其顶点个数也只有有限个。2.若可行域非空且有界则必有最优解；若可行域非空且无界，则可能有最优解，也可能无最优解。3.若线性规划问题有最优解（不论可行域非空还是无界），其最优解必可以在某个顶点上面达到。最优解的个数或者唯一，或者有无穷多个。关于可行域与解的性质1.若可行域非空且有界，则可行域是一10关于线性规划问题⑴线性规划问题的如果有解，则可行域为凸集；⑵线性规划问题最优解存在，那么唯一最优解一定是可行域凸集的某个顶点；无穷最优解一定是可行域的某个边或某个面；⑶线性规划问题的一般解题思路：先找出凸集的任一顶点，计算该点出目标函数值，与其他顶点的目标函数值比较，如果该点值最大，那么该点就是最优解或最优解之一；如果不是，那么就对目标函数值比该点大的另一点重复上述过程，直到找到最优解。关于线性规划问题⑴线性规划问题的如果有解，则可行域为凸集；11线性规划问题的标准型为了论述方便，通常把最大化、等式约束型的线性规划称为线性规划的标准型：线性规划问题的标准型为了论述方便，通常把最大化、等式约束型的12标准型的转化对于各种非标准型的线性规划都可以通过适当的方法变换为等价的标准型问题，具体方法如下：目标函数最小化：可令z’=-z,得到maxz’=-z;约束方程为不等式：如果是≤不等式约束，则可在≤的左端加入一个非负松弛变量，把原≤不等式约束变成等式约束；如果是≥不等式约束，则可在≥的左端减去一个非负剩余变量，把原≥不等式约束变成等式约束；

存在取值无约束的决策变量xk：可令xk=xk’-xk’’，其中xk’≥0，xk’’≥0标准型的转化对于各种非标准型的线性规划都可以通过适当的方法变13练习：化为标准型注：x3无约束练习：化为标准型注：x3无约束14作业复习：LP的图解方法与标准型。预习：单纯形法与对偶理论。作业：习题3.1；习题3.2作业复习：LP的图解方法与标准型。15

谢谢！再见！

16线性规划的图解法

1.确定可行解集合R，即可行域的图形.2.作出目标函数等值线.3.确定最优解，记为z*.注：图解法仅适应与求解两个决策变量的LP问题线性规划的图解法1.确定可行解集合R，即可行域的17

例1：生产计划问题图解法求解例1：生产计划问题图解法求解18040D501003040040D50100304019解方程组：得最优解：解方程组：得最优解：20雇工问题图解法365465(2,3)

雇工问题图解法36546521图解法求解结果有可能出现以下各种情形：（1）有最优解并且唯一；（2）有最优解但不唯一，有无穷多个；（3）因为可行域无界而不存在最优解；（4）可行域为空集，没有可行解。图解法求解结果有可能出现以下各种情形：22图解法求解（2）图解法求解（2）23图解法求解（3）图解法求解（3）24图解法求解（4）图解法求解（4）25关于可行域与解的性质1.若可行域非空且有界，则可行域是一个凸多边形，其顶点个数为有限个；若可行域非空且无界，其顶点个数也只有有限个。2.若可行域非空且有界则必有最优解；若可行域非空且无界，则可能有最优解，也可能无最优解。3.若线性规划问题有最优解（不论可行域非空还是无界），其最优解必可以在某个顶点上面达到。最优解的个数或者唯一，或者有无穷多个。关于可行域与解的性质1.若可行域非空且有界，则可行域是一26关于线性规划问题⑴线性规划问题的如果有解，则可行域为凸集；⑵线性规划问题最优解存在，那么唯一最优解一定是可行域凸集的某个顶点；无穷最优解一定是可行域的某个边或某个面；⑶线性规划问题的一般解题思路：先找出凸集的任一顶点，计算该点出目标函数值，与其他顶点的目标函数值比较，如果该点值最大，那么该点就是最优解或最优解之一；如果不是，那么就对目标函数值比该点大的另一点重复上述过程，直到找到最优解。关于线性规划问题⑴线性规划问题的如果有解，则可行域为凸集；27线性规划问题的标准型为了论述方便，通常把最大化、等式约束型的线性规划称为线性规划的标准型：线性规划问题的标准型为了论述方便，通常把最大化、等式约束型的28标准型的转化对于各种非标准型的线性规划都可以通过适当的方法变换为等价的标准型问题，具体方法如下：目标函数最小化：可令z’=-z,得到maxz’=-z;约束方程为不等式：如果是≤不等式约束，则可在≤的左端加入一个非负松弛变量，把原≤不等式约束变成等式约束；如果是≥不等式约束，则可在≥的左端减去一个非负剩余变量，把原≥不等式约束变成等式约束；

存在取值无约束的决策变量xk：可令xk=xk’-xk’’，其中xk’≥0，xk’’≥0标准型的转化对于各种非标准型的线性规划都可以通过适当的方法变29练习：化为标准型注：x3无约束练习：化为标准型