新运筹学课件

1、运运 筹筹 学学( Operations Research )Page 2 运筹学（Operations Research）是用数学方法研究各种系统的最优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。Page 3 选用教材选用教材 运筹学教程胡运权主编 （第2版）清华出版社参考教材运筹学牛英武主编 西安交通大学出版社运筹学(修订版) 钱颂迪主编 清华出版社 先修课程先修课程 高等数学 线性代数 概率论（1）运筹学的产生发展及发展趋势）运筹学的产生发展及发展趋势（2）运筹学的性质特点及解题思路）运筹学的性质特点及解题思路（3）运筹学

2、的分支简介）运筹学的分支简介（4）运筹学在管理中的应用）运筹学在管理中的应用本章主要内容：本章主要内容：Page 5一、一、运筹学（运筹学（Operations Research）的产生、发展及）的产生、发展及发展趋势发展趋势 运筹学运筹学 的发展：三个来源（军事、经济及管理）的发展：三个来源（军事、经济及管理） 1.军事：运筹学的主要发源地军事：运筹学的主要发源地 国外历史上的阿基米德、伽利略研究过作战问题；第一次世界大战时，英国的兰彻斯特（Lanchester）提出了战斗方程，指出了数量优势、火力和胜负的动态关系；美国的爱迪生为美国海军咨询委员会研究了潜艇攻击和潜艇回避攻击的问题。Page

3、 6运筹学的历史运筹学的历史“运作研究运作研究(Operational Research)小组小组”:解决复解决复杂的战略和战术问题。例如：杂的战略和战术问题。例如：1. 如何合理运用雷达有效地对付德军德空袭如何合理运用雷达有效地对付德军德空袭2. 对商船如何进行编队护航，使船队遭受德国潜对商船如何进行编队护航，使船队遭受德国潜艇攻击时损失最少；艇攻击时损失最少；3. 在各种情况下如何调整反潜深水炸弹的爆炸深在各种情况下如何调整反潜深水炸弹的爆炸深度，才能增加对德国潜艇的杀伤力等。度，才能增加对德国潜艇的杀伤力等。Page 7运筹学的正式产生：第二次世界大战运筹学的正式产生：第二次世界大战 据

4、不完全统计，二战期间，仅在英、美和加拿大，参加据不完全统计，二战期间，仅在英、美和加拿大，参加运筹学工作的科学家超过运筹学工作的科学家超过700名。名。2.管理管理 (1)泰勒的时间动作研究、甘特的用于生产计划与控制的泰勒的时间动作研究、甘特的用于生产计划与控制的“甘特图甘特图”、吉尔布雷思夫妇的动作研究等、吉尔布雷思夫妇的动作研究等 (2)爱尔朗（爱尔朗（Erlong）的排队论公式）的排队论公式 19091920年间，丹麦哥本哈根电话公司工程师爱尔朗年间，丹麦哥本哈根电话公司工程师爱尔朗陆续发表了关于电话通路数量等方面的分析与计算公式。陆续发表了关于电话通路数量等方面的分析与计算公式。尤其是

5、尤其是1909年的论文年的论文“概率与电话通话理论概率与电话通话理论”，开创了，开创了运筹学的重要分支排队论。运筹学的重要分支排队论。Page 83.经济（数理经济学）经济（数理经济学） (1)Von Neumann 与对策论与对策论 1932年，年，Von Neumann提出一个广义经济平衡模型；提出一个广义经济平衡模型；1939年，提出年，提出了一个属于宏观经济优化的控制论模型；了一个属于宏观经济优化的控制论模型；1944年，与年，与Morgenstern共著共著的对策论与经济行为开创了对策论分支。的对策论与经济行为开创了对策论分支。 (2)康托洛维奇与康托洛维奇与“生产组织与计划中的数学

