当前位置：文档之家 › 《线性规划》0934第二章2.4退化问题 2.6单纯形法的几何意义=第八次课

《线性规划》0934第二章2.4退化问题 2.6单纯形法的几何意义=第八次课

  • 格式：ppt
  • 大小：10.78 MB
  • 文档页数：26

下载文档原格式

  / 26

合集下载

线性规划——单纯形法文档

线性规划——单纯形法文档

线性规划——单纯形法设计文档——《通用优化模块》编写人：徐天爽编写时间：2010年06月完成2010年06月整理目录第一部分功能概述 (1)第二部分理论知识 (2)2.1 线性规划标准型 (2)2.2单纯形法 (4)2.2.1修正单纯形法 (4)2.2.2Bland规则 (7)第三部分程序主要内容 (9)第四部分程序测试 (10)备注 (17)参考文献 (18)第一部分功能概述单纯形法是线性规划算法的一种。

由于若线性规划问题有最优解，则一定存在一个基本可行解是最优解，因此单纯形法是通过沿着可行集的边界，从一个顶点转移到改善当前目标函数值的相邻定点，以此来寻找最优解。

程序编写了加入Bland规则的修正单纯形法，只需用户给定设计变量个数、约束条件个数、约束条件系数，委托矩阵操作类MatrixOperation进行矩阵运算，即可实现线性规划问题的优化。

第二部分 理论知识线性规划问题具备以下性质：定理1 若线性规划问题的可行域X 非空，则X 是一个凸集。

定理2 线性规划问题的每一个基本可行解x 都对应于可行域X 的一个顶点。

定理3 若线性规划问题有最优解，则一定存在一个基本可行解是最优解。

定理4 若线性规划问题有最优解，则目标函数的最优值一定可以再可行域X 的某个顶点上达到。

2.1 线性规划标准型定义1 如果目标函数是设计变量的线性函数，且约束条件也是关于设计变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。

单纯形法计算问题的最优值需要将原问题统一为标准形式。

定义线性规划问题的标准形式为：定义2 给定线性规划问题的标准型为()()11min ..1,2,,01,2,,nj jj n ij j i j j z c x s t a x b i m x j n ==⎧=⎪⎪⎪==⎨⎪⎪≥=⎪⎩∑∑ (1)其中()01,2,,i b i m ≥= 。

即对目标函数一律求最小值；设计变量均非负；约束条件除非负约束条件之外一律为等式约束；约束条件的右端项一律非负。

线性规划与单纯形法(4)

线性规划与单纯形法(4)

• 右端常数项非正
两端同乘以 -1
• 约束条件为不等式
– 当约束方程为“≤”时，左端加入一个非负的松弛变量， 就把不等式变成了等式；
– 当约束条件为“≥”时，不等式左端减去一个非负的剩余 变量(也可称松弛变量)即可。
• 决策变量xk没有非负性要求 令xk=xk′-x k〃， xk=xk′，x k〃 ≥0
例1是二维空间（平面）线性规划问题，可用作 图法直观地来表述它的求解。
因存在 x1,x2 0
必须在直角坐标的第1象限内作图，求解。
23
图1-2
max z 2x1 3x2
x1 2x2 8
4 x1
16 4x2 12
x1, x2 0
24
图1-3 目标值在（4，2）点，达到最大值14 目标函数 max z 2x1 3x2
约，用量不能突破。
– 生产单位甲产品的零部件需耗用A车间的生产能力 1工时，
– 生产单位乙产品不需耗用A车间的生产能力， – A车间的能力总量为8工时，则A车间能力约束条件
表述为
x1
≤8
– 同理，B和C车间能力约束条件为
2x2 ≤12
3x1 +4 x2 ≤36
16
(3)目标函数。目标是利润最大化，用Z表示利润，则
1
S.t. x1 -3 x2 ≥3
x1 ≥0, x2 ≥0 -1
x1 -3 x2
1
2
=3
3
x1
-1
36
1.3 线性规划问题的标准型式
一 、标准型
• 线性规划问题的数学模型有各种不同的形式，如 – 目标函数有极大化和极小化； – 约束条件有“≤”、“≥”和“＝”三种情况； – 决策变量一般有非负性要求，有的则没有。

