1 绪论_62504216

1、最优化方法最优化方法 陆玫陆玫 内容内容： v 1. 线性规划线性规划 2. 整数规划整数规划 3. 目标规划目标规划 4. 非线性规划非线性规划 参考书参考书 v数学规划数学规划黄红选，韩继业编著黄红选，韩继业编著 v优化建摸与优化建摸与LINDO/LINGO软件软件 谢金星，薛毅编著谢金星，薛毅编著 v运筹学运筹学运筹学教材编写组运筹学教材编写组 编著编著 作业要求与答疑安排作业要求与答疑安排 v请使用作业纸，写清名字与学号。请使用作业纸，写清名字与学号。 v每周二上午交作业。每周二上午交作业。 v助教：崔振华助教：崔振华 v通过邮箱通过邮箱()答疑答疑 v总成绩总成绩=平时成绩（平时成绩

2、（10%）+大作业（大作业（15%） +期末考试成绩（期末考试成绩（70%）+出勤（出勤（5%） 一、运筹学（一、运筹学（OROR）发展简介）发展简介 v运筹学在国外运筹学在国外 英国称为英国称为 Operational Research 美国称为美国称为 Operations Research 起源于二战期间的军事问题，如雷达的设置、运输船队起源于二战期间的军事问题，如雷达的设置、运输船队 的护航舰队的规模、反潜作战中深水炸弹的深度、飞的护航舰队的规模、反潜作战中深水炸弹的深度、飞 机出击队型、军事物资的存储等。机出击队型、军事物资的存储等。 二战以后运筹学应用于经济管理领域（二战以后运筹学

3、应用于经济管理领域（LP、计算机）、计算机） 1948年英国首先成立运筹学会年英国首先成立运筹学会(ORS) ； 1952年美国成立运筹学会年美国成立运筹学会(ORSA)和管理学会和管理学会(TIMS), (1994年合并为运筹与管理学会，即年合并为运筹与管理学会，即INFORMS)。 1952年，年，Morse 和和 Kimball出版出版运筹学方法运筹学方法 1959年：成立国际运筹学联合会年：成立国际运筹学联合会(IFORS), 每每3年一次年会年一次年会 v运筹学在国内运筹学在国内 中国古代朴素的运筹学思想中国古代朴素的运筹学思想:孙子兵法孙子兵法、田忌赛马、田忌赛马 v1950年代年

4、代(钱学森、华罗庚、许国志等钱学森、华罗庚、许国志等) v 两法推广（优选法、统筹法）两法推广（优选法、统筹法） 1956年成立运筹学小组年成立运筹学小组 1958年提出运输问题的图上作业法年提出运输问题的图上作业法 1962年提出中国邮路问题年提出中国邮路问题 1964年华罗庚推广统筹方法年华罗庚推广统筹方法 我国于我国于1982年加入国际运筹学联合会，并于年加入国际运筹学联合会，并于1999年年 8月组织了第月组织了第15届大会届大会 运筹学的发展及展望运筹学的发展及展望 v运筹学取得全面的发展。表现在：运筹学取得全面的发展。表现在： v1）数学理论得到加强；）数学理论得到加强； v2）分

5、支学科大量涌现；）分支学科大量涌现； v3）应用领域不断拓宽等。）应用领域不断拓宽等。 二、二、运筹学的定义运筹学的定义 运筹学是把科学方法应用在指导人员、工商企业、政运筹学是把科学方法应用在指导人员、工商企业、政 府和国防等方面解决发生的各种问题，其方法是发展一府和国防等方面解决发生的各种问题，其方法是发展一 个科学的系统模式，并运用这种模式预测、比较各种决个科学的系统模式，并运用这种模式预测、比较各种决 策及其产生的后果，以帮助主管人员科学地决定工作方策及其产生的后果，以帮助主管人员科学地决定工作方 针和政策针和政策英国运筹学会英国运筹学会 运筹学为决策机构对所控制的业务活动作决策时，提运

