- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Biblioteka Baidu
（二）基解，基可行解，可行基
• 基解：确定基B后，令非基变量XN=0，所得方程组AXB=b 的解称为LP关于B的基解（或基本解、基础解） • 基可行解：满足基变量为非负约束的基解 • 可行基：对应于基可行解的基，或者表述为“使基解满 足非负约束的基”
基解的特征
非基变量＝0的 解，注：基解的 基变量有可能小 于0，如： 约束x1－x2 ＝ 1 取x2为基变量， 即令x1 ＝0， 解得x2 ＝ － 1
请根据该准则，将例1 的线性规划模型转化为 标准形式！
线性规划问题解的概念
（一）可行解、最优解
1. 可行解：满足所有约束 条件（包括非负条件） 的解。 可行解的集合称为可行 集，或可行域。
90 9x1+4x2 360
原LP：Max Z=7x1+12x2
x2
9 x1 4 x 2 360 4 x1 5 x 2 200 s.t. 3 x1 10x 2 300 x1 , x 2 0
' '' max z x1' 2 x2 3 x3 3 x3 0 x4 0 x5 ' '' 2 x1' x2 x3 x3 x4 9 ' ' '' 3 x x 2 x 2 x 1 2 3 3 x5 4 s.t. ' ' '' 4 x 2 x 3 x 3 x 1 2 3 3 6 x ' , x , x ' , x '' , x , x 0 1 2 3 3 4 5
Error: Unexpected MATLAB operator
去噪问题
数学问题
目标函数： J(A) = (A与原始图像尽量接近) + r * (A尽量平滑)
分类问题（SVM）
①根据约束类型分类 【约束问题】 【无约束问题】
最优化问题
②根据目标函数及约束函数类型分类【线性规划】【非线性规划】 【二次规划】
可行解 基解
满足所有约束 的解，注：可 行解中没有基 变量的概念， 因此就有可能 解中所有变量 值都不为0。
3.非基向量、非基变量
非基向量：基向量以外的其他向量为非基向量,以N表示
如
N4= p4=
0 1 0
， N 5 = p2 =
0 0 1
非基变量：非基向量对应的决策变量xj为非基变量，记作XN 如 XN1＝(x4，x5)T
9 4 1 4 5 0 3 10 0 0 1 0 0 0 1
最优解 可行域
2. 最优解：使目标函数达 到极值的解（理应属于 可行解集）。
40 30
4x1+5x2 200 B
可行解
3x1+10x2 300
O
x1
40 50 100
1.基
x1
x2
x3
0 1
x4
x5
9 4 1 A= 4 5 0 3 10 0
0
0 0 1
设B为A的一个m m满秩子矩阵，且|B|≠0，（B中的行或列向 量线性无关，或行或列不全为0）这时，B就为该LP的一个基。 取
化一般形式为标准形式的方法:
1、目标函数为求极小值,即为: min z C T X
2、右端项bi<0 只需将等式或不等式两端同乘(－1),等式右端项必大于零
max z ' C T X
3、约束条件为不等式:（这里n为任意正数） 当约束条件为≤n时,需将约束条件左端加松弛变量 当约束条件为≥n时,需将约束条件左端减去松弛变量 4 、取值无约束的变量 可令x＝x’－x’’，其中x’ ≥0, x’’ ≥0 5 、对x≤0的情况 令x’ ＝－x，显然x’ ≥0
唯一解
多重最优解
(1)
(2)
无可行解
(3)
无有限最优解
(4)
注: 出现(3)(4)的情况时说明建模有问题
线性规划的一般形式
价值系数 决策变量 价值向量
目标函数
max
Z 2 x1 x 2
约束矩阵
Z C T X [1,2] X
5 x 2 15
约束条件
6 x 1 2 x 2 24 x1 x 2 5 x1 , x 2 0
线 性 规 划
最优化
1. 构造一个合适的目标函数，使得这个目标函数取到极值的解就是你所要求的东西 2. 找到一个能让这个目标函数取到极值的解的方法 1、我要做的决策是什么？ 2、我要达到的目标是什么？ 3、我的决策有什么约束？
>>Please！Help me denoise the picture!
9 4 1 B 1= 4 5 0 3 10 0
|B1|= 9 5 0+4 0 3+4 10 1-3 5 1- 4 4 0- 4 10 1≠0
2.基向量、基变量
基向量：对应于上述基B，组成B的向量称为基向量，记作 pj（j=1，2，…，m）
9 如 p1= 4 3
如
4 p2= 5 10
1 p3= 0 0
基变量：基向量对应的决策变量xj为基变量，记作XB
XB1＝(x1，x2，x3)T
9 4 1 4 5 0 3 10 0 0 1 0 0 0 1
A X b
右端向量
0 ,5 15 6 , 2 X 24 1 ,1 5
X 0
非负约束
线性规划的一般形式化为标准式
max z x1 2 x2 3 x3 2 x1 x2 x3 9 3 x x 2 x 4 1 2 3 s.t. 4 x1 2 x2 3x3 6 x1 0, x2 0, x3取值无约束
③根据变量类型分类【整数规划】【混合整数规划】 【0-1规划】
④其他分类方法 【多目标规划】【动态规划】
例1. （1）在有限资源的情况下，如何获得最大利润？
产品1 设备A(h) 设备B(h) 调试(h) 单件利润 0 6 1 2
产品2 5 2 1 1
可用资源 15 24 5
请针对该问题建立数学模型，并用图解法进行求解