第2章 线性规划原理与解法

第2章 线性规划原理与解法
2、最优性检验与解的判别 （以下判定定理针对标准型而言 ）
（1）最优解的判定定理： 对于一个基可行解，如果其所有非基变量的检验数 j 0 ， 则该解称为最优解。 （2）唯一最优解：所有非基变量的检验数都 < 0 （3）无穷多最优解： 已经是最优解，有某个非基变量的检验数 = 0
（4）无界解判定定理： 对于一个基可行解，其非基变量中有某个 m k 0 ， 同时它对应的系数列向量所有的 ai ,mk 0 ， 则该线性规划问题具有无界解。
x1
二、一般线性规划问题的求解基础
max z 2 x1 3 x2 0 x3 0 x4 0 x5 x1 2 x2 x3 8 （2）换出变量的确定 4 x1 x4 16 4 x2 x5 12 为了确保所有的变量均为非负，需确定换入变量的值为：
3、基变换
bi' ' bl' xk min ( ' aik 0) ' i aik alk
得: z 2 x1 9 3 4 x5 0 9 2 x1 3 4 x5
将式（2-5）代入目标函数
0 16 4 x1 0 x5
一、举例说明
步骤4 重复步骤2、3，直到目标函数中非基变量的系数均为负，无改进可能， 即找到最优解 本例依次向下迭代得到的基可行解分别为：
1确定初始可行解2解的最优性的判断3基变换换入和换出变量的确定1检验数单纯形表的矩阵表述3218141314161221812123人工变量及其处理二两阶段法三线性规划问题的各种情况讨论当约束条件出现或时不能直接找到单位矩阵如下例例22
第二章 线性规划原理与解法
§2-1 线性规划求解原理 §2-2 单纯形方法 §2-3 人工变量及其处理

运筹学 第二章 单纯形法

运筹学 第二章 单纯形法

按最小非负比值规则：
5 0 1 1/ 3 1 1 2 1
x2 x3
5 0 1 1/ 3 0 2/3 0 1/ 3 1
0 15 0 1/ 6 0 4 0 1/ 6 1 1 0 1/ 3 0 8 0
至此，检验行已没有负数， 当前解即为最优解。
0
此时对应的LP问题为：
min S 0 x1 0 x2 x3 x4 0 x5 1
x4 1 x1 2 x2 2 x3 s.t 0 x1 3x2 3x3 x4 x5 5 x 0 (i 1,2,3,4,5) i
i 1, ,5
可行基{ x1 , x 2 , x 3 }
令非基变量 x4 , 最优值：
x 5为0，得到最优解
17 max Z 2
15
7 3 15 X 3 ( , , ,0,0)T 2 2 2
此基本可行解对应可行域的顶点(7 / 2, 3 / 2) 其结果与图解法一致。 总结：①在迭代过程中要保持常数列向量非负，这能保证基 可行解的非负性。最小比值能做到这一点。 ②主元素不能为0。因为行的初等变换不能把0变成1。
此时，
x4
已经从24降到了0，达到了非基的取值，变
成非基变量。从而得到新的可行基{x1 , x3 , x5 } 。 由此得到一个新的基本可行解： X 1 ( 4,0,15,0,1)T
8
此基本可行解对应可行域的顶点(4,0)
目标函数值： ( X1 ) 2 4 8 Z ( X 0 ) 0. Z
T
X 0 (0,0,15,24,5)
(对应可行域的 o(0,0) )
显然不是最优。 因为从经济意义上讲， x1 0, x2 0

2-线性规划的单纯形法6_两阶段法

2-线性规划的单纯形法6_两阶段法

