金融学院-管理运筹学-02-线性规划与单纯型法

管理运筹学线性规划与单纯型法第二讲廣東金融學院工商管理系8/14/20193由实际问题引出数学模形。产品A产品B资源限量劳动力设备原材料9434510360200300利润元/KG701201.确定决策变量:设生产A,B分别为x1,x22.确定目标函数:2112070xxZMax3.确定约束条件:36049.21xxTS2005421xx30010321xx0,21xx一、LP问题的基本概念廣東金融學院工商管理系8/14/20194典型的LP问题:一、LP问题的基本概念njjjxcz1max),...,2,1(1mibxainjjij),...,2,1(0njxj廣東金融學院工商管理系8/14/20195用向量符号表示为:CXZMaxnjjjbxP10,0bX用向量和矩阵表示为:CXZMax0,0bXbAX一、LP问题的基本概念廣東金融學院工商管理系8/14/201961.基、基向量、基变量、非基变量设A为约束方程组的m×n阶系数矩阵，其秩为m，B是A中的一个m阶满秩子矩阵，称B为LP问题的一个基。B中每一个列向量称为基向量，对于的变量xj为基变量，其余的变量称为非基变量。54321xxxxx一、LP问题的基本概念廣東金融學院工商管理系8/14/201971.基、基向量、基变量、非基变量54321xxxxx54321xxxxx一、LP问题的基本概念廣東金融學院工商管理系8/14/20198满足约束方程(包括非负约束)的所有解，称为可行解。对于某组选定的基，令非基变量为0，与约束方程求得的唯一解，称为基解。2.可行解、基解、基可行解、可行基54321xxxxx00???321xxx54321xxxxx?0?0?531xxx一、LP问题的基本概念廣東金融學院工商管理系8/14/20199基解中满足所有变量非负约束的解，称为基可行解。2.可行解、基解、基可行解、可行基54321xxxxx000?0?0?321xxx54321xxxxx0?00?00?531xxx与基可行解对应的基称为可行基。一、LP问题的基本概念廣東金融學院工商管理系8/14/201910概念练习:找出下列LP问题的全部基解。32132xxxzMax531xx102421xxx452xx051x1234512345一、LP问题的基本概念廣東金融學院工商管理系8/14/201911组合x1x2x3x4x5z基可行解？1-2001-3001-4001-5002-3002-4002-5003-4003-5004-50051045////55-120452175541010-5415////52.51.517.554-32224319×××××一、LP问题的基本概念廣東金融學院工商管理系8/14/2019121.连线:二、重要定理与引理在n维Euclid空间中，点X与Y连线上的点，是指如下形式的点T:)10()1(YXT当α跑遍区间[0,1]时,相应的点T的集合就构成点X与Y之间的连线。廣東金融學院工商管理系8/14/2019132.凸集:一个由n维点所构成的集合K，如果对于K中任意两点X,Y∈K，恒有:)10()1(KYX则n维点集K称为凸集，即K中任意两点的连线上的点也在K中。3.凸组合:假定有k个n维Euclid空间的点它们的凸组合是指如下形式的点X:,,...,,)()2()1(kXXX特别，两个点X与Y的凸组合，叫做它们连线上的点。0,1...,...21)()2(2)1(1jkkkXXXX二、重要定理与引理廣東金融學院工商管理系8/14/2019144.顶点:设K是凸集，点X∈K；若对K中任何两个不同的点X,Y，以下等式恒不成立:)10()1(YXX就称X为凸集K的顶点。换句话说，凸集的顶点，就是不在凸集中任意两点连线上的点。二、重要定理与引理廣東金融學院工商管理系8/14/201915定理1.若LP问题的可行域非空,则可行域为凸集定理2.LP问题的基可行解X对应LP问题可行域的顶点定理3.若LP问题有最优解，则一定存在至少一个基可行解为最优解二、重要定理与引理LP问题的标准型，见P20廣東金融學院工商管理系8/14/201916(1)列初始单纯形表三、单纯形法的计算步骤cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b110…aij…a1nc2x2b200…a2j…a2n...............cmxmbm01…amj…amnб=cj-zj000miijjjacz1廣東金融學院工商管理系8/14/201917(2)从一个基可行解转换为相邻的另一个基可行解不失一般性，设初始基可行解中的前m个为基变量，)0,...,0,,...,,(00201)0(mxxxXTmxxxX)0,...,0,,...,,(00201)0(设单位矩阵的列向量为Pi，增广矩阵中单位矩阵以外的某个列向量为Pj，则Pj可以成为Pi的线性表达：111a1j.amjimiijjPaP101imiijjPaPTmbbbb),...,,(21三、单纯形法的计算步骤廣東金融學院工商管理系8/14/201918两式相加：0)(1imiijjPaPbxPoimii1bPPaxPjmiiijoimii11bPPaxjmiiiji10)(三、单纯形法的计算步骤对于一个正数：θ廣東金融學院工商管理系8/14/201919除了X(0)，还有其他解吗？bPPaxjmiiiji10)(TmxxxX)0,...,0,,...,,(00201)0(111a1j.amjTmbbbb),...,,(21TnmmxxxxxX),...,,,...,,(11111211)1(只需：)0,...,,...,0,,...,,(0202101)1(mjmjjaxaxaxX问题：X(1)是基可行解吗？三、单纯形法的计算步骤bxPnjjj1廣東金融學院工商管理系8/14/201920要使X(1)成为基可行解，必须满足：)0,...,,...,0,,...,,(0202101)1(mjmjjaxaxaxX00ijiax且，至少一个等式成立！显然，对于小于等于0的aij，上述不等式无条件成立；对于大于0的aij，则令：ljlijijiiaxaax00}0{min)(,0)(,00liliaxiji三、单纯形法的计算步骤廣東金融學院工商管理系8/14/201921TmxxxX)0,...,0,,...,,(00201)0(111a1j.amjTmbbbb),...,,(21111)0,...,,...,0,,...,,(0202101)1(mjmjjaxaxaxXTmbbbb),...,,(111121以上的系数矩阵的初等行变换，成为换基变换；如果仅且变换一个基变量，称对应的两个基可行解为相邻的基可行解。对应的顶点称为相邻的顶点，简称邻点。三、单纯形法的计算步骤廣東金融學院工商管理系8/14/201922将X(0),X(1)分别代入目标函数：(3)最优性判断TmxxxX)0,...,0,,...,,(00201)0(miiixcz10)0()0,...,,...,0,,...,,(0202101)1(mjmjjaxaxaxXjmiijiicaxcz10)1()(miijjjmiiiaccxcz110)1()(miijjjacczz1)0()1()(三、单纯形法的计算步骤廣東金融學院工商管理系8/14/201923miijjjacczz1)0()1()(其中：miijjjacc1称为检验数，也可表达为：jjzc或：j三、单纯形法的计算步骤廣東金融學院工商管理系8/14/201924【例】用单纯型法解下列LP问题：212maxxxz0,524261552121212xxxxxxx用矩阵形式表示为：52415100110102600150四、应用举例廣東金融學院工商管理系8/14/201925首先构造初始单纯型表如下：cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj20001四、应用举例廣東金融學院工商管理系8/14/201926cj21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj-zj200014)15,624,min(x1四、应用举例廣東金融學院工商管理系8/14/201927cj21000CB基bx1x2x3x4x50x315051002x124620100x5511001cj-zj20001x1四、应用举例廣東金融學院工商管理系8/14/201928cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/3第一次迭代结束四、应用举例廣東金融學院工商管理系8/14/201929cj21000CB基bx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61cj-zj000-1/31/346)46,12,3min(x2四、应用举例廣東金融學院工商管理系8/14/201930cj21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj-1/2-1/4000四、应用举例廣東金融學院工商管理系8/14/201931化为标准形式：五、单纯型法的进一步讨论—人工变量法(大M法)【例】用单纯型法求解下列LP问题：313maxxxz0931243132321321xxxxxxxxx91400130101120111100103914100013001101120001111MM00103廣東金融學院工商管理系8/14/201932构造初始单纯型表：cj-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj-zj-3-2M0004M-M1五、单纯型法的进一步讨论—人工变量法(大M法)廣東金融學院工商管理系8/14/201933第1次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx7660403-31cj-zj-3+6M-4M0003M1+4M五、单纯型法的进一步讨论—人工变量法(大M法)廣東金融學院工商管理系8/14/201934第2次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj-M-3/2-M+1/20003/23五、单纯型法的进一步讨论—人工变量法(大M法)廣東金融學院工商管理系8/14/201935第3次迭代：cj-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cj-zj-M+3/4-M+1/4-9/2-3/4000五、单纯型法的进一步讨论—人工变量法(大M法)廣東金融學院工商管理系8/14/201936同样题目六、