运筹学 线性规划 单纯形法

运筹学 线性规划 单纯形法

第一章 线性规划问题及单纯形法线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论

运筹学 线性规划 单纯形法

第五节

单纯形法的进一步讨论

本节重点: 本节重点:● 大 M法 ●两阶段法 ●解的存在情况判别

运筹学 线性规划 单纯形法

一, 人工变量的引入及其解法当约束条件为" 1. 当约束条件为"≥"型,引入剩余变量和人工变 量 由于所添加的剩余变量的技术系数为 由于所添加的剩余变量的技术系数为1,不能作 为初始可行基变量,为此引入一个人为的变量(注意, 为初始可行基变量,为此引入一个人为的变量(注意, 此时约束条件已为" ),以便取得初始基变量 以便取得初始基变量, 此时约束条件已为"="型),以便取得初始基变量, 故称为人工变量. 故称为人工变量. 人工变量 由于人工变量在原问题的解中是不能存在的, 由于人工变量在原问题的解中是不能存在的,应 尽快被迭代出去, 尽快被迭代出去,因此人工变量在目标函数中对应的 价值系数应具有惩罚性,称为罚系数 罚系数. 价值系数应具有惩罚性,称为罚系数.罚系数的取值 视解法而定 两种方法: 两种方法:大M法和二阶段法.

运筹学 线性规划 单纯形法

2. 大M法的求解过程 法的求解过程例1

人工变量添加前已为等式, 人工变量添加前已为等式, 其取值必须为0; 称为 其取值必须为 ;-M称为 惩罚因子" "惩罚因子"

运筹学 线性规划 单纯形法

例1的单纯型表迭代过程 的单纯型表迭代过程Cj CB X B b M x6 6 7 x3 4 10 x1 (2) 1 8 x2 1 1 7 x3 0 10

0 x4 1 0M

c j z j→

2M3 M1

0 x5 0 17

M x6 1 00

θ (3) 4

10 x1 7 x3

3 1

1 00

1/2 (1/2)1/2

0 10

c j z j →

1/2 0 1/2 13/2

1/2 1/2

6 (2)

7 M+3/2

10 x1 8 x2

2 2

1 00

0 10

c j z j→

1 2 1

1 12

1 26

M+2

1 1

答:最优解为 x1=2, x2=2, x3=0, OBJ=36

运筹学 线性规划 单纯形法

3.大 法的一些说明 3.大M法的一些说明(1)人工变量被迭代出去后一般就不会再成为基变量 法实质上与原单纯形法一样, (2)大M法实质上与原单纯形法一样,M 可看成一个 很大的常数 当检验数都满足最优条件, (3)当检验数都满足最优条件,但基变量中仍有人工 变量, 变量,说明原线性规划问题无可行解 法手算不会遇到麻烦, (4)大M法手算不会遇到麻烦,但计算机计算很容易产 生误差,因此提出了二阶段法. 生误差,因此提出了二阶段法.

运筹学 线性规划 单纯形法

4.二阶段法的求解过程 4.二阶段法的求解过程(1)第一阶段的任务是将人工变量尽快迭代出去,从而找 )第一阶段的任务是将人工变量尽快迭代出去, 到一个没有人工变量的基础可行解 (2)若第一阶段结束时,人工变量仍在基变量中,则原问 )若第一阶段结束时,人工变量仍在基变量中, 题无解( ) 题无解(3)第二阶段以第一阶段得到的基础可行解为初始 解,采用原单纯形法求解 (4)为了简化计算,在第一阶段重新定义价值系数

如下: )为了简化计算,在第一阶段重新定义价值系数如下:

运筹学 线性规划 单纯形法

用二阶段法求解例1的 用二阶段法求解例 的第一阶段

运筹学 线性规划 单纯形法

人工变量x 不在基变量中, 人工变量 6不在基变量中,从最终单纯形表中去除人工 变量,更换目标函数为原问题的目标函数, 变量,更换目标函数为原问题的目标函数,继续用单纯 形表计算. 形表计算.

运筹学 线性规划 单纯形法

用二阶段法求解例1的 用二阶段法求解例 的第二阶段

运筹学 线性规划 单纯形法

LP解的进一步讨论 二,LP解的进一步讨论 1.关于退化问题 1.关于退化问题当按照最小比值θ确定换出基变量时, 当按照最小比值θ确定换出基变量时,存在多个相同的最 最小比值 小比值, 小比值,从而使下一个表的基可行解中出现一个或多个基 变量等于零的退化解. 变量等于零的退化解. 退化的严重性在于可能导致死循环,克服死循环的方法有 退化的严重性在于可能导致死循环, 字典序" Bland规则:(1 规则:( "字典序"法,即Bland规则:(1)当按照最大检验数 确定换入变量时,存在多个相同的最大检验数, σj≥0确定换入变量时,存在多个相同的最大检验数,始终 选取下标值为最小的变量作为换入变量;( ;(2 当按照最 选取下标值为最小的变量作为换入变量;(2)当按照最 小比值θ确定换出基变量时,存在多个相同的最小比值, 小比值θ确定换出基变量时,存在多个相同的最小比值, 始终选取下标值为最小的变量作为换出变量. 始终选取下标值为最小的变量作为换出变量.

运筹学 线性规划 单纯形法

例2 m Z = 3x1 + 4x2 ax x1 + x2 ≤ 40 2x + x ≤ 60 1 2 s.t. x1 x2 = 0 x1, x2 ≥ 0

