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

Presentation on theme: "陆 玫 mlu@math.tsinghua.edu.cn 最优化方法 陆　玫 mlu@math.tsinghua.edu.cn."— Presentation transcript:

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

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

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

4 作业要求与答疑安排 请使用作业纸，写清名字与学号。 每周二上午交作业。 答疑时间：每周五下午3：30---4：30 地点：理科楼1322C。

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

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

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

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

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

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

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

12

13 合理下料问题 现要用长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、各种取料方式

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

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

16 2、模型

17 例（挑选球员问题）某篮球教练要从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

18

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

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

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

22 总结 最优化问题的共同特征： 每一个问题变量都用一组决策变量（x1, x2, …, xn）表示某一方案，这组决策变量的值代表一个具体方案。
存在一定的约束条件，这些约束条件可以用一组线性（或非线性）等式或线性（或非线性）不等式来表示。 目标函数用决策变量的线性（或非线性）函数来表示。按问题的不同，要求目标函数实现最大化和最小化。

23 基本概念 可行点（可行解）：在线性规划和非线性规划中，满足约束条件的点． 可行集或可行域S：全体可行点组成的集合．
无约束问题：如果一个问题的可行集是整个空间． 对于一个规划问题，下面三种情况必占其一： (1) S＝Φ，则称该问题无解或不可行； (2)S≠Φ，但目标函数在S上无界，则称该问题无界； (3)S≠Φ且目标函数有有限的最优解，则称该问题有（有限的）最优解．

24 定义１：设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的局部最优解．

25 　预备知识　 线性相关与线性无关：

26 范数

27 集合 内点： 补集： 开集： 闭集： 有界集 ： 紧集： 有界闭集称为紧集．

28 性质：

29 函数的展开 梯度： Hesse矩阵：

30 Taylor展开 定理：

31 二次型的正定性 定义： 定理：

32 二次型的半正定性 定义： 定理：

33 凸集(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)的凸组合.

34 H={x|pTx＝a}－－－－－－超平面
L={x|x=x(0)+λd,λ≥0}－－－－射线

35 凸集的性质 设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}为凸集。

36 凸锥和多面体 定义： 定义：

37 极点(extreme point) 定义： 设 则称 点． 极点 凸集 凸集

38 极方向(extreme direction)
定义：

39 例： d(2) d(1)

40 例：

41

42 定理： 证明：

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