6、筹学为决策机构对所控制的业务活动作决策时，提 供以数量为基础的科学方法供以数量为基础的科学方法Morse 和和 Kimball 运筹学是应用分析、试验、量化的方法对经济管理系运筹学是应用分析、试验、量化的方法对经济管理系 统中人力、物力、财力等资源进行统筹安排，为决策者统中人力、物力、财力等资源进行统筹安排，为决策者 提供有根据的最优方案，以实现最有效的管理提供有根据的最优方案，以实现最有效的管理中国中国 百科全书百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为现代运筹学涵盖了一切领域的管理与优化问题，称为 Management ScienceManagement Science 理解

7、上的几个要点：理解上的几个要点： Operation (运作运作): 某种行动或行动的某些部分某种行动或行动的某些部分(军军 事事“作战作战”) 运筹学是一种科学方法运筹学是一种科学方法 运筹学是一门应用科学运筹学是一门应用科学 运筹学用到数学运筹学用到数学(“定量定量”)，但并不是数学的分支，但并不是数学的分支 运筹学为执行部门提供决策帮助，但并不是工程的运筹学为执行部门提供决策帮助，但并不是工程的 一个分支，也不是效率工程（如一个分支，也不是效率工程（如“功效学功效学”） 运筹的职能非常类似于运筹的职能非常类似于“参谋参谋”职能职能 P.M. Morse 2:,| |; (3):,| |.

8、 | |. | |max | n n n n n nn iii i n ii xxxx x yxyxy xxx xxxxxx 若函数：满足下面条件： （ ）正定型：并且 （ ）三角不等式 齐次性 则称为上的范数 常用范数： 集合集合 00 |,0 xNxxx 的领域： 内点：内点： 00 0 0() n xSNxS xS 设，若存在，使得， 则称 为 的一个内点。 补集：补集： |, Cn SSx xS x集合 的补集定义为 开集：开集： ,xS xS 若对为内点，则称 为开集。 闭集：闭集： C SSS若集合 的补集为开集，则称 为闭集。 有界集有界集 ：0,|MxSxM S 若存在正数使得

9、成立， 则称 为有界集。 紧集：紧集：有界闭集称为紧集有界闭集称为紧集 性质：性质： 1 * 2 . i n kk n kk S xSxxxS S xSSx （ ）集合是闭集，当且仅当对任意的无穷 序列，若，则。 （ ）集合是紧集当且仅当对任意的无穷 序列，必存在收敛于 中点的子序列 函数的展开函数的展开 梯度：梯度： 1 ( )( ) ( ), T n fxfx fx xx Hesse矩阵：矩阵： 22 2 11 22 2 212 22 2 1 ( )( ) ( )( ) ( ) ( )( ) n n nn fxfx xxx fxfx fxxxxx fxfx xxx Taylor展开展开 2

10、2 : ()( )( )(|) 1 ()( )( )( )(| ). 2 nn T TT fp f xpf xf xpop f f xpf xf xppf x pop 设函数连续可微，向量，则 。 若函数 是二阶连续可微，则 定理：定理： 二次型的正定性二次型的正定性 定义：定义： ()0 ()0() T T f XX AXX f XX AXf X A 对实二次型，若，都有 成立，则称为正定二次型， 为正定矩阵。 定理：定理： 1 2 3 4. T T nA X AXA An An PAP P 对于 阶实对称矩阵 ，下列命题等价： （ ）是正定二次型（或 是正定矩阵）； （ ） 的 个顺序主子

11、式都大于零； （ ） 的 个特征值都大于零； （ ）存在可逆矩阵 ，使得 二次型的半正定性二次型的半正定性 定义：定义： ()0 ()0() T T f XX AXX f XX AXf X A 对实二次型，若，都有 成立，则称为半正定二次型， 为半正定矩阵。 定理：定理： 1 2 3 T nA X AXA A An 对于 阶实对称矩阵 ，下列命题等价： （ ）是半正定二次型（或 是半正定矩阵）； （ ） 的所有主子式（行号与列号取成相同的子式） 都大于等于零，而且至少有一个等于零； （ ） 的 个特征值都大于等于零，而且至少有一个 等于零。 凸集凸集(convex set) v定义：定义：设设