-M
-1
x6
x3 sacj impj
0
-2 2 1
1
0 -M
M-1
0
1 -1 0
0
0 0 0
-1
0 M -M
1
0 -M 0
-2
1
2M-1
-3M-1
1
1
1
— η=-M-1
0
-1
x4
x2
3
0
0
1
0
0
1
0
-2
-1
2
1
-5
-2
12
1
4
-
-1
x3
sacj impj
-2
2 1
0
-1
0
1
-1 0
0
0 0
Page 7
x5 0 b 2 Ө 2
-1
x5
sacj impj
3
-3
3
4
-4
4
0
0
0
-1
1
-1
1
-1
0
12
η=-12 2 4 η=-4
3
0 -1
x2 x5 sacj impj
2 -5
5 -5
1 0 0
0
1 -4 4 -4
Page 22
0 -1
0 1
-1 0
1
-1
得到最优解（0，2，0，0，4），此时 x 依然在基中，所以原问题没有最优解。
Page 24
cj
CB 0 xB x4
0
x1 1
0
x2 -2
0
x3 1
0
x4 1

运筹学 线性规划 单纯形法

运筹学 线性规划 单纯形法
量，alk为主元素
1．xk替换xl 2．列出新的单纯形表
① 对主元素行（第l行）
bl bl / alk , alj alj / alk
②其它行i（i≠l）
bi bi aik bl / alk , aij aij aik alj / alk
唯一最优解
例1：某糖果厂用原材料A、B、C加工成三种不同牌号的糖 果甲、乙、丙。已知各种牌号的糖果中A、B、C含量，原 料成本，各种原料每月限制用量，三种牌号糖果的单位加 工费及售价如下表所示。问该厂每月生产这三种牌号糖果 多少kg，使该厂获利最大。试建立该问题的LP的数学模型。
解：若用变量 xij 表示捷运公司在第 i(i 1,2,3,4)个月初签定的租借期为
j( j 1,2,3,4)个月的仓库面积的合同（单位为100 m）2 。因5月份起该公司不需 要租借仓库，x24 x33 x34 x42 x43 x44 均为零。该公司希望总的租借费用为最
小，故有如下的数学模型：
10 x1 2 1 0 1 1 1 1
8 x2 2 0 1 2 1 2 1
cjzj 0 0 1 2 6 M+2
答：最优解为 x1=2, x2=2, x3=0, OBJ=36
3.大M法的一些说明
（1）人工变量被迭代出去后一般就不会再成为基变量
（2）大M法实质上与原单纯形法一样，M 可看成一
个很大的常数 （3）当检验数都满足最优条件，但基变量中仍有人工
添加松弛变量、人工变 量 列出初始单纯形表
3.对目标函数求极大值标准型线性规 划问题，单纯形法计算步骤的框图
计算各列检验数бj
所有бj0
基变量中
是
有非零的 人工变量
否
某非基变

线性规划及单纯形法详解演示文稿


收集 数据 和 建立 模型
求解 模型 和 优化 方案
检验 模型 和 评价 方案
方案 实施 和 不断 改进
制定决策
第1章 线性规划与单纯形法
运筹学的一个主要的分支是数学规划。
数学规划研究：在一些给定的条件（约束条件）下， 求所考察函数（目标函数）在某种意义下的极值（极 小或极大）问题。 例如：在经济决策中，经常会遇到诸如在有限的资源 （人、原材料、资金等）情况下，如何合理安排生产， 使效益达到最大；或者给定具体的任务，如何统筹安 排现有资源，能够完成给定的任务，使花费最小这类 问题。 在这章，我们重点介绍的是应用最为广泛的线性规划 问题。
自己动手试一试【解】 两种新产品的有关数据如表：
车间
1 2 3
单位利润 （元）
单位产品的生产时间 （小时）
门
窗
1
0
0
2
3
2
每周可获得的生产时间 （小时）
4 12 18
300
500
自己动手试一试【解】 设x1为每周门的产量（扇），x2为每周窗的产量 （扇）。 线性规划模型如下：
maxz 300x1 500x2
仅仅生产II产品，设备的生产能力还有剩余。结论是 两种产品都要进行生产。 （4）两种产品的产量会受到什么限制条件呢？ 各种设备的生产能力，即占用各种设备的工时。 （5）要决策的问题是：I产品生产多少？II产品生产多 少？才能实现利润最大化呢？
一、线性规划模型实例（问题的提出）
按工艺资料规定，
生产例每1件-产1【品解I需】占：用各设备分别为2、1、4、0h；
二、线性规划问题的数据模型
1、线性规划模型的一般表达形式 （1）一般形式
min或（max）z c1x1 c2 x2 ... cn xn a11x1 a12 x2 ... a1n xn (, )b1

