运筹学 魏哲巍 副教授 中国人民大学信息学院.

Presentation on theme: "运筹学 魏哲巍 副教授 中国人民大学信息学院."— Presentation transcript:

1 运筹学 魏哲巍 副教授 中国人民大学信息学院

2 联系方式 教师：魏哲巍 办公室：信息学院229 网站：建设中 没有习题课，答疑时间下周确定

3 考核方式 期中考试：35% 期末考试：35% 作业（每周一次）：25% 课堂表现：5% 期中考试安排在第9周或者第10周

4 教材与参考书 教材： 《运筹学》 运筹学教材编写组 清华大学出版社 参考书： 1．《运筹学教程》，胡运权主编， 清华大学出版社
2. 《运筹学通论》， 魏权龄等编著， 中国人民大学出版社

5 第0章：学科简介

6 绪 论 一、运筹学的历史 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤
绪 论 一、运筹学的历史 二、运筹学的特点及研究对象 三、运筹学解决问题的方法步骤 帝置酒洛阳南宫，上曰：“彻侯、诸将毋敢隐朕，皆言其情：吾所以有天下者何？项氏之所以失天下者何？”高起、王陵对曰：“陛下使人攻城略地，因以与之，与天下同其利；项羽不然，有功者害之，贤者疑之，此其所以失天下也。””高祖曰：“公知其一，未知其二。夫运筹策帷帐之中，决胜于千里之外，吾不如子房。镇国家，抚百姓，给馈饷，不绝粮道，吾不如萧何。连百万之军，战必胜，攻必取，吾不如韩信。此三者，皆人杰也，吾能用之，此吾所以取天下也。项羽有一范增而不能用，此其所以为我擒也。”群臣说服。 最早的运筹学运用：田忌赛马

7 运筹学的历史 一、起源 Lanchester (1914)：人力与火力优势与胜利之间的关系。 Edison：反潜战略。
Erlang（1910）：电话交换机排队系统。 Von Neumann 与对策论 1932年，Von Neumann提出一个广义经济平衡模型；1939年，提出了一个属于宏观经济优化的控制论模型；1944年，与Morgenstern共著的《对策论与经济行为》开创了对策论分支。 兰切斯特，第一次世界大战前期，英国工程师兰彻斯特发表了有关用数学研究战争的大量论述，建立了描述作战双方兵力变化过程的数学方程，被称为兰彻斯特方程。近战，远程 爱迪生：和兰彻斯特同时代的美国科学家爱迪生，在研究反潜斗争中也应用了数学方法，他主要是用概率论和数理统计，研究水面舰艇躲避和击沉潜艇的最优战术。 爱尔朗：哥本哈根，电话排队论 打电话询问账单、或新买的物品时，我们常常听到一段标准电话录音“所有服务生都在接电话，请不要挂断电话，下一位空闲的服务员将会接听你的电话”。为什么呼叫中心不雇佣足够服务生回答我们的问题呢？1908年一位名叫A. K. 爱尔朗的年轻人也面对同样问题。作为数学系学生，爱尔朗被劝说接受丹麦哥本哈根电话公司新成立实验室的领导工作，那时实验室急需解决一个重要难题：电话公司应该设置多少台交换机、雇佣多少接线员？

8 运筹学的正式产生：第二次世界大战 鲍德西（Bawdsey）雷达站的研究
　1939年，以Blackett为首的一个研究小组（代号“Blackett 马戏团”），研究如何改进英国的空防系统，提高英国本土防空能力。 Blackett备忘录 　1941年12月， Blackett应盟国政府的要求，写了五份题为“Scientists at the Operational Level”的简短备忘录，建议在各大指挥部建立运筹学小组，此建议被迅速采纳。据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过700名。 博拉凯特 1935年，英国科学家R。Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。1939年由漫彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的P。M。S。Blackett为首，组织了一个小组，代号“Blackett马戏团”。这个小组包括三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“Operational Research”，即“运筹学”。

9 运筹学的历史 二、创建阶段（1945—1954） 三、成长阶段（1955—现在） 特点：（1）理论发展迅速。20个分支。
主要成果：G.B.Dantzing提出的线性规划单纯形法（1947年）。 英、美、法成立“OR”学会 MIT（1948）：首开“运筹学”课。 丹捷格 三、成长阶段（1955—现在） 特点：（1）理论发展迅速。20个分支。 （2）计算机发展的推动。 （3）在世界范围内的普及。

10 运筹学的历史 Operations Research (美国)—简称OR Operational Research(英国) 作业研究(港台)
运筹学(大陆) 管理科学 （Management Science，简称MS）

