陆 玫 mlu@math.tsinghua.edu.cn 最优化方法 陆　玫 mlu@math.tsinghua.edu.cn

内容： 1. 线性规划 2. 整数规划 3. 目标规划 4. 非线性规划　

参考书 《数学规划》黄红选，韩继业编著 《优化建摸与LINDO/LINGO软件》谢金星，薛毅编著 《运筹学》＜运筹学＞教材编写组编著

作业要求与答疑安排 请使用作业纸，写清名字与学号。 每周二上午交作业。 答疑时间：每周五下午3：30---4：30 地点：理科楼1322C。 欢迎通过邮箱(mlu@math.tsinghua.edu.cn)答疑

一、运筹学（OR）发展简介 运筹学在国外 英国称为 Operational Research 美国称为 Operations Research 起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。 二战以后运筹学应用于经济管理领域（LP、计算机） 1948年英国首先成立运筹学会；1952年美国成立运筹学会。 1952年，Morse 和 Kimball出版《运筹学方法》 1959年成立国际运筹学联合会

运筹学在国内 中国古代朴素的运筹学思想 1956年成立运筹学小组 1958年提出运输问题的图上作业法 1962年提出中国邮路问题 1964年华罗庚推广统筹方法 我国于1982年加入国际运筹学联合会，并于1999年8月组织了第15届大会

二、运筹学的定义 运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会 运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse 和 Kimball 运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science

三、运筹学的工作步骤 明确问题 明确问题 建立模型 设计算法 建立模型 整理数据 求解模型 评价结果 设计算法 简化？ 整理数据 求解模型 No 建立模型 设计算法 简化？ Yes 整理数据 求解模型 No 评价结果 满意？

运筹学的主要特点： 运筹学研究和解决问题的基础是最优化技术，并强调 系统整体最优。 运筹学研究和解决问题的优势是应用各学科交叉的 方法，具有综合性。 运筹学研究和解决问题的方法具有显著的系统分析特 征，其各种方法的运用，几乎都需要建立数学模型和利 用计算机进行求解。 4. 运筹学研究和解决问题的效果具有连续性。 5. 运筹学具有强烈的实践性和应用的广泛性。

生产计划的编制 问：企业应如何安排生产，能使总收益最大？

2、数学模型 决策目标：A、B、C 产品各生产多少台使企业 总收益最大？ 决策变量：设 目标函数： 约束条件： 非负条件：

合理下料问题 现要用长7.4米的圆钢截取长2.9米、2.1米和1.5米的材料各100根，应如何下料，才能使用料最省？ 合理下料问题 现要用长7.4米的圆钢截取长2.9米、2.1米和1.5米的材料各100根，应如何下料，才能使用料最省？ 0.9 2.9 2.1 1.5 1、各种取料方式

2、数学模型 (1) 决策目标：如何取料使所用原料最少 (3)目标函数： (4) 约束条件： (5) 非负条件： (2) 决策变量：设第 j 种下料方式所用的原料根数为xj (3)目标函数： (4) 约束条件： (5) 非负条件：

人力资源安排问题 某商场是个中型的百货商场，现在需要对营业员的工作时间作出安排，营业员每周工作五天，休息两天，并要求休息的两天是连续的，问题归结为：如何安排营业员的作息时间，既能满足工作需要，又使配备的营业员人数最少？ 1、有关数据 对营业员的需求进行统计分析，营业员每天的需求人数如下表所示：

2、模型

例（挑选球员问题）某篮球教练要从8名业余队员中挑选3名队员参加专业球队，使平均身高达到最高。队员的号码、身高及所擅长的位置如下。要求：中锋1人；后卫1人；前锋1人，但1号、3号与6号队员中必须保留1人给业余队。 号码 身高（米） 位置 挑选变量 1 2 3 4 5 6 7 8 1.92 1.91 1.90 1.86 1.85 1.83 1.80 1.79 中锋 前锋 后卫 x1 x2 x3 x4 x5 x6 x7 x8

例（运输问题）要把某种货物从m个工厂运到n个商店去，其中每个工厂的库存量为a1,a2,…,am,各商店的需求量为b1,b2,…,bn,从工厂i到商店j的运费（每单位货物）为cij,确定从工厂i到商店j的运输量xij(i=1,…,m,j=1,…,n),使在满足供求的条件下，总的运费最小。

例（选址问题）设有n个市场，第j个市场的位置为(aj,bj)，对某种货物的需要量为qj, j=1,…,n,现计划建立m个仓库，第i个仓库的容量为ci,i=1,…,m,试确定仓库的位置，使各仓库到各市场的运输量与路程乘积之和最小． 解：设第i个仓库的位置为(xi,yi)，运输量为wij.

例（数据拟合问题）在实验数据处理或统计资料分析中常遇到如下问题：设两个变量x和y，已知存在函数关系，但其解析表达式或者是未知的、或者虽然为已知的单过于复杂。设已取得一组数据， (xi, yi), i=1,2,…,m 根据这组数据导出函数y=f(x)的一个简单而近似的解析表达式。 取一个简单的函数序列g0(x), g1(x),…,gn(x)

总结 最优化问题的共同特征： 每一个问题变量都用一组决策变量（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的（全局）最优解． 使得对∀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}－－－－－－超平面 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(2) d(1)

例：

定理： 证明：

多面集的表示定理 定理：设S={x|Ax=b, x≥0}为非空多面集，则有 （１）极点集非空，且存在有限个极点 （２）极方向集合为空集的充要条件是S有界；若S无界，则存在有限个极方向 （３）