线性规划问题的标准型 PPT

大值 • 不等式约束的转化:
åaij xij £ bi加入松弛变量
åaij xij ³ b减i 去剩余变量
当约束条件中第个方程出现ai1x1+ai2x2+…+ainxn≥bi时， 则减去一个“松弛变量”xi1≥0，使它成为等式ai1x1+ ai2x2+…+ainxn − xi1=bi。
大家好
8
2.1.2 非标准型线性规划问题的标准化
ï s.t. í
4x1 + 5x2 + x4 = 200
ï
3x1 +10x2 + x5 = 300
ï î
x1³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0, x5 ³ 0
大家好
12
非标准型转化举例（二）
min z = x1 + 2x2 - 3x3
ì ï
x1 + x2 + x3 £ 9
ï s.t. í
第2章 线性规划单纯形法
线性规划单纯形法
2.1 线性规划问题的标准型
2.2 改进的单纯形法和对偶问题
2.3 线性规划问题的应用案例
2.4
单纯形法的原理
2.5 线性规划问题的Excel处理
大家好
2
2.1 线性规划问题的标准型
由上一章可知，线性规划模型有各种不同的形 式；即目标函数可以求极大值，也可以求极小值； 约束条件可以是等式也可以是不等式，不等号可 以是“≤”也可以是“≥”；决策变量一般是非 负的，但在理论模型中可能会允许在区间（−∞， +∞）内取值。
ï ï
( ) -3x1' + x2 - 3 x3' - x3'' = 5

线性规划解的概念


x1
1
x2
1
… 1m1
1n 1
2m1
2n 2
…
…
……
xm
1
mm 1
mn m
z
0 0 …0
… z m 1
n 0
最优性检验与解的判别
定理1（最优解的判别定理）设 x(0)为(LP)的 一基可行解，若对任意的非基变量，都 有 j 0，则 x(0)为最优解，称 j 为检验数。
定理2 若对某非基变量，有
z
0 0 -5/3 -2/3 -46/3
主元
×（2/3）
例2 用单纯形法求线性规划问题的解
min z x2 3x3 2x5
x1 3x2 x3
2x5 7
s.t.
2x2 4x3 x4
12
4x2 3x3 8x5 x6 10
xj 0,( j 1,,6).
主元
基 x1 x2 x3 x4 x5 x6 b x1 1 3 -1 0 2 0 7 x4 0 -2 4 1 0 0 12 3 x6 0 -4 3 0 8 1 10 10/3 z 0 -1 3 0 -2 0 0
x y6s.t.x2y8
x , y 0
最优解
可行域
继续
等值线 x+3y=C
解的概念
可行解(feasible solution) ：满足线性规划问题(LP) 的所有约束条件的解，称为线性规划问题的一 个可行解。
可行域：(LP)的所有可行解组成的集合K称为(LP) 的可行域。若可行域为空，则称不可行。对标 准型线性规划问题，其可行域为 K {x|A x b ,x0 }
x4
-1 ○2 0 1 8 8/2
z
1 ○3 0 0 0

9 《线性规划》0934第二章2.6几何意义 2.5初始基=第九次课


