运筹学 02_单纯形法.ppt

设线性规划的标准形式 maxz cjxj 1 s t aijxj bii 1 2 m 2 xj 0j 1 2 n 3 可行域 由约束条件 2 3 所围成的区域 可行解 满足 2 3 条件的解X x1 x2 xn T为可行解 基 设A是约束条件方程组的m n维系数矩阵 其秩为m B是A中m m阶非奇异子矩阵 则称B为线性规划问题的一个基 设 复习 线性规划问题解的概念 基向量 非基向量 基变量 非基变量 称pj j 1 2 m 为基向量 其余称为非基向量 与基向量pj j 1 2 m 对应的xj称为基变量 其全体写成XB x1 x2 xm T 否则称为非基变量 其全体经常写成XN 基解 对给定基B 设XB是对应于这个基的基变量XB x1 x2 xm T 令非基变量xm 1 xm 2 xn 0 由 2 式得出的解X x1 x2 xm 0 0 T称为基解 基可行解 所有决策变量满足非负条件 xj 0 的基解 称作基可行解 可行基 基可行解所对应的基底称为可行基 写出下述线性规划问题对应的基 基变量 基解 基可行解和可行基 定理2 X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点 线性规划问题的基可行解X对应于可行域D的顶点 定理3 若可行域有界 线性规划问题的目标函数一定可以在其可行域的顶点上达到最优 3单纯形法 SimplexMethod 例子 求解线性规划问题 线性规划问题的最优解 可以从基可行解中找到 图解法有局限性 枚举法计算量大 3 1单纯形法的引入 解 首先 将该问题化成标准形 第二 找初始可行解 即一个顶点 系数矩阵A p1p2p3p4p5 矩阵形式 因为p3 p4 p5线性独立 故B p3 p4 p5 构成一个基底 对应的基变量x3 x4 x5解出来为 用非基变量表示基变量 x3 8 x1 2x2x4 16 4x1 a x5 12 4x2将 a 代入目标函数中得z 0 2x1 3x2令非基底变量x1 x2 0 则有z 0 这时得到一个基可行解X 0 0 0 8 16 12 T 原点 第三 判别从目标函数中得知 非基底变量的系数为正 因此 将非基变量换入基底后可使目标函数增大 转入第四步 第四 换基底 旋转迭代 确定换入变量 由于z 0 2x1 3x2中非基底变量x2系数贡献最大3 故换入基底为x2 换入变量已定 必须从x3 x4 x5换出一个 并且要保证其余均是非负的 即x3 x4 x5 0 x3 8 2x2 0 x4 16 0 x5 12 4x2 0由此 只要选择x2 min 8 2 12 4 3 对应基底变量x5 0 从而确定用x2和x5对调 即将x5换出 有x3 2 x1 1 2x5x4 16 4x1 b x2 3 1 4x5 将 b 代入目标函数中得z 9 2x1 3 4x5令非基变量为零 又得到另一个基可行解X 1 0 3 2 16 0 T 顶点Q4 返回第三步 非基变量x1的系数是正的 还可增大 X 1 不是最优解 重复上述步骤 由于x1的系数是正的 从而x1为转入变量 再由x3 2 x1 0 x4 16 4x1 0 x2 3 0 只要选x1 min 2 16 4 2上式就成立 因为x1 2时 基变量x3 0 从而由x1换出x3 得x1 2 x3 1 2x54x1 x4 16 c x2 3 1 4x5高斯消去法 行变换 得 x1 2 x3 1 2x5x4 8 2x5 4x3x2 3 1 4x5 代入目标函数中 得z 13 2x3 1 4x5令非基变量x3 x5 0 又得到另一个基可行解X 2 X 2 2 3 0 8 0 T 新顶点Q3同理 返回第三步 再迭代 x5作为转入变量x1 2 1 2x5 0 x4 8 2x5 0 x2 3 1 4x5 0 只要取x5 min 8 2 12 4就有上式成立 x5 4时 x4 0 故决定用x5换x4x1 4 1 4x4x5 4 1 2x4 2x3x2 2 1 8x4 1 2x3代入得z 14 3 2x3 1 8x4 令x3 x4 0得z 14 新基可行解为X 3 4 2 0 0 4 T 为最优解 新顶点Q2最优目标值z 14 从实际例子中分析单纯形法原理的基本框架为 第一步 将线性规划模型变换成标准型 确定一个初始可行解 顶点 第二步 对初始基可行解最优性判别 若最优 停止 否则转下一步 第三步 从初始基可行解向相邻的基可行解 顶点 转换 且使目标值有所改善 目标函数值增加 重复第二和第三步直到找到最优解 3 2初始可行基的确定 设线性规划问题 为了确定初始基可行解 首先要找出初始可行基 其方法如下 从Pj j 1 2 n 中一般能直接观察到存在一个初始可行基 确定初始可行基的几种方法 形式的不等式 形式的不等式 的情形观察 小加大减 人造 约束是 形式的不等式 可以利用化标准型的方法 左端加一个松弛变量 经过整理 重新对xj及aij i 1 2 m j 1 2 n 进行调整编号 则可得下列方程组 小加 x1 a1 m 1xm 1 a1nxn b1x2 a2 m 1xm 1 a2nxn b2 xm am m 1xm 1 amnxn bmxj 0 j 1 2 n 显然得到一个m m单位矩阵 注意 aij和bi已经变化 移项整理得x1 b1 a1 m 1xm 1 a1nxnx2 b2 a2 m 1xm 1 a2nxn xm bm am m 1xm 1 amnxn令xm 1 xm 2 xn 0 可得xi bi i 1 2 m 又因bi 0 所以得到一个初始基可行解 X 0 x1x2 xm0 0 T b1b2 bm0 0 T 非基向量可以用基向量的线性组合表示将 3 式乘以一个正的数 0 得到 记初始基可行解为X 0 有该解满足约束方程 即 3 3从初始基可行解转换为另一基可行解 4 式和 1 式相加 整理后得到由 5 式可以找到满足约束方程的另一个点X 1 其中 是点X 1 的第j个坐标值 要使X 1 是一个基本可行解 则要求并且这m个等式中至少要有一个等号成立当时 6 式必然成立当时 令因此有所以X 1 中的正分量最多有m个 可证明m个向量P1 Ps 1 Ps 1 Pm Pj线性无关 按照式 7 确定 值 X 1 就是一个新的基可行解 何时达最优解 何种最优解 3 4最优性检验和判别定理 将基本可行解X 0 和X 1 分别代入目标函数得由此 j称做检验数 是对线性规划问题的解进行最优性检验的标志 最优解的判别定理 且对一切的j m 1 n有 则X 0 为最优解 若是一个基可行解 无穷多最优解判别定理 若是一个基可行解 且对一切的j m 1 n有 又存在某个非基变量的检验数则线性规划问题有无穷多最优解 无界解的判别定理 3 5基变换换入变量的确定 max j 0 k j m 1 n xk是换入变量 也可任选 换出变量的确定 确定换出变量的原则是保持解的可行性 就是说要使原基可行解的某一正分量xs变成零 同时保持其它的分量均非负 换基原则 min xi aij aij 0 xs asj s 1 2 m 最小比值准则 或 准则 3 6旋转运算在确定换入变量xk和换出变量xs以后 要把xk所对应的系数列向量pk变成单位向量 为此 只要对系数矩阵的增广阵进行 行 的初等变换即可 行变换的定义 第s行 1 ask得 当i s时 第i行 第s行 aik 经过初等变换后 新的增广矩阵是 4单纯形法的计算步骤和单纯形表约束方程组和目标函数组成n 1个变量 m 1个方程的方