管理科学理论精选PPT.ppt

管理科学理论第1页，此课件共80页哦优化部分优化部分-主要内容主要内容第一章第一章 概述概述第二章第二章 凸分析凸分析1 1，极大、极小与鞍点，极大、极小与鞍点，极大、极小与鞍点，极大、极小与鞍点2，凸集与凸函数，凸集与凸函数3，凸集的分离和支撑，凸集的分离和支撑4 4，凸规划，凸规划，凸规划，凸规划第三章第三章 无约束优化的理论与方法无约束优化的理论与方法1 1，常见的一维搜索方法，常见的一维搜索方法，常见的一维搜索方法，常见的一维搜索方法（1）平分法（）平分法（2）0.618法法（3 3）FibonacciFibonacci法法法法第2页，此课件共80页哦2 2，多维搜索，多维搜索，多维搜索，多维搜索（1 1）梯度法（最速下降法）梯度法（最速下降法）梯度法（最速下降法）梯度法（最速下降法）（2 2）共轭方向法和共轭梯度法）共轭方向法和共轭梯度法）共轭方向法和共轭梯度法）共轭方向法和共轭梯度法（3 3）变尺度法（拟）变尺度法（拟）变尺度法（拟）变尺度法（拟NewtonNewton法）法）法）法）（4 4）直接法（）直接法（）直接法（）直接法（PowellPowell法和单纯形法）法和单纯形法）法和单纯形法）法和单纯形法）第四章第四章 约束非线性优化理论与方法约束非线性优化理论与方法1 1，等式约束问题，等式约束问题，等式约束问题，等式约束问题（1 1）切向量与正规性）切向量与正规性）切向量与正规性）切向量与正规性（2 2）最优性条件）最优性条件）最优性条件）最优性条件2 2，具不等式约束的问题，具不等式约束的问题，具不等式约束的问题，具不等式约束的问题（1 1）下降方向集和可行方向集）下降方向集和可行方向集）下降方向集和可行方向集）下降方向集和可行方向集（2 2）最优性条件和鞍点）最优性条件和鞍点）最优性条件和鞍点）最优性条件和鞍点（3 3）对偶问题）对偶问题）对偶问题）对偶问题第3页，此课件共80页哦3，常用的非线性约束优化的算法，常用的非线性约束优化的算法（1）序列线性规划法）序列线性规划法（2）序列无约束极小化方法）序列无约束极小化方法v 外罚函数法和内罚函数法外罚函数法和内罚函数法v 混合罚函数与精确罚函数法混合罚函数与精确罚函数法vv 乘子法乘子法乘子法乘子法（3）Zoutendij 可行方向法可行方向法（4）简约梯度法与广义简约梯度法）简约梯度法与广义简约梯度法第4页，此课件共80页哦（5 5）梯度投影法）梯度投影法）梯度投影法）梯度投影法第五章多目标优化第五章多目标优化第五章多目标优化第五章多目标优化 1 1，概述，概述，概述，概述2 2，偏好关系，偏好关系，偏好关系，偏好关系3 3，ParetoPareto有效解有效解有效解有效解4 4，常用算法介绍，常用算法介绍，常用算法介绍，常用算法介绍第六章第六章 网络优化网络优化1 1，最短路问题，最短路问题，最短路问题，最短路问题2 2，最大流问题，最大流问题，最大流问题，最大流问题3 3，最大流最大切断定理，最大流最大切断定理，最大流最大切断定理，最大流最大切断定理第5页，此课件共80页哦第七章第七章第七章第七章 动态规划动态规划动态规划动态规划1 1，基本概念，基本概念，基本概念，基本概念2 2，最优性原理，最优性原理，最优性原理，最优性原理3 3，动态规划的解法，动态规划的解法，动态规划的解法，动态规划的解法第八章第八章 不确定优化的理论与方法不确定优化的理论与方法1 1，期望值模型，期望值模型，期望值模型，期望值模型2 2，遗传算法，遗传算法，遗传算法，遗传算法3 3，机会约束规划（，机会约束规划（，机会约束规划（，机会约束规划（Chance Constrained ProgrammingChance Constrained Programming）4 4，相关机会规划（，相关机会规划（，相关机会规划（，相关机会规划（Dependent Chance ProgrammingDependent Chance Programming）5 5，模糊优化方法，模糊优化方法，模糊优化方法，模糊优化方法第6页，此课件共80页哦Markowitz 证券组合理论证券组合理论设设由由n n个个个个证证证证券券券券组组组组成成成成的的的的证证证证券券券券组组组组合合合合，当当当当每每每每个个个个证证证证券券券券的的的的预预预预期期期期回回回回报报报报和和和和协协协协方方方方差差差差已已已已知知知知时时时时，可可可可由由由由以以以以下下下下优优优优化化化化方方方方法法法法，求求求求证证证证券券券券组组组组合合合合的最优权重：的最优权重：的最优权重：的最优权重：(1)其其中中 ,R R为为为为事事事事先先先先给给给给定定定定的的的的证证证证券券券券组组组组合合合合预预预预期期期期收收收收益的下界。益的下界。益的下界。益的下界。第7页，此课件共80页哦Markowitz 证券组合理论证券组合理论或或 （2）以上均为二次优化问题。以上均为二次优化问题。第8页，此课件共80页哦一，优化问题的数学描述一，优化问题的数学描述一，优化问题的数学描述一，优化问题的数学描述vv例例例例1 1，选址问题，选址问题，选址问题，选址问题第一章第一章 概述概述第9页，此课件共80页哦设某砖厂生产彩色和无色两种地砖，每吨地砖设某砖厂生产彩色和无色两种地砖，每吨地砖设某砖厂生产彩色和无色两种地砖，每吨地砖设某砖厂生产彩色和无色两种地砖，每吨地砖 机时机时机时机时 工时工时工时工时 颜料（升）颜料（升）颜料（升）颜料（升）利润（元）利润（元）利润（元）利润（元）彩色彩色彩色彩色 2 3 2 3002 3 2 300无色无色无色无色 1 3 0 2001 3 0 200每天资源每天资源每天资源每天资源 10 24 8 10 24 8 最大？最大？最大？最大？问：每天应如何安排两种地砖的生产，使利润最大？问：每天应如何安排两种地砖的生产，使利润最大？问：每天应如何安排两种地砖的生产，使利润最大？问：每天应如何安排两种地砖的生产，使利润最大？例例2：生产安排问题生产安排问题第10页，此课件共80页哦某公司有资金某公司有资金某公司有资金某公司有资金A A万元，可供投资的项目有万元，可供投资的项目有万元，可供投资的项目有万元，可供投资的项目有N N 项，已知每一项目所需项，已知每一项目所需项，已知每一项目所需项，已知每一项目所需资金资金资金资金 a ai i 和预期利润和预期利润和预期利润和预期利润 c ci i，问如何安排资金？，问如何安排资金？，问如何安排资金？，问如何安排资金？解：令解：令解：令解：令 投资项目投资项目投资项目投资项目i i 不投项目不投项目不投项目不投项目i i 问题问题问题问题 集装箱容积为集装箱容积为集装箱容积为集装箱容积为A A，可选择，可选择，可选择，可选择N N 件物品装入。已知每件物品所占件物品装入。已知每件物品所占件物品装入。已知每件物品所占件物品装入。已知每件物品所占容积和重量，问如何装箱使总重量最大？容积和重量，问如何装箱使总重量最大？容积和重量，问如何装箱使总重量最大？容积和重量，问如何装箱使总重量最大？例例3（投资问题（投资问题1）第11页，此课件共80页哦某公司有资金某公司有资金某公司有资金某公司有资金A A万元，有万元，有万元，有万元，有2 2个项目可选择投资。已知项目个项目可选择投资。已知项目个项目可选择投资。已知项目个项目可选择投资。已知项目1 1和和和和2 2的年预期收益率分别为的年预期收益率分别为的年预期收益率分别为的年预期收益率分别为20%20%和和和和16%16%，且总风险函数已获得。，且总风险函数已获得。，且总风险函数已获得。，且总风险函数已获得。问如何安排投资，使收益尽可能大，风险尽可能小？问如何安排投资，使收益尽可能大，风险尽可能小？问如何安排投资，使收益尽可能大，风险尽可能小？问如何安排投资，使收益尽可能大，风险尽可能小？解：设解：设解：设解：设 x x i i 项目项目项目项目I I 的投资额，且已知总风险函数为：的投资额，且已知总风险函数为：的投资额，且已知总风险函数为：的投资额，且已知总风险函数为：在可承受风险下，求收益最大：在可承受风险下，求收益最大：在可承受风险下，求收益最大：在可承受风险下，求收益最大：例例4（投资问题（投资问题2）第12页，此课件共80页哦在收益保证的条件下，求风险最小问题在收益保证的条件下，求风险最小问题在收益保证的条件下，求风险最小问题在收益保证的条件下，求风险最小问题双目标模型：双目标模型：双目标模型：双目标模型：第13页，此课件共80页哦最优化技术与方法周宗放最优化技术与方法周宗放【例例】令令令令则有则有第14页，此课件共80页哦设某传输网络由设某传输网络由设某传输网络由设某传输网络由n n 个电站，向个电站，向个电站，向个电站，向 m m 个负载输送电能。要求确定一个个负载输送电能。要求确定一个个负载输送电能。要求确定一个个负载输送电能。要求确定一个最经济的传输方案，既要满足用户的要求，又使各电站生产所最经济的传输方案，既要满足用户的要求，又使各电站生产所最经济的传输方案，既要满足用户的要求，又使各电站生产所最经济的传输方案，既要满足用户的要求，又使各电站生产所需成本最低？需成本最低？需成本最低？需成本最低？解：解：解：解：Lagrange Lagrange 函数函数函数函数例例5 能量传输优化问题能量传输优化问题第15页，此课件共80页哦得到：得到：得到：得到：最优能量传输规律：最优能量传输规律：最优能量传输规律：最优能量传输规律：生产电能的边际成本与各电站相对于总耗生产电能的边际成本与各电站相对于总耗生产电能的边际成本与各电站相对于总耗生产电能的边际成本与各电站相对于总耗损的边际贡献成正比，比例系数恰为损的边际贡献成正比，比例系数恰为损的边际贡献成正比，比例系数恰为损的边际贡献成正比，比例系数恰为 .第16页，此课件共80页哦设国际市场对我国某出口商品每年需求为设国际市场对我国某出口商品每年需求为设国际市场对我国某出口商品每年需求为设国际市场对我国某出口商品每年需求为 x x 吨，服从均匀分布：吨，服从均匀分布：吨，服从均匀分布：吨，服从均匀分布：U U（20002000，40004000）。每售出）。每售出）。每售出）。每售出1 1吨赚外汇吨赚外汇吨赚外汇吨赚外汇3 3万元，保养费万元，保养费万元，保养费万元，保养费1 1万元万元万元万元 /吨。问吨。问吨。问吨。问应如何组织出口？应如何组织出口？应如何组织出口？应如何组织出口？解：设解：设解：设解：设y y为年出口量。为年出口量。为年出口量。为年出口量。需求大于出口需求大于出口需求大于出口需求大于出口 收益收益收益收益 需求小于出口需求小于出口需求小于出口需求小于出口例例6 随机优化问题随机优化问题第17页，此课件共80页哦求均值：求均值：求均值：求均值：建立优化模型：建立优化模型：建立优化模型：建立优化模型：求解：求解：求解：求解：y=y=35003500（吨）。（吨）。（吨）。（吨）。第18页，此课件共80页哦某工厂在周期性生产过程中，每一周期的产量不能超过某工厂在周期性生产过程中，每一周期的产量不能超过某工厂在周期性生产过程中，每一周期的产量不能超过某工厂在周期性生产过程中，每一周期的产量不能超过X X件，库存不能超过件，库存不能超过Y Y件，初始库存为件，初始库存为件，初始库存为件，初始库存为0 0。现设在第。现设在第i i个周个周期中，生产期中，生产x xi i 件产品的成本为件产品的成本为件产品的成本为件产品的成本为f fi i(x xi i)，库存库存库存库存y yi i件产品的成件产品的成件产品的成件产品的成本为本为本为本为 g gi i(y yi i)，问如何组织生产，使，问如何组织生产，使，问如何组织生产，使，问如何组织生产，使n n个周期的总成本最小。个周期的总成本最小。个周期的总成本最小。个周期的总成本最小。解解解解：例例7 生产组织问题生产组织问题第19页，此课件共80页哦特别若仅考虑一个周期（特别若仅考虑一个周期（特别若仅考虑一个周期（特别若仅考虑一个周期（n n1 1）：）：）：）：再不妨设再不妨设再不妨设再不妨设 f f(x x)=x=x2,g,g(y y)=y=y2 2，得：，得：，得：，得：得最优解：得最优解：得最优解：得最优解：第20页，此课件共80页哦v古代军事运筹学思想古代军事运筹学思想vv中国古代中国古代中国古代中国古代“孙子兵法孙子兵法孙子兵法孙子兵法”渗透着量的渗透着量的渗透着量的渗透着量的分析（分析（分析（分析（1981年美国军事运筹学会出年美国军事运筹学会出年美国军事运筹学会出年美国军事运筹学会出版书中第一句话称孙武是世界上第版书中第一句话称孙武是世界上第版书中第一句话称孙武是世界上第版书中第一句话称孙武是世界上第一个军事运筹学的实践家）。一个军事运筹学的实践家）。一个军事运筹学的实践家）。一个军事运筹学的实践家）。军事运筹优化重要来源军事运筹优化重要来源第21页，此课件共80页哦运筹与优化第二来源：管理运筹与优化第二来源：管理v管理科学，按照国际管理科学会的说法，是把各种科学管理科学，按照国际管理科学会的说法，是把各种科学方法用于管理。企业的管理经历三个时期：方法用于管理。企业的管理经历三个时期：1，手工式，手工式管理；管理；2，机械化管理；，机械化管理；3，系统化管理。，系统化管理。v小农经济或小手工业经济的管理是由家长、业主兼雇。小农经济或小手工业经济的管理是由家长、业主兼雇。这种管理方式完全凭记忆、思考，或极其简单的工具这种管理方式完全凭记忆、思考，或极其简单的工具计算。计算。vv大规模的机械化生产，使企业管理进入机械化时期。管大规模的机械化生产，使企业管理进入机械化时期。管大规模的机械化生产，使企业管理进入机械化时期。管大规模的机械化生产，使企业管理进入机械化时期。管理职能分化为相对独立的部分。与此相适应，簿记、报理职能分化为相对独立的部分。与此相适应，簿记、报理职能分化为相对独立的部分。与此相适应，簿记、报理职能分化为相对独立的部分。与此相适应，簿记、报告和机械式计算是管理人员掌握的工具。告和机械式计算是管理人员掌握的工具。告和机械式计算是管理人员掌握的工具。告和机械式计算是管理人员掌握的工具。第22页，此课件共80页哦运筹与优化第三来源：经济运筹与优化第三来源：经济v数理经济学对运筹学，特别是运筹学中线性数理经济学对运筹学，特别是运筹学中线性规划产生重要的影响，许多经济学家对数理规划产生重要的影响，许多经济学家对数理经济有着显著贡献，最有名的是沃尔拉思经济有着显著贡献，最有名的是沃尔拉思(walras)，他当时研究经济平衡问题，其数学，他当时研究经济平衡问题，其数学形式为后来的数理经济学家一再研究和发展。形式为后来的数理经济学家一再研究和发展。20世纪世纪30年代奥地利和德国的经济学家推年代奥地利和德国的经济学家推广了沃尔拉思的工作。广了沃尔拉思的工作。第23页，此课件共80页哦数理经济学数理经济学vVon Neumann 与对策论与对策论v1932年，年，Von Neumann提出广义经济平衡模提出广义经济平衡模型；型；1939年，又提出宏观经济优化控制模型；年，又提出宏观经济优化控制模型；1944年，与年，与Morgenstern共著的共著的对策论与对策论与经济行为经济行为开创了对策论分支。开创了对策论分支。v康托洛维奇与康托洛维奇与“生产组织与计划中的数学方生产组织与计划中的数学方法法”v30年代，苏联数理经济学家康托洛维奇从事年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得生产组织与管理中的定量化方法研究，取得了很多重要成果。了很多重要成果。1939年，出版年，出版生产组织生产组织与计划中的数学方法与计划中的数学方法，其思想和模型被归，其思想和模型被归入线性规划范畴。入线性规划范畴。第24页，此课件共80页哦马克思也是成功地把数学用于经济研究的经马克思也是成功地把数学用于经济研究的经济学家；在济学家；在资本论资本论中，处处渗透看定量中，处处渗透看定量化的分析。化的分析。1863年致恩格斯的信中，马克思说他本人正年致恩格斯的信中，马克思说他本人正在研究微积分，并向恩格斯推荐。正如恩格在研究微积分，并向恩格斯推荐。正如恩格斯所说：马克思是当时唯斯所说：马克思是当时唯能用哲学作为能用哲学作为指导来研究数学的人。指导来研究数学的人。第25页，此课件共80页哦优化的性质和特点优化的性质和特点优化方法应用现有的科学技术知识和数学方法，解决优化方法应用现有的科学技术知识和数学方法，解决优化方法应用现有的科学技术知识和数学方法，解决优化方法应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定实际中提出的专门问题，为决策者选择最优决策提供定实际中提出的专门问题，为决策者选择最优决策提供定实际中提出的专门问题，为决策者选择最优决策提供定量依据。量依据。量依据。量依据。优化的特点优化的特点优化的特点优化的特点定量化分析。定量化分析。多学科交叉，如综合利用了管理学、经济学、数多学科交叉，如综合利用了管理学、经济学、数量科学等理论与方法。量科学等理论与方法。最优决策。最优决策。第26页，此课件共80页哦优化的主要研究对象优化的主要研究对象设备、人员、资金等如何最佳利用和配置问题、生设备、人员、资金等如何最佳利用和配置问题、生产组织问题、选址问题、运输问题以及投资与决策产组织问题、选址问题、运输问题以及投资与决策问题等等。问题等等。常用方法包括：线性和非线性规划、整数规划、网常用方法包括：线性和非线性规划、整数规划、网络优化、动态规划和多目标规划等。络优化、动态规划和多目标规划等。第27页，此课件共80页哦线性规划问题线性规划问题v例例1中华家电公司推销一种新型洗衣机，有关数据见下中华家电公司推销一种新型洗衣机，有关数据见下中华家电公司推销一种新型洗衣机，有关数据见下中华家电公司推销一种新型洗衣机，有关数据见下表。销售部第一月的广告预算为表。销售部第一月的广告预算为表。销售部第一月的广告预算为表。销售部第一月的广告预算为2 2万元，要求至少有万元，要求至少有万元，要求至少有万元，要求至少有8 8次次次次电视商业节目，电视商业节目，电视商业节目，电视商业节目，1515家报纸广告，电视广告费不得超过家报纸广告，电视广告费不得超过家报纸广告，电视广告费不得超过家报纸广告，电视广告费不得超过1.21.2万元，电台广播至少隔日有一次。问该公司销售部应当采万元，电台广播至少隔日有一次。问该公司销售部应当采万元，电台广播至少隔日有一次。问该公司销售部应当采万元，电台广播至少隔日有一次。问该公司销售部应当采用怎样的广告宣传计划，才能取得最好的效果用怎样的广告宣传计划，才能取得最好的效果用怎样的广告宣传计划，才能取得最好的效果用怎样的广告宣传计划，才能取得最好的效果?第28页，此课件共80页哦广告方式广告费用(元/次)可用最高次数/月期望的宣传效果（得分）/次电视台a(白天1 分钟)5001650电视台b(晚上30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)802515第29页，此课件共80页哦第30页，此课件共80页哦第31页，此课件共80页哦第32页，此课件共80页哦对偶问题对偶问题v例例 某工厂准备生产某工厂准备生产MM1 1，MM2 2，MM3 3三种产品，生产这三种产品，生产这些产品需要些产品需要N N1，N N2 2，N N3 3三种原料。各单位产品需要消耗三种原料。各单位产品需要消耗三种原料。各单位产品需要消耗三种原料。各单位产品需要消耗的原料如下表所示：的原料如下表所示：的原料如下表所示：的原料如下表所示：原料消耗M1M2M3N1N2N3642831.511.50.5第33页，此课件共80页哦产产品品M1 1，M2，MM3 3的的的的单单单单位位位位售售售售价价价价分分分分别别别别为为为为6060、3030和和和和2020元元元元，且且且且都都都都能能能能售售售售出出出出。现现现现有有有有原原原原料料料料N1，N N2 2，N N3 3分分别别48、20和和8个个单单位位，问问如如何安排生产才能使销售收入最大？何安排生产才能使销售收入最大？解解解解 设设设设x1 1，x x2 2，x x3 3分分分分别别别别为为为为产产产产品品品品M1 1，MM2，MM3 3的的的的生生生生产产产产数数数数量量量量。问问问问题题题题化为如下线性规划问题：化为如下线性规划问题：化为如下线性规划问题：化为如下线性规划问题：第34页，此课件共80页哦现从另一角度讨论问题：某公司打算买入该厂原料自行生产，现从另一角度讨论问题：某公司打算买入该厂原料自行生产，现从另一角度讨论问题：某公司打算买入该厂原料自行生产，现从另一角度讨论问题：某公司打算买入该厂原料自行生产，公司需要确定这些原料的购买价格。设公司需要确定这些原料的购买价格。设公司需要确定这些原料的购买价格。设公司需要确定这些原料的购买价格。设y1 1，y2 2，y3 3分别为原分别为原分别为原分别为原料料料料N1 1，N N2，N N3的购买价格，买进这些产品的总费用为：的购买价格，买进这些产品的总费用为：的购买价格，买进这些产品的总费用为：的购买价格，买进这些产品的总费用为：48 48 y y1 12020y2 28 8y y3 3。公司希望购买价格越低越好，但价格太。公司希望购买价格越低越好，但价格太。公司希望购买价格越低越好，但价格太。公司希望购买价格越低越好，但价格太低工厂不愿出售，于是该购买价格应受到约束。低工厂不愿出售，于是该购买价格应受到约束。低工厂不愿出售，于是该购买价格应受到约束。低工厂不愿出售，于是该购买价格应受到约束。由于工厂使用一组原料（由于工厂使用一组原料（由于工厂使用一组原料（由于工厂使用一组原料（8 8单位单位N N1，4 4单位单位单位单位N N2，2单位单位单位单位N N3 3）即可生产出一个产品即可生产出一个产品即可生产出一个产品即可生产出一个产品MM1 1，售价，售价，售价，售价60元，因此公司至少需付出元，因此公司至少需付出元，因此公司至少需付出元，因此公司至少需付出6060元才能买走这组原料，即元才能买走这组原料，即元才能买走这组原料，即元才能买走这组原料，即 8 8 y y1 14 4y2 22 2y3 3 6060第35页，此课件共80页哦类似地对产品类似地对产品类似地对产品类似地对产品M2和和和和M3 3，应满足：，应满足：6 6y y1 12 2y y2 21,51,5y3 3 30 30 和和和和 y11.1.5y20.50.5y3 3 2020对公司而言，问题化为如下线性规划问题：对公司而言，问题化为如下线性规划问题：对公司而言，问题化为如下线性规划问题：对公司而言，问题化为如下线性规划问题：第36页，此课件共80页哦显然，当显然，当min min W W=max=max z 时，双方都能够得到最优结果。时，双方都能够得到最优结果。时，双方都能够得到最优结果。时，双方都能够得到最优结果。两个模型的数据来源相同，表达形式不同，经济活动意两个模型的数据来源相同，表达形式不同，经济活动意两个模型的数据来源相同，表达形式不同，经济活动意两个模型的数据来源相同，表达形式不同，经济活动意义也不同，称其为互为对偶的线性规划问题。义也不同，称其为互为对偶的线性规划问题。义也不同，称其为互为对偶的线性规划问题。义也不同，称其为互为对偶的线性规划问题。对偶定理对偶定理对偶定理对偶定理 若原问题或对偶问题中一个有解，则另一个也若原问题或对偶问题中一个有解，则另一个也若原问题或对偶问题中一个有解，则另一个也若原问题或对偶问题中一个有解，则另一个也有解，且它们的最优目标值相同。有解，且它们的最优目标值相同。有解，且它们的最优目标值相同。有解，且它们的最优目标值相同。一般地有：一般地有：一般地有：一般地有：第37页，此课件共80页哦对偶问题对偶问题v原问题原问题v如如v对偶问题对偶问题第38页，此课件共80页哦对偶变量的经济解释对偶变量的经济解释v对偶变量对偶变量 yi 在经济意义上表示原问题第在经济意义上表示原问题第 i 种资种资源的边际贡献，即当第源的边际贡献，即当第 i 种资源增加一个单位种资源增加一个单位时，相应目标值时，相应目标值W的增量。对偶问题的最优解的增量。对偶问题的最优解 yi*称原问题第称原问题第 i 种资源的影子价格。种资源的影子价格。v1，出租资源或设备，租金价格设定；，出租资源或设备，租金价格设定；v2，企业内资源，企业内资源 i 存量设定；存量设定；v3，调整资源分配量以增加利润。，调整资源分配量以增加利润。第39页，此课件共80页哦运输问题运输问题 收点发点B1B2Bn发量A1C11 x 11C12x12 C1nx1na1AmCm1xm1Cm2xm2Cmn xmnam收量b1b2bn其中：其中：其中：其中：x xij ij为第为第为第为第i i个发点个发点个发点个发点A Ai i到第到第到第到第j j个收点个收点个收点个收点B Bi i的运量；的运量；的运量；的运量；C Cij ij为第为第为第为第i i个发点到第个发点到第个发点到第个发点到第j j个收点的单位运费。个收点的单位运费。个收点的单位运费。个收点的单位运费。第40页，此课件共80页哦 运输问题模型运输问题模型vMin z=vS.t.第41页，此课件共80页哦指派问题指派问题vv设有设有设有设有n n 个人个人个人个人A A1 1，A2 2，A An n被分派做被分派做被分派做被分派做n 件事件事件事件事B B1 1,B B2 2，B Bn n，要求每件事必须有一人做，且不同事由不同人做。，要求每件事必须有一人做，且不同事由不同人做。已知每人已知每人A Ai i 做每件事做每件事做每件事做每件事B Bj j 的效率的效率的效率的效率(如劳动工时或成本，或创如劳动工时或成本，或创如劳动工时或成本，或创如劳动工时或成本，或创造的价值等造的价值等造的价值等造的价值等)为为为为C Cij，问应如何指派，才能使工作效益最高，问应如何指派，才能使工作效益最高，问应如何指派，才能使工作效益最高，问应如何指派，才能使工作效益最高?v指派问题既是运输问题的特殊情形，也是整数规划的指派问题既是运输问题的特殊情形，也是整数规划的特殊情形。特殊情形。第42页，此课件共80页哦指派问题的数学模型指派问题的数学模型vvMax Max z z=S.t.S.t.设当第设当第设当第设当第i i个人个人个人个人A Ai i 做第做第做第做第j j个件事个件事个件事个件事B Bi i 时，变量时，变量时，变量时，变量x xij ij 取取取取1 1，否则取零；，否则取零；，否则取零；，否则取零；C Cij ij 为第为第为第为第i i 个人做第个人做第个人做第个人做第j j 件事的效件事的效件事的效件事的效率。率。率。率。第43页，此课件共80页哦配矿计划的优化问题配矿计划的优化问题v某大型冶金矿业公司有某大型冶金矿业公司有14个出矿点，年产个出矿点，年产量及各出矿点矿石的平均品位均已知。按量及各出矿点矿石的平均品位均已知。按照炼铁生产的要求，在矿石采出后需按照照炼铁生产的要求，在矿石采出后需按照指定的品位值指定的品位值T进行不同品位矿石的混合配进行不同品位矿石的混合配料。料。v按照该企业设备和工艺要求，混合后矿石按照该企业设备和工艺要求，混合后矿石的平均品位的平均品位T规定为规定为45。问如何配矿才能。问如何配矿才能获得最佳的效益？获得最佳的效益？第44页，此课件共80页哦v变量：记变量：记xi,i=1,2,14 分别表示各出矿点分别表示各出矿点参与配矿的数量。参与配矿的数量。v约束条件包含如下三类：约束条件包含如下三类：v供给约束：供给约束：v品位约束：品位约束：v非负约束。非负约束。v目标函数取为配矿总量。目标函数取为配矿总量。第45页，此课件共80页哦应用单纯形法求解得到最优解为应用单纯形法求解得到最优解为最优目标值为最优目标值为 （万吨）（万吨）由于出矿点由于出矿点由于出矿点由于出矿点1 1平均品位仅平均品位仅平均品位仅平均品位仅37.1637.16，属于贫矿，有，属于贫矿，有，属于贫矿，有，属于贫矿，有38.879（万吨）没有参与配矿。该方案未被公司接受，原因（万吨）没有参与配矿。该方案未被公司接受，原因（万吨）没有参与配矿。该方案未被公司接受，原因（万吨）没有参与配矿。该方案未被公司接受，原因是公司需要解决出矿点是公司需要解决出矿点是公司需要解决出矿点是公司需要解决出矿点1的矿产闲置及环保等问题。的矿产闲置及环保等问题。的矿产闲置及环保等问题。的矿产闲置及环保等问题。第46页，此课件共80页哦如果将品位要求如果将品位要求如果将品位要求如果将品位要求T T T T降低为降低为降低为降低为43434343，则所有贫矿全部入选，剩余，则所有贫矿全部入选，剩余，则所有贫矿全部入选，剩余，则所有贫矿全部入选，剩余的矿产的矿产的矿产的矿产5.375.375.375.37万吨全部为品位超过万吨全部为品位超过万吨全部为品位超过万吨全部为品位超过50505050的富矿，可用于生产的富矿，可用于生产的富矿，可用于生产的富矿，可用于生产高附加值的产品。且工艺操作上只需稍加改进公司即可高附加值的产品。且工艺操作上只需稍加改进公司即可高附加值的产品。且工艺操作上只需稍加改进公司即可高附加值的产品。且工艺操作上只需稍加改进公司即可正常生产。此时配矿总量可达到正常生产。此时配矿总量可达到正常生产。此时配矿总量可达到正常生产。此时配矿总量可达到175175175175万吨，较万吨，较万吨，较万吨，较T T T T45454545增加增加增加增加931.86931.86931.86931.86万吨。因此公司选择将品位要求万吨。因此公司选择将品位要求万吨。因此公司选择将品位要求万吨。因此公司选择将品位要求T T T T降低为降低为降低为降低为43434343。此案例说明运筹学方法通常需与实际情况结合，才能发挥此案例说明运筹学方法通常需与实际情况结合，才能发挥此案例说明运筹学方法通常需与实际情况结合，才能发挥此案例说明运筹学方法通常需与实际情况结合，才能发挥其应有的作用。其应有的作用。其应有的作用。其应有的作用。第47页，此课件共80页哦v18、1919世纪，世纪，世纪，世纪，NewtonNewton、Lagrange、Cauchy 时代的时代的时代的时代的极值问题。极值问题。极值问题。极值问题。vv上世纪上世纪上世纪上世纪40504050年代以来，在处理线性优化方面，有年代以来，在处理线性优化方面，有年代以来，在处理线性优化方面，有年代以来，在处理线性优化方面，有DantzigDantzig（19471947）单纯形法；）单纯形法；Frank 和和和和 Wolfe（19561956）序列线性规划法；哈奇扬的椭球算法（）序列线性规划法；哈奇扬的椭球算法（19791979）以）以）以）以及及及及Karmarkar提出的提出的提出的提出的KMK算法（算法（算法（算法（19841984）等。）等。简单的历史回顾简单的历史回顾第48页，此课件共80页哦简单的历史回顾简单的历史回顾6060年代是优化发展最重要的时期：处理无约束优化方面有：年代是优化发展最重要的时期：处理无约束优化方面有：年代是优化发展最重要的时期：处理无约束优化方面有：年代是优化发展最重要的时期：处理无约束优化方面有：M.J.D.Powell 提出的共轭方向法，提出的共轭方向法，提出的共轭方向法，提出的共轭方向法，W.C.Davidon W.C.Davidon 提出的提出的提出的提出的变尺度法，变尺度法，变尺度法，变尺度法，R.Fletcher R.Fletcher 和和Powell 提出的改进变尺度法等。提出的改进变尺度法等。提出的改进变尺度法等。提出的改进变尺度法等。6060年代以来理论方面最重要的贡献可谓年代以来理论方面最重要的贡献可谓 H.W.Kuhn H.W.Kuhn 和和A.W.Tucher A.W.Tucher 提出的提出的KTKT条件。在非线性约束优化方面条件。在非线性约束优化方面条件。在非线性约束优化方面条件。在非线性约束优化方面包括包括包括包括G.Zoutendijk G.Zoutendijk 的可行方向法的可行方向法的可行方向法的可行方向法 和和和和 J.B.Rosen J.B.Rosen 的投影梯度的投影梯度的投影梯度的投影梯度法等。法等。法等。法等。第49页，此课件共80页哦v90年代以来一些新的求解非年代以来一些新的求解非年代以来一些新的求解非年代以来一些新的求解非线性优化的方法线性优化的方法线性优化的方法线性优化的方法v（1 1）神经优化方法）神经优化方法）神经优化方法）神经优化方法vv（2）模拟退火算法）模拟退火算法vv（3 3）遗传算法）遗传算法）遗传算法）遗传算法v（4）微分方程逼近方法）微分方程逼近方法）微分方程逼近方法）微分方程逼近方法（Ordinary Differential Ordinary Differential EquationsEquations，ODEODE法）法）简单的历史回顾简单的历史回顾第50页，此课件共80页哦第二章第二章 凸分析凸分析第51页，此课件共80页哦一一一一,极大，极小和鞍点极大，极小和鞍点极大，极小和鞍点极大，极小和鞍点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*）=为为为为一阶微分。一阶微分。一阶微分。一阶微分。第52页，此课件共80页哦定义定义定义定义2 2 沿方向沿方向沿方向沿方向h h的方向导数的方向导数的方向导数的方向导数或设或设或设或设 g g（t t）=f=f（x*+thx*+th）可得：）可得：）可得：）可得：定义定义定义定义3 3 二阶微分二阶微分二阶微分二阶微分第53页，此课件共80页哦定义定义定义定义4 4 二阶方向导数二阶方向导数二阶方向导数二阶方向导数定理定理定理定理1 1（一阶必要条件）：设（一阶必要条件）：设（一阶必要条件）：设（一阶必要条件）：设x*x*是是是是 可微函数可微函数可微函数可微函数 f f（x x）在开集）在开集）在开集）在开集S S上的局上的局上的局上的局部极值点，则部极值点，则部极值点，则部极值点，则 对任意方向对任意方向对任意方向对任意方向h h均成立。均成立。均成立。均成立。定理定理定理定理2 2（二阶充分条件）设（二阶充分条件）设（二阶充分条件）设（二阶充分条件）设 f f（x x）二阶可微，若在）二阶可微，若在）二阶可微，若在）二阶可微，若在x*x*处一阶必要处一阶必要处一阶必要处一阶必要条件成立，且二阶方向导数为正（负），则条件成立，且二阶方向导数为正（负），则条件成立，且二阶方向导数为正（负），则条件成立，且二阶方向导数为正（负），则x*x*必是必是必是必是 f f（x x）的一个）的一个）的一个）的一个局部极小（大）点。局部极小（大）点。局部极小（大）点。局部极小（大）点。第54页，此课件共80页哦3，鞍点，鞍点定义定义5 如果存在如果存在 0,使下式成立使下式成立 则称（则称（x0,y0）为函数）为函数 f(x,y)的鞍点。的鞍点。在欧式空间中，称在欧式空间中