x1 + 2 x2 ≤ 8 用单纯形法求解 x1 , x2 ≥ 0
求解结果如下： 求解结果如下：
xi ≥ 0 (i = 1, 2,⋯,5) 为初始可行基， 以B1=( p3 , p4 , p5 )为初始可行基，以x(1) 为初始可行基 = (0 , 0 , 4 , 3 , 8)T为初始基可行解开始； 为初始基可行解开始；
2.6 单纯形法的几何意义
一、基本概念
3、超平面和闭半空间 、
(1)、超平面：集合H称为 n中的超平面，其中 、超平面：集合 称为 中的超平面， 称为R H = { x ax = β , x ∈ R n } (2)、闭半空间 集合 ＋和H－称为 n中的闭半空间，其中 称为R 中的闭半空间， 、闭半空间: 集合H H + = { x ax ≥ β , x ∈ R n } H − = { x ax ≤ β , x ∈ R n } 是由超平面H所划分的两个闭半空间 所划分的两个闭半空间。 即，H＋和H－是由超平面H所划分的两个闭半空间。 平面中，超平面实为平面中的直线， 平面中，超平面实为平面中的直线，而由此超平面所划 分的两个闭半空间实为两个半平面 两个闭半空间实为两个半平面。 分的两个闭半空间实为两个半平面。 三维空间中，超平面就是通常所说的平面。 三维空间中，超平面就是通常所说的平面。 超平面H 恰为两个闭半空间的交集， 注: ①超平面 恰为两个闭半空间的交集，即H=H＋∩H－。 闭半空间是闭凸集(P69第2题)。 ②闭半空间是闭凸集 第 题。 闭集∩闭集 闭集→闭集 闭集 闭集 闭集 闭半空间的交集是闭凸集。 ③闭半空间的交集是闭凸集。 凸集∩凸集 凸集→凸集 凸集 凸集 凸集
ˆ x = (2 ,
(3)
3)T
ˆ x (4) = (4 , 2)T
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

离基
*
规则，取x1为进基变量。 因为最小比值θ 在第1、2
行取得，故x5为离基变量。
最小下标规则
x1为新的基变量，则对应单位列向量 于是，b11为表2-15的枢元，新基为B1=( p1，p6，p7 )。 对表2-15作初等行变换，并将x5换为x1，得新基B1对应的单纯 形表，见表2-16：
2.4 退化情形的处理
进基
变量。
离基
*
由表2-19可知， x1 、x5的 检验数均为正数，由Bland 规则取x1为进基变量。
因为最小比值θ 在第3行取 得，故x7为离基变量。
x1为新的基变量，则对应单位列向量 于是，b31为表2-19的枢元，新基为B5=( p3，p4，p1 )。 对表2-19作初等行变换，并将x7换为x1，得新基B5对应的单纯 形表，见表2-22：
二、退化问题中避免基循环的方法
P48 Beale例子 ——用Bland法则求解
解：基 B1=( p1，p6，p7 )对应的单纯形表见表2-16。 进基 由表2-16可知， x2 、x3的 检验数均为正数，由Bland 规则，取x2为进基变量。 进基的选择也符合：最 大检验数规则。
类似地，得到基 B2=( p1，p2，p7 )。
类似地，得到基 B4=( p3，p4，p7 )。
前4次迭代：用最大检验数规则和Bland规则的结论一样， 具体结果都是表2-15与2-19。
2.4 退化情形的处理
二、退化问题中避免基循环的方法
进基的选择：
P48 Beale例子 ——用Bland法则求解 不符合最大检
验数规则，否
解：基 B4=( p3，p4，p7 )对应的单纯形表见表2-19 。则x5才是进基
2、由于退化问题的目标函数值在迭代过程中可能并不改
进，一旦前面出现的基在迭代过程中又重新出现，则后面的
迭代过程可能会在几个基上面兜圈子，此现象成为“基的循
环”。
(如2.3节的例4)
3、若问题还未达到最优就出现了“基的循环”，再按照
通
常的单纯形法继续迭代下去，必然导致“死循环”，以致最终
不能得到最优解。(如P48的Beale例子)
2.4 退化情形的处理
二、退化问题中避免基循环的方法
进基的选择也
P48 Beale例子 ——用Bland法则求解
符合：最大检 验数规则
解：基
B5=(
p3，p4，p1
)对应的单纯形表见表2-22 进基
2.4 退化情形的处理
二、退化问题中避免基循环的方法
可确保不出现 方法：摄动法、字典序法、布兰德规则 基的循环
定理2.7(P50) 对任一线性规划问题LP用单纯形法求解时，按 Bland规则确定进基变量和离基变量，便不会出现基的循环。
布兰德(Bland)规则 ——进基、离基均采用最小下标规则
√规则1、当有多个检验数是正数时，选对应变量中下标最小者 为进基变量。与普通单纯形法：有区别 即由 m inj| j 0 r (2 .3 9 )确定进基变量为xr 。
类似地，得到基 B3=( p3，p2，p7 )。
2.4 退化情形的处理
二、退化问题中避免基循环的方法
P48 Beale例子 ——用Bland法则求解
解：基 B3=( p3，p2，进p基7 )对应的单纯形表见表2-18 。 由表2-18可知， x4 、x5的 检验数均为正数，由Bland 规则，取x4为进基变量。 进基的选择也符合：最 大检验数规则。
规则2、当最小比值θ同时在多行达到时，选取对应基变量中 下标最小者为离基变量。与普通单纯形法：没有区别
即由
m in jl
确定离基变量为xjs 。
b bllr0m birin 0 b biir0 js
(2.40)
2.4 退化情形的处理
二、退化问题中避免基循环的方法
P48 Beale例子 ——用Bland法则求解
2.4 退化情形的处理
一、退化问题可能会出现基的循环
非退化情形： 对非退化的线性规划问题使用单纯形法时，
由于每次迭代都使目标函数值有所改进，从而经过有限次迭 代，必能求得最优解或判断问题无最优解。
退化情形： 对退化的线性规划问题，使用单纯形法时：
1、如果迭代过程中基不出现重复，则经过有限次迭代也 能得到最优解或判断问题无最优解。
min
f
3 4
x1
150x2

