运筹学绪论ppt课件.ppt

《运筹学绪论ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学绪论ppt课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。系统工程A严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第一讲第一讲 绪绪 论论一、运筹学的形成与发展一、运筹学的形成与发展二、运筹学模型及分析步骤二、运筹学模型及分析步骤三、运筹学的定义及学科体系三、运筹学的定义及学科体系学习目的学习目的学习目的学习目的 学习本章要了解运筹学的形成和发展历史、典型案例，学习本章要了解运筹学的形成和发展历史、典型案例，学习本章要了解运筹学的形成和发展历史、典型案例，学习本章要了解运筹学

2、的形成和发展历史、典型案例，以及运筹学研究的主要内容等。以及运筹学研究的主要内容等。以及运筹学研究的主要内容等。以及运筹学研究的主要内容等。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第一节第一节第一节第一节 运筹学的形成和发展运筹学的形成和发展运筹学的形成和发展运筹学的形成和发展pp运运运运筹筹筹筹学学学学（Operations Operations Operations Operations ResearchResearchResearchResearch）是是是是系系系系统统统统工工工工程程程程的的的的最最最最重重重重要

3、要要要的的的的理理理理论论论论基基基基础础础础之之之之一一一一，在在在在美美美美国国国国有有有有人人人人把把把把运运运运筹筹筹筹学学学学称称称称之之之之为为为为管管管管理理理理科科科科学学学学(Management Science)(Management Science)(Management Science)(Management Science)。pp运运运运筹筹筹筹学学学学所所所所研研研研究究究究的的的的问问问问题题题题，可可可可简简简简单单单单地地地地归归归归结结结结为为为为一一一一句句句句话话话话：“依依依依照照照照给给给给定定定定条条条条件件件件和和和和目目目目标标标标，从从从从众

4、众众众多多多多方方方方案案案案中中中中选选选选择择择择最最最最佳佳佳佳方方方方案案案案”，故故故故有有有有人称之为人称之为人称之为人称之为最优化技术最优化技术最优化技术最优化技术。pp1938193819381938年年年年 英英英英 国国国国 最最最最 早早早早 出出出出 现现现现 了了了了 军军军军 事事事事 运运运运 筹筹筹筹 学学学学，命命命命 名名名名 为为为为“Operational Operational Operational Operational ResearchResearchResearchResearch”,1942”,1942”,1942”,1942年年年年，美美美

5、美国国国国从从从从事事事事这这这这方方方方面面面面工工工工作作作作的的的的科科科科学学学学家家家家命命命命其其其其名名名名为为为为“Operations Operations Operations Operations ResearchResearchResearchResearch”，这这这这个个个个名名名名字一直延用至今。字一直延用至今。字一直延用至今。字一直延用至今。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一、中国古代的运筹学思想一、中国古代的运筹学思想一、中国古代的运筹学思想一、中国古代的运筹学思想 中国中国史记史

6、记中的中的“运筹帷幄之中，决胜千运筹帷幄之中，决胜千里之外里之外”表达了中国古代运筹学思想，在古代中表达了中国古代运筹学思想，在古代中国有许多运筹学思想的应用案例，如国有许多运筹学思想的应用案例，如丁谓修宫、丁谓修宫、田忌赛马田忌赛马等，都蕴藏着神奇的运筹学思想，这些等，都蕴藏着神奇的运筹学思想，这些案例至今仍有很高的参考和借鉴价值。案例至今仍有很高的参考和借鉴价值。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。1 1丁谓修宫丁谓修宫 宋朝宋朝梦溪笔谈梦溪笔谈中记载了这样一个故事：北宋真宗中记载了这样一个故事：北宋真宗年间，皇宫

