管理科学理论 精选文档.ppt

《管理科学理论 精选文档.ppt》由会员分享，可在线阅读，更多相关《管理科学理论 精选文档.ppt（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理科学理论 本讲稿第一页，共八十页优化部分优化部分-主要内容主要内容第一章第一章 概述概述第二章第二章 凸分析凸分析1 1，极大、极小与鞍点，极大、极小与鞍点，极大、极小与鞍点，极大、极小与鞍点2 2，凸集与凸函数，凸集与凸函数，凸集与凸函数，凸集与凸函数3 3，凸集的分离和支撑，凸集的分离和支撑，凸集的分离和支撑，凸集的分离和支撑4 4，凸规划，凸规划，凸规划，凸规划第三章第三章 无约束优化的理论与方法无约束优化的理论与方法1，常见的一维搜索方法，常见的一维搜索方法（1 1）平分法（）平分法（）平分法（）平分法（2 2）0.6180.618法法法法（3 3）FibonacciFibonac

2、ci法法法法本讲稿第二页，共八十页2 2，多维搜索，多维搜索，多维搜索，多维搜索（1 1）梯度法（最速下降法）梯度法（最速下降法）梯度法（最速下降法）梯度法（最速下降法）（2 2）共轭方向法和共轭梯度法）共轭方向法和共轭梯度法）共轭方向法和共轭梯度法）共轭方向法和共轭梯度法（3 3）变尺度法（拟）变尺度法（拟）变尺度法（拟）变尺度法（拟NewtonNewton法）法）法）法）（4 4）直接法（）直接法（）直接法（）直接法（PowellPowell法和单纯形法）法和单纯形法）法和单纯形法）法和单纯形法）第四章第四章第四章第四章 约束非线性优化理论与方法约束非线性优化理论与方法约束非线性优化理论与

3、方法约束非线性优化理论与方法1 1，等式约束问题，等式约束问题，等式约束问题，等式约束问题（1 1）切向量与正规性）切向量与正规性）切向量与正规性）切向量与正规性（2 2）最优性条件）最优性条件）最优性条件）最优性条件2 2，具不等式约束的问题，具不等式约束的问题，具不等式约束的问题，具不等式约束的问题（1 1）下降方向集和可行方向集）下降方向集和可行方向集）下降方向集和可行方向集）下降方向集和可行方向集（2 2）最优性条件和鞍点）最优性条件和鞍点）最优性条件和鞍点）最优性条件和鞍点（3 3）对偶问题）对偶问题）对偶问题）对偶问题本讲稿第三页，共八十页3，常用的非线性约束优化的算法，常用的非线

4、性约束优化的算法（1 1）序列线性规划法）序列线性规划法）序列线性规划法）序列线性规划法（2 2）序列无约束极小化方法）序列无约束极小化方法）序列无约束极小化方法）序列无约束极小化方法v 外罚函数法和内罚函数法外罚函数法和内罚函数法v 混合罚函数与精确罚函数法混合罚函数与精确罚函数法vv 乘子法乘子法乘子法乘子法（3 3）Zoutendij Zoutendij 可行方向法可行方向法可行方向法可行方向法（4）简约梯度法与广义简约梯度法）简约梯度法与广义简约梯度法本讲稿第四页，共八十页（5 5）梯度投影法）梯度投影法）梯度投影法）梯度投影法第五章多目标优化第五章多目标优化 1 1，概述，概述，概述

5、，概述2 2，偏好关系，偏好关系，偏好关系，偏好关系3 3，ParetoPareto有效解有效解有效解有效解4 4，常用算法介绍，常用算法介绍，常用算法介绍，常用算法介绍第六章第六章第六章第六章 网络优化网络优化网络优化网络优化1 1，最短路问题，最短路问题，最短路问题，最短路问题2 2，最大流问题，最大流问题，最大流问题，最大流问题3 3，最大流最大切断定理，最大流最大切断定理，最大流最大切断定理，最大流最大切断定理本讲稿第五页，共八十页第七章第七章第七章第七章 动态规划动态规划动态规划动态规划1 1，基本概念，基本概念，基本概念，基本概念2 2，最优性原理，最优性原理，最优性原理，最优性原

6、理3 3，动态规划的解法，动态规划的解法，动态规划的解法，动态规划的解法第八章第八章第八章第八章 不确定优化的理论与方法不确定优化的理论与方法不确定优化的理论与方法不确定优化的理论与方法1 1，期望值模型，期望值模型，期望值模型，期望值模型2 2，遗传算法，遗传算法，遗传算法，遗传算法3 3，机会约束规划（，机会约束规划（，机会约束规划（，机会约束规划（Chance Constrained ProgrammingChance Constrained Programming）4 4，相关机会规划（，相关机会规划（，相关机会规划（，相关机会规划（Dependent Chance Programmi