1 50
x3
6 x4
1
1
s.t. 4 x1 60 x2 25 x3 9 x4 x5
1
1
2 x1 90x2 50 x3 3x4 x6
解：取初始基为B0=( p5，p6，p7 ) 且原问题即为基B0对应的典式。 0 基B0对应的单纯形表见表2-15 。 0 且此问题为退化的线性规划问题。
x3
x7 1
xi 0 (i 1,2,L ,7)
2.4 退化情形的处理
二、退化问题中避免基循环的方法
进基的选择也
P48 Beale例子 ——用Bland法则求解
符合：最大检 验数规则
解：基 B0=( p5，p6，p7 )对应的单纯形表见表2-15 。 进基
由表2-15可知， x1 、x3的 检验数均为正数，由Bland
由此确定xj s为离基变量(若上述最小值同时在几个比值上 达到，则选取其中下标最小的变量为离基变量)。然后用pr 代换pjs，得到新基 B ，再接下一步。最小下标规则
第五步，求出新基 B 对应的典式以及基可行解x (1)，然后 以 B 取代B，x (1)取代x (0)，返回第二步。
从第二步到第五步的每一次循环，称为一次单纯形迭代。
2.4 退化情形的处理
复习 单纯形法的计算步骤
第四步，若检验数中有些为正数，且它们所对应的系数 bir中有正数，则需要换基、进行迭代运算。最大检验数规则
在所有大于零的检验数中选取最大的一个，设对应的 非基变量为xr， 则取xr为进基变量，并求最小比值：
m in b biir 0bir0,i1,2,L,m b br sr 0
2.4 退化情形的处理
二、退化问题中避免基循环的方法
P48 Beale例子 ——用Bland法则求解
解：基 B2=( p1，p2，p7 )对应的单纯形表见表2-17 。 进基 由表2-17可知， 只有x3的 检验数均为正数，取x3为 进基变量。
进基的选择：既符合最 大检验数规则，又符合 Bland规则。