7、失火，皇帝召各大臣商议如何在很短的时间年间，皇宫失火，皇帝召各大臣商议如何在很短的时间内修复好皇宫，而修复皇宫包括内修复好皇宫，而修复皇宫包括取土烧砖，运输建筑材取土烧砖，运输建筑材料，清理废墟料，清理废墟三大工程，但在当时的条件下，这是相当三大工程，但在当时的条件下，这是相当繁重的工程，大家都无以言答。当时有个叫丁谓的大臣，繁重的工程，大家都无以言答。当时有个叫丁谓的大臣，他提出了一个一举三得的方案他提出了一个一举三得的方案丁谓修宫工程问题示意图丁谓修宫工程问题示意图丁谓修宫工程问题示意图丁谓修宫工程问题示意图取土问题取土问题 木材和石料运输问题木材和石料运输问题建筑垃圾处理问题建筑垃圾处理

8、问题挖沟挖沟引水入沟引水入沟填沟填沟严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2 2田忌赛马田忌赛马 战国时期齐王和田忌赛马战国时期齐王和田忌赛马战国时期齐王和田忌赛马战国时期齐王和田忌赛马,各从自己上等马各从自己上等马各从自己上等马各从自己上等马 、中等、中等、中等、中等马马马马 、下等马中选送一匹进行比赛，每输一局，输银千两，、下等马中选送一匹进行比赛，每输一局，输银千两，、下等马中选送一匹进行比赛，每输一局，输银千两，、下等马中选送一匹进行比赛，每输一局，输银千两，齐王的马都比田忌的好，但田忌的下等马与齐王的上等齐王的

9、马都比田忌的好，但田忌的下等马与齐王的上等齐王的马都比田忌的好，但田忌的下等马与齐王的上等齐王的马都比田忌的好，但田忌的下等马与齐王的上等马赛，用上等马对中等马，用中等马对下等马，这样田马赛，用上等马对中等马，用中等马对下等马，这样田马赛，用上等马对中等马，用中等马对下等马，这样田马赛，用上等马对中等马，用中等马对下等马，这样田忌非但没有输，反而嬴了一千两银子，这便是系统中从忌非但没有输，反而嬴了一千两银子，这便是系统中从忌非但没有输，反而嬴了一千两银子，这便是系统中从忌非但没有输，反而嬴了一千两银子，这便是系统中从整体出发，选最优方案，到最后实施的对策策略。整体出发，选最优方案，到最后实施的

10、对策策略。整体出发，选最优方案，到最后实施的对策策略。整体出发，选最优方案，到最后实施的对策策略。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。二、运筹学学科的形成二、运筹学学科的形成二、运筹学学科的形成二、运筹学学科的形成 现在普遍认为，运筹学的研究是从现在普遍认为，运筹学的研究是从现在普遍认为，运筹学的研究是从现在普遍认为，运筹学的研究是从第二次世界大战第二次世界大战第二次世界大战第二次世界大战初期的军事任务开始的，以英国为代表的科学家做了奠基初期的军事任务开始的，以英国为代表的科学家做了奠基初期的军事任务开始的，以英国为代

11、表的科学家做了奠基初期的军事任务开始的，以英国为代表的科学家做了奠基性的工作。性的工作。性的工作。性的工作。当时迫切需要把各项稀少的资源以有效的方式当时迫切需要把各项稀少的资源以有效的方式当时迫切需要把各项稀少的资源以有效的方式当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动，分配给各种不同的军事经营及在每一经营内的各项活动，分配给各种不同的军事经营及在每一经营内的各项活动，分配给各种不同的军事经营及在每一经营内的各项活动，所以美国及随后美国的军事管理当局都号召大批科学家运所以美国及随后美国的军事管理当局都号召大批科学家运所以美国及随后美国的军事管理当局

12、都号召大批科学家运所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题，实际上这便是要求他用科学手段来处理战略与战术问题，实际上这便是要求他用科学手段来处理战略与战术问题，实际上这便是要求他用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正是最们对种种（军事）经营进行研究，这些科学家小组正是最们对种种（军事）经营进行研究，这些科学家小组正是最们对种种（军事）经营进行研究，这些科学家小组正是最早的运筹小组（早的运筹小组（早的运筹小组（早的运筹小组（O.R.O.R.O.R.O.R.小组）。小组）。小组）。小组）。第二次世界大