7、ngDependent Chance Programming）5 5，模糊优化方法，模糊优化方法，模糊优化方法，模糊优化方法本讲稿第六页，共八十页Markowitz 证券组合理论证券组合理论设设设设由由由由n n个个个个证证证证券券券券组组组组成成成成的的的的证证证证券券券券组组组组合合合合，当当当当每每每每个个个个证证证证券券券券的的的的预预预预期期期期回回回回报报报报和和和和协协协协方方方方差差差差已已已已知知知知时时时时，可可可可由由由由以以以以下下下下优优优优化化化化方方方方法法法法，求求求求证证证证券券券券组组组组合合合合的最优权重：的最优权重：的最优权重：的最优权重：(1)(1)其

8、其其其中中中中 ,R为为为为事事事事先先先先给给给给定定定定的的的的证证证证券券券券组组组组合合合合预预预预期期期期收益的下界。收益的下界。收益的下界。收益的下界。本讲稿第七页，共八十页Markowitz 证券组合理论证券组合理论或或 （2）以上均为二次优化问题。以上均为二次优化问题。本讲稿第八页，共八十页一，优化问题的数学描述一，优化问题的数学描述vv例例例例1 1，选址问题，选址问题，选址问题，选址问题第一章第一章 概述概述本讲稿第九页，共八十页设某砖厂生产彩色和无色两种地砖，每吨地砖设某砖厂生产彩色和无色两种地砖，每吨地砖设某砖厂生产彩色和无色两种地砖，每吨地砖设某砖厂生产彩色和无色两种

9、地砖，每吨地砖 机时机时机时机时 工时工时工时工时 颜料（升）颜料（升）颜料（升）颜料（升）利润（元）利润（元）利润（元）利润（元）彩色彩色彩色彩色 2 3 2 3002 3 2 300无色无色无色无色 1 3 0 2001 3 0 200每天资源每天资源每天资源每天资源 10 24 8 10 24 8 最大？最大？最大？最大？问：每天应如何安排两种地砖的生产，使利润最大？问：每天应如何安排两种地砖的生产，使利润最大？问：每天应如何安排两种地砖的生产，使利润最大？问：每天应如何安排两种地砖的生产，使利润最大？例例2：生产安排问题生产安排问题本讲稿第十页，共八十页某公司有资金某公司有资金某公司有

10、资金某公司有资金A A万元，可供投资的项目有万元，可供投资的项目有万元，可供投资的项目有万元，可供投资的项目有N N 项，已知每一项目所需资金项，已知每一项目所需资金项，已知每一项目所需资金项，已知每一项目所需资金 a ai i 和预期利润和预期利润和预期利润和预期利润 c ci i，问如何安排资金？，问如何安排资金？，问如何安排资金？，问如何安排资金？解：令解：令解：令解：令 投资项目投资项目投资项目投资项目i i 不投项目不投项目不投项目不投项目i i 问题问题问题问题 集装箱容积为集装箱容积为集装箱容积为集装箱容积为A A，可选择，可选择，可选择，可选择N N 件物品装入。已知每件物品所

11、占件物品装入。已知每件物品所占件物品装入。已知每件物品所占件物品装入。已知每件物品所占容积和重量，问如何装箱使总重量最大？容积和重量，问如何装箱使总重量最大？容积和重量，问如何装箱使总重量最大？容积和重量，问如何装箱使总重量最大？例例3（投资问题（投资问题1）本讲稿第十一页，共八十页某公司有资金某公司有资金某公司有资金某公司有资金A A万元，有万元，有万元，有万元，有2 2个项目可选择投资。已知项目个项目可选择投资。已知项目个项目可选择投资。已知项目个项目可选择投资。已知项目1 1和和和和2 2的年预期收益率分别为的年预期收益率分别为的年预期收益率分别为的年预期收益率分别为20%20%和和和和

12、16%16%，且总风险函数已获得。，且总风险函数已获得。，且总风险函数已获得。，且总风险函数已获得。问如何安排投资，使收益尽可能大，风险尽可能小？问如何安排投资，使收益尽可能大，风险尽可能小？问如何安排投资，使收益尽可能大，风险尽可能小？问如何安排投资，使收益尽可能大，风险尽可能小？解：设解：设解：设解：设 x x i i 项目项目项目项目I I 的投资额，且已知总风险函数为：的投资额，且已知总风险函数为：的投资额，且已知总风险函数为：的投资额，且已知总风险函数为：在可承受风险下，求收益最大：在可承受风险下，求收益最大：在可承受风险下，求收益最大：在可承受风险下，求收益最大：例例4（投资问题（

