最优化方法与最优控制5
根据对偶问题的定义知道，原问题与对偶问题是互为对偶的。在给出原问题的对偶问题过程中应注意的几点关系：
(1) 原问题各约束条件中的限制符号，必须统一是“≤”或统一为“≥”，不必考虑向量b 的元素是否是正值；
(2) 如原问题有等式约束，则将该条件用等价的两个不等式约束条件替换，即“k f =)x (”可改写成两个不等式条件“k f ≤)x (，k f -≤-)x (”；
(3) 对偶前后都要求变量是非负的；
(4) 对偶关系是，“极大”对“极小”；“≤”对“≥”；向量c 与向量b 对调位置；矩阵A 转置。
例3-14 给出以下线性规划问题的对偶问题
212max x x z +=
12321≤+x x ； 521=+x x ； 16421≤+x x ； 21≥x ；02≥x 。
解：原问题的规范形式及对偶形式写在表3-17中。
表3-17 线性规划对偶问题
原问题
对偶问题
min 543212551612w w w w w s --++=
max 212x x z +=
1354321≥--++w w w w w
12321≤+x x ； 244321≥-++w w w w
16421≤+x x ；
0≥i w ，51≤≤i 。
521≤+x x ；
对偶问题的线性规划标准形式
521-≤--x x ； max 543212551612w w w w w s ++---= 21-≤-x ； 13654321=---++w w w w w w 01≥x ，02≥x 。
2474321=--++w w w w w
0≥i w ，71≤≤i 。
下面介绍线性规划对偶问题的一些性质。
定理3-4 在式(3-23)定义的对偶问题中，若x 和w 分别是原问题和对偶问题的任意可
行解，则一定有
w b x c T T ≤。 (3-24)
证 因为是可行解，必然满足各自的全部约束条件，即
b A ≤x ，0x ≥；
c w T ≥A ，0w ≥。
由此导出，
b w x w T T ≤A ；
c x w x T T T ≥A 。
标量的转置就是标量本身，即
b w x w w x
c x x c T T T T T T ≤=≤=A A 。 证毕 该性质表明，若*x 是求极大值问题的最优解，则*
x c T 是对偶问题目标函数的下界；若*w 是求极小值问题的最优解，则*w b T 是对偶问题目标函数的上界。其次，若其中一个问
题的解是无穷大(或无穷小)，则对偶问题无可行解；若其中一个问题无可行解，则对偶问题无可行解或解是无穷大(或无穷小)。
例3-15 讨论以下互为对偶问题的解
max 212x x z +=； min 214w w s +=；
4221≤+-x x ； 121≥--w w ； 121≤+-x x ； 2221≥+w w ； 01≥x ，02≥x 。
01≥w ，02≥w 。
解
由图3-3可知，原问题解为无穷大，对偶问题无可行解。
定理3-5 在式(3-23)定义的对偶问题中，若*
x 和*
w 分别是原问题和对偶问题的可行
解，且*
*=w b x c T T ，则*x 和*w 分别是原问题和对偶问题的最优解。
证 该定理的结论可直接有定理3-4导出，即
**=≤x
c w b x c T T T ；
**=≥w b x c w b T T T 。 证毕
定理3-6 在式(3-23)定义的对偶问题中，若*
x 是原问题的最优解，则对偶问题也必有
最优解，且最优值相等，即*
*=w b x c T T 。
证 应用单纯形法求解结果证明本定理。引入松弛(辅助)变量，原问题表示为
x c max T =z
b A s =I +x x ；0x ≥；0x ≥s 。 (3-24)
式中 n m R A ?∈，n R ∈x ，m m R ?∈I 单位矩阵，m
R ∈b 。用j a 表示系数矩阵][I A 中的 第j 个列向量。
设*n x 是原问题(3-24)的最优解(*
n x 中除去辅助变量后就是原问题的最优解*x )，与最优
解对应的基底为B ，加权系数向量为B
c 。最优解*n x 的值是b 1-B 。
由于*n x 是原问题(3-24)的最优解，对应的判别数
0≥-=j j B j c z σ；
从式(3-7)和式(3-8)
j B j B B z a c 1T -=；
-x 1+2x -x 1+x 2图3-3
(a )原问题
代入最优解判别数的表达式，得到
c )c (c c 0a c T 1T T T
1T 1T ≥?≥?≥----B A A B c B B B j j B 。 (3-25)
考虑到最右边的表达式形同对偶问题的约束条件，取T 1T )c (w -*=B B 。将式(3-25)中第
一个表达式用于所有辅助变量对应的列，因辅助变量在目标函数中的加权系数均为零，得
到0c 1
T ≥-B B ，表明*w 是对偶问题的一个可行解。
因*
x 是原问题的最优解，目标函数最优值为
b c x c 1
T T -**==B z B n ；
而对偶问题的一个可行解*w 对应的目标函数值是
*
*-*====z B s n B x c b c w b T 1T T ，
由定理3-4得知，*w 为对偶问题的最优解，而且两个问题的最优函数值相等。 证毕 定理3-6表明，如果已得到式(3-23)中的原问题的最优解*
x ，那么就可以得到对偶问题
的最优解B
B c )(w T 1-*=，其中B 是原问题中对应于*x 的基底，B c 是相应的加权向量。由式(3-25)的第一个表达式知道，在单纯形表格法的最终表格的最后一行中，已经给出了对偶
问题的最优解，即对应辅助变量的判别数的矩阵表达形式1
T c -B B 就是对偶问题的最优解*w 。从对偶问题的最终表格中，也能得到原问题的最优解。
定理3-7 (互补松弛定理)在式(3-23)定义的对偶问题中，若*x 和*w 分别是原问题和对
偶问题最优解，记T 21][x ****=n x x x 、T
21][w ****=m w w w 。引入辅助变 量记为si x ,)1(m i ≤≤和sj w ,)1(n j ≤≤。约束条件表示为
i si n
j j j
i b x x a
=+∑=*1，)1(m i ≤≤； (3-26)
j j s m
i i j
i c w w a
=-∑=*1
，)1(n j ≤≤； (3-27)
0≥si x ，)1(m i ≤≤；0≥sj w ，)1(n j ≤≤。
则一定有
0=*i si w x ，)1(m i ≤≤； 0=*j sj x w ，)1(n j ≤≤。
证 用*i w 和*j x 分别乘到式(3-26)和式(3-27)的两边，得到
**=**=+∑i i i si n
j i j j
i w b w x w x a
1
，)1(m i ≤≤； (3-28) **=**=-∑j j j j s m i j i j
i x c x w x w a
1
，)1(n j ≤≤； (3-29)
式(3-28)和式(3-29)各自累加，得到
*=*=**==+∑∑∑w b T 1
11m
i i si n
j i
j
j
i m
i w x w x a
；
*
=*=**==-∑∑∑x c T 1
1
1
n
j j j s m i j i j
i n
j x w x w a
；
因*
*
=w b x c T
T
，上述两式相减，得到
0=+∑∑**n
j sj m i
si
x w w x
；
考虑到 0≥*i w ，0≥si x ，)1(m i ≤≤；0≥*j x ，0≥sj w ，)1(n j ≤≤，上式成立只能是 各项都等于零，即定理命题得证。 证毕 定理3-7表明，如果原问题(对偶问题)的最优解中的某个变量si x (sj w )具有非零值，则 对偶问题(原问题)的最优解中的变量*i w (*j x )值为零。若原问题的最优解中的变量(对偶问题) *j x (*
i w )值非零，则对偶问题(原问题) 的最优解中的变量sj w (si x )值为零。
例3-16 讨论以下互为对偶问题的解
max 214x x z +=； min 321412w w w s ++=；
122321≤-x x ； 43321≥-+w w w ； 1621≤-x x ；
1262321≥+--w w w ；
4221≤+-x x ； 01≥w ，02≥w ，03≥w 。
01≥x ，02≥x 。
解：采用单纯形表格法求解，对应的最终表格分别为表3-18和表3-19。
38=*z ；T ]029068[x =*；
T x ]4/1104/900[=σ；
38=*s ；T ]004/1104/9[w =*； T w ]680290[=σ。 这个简单例子验证了定理3-6和定理3-7。注意，4x 是原问题的第2个松弛变量，显然，
满足024=*
w x 。
3-6 对偶单纯形法
本节首先介绍对偶单纯形法的解题思路，然后给出具体操作步骤。 设线性规划原问题为
x c max T =z ；
b x =A ， 0x ≥。
下面导出适合采用对偶单纯形法的形式。把等式约束转化为
b x ≤A ，b x -≤-A ；
则原线性规划问题的对偶问题为
2T 1T w b w b min -=s ；
c w w 2T 1T ≥-A A ，0w 1≥，0w 2≥；
令自由变量21w w w -=，于是原等式约束问题的对偶问题为
w b min T =s ；
c w T ≥A ，
w 自由。 (3-30)
定理3-5表明，如果原问题的一个基本可行解*
x 中的基本变量值为
b x 1-*=B B ， (3-31) T 1T )
c (w -*=B B (3-32)
是对偶问题的可行解，则*
x 和*w 分别是原问题和对偶问题的最优解。因此，若得到对偶问题的一个可行解w ，且w 使(3-30)约束具有m 个等式关系，由式(3-31)和式(3-32)可得到
原问题的基本变量值B x 。若0x ≥B
，由B x 和零值的非基本变量构成基本解就是原问题的最优解。若有0
≥=-B B
。这就是对偶单纯形法的解题思路。
对偶问题的可行解是满足约束方程c w T
≥A 的，即满足0c )(c T -1T T ≥-B A B 。这就是
说，原问题的基本解B
x 是满足最优性判据的，但不一定是可行的。因此，对偶单纯形法的各次迭代都是在保证满足最优性的基础上进行的，逐步使不可行的基本解变为可行基本解，得到的基本可行解就是最优解。作为比较，单纯形法的各次迭代是在保证基本解是可行的条件下进行的，逐步使基本可行解达到最优解。
应用对偶单纯形法的线性规划问题标准形式
x c min T =z ；
0b Ix x =+s A ，
0x ≥，0x ≥s ，0c ≥，0b 自由。 (3-33)
注意：一般线性规划问题转换成标准形式(3-33)的操作顺序如下， (1) 确认目标函数求极小值；若为求极大值，则目标函数反号；
(2) 确认加权系数均为非负值；若0 (3) 确认约束条件均改换成“≤”形式，引入松弛变量s x ，构成等式约束条件。 对偶单纯形法的操作步骤如下： 1. 设置初始表格 表格的首行是标题栏(参见表3-20)，标明标题下面的数据是那些变量或参数的数值。从左向右依次是基本变量、j a 和0b ，最右一行是选择进入变量时作计算 用的工作单元。在初始表中，基本变量从上到下依次为j n x +，m j ≤≤1。表格的倒数第2 行，最左单元填入z 字母，表示“z ”行的数据与目标函数值有关，接着是对应j x 的判别 数，在原始表中是加权系数，接着单元里的数据是当时的反号的目标函数值。 表3-20 对偶单纯形初始表格 2. 最优性检验 如果，所有00≥i b ，m i ≤≤1就得到了最优解，“z ”行的最右边的数 据就是目标函数的最大值。 如果没有得到最优解，就需要更换基底，即选择退出变量(对应表格的行选择)和进入变量(对应表格的列选择)。 3. 选择退出变量 既然未得到可行解，表明有小于零的基本变量即00 4. 选择进入列 必须在满足最优性的条件下选择进入列。通过下面的分析导出选取方法。 设j x 作为进入变量，应用初等变换将r 行和j 列相交的元素值变换为1，j 列上的其它 元素值都变换为0。此时，各判别数为 rj rk j k k a a /σσσ-= ，m n k +≤≤1。 若0≥rj a ，因00 要保证所有判别数0≥k σ ，选取的rj a 应满足 ]0|/max[/<=rk rk k rj j a a a σσ。 (3-34) 这样，新基本变量0>j x 。按式(3-34)选取进入列，对应的变量就是进入变量j x ，在标题 栏变量名左边加标记，即“↓j x ”。 5. 计算基本变量 将“←j x ”改为“r x ”，为下一次迭代准备合格的“初始表”，应用初 等变换将r 行和j 列相交的元素值变换为1，，表示新的基本变量r j b x 0=。j 列上的其它元 素值都变换为0。 在进行上述计算操作过程，同时完成了判别数j σ的计算，数据保存在“z ” 行中； 完成了目标函数值的计算，数值保存该行最后一个元素中。 在步骤5完成后，返回步骤2，直到获得最优解。 例3-17 试用对偶单纯形法求解以下线性规划问题 312min x x z +=； 10321≥-+x x x ； 162321≥+-x x x ； 0≥i x ，3,2,1=i 。 解： 312min x x z +=； ?? ????--=??????----1610x 1012101111；0x ≥ (1) 设置初始表3-21；初始基本变量T T 54]1610[][x --==x x B ，不可行； (3) 选取退出变量 因00102< (4) 选取进入列 因211233//a a σσ>，选取3x 作为进入变量； (5) 计算基本变量 见表3-22；以下不再重复，参见表3-23； 因所有00≥i b ，表3-23是最终表格。最优解为T ]0018280 [x =*；最优值 为18min =*z 。说明：对偶单纯形法在记录单元中最优值为反号值。 表3-23 例3-17的最终结果 X B x 1 x 2 x 3 x 4 x 5 0 x 2 5/2 1 0 -2 -1/2 28 x 3 3/2 0 1 -1 -1/2 18 z 2/4 1 1/2 -18 3-7 线性规划应用举例 线性规划问题都能应用单纯形法和对偶单纯形法处理。本节介绍线性规划在运输、分配等方面的应用。这些方面的线性规划问题都有自身特有形式，因而有自己特殊、有效的处理方法。本节分别用几个例子介绍这些方法。 3-7-1 运输问题 运输问题代表一类约束条件很有特点的线性规划问题。 某种产品有n 个产地，m 个销地。产地i 的产量为i a ，销地j 的需求量为j b 。从产地i 运往销地j 的产品数量为j i x ，其单位运价为j i c 。该产品产销平衡。应如何安排运输，才能 使总运输费用最低。 根据问题要求，可以列出以下数学表达式： ∑∑===n i m j j i j i x c z 11min ； i m j j i a x =∑=1，n j ≤≤1；j n i j i b x =∑=1 ，m j ≤≤1； (3-35) ∑∑===m j j n i i b a 1 1 ；0≥j i x ，n j ≤≤1，m j ≤≤1。 约束条件式(3-35)有以下几个特点：所有约束条件都是等式约束；所有变量在约束方程中的系数都是1；在)(m n +个变量方程中，只有)1(-+m n 个独立变量。因产销平衡方程限制，减少一个独立变量。下面举例说明针对运输问题特点的简便方法。 例3-18 某产品有三个制造厂位于A 、B 和C 三地。各厂月产量依次为200、600和700单位。产品销往D 、E 、F 和G 四地，各地每月需求量依次为300、300、400和500单位。从产地到销地的销量j i x 及运费单价j i c 如表3-24所示。问应该如何安排运输使总运输费用最少。 1111 1212 1313 1414 B x 21，c 21 = 17 x 22，c 22 = 14 x 23，c 23 = 12 x 24，c 24 = 13 C x 31，c 31 = 18 x 32，c 32 = 18 x 33，c 33 = 15 x 34，c 34 = 12 若用标准的单纯形表格法，因其变量数)(m n ?和约束条件数)(m n +都很大，填写单纯形表格不方便。这里介绍运输问题的表格法(简化的单纯形表格法)及操作步骤。同样，先找出初始基本可行解，然后逐步优化，最终得到最优解。 1. 求取初始基本可行解 求取初始基本可行解有两种常用方法，西北角法和行列最小法。 a) 西北角法 先绘制出含有)(m n ?单元的表格，首行填入产品销地名称及需求量，第一列填写产品生产地名称及产出量，如表3-25所示。西北角法就是从表格的左上角开始，寻找初始基本可行解。填写表格(产销平衡)优先原则是，左方销地需求优先，上方产地销售优先。在左上角填写不超出产量和销量的数字，产量剩余数填写入右边相邻格，需求量不足数填入下边相邻格。循此继进，填写到表格的右下角，就得到初始基本可行解。 本例的初始基本可行解见表3-25，格中带有括号的数字是填写顺序，实际操作时不使用，带下划线的数字是运输单价。表中未说明部分是为最优性检验准备的。 b) 行列最小法 西北角法总是从表格的右上角开始寻找初始基本可行解，这种方法完全没有考虑目标函数值的大小。下面介绍考虑目标函数值大小的寻找初始基本可行解的行列最小法。基本表格同西北角法，只是每格中还标注有运费单价，用带下划线的数字表示，见表3-26。 行列最小法是单价最低的格优先填写。首先找出单价最低的格j i x ，在格中填写尽可能 大的数),min(j i j i b a x =，若产品不足销地所需，则i 行剩余格填写0，否则j 列剩余格填 写0。接着在未填写格中，找出单价最低的格kh x ，在格中填写尽可能大的数，要保证k 行 的数据累加值小于k a ，且h 列的数据累加值小于h b ，行和列的剩余格处理同前。依此方法 填满表格，就得到初始基本可行解。填写过程参见表3-26。 注意：表中带有括号的数字表示填写顺序，它们和填写的数值0都是便于描述填写过程而使用的，实际处理时不使用。 2. 逐步优化基本可行解 在得到初始基本可行解后，按下述操作步骤优化目标函数，直到获得最优解。 (1) 计算行列乘子i u 和j v 1 (1) 13 11 15 20 B a 2 = 600 100 (2) 17 300 (3) 14 200 (4) 12 13 4 C a 3 = 700 18 18 200 (5) 15 500 (6)12 7 v j 13 10 8 5 1 13 11 15 20 B a 2 = 600 100 (5) 17 100 (4) 14 400 (2) 12 0 (3) 13 C a 3 = 700 200 (6) 18 0 (4) 18 0 (2) 15 500 (3) 12 表3-26与表3-25优化方法是相同的，用表3-25作为进行优化的初始表。引入与基本可行解相对应的乘子i u 和j v ，并将它们的值附加在表格的右侧和下边，见表3-25。它们的 值满足：01=u ，j i j i c v u =+，其中 j i c 所在格有大于零的数据j i x 。 (2) 最优性检验 如何判断所得到的解是最优解？如果不能够用变更基本变量使费用减少，则所得解就是最优解。考察表3-25给出的虚线框(闭回路)，若让非基本变量31x 转为基本变量，将其值 增加1，为保持产销平衡，须使21x 值减1、23x 值增1和33x 减1。这次基本变量替换引起 的费用变化为 )()()(331232313321233131v u v u v u c c c c c f +-+-++=--+=， 即 )(133131v u c f +-=。 显然，若31f 是负值，表示运费降低，应采取基本变量替换。反之，拒绝这次变量替换。因 此，最优性检验准则是，若所有非基本变量的 0)(≥+-=j i j i j i v u c f ， (3-36) 则得到的解就是最优解。由式(3-36)的 (产销平衡) 推导过程得知，j i f 的计算值与闭回路形 状无关，因此，最优性检验很方便。 如果不满足式(3-36)，则进行基本变量替换，获取新基本可行解。在得到新解后，需更新行列乘子i u 和j v 的值，进行最优性检验。如此重复，直到得到最优解。 由于在非基本变量格上j i j i c v u =+不成立，例如表3-25中31131820c v u =≠=+， 计算结果是虚假费用，因此，称这种优化的方法为虚假费用法。 再回到本例，根据表3-25，关于非基本变量格的j i f 计算如下： 1101112=-=f ； 781513=-=f ； 1552014=-=f ； 491324=-=f ； 2201831-=-=f ； 1171832=-=f 。 检验结果不满足最优性条件，因只有031 对应新基本可行解的表格是表3-27，表中的行列乘子i u 和j v 的值已更新。 12x 作为 113333x 作为退 出变量。对应新基本可行解的表格是表3-28。 1 13 11 15 20 B a 2 = 600 17 300 14 300 12 1 3 2 C a = 700 100 18 18 100 15 500 12 5 最优性检验：613=f ；1314=f ；121=f ；324=f ；232=f ；133=f 。已经满足最优 性检验条件，得到最优解。 作为练习，可以在行列最小法得到的初始基本可行解的基础上，进行基本可行解优化。结果是，只需一次迭代就得到了最优解。一般来说，行列最小法在获取初始基本可行解时，已经完成了部分优化工作，减少了后续的优化步骤。 3-7-2 分配问题 设有n 个人和n 种工作。不同人作不同工作时支出不一样。设第i 人作第j 种工作支出为j i c 。现在给每人分配一件工作。怎样分配工作，才能使总支出最少？ 设1=j i x 表示第i 人作第j 种工作，而0=j i x 表示第i 人不作第j 种工作。数学表达为 ∑∑===n i n j j i j i x c z 11 min ； 11=∑=n j j i x ，n j ≤≤1； 11 =∑=n i j i x ，n i ≤≤1；]1,0[∈j i x 。 分配问题是一种特殊的“运输问题”。它的特点是：(1)m n =；(2)1==j i b a ；(3)j i x 仅能取值为0或1；(4)基本可行解中的基本变量个数为n ，而且值等于1。显然，解分配问 题可以用单纯形表格法或当作是“运输问题”求解,分配问题的特殊性使得分配问题能有特 别方便的求解方法。 由于j i x 仅能取值为0或1，那么，目标函数值只是n 个较小的加权系数j i c 累加和，选 出的j i c 要保证约束条件成立。分配问题就变成在加权系数矩阵C 中选取j i c , 选取结果要保 证每一行和每一列都有一个而且只能有一个被选中。加权系数矩阵C 为 ???? ???? ??=nn n n n n c c c c c c c c c C 21222 2111211。 为了使目标函数取最小值，当然，要在数值较小的满足条件的j i c 中选取。为便于观察，将 每一行的数都减去本行中最小数，再将每一列的数减去本中列最小数。此时, 各行和各列中， 至少有一个0，即有多于n 个较小的j i c 可以选用，需要检查是否能保证每一行和每一列都 有一个而且只有一个被选中。检查办法是，用横线和竖线划去尽可能多的0，若划线根数等 于n ，则得到最优解， 例3-19 车间给5个工人分配5件不同工作，每个工人完成不同工作所需工时如表3-29 1 13 11 15 20 B a 2 = 600 17 200 14 400 12 1 3 3 C a 3 = 700 200 18 18 15 500 12 5 v j 13 11 9 7 所示。如何分配工作才能使总工时消耗最少？ 表3-29 工作 1 2 3 4 5 工人 1 6 5 9 4 6 2 3 8 3 9 5 3 2 7 6 5 6 4 5 9 8 3 8 5 1 3 7 4 2 解：0C 即为表3-29中的方块。每一行减去本行中最小的数，如第一行减去4，最后一 行减去1，得到1C 。接着，1C 中每一列减去本列中最小的数(0是最小的数)，得到2C 。因 不可能用4根横竖直线划去2C 中的8个0，在其中可以找到最优解。可逐行(或列)选取，若 有多个0，则选取所在列(或行)无其它0的变量；问题可能有多解。本例可选取 155********=====x x x x x ；155********=====x x x x x 。15=*z 。 上述两个表达式表示选取变量顺序，前者逐行选取，后者逐列选取。结果相同，表示只有唯一解。 如果在2C 中可以用少于n 根横竖直线划去所有0，又该如何处理。这时，将不在划线 上的各元素都减去它们中最小的数值，并把这个最小值加到横竖线交叉的元素值上，构成 新的矩阵，重新划横竖线，必须要n 根横竖直线划去所有0。 上面解题时，先作行处理的。现在，先作列处理，并说明当2C 未满足要求时的处理方 法。1C 和2C 如下面所示。4根横竖直线划去2C 中的7个0，不在划线上的最小数是1，处 理后，得到3C ，该矩阵满足要求，得到与先作行处理相同的最优解。 ?? ??????????=0140060564423 4136052416251C ；?? ??????????=01 4 0060564312 3036052305142C ；????? ???????=02 401 5045421120 37053204043C 。 155********=====x x x x x ；155 442312 31=====x x x x x 。15=*z 。 习题三 3.1 某工厂生产A 和B 两种产品，都要经过组装和测试车间加工。产品A 所需组装和测试工时分别为10工时/件和5工时/件，产品B 所需工时为6工时/件和4工时/件；组装车间的生产能力为1200工时/周，测试车间为800工时/周。A 和B 两种产品的单件利润分别为150元/件和100元/件。如何安排生产，才能获得最高利润？ 3.2 某工厂生产A 和B 两种产品，需使用1y 、2y 和3y 三种原料。生产1吨A 需要1 吨2y 和2吨3y 原料，生产1吨B 需要三种原料各1吨。A 和B 两种产品的利润分别为50 元/吨和100元/吨。现有原料1y 为250吨、2y 为300吨、3y 为400吨。A 和B 两种产品各 生产多少吨，能够获得最高利润？ 3.3 某工地需要长度分别为3、4、6、8米的条钢各200根，问最少要领取20米长的 ?? ??????????=13 620 5056243450 260502051 21C ；????? ???????=03 610 4055233440 16040105022C 。 条钢多少根才能满足需要？ 3.4 求解线性规划问题 21max x x z +=； 122321≤-x x ； 4221-≥-x x ； 1621≤-x x ； 01≥x ，02≥x 。 3.5 求解下列线性规划问题 a) 21max x x z +=； 2221≤+x x ； 11≤x ； 01≥x ；02≥x 。 b) 21min x x z +=； 2221≥+x x ； 11≤x ； 221≥-x x ； 01≥x ；02≥x 。 c) 21max x x z α+=； 1221-≥-x x ； 3321-≥-x x ； 01≥x ；02≥x 。 试讨论α的取值(范围)对问题解的影响。 3.6 用单纯形法求解下列线性规划问题 a) 4321223max x x x x z +++=； 83421≤++x x x ； 64321≤++x x x ； 6242≤+x x ； 0≥i x ，41≤≤i 。 b) 432144max x x x x z +++=； 788434321≤+++x x x x ； 912544321≤+++x x x x ； 395264321≤+++x x x x ； 0≥i x ，41≤≤i 。 c) 32132max x x x z ++=； 32321≤++x x x ； 63232≤+x x ； 623321≤++x x x ； 0≥i x ，31≤≤i 。 d) 32132min x x x z -+=； 30431≤+-x x ； 2523321≤-+x x x ； 0≥i x ，31≤≤i 。 e) 3212min x x x z ++=； 664321≤++x x x ； 52321≤+x x ； 132321=++x x x ； 01≥x ，02≥x ，3x 自由。 f) 43219810min x x x x z ++-=； 74744321≤+++-x x x x ； 7056324321≤+++x x x x ； 14324321=++-x x x x ； 35352321=+-x x x ； 0≥i x ，41≤≤i 。 3.7 求解线性规划问题 3212m a x x x x z -+=； 43321≤+-x x x ； 44321≤-+x x x ； 232321≥+-x x x ； 0≥i x ，31≤≤i 。 3.8 求解下列线性规划问题 a) 4321322max x x x x z +++=； 50324321≤+++x x x x ； 50234321≤+++x x x x ； 75244321≤+++x x x x ； 75324321≤+++x x x x ； 0≥i x ，41≤≤i 。 b) 43214232max x x x x z +++=； 1532534321≤+++x x x x ； 156244321≤+++x x x x ； 932224321≤+++x x x x ； 124224321≤+++x x x x ； 0≥i x ，41≤≤i 。 3.9 用对偶单纯形法求解下列线性规划问题的对偶问题解： a) 4321232max x x x x z +++=； 24234321≤+++x x x x ； 322434321≤+++x x x x ； 363324321≤+++x x x x ； 482224321≤+++x x x x ； 0≥i x ，41≤≤i 。 b) 4321342max x x x x z +++=； 30224321≤+-+x x x x ； 322431≤++x x x ； 452234321≤+++x x x x ； 20243≤-x x ； 0≥i x ，41≤≤i 。 3.10 有A 、B 、C 和D 四个面包厂，供应E 、F|、G 和H 四个小镇。每千个面包的运输费用如表3-30所示。E 、F|、G 和H 四镇每天需消费面包依次为6000、12000、5000和8000只，A 、B 、C 和D 四厂每天生产能力分别为7000、8000、11000和5000只。求最小费用的运输安排。 表3-30运输费用表 E F G H A 14 10 8 7 B 10 8 8 7 C 12 10 12 14 D 6 8 14 15 3.11 某车间要分配5个工人生产5种产品A 、B 、C 、D 和E ，由于技术问题，各人生产各种产品耗时(分钟)见表3-31，表中“×”表示该工人不合适生产这种产品。如何分配工作才能获得最高产值？ 表3-31 生产耗时表 A B C D E 1 25 22 22 25 22 2 × 28 28 30 20 3 25 28 22 × 25 4 28 25 20 28 28 5 30 25 20 22 25 3.12 某车间要分配5个工人操作5台机器A 、B 、C 、D 和E ，由于技术问题，各人操作不同机器时每小时所产生的利润不同(元)见表3-32，表中“×”表示该工人不合适操作这台机器。如何分配工作才能获得最高利润？ 表3-32 利润表 A B C D E 1 8 × 8 9 10 2 8 8 9 9 8 3 6 6 7 7 × 4 7 8 7 9 7 5 7 7 8 10 9 浅谈最优控制 发表时间：2008-12-10T10:25:09.263Z 来源：《黑龙江科技信息》供稿作者：李晶1 陈思2 [导读] 主要阐述了关于最优控制问题的基本概念，最优控制是最优化方法的一个应用。最优化一般可以分为最优设计、最优计划、最优管理和最优控制四个方面。 摘要：主要阐述了关于最优控制问题的基本概念，最优控制是最优化方法的一个应用。最优化一般可以分为最优设计、最优计划、最优管理和最优控制四个方面。而最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科，解决最优控制问题的主要方法有古典变分法、极大值原理和动态规划。通过以上知识的讲解使初学者能够快速掌握最优控制的问题。关键词：最优化；最优控制；极值 最优控制是最优化方法的一个应用，如果想了解最优控制必须知道什么是最优化方法。所谓最优化方法为了达到最优化目的所提出的各种求解方法。从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。 最优化一般可以分为最优设计、最优计划、最优管理和最优控制四个方面。（1）最优设计:世界各国工程技术界,尤其是飞机、造船、机械、建筑等部门都已广泛应用最优化方法于设计中，从各种设计参数的优选到最佳结构形状的选取等，结合有限元方法已使许多设计优化问题得到解决。一个新的发展动向是最优设计和计算机辅助设计相结合。电子线路的最优设计是另一个应用最优化方法的重要领域，它存在着巨大的开发潜力，尤其是对于学电工学的学生来说。配方配比的优选方面在化工、橡胶、塑料等工业部门都得到成功的应用,并向计算机辅助搜索最佳配方、配比方向发展。（2）最优计划:现代国民经济或部门经济的计划，直至企业的发展规划和年度生产计划，尤其是农业规划、种植计划、能源规划和其他资源、环境和生态规划的制订,都已开始应用最优化方法。一个重要的发展趋势是帮助领导部门进行各种优化决策，使工作结构简单，工作效率最高化，节省了很多时间。（3）最优管理：一般在日常生产计划的制订、调度和运行中都可应用最优化方法。随着管理信息系统和决策支持系统的建立和使用，使最优管理得到迅速的发展。（4）最优控制：主要用于对各种控制系统的优化。下面着重来解释一下最优控制。 最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科。它是现代控制理论的重要组成部分。这方面的开创性工作主要是由贝尔曼（R.E.Bellman）提出的动态规划和庞特里亚金等人提出的最大值原理。这方面的先期工作应该追溯到维纳（N.Wiener）等人奠基的控制论（Cybernetics）。1948年维纳发表了题为《控制论——关于动物和机器中控制与通讯的科学》的论文，第一次科学的提出了信息、反馈和控制的概念，为最优控制理论的诞生和发展奠定了基础。钱学森1954年所著的《工程控制论》（EngineeringCybernetics）直接促进了最优控制理论的发展和形成。 为了解决最优控制问题，必须建立描述受控运动过程的运动方程，即系统的数学模型，给出控制变量的允许取值范围，指定运动过程的初始状态和目标状态，并且规定一个评价运动过程品质优劣的性能指标。通常，性能指标的好坏取决于所选择的控制函数和相应的运动状态。系统的运动状态受到运动方程的约束，而控制函数只能在允许的范围内选取。因此，从数学上看，确定最优控制问题可以表述为：在运动方程和允许控制范围的约束下，对以控制函数和运动状态为变量的性能指标函数（称为泛函）求取极值（极大值或极小值）。解决最优控制问题的主要方法有古典变分法、极大值原理和动态规划。 1 古典变分法 研究对泛函求极值的一种数学方法。古典变分法只能用在控制变量的取值范围不受限制的情况。在许多实际控制问题中，控制函数的取值常常受到封闭性的边界限制，如方向舵只能在两个极限值范围内转动，电动机的力矩只能在正负的最大值范围内产生等。因此，古典变分法对于解决许多重要的实际最优控制问题，是无能为力的。 2 极大值原理 极大值原理，是分析力学中哈密顿方法的推广。极大值原理的突出优点是可用于控制变量受限制的情况，能给出问题中最优控制所必须满足的条件。 3 动态规划 动态规划是数学规划的一种，同样可用于控制变量受限制的情况，是一种很适合于在计算机上进行计算的比较有效的方法。随着社会科技的不断进步,最优控制理的应用领域十分广泛，如时间最短、能耗最小、线性二次型指标最优、跟踪问题、调节问题和伺服机构问题等。但它在理论上还有不完善的地方，其中两个重要的问题就是优化算法中的鲁棒性问题和最优化算法的简化和实用性问题。大体上说，在最优化理论研究和应用方面应加强的课题主要有：（1）适合于解决工程上普遍问题的稳定性最优化方法的研究；（2）智能最优化方法、最优模糊控制器设计的研究；（3）简单实用的优化集成芯片及最优化控制器的开发和推广利用；（4）复杂系统、模糊动态模型的辩识与优化方法的研究；（5）最优化算法的改进。相信随着对这些问题的研究和探索的不断深入，最优控制技术将越来越成熟和实用，它也将给人们带来不可限量的影响。 参考文献 [1]胡寿松.最优控制理论与系统[M].（第二版）北京：科学出版社，2005. [2]阳明盛.最优化原理、方法及求解软件[M].北京：科学出版社，2006. [3]葛宝明.先进控制理论及其应用[M].北京：机械工业出版社，2007. [4]章卫国.先进控制理论与方法导论[M].西安：西北工业大学出版社，2000. 约束最优化问题 一实习目的 1.熟练掌握科学与工程计算中常用的基本算法； 2.掌握分析问题，设计算法的能力； 3.掌握模块化程序设计的基本思想，注重模块的“高内聚，低耦合”； 4.采用自顶向下，逐步细化的编程思想完成程序书写； 5.牢固建立“清晰第一，效率第二”的软件设计观念； 6.掌握软件调试，测试的基本技能和方法； 7.提高科技报告的书写质量； 8.在掌握无约束最优化问题求解方法的前提下，对一般情形下的约束最优化问题进行研究，通过实习掌握外点罚函数法、内点罚函数法、乘子法、线性近似规划法和序列二次规划法在求解一般情形下的约束最优化问题的应用。 二问题定义及题目分析 问题1： 要求用外点罚函数法和内点罚函数法解决约束问题： Min f(x)=错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 问题2： 要求用乘子法解决约束问题： Min 错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 (错误！未找到引用源。) 问题3： 要求用线性近似规划法和序列二次规划法解决约束问题: Min 错误！未找到引用源。 s.t. 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 错误！未找到引用源。 三程序概要设计 1.外点罚函数法 Step1. 给定初始点错误！未找到引用源。,罚参数序列{错误！未找到引用源。}(常取错误！未找到引用源。),精度错误！未找到引用源。，并令k=0； Step2. 构造增广目标函数错误！未找到引用源。; Step3. 求解无约束优化问题min 错误！未找到引用源。,x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则：惩罚项充分小，或等价地错误！未找到引用源。近似可行）若错误！未找到引用源。，或者错误！未找到引用源。,错误！ 未找到引用源。,则得解错误！未找到引用源。，否则令k=k+1，转 Step2. 2.内点罚函数法： Step1. 给定初始可行解错误！未找到引用源。，罚参数序列{错误！未找到引用源。}(常取错误！未找到引用源。),精度错误！未找到引用源。，并令 k=0； Step2. 构造增广目标函数错误！未找到引用源。; Step3. 求解无约束优化问题min 错误！未找到引用源。,x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则）若错误！未找到引用源。，则得解错误！未找到引用源。，否则令k=k+1，转 Step2. 3.乘子法： Step1. 给定初始点错误！未找到引用源。，初始lagrange乘子错误！未找到引用源。,i错误！未找到引用源。罚参数序列{错误！未找到引用源。}, 精度错误！未找到引用源。，并令k=0； Step2. 构造增广目标函数错误！未找到引用源。 Step3. 求解无约束优化问题min 错误！未找到引用源。，x错误！未找到引用源。,其解记为错误！未找到引用源。； Step4. （终止准则）若错误！未找到引用源。,则得解错误！未找到引用源。，否则令 K=k+1,转Step2. 4.线性近似规划法： Step1. 给定初始点错误！未找到引用源。，步长限制错误！未找到引用源。,缩小系数错误！未找到引用源。。精度错误！未找到引用源。,并令k=0；Step2. 求解线性规划问题：min 错误！未找到引用源。 常用无约束最优化方法评价准则 方法算法特点适用条件 最速下降法属于间接法之一。方法简便，但要计算一阶偏导 数，可靠性较好，能稳定地使函数下降，但收敛 速度较慢，尤其在极点值附近更为严重 适用于精度要求不高或用于对 复杂函数寻找一个好的初始 点。 Newton法属于间接法之一。需计算一、二阶偏导数和Hesse 矩阵的逆矩阵，准备工作量大，算法复杂，占用 内存量大。此法具有二次收敛性，在一定条件下 其收敛速度快，要求迭代点的Hesse矩阵必须非 奇异且定型（正定或负定）。对初始点要求较高， 可靠性较差。 目标函数存在一阶\二阶偏导 数，且维数不宜太高。 共轭方向法属于间接法之一。具有可靠性好，占用内存少， 收敛速度快的特点。 适用于维数较高的目标函数。 变尺度法属于间接法之一。具有二次收敛性，收敛速度快。 可靠性较好，只需计算一阶偏导数。对初始点要 求不高，优于Newton法。因此，目前认为此法是 最有效的方法之一，但需内存量大。对维数太高 的问题不太适宜。 适用维数较高的目标函数 （n=10～50）且具有一阶偏导 数。 坐标轮换法最简单的直接法之一。只需计算函数值，无需求 导，使用时准备工作量少。占用内存少。但计算 效率低，可靠性差。 用于维数较低（n<5）或目标函 数不易求导的情况。 单纯形法此法简单，直观，属直接法之一。上机计算过程 中占用内存少，规则单纯形法终止条件简单，而 不规则单纯形法终止条件复杂，应注意选择，才 可能保证计算的可靠性。 可用于维数较高的目标函数。 常用约束最优化方法评价标准 方法算法特点适用条件 外点法将约束优化问题转化为一系列无约束优化问题。 初始点可以任选，罚因子应取为单调递增数列。 初始罚因子及递增系数应取适当较大值。 可用于求解含有等式约束或不等 式约束的中等维数的约束最优化 问题。 内点法将约束优化问题转化为一系列无约束优化问题。 初始点应取为严格满足各个不等式约束的内点， 障碍因子应取为单调递减的正数序列。初始障碍 因子选择恰当与否对收敛速度和求解成败有较大 影响。 可用于求解只含有不等式约束的 中等维数约束优化问题。 混合罚函数法将约束优化问题转化为一系列无约束优化问题， 用内点形式的混合罚函数时，初始点及障碍因子 的取法同上；用外点形式的混合罚函数时，初始 点可任选，罚因子取法同外点法相同。 可用于求解既有等式约束又有不 等式约束的中等维数的约束化问 题。 约束坐标轮换法由可行点出发，分别沿各坐标轴方向以加步探索 法进行搜索，使每个搜索点在可行域内，且使目 标函数值下降。 可用于求解只含有不等式约束， 且维数较低（n<5），目标函数的 二次性较强的优化问题。 复合形法在可行域内构造一个具有n个顶点的复合形，然 后对复合形进行映射变化，逐次去掉目标函数值 最大的顶点。 可用于求解含不等式约束和边界 约束的低维优化问题。 无约束优化方法---鲍威尔方法 本实验用鲍威尔方法求函数f(x)=(x1-5)2+(x2-6)2 的最优解。 一、简述鲍威尔法的基本原理 从任选的初始点x⑴o出发，先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索，得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴ 再沿此方向作一维搜索，得该方向上的一维极小点x⑴. 从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向，称为新生方向。 接着，以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴ 弃去第一环方向组中的第一个方向e1，将第一环新生方向S1补在最后，构成第二环的基本搜索方向组e2,e3,S1，依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接 Xo⑵与x3⑵,又得第二环的新生方向 S2=x3⑵-xo⑵ 沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点 二、鲍威尔法的程序 #include "stdafx.h" /* 文件包含*/ #include #include 项目三 常用无约束最优化方法（一） [实验目的] 编写最速下降法、Newton 法（修正Newton 法）的程序。 [实验学时] 2学时 [实验准备] 1．掌握最速下降法的思想及迭代步骤。 2．掌握Newton 法的思想及迭代步骤； 3．掌握修正Newton 法的思想及迭代步骤。 [实验内容及步骤] 编程解决以下问题：【选作一个】 1．用最速下降法求 22120min ()25[22]0.01T f X x x X ε=+==，，，． 2．用Newton 法求 22121212min ()60104f X x x x x x x =--++-， 初始点 0[00]0.01T X ε==，，． 最速下降法 Matlab 程序： clc;clear; syms x1 x2; X=[x1,x2]; fx=X(1)^2+X(2)^2-4*X(1)-6*X(2)+17; fxd1=[diff(fx,x1) diff(fx,x2)]; x=[2 3]; g=0; e=0.0005; a=1; fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); step=0; while g>e step=step+1; dk=-fan; %点x(k)处的搜索步长 ak=((2*x(1)-4)*dk(1)+(2*x(2)-6)*dk(2))/(dk(1)*dk(2)-2*dk(1)^2-2*dk(2)^2); xu=x+ak*dk; x=xu; %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf(' x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); %计算目标函数点x(k+1)处一阶导数值 fan=subs(fxd1,[x1 x2],[x(1) x(2)]); g=0; for i=1:length(fan) g=g+fan(i)^2; end g=sqrt(g); end %输出结果 optim_fx=subs(fx,[x1 x2],[x(1) x(2)]); fprintf('\n最速下降法\n结果：\n x=[ %d %d ] optim_fx=%d\n',x(1),x(2),optim_fx); c++程序 #include 最优化方法与最优控制复习文件 1. 非线性优化的基本概念，最优解的一阶和二阶条件，最速下降方法，拟牛顿法情况，BFGS 修正。 2. 变分问题的最优必要性条件推导，各种情况下的必要性条件，Hamilton 函数、拉格让日 函数。PPT 中讲到的最优控制实例，包括求解过程需要掌握。 3. 极大值原理搞清楚，以及PPT 中的计算实例。 4. 动态规划，原理和简单的求解技术。 5. LQR 问题也要看一下。 除此之外，还有几个作业题目大家做一下，如下所示： 1. 非线性优化中，从直观考虑最速下降法是一种最快速的迭代优化方法，实际过程中为什 么不理想？为什么采用二阶方法？二阶方法中的二阶导数矩阵怎么得到的？有什么要求？ （15分） 2. 对于函数形式为 的优化问题，若采用最速下降法求解，请给出最优搜索方向p k 的表达式。变量初值为X0=[1,1,1]T ，请写出第一步迭代过程，以及得到的X1的关于搜索步长α0表达式，在这种情况下，使得))0()0((F 0p x α+最小的搜索步长α0应该等于多少？（15分） 3. 题目要求如下，采用动态规划方法寻求从A 点到B 点的最小时间路径（A 到B 仅能向前 走），（20分） 4. 对于以下简单的标量非线性系统，请通过求解相关HJB 方程得到其最优反馈控制策略。 提示，HJB 微分方程允许如此形式的解。 5.写出如下优化控制问题的Hamiltonian 函数、优化求解的必须性条件，并通过必要性条 件的求解计算出该优化控制和状态轨线。最小化目标函数 6.根据你对优化控制求解方法的了解，目前对于优化控制问题（或者成为动态优化问题， DAOPs问题）有哪些求解方法， 7. 分数: ___________ 任课教师签字：___________ 华北电力大学研究生结课作业 学年学期：2013-2014第二学期 课程名称：优化理论和最优控制 学生姓名： 学号： 提交时间：2014年4月26日 《优化理论和最优控制》结课总结 摘要：最优控制理论是现代控制理论的核心，控制理论的发展来源于控制对象的要求。尽50年来，科学技术的迅速发展，对许多被控对象，如宇宙飞船、导弹、卫星、和现代工业设备的生产过程等的性能提出了更高的要求，在许多情况下要求系统的某种性能指标为最优。这就要求人们对控制问题都必须从最优控制的角度去进行研究分析和设计。最优控制理论研究的主要问题是：根据已建立的被控对象的时域数学模型或频域数学模型，选择一个容许的控制律，使得被控对象按预定要求运行，并使某一性能指标达到最优值[1]。 关键字：最优控制理论，现代控制理论，时域数学模型，频域数学模型，控制率 Abstract： The Optimal Control Theory is the core of the Modern Control Theory，the development of control theory comes from the requires of the controlled objects.During the 50 years， the rapid development of the scientific technology puts more stricter requires forward to mang controlled objects，such as the spacecraft，the guide missile，the satellite，the productive process of modern industrial facilities，and so on，and requests some performance indexes that will be best in mang cases.To the control problem，it requests people to research ,analyse，and devise from the point of view of the Optimal Control Theory. There are mang major problems of the Optimal Control Theory studying,such as the building the time domain’s model or the frenquency domain’s model according to the controlled objects,controlling a control law with admitting, making the controlled objects to work according to the scheduled requires, and making the performance index to reseach to a best optimal value. Keywords: The Optimal Control Theroy， The Modern Control Theroy， The 根据对偶问题的定义知道，原问题与对偶问题是互为对偶的。在给出原问题的对偶问题过程中应注意的几点关系： (1) 原问题各约束条件中的限制符号，必须统一是“≤”或统一为“≥”，不必考虑向量b 的元素是否是正值； (2) 如原问题有等式约束，则将该条件用等价的两个不等式约束条件替换，即“k f =)x (”可改写成两个不等式条件“k f ≤)x (，k f -≤-)x (”； (3) 对偶前后都要求变量是非负的； (4) 对偶关系是，“极大”对“极小”；“≤”对“≥”；向量c 与向量b 对调位置；矩阵A 转置。 例3-14 给出以下线性规划问题的对偶问题 212max x x z += 12321≤+x x ； 521=+x x ； 16421≤+x x ； 21≥x ；02≥x 。 解：原问题的规范形式及对偶形式写在表3-17中。 表3-17 线性规划对偶问题 原问题 对偶问题 min 543212551612w w w w w s --++= max 212x x z += 1354321≥--++w w w w w 12321≤+x x ； 244321≥-++w w w w 16421≤+x x ； 0≥i w ，51≤≤i 。 521≤+x x ； 对偶问题的线性规划标准形式 521-≤--x x ； max 543212551612w w w w w s ++---= 21-≤-x ； 13654321=---++w w w w w w 01≥x ，02≥x 。 2474321=--++w w w w w 0≥i w ，71≤≤i 。 下面介绍线性规划对偶问题的一些性质。 定理3-4 在式(3-23)定义的对偶问题中，若x 和w 分别是原问题和对偶问题的任意可 行解，则一定有 w b x c T T ≤。 (3-24) 证 因为是可行解，必然满足各自的全部约束条件，即 b A ≤x ，0x ≥； c w T ≥A ，0w ≥。 由此导出， b w x w T T ≤A ； c x w x T T T ≥A 。 标量的转置就是标量本身，即 五种最优化方法 1.最优化方法概述 最优化问题的分类 1）无约束和有约束条件； 2）确定性和随机性最优问题（变量是否确定）； 3）线性优化与非线性优化（目标函数和约束条件是否线性）； 4）静态规划和动态规划（解是否随时间变化）。 最优化问题的一般形式（有约束条件）： 式中f（X）称为目标函数（或求它的极小，或求它的极大），si（X）称为不等式约束，hj（X）称为等式约束。化过程就是优选X，使目标函数达到最优值。 2.牛顿法 简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法： 3）是一种函数逼近法。 原理和步骤 3.最速下降法（梯度法） 最速下降法简介 1）解决的是无约束非线性规划问题； 2）是求解函数极值的一种方法； 3）沿函数在该点处目标函数下降最快的方向作为搜索方向； 最速下降法算法原理和步骤 4?模式搜索法（步长加速法） 简介 1）解决的是无约束非线性规划问题； 2）不需要求目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。 3）模式搜索法每一次迭代都是交替进行轴向移动和模式移动。轴向移动的目的 是探测有利的下降方向，而模式移动的目的则是沿着有利方向加速移动。 模式搜索法步骤 5.评价函数法 简介 评价函数法是求解多目标优化问题中的一种主要方法。在许多实际问题中，衡量一个方案的好坏标准往往不止一个，多目标最优化的数学描述如下： min (f_1(x),f_2(x),…,f_k(x)) .g(x)<=o 传统的多目标优化方法本质是将多目标优化中的各分目标函数, 经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。常用的方法有“线性加权和法”、“极大极小法”、“理想点法”。选取其中一种线性加权 求合法介绍。 线性加权求合法 6.遗传算法 智能优化方法是通过计算机学习和存贮大量的输入-输出模式映射关系，进而达到优化的一种方法，主要有人工神经网络法，遗传算法和模拟退火法等。遗传算法基本概念 1.个体与种群 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼。种群就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。 2.适应度与适应度函数 适应度就是借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度。 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。该函数就是遗传算法中指导搜索的评价函数。 遗传算法基本流程 的就是对一定数量个体组成的生物种群进行选择、交叉、变异等遗传操作，最终求得最优解或近似最优解。 遗传算法步骤 《最优化与最优控制》教学大纲 课程编号：4050141 开课院系：自动化学院控制科学与工程系课程类别：专业选修 适用专业：自动化 课内总学时：32 学分：2 实验学时：0 设计学时：0 上机学时：0 先修课程：数学分析、线性代数、常微分方程、自动控制原理 执笔：邵立珍 审阅：董洁 一、课程教学目的 最优化与最优控制在工程技术，经济，管理等领域有广泛的应用。通过本课程的学习，使学生学会最优化的基本理论和算法，学会最优控制基本概念和理论。 二、课程教学基本要求 1．课程重点： 要求学生掌握典型的最优化算法，了解最优化的基本理论，掌握最优控制基本概念，掌握极大值原理，动态规划法了解典型最优控制问题。 2．课程难点： 极大值原理，动态规划法。 3．能力培养要求： 能够解决一些典型的最优控制问题，首先能够将实际问题，描述为最优控制问题，然后根据问题的条件，选择合适的求解工具并得到正确的答案。 三、课程教学内容与学时 课堂教学（32学时） 1．最优化概论(2学时) 最优化问题的数学模型 最优化方法及其结构 线性搜索 2．无约束最优化方法(4学时) 局部极小的条件 牛顿法 拟牛顿法 共轭梯度法 方向集法 3．约束优化的理论与方法(8学时) 约束问题和Lagrange乘子法 一阶最优条件 二阶最优条件 罚函数与障碍函数 乘子法 4．二次规划(6学时) 等式约束法 Lagrange方法 有效集法 5．最优控制概论(2学时) 经典控制与现代控制理论简介 最优控制问题的产生 最优控制问题的一般提法 最优控制问题分类 6．变分法与最优控制(4学时) 变分法 用变分法解最优控制 7．极大值原理(4学时) 末端自由的极大值原理 末端受约束的极大值原理 时变系统,复合型性能指标问题 8．动态规划法(2学时) 多步决策与动态规划 离散系统动态规划法 连续系统动态规划法 实验（上机、设计）教学（0学时） 四、教材与参考书 教材 1. 王晓陵，陆军编，《最优化方法与最优控制》，哈尔滨工程大学出版社，2008年，第1版 参考书 1. 吴受章编，《最优控制理论与应用》，机械工业出版社，2008年，第1版 2.李国勇编，《最优控制理论与应用》，国防工业出版社，2008年，第1版 3. 赫孝良等编，《最优化与最优控制》，西安交通大学出版社，1992年，第1版 最优控制 学院 专业 班级 姓名 学号 1948年维纳发表了题为《控制论—关于动物和机器中控制与通讯的科学》的论文，第一次科学的提出了信息、反馈和控制的概念，为最优控制理论的诞生和发展奠定了基础。钱学森1954年所着的《工程控制论》直接促进了最优控制理论的发展和形成。 最优控制理论所研究的问题可以概括为：对一个受控的动力学系统或运动过程，从一类允许的控制方案中找出一个最优的控制方案，使系统的运动在由某个初始状态转移到指定的目标状态的同时，其性能指标值为最优。这类问题广泛存在于技术领域或社会问题中。 从数学上看，确定最优控制问题可以表述为：在运动方程和允许控制范围的约束下，对以控制函数和运动状态为变量的性能指标函数（称为泛函）求取极值（极大值或极小值）。解决最优控制问题的主要方法有古典变分法（对泛函求极值的一种数学方法）、极大值原理和动态规划。最优控制已被应用于综合和设计最速控制系统、最省燃料控制系统、最小能耗控制系统、线性调节器等。 例如，确定一个最优控制方式使空间飞行器由一个轨道转换到另一轨道过程中燃料消耗最少，选择一个温度的调节规律和相应的原料配比使化工反应过程的产量最多，制定一项最合理的人口政策使人口发展过程中老化指数、抚养指数和劳动力指数等为最优等，都是一些典型的最优控制问题。最优控制理论是50年代中期在空间技术的推动下开始形成和发展起来的。苏联学者Л.С.庞特里亚金1958年提出的极大值原理和美国学者R.贝尔曼1956年提出的动态规划，对最优控制理论的形成和发展起了重要的作用。线性系统在二次型性能指标下的最优控制问题则是R.E.卡尔曼在60年代初提出和解决的。 最优控制理论-主要方法 解决最优控制问题的主要方法 解决最优控制问题，必须建立描述受控运动过程的运动方程 为了解决最优控制问题，必须建立描述受控运动过程的运动方程，给出控制变量的允许取值范围，指定运动过程的初始状态和目标状态，并且规定一个评价运动过程品质优劣的性能指标。通常，性能指标的好坏取决于所选择的控制函数和相应的运动状态。系统的运动状态受到运动方程的约束，而控制函数只能在允许的范围内选取。因此，从数学上看，确定最优控制问题可以表述为：在运动方程和允许控制范围的约束下，对以控制函数和运动状态为变量的性能指标函数（称为泛函）求取极值（极大值或极小值）。解决最优控制问题的主要方法有古典变分法、极大值原理和动态规划。 第一章 最优化方法的一般概念 人们在处理日常生活、生产过程、经营管理、社会发展等实际问题时，都希望获得最佳的处理结果。在有多种方案及各种具体措施可供选择时，处理结果与所选取方案和具体措施密切相关。获取最佳处理结果的问题称为最优化问题。针对最优化问题，如何选取满足要求的方案和具体措施，使所得结果最佳的方法称为最优化方法。 1-1 目标函数、约束条件和求解方法 目标函数就是用数学方法描述处理问题所能够达到结果的函数，该函数的自变量是表示可供选择的方案及具体措施的一些参数或函数，最佳结果表现为目标函数取极值。在处理实际问题时，通常会受到经济效率、物理条件、政策界限等许多方面的限制，这些限制的数学描述称为最优化问题的约束条件。求解方法是获得最佳结果的必要手段，该方法使目标函数取极值，所得结果称为最优解。针对各种类型的最优化问题，找出可靠、快捷的处理方法是最优化方法(理论)的研究范畴。 目标函数、约束条件和求解方法是最优化问题的三个基本要素。无约束条件的最优化问题称为理想最优化问题，所得结果称为理想最优解。下面用三个简单的例子，说明最优化问题的目标函数和约束条件。 例1-1 有一块薄的塑料板，宽为a ，对称地把两边折起，做成槽(如图1-1)。欲使槽的横截面积S 最大， 1x 、2x 和θ的最优值是多少？ 该问题要找出最优参数1x 、2x 和θ，使槽的横截面积S 最大，所以，目标函数为 θθsin )cos (max 221x x x S ?+=； (1-1) 由于底边与两个斜边的总长度应等于塑料板宽度a ，即约束条件为 a x x =+212。 (1-2) 有许多最优化问题可以方便地将等式约束条件代入目标函数中，使原问题转换为无约束条件的最优化问题，便于求解。例1-1为无约束条件的最优化问题时，目标函数如下 θθsin )cos 2(max 222x x x a S ?+-=。 (1-3) 例1-2 仓库里存有20米长的钢管，现场施工需要100根6米长和80根8米长的钢管，问最少需要领取多少根20米长的钢管？ 用一根20米长的钢管，截出8米管或6米长管的方法只有三种，设：1x —1根长管截 成2根8米管的根数；2x —1根长管截成1根8米管和2根6米管的根数；3x —1根长管 截成3根6米管的根数。该问题的目标函数为 321min x x x n ++=， (1-4) 现场施工需要80根8米长和100根6米长的钢管，即约束条件为 ???≥+≥+,10032,80232 21x x x x 3,2,10=≥i x i (1-5) a 图1-1 横截面积与参数关系图 第三章无约束最优化方法 本章内容及教学安排 第一节概述 第二节迭代终止原则 第三节常用的一维搜索方法 第四节梯度法 第五节牛顿法 第六节共轭方向法 第七节变尺度法 第八节坐标轮换法 第九节鲍威尔方法 第一节概述 优化问题可分为 无约束优化问题 有约束优化问题 无约束最优化问题求解基于古典极值理论的一种数值迭代方法，主要用来求解非线性规划问题 迭代法的基本思想： 所以迭代法要解决三个问题 1、如何选择搜索方向 2、如何确定步长 3、如何确定最优点（终止迭代） 第二节 迭代终止准则 1）1K K X X ε+-≤ 111/2 21K K K K n i i i X X X X ε++=??-=-≤???? ∑（） 2） 11()()()() () K K K K K f X f X f X f X or f X ε ε ++-≤-≤ 3）(1)()K f X ε+?≤ 第三节 常用的一维搜索方法 本节主要解决的是如何确定最优步长的问题。 从初始点(0)X 出发，以一定的步长沿某一个方向，可以找到一个新的迭代点，其公式如下： (1)(0)00(2)(1)11(1)() K K k k X X S X X S X X S ααα+=+=+= + 现在假设K S 已经确定，需要确定的是步长k α，就把求多维目标函数的极小值这个多维算过程中，当起步点和方向问题，变成求一个变量即步长的最优值的一维问题了。即 (1)()min ()min ()min ()K K K k k f X f X S f αα+=+= 由此可见，最佳步长*K α由一维搜索方法来确定 求*k α，使得()()()()()()min K K K K f f X S αα=+→ 一、一维搜索区间的确定 区间[,]a b 应满足 ()(*)()f a f f b α>< 最优控制问题求解方法综述 学院：信息科学与工程学院 专业班级： 学号： 姓名: 指导老师： 2013年4月27日 最优控制问题求解方法综述 摘要：最优控制理论是研究和解决从一切可能的控制方案中寻找最优解的一门学科。本文阐述了最优控制问题的基本概念，解决最优控制问题的主要方法有古典变分法、极小值原理和动态规划法。本文着重讲解各种方法的特点，适用范围，可求解问题的种类以及各方法之间的联系等。 关键字：最优控制；变分法；极小值原理；动态规划 1、最优控制问题基本介绍 最优控制理论是现代控制理论的核心，控制理论的发展来源于控制对象的要求。随着社会科技的不断进步,最优控制理论的应用领域十分广泛，如时间最短、能耗最小、线性二次型指标最优、跟踪问题、调节问题和伺服机构问题等。 所谓最优控制，就是寻找一个最优控制方案或最优控制律，使所研究的对象（或系统）能最优地达到预期的目标。最优控制研究的主要问题就是根据建立的被控对象的数学模型，选择一个容许的控制律，使得被控对象按预定要求运行，并使给定的某一性能指标达到极小值（或极大值）。在现实动态系统中，动态最优问题的目标函数是一个泛函，求解动态最优问题常用的方法有经典变分法，极小值原理，动态规划和线性二次型最优控制法等。 对于动态系统，当控制无约束时，采用经典微分法或经典变分法；当控制有约束是，采用极值原理或者动态规划；如果是线性的，性能指标是二次型形式的，则可采用线性二次型最优控制问题求解。 2、最优控制的求解方法 2.1变分法 变分法是求解泛函极值的一种经典方法，也是解决最优控制问题的本质方法，是研究最优控制问题的一种重要工具。掌握变分法的基本原理，还有助于理解以最小值原理和动态规划等最优控制理论的思想和内容。 对于没有对泛函的极值函数附加任何条件的求解方法，即无约束条件下的求解方法，我们可以利用欧拉方程求解，在一般性情况下，我们可以利用一下步骤求解： 无约束最优化直接方法和间接方法的异同 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称 无约束最优化直接方法和间接方法的异同一、什么是无约束最优化 最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。其的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。 最优化问题分为无约束最优化和约束最优化问题，约束最优化问题是具有辅助函数和形态约束条件的优化问题，而无约束优化问题则没有任何限制条件。无约束最优化问题实际上是一个多元函数无条件极值问题。 虽然在工程实践中，大多数问题都是具有约束的优化问题，但是优化问题的处理上可以将有约束的优化问题转化为无约束最优化问题，然后按无约束方法进行处理。或者是将约束优化问题部分转化为无约束优化问题，在远离极值点和约束边界处按无优化约束来处理，在接近极值点或者约束边界时按照约束最优化问题处理。所以无约束优化问题的解法不仅是优化设计方法的基本组成部分，也是优化方法的基础。 无约束最优化方法大致分为两类：一类是使用导数的间接方法，即在计算过程中要用到目标函数的导数；另一类是直接方法，即只要用到目标函数值，不需要计算导数。这里我们比较这两类方法的异同。 二、无约束最优化方法 1. 使用导数的间接方法 1.1 最速下降法 函数的负梯度方向是函数值在该点下降最快的方向。将n维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最 第九章经典最优化方法 9.1 最优化的基本概念 最优化方法是一门古老而又年青的学科。这门学科的源头可以追溯到17世纪法国数学家拉格朗日关于一个函数在一组等式约束条件下的极值问题（求解多元函数极值的Lagrange乘数法）。19世纪柯西引入了最速下降法求解非线性规划问题。直到20世纪三、四十年代最优化理论的研究才出现了重大进展，1939年前苏联的康托洛维奇提出了解决产品下料和运输问题的线性规划方法；1947年美国的丹奇格提出了求解线性规划的单纯形法，极大地推动了线性规划理论的发展。非线性规划理论的开创性工作是在1951年由库恩和塔克完成的，他们给出了非线性规划的最优性条件。随着计算机技术的发展，各种最优化算法应运而生。比较著名的有DFP和BFGS无约束变尺度法、HP广义乘子法和WHP约束变尺度法。 最优化问题本质是一个求极值问题，几乎所有类型的优化问题都可概括为如下模型：给定一个集合（可行集）和该集合上的一个函数（目标函数），要计算此函数在集合上的极值。通常，人们按照可行集的性质对优化问题分类：如果可行集中的元素是有限的，则归结为“组合优化”或“网络规划”，如图论中最短路、最小费用最大流等；如果可行集是有限维空间中的一个连续子集，则归结为“线性或非线性规划”；如果可行集中的元素是依赖时间的决策序列，则归结为“动态规划”；如果可行集是无穷维空间中的连续子集，则归结为“最优控制”。 线性规划与非线性规划是最优化方法中最基本、最重要的两类问题。 一般来说，各优化分支有其相应的应用领域。线性规划、网络规划、动态规划通常用于管理与决策科学；最优控制常用于控制工程；非线性规划更多地用于工程优化设计。 前面提到的算法是最优化的基本方法，它们简单易行，对于性态优良的一般函数，优化效果较好。但这些经典的方法是以传统微积分为基础的，不可避免地浅谈最优控制
约束最优化问题
常用最优化方法评价准则
无约束优化方法程序
常用无约束最优化方法(一)
最优化方法与最优控制复习文件
优化理论和最优控制
最优化方法与最优控制5
五种最优化方法
《最优化与最优控制》教学大纲 - 北京科技大学自动化学院
最优控制
最优化方法与最优控制1
第三章 无约束最优化方法
最优控制问题求解方法综述
无约束最优化直接方法和间接方
无约束最优化直接方法和间接方法的异同
第九章经典最优化方法