线性规划及单纯形法详解演示文稿.pptVIP

如何确定换入，换出变量？ 一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。 现分析(1-3)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x5≥0。 当前第94页\共有150页\编于星期二\13点 当x1=0,由(1-3)式得到 当前第95页\共有150页\编于星期二\13点 x2取何值时，才能满足非负要求？ 从(1-5)式中可以看出，只有选择 x2=min(8/2,12/4)=3时，才能使(1-5)式成立。 因当x2=3时，基变量x5=0，这就决定用x2去替换x5。 以上数学描述说明了每生产一件产品Ⅱ，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品Ⅱ的产量。 这里就是由原材料B的数量确定了产品Ⅱ的产量x2=12/4=3件。 当前第96页\共有150页\编于星期二\13点 为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-3)中x2的位置与x5的位置对换。得到 当前第97页\共有150页\编于星期二\13点 用高斯消去法 将(1-6)式中x2的系数列向量变换为单位列向量。其运算步骤是： ③′=③/4；①′=①-2×③′;②′=②, 并将结果仍按原顺序排列有： 当前第98页\共有150页\编于星期二\13点 再将(1-7)式代入目标函数(1-1)式得到 令非基变量x1=x5=0，得到z=9，并得到另一个基可行解X（1） X（1）=（0，3，2，16，0）T 当前第99页\共有150页\编于星期二\13点 从目标函数的表达式(1-8)中可以看到，非基变量x1的系数是正的，说明目标函数值还可以增大，X(1)还不是最优解。 于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2) X(2)=(2,3,0,8,0)T 再经过一次迭代，再得到一个基可行解X(3) X(3)=(4,2,0,0,4)T 而这时得到目标函数的表达式是： z=14-1.5x3-0.125x4 (1-9) 当前第100页\共有150页\编于星期二\13点 z=14-1.5x3-0.125x4 (1-9) 再检查(1-9)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。 所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品Ⅰ生产4件，产品Ⅱ生产2件，工厂才能得到最大利润。 当前第101页\共有150页\编于星期二\13点 四、单纯形法 4、单纯形法求解线性规划 再引入一实例，介绍利用单纯形法求解线性规划时可以使用的一种工具，即单纯形表。 例1-12 用单纯形法求解下列线性规划的最优解 当前第102页\共有150页\编于星期二\13点 例1-12 【解】 化为标准型为： 约束方程的系数矩阵A为： 当前第103页\共有150页\编于星期二\13点 例1-12 【解】 确定初始基和基变量、非基变量、初始基本可行解。 基变量为：x3，x4 非基变量为：x1，x2 令非基变量x1=x2=0，代入约束方程中 得到：x3=40，x4=30 则初始基本可行解为： X（0）=（0，0，40，30）T 当前第104页\共有150页\编于星期二\13点 例1-12 【解】 以上得到的一组基本可行解是否是最优解? 从目标函数z=3x1+4x2中看出： X1和x2的系数大于零，如果x1和x2为一个正数，那么目标值就能够变得更大。 因此，只要非基变量的系数大于零，那么目标函数就没有达到最大，即没有找到最优解。 判别线性规划问题是否达到最优解的数称为检验数，记作λj（j=1，2，…，n）。在例1-11中λ1=3，λ2=4，λ3=0，λ4=0。 检验数：目标函数用非基变量表示，其变量的系数为检验数 当前第105页\共有150页\编于星期二\13点 四、单纯形法 1、预备知识：凸集和顶点 ① 凸集： ② 顶点 凸集C中满足下述条件的点X称为顶点： 如果C中不存在任何两个不同的点X1、X2，使X成为这两个点连线上的一个点。 对任何X1∈C，X2 ∈C，不存在X=aX1+（1-a）X2 （0<a<1），则称X是凸集C的顶点。 解释：顶点是不会出现在集合C中任意两点之间的连线上。 当前第62页\共有150页\编于星期二\13点 四、单纯形法 2、线性规划问题的解 假设所要研究的线性规划模型的形式为： 求解线性规划问题，就是满足约束条件（b）、（c）的方程组中