13、战期间，运筹学（第二次世界大战期间，运筹学（第二次世界大战期间，运筹学（第二次世界大战期间，运筹学（OROROROR）成功地解决了许）成功地解决了许）成功地解决了许）成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为多重要作战问题，显示了科学的巨大物质威力，为多重要作战问题，显示了科学的巨大物质威力，为多重要作战问题，显示了科学的巨大物质威力，为“OR”OR”OR”OR”后来的发展铺平了道路。后来的发展铺平了道路。后来的发展铺平了道路。后来的发展铺平了道路。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。193519351

14、9351935年，英国科学家年，英国科学家年，英国科学家年，英国科学家R.Watson-WartR.Watson-WartR.Watson-WartR.Watson-Wart发明了雷达。丘吉尔命发明了雷达。丘吉尔命发明了雷达。丘吉尔命发明了雷达。丘吉尔命令在英国东海岸的令在英国东海岸的令在英国东海岸的令在英国东海岸的BawdseyBawdseyBawdseyBawdsey建立了一个秘密雷达站。建立了一个秘密雷达站。建立了一个秘密雷达站。建立了一个秘密雷达站。1939193919391939年由年由年由年由P.M.S.BlackettP.M.S.BlackettP.M.S.BlackettP.M

15、.S.Blackett（著名物理学家）（著名物理学家）（著名物理学家）（著名物理学家）为首，组织了为首，组织了为首，组织了为首，组织了一个小组，代号一个小组，代号一个小组，代号一个小组，代号“BlackettBlackettBlackettBlackett马戏团马戏团马戏团马戏团”。研究的问题是：设计将。研究的问题是：设计将。研究的问题是：设计将。研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对

16、探测、信息传递、作战指挥、战斗机与武器的的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。协调，作了系统的研究，并获得成功。协调，作了系统的研究，并获得成功。协调，作了系统的研究，并获得成功。“BlackettBlackettBlackettBlackett马戏团马戏团马戏团马戏团”在秘密报告中使用了在秘密报告中使用了在秘密报告中使用了在秘密报告中使用了“Operational Operational Operational Operational

17、ResearchResearchResearchResearch”，即，即，即，即“运筹学运筹学运筹学运筹学”。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。1 1 1 1模型模型模型模型 运筹学模型是用一些数学关系（数学方程、逻辑关系等）运筹学模型是用一些数学关系（数学方程、逻辑关系等）运筹学模型是用一些数学关系（数学方程、逻辑关系等）运筹学模型是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理定律、外部环来描述被研究对象的实际关系（技术关系、物理定律、外部环来描述被研究对象的实际关系（技术关系

18、、物理定律、外部环来描述被研究对象的实际关系（技术关系、物理定律、外部环境等）。境等）。境等）。境等）。运筹学模型的一个显著特点是它们大部分为运筹学模型的一个显著特点是它们大部分为运筹学模型的一个显著特点是它们大部分为运筹学模型的一个显著特点是它们大部分为最优化模型最优化模型最优化模型最优化模型。一般来说，运筹学模型都有一个一般来说，运筹学模型都有一个一般来说，运筹学模型都有一个一般来说，运筹学模型都有一个目标函数目标函数目标函数目标函数和和和和一系列的约束条件一系列的约束条件一系列的约束条件一系列的约束条件，模型的目标是在满足约束条件的前提下使目标函数模型的目标是在满足约束条件的前提下使目标

19、函数模型的目标是在满足约束条件的前提下使目标函数模型的目标是在满足约束条件的前提下使目标函数最大化最大化最大化最大化或或或或最最最最小化小化小化小化。第二节、运筹学模型及分析步骤第二节、运筹学模型及分析步骤第二节、运筹学模型及分析步骤第二节、运筹学模型及分析步骤 MaxMaxMaxMax（MinMinMinMin）z z z z7 x7 x7 x7 x1 1 1 1+5 x+5 x+5 x+5 x2 2 2 2 3 x 3 x 3 x 3 x1 1 1 1+2 x+2 x+2 x+2 x2 2 2 2 90 90 90 90 4 x 4 x 4 x 4 x1 1 1 1+6 x+6 x+6 x