13、投资问题2）本讲稿第十二页，共八十页在收益保证的条件下，求风险最小问题在收益保证的条件下，求风险最小问题在收益保证的条件下，求风险最小问题在收益保证的条件下，求风险最小问题双目标模型：双目标模型：双目标模型：双目标模型：本讲稿第十三页，共八十页最优化技术与方法周宗放最优化技术与方法周宗放【例例例例】令令则有则有本讲稿第十四页，共八十页设某传输网络由设某传输网络由设某传输网络由设某传输网络由n n 个电站，向个电站，向个电站，向个电站，向 m m 个负载输送电能。要求确定一个最个负载输送电能。要求确定一个最个负载输送电能。要求确定一个最个负载输送电能。要求确定一个最经济的传输方案，既要满足用户的

14、要求，又使各电站生产所需成本经济的传输方案，既要满足用户的要求，又使各电站生产所需成本经济的传输方案，既要满足用户的要求，又使各电站生产所需成本经济的传输方案，既要满足用户的要求，又使各电站生产所需成本最低？最低？最低？最低？解：解：解：解：Lagrange Lagrange 函数函数函数函数例例5 能量传输优化问题能量传输优化问题本讲稿第十五页，共八十页得到：得到：得到：得到：最优能量传输规律：最优能量传输规律：最优能量传输规律：最优能量传输规律：生产电能的边际成本与各电站相对于总耗生产电能的边际成本与各电站相对于总耗生产电能的边际成本与各电站相对于总耗生产电能的边际成本与各电站相对于总耗损

15、的边际贡献成正比，比例系数恰为损的边际贡献成正比，比例系数恰为损的边际贡献成正比，比例系数恰为损的边际贡献成正比，比例系数恰为 .本讲稿第十六页，共八十页设国际市场对我国某出口商品每年需求为设国际市场对我国某出口商品每年需求为设国际市场对我国某出口商品每年需求为设国际市场对我国某出口商品每年需求为 x x 吨，服从均匀分布：吨，服从均匀分布：吨，服从均匀分布：吨，服从均匀分布：U U（20002000，40004000）。每售出）。每售出）。每售出）。每售出1 1吨赚外汇吨赚外汇吨赚外汇吨赚外汇3 3万元，保养费万元，保养费万元，保养费万元，保养费1 1万元万元万元万元 /吨。吨。吨。吨。问应

16、如何组织出口？问应如何组织出口？问应如何组织出口？问应如何组织出口？解：设解：设解：设解：设y y为年出口量。为年出口量。为年出口量。为年出口量。需求大于出口需求大于出口需求大于出口需求大于出口 收益收益收益收益 需求小于出口需求小于出口需求小于出口需求小于出口例例6 随机优化问题随机优化问题本讲稿第十七页，共八十页求均值：求均值：求均值：求均值：建立优化模型：建立优化模型：建立优化模型：建立优化模型：求解：求解：求解：求解：y=y=35003500（吨）。（吨）。（吨）。（吨）。本讲稿第十八页，共八十页某工厂在周期性生产过程中，每一周期的产量不能超某工厂在周期性生产过程中，每一周期的产量不能

17、超过过X X件，库存不能超过件，库存不能超过件，库存不能超过件，库存不能超过Y件，初始库存为件，初始库存为件，初始库存为件，初始库存为0。现设在第。现设在第。现设在第。现设在第i i个个个个周期中，生产周期中，生产周期中，生产周期中，生产xi i 件产品的成本为件产品的成本为f fi i(x xi i)，库存库存库存库存yi件产品的件产品的件产品的件产品的成本为成本为成本为成本为 g gi i(yi i)，问如何组织生产，使，问如何组织生产，使，问如何组织生产，使，问如何组织生产，使n n个周期的总成本最个周期的总成本最小。小。解解解解：例例7 生产组织问题生产组织问题本讲稿第十九页，共八十页

18、特别若仅考虑一个周期（特别若仅考虑一个周期（特别若仅考虑一个周期（特别若仅考虑一个周期（n n1 1）：）：）：）：再不妨设再不妨设再不妨设再不妨设 f f(x x)=x=x2 2,g,g(y y)=y=y2 2，得：，得：，得：，得：得最优解：得最优解：得最优解：得最优解：本讲稿第二十页，共八十页vv古代军事运筹学思想古代军事运筹学思想古代军事运筹学思想古代军事运筹学思想vv中国古代中国古代中国古代中国古代“孙子兵法孙子兵法孙子兵法孙子兵法”渗透着量的渗透着量的渗透着量的渗透着量的分析（分析（分析（分析（19811981年美国军事运筹学会出年美国军事运筹学会出年美国军事运筹学会出年美国军事运