11 运筹学的定义 Morse 和 Kimball 的定义 为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。 其他定义
运筹学应用科学技术和数学方法，解决专门问题，为决策者选择最优决策提供定量依据。 莫斯 金博尔 决策是定性的，运筹学只提供定量的分析 很多问题不见得能得到最优解，通常次优解或者满意解

12 运筹学的特点及研究对象 运筹学的分支 数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等 图论与网路理论 随机服务理论：排队论
存储理论 决策理论 对策论 系统仿真：随机模拟技术、系统动力学 可靠性理论 金融工程 线性规划是当约束条件及目标函数均为线性函数时的规划，通过合理分配资源问题最大化产出。 非线性规划是当约束条件或目标函数为非线性方程的规划，通过合理分配资源问题最大化产出。人们在实际应用中为计算方便，常把非线性问题近似地处理成多级线性规划问题。 整数规划是规划论的特殊问题，要求变量和目标函数采用整数进行运算。 动态规划是解决多级决策过程员优化的一种数学方法，可把多级决策过程作为总体决策，构成决策空间，并对每个决策找出其定量评估优劣的准则函数，选出准则函数为员优值的决策方案。 排队论亦称“等待理论”、“公用服务系统理论”或“随机服务系统理论”。是研究系统的排队现象而使顾客获得最佳流通的一种科学方法。 对策论是研究冲突局势下局中人如何选择最优策略的一种数学方法。由于这门学问最初是从赌博和弈棋中提出的，因此亦称“博奕论”。 存储论亦称“库存论”，是研究在何时何地从什么来源保证必需的物资储备，并使库存物资及补充采购所需的总费用最少的理论和方法

13 运筹学解决问题的方法 明确问题 建立模型 Yes 设计算法 简化？ No 整理数据 求解模型 No 评价结果 满意？

14 运筹学的应用 联合航空公司（1-2/1986，$600万） 满足乘客需求以最低成本进行订票处和机场工作班次排程
Citgo石油公司（1-2/1987，$7000万） 优化炼油运作以及产品的供应、配送和营销 旧金山警署（1-2/1989，$1100万） 用计算机系统最优排程和巡警设置 荷玛特发展公司（1-2/1987，$4000万） 商业区和办公楼销售的最优化安排 AT&T（1-2/1990，$4.06亿，更多的销售） 为公司商业用户的电话销售中心的优化选址

15 课程内容 1 线性规划问题 2 整数规划与非线性规划问题 3 动态规划问题 3 其他：排队论，图与网络，决策论

16 课程学习方法 1 本质上是一门数学课 2 线性代数为核心(线性方程，矩阵变换) 3 以解模型为重点 4 算法为导向

17 第一章：线性规划

18 本章内容 1.1 线性规划问题及其数学模型 1.2 图解法 1.3 单纯形法原理 1.4 单纯形法计算步骤 1.5 单纯形法的进一步讨论
1.6 应用举例

19 本章内容要点 线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤

20 本章主要内容框架图

21 1.1 线性规划问题及其数学模型 例1.1 某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。 已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？

22 1.1 线性规划问题及其数学模型 解：例1.1可用表1－1表示。 车间 单位产品的生产时间（小时） 每周可获得的生产时间（小时） 门 窗 1
4 2 12 3 18 单位利润（元） 300 500

23 1.1 线性规划问题及其数学模型 在该问题中，目标是总利润最大化，所要决策的变量是新产品的产量，而新产品的产量要受到三个车间每周可用于生产新产品时间的限制。因此，该问题可以用目标、决策变量和约束条件三个因素加以描述。实际上，所有的线性规划问题都包含这三个因素： （1）决策变量是问题中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。 （2）目标函数是指对问题所追求的目标的数学描述。例如利润最大、成本最小等。 （3）约束条件是指实现问题目标的限制因素。如原材料供应量、生产能力、市场需求等，它们限制了目标值所能到达的程度。

24 1.1 线性规划问题及其数学模型 （1）决策变量 本问题的决策变量是每周门和窗的产量。 可设：x1为每周门的产量（扇）；
（2）目标函数 本问题的目标是总利润最大。由于门和窗的单位利润分别为300元和500元，而其每周产量分别为x1和x2，所以每周总利润z为： z = 300x1＋500x2 （元）

25 1.1 线性规划问题及其数学模型 （3）约束条件 本问题的约束条件共有四个。 车间1每周可用工时限制：x1  4
车间3每周可用工时限制：3x1 +2x2  18 非负约束:x1  0, x2  0

