线性规划图解法和标准化.pptx

会计学1线性规划图解法和标准化线性规划图解法和标准化2几何概念几何概念代数概念代数概念 直 线满足一个等式约束的解 半平面满足一个不等式约束的解半平面的交集：凸多边形满足一组不等式约束的解目标函数等值线：一组平行线 目标函数值等于一个常数的解1图图 解解 法法注：当目标函数求极大时，等值线向右移；当目标函数求极小时，等值线向左移。注：当目标函数求极大时，等值线向右移；当目标函数求极小时，等值线向左移。第2页/共22页第1页/共22页311图图图图 解解解解 法法法法 (1)(1)分别取决策变量分别取决策变量X X1 1和和X X2 2为横轴和纵轴，建立直角坐标系。为横轴和纵轴，建立直角坐标系。在直角坐标系中，图上任意一点的坐标代表了决策变量的在直角坐标系中，图上任意一点的坐标代表了决策变量的一组取值，例一组取值，例1 1的每个约束条件都代表一个半平面。的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0第3页/共22页第2页/共22页411图图图图 解解解解 法法法法（2 2）对每个不等式）对每个不等式(约束条件约束条件)，先取其等式在坐标系中作直，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400第4页/共22页第3页/共22页511图图图图 解解解解 法法法法（3 3）把五个图合并成一个图，取各约束条件的公共部分，如）把五个图合并成一个图，取各约束条件的公共部分，如图图3-13-1所示。所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图3-1第5页/共22页第4页/共22页611图图图图 解解解解 法法法法（4 4）目标函数）目标函数Z=50 xZ=50 x1 1+100 x+100 x2 2，当，当Z Z取某一固定值时得到一条取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为直线，直线上的每一点都具有相同的目标函数值，称之为“等值线等值线”。平行移动等值线，。平行移动等值线，当移动到当移动到B B点时，点时，Z Z在可在可行域内实现了最大化行域内实现了最大化。A A，B B，C C，DD，E E是可行域的顶点，是可行域的顶点，对有限个约束条件，则其可行域的顶点也是有限的。对有限个约束条件，则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图3-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE第6页/共22页第5页/共22页7例例2 2 maxmax z=x z=x1 1+3x+3x2 2s.t.s.t.x x1 1+x+x2 266-x-x1 1+2x+2x2 288x x1 1 0,x0,x2 200可行域目标函数等值线最优解64-860 x1x211图图图图 解解解解 法法法法第7页/共22页第6页/共22页8进进进进 一一一一 步步步步 讨讨讨讨 论论论论 例例例例3 3 3 3 某公司由于生产需要，共需要某公司由于生产需要，共需要A A、B B两种原料至少两种原料至少350350吨（吨（A A，B B两种材料有一定替代性），其中两种材料有一定替代性），其中A A原料至少购进原料至少购进125125吨。但由于吨。但由于A A，B B两种原料的规格不同，各自所需的加工时间两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨也是不同的，加工每吨A A原料需要原料需要2 2个小时，加工每吨个小时，加工每吨B B原料需原料需要要1 1小时，而公司总共有小时，而公司总共有600600个加工小时。又知道每吨个加工小时。又知道每吨A A原料的原料的价格为价格为2 2万元，每吨万元，每吨B B原料的价格为原料的价格为3 3万元，试问在满足生产需万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买要的前提下，在公司加工能力的范围内，如何购买A A、B B两种两种原料，使得购进成本最低？原料，使得购进成本最低？第8页/共22页第7页/共22页9进进进进 一一一一 步步步步 讨讨讨讨 论论论论解：目标函数：解：目标函数：Min Z=2xMin Z=2x1 1+3 x+3 x2 2 约束条件：约束条件：s.t.xs.t.x1 1+x+x2 2 350 350 x x1 1 125125 2 x 2 x1 1+x+x2 2 600600 x x1 1 ,x,x2 2 0 0 采用图解法，如左图：得采用图解法，如左图：得QQ点坐点坐标（标（250250，100100）为最优解。）为最优解。100200300400500600100200300400600500 x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1 x2 Q第9页/共22页第8页/共22页10重要结论1：线性规划的可行域是凸集线性规划的可行域是凸集可行域的顶点为有限个可行域的顶点为有限个线性规划的最优解一定可以在某个顶点上实现线性规划的最优解一定可以在某个顶点上实现凸集凸集不是凸集顶点1图图 解解 法法第10页/共22页第9页/共22页111图图 解解 法法 重要结论重要结论重要结论重要结论2 2：n n如果线性规划有如果线性规划有唯一最优解唯一最优解（例（例1 1、2 2、3 3），则一定有一个可行域的顶点对），则一定有一个可行域的顶点对应最优解；应最优解；n n无穷多个最优解无穷多个最优解。若将例。若将例1 1中的目标中的目标函数变为函数变为max z=50 xmax z=50 x1 1+50 x+50 x2 2，则线段，则线段BCBC上的所有点都代表最优解；上的所有点都代表最优解；n n无界解无界解。即可行域的范围延伸到无穷。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一般来说，这说明模型有错，忽略了一些必要的约束条件；一些必要的约束条件；n n无可行解无可行解。若在例。若在例1 1的数学模型中再的数学模型中再增加一个约束条件增加一个约束条件4x4x1 1+3x+3x2 212001200，则可，则可行域为空域，不存在满足约束条件的行域为空域，不存在满足约束条件的解，当然也就不存在最优解。解，当然也就不存在最优解。第11页/共22页第10页/共22页1222线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化一般形式一般形式一般形式一般形式目标函数：目标函数：Max Max（MinMin）Z=cZ=c1 1 x x1 1+c+c2 2 x x2 2+c+cn n x xn n 约束条件：约束条件：s.t.s.t.a a1111 x x1 1+a a1212 x x2 2+a a1n1n x xn n （=,=,）b b1 1 a a2121 x x1 1+a a2222 x x2 2+a a2n2n x xn n （=,=,）b b2 2 a am1m1 x x1 1+a am2m2 x x2 2+a amnmn x xn n （=,=,）b bmm x x1 1，x x2 2，x xn n 0 0 n n标准形式标准形式标准形式标准形式目标函数：目标函数：MaxMax Z =c Z =c1 1 x x1 1+c+c2 2 x x2 2+c+cn n x xn n 约束条件：约束条件：s.t.s.t.a a1111 x x1 1+a a1212 x x2 2+a a1n1n x xn n =b b1 1 a a2121 x x1 1+a a2222 x x2 2+a a2n2n x xn n =b b2 2 a am1m1 x x1 1+a am2m2 x x2 2+a amnmn x xn n =b bmm x x1 1，x x2 2，x xn n 0 0，b bi i 0 0 注：只能使用一个脚码（变量连续编号），不能使用多重脚码注：只能使用一个脚码（变量连续编号），不能使用多重脚码第12页/共22页第11页/共22页1322线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化 可以看出，线性规划的标准形式有如下四个特点：可以看出，线性规划的标准形式有如下四个特点：n n目标极大化；目标极大化；n n约束条件为等式；约束条件为等式；n n决策变量均非负；决策变量均非负；n n约束条件右端常数项非负。约束条件右端常数项非负。对于各种非标准形式的线性规划问题，我们总可对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式以通过以下变换，将其转化为标准形式:第13页/共22页第12页/共22页1422线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化1 1 1 1、变量不是大于等于、变量不是大于等于、变量不是大于等于、变量不是大于等于0 0 0 0的问题的问题的问题的问题（1 1）若）若x xj j0,0,令令 x x x xj j j j=-=-=-=-x x x xj j j j，则则x xj j00（2 2）若变量为无约束）若变量为无约束 在在标标准准形形式式中中，必必须须每每一一个个变变量量均均有有非非负负约约束束。当当某某一个变量一个变量x xj j没有非负约束时，可以令：没有非负约束时，可以令：x x x xj j j j=x x x xj j j j-x x x xj j j j”其中其中 x xj j 00，x xj j”00 即即用用两两个个非非负负变变量量之之差差来来表表示示一一个个无无符符号号限限制制的的变变量量，当然当然x xj j的符号取决于的符号取决于x xj j 和和x xj j”的大小。的大小。第14页/共22页第13页/共22页1522线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化2 2 2 2、目标函数为极小化的问题：、目标函数为极小化的问题：、目标函数为极小化的问题：、目标函数为极小化的问题：设目标函数为：设目标函数为：Min Min Z Z=c c1 1x x1 1 +c c2 2x x2 2 +c cn nx xn n (可以可以)令令 Z Z -Z-Z ，则该极小化问题与下面的极大化问题有相同的最优解，则该极小化问题与下面的极大化问题有相同的最优解，即：即：Max Max Z Z =-c-c1 1x x1 1 -c-c2 2x x2 2-c-cn nx xn n 但必须注意，尽管以上两个问题的最优解相同，但它们但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即：最优解的目标函数值却相差一个符号，即：Min Min Z Z -Max-Max Z Z 3 3、右端常数项为负数的问题：、右端常数项为负数的问题：在标准形式中，要求约束条件右端常数项必须全部是非负的。当某个右端常数项为负时，如 bi0，则把该约束条件两端同时乘以(-1)，得到：-ai1 x1-ai2 x2-ain xn=-bi第15页/共22页第14页/共22页1622线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化4 4 4 4、约束条件不是等式的问题：、约束条件不是等式的问题：、约束条件不是等式的问题：、约束条件不是等式的问题：设约束条件为设约束条件为 a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n b bi i 可可以以引引进进一一个个新新的的变变量量s s s s ，使使它它等等于于约约束束右右边边与与左左边边之差之差 s s=b bi i(a ai1 i1 x x1 1 +a ai2 i2 x x2 2 +a ain in x xn n )显然，显然，s s 也具有非负约束，即：也具有非负约束，即：s s 00，这时新的约束条件成为这时新的约束条件成为 a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n+s s=b bi i第16页/共22页第15页/共22页1722线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化 当约束条件为当约束条件为 a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n b bi i 时，时，类似地令类似地令 s s=(=(a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n)-)-b bi i 显显然然，s s 也也具具有有非非负负约约束束，即即s s00，这这时时新新的的约约束条件成为束条件成为 a ai1 i1 x x1 1+a ai2 i2 x x2 2+a ain in x xn n-s s=b bi i第17页/共22页第16页/共22页1822线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化 为了使为了使约束由不等式成为等式而引进的变量约束由不等式成为等式而引进的变量s,s,当不等当不等式为式为“小于等于小于等于”时称为时称为“松弛变量松弛变量”；当不等式为；当不等式为“大大于等于于等于”时称为时称为“剩余变量剩余变量”。如果原问题中有若干个非。如果原问题中有若干个非等式等式约束条件，则将其转化为标准形式时，必须对各个约约束条件，则将其转化为标准形式时，必须对各个约束条件引进不同的松弛变量或剩余变量。束条件引进不同的松弛变量或剩余变量。结论：当约束条件为：结论：当约束条件为：结论：当约束条件为：结论：当约束条件为：“”：在约束条件的左端加入非负的松弛变量：在约束条件的左端加入非负的松弛变量：在约束条件的左端加入非负的松弛变量：在约束条件的左端加入非负的松弛变量 “”：在约束条件的左端减去非负的剩余变量：在约束条件的左端减去非负的剩余变量：在约束条件的左端减去非负的剩余变量：在约束条件的左端减去非负的剩余变量注：注：注：注：*松弛变量和剩余变量在目标函数中的系数为松弛变量和剩余变量在目标函数中的系数为松弛变量和剩余变量在目标函数中的系数为松弛变量和剩余变量在目标函数中的系数为0 0 0 0*第18页/共22页第17页/共22页19例例例例4 4：将下列线性规划模型标准化：将下列线性规划模型标准化：将下列线性规划模型标准化：将下列线性规划模型标准化：22线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化第19页/共22页第18页/共22页2022线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化第20页/共22页第19页/共22页2122线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化例例例例5 5：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式 Min Min f f =2 =2 x x1 1-3-3x x2 2+4 +4 x x3 3 s.t.3 s.t.3 x x1 1 +4+4x x2 2-5 -5 x x3 3 6 6 2 2 x x1 1 +x x3 3 8 8 x x1 1 +x x2 2 +x x3 3 =-9 =-9 x x1 1,x x2 2,x x3 3 0 0解：首先，将目标函数转换成极大化：解：首先，将目标函数转换成极大化：令令 z z=-=-f f=-2=-2x x1 1+3+3x x2 2-4-4x x3 3 其其次次考考虑虑约约束束条条件件，有有2 2个个不不等等式式约约束束，引引进进松松弛弛变变量量X X4 4和和剩余变量剩余变量x x5 5 。第三个约束条件的右端常数项为负，在等式两边同时乘第三个约束条件的右端常数项为负，在等式两边同时乘-1-1。第21页/共22页第20页/共22页2222线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化 通通过过以以上上变变换换，可可以以得得到到以以下下标标准准形形式式的的线线性规划问题：性规划问题：Max z=-2x1+3 x2-4x3 s.t.3x1+4x2-5x3 +x4 =6 2x1 +x3 -x5 =8 -x1 -x2 -x3 =9 x1,x2,x3,x4,x5 0第22页/共22页第21页/共22页