19、筹学会出版书中第一句话称孙武是世界上第版书中第一句话称孙武是世界上第版书中第一句话称孙武是世界上第版书中第一句话称孙武是世界上第一个军事运筹学的实践家）。一个军事运筹学的实践家）。一个军事运筹学的实践家）。一个军事运筹学的实践家）。军事运筹优化重要来源军事运筹优化重要来源本讲稿第二十一页，共八十页运筹与优化第二来源：管理运筹与优化第二来源：管理vv管理科学，按照国际管理科学会的说法，是把各种科学方法管理科学，按照国际管理科学会的说法，是把各种科学方法管理科学，按照国际管理科学会的说法，是把各种科学方法管理科学，按照国际管理科学会的说法，是把各种科学方法用于管理。企业的管理经历三个时期：用于管理

20、。企业的管理经历三个时期：用于管理。企业的管理经历三个时期：用于管理。企业的管理经历三个时期：1 1，手工式管理；，手工式管理；，手工式管理；，手工式管理；2 2，机械化管理；机械化管理；机械化管理；机械化管理；3 3，系统化管理。，系统化管理。，系统化管理。，系统化管理。vv小农经济或小手工业经济的管理是由家长、业主兼雇。这种小农经济或小手工业经济的管理是由家长、业主兼雇。这种小农经济或小手工业经济的管理是由家长、业主兼雇。这种小农经济或小手工业经济的管理是由家长、业主兼雇。这种管理方式完全凭记忆、思考，或极其简单的工具计算。管理方式完全凭记忆、思考，或极其简单的工具计算。管理方式完全凭记忆

21、、思考，或极其简单的工具计算。管理方式完全凭记忆、思考，或极其简单的工具计算。vv大规模的机械化生产，使企业管理进入机械化时期。管理职大规模的机械化生产，使企业管理进入机械化时期。管理职大规模的机械化生产，使企业管理进入机械化时期。管理职大规模的机械化生产，使企业管理进入机械化时期。管理职能分化为相对独立的部分。与此相适应，簿记、报告和机械能分化为相对独立的部分。与此相适应，簿记、报告和机械能分化为相对独立的部分。与此相适应，簿记、报告和机械能分化为相对独立的部分。与此相适应，簿记、报告和机械式计算是管理人员掌握的工具。式计算是管理人员掌握的工具。式计算是管理人员掌握的工具。式计算是管理人员掌

22、握的工具。本讲稿第二十二页，共八十页运筹与优化第三来源：经济运筹与优化第三来源：经济v数理经济学对运筹学，特别是运筹学中线性数理经济学对运筹学，特别是运筹学中线性规划产生重要的影响，许多经济学家对数理规划产生重要的影响，许多经济学家对数理经济有着显著贡献，最有名的是沃尔拉思经济有着显著贡献，最有名的是沃尔拉思(walras)，他当时研究经济平衡问题，其数学，他当时研究经济平衡问题，其数学形式为后来的数理经济学家一再研究和发展。形式为后来的数理经济学家一再研究和发展。20世纪世纪30年代奥地利和德国的经济学家推年代奥地利和德国的经济学家推广了沃尔拉思的工作。广了沃尔拉思的工作。本讲稿第二十三页，

23、共八十页数理经济学数理经济学vVon Neumann 与对策论与对策论v1932年，年，Von Neumann提出广义经济平衡模提出广义经济平衡模型；型；1939年，又提出宏观经济优化控制模型；年，又提出宏观经济优化控制模型；1944年，与年，与Morgenstern共著的共著的对策论与对策论与经济行为经济行为开创了对策论分支。开创了对策论分支。v康托洛维奇与康托洛维奇与“生产组织与计划中的数学方生产组织与计划中的数学方法法”v30年代，苏联数理经济学家康托洛维奇从事年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得生产组织与管理中的定量化方法研究，取得了很多重要成果。

24、了很多重要成果。1939年，出版年，出版生产组织生产组织与计划中的数学方法与计划中的数学方法，其思想和模型被归，其思想和模型被归入线性规划范畴。入线性规划范畴。本讲稿第二十四页，共八十页马克思也是成功地把数学用于经济研究的经马克思也是成功地把数学用于经济研究的经济学家；在济学家；在资本论资本论中，处处渗透看定量中，处处渗透看定量化的分析。化的分析。1863年致恩格斯的信中，马克思说他本人正年致恩格斯的信中，马克思说他本人正在研究微积分，并向恩格斯推荐。正如恩格在研究微积分，并向恩格斯推荐。正如恩格斯所说：马克思是当时唯斯所说：马克思是当时唯能用哲学作为能用哲学作为指导来研究数学的人。指导来研究

25、数学的人。本讲稿第二十五页，共八十页优化的性质和特点优化的性质和特点优化方法应用现有的科学技术知识和数学方法，解决实优化方法应用现有的科学技术知识和数学方法，解决实优化方法应用现有的科学技术知识和数学方法，解决实优化方法应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依际中提出的专门问题，为决策者选择最优决策提供定量依际中提出的专门问题，为决策者选择最优决策提供定量依际中提出的专门问题，为决策者选择最优决策提供定量依据。据。据。据。优化的特点优化的特点定量化分析。定量化分析。多学科交叉，如综合利用了管理学、经济学、数多学科交叉，如综合利用了管理学、经济学

