1.单纯形法.ppt

三、课堂教学内容 运筹学的工作步骤 线性规划 (Linear Programming ——LP)是 数学规划的一个分支，数学规划着重解决资源 的优化配置，一般可以表达成以下两个问题中 的一个： 当资源给定时，要求完成的任务最多； 当任务给定时，要求为完成任务所消耗的资源最少。 若上述问题的目标﹑约束都能表达成变量的 线性关系，则这类优化问题称LP问题。 LP是一种解决在线性约束条件下追求最大或最 小的线性目标函数的方法。 第一章 线性规划及单纯形法第一节 线性规划问题及数学模型（P8） 四、 线性规划问题的标准型 例1 第2节 LP理论基础：凸集、凸组合、顶点；定理（1﹑*2﹑3） 证明定理1： 设X(1)﹑X(2)为LP可行域D内任意两点，X(1)≠X(2) ， 则AX(1)=b，AX(2)=b，X(1)≥0，X(2)≥0 令X为X(1)﹑X(2) 连线上任意一点，即X=αX(1)+（1-α）X(2) ，（0≤α≤1） 代入约束AX=αAX(1)+（1-α）AX(2) =αb+（1-α）b=b， 又∵α≥0，（1-α）≥0，∴X≥0，即X(1)﹑X(2) 连线上任意一点也在D内，由凸集定义，D为凸集。 证明定理3： 设X(1)﹑...﹑X(k)为可行域顶点，相应目标值 Z(1)﹑...﹑Z(k) ，其中第m个顶点X(m)处目标值最大， 记为Z(m) ，若X(0) 不是顶点但其目标值最优，则： 第3节 单纯形法(George Dantgig于1947年提出) 由线性代数知，对标准形LP问题，理论上可以求出所有基解（枚举法），再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。 为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是，停止。二是若不是最优，要保证下一步得到的解不劣于当前解。基于线性代数原理，并将上述功能贯穿于算法过程，这就是线性规划的单纯形法。 表1-3 x3 x4 x2 x3 x4 x2 3 0 1 0 0 1/4 2 1 0 1 0 -1/2 8 0 0 -4 1 2 x1 x4 x2 2 0 3 检验行 ?j 0 0 -2 0 1/4 - 8/2=4 3*4=12 ↓ ← 2 0 3 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0 检验行 ?j 0 0 -1.5 -1/8 0 x1 x5 x2 表1-5 表1-6 最优解： x1=4 x2=2 x3=0 x4=0 x5=4 z=14 第4节 单纯形步骤 1.化标准形 2.在系数矩阵中找出（构造）m（方程个数）阶单位矩阵，以其 为初始基，对应变量为基变量，画初始单纯形表； 3.计算检验数?j ，若所有?j≤0，得最优解，否则转4； 4.若某个?j0，其对应列系数均≤0，得无界解，停止，否则转5； 5.选最大?j(0)对应变量进基，最小比值? 对应变量出基（这种做 法称? 规则），标出主元(进基变量和出基变量交叉处元素)； 6.将主元变为1，主元列(主元所在列)其它元素变为0，得新表， 返回3。 检验数?j算法： 基变量检验数总是0，只需求非基变量检验数。方法是：将左列基变量价值系数与所求非基变量系数列分别相乘再相加，然后被该非基变量价值系数减去。 最小比值?算法： 以b列为分子，主元列元素(0)为分母,计算各行比值，其最小者为?。 ?j算法公式推导： 设前m个为基变量，则xi=bi- aijxj (i=1…m) 代入目标函数 Z= cixi+ cjxj= ci(bi- aijxj)+ cjxj = cibi- ci aijxj+ cjxj= cibi+( cj- ciaij)xj 令Z0= cibi，Zj= ciaij, 则Z=Z0+ (cj-Zj)xj 令?j=cj-Zj= cj- [c1a1j+c2a2j+