运筹学第章单纯形法PPT课件

OR课件,LP,局限性：仅能求解两个变量的LP问题重要启示：（1）LP问题的最优解一定在可行域的顶点上达到；（2）可行域中顶点的转移实现了数学迭代，顶点的转移使得目标函数值上升或下降。,单纯形法的基本原理和基本思想,导学-回顾,OR课件,可行域顶点的个数是否有限？最优解是否一定在可行域顶点上达到？如何找到顶点？如何从一个顶点转移到另一个顶点?,导学-问题,OR课件,SimplexMethod,OR课件,LP,1LP问题的几何意义2单纯形法的经济解释3单纯形法的计算步骤4单纯形法的进一步讨论5LP问题解的讨论。,导学-主要内容,重点单纯形法的经济含义、优化原理和计算步骤、以及有关概念。难点单纯形法的迭代原理和迭代方法，以及迭代过程中所反映的经济含义。,OR课件,导学-重点与难点,OR课件,LP,1几何意义,基本概念,1、凸集,2、顶点：上式中1或0时对应的点。,非凸集,非凸集,OR课件,LP,基本定理,LP问题的可行域是凸集可行解是基本可行解的充要条件（-是X的非零分量所对应的系数列向量线性无关）基本可行解对应可行域的顶点有可行解必有基本可行解，即凸集有顶点最优解在可行域的顶点上达到,1几何意义,OR课件,LP,例2.1设有一家具厂用木材和钢材生产A,B,C三种家具，生产一件家具所需的材料、每件家具可获得的利润以及每月可供的木材自河钢材数量如下表，问此家具厂应如何安排各种家具的生产量才能使企业获得最大的利润？,解：设A,B,C三件家具的产量(件数)分别为x1,x2,x3，有：,2经济解释,OR课件,LP,模型的标准型为：,系数矩阵和基：,则：基变量为x4,x5;非基变量为x1,x2，x3，变换标准型的约束条件：,代入目标函数：Z=0+4x1+x2+5x3令非基变量等于0，基变量x4=8000,x5=3000,初始基本可行解,2经济解释,OR课件,LP,观察目标函数：,选x3入基，x1,x2仍为非基变量，且为0，代入上方程组：,则：基变量为x4,x3;非基变量为x1,x2x5，变换标准型的约束条件：,代入目标函数：Z=3750+1.5x10.25x21.25x5令非基变量等于0，基变量x3=750,x4=5000,基本可行解,当x3=750时，x5=0即为非基变量，x4=5000,2经济解释,OR课件,LP,观察目标函数：,选x1入基，x2,x5仍为非基变量，且为0，代入上方程组：,则：基变量为x1,x4;非基变量为x2,x3x5，变换标准型的约束条件：,代入目标函数：Z=6000x23x32x5令非基变量等于0，基变量x1=1500,x4=3500,最优解,当x1=1500时，x3=0即为非基变量，x4=3500,2经济解释,OR课件,LP,例题小结：明确以下问题：,变量的经济意义目标函数及其系数的经济意义变量换入、换出时的经济意义,目的在于：引入单纯形法的计算过程,2经济解释,OR课件,LP,将LP问题化标准型，求出初始基本可行解，并列入单纯形表,是否最优？,是否无解？,最优解,Y,N,Y,无解,N,确定换入变量、换出变量，得到一个新的基本可行解,？,？,？,？,3计算步骤,OR课件,LP,例2.1线性规划问题的标准型：,初始单纯形表：,？推导,初始解为X=(0,0,0,8000,3000)Z=0,3计算步骤,OR课件,LP,检验数表达式推导：,判别式：MaxZ:cjzj0(对于所有的非基变量）问题达到最优；,3计算步骤,OR课件,LP,换入变量的确定：,换出变量的确定：,系数矩阵的变换：,按照增广矩阵的变换规则，将基变量的系数矩阵转化为单位矩阵，非基矩阵和资源向量作相应的变化。,3计算步骤,OR课件,LP,2000750,K,L,4,主元素,x4,x3,0,5,750,1/2,1/4,1,0,1/4,5000,1,0,0,1,-1,5/2,5/4,5,0,5/4,3/2,-1/4,0,0,-5/4,K,K,50001500,L,1/2,3计算步骤,OR课件,LP,x4,x1,0,4,1500,1,1/2,2,0,1/2,3500,0,-1/2,-2,1,-3/2,4,2,8,0,2,0,-1,-3,0,-2,最优解为：X=(1500,0,0,3500，0)Z=6000,当前解为：X=(0,0,750,5000，0)Z=3750,3计算步骤,OR课件,LP,1、极小(MinS)目标函数的处理：方法一：CjZj0达到最优方法二：ZjCj0达到最优,4进一步讨论,OR课件,LP,2、构造基：当约束条件为“”或“”时，需要设置“人工变量”构造基。求解方法有：方法一：大M法方法二：两阶段法,4进一步讨论,OR课件,LP,大M法,方法要点：目标函数按下式处理（M是一个充分大的正数），约束条件不变，填入单纯形表进行求解。,4进一步讨论,OR课件,LP,例2.2,或,4进一步讨论,OR课件,LP,两阶段法,方法要点（1）第一阶段目标函数的设置：（2）转入第二阶段的条件及处理方法：,条件：第一阶段满足最优性检验，且该阶段的目标值等于0，转入第二阶段；否则该问题无解，计算终止。处理：替换目标函数，在第一阶段最优表上继续。,4进一步讨论,OR课件,LP,学习提示：注意与图解法对比。,不可行解：最终表的基变量中含人工变量；,例2.3如有线性规划,5解的讨论,OR课件,LP,两阶段法的最优单纯形表如下：,人工变量,无可行解,5解的讨论,OR课件,LP,无限界解：,5解的讨论,OR课件,LP,例2.4如有线性规划,无限界解,5解的讨论,OR课件,LP,退化解：LP问题的基本可行解中非零变量的个数少于约束条件数，也就是有基变量的取值为0。,例题：下列有一求目标函数极大的LP问题的单纯形表,基变量x2=0,退化解,5解的讨论,OR课件,LP,多重解：有非基变量的检验数等于0。,例题：下表是某极大化LP问题的最优单纯形表,非基变量的检验