第一章线性规划及单纯形法第讲.pptVIP

第一章线性规划及单纯形法LP问题解的几何意义定义5设集合是n维欧氏空间中的一个点集，如果及实数则称S是一个凸集。几何意义：如果集合中任意两点连线上的一切点都在该集合中，则称该集合为凸集。Note:空集和单点集也是凸集。第31页，共64页，星期日，2025年，2月5日§3线性规划问题解的基本性质定义6设则称为点的一个凸组合。定义7设凸集两点表示为则称x为S的一个极点（或顶点）。定理4LP问题的可行解集第32页，共64页，星期日，2025年，2月5日第一章线性规划及单纯形法定理5设D为LP问题的可行解集，，则x是D的极点的充分必要条件是x为LP问题的基可行解。prove推论1如果LP问题的可行解集非空，则极点集合也一定非空，且极点的个数是有限的。推论2如果LP问题有最优解，则一定可在可行解集D的极点上达到。定理6设LP问题在多个极点x(1),x(2),…x(k)处取到最优解，则它们的凸组合，即也是LP问题的最优解.（此时，该LP问题有无穷多最优解）第33页，共64页，星期日，2025年，2月5日§3线性规划问题解的基本性质Note:1、如何判断LP问题有最优解；2、计算复杂性问题。设有一个50个变量、20个约束等式的LP问题，则最多可能有个基。即约150万年如果计算一个基可行解只需要1秒，那么计算所有的基可行解需要：1364.7101.510360024365′?′′′（年）第34页，共64页，星期日，2025年，2月5日§4单纯形法的基本原理单纯形法（SimplexMethod）是1947年由G.B.Dantzig提出，是解LP问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。基本思路：基于LP问题的标准形式，先设法找到一个基可行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不相同）。第35页，共64页，星期日，2025年，2月5日第一章线性规划及单纯形法单纯形法引例首先，化原问题为标准形式：x3,x4是基变量.基变量用非基变量表示：x3=60-x1-3x2x4=40-x1-x2代入目标函数：z=15x1+25x2令非基变量x1=x2=0z=0基可行解x(0)=(0,0,60,40)T是最优解吗？maxz=15x1+25x2s.t.x1+3x2≤60x1+x2≤40x1，x2≥0 maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60x1+x2+x4=40x1，x2,x3,x4≥0 第36页，共64页，星期日，2025年，2月5日§4单纯形法的基本原理z=15x1+25x2x3=60-x1-3x2x4=40-x1-x2因为x2的系数大，所以x2换入基变量。x3=60-3x2≥0x4=40-x2≥0谁换出？如果x4换出，则x2=40，x3=-60，不可行。如果是“+”会怎样？如果x3换出，则x2=20，x4=20。最小比值法则所以x3换出。基变量用非基变量表示：代入目标函数：z=500+20/3x1-25/3x3令非基变量x1=x3=0z=500基可行解x(1)=(0,20,