6、方法生产组织与计划中的数学方法” 30年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定年代，苏联数理经济学家康托洛维奇从事生产组织与管理中的定量化方法研究，取得了很多重要成果。量化方法研究，取得了很多重要成果。1939年，出版了堪称运筹学的先年，出版了堪称运筹学的先驱著作生产组织与计划中的数学方法，其思想和模型被归入线驱著作生产组织与计划中的数学方法，其思想和模型被归入线性规划范畴。性规划范畴。Page 9Page 1011二、运筹学的研究对象、研究特征及解题思路二、运筹学的研究对象、研究特征及解题思路中国企业管理百科全书中国企业管理百科全书：运筹学是运用分析，试：运筹学是运用分析，试

7、验，量化的方法，对经济管理系统中人、财、物验，量化的方法，对经济管理系统中人、财、物( (时间时间) )等有限资源，进行统筹安排，为决策者提供有依据的等有限资源，进行统筹安排，为决策者提供有依据的最优方案最优方案（满意方案）（满意方案），以实现最有效地管理。，以实现最有效地管理。辞海辞海对运筹学解释为：对运筹学解释为：“二十世纪四十年代开始二十世纪四十年代开始形成的一门科学，主要研究经济活动与军事活动中能形成的一门科学，主要研究经济活动与军事活动中能用数量来表达的有关运用，筹划与管理方面的问题，用数量来表达的有关运用，筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综它根据问

8、题的要求，通过数学的分析与运算，作出综合性的合理的安排，以达到较经济、较有效地使用人合性的合理的安排，以达到较经济、较有效地使用人力、物力。近年来，它在理论与应用方面都有较大发力、物力。近年来，它在理论与应用方面都有较大发展。其主要分支有规划论、对策论、排队论及质量控展。其主要分支有规划论、对策论、排队论及质量控制等。制等。”运筹学的研究对象、研究特征及解题思路运筹学的研究对象、研究特征及解题思路Page 12 1）机器、工具、设备、人员等资源如何最佳利用问题）机器、工具、设备、人员等资源如何最佳利用问题 研究方法有：线性规划、整数规划、网络图、动态规划、研究方法有：线性规划、整数规划、网络图

9、、动态规划、 目标规划等目标规划等2）竞争现象：如战争、投资、商品竞争）竞争现象：如战争、投资、商品竞争 方法是对策论方法是对策论3）拥挤现象：如公共汽车排队、打电话、买东西、飞机着）拥挤现象：如公共汽车排队、打电话、买东西、飞机着陆、船舶进港等陆、船舶进港等 方法是排队论方法是排队论Page 13所以可对运筹学的研究对象做如下概括： .运筹学的研究对象是各种系统。 .运筹学的研究目的是实现系统的最优化，求得合理利用各种资源的最优方案。 .运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解。 . .运筹学的研究动机是为决策者提供科学决策的依据。运筹学的

10、研究动机是为决策者提供科学决策的依据。 运筹学在工业、农业、商业、物流、经济计划、人力资源、军事等运筹学在工业、农业、商业、物流、经济计划、人力资源、军事等行业都有着非常广泛的应用。有人曾对世界上行业都有着非常广泛的应用。有人曾对世界上500500家著名的企业集团或家著名的企业集团或跨国公司进行过调查，发现其中跨国公司进行过调查，发现其中95%95%曾使用过线性规划，曾使用过线性规划，75%75%使用过运输使用过运输模型，模型，90%90%使用过网络计划技术，使用过网络计划技术，90%90%使用过存储模型，使用过存储模型，43%43%使用过动态使用过动态规划。规划。 由此可见运筹学是一门应用性

11、很强的学科。特别是随着计算机技术由此可见运筹学是一门应用性很强的学科。特别是随着计算机技术的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显示出其广泛的使用价值。示出其广泛的使用价值。Page 143.3.运筹学的性质特点运筹学的性质特点1 1）运筹学的性质）运筹学的性质 应用科学“应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据”。2)2)运筹学的特点运筹学的特点定量化分析多学科交叉，如综合利用了心理学、经济学、物理、化学等方法实现最优决策15(1) (1) 科学性：运筹学是

