第3讲-LP图解法概要课件.ppt

《第3讲-LP图解法概要课件.ppt》由会员分享，可在线阅读，更多相关《第3讲-LP图解法概要课件.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划的图解法线性规划的图解法 1.确定可行解集合确定可行解集合R R，即即可行域可行域的图形的图形.2.2.作出作出目标函数等值线目标函数等值线.3.3.确定确定最优解最优解，记为，记为z*.z*.注：图解法仅适应与求解注：图解法仅适应与求解两个两个决策决策变量的变量的LPLP问题问题例例1 1：生产计划问题图解法求解生产计划问题图解法求解040D501003040解方程组：解方程组：得最优解：得最优解：雇工问题图解法雇工问题图解法365465 (2,32,3)图解法求解结果图解法求解结果有可能出现以下各种情形：有可能出现以下各种情形：（1）有最优解并且唯一；）有最优解并且唯一；（2）有最

2、优解但不唯一，有无穷多个；）有最优解但不唯一，有无穷多个；（3）因为可行域无界而不存在最优解；）因为可行域无界而不存在最优解；（4）可行域为空集，没有可行解。）可行域为空集，没有可行解。图解法求解（图解法求解（2）图解法求解（图解法求解（3）图解法求解（图解法求解（4）关于可行域与解的性质关于可行域与解的性质1.若可行域非空且有界，则可行域是一个凸多边若可行域非空且有界，则可行域是一个凸多边 形，其顶点个数为有限个；若可行域非空且无界，形，其顶点个数为有限个；若可行域非空且无界，其顶点个数也只有有限个。其顶点个数也只有有限个。2.若可行域非空且有界则必有最优解；若可行域若可行域非空且有界则必有

3、最优解；若可行域 非空且无界，则可能有最优解，也可能无最优解。非空且无界，则可能有最优解，也可能无最优解。3.若线性规划问题有最优解（不论可行域非空还若线性规划问题有最优解（不论可行域非空还是无界），其最优解必可以在某个顶点上面达到。是无界），其最优解必可以在某个顶点上面达到。最优解的个数或者唯一，或者有无穷多个。最优解的个数或者唯一，或者有无穷多个。关于线性规划问题关于线性规划问题 线性规划问题的如果有解，则可行域为凸集；线性规划问题的如果有解，则可行域为凸集；线性规划问题最优解存在，那么唯一最优解一定是可线性规划问题最优解存在，那么唯一最优解一定是可行域凸集的某个顶点；无穷最优解一定是可行

4、域的某行域凸集的某个顶点；无穷最优解一定是可行域的某个边或某个面；个边或某个面；线性规划线性规划问题的一般问题的一般解题思路解题思路：先找出凸集的任一顶：先找出凸集的任一顶点，计算该点出目标函数值，与其他顶点的目标函数点，计算该点出目标函数值，与其他顶点的目标函数值比较，如果该点值最大，那么该点就是最优解或最值比较，如果该点值最大，那么该点就是最优解或最优解之一；如果不是，那么就对目标函数值比该点大优解之一；如果不是，那么就对目标函数值比该点大的另一点重复上述过程，直到找到最优解。的另一点重复上述过程，直到找到最优解。线性规划问题的标准型线性规划问题的标准型为了论述方便，通常把为了论述方便，通

5、常把最大化、等式约束型最大化、等式约束型的线性规划的线性规划称为线性规划的标准型：称为线性规划的标准型：标准型的转化标准型的转化对于各种非标准型的线性规划都可以通过适当的方法变换为对于各种非标准型的线性规划都可以通过适当的方法变换为等价等价的标准型问题，的标准型问题，具体方法如下：具体方法如下：目标函数最小化：可令目标函数最小化：可令z=-z,得到得到max z=-z;约束方程为不等式：约束方程为不等式：如果是如果是不等式不等式约束约束，则可在，则可在 的左端加入一个的左端加入一个非负松弛非负松弛变量变量，把原，把原不等式不等式约束约束变成等式变成等式约束约束；如果是如果是不等式不等式约束约束，则可在，则可在 的左端减去一个的左端减去一个非负剩余变非负剩余变量量，把原，把原不等式不等式约束约束变成等式变成等式约束约束；存在存在取值无约束取值无约束的决策变量的决策变量xk：可令可令xk=xk-xk，其中其中xk 0，xk 0练习：化为标准型练习：化为标准型注：注：x x3 3无约束无约束作业作业复习：复习：LP的图解方法与标准型。的图解方法与标准型。预习：预习：单纯形法与对偶理论单纯形法与对偶理论。作业：习题作业：习题 3.1；习题；习题 3.2 谢谢 谢！谢！再再 见！见！