管理科学基础1线性规划03

1线性规划问题及其数学模型图解法单纯形法线性规划模型的应用线性规划2设备产品ABCD利润（元/件）P121402P222043有效台时1281612例：已知信息如右表所示，问如何安排生产才能获得最大利润？模型:maxZ=2x1+3x2s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0线性规划问题及其数学模型30012211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcZ)()((min)max目标函数：约束条件：①②③价值系数技术系数限额系数线性规划数学模型的一般形式4也可以记为如下形式：),2,,1(j0),2,,1(i)(Z(min)max11nxmbxaxcjnjijijnjjj目标函数：约束条件：5向量形式：),,,(21ncccCnxxX1mjjjaaP1mbbb10)((min)max1XbxPCXZnjjj决策变量向量价值向量资源向量系数列向量6矩阵形式：mnmnaaaaA11110)((min)maxXbAXCXZ系数矩阵7)n21,jm;21,(i0max11jinjjijnjjjxbxaxcZ特征：⑴目标函数为求最大值；⑵所有约束条件（非负条件除外）都是等式，右端常数项大于零；⑶变量为非负。①②③线性规划模型的标准形式8标准型转换方式：(1)如果极小化原问题minZ=CX，则令Z'=-Z，转为求maxZ'=-CX(2)若某个bi0，则以－1乘该约束两端，使之满足非负性的要求。(3)对于≤型约束，在左端加上一个非负松弛变量，使其为等式。(4)对于≥型约束，在左端减去一个非负剩余变量，使其为等式。(5)若某决策变量xk无非负约束，令xk=x'k-xk，(x'k≥0,xk≥0)。9转换方式：⑴目标函数的转换也就是：令，可得到上式。ZZ即如果是求最小值即，则可将目标函数乘以（－1），可化为求最大值问题。jjxcZminjjxcZZmax10⑵约束条件的转换：由不等式转换为等式。称为松弛变量称为剩余变量ijijbxa0iniinjijxbxxaijijbxa0iniinjijxbxxa11⑶变量的变换例1：将下列线性规划问题化为标准形式为无约束（无非负限制）,0,523247532min321321321321321xxxxxxxxxxxxxxxZ若存在取值无约束的变量，可令其中：jxjjjxxx0,jjxx12解:用x4-x5替换x3，且x4,x5=0，将第3个约束方程两边乘以（－1），再将最小值问题反号，变为求最大值。标准形式如下：76,xx引入变量0,,,,,5)(252)(7)(500)(32max76542154217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxZ13例2：将线性规划问题化为标准型为无约束解：,0435832min21212121xxxxxxxxZ0,,,,4)(35)(83)(2max6543164315431431xxxxxxxxxxxxxxxxZ作业1•将下面的线性规划模型转换成标准形式（标准型）15⑴可行解：满足所有约束条件的解为可行解。所有解的集合称为可行解的集或可行域。⑵最优解：使目标函数达到最优值的可行解。⑶基：若B是矩阵A的一个m×m阶非奇异子矩阵（∣B∣≠0），则B是一个基。),,,(211111mmmmmPPPaaaaB则称Pj(1≤j≤m)为基向量。∴xj(1≤j≤m)为基变量，其他变量为非基变量。线性规划问题的解16⑷基解(基本解)：非零分量的数目不大于约束方程个数m的解（对应着一个基），最多为个。⑸基可行解：满足所有非负约束条件的基解⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解Cmn17一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量，但需将一般形式变成标准形式线性规划模型的求解方法18建立直角坐标，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。例一:)0,(21xx0,012416482122232max2121212121xxxxxxxxxxZ⑴⑵⑶⑷图解法19012345678123456⑴⑵⑶⑷作图∴最优解：x1=4,x2=2，有唯一最优解，Z=14x2x1(42)00124164821222322121212121xxxxxxxxxxZ,max⑴⑵⑶⑷可行域20例二：例三：0,021223622max212212121xxxxxxxxxZ⑴⑵⑶无穷多最优解0,122max21212121xxxxxxxxZ⑴⑵无界解x1x1x2x2210,632123min2121211xxxxxxxxZ⑴⑵x1x2无可行解0,150510032170251810max2121212121xxxxxxxxxxZ0,4322232max212212121xxxxxxxxxZ例四:练习122解的情况唯一解无穷多最优解（多重最优解）无界解无可行解有最优解无最优解23凸集凸集不是凸集顶点线性规划问题的几何意义几个概念：1.凸集2.凸组合3.顶点24是否凸集？abcd25K是n维欧氏空间En的一个点集，若任意两点的连线上的所有点，则称K为凸集。凸集：KXK,X(2)(1)K)X-(1X(2)(1)1)(0凸组合：的凸组合。，，，为则称，）使（，，，个数的若存在总和为个点。中的维欧氏空间是，，，设(k)(2)(1)(k)k(2)2(1)1ik21n(k)(2)(1)XXXXXXXXk,1,2,i1,01EnXXXkk26顶点：1)(0)X-(1XXKXKXKXK(2)(1)(2)(1)的线性组合表示为和不能用不同的两点。若是凸集，设K则称X为K的一个顶点（或极点）。27几个定理定理1.若线性规划问题存在可行域，则其可行域是凸集0,|1jnjjjxbxPXD证明.设n,1,2,,0x,xn,1,2,,0x,x)x,x,(xX)x,x,(xX(2)j1(2)j(1)j1(1)jT(2)n(2)2(2)1(2)T(1)n(1)2(1)1(1)jbPjbPDnjjnjj有内任意不同的两点，则是，，，1)(0)X-(1XX)x,x,(xXXXX(2)(1)Tn21(2)(1)，则有，令内。均在两点的连线上任意点，只需证明D28是凸集。，，因此易知将它代入约束条件可得，的每个分量是DD0)x-(1x)x-(1xxX1(2)j(1)j1(2)j(1)jjXxbPxPjnjjnjjj引理1.线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量线性无关。几个定理29定理2.线性规划问题的基可行解X对应于可行域D的顶点。证明.不失一般性，设基可行解X的前m个分量为正，则bxPjjjm1分两步证明：（1）若X不是基可行解，则它不是可行域D的顶点。根据引理1，若X不是基可行解，则其正分量对应的系数列向量线性相关，即存在不全为0的数使得(1-8)-μ×(1-9)：mPPP,,,21i02211mmPPP(1-8)(1-9)b)()()(222111mmmPxPxPx几个定理30(1-8)-μ×(1-9)：b)()()(222111mmmPxPxPxb)()()(222111mmmPxPxPx(1-8)+μ×(1-9)：取]0,,0),(,),(),[(2211)1(mmxxxX]0,,0),(,),(),[(2211)2(mmxxxX)(21)2()1(XXX当μ充分小时，有0iix的顶点。不是可行域是可行解。因此与故DXXX)2()1(几个定理31（2）若X不是可行域D的顶点，则它不是基可行解。因为X不是可行域D的顶点，因此D内存在不同的两点T(2)n(2)2(2)1(2)T(1)n(1)2(1)1(1))x,x,(xX)x,x,(xX，，，1)(0)X-(1XX(2)(1)使得设X是基可行解，对应的向量组线性无关。当jm时，0xj0x0x)x-(1xx(2)j(1)j(2)j(1)jj，因此由于0)x(xxxm1(2)j(1)jm1(2)jm1(1)jjjjjjjPbPbP两式相减可得与将线性相关，矛盾！mPPP,,,21几个定理32引理2.若K是有界凸集，则任何一点可表示为K的顶点的凸组合。定理3.若可行域D有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。KX(m)1i(m)1i(i)1i(i)(0)1i1i(i)(0)(0)(0)(k)(2)(1)XXXXX1,XXXz*XXXXCCCCCCkikikikiki因此不是顶点。是可行域的顶点，，，，设几个定理33思路：先找一个基可行解（顶点），如不是最优，继续寻找下一个基可行解（顶点），直到找出最优为止。⑴线性规划问题的可行域（非空）是凸集（凸多边形）。（定理1）⑵若可行域是有界凸集，则最优解一定是在凸集的某一顶点实现（顶点数目不超过个）（定理3）结论：Cmn(3)线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。求解线性规划的一种有效方法（1947，丹捷格/丹齐克），该方法被誉为20世纪十大算法之一。20世纪创造经济效益最多的算法。将模型的一般形式转化成标准形式，再根据标准型从可行域中找一个基可行解，并判断是否最优解。如果不是，继续寻找另一个基可行解，当目标函数达到最优时，得到最优解。基本思想单纯形法35例1：转换成标准型：0,1241648232max21212121xxxxxxxxZ1,2,3,4,5)(j01241648200032max524132154321jxxxxxxxxxxxxxZ单纯形法36约束条件的系数矩阵54321PPPPP100400100400121AIB100010001PPP543543,,xxx21xx,为基变量为非基变量I为单位矩阵37令：21x,61x8,x054321xx则：∴基可行解为（0，0，8，16，12）T此时，Z=0然后，找另一个基可行解（需要将非基变量换入基变量中，并从基变量中找到一个换出变量）。如此循环下去，直到找到最优解为止。38找出一个初始可行解是否最优转移到另一个目标函数（找更优的基可行解）最优解是否循环结束其步骤总结如下：39为换入变量，令01x2x041201602825423xxxxx确定换出变量：3)412,,28min(2x5x为换出变量