运筹学-第1章 3-单纯形法.ppt

浙江科技学院经济管理学院管工系 运筹学——计算机与通信工程学院 * 授课主要内容 目录： 第一章 线性规划 第二章 运输问题 第三章 动态规划 第四章 图与网络分析 * 1.3 单纯形法 单纯形法的基本思想： 从可行域的一个基可行解（顶点）出发，判断是否为最优解，如果不是最优解就转移到另一个较好的基可行解（相邻），如果目标函数达到最优，则已经得到最优解，否则继续转移到其他较好的基可行解（顶点）。 由于基可行解的数目有限，所以在有限次迭代内，可以找到最优解。 * 单纯形法迭代原理 迭代基础：如果LP存在最优解，则一定有一个基可行最优解，且对应LP可行域的顶点。（可行，基解，最优） 1.确定初始基可行解 基解，可行解 （1）直接观察法 *max z = x1 + 3x2 + 2x3 + x4s.t. x1 + 2x2 + 3x3= 33x2 + x3 + x4 = 4x1,x2,x3,x4 ≥ 0选 XB = (x1 x4)T令x2 = x3 = 0则 初始基可行解：X = (3 0 0 4)T （2）人工变量法（大M法） * 若给定问题标准化后，系数矩阵中不存在m个线性无关的单位列向量，则在某些约束的左端加一个非负变量xn+i（人工变量），使得变化后的系数矩阵中恰有m个线性无关的单位列向量，并且在目标函数中减去这些人工变量与一个足够大的正数M的乘积，对于变化后的问题，取m个单位列向量构成的单位子矩阵为初始基，则该基对应的可行解一定是基可行解。 （2）人工变量法（大M法） * 原问题的任意基可行解都是变化后问题的基可行解 若变化后的问题最优解中不含有非零的人工变量，则该解就是原问题的最优解 若变化后的问题中含有非零的人工变量则元问题无可行解 例：max z = x1 + 2x2 + 3x3x1 + 3x2 + 2x3 = 3s.t. 2x1 + x2 + x3 = 4x1,x2,x3 ≥ 0 * 2.最优性检验和解的判别 非基变量检验数 * 由检验数可以判断解的最优性情况 （1）因为所有Xj≥0，当所有σj0时，则Z≤Z0,则该基可行解对应最优解； （2）因为所有Xj≥0，当σj≤ 0 且存在σj＝0（j=m+1,…,n)时，则该线性规划问题有无穷多最优解； （3）对基可行解X0,若存在某个σk0,且所有aik≤0(Pj≤0), i=1,2,…,m，则该问题无界（无界解）； （4）因为所有Xj≥0，当存在σj0时，则该基可行解不是最优解，需要寻找另一个基可行解； * 3.基变换 变换目的：使目标函数Z值得到改善，接近最优解，一次基变换，是从该顶点到相邻顶点，即一次基变换仅变换一个基变量。 换入变量的确定（入基变量） σk0,aik 至少一个大于0，若σk=Max{σj| σj0},则xk为换入变量。 换出变量的确定（出基变量） 则xl为换出变量。 系数变换（初等行变换） * 以alk为主元进行初等行变换 * 1.4 单纯形法计算步骤 求初始基可行解 最优性检验 基变换 * 单纯形法原理—单纯形法总结 STEP 0找到一个初始的基础可行解，确定基变量和非基变量。转STEP 1。 STEP 1将目标函数和基变量分别用非基变量表示。转STEP 2。 STEP 2如果目标函数中所有非基变量的检验数全部为非正数，则已经获得最优解，如果全为负数，则为唯一最优解，运算终止。 ；如果有为0的非基变量检验数，则有无穷多最优解。运算终止。如果有某非基变量检验数为正，且工艺系数全非正，则无界，运算终止。否则，选取检验数为正数最大的非基变量进基。转STEP 3。 STEP 3选择最小比值对应的基变量离基，进行系数初等行变换，得新的基可行解，转STEP 1。 * 一.求初始基可行解 1.当约束条件为“≤”时，直接在约束不等式左边加上非负的松弛变量，使约束方程的系数矩阵很容易找到一个单位矩阵，求出一个初始基可行解。 2.当约束条件为“≥时，直接在约束不等式左边减去非负的剩余变量，此情况下很难找到一个单位矩阵，为求出初始基可行解，为此需要引入人工变量，以方便构成初始基可行解的一个基。 为了不改变问题的性质，对引入人工变量Xi”的线性规划问题，需要在目标函数中减去MXi”,M为足够大的正数，称罚因子，促使Xi”最终必为0。 3.当约束条件为”=“时，同样需要引入人工变量，以方便构成初始基可行解的一个基。目标函数需要减去罚因子。 * 二.最优性检验 （1）若所有σj0时，则已得唯一最优解，计算终止；如果基变量中存在非0人工变量，则无解。 （2）当所有σj≤ 0 且存在σj＝0（j=m+1,…,n)时，则已得最优解，且有无穷多最优解，计算终止。 （3）若存在某个σk0,且所有aik≤0(Pj≤0), i=1,2,…,m，则该