12、以研究事物内科学性：运筹学是以研究事物内在规律，并从定量分析的角度探求更在规律，并从定量分析的角度探求更好地解决问题的一门科学。好地解决问题的一门科学。运筹学的研究对象、研究特征及解题思路运筹学的研究对象、研究特征及解题思路16(2) (2) 应用性：运筹学既对各种经营进应用性：运筹学既对各种经营进行创造性的科学研究，又涉及到组织行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意性，最终应能向决策者提供建设性意见，并应收到实效；见，并应收到实效；运筹学的研究对象、研究特征及解题思路运筹学的研究对象、研究特征及解题思路

13、17(3)(3)多学科的交叉性、综合性：运筹学研究多学科的交叉性、综合性：运筹学研究中吸收了来自不同领域的经验，并被广泛中吸收了来自不同领域的经验，并被广泛应用于工商企业、军事部门、民政事业等应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不研究组织内的统筹协调问题，故其应用不受行业、部门之限制；受行业、部门之限制；运筹学的研究对象、研究特征及解题思路运筹学的研究对象、研究特征及解题思路18(4)(4)系统性和最优性系统性和最优性: :它以整体最优为目它以整体最优为目标标, ,从系统的观点出发从系统的观点出发, ,力图以整个系统力图以整个系统最佳的方式来解决该系统各部门之

14、间的最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解利害冲突。对所研究的问题求出最优解, ,寻求最佳的行动方案寻求最佳的行动方案, ,所以它也可看成是所以它也可看成是一门优化技术一门优化技术, ,提供的是解决各类问题的提供的是解决各类问题的优化方法。优化方法。运筹学的研究对象、研究特征及解题思路运筹学的研究对象、研究特征及解题思路Page 19运筹学的研究对象、研究特征及解题思路运筹学的研究对象、研究特征及解题思路4.4.运筹学的工作步骤运筹学的工作步骤v提出和形成问题，v建立模型，v求解，v解的检验，v解的控制，v解的实施Page 20运筹学的研究的主要步骤：运筹学的研究

15、的主要步骤：真实系统真实系统系统分析系统分析问题描述问题描述模型建立模型建立与修改与修改模型求解模型求解与检验与检验结果分析与结果分析与实施实施数据准备数据准备Page 21数学规划（数学规划（线性规划、整数规划、目标规划线性规划、整数规划、目标规划、动态、动态规划等）规划等）图论图论存储论存储论排队论排队论对策论对策论排序与统筹方法排序与统筹方法决策分析决策分析Page 22运筹学在管理中的应用涉及几个方面：运筹学在管理中的应用涉及几个方面：1. 生产计划2. 运输问题3. 人事管理4. 库存管理5. 市场营销6. 财务和会计另外，还应用于设备维修、更新和可靠性分析，项目的选择另外，还应用于

16、设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。与评价，工程优化设计等。231.3 1.3 运筹学在管理中的应用运筹学在管理中的应用 生产计划生产计划: : 生产作业的计划、日程表的编生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等排、合理下料、配料问题、物料管理等; ; 库存管理库存管理: : 多种物资库存量的管理多种物资库存量的管理, , 库存库存方式、库存量等方式、库存量等; ; 运输问题运输问题: : 确定最小成本的运输线路、物确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址资的调拨、运输工具的调度以及建厂地址的选择等的选择等; ; 人事管理人事

17、管理: : 对人员的需求和使用的预测，对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才确定人员编制、人员合理分配，建立人才评价体系等评价体系等; ;241.3 1.3 运筹学在工商管理中的应用运筹学在工商管理中的应用 市场营销市场营销: : 广告预算、媒介选择、广告预算、媒介选择、定价、产品开发与销售计划制定等定价、产品开发与销售计划制定等; ; 财务和会计财务和会计: : 预测、贷款、成本分预测、贷款、成本分析、定价、证券管理、现金管理等析、定价、证券管理、现金管理等; ; * * * * 设备维修、更新，项目选择、设备维修、更新，项目选择、评价，工程优化设计与管理等评价，工程

