数据、模型与决策--线性规划.ppt

以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数 Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作λj , j=1,2…,n。 本例中λ1=3,λ2=4,λ3=0,λ4=0。参看表1.4（a）。 最优解判断标准 当所有检验数λj≤0（j=1，…，n）时，基本可行解为最优解。 当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。 1.5 单纯形法 Simplex Method 检验数 目标函数用非基变量表达时的变量系数 进基列 出基行 bi /ai2，ai20 θi 表1-4 (1) XB x1 x2 x3 x4 b x3 2 1 1 0 40 x4 1 3 0 1 30 λj 3 4 0 0 ? ? (2) x3 x2 λj ? ? (3) x1 ? x2 ? λj ? ? 基变量 1 10 0 0 1/3 0 1/3 10 5/3 1 -1/3 40 5/3 0 -4/3 30 1 0 3/5 -1/5 18 0 1 -1/5 2/5 4 0 0 -1 -1 将3化为1 乘以1/3后得到 1.5 单纯形法 Simplex Method 30 18 最优解X=(18，4，0，0)T，最优值Z=70 O 20 30 10 40 (3,4) X(3)=(18,4) 最优解X=(18,4) 最优值Z=70 X(1)=(0,0) 20 10 x2 x1 30 1.5 单纯形法 Simplex Method X(2)=(0,10) 单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表1.4）。 计算步骤： 1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零； 2.判断： （a）若λj≤０（j＝１，２，…，n）得到最解； （b）某个λk0且aik≤０（i=1，2,…,m）则线性规划具有无界解(见例1.18)。 （c）若存在λk0且aik (i=1,…,m)不全非正，则进行换基； 1.5 单纯形法 Simplex Method 第Ｌ个比值最小 ，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素； (c）求新的基可行解：用初等行变换方法将aLk 化为１,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。 （b）选出基变量 ，求最小比值： 1.5 单纯形法 Simplex Method 3.换基： （a）选进基变量 设λk=max｛ λj | λj 0｝,xk为进基变量 【例1.16】 用单纯形法求解 【解】将数学模型化为标准形式： 不难看出x4、x5可作为初始基变量，单纯法计算结果如表 1.５所示 。 1.5 单纯形法 Simplex Method Cj 1 2 1 0 0 b θ CB XB x1 x2 x3 x4 x5 0 x4 2 －3 2 1 0 15 0 x5 1/3 1 5 0 1 20 λj 1 2 1 0 0 ? ? 0 x4 2 x2 λj ? ? 1 x1 ? 2 x2 ? λj ? ? 表1－5 1/3 1 5 0 1 20 3 0 17 1 3 75 1/3 0 －9 0 －2 M 20 25 60 1 0 17/3 1/3 1 25 0 1 28/9 －1/9 2/3 35/3 0 0 －98/9 －1/9 －7/3 最优解X=(25，35/3，0，0，0)T，最优值Z=145/3 1.5 单纯形法 Simplex Method 【例1.17】用单纯形法求解 【解】 这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是：λj≥0(j=1，…，n)时得到最优解。 容易观察到,系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量x4,由第二个约束得到x