02-单纯形法

null 第二章 单纯形法Simplex MethodSM第2章 单纯形法第2章 单纯形法2.1 单纯形法的基本思想 2.2 单纯形法的计算过程 2.3 人工变量法 2.4 单纯形法补遗2.1 单纯形法的基本思想2.1 单纯形法的基本思想 单纯形法有三种形式： ① 方程组形式 ② 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 格形式 ③ 矩阵形式 2.1.1 方程组形式的单纯形法 思路：由一个基本可行解转化为另一个基本可行解。z -3x1 -5x2 = 0例1 范例等价改写为目标方程2.1 单纯形法的基本思想2.1 单纯形法的基本思想 0 0 0 1 0 0 0 1典式 条 典 ⑴ 当前基：m阶排列阵 ⑵ 目标方程中：一切基变量 的系数 σj = 0最优性检验：一切σj ≥ 0 ？初始基本可行解 X0 = (0, 0, 8, 12, 36)T z0 = 0 排列阵： 每行每列有且仅有一个元素 为1，其余元素全为0 的方阵。σ1 = -3< 0σ2 = -5 < 0当前解 X0 非优；+0x3+0x4+0x5须由X0 转化为另一个基本可行解 X1。满足条典的方程组称为典式(方程组)。思路：让X0 中的一个非基变量进基，去替换原来的一个基变量（离基）。2.1 单纯形法的基本思想2.1 单纯形法的基本思想x1仍为非基变量，其值为0。→ x2 ≤ 12/2 → x2 ≤ 36/4 离基（最小比值规则） ： x2 ≤ min {－，12/2，36/4 } = 6 x2 = min {－，12/2，36/4 } = 6 －x4x4为离基变量 进基（最小检验数规则）： 在负检验数中选择最小的进基。 min{σ j︱σj<0 } = σk → xk 进基 min{ -3，-5 } = -5= σ2 → x2 进基≥ 0≥ 0≥ 0= = 12 X1 =( 120,6,8,0,)T由① ② ③有2.1 单纯形法的基本思想2.1 单纯形法的基本思想主方程 0主列主元 z - 3x1 - 5 x2 = 0x1 +x3 = 8 2 x2 +x4 = 12 3x1 + 4 x2 +x5 = 36 (Ⅰ)- 6 9比值min以主列中正值元素为分母，同行右端常数为分子，求比值；按最小比值规则确定主方程和主元素，以及离基变量。2.1 单纯形法的基本思想2.1 单纯形法的基本思想X0 = ( 0, 0, 8, 12, 36 )T z0 = 0 (Ⅱ) x1 +x3 = 8 ① 3x1 -2x4 +x5 = 12 ③得X1 =z0 = 30称为单纯形法的一次迭代。( 120,6,8,0,)T换基运算—— 方程组的初等变换 目的是把主列变为 单位向量：主元变 为1，其余变为0。用换基运算 将X0 转化为 另一个基本 可行解 X1。0 0 1 02.1 单纯形法的基本思想2.1 单纯形法的基本思想(Ⅲ)(Ⅱ) x1 +x3 = 8 ① 3 x1 -2x4 + x5 = 12 ③得X* = ( 4, 6, 4, 0, 0 )T z* = 428 - 4min比值1 02.1 单纯形法的基本思想2.1 单纯形法的基本思想2.1.2 单纯形法的几何意义z = 0脊线( 4, 6, 4, 0, 0 )T( 0, 0, 8, 12, 36 )T( 0, 6, 8, 0, 12 )Tz 法向或棱线2.2 单纯形法的计算过程2.2 单纯形法的计算过程2.2.1 单纯形表 范例: 基于典式标准形cj 基 解 x1 x2 x3 x4 x5 3 5 0 0 0比 值 1 0 1 0 0x3 x4 x5 8 12 36 0 2 0 1 00 0 0 3 4 0 0 1 0 0 00-3-5检验行CBb35检验行 计算公式j=1,2,…,n2.2 单纯形法的计算过程2.2 单纯形法的计算过程初始单纯形表的一般形式2.2 单纯形法的计算过程2.2 单纯形法的计算过程 2.2.2 单纯形法的计算步骤 1° 把LP问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 化为标准形。 2° 在系数阵中找出或构造一个m阶排列阵作为初始 可行基，建立初始单纯形表。 3° 最优性检验: 若所有检验数σj ≥0，就得到一个 最优基本解，停止计算；否则转4° 。 4° 解无界判断: 在所有σj< 0中, 只要有一个σr < 0 所对应的系数列向量 ar≤ 0，即一切 air≤ 0 ， i=1, 2, … , m 则该LP问题解无界，停止计算；否则转5° 。预 备 步 骤迭 代 步 骤2.2 单纯形法的计算过程2.2 单纯形法的计算过程 5° 确定主元 ● 先按最小检验数规则 min {σj︱σj < 0 } = σk 确定进基变量 xk 和主列ak； ● 再按最小比值规则 确定主元al k, 同时也就确定第l 行的基变量 xr 离基。 6° 以al k为主元对当前表格进行一次换基运算，得到 一个新单纯形表，返3° 。 迭 代 步 骤2.2 单纯形法的计算过程2.2 单纯形法的计算过程2.2.3 单纯形法计算之例 范例 第0次迭代- 6 9min22.2 单纯形法的计算过程2.2 单纯形法的计算过程第一次迭代x3 x2 x5 0 5 01/2 8 1 0 1 0 0-25/2 4min 1600012300130-30008 -2.2 单纯形法的计算过程2.2 单纯形法的计算过程cj 基 解 x1 x2 x3 x4 x5 3 5 0 0 0比 值 1 0 1 0 0x3 x2 x5 8 6 12 0 1 0 1/2 00 5 0 3 0 0 -2 1 30 -3 0 0 5/2 0x3 x2 x1 0 5 36 0 1 0 1/2 04 0 0 1 2/3 -1/3 4 1 0 0 -2/3 1/342 0 0 0 1/2 18 - 4min3X*= (4, 6, 4, 0, 0)T, z* = 42第二次迭代2.2 单纯形法的计算过程2.2 单纯形法的计算过程cj 基 解 x1 x2 x3 x4 3 2 0 0 -2 1 1 0x3 x4 2 3 1 -3 0 10 0 0 -3 -2 0 01 3 1 -3 0 1x3 x1 0 3 8 0 -5 1 2 9 0 -11 0 3解无界例2 求解下述LP问题2.3 人工变量法2.3 人工变量法 考虑标准型 (M)： 分别给每个约束方程硬性加入一个非负变量 a11x1 +a12x2+…+a1nxn +xn+1 = b1 (≥0) a12x1 +a22x2+…+a2nxn +xn+2 = b2 (≥0) … … … … … am1x1+am2x2+…+amnxn +xn+m = bm(≥0)n个 xn+1, xn+2, … , xn+m 称为人工变量。 初始基本可行解：( 人造基本解 ) X0 = ( 0, 0, … , 0, b1, b2, …, bm )T(2.1)2.3 人工变量法2.3 人工变量法 基本思想： 人造解 X0 不是原LP问题的基本可行解。 但若能通过单纯形法的迭代步骤，将虚拟 的人工变量都替换出去，都变为非基变量（即 人工变量xn+1 = xn+2 = … = xn+m = 0），则X0的 前n个分量就构成原LP问题的一个基本可行解。 反之，若经过迭代，不能把人工变量都变 为非基变量，则表明原LP问题无可行解。2.3 人工变量法2.3 人工变量法2.3.1 大M法 在原问题的目标函数中添上全部人工变量，并令其系数 都为-M， 而M是一个充分大的正数。即 max z = c1x1 + c2x2 + c3x3 + … + cnxn – M( xn+1 + xn+2 +…+ xn+m ) 由于问题目标要求最大化，因此迭代必然趋向于把具有充分小系 数的人工变量从基变量中替换出去。 若迭代最终得到最优解X* ，而且基变量中不含有人工变量，则X*的 前n个分量就构成原问题的一个最优基本解；否则，原问题无可行解。 若迭代结果是解无界，而且基变量中不含有人工变量， 则原问题也 解无界；否则，原问题无可行解。2.3 人工变量法2.3 人工变量法 例3 用大M法求解下述LP问题 max z = 3x1 – x2 – 2x3 3x1+ 2x2 – 3x3 = 6 x1 – 2x2 + x3 = 4 x1， x2， x3 ≥ 0 max z = 3x1 – x2 – 2x3 3x1+ 2x2 – 3x3 +x4 = 6– Mx4x1 – 2x2 + x3 + x5 = 4–Mx5x1， x2， x3 ， x4， x5 ≥ 0s.t.解s.t.2.3 人工变量法2.3 人工变量法cj 基 解 x1 x2 x3 x4 x5 0 0 0 - M - M比 值 3 2 -3 1 0x4 x5 6 4 1 -2 1 0 1- M - M -10M -4M-3 1 2M +2 0 02 43 2 1 2/3 -1 1/3 0x1 x5 0 - M 2 0 -8/3 2 -1/3 16-2M 0 8M/3+3 -2M-1 4M/3+1 02 3 -2 x1 x3 1 0 - 4/3 1 -1/6 1/2 3 1 -2/3 0 1/6 1/2 7 0 5/3 0 M+5/6 M+1/2min X* = ( 3, 0, 1 )T, z* = 7 2.3 人工变量法2.3 人工变量法2.3.2 两阶段法 阶段Ⅰ 求解人造极大问题 max w = -xn+1 -xn+2 - … -xn+m s.t. ( 2.1 ) 因为人工变量 xn+1, xn+2, … , xn+m ≥ 0 所以 max w ≤ 0(1) 若w* < 0，则原问题无可行解，停止计算； (2) 若w* = 0，且人工变量都不是基变量，则转入阶段Ⅱ： 求解原问题；2.3 人工变量法2.3 人工变量法 (3) 若w* = 0，但“基列”存在人工变量，例如该列第l 行的基变量 xBl是人工变量，同时该行的前n个系数al j全都是0，这说明 原问题的该约束方程式多余的，那么删去第l 行及xBl列，类 似情况全都这样删去相应行、列；转入阶段Ⅱ； (4) 若w* = 0，且存在人工变量xBl是基变量，但该行的前n个系数 中存在al k≠0 ，则以al k为主元进行一次换基运算，可使原变 量xk取代人工变量xBl作为基变量，类似可将这类人工变量全 部都由基变量变为非基变量；转入阶段Ⅱ。 2.3 人工变量法2.3 人工变量法 阶段Ⅱ 求解原问题 建立原问题的初始单纯形表。只需把阶段Ⅰ的最末单纯形表 修改如下： (1) 删去人工变量 xn+1，xn+2 ， … ， xn+m诸列； (2) 把cj行与cj列的数字换成原问题目标函数的相应系数; (3) 重新计算z0和σj ，用以取代原检验行中相应数字。 然后用单纯形法进行迭代，直到运算结束。 s.t.3x1 +2x2 – 3x3 +x4 = 6x1 – 2x2 + x3 + x5 = 4x1， x2 ， x3， x4， x5 ≥ 0例4max w = – x4– x52.3 人工变量法2.3 人工变量法cj 基 解 x1 x2 x3 x4 x5 0 0 0 - 1 -1比 值 3 2 -3 1 0x4 x5 6 4 1 -2 1 0 1-1 -1 -10 - 4 0 2 0 02 43 2 1 2/3 -1 1/3 0x1 x5 0 -1 2 0 -8/3 2 -1/3 1 -2 0 8/3 -2 4/3 02min 3 -2 x1 x3 0 0 - 4/3 1 -1/6 1/2 0 1 -2/3 0 1/6 1/2 0 0 0 0 1 12.3 人工变量法2.3 人工变量法 阶段Ⅱ：求解原问题X* = ( 3, 0, 1 )T, z* = 7 3 -1 -2 3 -2 7 0 5/3 02.4 单纯形法补遗2.4 单纯形法补遗2.4.1 进基变量的相持及其突破 进基变量按最小检验数规则选定，如果出 现两个或更多个σj<0同时达到最小而相持时, 则应：从相持的检验数σk 所对应的变量 xk中,任选一个作为进基量。2.4 单纯形法补遗2.4 单纯形法补遗2.4.2 离基变量的相持及其突破——退化与循环 6 3/4 1 0 0 1/4x3 x4 x2 0 0 5 0 -3/2 0 0 1 -1/2 8 1 0 1 0 1 30 3/4 0 0 0 5/4X*= (0, 6, 8, 0, 0)T, z* = 30 2.4 单纯形法补遗2.4 单纯形法补遗 突破离基变量的相持是一重要问题，关键在于 突破离基变量的相持必然导致一个退化的基本可行 解，这就有可能造成单纯形法的迭代步骤陷入一个 周而复始的循环过程。 避免循环的方法有： ① 摄动法；② 辞典序法；③ 布兰德法 根据摄动法，避免循环的准则是：从相持的离基变量中，选择下标最大者离基。2.4 单纯形法补遗2.4 单纯形法补遗 定理1 多重最优解判别准则 在最优单纯形表中： ⑴ 若有一个或更多个非基变量xj的检验数σj = 0，则该问题有无穷 多个最优解； 2.4.3 多重最优解每次都选一个这样的 xj 进基，就能得到其它最优基本解； ⑶ 若问题有r 个最优极点解Xi*，则该LP问题有无穷多个最优解，且 其中任一最优解X*都能表示成这r 个最优极点解的凸组合：0≤ μi ≤1 ， i = 1, 2, … , r, 且∑ui = 1其中：X* = μ1X1* +μ2X2* + … +μr Xr* 2.4 单纯形法补遗2.4 单纯形法补遗 cj 基 解 x1 x2 x3 x4 x5 3 4 0 0 0比 值 1 0 1 0 0x3 x4 x5 8 12 36 0 2 0 1 00 0 0 3 4 0 0 1 0 -3 - 4 0 0 0- 6 9min2 6 0 1 0 1/2 0x3 x2 x5 0 4 0 8 1 0 1 0 0 12 3 0 0 -2 1 24 -3 0 0 2 08 - 4 min32.4 单纯形法补遗2.4 单纯形法补遗 cj 基 解 x1 x2 x3 x4 x5 3 4 0 0 0比 值 4 0 0 1 2/3 -1/3 x3 x2 x1 6 0 1 0 1/2 00 4 3 4 1 0 0 -2/3 1/3 36 0 0 0 0 1 6 12 -min2/3 3 0 1 -3/4 0 1/4x4 x2 x1 0 4 3 6 0 0 3/2 1 -1/2 8 1 0 1 0 0 36 0 0 0 0 1X1* = (4, 6)TX2* = (8, 3)T2.4 单纯形法补遗2.4 单纯形法补遗 X1* = (4, 6)T, X2* = (8, 3)T µ[ 0, 1 ]X* = ( 8 -4µ , 3+3µ )T , µ[ 0, 1 ]