《2_2线性规划的图解法.ppt》由会员分享，可在线阅读，更多相关《2_2线性规划的图解法.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上页上页上页上页下页下页下页下页返回返回返回返回v 线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果v 由图解法得到的启示由图解法得到的启示第二节第二节 线性规划的图解法线性规划的图解法继续继续继续继续返回返回返回返回上页上页上页上页下页下页下页下页返回返回返回返回x1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=85例例1上页上页上页上页下页下页下页下页返回返回返回返回246x1x2246最优解X=(3,1)最优值Z=5(3,1)min Z=x1+2x2例例2上页上页上页上页下页下页下页下页返回返回返回返回246x1x2246有
2、无穷多个最优解即具有多重解,通解为X（2）（3,1）X（1）（1,3）01 如：当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)min Z=5x1+5x2例例3上页上页上页上页下页下页下页下页返回返回返回返回246x1x2246无界解(无最优解)max Z=x1+2x2例例4上页上页上页上页下页下页下页下页返回返回返回返回x1x2O10203040102030405050无可行解即无最优解max Z=3x1+4x2例例5上页上页上页上页下页下页下页下页返回返回返回返回由以上例题可知，线性规由以上例题可知，线性规划的解有划的解有4种形式种形式：1.有唯一最优解有唯一最
3、优解(例例1例例2)2.有多重解有多重解(例例3)3.有无界解有无界解(例例4)4.无可行解无可行解(例例5)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解上页上页上页上页下页下页下页下页返回返回返回返回 基本概念凸集：上页上页上页上页下页下页下页下页返回返回返回返回 极点:若K是凸集，XK；若X不能用不同的两点 的线性组合表示为：则X为极点.凸集凸集上页上页上页上页下页下页下页下页返回返回返回返回可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在若线性规划问题存在
4、最优解，它一定可以在若线性规划问题存在最优解，它一定可以在若线性规划问题存在最优解，它一定可以在可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的若两个顶点同时得到最优解，则其连线上的所有点都是最优解。所有点都是最优解。所有点都是最优解。所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函解题思路：找出凸集的顶点，计算其目标函数值，比较即得。数值，比较即得。数值，比较即得。数值，比
5、较即得。上页上页上页上页下页下页下页下页返回返回返回返回练习：练习：用图解法求解用图解法求解LP问题问题 上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16可行域可行域ABCDE上页上页上页上页下页下页下页下页
6、返回返回返回返回图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)34x1+40 x2=272上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法（练习）（练习）18 16 14 12 10 8 6 4 2 0|24681012141618x1x24x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)上页上页上页上页下页下页下页下页返回返回返回返回图解法图解法（练习）（练习）x218 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18上页上页上页上页下页下页下页下页返回返回返回返回第二节第二节 线性规划的图解法线性规划的图解法返回返回返回返回