18、优化设计与管理等; ;Page 25学科总成绩学科总成绩平时成绩平时成绩（2020）课堂考勤课堂考勤（5050）平时作业平时作业（5050）期末成绩期末成绩（8080）讲授为主，结合习题作业讲授为主，结合习题作业26“田忌田忌赛马赛马”是家喻户晓的历史故事。战国时齐威王与齐是家喻户晓的历史故事。战国时齐威王与齐相田忌赛马，双方各出三匹马比赛，每胜一场赢得一千金。由相田忌赛马，双方各出三匹马比赛，每胜一场赢得一千金。由于王府的马比相府的马好，所以田忌每次比赛都要输掉三千金。于王府的马比相府的马好，所以田忌每次比赛都要输掉三千金。 后来田忌的谋士孙膑献了一计：在每次开赛前要求对方先后来田忌的谋士孙

19、膑献了一计：在每次开赛前要求对方先报马名，由此区分对方参赛的是上马、中马还是下马；然后以报马名，由此区分对方参赛的是上马、中马还是下马；然后以自己的上马对对方的中马、自己的中马对对方和下马、自己的自己的上马对对方的中马、自己的中马对对方和下马、自己的下马对对方的上马。这样，两胜一负反而赢得一千金。下马对对方的上马。这样，两胜一负反而赢得一千金。 几个典故几个典故 我国古代我国古代运筹运筹思想运用的典故思想运用的典故1 1“田忌田忌赛马赛马”27第一章第一章 绪绪 论论 我国古代我国古代运筹运筹思想运用的典故思想运用的典故2 2晋国公重建皇城晋国公重建皇城晋国公重建皇城的施工方案，晋国公重建皇城

20、的施工方案，体现了运筹学的朴素思想。要体现了运筹学的朴素思想。要使重建工程的各个工序使重建工程的各个工序, ,在时间、空间上彼此协调在时间、空间上彼此协调, ,环环环相扣环相扣, ,就需要运用行列式的相关知识就需要运用行列式的相关知识, ,进行精确计算进行精确计算. .283.3.沈括运粮沈括运粮 沈括沈括(1031-1095年年),北宋时期大科学家、军事北宋时期大科学家、军事家家.在率兵在率兵抗击西夏侵扰抗击西夏侵扰的征途中的征途中,曾经从行军中各曾经从行军中各类人员可以背负粮食的基本数据出发类人员可以背负粮食的基本数据出发,分析计算分析计算了后了后勤人员与作战士兵在不同行军天数中的不同比例

21、关勤人员与作战士兵在不同行军天数中的不同比例关系系,同时也分析计算了用各种牲畜运粮与人力运粮之同时也分析计算了用各种牲畜运粮与人力运粮之间的间的利弊利弊,最后做出了最后做出了从敌国就地征粮从敌国就地征粮,保障前方供保障前方供应的重要决策应的重要决策.从而减少了后勤人员的比例从而减少了后勤人员的比例,增强了增强了 前方作战的兵力前方作战的兵力. Page 29“管理运筹学管理运筹学”2.02.0版包括：线性规划、运输问题、整数规划（版包括：线性规划、运输问题、整数规划（0-10-1整数整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、规划、纯整数规划和混合整数规划）、目标规划、对

22、策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共决策分析、预测问题和层次分析法，共1515个子模块。个子模块。Chapter1 线性规划线性规划 (Linear Programming) LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 LP模型的应用模型的应用Page 311. 规划问题规划问题 生产和经营管理中经常提出如何合理安排，使生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源

23、得到充分利用，获得最大的人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。效益，这就是规划问题。（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，用）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源最少的资源 （如资金、设备、原标材料、人工、时间等）（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得最）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多好的经济效益（如产品量最多 、利润最大、利润最大. .）Page 32例例1.1 如图所示，如何截取如图所示

