第二章3线性规划问题的图解法.ppt

第三节 线性规划问题的图解法 本节主要介绍图解法求解线性规划问题本节主要介绍图解法求解线性规划问题的基本过程及可行域、等值线、顶点等概念的基本过程及可行域、等值线、顶点等概念 对对对对于于于于不不不不超超超超过过过过三三三三个个个个变变变变量量量量的的的的线线线线性性性性规规规规划划划划问问问问题题题题，可可可可以以以以画画画画成成成成平平平平面面面面图图图图或或或或立立立立体体体体图图图图用用用用图图图图解解解解法法法法求求求求解解解解，它它它它虽虽虽虽然然然然没没没没有有有有多多多多大大大大是是是是实实实实用用用用价价价价值值值值，但但但但简简简简单单单单直直直直观观观观，有有有有助助助助于于于于了了了了解解解解线线线线性性性性规规规规划划划划问问问问题题题题求求求求解解解解的的的的基基基基本本本本原原原原理理理理。下下下下面面面面通通通通过过过过一一一一 道例题的求解来讲述图解法的基本过程。道例题的求解来讲述图解法的基本过程。道例题的求解来讲述图解法的基本过程。道例题的求解来讲述图解法的基本过程。第三节 线性规划问题的图解法 max Z=10 x1+5x2 3x1+4x2 9 5x1+2x2 8 x1，x2 0 解解：分分析析：初初等等数数学学中中已已经经学学过过，3x1+4x2 9 在在以以x1、x2 为为坐坐标标轴轴的的直直角角坐坐标标系系中中，表表示示以以直直线线3x1+4x2=9为边界的半平面，如图示：为边界的半平面，如图示：第三 节 线性规划问题的图解法第三 节 线性规划问题的图解法第三节 线性规划问题的图解法两两两两个个个个区区区区域域域域的的的的公公公公共共共共部部部部分分分分（交交交交集集集集）中中中中的的的的每每每每一一一一点点点点（包包包包括括括括边边边边界界界界上上上上的的的的点点点点）都都都都满满满满足足足足所所所所有有有有的的的的约约约约束束束束条条条条件件件件，每每每每一一一一点点点点的的的的坐坐坐坐标标标标值值值值都都都都是是是是线线线线性性性性规规规规划划划划问问问问题题题题的的的的一一一一个个个个解解解解（称称称称为为为为可可可可行行行行解解解解）。满满满满足足足足线线线线性性性性规划问题所有约束条件的一切点的集合称为可行域。规划问题所有约束条件的一切点的集合称为可行域。规划问题所有约束条件的一切点的集合称为可行域。规划问题所有约束条件的一切点的集合称为可行域。另另另另外外外外，目目目目标标标标函函函函数数数数Z Z=10 x=10 x1 1+5x+5x2 2 在在在在坐坐坐坐标标标标平平平平面面面面上上上上表表表表示示示示以以以以z z为为为为参参参参数数数数以以以以-2-2（-10/5=-2-10/5=-2）为为为为斜斜斜斜率率率率的的的的一一一一族族族族平平平平行行行行直直直直线线线线。位位位位于于于于这这这这条条条条直直直直线线线线上上上上所所所所有有有有点点点点具具具具有有有有相相相相同同同同的的的的函函函函数数数数值值值值，因因因因而而而而称称称称它它它它为为为为“等等等等值值值值线线线线”。考考考考虑虑虑虑到到到到x x1 1 ，x x2 2 0 0 时时时时，它它它它表表表表示示示示一一一一族族族族平平平平行行行行线线线线段段段段，线线线线段段段段的的的的两两两两个个个个端端端端点点点点在在在在第第第第一一一一象象象象限限限限的的的的坐坐坐坐标标标标轴轴轴轴上上上上，并并并并随随随随着着着着z z值值值值的的的的增增增增大大大大向向向向上上上上（沿沿沿沿着着着着法法法法线线线线方方方方向向向向，法法法法线线线线是是是是与与与与直直直直线线线线垂垂垂垂直直直直的的的的直线）滑动。直线）滑动。直线）滑动。直线）滑动。第三节 线性规划问题的图解法第三 节 线性规划问题的图解法 图解法求解线性规划问题的步骤图解法求解线性规划问题的步骤n建建立立直直角角坐坐标标系系，根根据据约约束束条条件件作作出出线线性性规规划划问问题题的的可行域（若无可行域则该问题无解）。可行域（若无可行域则该问题无解）。n求求出出可可行行域域顶顶点点的的坐坐标标，并并计计算算每每一一顶顶点点对对应应的的目目标标函数值。函数值。n选选出出目目标标函函数数值值最最大大（最最小小）的的顶顶点点坐坐标标就就是是该该问问题题的的最最优优解解。若若同同时时在在两两个个顶顶点点取取得得最最优优值值，那那么么以以这这两两个个顶顶点点为为端端点点的的线线段段上上任任意意一一点点都都能能使使目目标标函函数数值值达到最大（小），该问题一定有多重解达到最大（小），该问题一定有多重解。n n（关关于于图图解解法法中中解解的的讨讨论论请请参参阅阅文文献献（1 1）、（2 2）中有关章节的内容）中有关章节的内容）第三 节 线性规划问题的图解法