20、+6 x2 2 2 2 200 200 200 200 7 x 7 x 7 x 7 x2 2 2 2 210210210210 x x x x1 1 1 10 0 0 0，x x x x2 2 2 20 0 0 0 数学模型举例：严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。2 2研究方法研究方法 从现实生活场合抽出本质的要素来构造数学模从现实生活场合抽出本质的要素来构造数学模 型；型；探索求解的结构并导出系统的求解过程；探索求解的结构并导出系统的求解过程；从可行方案中寻求系统的最优解法。从可行方案中寻求系统的最优解法。0102

21、03严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。3 3 运筹学解决问题的方法步骤运筹学解决问题的方法步骤明确问题明确问题明确问题明确问题建立模型建立模型建立模型建立模型设计算法设计算法设计算法设计算法整理数据整理数据整理数据整理数据求解模型求解模型求解模型求解模型评价结果评价结果评价结果评价结果明确问题明确问题建立模型建立模型设计算法设计算法整理数据整理数据求解模型求解模型评价结果评价结果简化？简化？满意？满意？YesNoNo严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或

22、突发事件。pOperations Research含义 Operations Operations 汉语翻译 工作、操作、行动、手术、运算Operations ResearchOperations Research 日本运用学 港台作业研究 中国大陆运筹学第三节第三节第三节第三节 运筹学的定义及学科体系运筹学的定义及学科体系运筹学的定义及学科体系运筹学的定义及学科体系严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。运筹学的定义运筹学的定义运筹学的定义运筹学的定义 Morse&KimballMorse&Kimball（运筹学界元老）

23、（运筹学界元老）运筹学是为决策运筹学是为决策机构在对其控制的业务活动进行决策时，提供的数量化机构在对其控制的业务活动进行决策时，提供的数量化为基础的科学方法。为基础的科学方法。英国人运筹学会英国人运筹学会（世界上最早的运筹学会）（世界上最早的运筹学会）运筹学运筹学是运用科学方法（特别是数学方法）来解决工业、商业、是运用科学方法（特别是数学方法）来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大政府、国防等部门里有关人力、机器、物资、金钱等大型系统的指挥和管理中出现的复杂问题的一门学科。型系统的指挥和管理中出现的复杂问题的一门学科。由一支由一支综合性综合性的队伍的队伍 ，采用，采

24、用科学的科学的方法，为一些涉及方法，为一些涉及到有机系统（人到有机系统（人-机）的控制系统问题提供解答，为该机）的控制系统问题提供解答，为该系统的系统的总目标服务总目标服务的学科。的学科。钱学森等钱学森等严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。学科体系学科体系学科体系学科体系 运筹学已经形成了一个庞大的学科体系，其具体内容主要包括：运筹学已经形成了一个庞大的学科体系，其具体内容主要包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、决规划论（包括线性规划、非线性规划、整数规划和动态规划）、决策论、对策论、排队论、

25、存储论、网络分析等。策论、对策论、排队论、存储论、网络分析等。线性规划对偶理论运输问题整数规划动态规划图与网络方法网络计划技术矩阵决策决策分析严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。绪论-思考题1 1 1 1什么是运筹学？什么是运筹学？什么是运筹学？什么是运筹学？列举我国古代运筹学思想的应用案例。列举我国古代运筹学思想的应用案例。列举我国古代运筹学思想的应用案例。列举我国古代运筹学思想的应用案例。2 2 2 2在第二次世界大战中，有哪些运用运筹学的战例？在第二次世界大战中，有哪些运用运筹学的战例？在第二次世界大战中，有哪些

26、运用运筹学的战例？在第二次世界大战中，有哪些运用运筹学的战例？3 3 3 3我国的运筹学研究和应用情况如何？我国的运筹学研究和应用情况如何？我国的运筹学研究和应用情况如何？我国的运筹学研究和应用情况如何？4 4 4 4主要分支有哪些？主要分支有哪些？主要分支有哪些？主要分支有哪些？5 5 5 5简述运筹学分析的步骤。简述运筹学分析的步骤。简述运筹学分析的步骤。简述运筹学分析的步骤。上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第第 一一 章章 线线 形形 规规 划划 本章学习重点本