24、，如何截取x使铁皮所围成的容积最使铁皮所围成的容积最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax Page 33例例1、(生产计划问题）生产计划问题） 某企业计划生产甲、乙两种产某企业计划生产甲、乙两种产品。这些产品分别要在品。这些产品分别要在A、B、C、D、四种不同的设、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？排生产计划，使企业总的利润最大？ 设设 备备产产

25、品品 A B C D利润（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12Page 34解：设解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：分别为甲、乙两种产品的产量，则数学模型为：Page 35例例2（下料问题）长度为（下料问题）长度为1米的圆钢多根，欲截成米的圆钢多根，欲截成40、30、20cm长的用料分别长的用料分别为为20、45、50根，问如何下料才能使用料最省？根，问如何下料才能使用料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8

26、8种不种不同的下料方案：同的下料方案：圆钢（米）圆钢（米）40402 21 11 11 10 00 00 00 030300 02 21 10 03 32 21 10 020201 10 01 13 30 02 23 35 5料头（米）料头（米）0 00 010100 010100 010100 0Page 36 上述问题归纳为如何混合使用这上述问题归纳为如何混合使用这8 8种不同的下料方案，种不同的下料方案，来制造来制造20,45,5020,45,50根不同的钢料，且要使用料最省？根不同的钢料，且要使用料最省？ 用料最省反映在两个方面：用料最省反映在两个方面： 1. 1.所用圆钢数最少所用圆

27、钢数最少 2. 2.使剩余的料头总长为最短使剩余的料头总长为最短 设设x xj j表示用第表示用第j j种下料方案下料的原料根种下料方案下料的原料根j=1,2,j=1,2,8,8,目标：料头总长度目标：料头总长度= = 圆钢数圆钢数= =Page 37例例3（运输问题）两个仓库（运输问题）两个仓库A1、A2，每月可分别调出钢材，每月可分别调出钢材28、29吨，吨，工地工地B1、B2、B3每月需钢材分别每月需钢材分别12、15、30吨均由仓库吨均由仓库A1、A2供应，供应，各仓库运往各工地每吨钢材的运费（元各仓库运往各工地每吨钢材的运费（元/吨）如下表，问如何安排运输吨）如下表，问如何安排运输计

28、划可是总费用最小？计划可是总费用最小？B1B2B3供应量A118252028A221222429需求量121530Page 38例例4、（合理配料问题）要求所分配饲料每单位的营养标准为：含蛋白、（合理配料问题）要求所分配饲料每单位的营养标准为：含蛋白质不少于质不少于21%，纤维不少于，纤维不少于5%，脂肪不少于，脂肪不少于3.4%，铁不少于，铁不少于1%但不大但不大于于1.05%，钙不少于，钙不少于0.45%但不大于但不大于0.6%。要求得出成本最小的配比方案要求得出成本最小的配比方案Page 39例例5、（广告方式的选择）某公司推销一种新产品，有关数据如下表，销、（广告方式的选择）某公司推销

29、一种新产品，有关数据如下表，销售部第一个月的广告预算费为售部第一个月的广告预算费为2万元，要求至少有万元，要求至少有8次电视广告，次电视广告，15次报次报纸广告，电视广告费不得超过纸广告，电视广告费不得超过1.2万元，电台广播至少隔日一次，问公司万元，电台广播至少隔日一次，问公司销售部应采用怎样的广告宣传计划，才能取得最好的宣传效果？销售部应采用怎样的广告宣传计划，才能取得最好的宣传效果？广告方式广告费用（元/次）可用最高次数（每月）期望宣传效果电视（白天）5001650电视（晚上）10001080每日晨报1002430星期日报广播电台300804254015Page 40Page 4100

30、)( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 简写为：简写为：Page 42通常称 为决策变量， 为价值系数， 为消耗系数, 。 为资源限制系数。) (21ncccC 12nx, x, x1 11 2m na,a, a12mb, b, bPage 43) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：Page 44 mnmnaaaaA11

31、11 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB1Page 454. 线性规划问题的标准形式线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特点：特点：(1) 目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2) 约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3) 决策变量决策变量xj为非负。为非负。Page 46（1 1）如何化标准形式）如何化标准形式 目标函数的转换目标函数的转换如果是求极小值即

32、如果是求极小值即 则可将目标函数乘以则可将目标函数乘以(-1)(-1)可化为求极可化为求极大值问题。大值问题。 jjxczmin也就是：令也就是：令 可得到上式。可得到上式。zz jjxczzmax即即若存在取值无约束的变量若存在取值无约束的变量 可令可令 其中：其中：jxjjjxxx 0, jjxx 变量的转换变量的转换Page 47 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量 变量的变换当变量的变换当 可令可令 ，显然，显