26、、数量科学等理论与方法。量科学等理论与方法。最优决策。最优决策。本讲稿第二十六页，共八十页优化的主要研究对象优化的主要研究对象设备、人员、资金等如何最佳利用和配置问题、生产组设备、人员、资金等如何最佳利用和配置问题、生产组设备、人员、资金等如何最佳利用和配置问题、生产组设备、人员、资金等如何最佳利用和配置问题、生产组织问题、选址问题、运输问题以及投资与决策问题等等。织问题、选址问题、运输问题以及投资与决策问题等等。织问题、选址问题、运输问题以及投资与决策问题等等。织问题、选址问题、运输问题以及投资与决策问题等等。常用方法包括：线性和非线性规划、整数规划、网络常用方法包括：线性和非线性规划、整数

27、规划、网络常用方法包括：线性和非线性规划、整数规划、网络常用方法包括：线性和非线性规划、整数规划、网络优化、动态规划和多目标规划等。优化、动态规划和多目标规划等。优化、动态规划和多目标规划等。优化、动态规划和多目标规划等。本讲稿第二十七页，共八十页线性规划问题线性规划问题vv例例例例1 1中华家电公司推销一种新型洗衣机，有关数据见下表。中华家电公司推销一种新型洗衣机，有关数据见下表。中华家电公司推销一种新型洗衣机，有关数据见下表。中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第一月的广告预算为销售部第一月的广告预算为销售部第一月的广告预算为销售部第一月的广告预算为2 2万元，要求至少有

28、万元，要求至少有万元，要求至少有万元，要求至少有8 8次电视商次电视商次电视商次电视商业节目，业节目，业节目，业节目，1515家报纸广告，电视广告费不得超过家报纸广告，电视广告费不得超过家报纸广告，电视广告费不得超过家报纸广告，电视广告费不得超过1.2万元，电万元，电万元，电万元，电台广播至少隔日有一次。问该公司销售部应当采用怎样台广播至少隔日有一次。问该公司销售部应当采用怎样台广播至少隔日有一次。问该公司销售部应当采用怎样台广播至少隔日有一次。问该公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果的广告宣传计划，才能取得最好的效果的广告宣传计划，才能取得最好的效果的广告宣传计划，才能取

29、得最好的效果?本讲稿第二十八页，共八十页广告方式广告费用(元/次)可用最高次数/月期望的宣传效果（得分）/次电视台a(白天1 分钟)5001650电视台b(晚上30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)802515本讲稿第二十九页，共八十页本讲稿第三十页，共八十页本讲稿第三十一页，共八十页本讲稿第三十二页，共八十页对偶问题对偶问题vv例例例例 某工厂准备生产某工厂准备生产某工厂准备生产某工厂准备生产M1 1，M2，MM3 3三种产品，生产这些三种产品，生产这些产品需要产品需要N N1，N N2，N N3 3三种原料。各单位产品需要

30、消耗三种原料。各单位产品需要消耗三种原料。各单位产品需要消耗三种原料。各单位产品需要消耗的原料如下表所示：的原料如下表所示：的原料如下表所示：的原料如下表所示：原料消耗M1M2M3N1N2N3642831.511.50.5本讲稿第三十三页，共八十页产产产产品品品品MM1 1，MM2 2，MM3 3的的的的单单单单位位位位售售售售价价价价分分分分别别别别为为为为60、3030和和和和2020元元元元，且且且且都都都都能能能能售售售售出出出出。现现现现有有有有原原原原料料料料N1 1，N2 2，N3 3分分分分别别别别48、20和和和和8 8个个个个单单单单位位位位，问问问问如何安排生产才能使销售

31、收入最大？如何安排生产才能使销售收入最大？如何安排生产才能使销售收入最大？如何安排生产才能使销售收入最大？解解解解 设设设设x x1 1，x2 2，x x3分分别别为为产产品品MM1 1，MM2，MM3 3的的的的生生生生产产产产数数数数量量量量。问问问问题题题题化为如下线性规划问题：化为如下线性规划问题：化为如下线性规划问题：化为如下线性规划问题：本讲稿第三十四页，共八十页现从另一角度讨论问题：某公司打算买入该厂原料自行生产，现从另一角度讨论问题：某公司打算买入该厂原料自行生产，现从另一角度讨论问题：某公司打算买入该厂原料自行生产，现从另一角度讨论问题：某公司打算买入该厂原料自行生产，公司需