27、章学习重点 线性规划是运筹学中比较成熟的一个分支，线性规划是运筹学中比较成熟的一个分支，线性规划是运筹学中比较成熟的一个分支，线性规划是运筹学中比较成熟的一个分支，它具有成熟而有效的求解方法，可以借助于计它具有成熟而有效的求解方法，可以借助于计它具有成熟而有效的求解方法，可以借助于计它具有成熟而有效的求解方法，可以借助于计算机进行求解，在军事、经济等领域中具有广算机进行求解，在军事、经济等领域中具有广算机进行求解，在军事、经济等领域中具有广算机进行求解，在军事、经济等领域中具有广泛的应用。学习本章，要掌握线性规划的泛的应用。学习本章，要掌握线性规划的泛的应用。学习本章，要掌握线性规划的泛的应用

28、。学习本章，要掌握线性规划的数学数学数学数学模型模型模型模型（建模以及把不同形式的线性规划问题化（建模以及把不同形式的线性规划问题化（建模以及把不同形式的线性规划问题化（建模以及把不同形式的线性规划问题化为为为为标准形式标准形式标准形式标准形式的方法）、的方法）、的方法）、的方法）、求解方法求解方法求解方法求解方法。v 线性规划问题的提出线性规划问题的提出v线性规划的数学模型线性规划的数学模型v线性规划的基本概念线性规划的基本概念v 线性规划问题的标准形式线性规划问题的标准形式继续继续继续继续返回返回返回返回第一节第一节 线性规划问题线性规划问题 及其数学模型及其数学模型上页上页上页上页下页下

29、页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。问题的提出问题的提出引例引例:生产计划问题生产计划问题上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。产品产品甲甲产品产品乙乙如何安排生产如何安排生产使利润最大使利润最大？上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。线性规划研究的内容

30、线性规划研究的内容在在现现有有的的资资源源条条件件下下，如如何何充充分分利利用用资资源源，使使任任务务或或目目标标完完成成得得最最好好（求求极极大大化问题）。化问题）。在在给给定定目目标标下下，如如何何以以最最少少的的资资源源消消耗耗，实现这个目标（求极小化问题）。实现这个目标（求极小化问题）。上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。是问题中要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，是问题中要确定的未知量，表明规划中的用数量表示的表明规划中的用数量表示的

31、表明规划中的用数量表示的表明规划中的用数量表示的方案、措施，可由决策者决方案、措施，可由决策者决方案、措施，可由决策者决方案、措施，可由决策者决定和控制。定和控制。定和控制。定和控制。第第1步步-确定决策变量确定决策变量设设 甲的产量甲的产量 乙的产量乙的产量 上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。Max Z=x1+x2决策变量决策变量第第2步步-定义目标函数定义目标函数 利利利利润润润润上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批

32、制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。Max Z=2 x1+3 x2系数系数第第2步步-定义目标函数定义目标函数上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。对我们有对我们有何限制何限制?上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第第3步步-表示约束条件表示约束条件 x1+2 x2 8 4 x1 16 4 x2 12 x1、x2

33、0 0上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。该计划的数学模型该计划的数学模型 目标函数目标函数 Max Z=2x1+3x2 约束条件约束条件 x1+2x2 8 4x1 16 4x2 12 x1、x2 0 0 x1 x2上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。决策变量（决策变量（决策变量（决策变量（Decision variablesDecision var

34、iables）目标函数（目标函数（目标函数（目标函数（Objective functionObjective function）约束条件（约束条件（约束条件（约束条件（Constraint conditionsConstraint conditions）可行域（可行域（可行域（可行域（Feasible region)Feasible region)最优解（最优解（最优解（最优解（Optimal solution)Optimal solution)基本概念基本概念问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表问题中要确定的未知量，表明规划中的用数量表示的方明规划中的用数