运筹学 线性规划 单纯形法

.关于多重解问题 2 .关于多重解问题最优单纯形表中有非基变量的检验数为0 最优单纯形表中有非基变量的检验数为0 非基变量的检验数为

运筹学 线性规划 单纯形法

例3 的单纯型表及其迭代过程

运筹学 线性规划 单纯形法

4 .关于无可行解问题 关于无可行解问题单纯形表达到最优解检验条件时, 单纯形表达到最优解检验条件时,人工变量仍在基 变量中

运筹学 线性规划 单纯形法

例4第一阶段的单纯型表 第一阶段的单纯型表

运筹学 线性规划 单纯形法

三,单纯形法小结 如下所示: 如下所示:

运筹学 线性规划 单纯形法

1. 线性规划模型及其变换, , 根据实际问题给出数学模型,进行标准化,列出初始单纯型表, 根据实际问题给出数学模型,进行标准化,列出初始单纯型表,见表 xj ≥ 0 不需要处理 变 xj ≤ 0 令 xj′ =-xj; x j ′≥ 0 量 xj 无约束 令 xj=xj′ -xj〃 ; xj′ , xj〃≥ 0 b>0 约 不需要处理 b<0 约束条件两端同乘-1 束 约束条件两端同乘 = 条 加人工变量 ≥ 减去剩余, 件 减去剩余,加人工变量 ≤ 加松弛变量 Max z 目 不需要处理 Min z 标 令 z′=-z 求 Max z′ 0 函 加入变量 松弛变量 人工变量 -M 数 的系数 分别以每一个约束条件中松弛变量或人工变量为基变量, 分别以每一个约束条件中松弛变量或人工变量为基变量, 列出初始单纯型

表

运筹学 线性规划 单纯形法

2.线性规划解的情况 线性规划解的情况解除有唯一最优解的情况外,还有如下几种情况: 解除有唯一最优解的情况外,还有如下几种情况: 唯一最优解的情况外无界解:(1) 可行区域不闭合 约束条件有问题 :(1 可行区域不闭合(约束条件有问题 约束条件有问题) 无界解:( 对应的列中所有a (2)单纯形中存在某入基变量 xk 对应的列中所有 ik≤0 ) 退化解: 退化问题的原因很复杂, 退化解:(1) 退化问题的原因很复杂,当原问题存在平衡约束时 (2)当单纯型表中同时有多个基变量可选作出变量时 ) (3)退化的严重性在于可能导致死循环 ) 无穷多解: (1)多个基础可行解都是最优解,这些解在同一个超平面上, 多个基础可行解都是最优解,这些解在同一个超平面上, 无穷多解: 且该平面与目标函数等值面平行 (2)最优单纯形表中有非基变量的检验数为0 最优单纯形表中有非基变量的检验数为 (3)最优解的线性组合仍是最优解,即 X=aX1+bX2,a+b=1 最优解的线性组合仍是最优解, 无可行解: (1) 约束条件互相矛盾,无可行域 约束条件互相矛盾, 无可行解: (2)单纯型表达到最优解检验条件时,人工变量仍在基 单纯型表达到最优解检验条件时, 变量中

运筹学 线性规划 单纯形法

添加松弛变量, 添加松弛变量 , 人工变 量 列出初始单纯形表 计算各列检验数б 计算各列检验数бj

3.对目标函数求极大值标准型线性规 对目标函数求极大值标准型线性规 划问题, 划问题,单纯形法计算步骤的框图否 唯一最优解

所有б 所有бj≤0 否 对任一б 对任一бj≥0 有aik≤0 否 令бk=max{бj} б

是

基变量中 有非零的 人工变量是

否

某非基变 量检验数 为零 无穷多最优解

无可行解 是 无界解

xk为换入变量

1.xk替换 l . 替换x 2.列出新的单纯形表 . 对主元素行( 行 ① 对主元素行(第l行)

对 所 有 aik>0 计 算 θi=bi/aik 令θl=min{θi} 个基变量为换出变 第 l 个基变量 为换出变 量,alk为主元素

′ bl′ = bl / a lk , a lj = a lj / a lk②其它行i(i≠l) 其它行 ( )

′ bi′ = bi aik bl / alk , aij = aij aik alj / alk

运筹学 线性规划 单纯形法

例1:某糖果厂用原材料A,B,C加工成三种不同牌号的糖 :某糖果厂用原材料 , , 加工成三种不同牌号的糖 果甲, 已知各种牌号的糖果中A, , 含量 含量, 果甲,乙,丙.已知各种牌号的糖果中 ,B,C含量,原 料成本,各种原料每月限制用量, 料成本,各种原料每月限制用量,三种牌号糖果的单位加 工费及售价如下表所示. 工费及售价如下表所示.问该厂每月生产这三种牌号糖果 多少kg,使该厂获利最大.试建立该问题的LP的数学模型 的数学模型. 多少 ,使该厂获利最大.试建立该问题的 的数学模型.甲 A B C 加工费 元/kg 售价 元/kg ≤20% 0.5 3.4 ≤50% 0.4 2.85 ≤60% 0.3 2.25 ≥60% 乙 ≥30% 丙 原料

售价 元/kg 2 1.5 1 每月限量 kg 2000 2500 1200

本文来源：https://www.bwwdw.com/article/m321.html