32、要确定这些原料的购买价格。设公司需要确定这些原料的购买价格。设公司需要确定这些原料的购买价格。设公司需要确定这些原料的购买价格。设y y1 1，y2，y y3 3分别为原分别为原分别为原分别为原料料料料N N1 1，N N2 2，N N3 3的购买价格，买进这些产品的总费用为：的购买价格，买进这些产品的总费用为：的购买价格，买进这些产品的总费用为：的购买价格，买进这些产品的总费用为：48 48 y1 12020y28 8y3 3。公司希望购买价格越低越好，但价格太低。公司希望购买价格越低越好，但价格太低。公司希望购买价格越低越好，但价格太低。公司希望购买价格越低越好，但价格太低工厂不愿出售，于

33、是该购买价格应受到约束。工厂不愿出售，于是该购买价格应受到约束。工厂不愿出售，于是该购买价格应受到约束。工厂不愿出售，于是该购买价格应受到约束。由于工厂使用一组原料（由于工厂使用一组原料（由于工厂使用一组原料（由于工厂使用一组原料（8 8单位单位单位单位N N1，4单位单位单位单位N N2 2，2 2单位单位单位单位N N3 3）即）即）即）即可生产出一个产品可生产出一个产品可生产出一个产品可生产出一个产品M1 1，售价，售价，售价，售价6060元，因此公司至少需付出元，因此公司至少需付出元，因此公司至少需付出元，因此公司至少需付出6060元才能买走这组原料，即元才能买走这组原料，即元才能买走

34、这组原料，即元才能买走这组原料，即 8 8 y y1 14 4y y2 22y y3 6060本讲稿第三十五页，共八十页类似地对产品类似地对产品类似地对产品类似地对产品M2 2和和MM3 3，应满足：，应满足：6 6y y12 2y y21,51,5y3 3 30 30 和和和和 y1 11.1.5y5y2 20.50.5y y3 3 2020对公司而言，问题化为如下线性规划问题：对公司而言，问题化为如下线性规划问题：对公司而言，问题化为如下线性规划问题：对公司而言，问题化为如下线性规划问题：本讲稿第三十六页，共八十页显然，当显然，当显然，当显然，当min W W=max=max z 时，双方

35、都能够得到最优结果。时，双方都能够得到最优结果。时，双方都能够得到最优结果。时，双方都能够得到最优结果。两个模型的数据来源相同，表达形式不同，经济活动意两个模型的数据来源相同，表达形式不同，经济活动意两个模型的数据来源相同，表达形式不同，经济活动意两个模型的数据来源相同，表达形式不同，经济活动意义也不同，称其为互为对偶的线性规划问题。义也不同，称其为互为对偶的线性规划问题。义也不同，称其为互为对偶的线性规划问题。义也不同，称其为互为对偶的线性规划问题。对偶定理对偶定理对偶定理对偶定理 若原问题或对偶问题中一个有解，则另一个也有若原问题或对偶问题中一个有解，则另一个也有若原问题或对偶问题中一个有

36、解，则另一个也有若原问题或对偶问题中一个有解，则另一个也有解，且它们的最优目标值相同。解，且它们的最优目标值相同。解，且它们的最优目标值相同。解，且它们的最优目标值相同。一般地有：一般地有：一般地有：一般地有：本讲稿第三十七页，共八十页对偶问题对偶问题v原问题原问题v如如v对偶问题对偶问题本讲稿第三十八页，共八十页对偶变量的经济解释对偶变量的经济解释v对偶变量对偶变量 yi 在经济意义上表示原问题第在经济意义上表示原问题第 i 种资种资源的边际贡献，即当第源的边际贡献，即当第 i 种资源增加一个单位种资源增加一个单位时，相应目标值时，相应目标值W的增量。对偶问题的最优解的增量。对偶问题的最优解

37、 yi*称原问题第称原问题第 i 种资源的影子价格。种资源的影子价格。v1，出租资源或设备，租金价格设定；，出租资源或设备，租金价格设定；v2，企业内资源，企业内资源 i 存量设定；存量设定；v3，调整资源分配量以增加利润。，调整资源分配量以增加利润。本讲稿第三十九页，共八十页运输问题运输问题 收点发点B1B2Bn发量A1C11 x 11C12x12 C1nx1na1AmCm1xm1Cm2xm2Cmn xmnam收量b1b2bn其中：其中：其中：其中：x xij ij为第为第为第为第i i个发点个发点个发点个发点A Ai i到第到第到第到第j j个收点个收点个收点个收点B Bi i的运量；的运