35、量表示的方明规划中的用数量表示的方明规划中的用数量表示的方案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定案、措施，可由决策者决定和控制。和控制。和控制。和控制。它是决策变量的函数它是决策变量的函数它是决策变量的函数它是决策变量的函数指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的指决策变量取值时受到的各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通各种资源条件的限制，通常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等常表达为含决策变量的等式或不等式。式或不等式。式或不等式。式或不等式。满足约束条件的决满足约束条件的

36、决满足约束条件的决满足约束条件的决策变量的取值范围策变量的取值范围策变量的取值范围策变量的取值范围可行域中使目标可行域中使目标可行域中使目标可行域中使目标函数达到最优的函数达到最优的函数达到最优的函数达到最优的决策变量的值决策变量的值决策变量的值决策变量的值上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。线性规划问题的共同特征线性规划问题的共同特征一组决策变量一组决策变量X X表示一个方案表示一个方案,一般一般X X大大于等于零。于等于零。约束条件是线性等式或不等式。约束条件是线性等

37、式或不等式。目标函数是线性的。目标函数是线性的。求目标函数最大求目标函数最大化或最小化化或最小化上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例例2(2(书书)某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品某厂生产甲乙两种产品，已知制成一吨产品甲需用资源甲需用资源甲需用资源甲需用资源A 3A 3A 3A 3吨，资源吨，资源吨，资源吨，资源B 4mB 4mB 4mB 4m3 3 3 3；制成一吨产品乙；制成一吨产品乙

38、；制成一吨产品乙；制成一吨产品乙需用资源需用资源需用资源需用资源A 2A 2A 2A 2吨，资源吨，资源吨，资源吨，资源B 6mB 6mB 6mB 6m3 3 3 3，资源，资源，资源，资源c 7c 7c 7c 7个单位。若个单位。若个单位。若个单位。若一吨产品甲和乙的经济价值分别为一吨产品甲和乙的经济价值分别为一吨产品甲和乙的经济价值分别为一吨产品甲和乙的经济价值分别为7 7 7 7万元和万元和万元和万元和5 5 5 5万元，万元，万元，万元，三种资源的限制量分别为三种资源的限制量分别为三种资源的限制量分别为三种资源的限制量分别为90909090吨、吨、吨、吨、200m200m200m200

39、m3 3 3 3和和和和210210210210个单个单个单个单位，试决定应生产这两种产品各多少吨才能使创位，试决定应生产这两种产品各多少吨才能使创位，试决定应生产这两种产品各多少吨才能使创位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高造的总经济价值最高造的总经济价值最高造的总经济价值最高?上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。建模步骤：建模步骤：第一步：确定决策变量第一步：确定决策变量 x x1 1：生产产品甲的数量（吨）：生产产品甲的数量（吨）x x2 2

40、：生产产品乙的数量（吨）：生产产品乙的数量（吨）上述变量为由决策者决定的未知量，称上述变量为由决策者决定的未知量，称为为决策变量决策变量。上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第二步：确定目标函数第二步：确定目标函数 以以 Z Z 表示生产甲和乙两种产品各为表示生产甲和乙两种产品各为x x1 1和和x x2 2（吨）时产生的经济价值，总经济价值（吨）时产生的经济价值，总经济价值最高的目标可表示为：最高的目标可表示为：max zmax z7 x7 x1 1十十5 x5 x2

41、2 这就是该问题的这就是该问题的目标函数目标函数。上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。第三步：确定约束条件第三步：确定约束条件 本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各本例的约束条件为三种资源的限制用量。对各个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关个限制条件逐一加以分析，写出反映其限制关系的表达式（等式或不等式），

42、从而得到系的表达式（等式或不等式），从而得到系的表达式（等式或不等式），从而得到系的表达式（等式或不等式），从而得到约束约束约束约束条件条件条件条件。资源资源资源资源A A A A限制：限制：限制：限制：3 x3 x3 x3 x1 1 1 1十十十十2 x2 x2 x2 x2 2 2 2 90 90 90 90 资源资源资源资源B B B B限制；限制；限制；限制；4 x4 x4 x4 x1 1 1 1十十十十6 x6 x6 x6 x2 2 2 2 200 200 200 200 资源资源资源资源C C C C限制：限制：限制：限制：7 x7 x7 x7 x2 2 2 2 2102102102

43、10 此外，产量此外，产量此外，产量此外，产量x x x x1 1 1 1和和和和x x x x2 2 2 2不能为负，只能取正值不能为负，只能取正值不能为负，只能取正值不能为负，只能取正值 非负条件：非负条件：非负条件：非负条件：x x x x1 1 1 1 0 0 0 0，x x x x2 2 2 2 0 0 0 0 上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。经上述分析，可将该问题表示为：经上述分析，可将该问题表示为：max zmax z7 x7 x1 1十十5 x5 x2

44、 2 3 x 3 x1 1十十2 x2 x2 2 90 90 4 x 4 x1 1十十6 x6 x2 2 200 200 7 x 7 x2 2 210210 x x1 1 0 0，x x2 2 0 0这种数学表达方式，称为该问题的一种数学模型。这种数学表达方式，称为该问题的一种数学模型。上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。线性规划三要素线性规划三要素 线性规划线性规划线性规划线性规划(Linear Programming(Linear Programming，LP)LP)

45、有：有：有：有：一组有待一组有待一组有待一组有待决策的变量决策的变量决策的变量决策的变量 （指模型中要求解的未知量指模型中要求解的未知量指模型中要求解的未知量指模型中要求解的未知量）一个线性的一个线性的一个线性的一个线性的目标函数目标函数目标函数目标函数 （指模型中要达到的目标的数学表达式）（指模型中要达到的目标的数学表达式）（指模型中要达到的目标的数学表达式）（指模型中要达到的目标的数学表达式）一组线性的一组线性的一组线性的一组线性的约束条件约束条件约束条件约束条件 （指模型中的变量取值所需要满足的一切限制（指模型中的变量取值所需要满足的一切限制（指模型中的变量取值所需要满足的一切限制（指模

46、型中的变量取值所需要满足的一切限制条件）条件）条件）条件）上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。线性规划模型的一般形式线性规划模型的一般形式 上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。线性规划问题的标准形式线性规划问题的标准形式标准形式为标准形式为:目标函数最大目标函数最大约束条件等式约束条件等式决策变量非负决策变量非负右端常数项非负右端常数项非负上页上页上

47、页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。用矩阵表示用矩阵表示用矩阵表示用矩阵表示A A系数矩阵系数矩阵C C价值向量价值向量b b资源向量资源向量X X决策变量向量决策变量向量上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一般线性规划问题的标准形化一般线性规划问题的标准形化线型规划问题的数学模型有各种不同的形式，为线型规划问题的数学模型有各种不同的形式，为了便于讨论和求解，

48、需要将线型规划问题的数学了便于讨论和求解，需要将线型规划问题的数学模型写成一个统一的格式，称为线型规划问题的模型写成一个统一的格式，称为线型规划问题的标准型。标准型。统一格式规定如下统一格式规定如下：1、目标函数取最大化、目标函数取最大化 2、所有约束条件用等式来表示、所有约束条件用等式来表示 3、所有决策变量取非负值、所有决策变量取非负值 4、每一约束条件的右端常数（资源限量）为非负值、每一约束条件的右端常数（资源限量）为非负值上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。min

49、 Z=CX min Z=CX 等价于等价于 max Zmax Z=-CX=-CX“”约束：加入非负松驰变量约束：加入非负松驰变量一般线性规划问题的标准形化一般线性规划问题的标准形化例：例：目标函数目标函数目标函数目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件约束条件约束条件约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 0 0上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并

50、处理各类违纪行为或突发事件。min Z=CX min Z=CX 等价于等价于 max Zmax Z=-CX=-CX“”约束：加入非负松驰变量约束：加入非负松驰变量一般线性规划问题的标准形化一般线性规划问题的标准形化例：例：上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。“”约束：约束：减去非负剩余变量；减去非负剩余变量；Max 例例例例 ：可正可负（即无约束）；可正可负（即无约束）；上页上页上页上页下页下页下页下页返回返回返回返回严格执行突发事件上报制度、校外活动报批制度等相关规章制