26 1.1 线性规划问题及其数学模型 例1.1的线性规划模型:
这是一个典型的利润最大化的生产计划问题。其中，“max”是英文单词“maximize”的缩写，含义为“最大化”； “s.t.”是“subject to”的缩写，表示“满足于……”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最大时x1，x2的取值。

27 1.1 线性规划问题及其数学模型 本章讨论的问题均为线性规划问题。所谓“线性”规划，是指如果目标函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的规划问题就称为线性规划问题。

28 例1.2 某公司有100万元的资金可供投资（要求全部用完)。该公司有六个可选的投资项目，其各种数据如表1－2所示。
1.1 线性规划问题及其数学模型 例1.2 某公司有100万元的资金可供投资（要求全部用完)。该公司有六个可选的投资项目，其各种数据如表1－2所示。 投资项目 风险（%） 红利（%） 增长（%） 信用度 1 18 4 22 2 6 5 7 10 3 9 12 8 15

29 该公司想达到的目标为：投资风险最小，每年红利至少为6.5万元，最低平均增长率为12%，最低平均信用度为7。请用线性规划方法求解该问题。
1.1 线性规划问题及其数学模型 该公司想达到的目标为：投资风险最小，每年红利至少为6.5万元，最低平均增长率为12%，最低平均信用度为7。请用线性规划方法求解该问题。

30 1.1 线性规划问题及其数学模型 解： （1）决策变量
本问题的决策变量是在每种投资项目上的投资额。设xi为项目i的投资额（万元）（i=1,2,,6） （2）目标函数 本问题的目标为总投资风险最小，即

31 1.1 线性规划问题及其数学模型 （3）约束条件 本问题共有五个约束条件: ① 各项目投资总和为100万元; ② 每年红利至少为6.5万元;
③ 最低平均增长率为12%; ④ 最低平均信用度为7; ⑤ 非负约束。

32 1.1 线性规划问题及其数学模型 得到的线性规划数学模型为：
这是一个典型的成本（或风险）最小化问题。其中，“min”是英文单词“minimize”的缩写，含义为“最小化”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最小时的x1,x2,x3,x4,x5,x6取值

33 线性规划的模型结构: 1.1 线性规划问题及其数学模型
从以上两个例子中可以归纳出线性规划问题的一般形式：对于一组决策变量x1,x2,xn，取

34 1.1 线性规划问题及其数学模型 在线性规划模型中，也直接称z为目标函数； 称xj(j=1,2,,n)为决策变量；称cj(j=1,2,,n) 为目标函数系数或价值系数或费用系数；称 bi(i=1,2,,m)为函数约束右端常数或简称右端值，也称资源常数；称aij(i=1,2,,m;j=1,2,,n)为约束系数或技术系数。这里，cj，bi，aij均为常数。 线性规划的数学模型可以表示为下列简洁的形式：

35 1.1 线性规划问题及其数学模型 线性规划问题的标准形式

36 1.1 线性规划问题及其数学模型 讨论： 1. 当目标函数为求极小值 2. 当约束条件为不等式 3. 当取值为无约束的变量 4. 当 时

37 1.2 线性规划问题的图解法 对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图求解。 可行域与最优解 线性规划的图解法

38 1.2 线性规划问题的图解法 唯一解 无穷多解 无解 可行域无界（目标值不收敛）

39 1.2 线性规划问题的图解法 唯一解 线性规划问题具有唯一解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。例1.1就是一个具有唯一解的规划问题

40 无穷多解 1.2 线性规划问题的图解法 线性规划问题具有无穷多解是指该规划问题有无穷多个既在可行域内、又使得目标值达到最优的解。
在例1.1中，设门的单位利润从300元增加至750元，这时该问题的解将发生变化

41 1.2 线性规划问题的图解法 可行域无界 （目标值不收敛）
线性规划问题的可行域无界，是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。 在例1.1中，如果没有车间可用工时的约束，但要求门与窗的总产量不得少于4。

42 1.2 线性规划问题的图解法 无解 当线性规划问题中的约束条件不能同时满足时，无可行域的情况将会出现，这时不存在可行解，即该线性规划问题无解。 在例1.1中，若要求门的每周产量不得少于6，则需再加上一个约束条件：x16

43 唯一最优解、无穷多最优解、无界解、无可行解 若线性规划的可行域存在，则可行域是个凸集
1.2 线性规划问题的图解法 启示： 线性规划解的情况 唯一最优解、无穷多最优解、无界解、无可行解 若线性规划的可行域存在，则可行域是个凸集 若线性规划的最优解存在，则最优解一定是可行域的凸集的某个顶点

44 谢谢大家