第六章线性规划第一讲.pptVIP

第六章 线性规划建模及单纯形法 1.线性规划的概念 例6.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 1.线性规划的概念 对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 ≤75 ；另外，产品数不可能为负，即 x1 ,x2 ≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2 。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型： 1.线性规划的概念 目标函数 Max z =1500x1+2500x2? 约束条件 s.t. 3x1+2x2≤ 65 2x1+x2≤ 40 3x2≤ 75 x1 ,x2 ≥0? 1.线性规划的概念 这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subject to”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2 的取值。 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 标准型要求 min z = C x ? max z’= -Cx ……= -bi, 两边乘 (-1) ? …… = bi; …… b, 左加松驰变量?…… +xi+1 = bi; …… b, 左减剩余变量?…… - xi+1 = bi; 无约束变量x ? x=x’-x”, x’ 0, x” 0 注： 标准形在单纯形法中用. 1.线性规划的概念 1.线性规划的概念 1.线性规划的概念 2.线性规划的图解法 线性规划的图解法(解的几何表示)对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下： (1)分别取决策变量x1 ,x2 为坐标向量建立直角坐标系。 2.线性规划的图解法 （2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域(存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。然后进行（3）。否则该线性规划问题无可行解。 2.线性规划的图解法 （3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 设有一线性规划问题表达式(包括目标函数、约束条件)如下?????max?? f＝50X1 ＋40X2????? ? X1＋X2≤450????????????????????????????? ?(1)?????? ?2 X1＋X2≤800??????????????????????????? (2)??????? X1＋3 X2≤900??????????????????????????? (3)??????? X1，X2≥0???????????????????????????????? (4)??????? 以X1 ，X2为坐标，当式(l)为等式，即X1 ＋X2＝450时，在X1 ，X2坐标系，它是一条直线，但式(l)不是等式，而是X1 ＋X2≤450，即在式(1)表示的约束条件中给定的不仅是在直线上的所有点，而是在直线X1 ＋X2= 450左下部一个广大的区域(包括直线在内的阴影线部分)，见图，例如X1 ＝0、X2=0， X1 ＝-5、X2=0, X1 =3、X2=-3等等,都是满足式(1)的点。 同理，也可以在X1 ，X2坐标系中画出式(2)、(3)、(4)所决定的4条直线，连同式(1)，共5条直线，如图所示。?????? ?由图所示的5条直线所围成的一个凸多边形，就是约束条件给定的区域，其中所有的点都满足约束条件的要求。实际上，它表示一个由凸多边形内