1 绪论_62504216.pptVIP

总结 目标函数用决策变量的线性（或非线性）函数来表示。按问题的不同，要求目标函数实现最大化和最小化。 最优化问题的共同特征： 每一个问题变量都用一组决策变量（x1, x2, …, xn）表示某一方案，这组决策变量的值代表一个具体方案。 存在一定的约束条件，这些约束条件可以用一组线性（或非线性）等式或线性（或非线性）不等式来表示。 基本概念 可行点（可行解）：在线性规划和非线性规划中，满足约束条件的点． 可行集或可行域S：全体可行点组成的集合． 无约束问题：如果一个问题的可行集是整个空间． 对于一个规划问题，下面三种情况必占其一： (1) S＝Φ，则称该问题无解或不可行； (2)S≠Φ，但目标函数在S上无界，则称该问题无界； (3)S≠Φ且目标函数有有限的最优解，则称该问题有（有限的）最优解． 定义１：设f(x)为目标函数，S为可行域，x0∈S，若对?x∈S,有f(x)≥f(x0),则x0称为极小化问题minf(x)， x∈S的（全局）最优解． 定义２：设f(x)为目标函数，S为可行域，若存在x0的ε邻域 　　　 使得对?x∈S∩Nε(x0)，有f(x)≥f(x0),则x0称为极小化问题minf(x)， x∈S的局部最优解． 　预备知识　 线性相关与线性无关： 范数 集合 内点： 补集： 开集： 闭集： 有界集 ： 紧集： 有界闭集称为紧集． 性质： 函数的展开 梯度： Hesse矩阵： Taylor展开 定理： 二次型的正定性 定义： 定理： 二次型的半正定性 定义： 定理： 凸集(convex set) 定义：设x,y为欧氏空间En中相异的两个点，则点集 P={λx+(1-λ)y|λ∈R} 称为通过x和y的直线。 定义：设S?En,若对?x(1),x(2)∈S及?λ∈[0,1],都有 λx(1)+(1-λ)x(2)∈S 则称S为凸集。 设x(1),x(2)，…,x(k)∈S,称 λ1x(1)+λ2x(2)+…+λkx(k) (其中λ1+λ2+…+λk=1)为x(1),x(2),…,x(k)的凸组合. H={x|pTx＝a}－－－－－－超平面 H-={x|pTx≤a}－－－－－－（闭）半空间 L={x|x=x(0)+λd,λ≥0}－－－－射线 凸集的性质 设S1和S２为En中的两个凸集，β是实数，则 (1) βS1 ={βx|x∈S1}为凸集。 (2) S1∩S2为凸集。 (3) S1+S２={x(1)+x(2)|x(1)∈S1 ，x(2)∈ S2}为凸集。 (4) S1-S２={x(1)-x(2)|x(1)∈S1 ，x(2)∈ S2}为凸集。 凸锥和多面体 定义： 定义： 极点(extreme point) 定义： 凸集 凸集 极点 设 则称 点． 极方向(extreme direction) 定义： 例： d(1) d(2) 例： 定理： 证明： 多面集的表示定理 定理：设S={x|Ax=b, x≥0}为非空多面集，则有 （１）极点集非空，且存在有限个极点 （２）极方向集合为空集的充要条件是S有界；若S无界，则存在有限个极方向 （３） * 最优化方法 陆　玫 mlu@ 内容： 1. 线性规划 2. 整数规划 3. 目标规划 4. 非线性规划　 参考书 《数学规划》黄红选，韩继业编著 《优化建摸与LINDO/LINGO软件》谢金星，薛毅编著 《运筹学》＜运筹学＞教材编写组编著 作业要求与答疑安排 请使用作业纸，写清名字与学号。 每周二上午交作业。 助教：崔振华 通过邮箱(mlu@)答疑 总成绩=平时成绩（10%）+大作业（15%）+期末考试成绩（70%）+出勤（5%） 一、运筹学（OR）发展简介 运筹学在国外 英国称为 Operational Research 美国称为 Operations Research 起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。 二战以后运筹学应用于经济管理领域（LP、计算机） 1948年英国首先成立运筹学会(ORS) ； 1952年美国成立运筹学会(ORSA)和管理学会(TIMS), (1994年合并为运筹与管理学会，即INFORMS)。 1952年，Morse 和 Kimball出版《运筹学方法》 1959年：成立国际运筹学联合会(IFORS), 每3年一次年会 运筹学在国内 中国古代朴素的运筹学思想:《孙子兵法》、田忌赛马 1950年代(钱学森、华罗庚、许国志等)