12、x,y为欧氏空间为欧氏空间En中相异的两个点，则点中相异的两个点，则点 集集 v P=x+(1-)y|R v称为通过称为通过x和和y的直线。的直线。 v定义：定义：设设SEn, ,若对若对x(1) (1), ,x(2)(2)S S及及 0,1,0,1, 都有都有 v x(1) (1)+(1- +(1-) )x(2) (2)S S v则称则称S S为凸集。为凸集。 v设设x(1) (1), ,x(2)(2)， ，,x( (k) )S,S,称称 v 1x(1)+2x(2)+kx(k) v( (其中其中1 1+ +2 2+k=1)=1)为为x(1) (1), ,x(2)(2), ,x( (k) )的

13、凸组的凸组 合合. . vH=x|pTxa 超平面超平面 vH-=x|pTxa （闭）半空间（闭）半空间 vL=L=x| |x= =x(0) (0)+ + d, ,00射线射线 凸集的性质凸集的性质 v设设S1和和S 为 为En中的两个凸集，中的两个凸集，是实数，则是实数，则 v(1) S1 =x| |xS1 为凸集。为凸集。 v(2) (2) S1S2为凸集。为凸集。 v(3) (3) S1+ +S = =x(1) (1)+ +x(2)(2)| |x(1)(1) S1 ，x(2) (2) S2为为 凸集。凸集。 v(4) (4) S1- -S = =x(1) (1)- -x(2)(2)| |

14、x(1)(1) S1 ，x(2) (2) S2为为 凸集。凸集。 凸锥和多面体凸锥和多面体 定义：定义： 0 n CECx xCCC C 设有集合，若对 中每一点 ，及任意的 ，都有，则称 为锥；若 为凸集，则称 为凸锥。 定义：定义： |x Axb有限个闭半空间的交称为多面体。 极点极点(extreme point) 定义：定义： (1)(2) (1)(2)(1)(2) (1), (0,1), SxSxxx xxSxxxx S 是非空凸集，若由 其中，必推出，是 的极 凸集凸集凸集凸集 极点极点 设设 则称则称 点点 极方向极方向(extreme direction) 定义：定义： (1)(

15、2) (1)(2)(1)(2) ,0 |0 ,0, , nn SEdEdxS xdS dSddS ddddSd dS 设 为中的闭凸集，如果对，有 则称向量 为 的方向。设为 的方向，若对任意的 有则称与是两个不同的方向。若 的方向 不 能表示为该集合的两个不同方向的正的线性组合，则称 为 的极方向。 例：例： (1)(2) 1221 (1)(2) ( ,) |,(1,1) ,( 1,1) , , TTT Sx xxxdd ddS 设 则是 的极方向。 d(1)d(2) 例：例： (1)(2) 1221 (1)(2) ( ,) |,(1,1) ,( 1,1) , , TTT Sx xxxdd

16、ddS 设 则是 的极方向。 11(1) 22 21 211 (1) (1) ,0, 1 , 1 |, | |0 xS xx xd xx xSxx xxx xdS dS 对有 ， 而 是 的方向。 1111(1) 2222 11 1122 22 2 1212 1 1111 2121 2222 () |,|,0, xyxy dS xyxy xy xyxy xy xyyx xyxy Sxxyy xyxy 1212 12 1212 12 设=,其中 ，0,是 的方向, 1= 则有 1= ,是 的方向, 2 2121221 1 11 1 212121 221 (1) 0 |() |, xxyyxyy xy x yyyyxx xyy dS 所以，是 的极方向。 定理：定理： |,0, 00. Sx Axb xdd SdAd 设是非零向量，则 是 的方向，且 ,00 () , , 0 () ,0,0. 000. xSxd A xdAxAdb xdSdS dSxS xdS A xdb AxbAd xdd “”，有，且 即 是 的方向。 “” 设 是 的方向，则由得 ， 其中 由得 又对， 证明：证明： 多面集的表示定理多面集的表示定理