发布时间 : 星期日 文章最优化理论与方法1（2014-简版）更新完毕开始阅读931829f302d276a200292e98
fx(k?1)?fx(k),k?0，1，2，?
????? 迭代法要解决的问题：
x(k?1)?x(k)???k?s(k)
即(1)选择搜索方向；(2)确定步长因子；(3)给定收敛准则。 (一) 柯西收敛准则
点列?xk?收敛的充要条件是：对于任意指定的实数??0，都存在一个只与?有关而与?无关的自然数N，使得当两自然数m，p > N时，满足
?m??p??
或
???i?1nmi??ip?2??
或 ?im??ip??i?(二) 迭代终止准则 （1）点距准则
Xk?1?Xk??1 或
?n
Xk?1?XkXk??2
其中?1、?2是事先给定的要求精度。 （2）函数值下降量准则
fk?1?fk??3 或
fk?1?fkfk??4
（3）目标函数梯度准则
?fxk??5
??至于采用哪种收敛准则，可视具体问题而定。可以取：
??10?2~10?5
第二章 线性规划
2.1 线性规划问题及其数学模型 2.1.1 问题的提出
例1：（下料问题）某车间有长度为180cm的钢管（数量足够多），今要将其截为三种不同长度的管料，长度分别为70cm、52cm和35cm。生产任务规定，70cm的管料只需100根，而52cm、35cm的管料分别不少于150根、120根，问应采取怎样的截法才能完成任务，同时使剩下的余料最少？
解：所用可能的截法共有8种，见下表：
截法 长度 (cm) 70 52 35 一 2 0 1 5 二 三 1 2 0 6 1 1 1 23 四 1 0 3 5 五 六 七 八 需要量/根 0 3 0 24 0 2 2 6 0 1 3 23 0 0 5 5 100 ?150 ?120 余料长度(cm) 上述下料问题的数学模型为：
minf?X??5x1?6x2?23x3?5x4?24x5?6x6?23x7?5x8
s.t. 2x1?x2?x3?x4?100
2x2?x3?3x5?2x6?x7?150 x1?x3?3x4?2x6?3x7?5x8?120
xi?0?i?1,2,?,8?
2.1.2 基本特点
线性规划问题的共同特征：
? 一组决策变量X表示一个方案，一般X大于等于零。 ? 约束条件是线性等式或不等式。
? 目标函数是线性的，且求目标函数最大化或最小化。 线性规划模型的一般形式：
minf?c1x1?c2x2??cnxn ?a11x1?a12x2???a1nxn???,??b1?ax?ax???ax???,??b2nn2?211222?????????ax?ax???ax??,??b
mnnm?m11m22?x1,x2,?,xq?0???xq?1,?,xn????0s.t. 线性规划问题的标准形式
(1)标准形式为—目标函数最小、约束条件等式、决策变量非负。
minf?c1x1?c2x2??cnxn
?a11x1?a12x2???a1nxn???,??b1?ax?ax???ax???,??b2112222nn2???????? ??ax?ax???ax??,??bm22mnnm?m11??x1,x2,?,xn?0s.t.(2)简写形式
minf?X???cjxj
j?1n?n??aijxj?bi,i?1,2,?,m ?j?1?x?0,j?1,2,?,n?j(3) 向量形式
minf?X??CX
?n??AjXj?bs.t. ?j?1
?x?0,j?1,2,?,n?j其中C??c1,c2,?,cn?，X??x1,x2,?,xn?T，Aj??a1j,a2j,?,amj?T，
Tb??b1,b2,?,bm?
(4) 矩阵形式
mins.t.f?X??CXAX?bX?O?a11??a1n??0????A,A,?,A???? ????O?其中 A?? 12n???????0???am1??amn??
一般线性规划问题的标准化 ? maxf?X??CX等价于minf*?X???CX ? “?” 约束：加入非负松驰变量 例1：目标函数 maxf?2x1?3x2 约束条件 x1?2x2?8
minf*??2x1?3x2?0x3?0x4?0x5 ?8?x1?2x2?x3 4x1?16 改为 ? ? x4 ? 164x2?12 ? 4 x1?4x2 ?x5?12? x1、x2?0 ??x1,x2,x3,x4,x5?0目标函数最小； 约束条件等式； 决策变量非负。 ? “?” 约束： 减去非负剩余变量，即xk可正可负（即无约束）。 例2：min f??x1?2x2?3x3 ? 3 x ?x?2x?7123minf??x1?2x2?3(x4?x5)?0x6?0x7?7 x 1 ? x 2 ? x3 ? 7 ? x1 ?x2? (x4?x5)?x6 x1 ?x2? x3?2x1 ?x2? (x4?x5) ?x7?2?3x1?x2?2(x4?x5) ?7x1,x2,x4,x5,x6,x7?0
x1,x2?0,x3无约束其中x3?x4?x5