38、量；的运量；的运量；C Cij ij为第为第为第为第i i个发点到第个发点到第个发点到第个发点到第j j个收点的单位运费。个收点的单位运费。个收点的单位运费。个收点的单位运费。本讲稿第四十页，共八十页 运输问题模型运输问题模型vMin z=vS.t.本讲稿第四十一页，共八十页指派问题指派问题v设有设有n n 个人个人个人个人A A1 1，A A2 2，A An n被分派做被分派做被分派做被分派做n n 件事件事件事件事B B1,B B2 2，B Bn n，要求每件事必须有一人做，且不同事由不同人做。已知，要求每件事必须有一人做，且不同事由不同人做。已知，要求每件事必须有一人做，且不同事由不同人

39、做。已知，要求每件事必须有一人做，且不同事由不同人做。已知每人每人每人每人A Ai i 做每件事做每件事做每件事做每件事B Bj j 的效率的效率(如劳动工时或成本，或创造如劳动工时或成本，或创造的价值等的价值等)为为C Cij，问应如何指派，才能使工作效益最高，问应如何指派，才能使工作效益最高?v指派问题既是运输问题的特殊情形，也是整数规划的指派问题既是运输问题的特殊情形，也是整数规划的特殊情形。特殊情形。本讲稿第四十二页，共八十页指派问题的数学模型指派问题的数学模型vvMax Max z z=S.t.S.t.设当第设当第设当第设当第i i个人个人个人个人A Ai i 做第做第做第做第j j

40、个件事个件事个件事个件事B Bi i 时，变量时，变量时，变量时，变量x xij ij 取取取取1 1，否则取零；，否则取零；，否则取零；，否则取零；C Cij ij 为第为第为第为第i i 个人做第个人做第个人做第个人做第j j 件事的件事的件事的件事的效率。效率。效率。效率。本讲稿第四十三页，共八十页配矿计划的优化问题配矿计划的优化问题v某大型冶金矿业公司有某大型冶金矿业公司有14个出矿点，年产个出矿点，年产量及各出矿点矿石的平均品位均已知。按量及各出矿点矿石的平均品位均已知。按照炼铁生产的要求，在矿石采出后需按照照炼铁生产的要求，在矿石采出后需按照指定的品位值指定的品位值T进行不同品位矿

41、石的混合配进行不同品位矿石的混合配料。料。v按照该企业设备和工艺要求，混合后矿石按照该企业设备和工艺要求，混合后矿石的平均品位的平均品位T规定为规定为45。问如何配矿才能。问如何配矿才能获得最佳的效益？获得最佳的效益？本讲稿第四十四页，共八十页v变量：记变量：记xi,i=1,2,14 分别表示各出矿点分别表示各出矿点参与配矿的数量。参与配矿的数量。v约束条件包含如下三类：约束条件包含如下三类：v供给约束：供给约束：v品位约束：品位约束：v非负约束。非负约束。v目标函数取为配矿总量。目标函数取为配矿总量。本讲稿第四十五页，共八十页应用单纯形法求解得到最优解为应用单纯形法求解得到最优解为最优目标值

42、为最优目标值为最优目标值为最优目标值为 （万吨）（万吨）（万吨）（万吨）由于出矿点由于出矿点由于出矿点由于出矿点1 1平均品位仅平均品位仅平均品位仅平均品位仅37.1637.16，属于贫矿，有，属于贫矿，有，属于贫矿，有，属于贫矿，有38.87938.879（万（万吨）没有参与配矿。该方案未被公司接受，原因是公吨）没有参与配矿。该方案未被公司接受，原因是公司需要解决出矿点司需要解决出矿点1的矿产闲置及环保等问题。的矿产闲置及环保等问题。本讲稿第四十六页，共八十页如果将品位要求如果将品位要求如果将品位要求如果将品位要求T T T T降低为降低为降低为降低为43434343，则所有贫矿全部入选，剩

43、余的，则所有贫矿全部入选，剩余的，则所有贫矿全部入选，剩余的，则所有贫矿全部入选，剩余的矿产矿产矿产矿产5.375.375.375.37万吨全部为品位超过万吨全部为品位超过万吨全部为品位超过万吨全部为品位超过50505050的富矿，可用于生产高附加的富矿，可用于生产高附加的富矿，可用于生产高附加的富矿，可用于生产高附加值的产品。且工艺操作上只需稍加改进公司即可正常生产。此值的产品。且工艺操作上只需稍加改进公司即可正常生产。此值的产品。且工艺操作上只需稍加改进公司即可正常生产。此值的产品。且工艺操作上只需稍加改进公司即可正常生产。此时配矿总量可达到时配矿总量可达到时配矿总量可达到时配矿总量可达到

44、175175175175万吨，较万吨，较万吨，较万吨，较T T T T45454545增加增加增加增加931.86931.86931.86931.86万吨。因此万吨。因此万吨。因此万吨。因此公司选择将品位要求公司选择将品位要求公司选择将品位要求公司选择将品位要求T T T T降低为降低为降低为降低为43434343。此案例说明运筹学方法通常需与实际情况结合，才能发此案例说明运筹学方法通常需与实际情况结合，才能发此案例说明运筹学方法通常需与实际情况结合，才能发此案例说明运筹学方法通常需与实际情况结合，才能发挥其应有的作用。挥其应有的作用。挥其应有的作用。挥其应有的作用。本讲稿第四十七页，共八十页