33、然0 jxjjxx 0 jxPage 48例例1.3 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式 ,0,52324 7 532min321321321321321无无约约束束xxxxxxxxxxxxxxxZ用用 替换替换 ，且，且 解解:（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以33xx 3x0,33 xxPage 49(2) 第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3) 第二个约束条件是第二个约束

34、条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4) 第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;Page 50 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标

35、准形式如下：标准形式如下：Page 515. 5. 线性规划问题的解线性规划问题的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 52线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体

36、坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策只有两个决策变量的线性规划问题，这时可以通过图解的方法变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。探线性规划基本原理和几何意义等优点。Page 53max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X

37、2 0例例1.5 用图解法求解线性规划问题用图解法求解线性规划问题Page 54x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z = 2X1 + X2Page 55max Z=3X1+5.7X

38、2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域Page 56min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 +

39、1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此点是唯一最优解此点是唯一最优解Page 57 006346321212121xxxxxxxx、246x1x2246无界解无界解( (无最优解无最优解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zx1x2O10203040102030405050无可行解无可行解(即无最优解即无最优解)0,050305 .140221212121 xxxxxxxxmax Z=3x1+4x2例

40、例1.7Page 59学习要点：学习要点：1. 通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）（唯一最优解；无穷多最优解；无界解；无可行解）2. 作图的关键有三点：作图的关键有三点： (1) 可行解区域要画正确可行解区域要画正确 (2) 目标函数增加的方向不能画错目标函数增加的方向不能画错 (3) 目标函数的直线怎样平行移动目标函数的直线怎样平行移动Page 60 可行解可行解：满足约束条件、的解为可行解。所有可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。的集合为可行域。 最优解最优解：使目标函数达到最大值

41、的可行解。：使目标函数达到最大值的可行解。 基：基：设设A为约束条件的为约束条件的mn阶系数矩阵阶系数矩阵(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 83例例1.9 用单纯形法求解用单纯形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：将数学模型化为标准形式：解：将数学模型化为标准形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不难

42、看出不难看出x4、x5可作为初始基变量，列单纯形表计算。可作为初始基变量，列单纯形表计算。Page 84cj12100icB基变量基变量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 85学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤Page 86人工变量

43、法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大的变量称为人工变量，构成的可行基称为人工基，用大MM法或两阶段法求解，这种用人工变量作桥梁的求解方法称法或两阶段法求解，这种用人工变量作桥梁的求

44、解方法称为人工变量法。为人工变量法。Page 87例例1.10 用大用大M法解下列线性规划法解下列线性规划 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。Page 88故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：

45、7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 Page 89cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2

46、+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 90解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）

47、多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：）退化解的判别：存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。Page 91单纯性法小结单纯性法小结:建建立立模模型型个个 数数

48、取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加变量新加变量系数系数两两个个三个三个以上以上xj0 xj无无约束约束xj 0 bi 0bi mi 时，企业愿意时，企业愿意购进这种资源，单位纯利为购进这种资源，单位纯利为yi*mi ，则有利可图；如果，则有利可图；如果yi* mi 则购进资源则购进资源i，可获单位纯利，可获单位纯利yi*mi 若若yi* mi则转让资源则转让资源i ，可获单位纯利，可获单位纯利miyiPage 1473）影子价格在资源利用中的应用）影子价格在资源利用中的应用根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理:Y*Xs=0 , YsX

49、*=0表明生产过程中如果某种资源表明生产过程中如果某种资源bi未得到充分利用时，该种资未得到充分利用时，该种资源的影子价格为源的影子价格为0；若当资源资源的影子价格不为；若当资源资源的影子价格不为0时，表明时，表明该种资源在生产中已耗费完。该种资源在生产中已耗费完。Page 1484）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数 miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j种产品的价格种产品的价格; ; 表示生产该种产品所表示生产该种产品所消耗的各项资源的影子价格的总和消耗的各项资源的影子价格的总和, ,即产品的

50、隐含成本。即产品的隐含成本。 miiijya1当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产品有，表明生产该项产品有利，可在计划中安排；否则利，可在计划中安排；否则 ，用这些资源生产别的，用这些资源生产别的产品更有利，不在生产中安排该产品。产品更有利，不在生产中安排该产品。0 j 0 j Page 149 对偶单纯形法是求解线性规划的另一个基本方法。它对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形对偶单纯形法。不要简单理解为是

51、求解对偶问题的单纯形法。法。 找出一个对偶问题的可行基，保持对偶问题为可行解的找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断条件下，判断XB是否可行（是否可行（XB为非负），若否，通过变换基为非负），若否，通过变换基解，直到找到原问题基可行解（即解，直到找到原问题基可行解（即XB为非负），这时原问题为非负），这时原问题与对偶问题同时达到可行解，由定理与对偶问题同时达到可行解，由定理4可得最优解。可得最优解。Page 150找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为可行解情况下转移到LP的另一个基本解的另一个基本解最优解最

52、优解是是否否循循环环结束结束Page 151例例2.9 用对偶单纯形法求解：用对偶单纯形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:（1）将模型转化为求最大化问题，约束方程化为等式求将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行，即全部检验数出一组基本解，因为对偶问题可行，即全部检验数0（求（求max问题）。问题）。Page 152 014 5 12 3210 2215129max61632153214321321xxxxxxxxxxxxxxxxZcj-9-12-15000bcBxB

53、x1x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14(-9/-1.-12/-1. -15/-5)j-9-12-150000iPage 153cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x

54、29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14ij j Page 154cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3j 原问题的最优解为：原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 其对偶问题的最优解为：其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），），W*= 72Page

55、 155 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题： 用对偶单纯形法求解线性规划是一种求解方法，而不是去求对用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解偶问题的最优解 初始表中一定要满足对偶问题可行，也就是说检验数满足最优初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则判别准则 最小比值中最小比值中 的绝对值是使得比值非负，在极小化问题的绝对值是使得比值非负，在极小化问题 j j00，分母分母a aij ij0 0 这时必须取绝对值。在极大化问题中，这时必须取绝对值。在极大化问题中， j j00，分母，分母a aij ij00， 总满足非负，这时

56、绝对值符号不起作用，可以去掉。如总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成在本例中将目标函数写成ijja 这里这里 j j 0 0在求在求 k k时就可以不带绝对值符号。时就可以不带绝对值符号。32134maxxxxz ijja Page 156 对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；量后确定进基变量； 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是

57、保证下一其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是个原问题的基本解可行，对偶单纯形法的最小比值是 0minikikiiaab其目的是保证下一个对偶问题的基本解可行其目的是保证下一个对偶问题的基本解可行 0|minljljjjaa 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的规则，任选一个小于零的b bii对应的基变量出基，不影响计算结果，对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。只是迭代次数可能不一样。 0|min iilbbbPage 157学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概

58、念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤运输规划问题的数学模型运输规划问题的数学模型表上作业法表上作业法运输问题的应用运输问题的应用 Page 159例例3.1 某公司从两个产地某公司从两个产地A1、A2将物品运往三个销地将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最物品的运费如下表所示，问：应如何调运可使总运输费用最小？小？B1B2B3产量产量A1646200A2655300销量销量1

59、50150200Page 160解：产销平衡问题：总产量解：产销平衡问题：总产量 = 总销量总销量500 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列运输量的运输量，得到下列运输量表：表：B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij

60、 0 ( i = 1、2；j = 1、2、3）Page 161运输问题的一般形式：产销平衡运输问题的一般形式：产销平衡A1、 A2、 Am 表示某物资的表示某物资的m个产地；个产地； B1、B2、Bn 表示表示某物质的某物质的n个销地；个销地；ai 表示产地表示产地Ai的产量；的产量； bj 表示销地表示销地Bj 的销量；的销量； cij 表示把物资从产地表示把物资从产地Ai运往销地运往销地Bj的单位运价。设的单位运价。设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，得到下列一般运输量问题的模型：的运输量，得到下列一般运输量问题的模型： minjijijxcz11min njmi