45、vv1818、19世纪，世纪，世纪，世纪，Newton、Lagrange、Cauchy Cauchy 时代的时代的时代的时代的极值问题。极值问题。极值问题。极值问题。vv上世纪上世纪上世纪上世纪40504050年代以来，在处理线性优化方面，有年代以来，在处理线性优化方面，有年代以来，在处理线性优化方面，有年代以来，在处理线性优化方面，有DantzigDantzig（19471947）单纯形法；）单纯形法；）单纯形法；）单纯形法；Frank Frank 和和和和 WolfeWolfe（19561956）序列线性规划法；哈奇扬的椭球算法（序列线性规划法；哈奇扬的椭球算法（1979）以及）以及）以及

46、）以及KarmarkarKarmarkar提出的提出的KMKKMK算法（算法（算法（算法（19841984）等。）等。简单的历史回顾简单的历史回顾本讲稿第四十八页，共八十页简单的历史回顾简单的历史回顾60年代是优化发展最重要的时期：处理无约束优化方年代是优化发展最重要的时期：处理无约束优化方面有：面有：M.J.D.Powell M.J.D.Powell 提出的共轭方向法，提出的共轭方向法，提出的共轭方向法，提出的共轭方向法，W.C.Davidon W.C.Davidon 提出的变尺度法，提出的变尺度法，R.Fletcher R.Fletcher 和和Powell Powell 提出的改进变提出

47、的改进变尺度法等。尺度法等。6060年代以来理论方面最重要的贡献可谓年代以来理论方面最重要的贡献可谓 H.W.Kuhn H.W.Kuhn 和和和和A.W.Tucher A.W.Tucher 提出的提出的提出的提出的KT条件。在非线性约束优化方面包条件。在非线性约束优化方面包条件。在非线性约束优化方面包条件。在非线性约束优化方面包括括括括G.Zoutendijk G.Zoutendijk 的可行方向法的可行方向法的可行方向法的可行方向法 和和和和 J.B.Rosen J.B.Rosen 的投影梯度的投影梯度法等。法等。本讲稿第四十九页，共八十页vv9090年代以来一些新的求解非年代以来一些新的求

48、解非年代以来一些新的求解非年代以来一些新的求解非线性优化的方法线性优化的方法线性优化的方法线性优化的方法v（1 1）神经优化方法）神经优化方法）神经优化方法）神经优化方法vv（2 2）模拟退火算法）模拟退火算法）模拟退火算法）模拟退火算法v（3 3）遗传算法）遗传算法vv（4 4）微分方程逼近方法）微分方程逼近方法）微分方程逼近方法）微分方程逼近方法（Ordinary Differential Ordinary Differential EquationsEquations，ODE法）法）法）法）简单的历史回顾简单的历史回顾本讲稿第五十页，共八十页第二章第二章 凸分析凸分析本讲稿第五十一页，共

49、八十页一一一一,极大，极小和鞍点极大，极小和鞍点极大，极小和鞍点极大，极小和鞍点vv1 1，单变量情况，单变量情况，单变量情况，单变量情况设设设设x*x*是函数是函数是函数是函数 f f（x x）的一个局部极小点，则）的一个局部极小点，则）的一个局部极小点，则）的一个局部极小点，则称称称称 ff（x*x*）=0=0 为一阶必要条件。为一阶必要条件。为一阶必要条件。为一阶必要条件。vv2 2，多变量的情况，多变量的情况，多变量的情况，多变量的情况vv定义定义定义定义1 1 称称称称 f f（x*x*）为一阶梯度，）为一阶梯度，）为一阶梯度，）为一阶梯度，dfdf（x*x*）=为一为一为一为一阶微

50、分。阶微分。阶微分。阶微分。本讲稿第五十二页，共八十页定义定义定义定义2 2 沿方向沿方向沿方向沿方向h h的方向导数的方向导数的方向导数的方向导数或设或设或设或设 g g（t t）=f=f（x*+thx*+th）可得：）可得：）可得：）可得：定义定义定义定义3 3 二阶微分二阶微分二阶微分二阶微分本讲稿第五十三页，共八十页定义定义定义定义4 4 二阶方向导数二阶方向导数二阶方向导数二阶方向导数定理定理定理定理1 1（一阶必要条件）：设（一阶必要条件）：设（一阶必要条件）：设（一阶必要条件）：设x*x*是是是是 可微函数可微函数可微函数可微函数 f f（x x）在开集）在开集）在开集）在开集S