自学_运筹学.ppt

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

1、运筹学自学要求运筹学自学要求运筹学（运筹学（Operations ResearchOperations Research）是用数学方法研究各种系统的最优）是用数学方法研究各种系统的最优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。各种资源的最佳方案，为决策者提供科学决策的依据。运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存储论，决策论和对策论等，其中数学规划又包括线性规划，整数规划，储论，决策论和对策

2、论等，其中数学规划又包括线性规划，整数规划，非线性规划，目标规划和动态规划等，非线性规划，目标规划和动态规划等，虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。学习内容

3、：线性规划、整数规划学习内容：线性规划、整数规划要求：建立模型、软件求解（要求：建立模型、软件求解（Matlab）概述概述运筹学（运筹学（Operations ResearchOperations Research）是用数学方法研究各种系统的最优）是用数学方法研究各种系统的最优化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用化问题，运筹学强调发挥现有系统的效能，应用数学模型求得合理利用各种资源的最佳方案，为决策者提供科学决策的依据。各种资源的最佳方案，为决策者提供科学决策的依据。运筹学的内容有数学规划，运输问题，图与网络分析，排队论，存运筹学的内容有数学规划，运输问题，图与网络分

4、析，排队论，存储论，决策论和对策论等，其中数学规划又包括线性规划，整数规划，储论，决策论和对策论等，其中数学规划又包括线性规划，整数规划，非线性规划，目标规划和动态规划等，非线性规划，目标规划和动态规划等，虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以虽然运筹学包括的内容较多，但是它们有两个共同的特点：一是以全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技全局最优作为问题的基本出发点；二是通过建立数学模型，运用优化技术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相术求得系统最合理的运营方案。由于各种系统的运营机制和性能不尽相同，它们的数学模型也各不相同，

5、从而形成了运筹学的不同分支。同，它们的数学模型也各不相同，从而形成了运筹学的不同分支。所以可对运筹学做如下概括：所以可对运筹学做如下概括：，运筹学的研究对象是各种系统，运筹学的研究对象是各种系统，运筹学的研究目的是实现系统的最优化，求得合理利用各种资源，运筹学的研究目的是实现系统的最优化，求得合理利用各种资源的最优方案，的最优方案，运筹学的研究方法是运用数学语言来描述实际系统，通过建立数，运筹学的研究方法是运用数学语言来描述实际系统，通过建立数学模型和优化技术求得系统运营的最优解。学模型和优化技术求得系统运营的最优解。，运筹学的研究动机是，运筹学的研究动机是为决策者提供科学决策的依据。为决策者

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

7、算机技术由此可见运筹学一门应用性很强的学科。特别是随着计算机技术的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越的不断发展，计算机成为运筹学最强有力的运算工具，运筹学越来越显示出其广泛的使用价值。显示出其广泛的使用价值。运筹学这一名词最早出现于运筹学这一名词最早出现于19381938年。当时英，美等国盟军在与德国年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如，防空雷达的布置问题：英美等国为了对付德国的空袭配备了先进的，防空雷达的布置问题：英美等国为了对付德国的空袭配备了先进的雷达作为防空

8、系统的一部分，但是由于雷达系统的布置不甚合理，通过雷达作为防空系统的一部分，但是由于雷达系统的布置不甚合理，通过防空演习发现实际效果并不理想，防空演习发现实际效果并不理想，护航舰队的编队问题：英美等国需要对本国的商船队配备护航舰队，护航舰队的编队问题：英美等国需要对本国的商船队配备护航舰队，以防止德国潜艇的攻击，这里有一个如何合理编队才能使商船队一旦遭以防止德国潜艇的攻击，这里有一个如何合理编队才能使商船队一旦遭受德国潜艇攻击时损失最少的问题。受德国潜艇攻击时损失最少的问题。为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家

9、，在三军组织了各种研究小组，研究的问题都是军事性质的，在英学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为国称为“Operational ResearchOperational Research”，其他英语国家称为，其他英语国家称为“Operations Operations ResearchResearch”，意思是军事行动研究。这些研究小组运用系统优化的思想，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。应用数学技术分析军事问题，取得了非常理想的效果。二次大战以后，在军事运筹小组中工作过的一部分科学家开始转二次大战以

10、后，在军事运筹小组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。统的研究上。19471947年美国数学家年美国数学家G.B.DantzigG.B.Dantzig在研究美国空军资源配置时在研究美国空军资源配置时,提出提出了求解线性规划的有效方法了求解线性规划的有效方法单纯形法。二十世纪五十年代初，应用单纯形法。二十世纪五十年代初，应用计算机求解线性规划获得成功。计算机求解线性规划获得成功。至五十年代末，一些工业先进国家的大型企业已经较普遍地使用至五十年代末，一些工业先进国家的大型企业

11、已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事业。业。同时同时很多国家成立了运筹学研究学会，很多国家成立了运筹学研究学会，一些大学的相关专业也陆一些大学的相关专业也陆续设置了运筹学的有关课程。专门发表运筹学研究论文的刊物开始出续设置了运筹学的有关课程。专门发表运筹学研究论文的刊物开始出版，运筹学的理论研究日趋成熟，在实际应用上则日趋广泛。版，运筹学的理论研究日趋成熟，在实际应用上则日趋广

12、泛。我国运筹学的研究始于五十年代中期，当时由钱学森教授将运筹学我国运筹学的研究始于五十年代中期，当时由钱学森教授将运筹学我国运筹学的研究始于五十年代中期，当时由钱学森教授将运筹学我国运筹学的研究始于五十年代中期，当时由钱学森教授将运筹学从西方国家引入我国，以华罗庚教授为首的一大批科学家在有关企事业从西方国家引入我国，以华罗庚教授为首的一大批科学家在有关企事业从西方国家引入我国，以华罗庚教授为首的一大批科学家在有关企事业从西方国家引入我国，以华罗庚教授为首的一大批科学家在有关企事业单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，

13、水利建设单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我国年轻的数学家管梅谷于国年轻的数学家管梅谷于国年轻的数学家管梅谷于国年轻的数学家管梅谷于19621962年首先提出的，在国际上统称为中国邮递年首先提出的，在国际上统称为中国邮递年首先提出的，在国际上统称为中国邮递年首先提

14、出的，在国际上统称为中国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。如今对运筹学的研究大致在三个领域发展：运筹学应用，运筹科学如今对运筹学的研究大致在三个领域发展：运筹学应用，运筹科学如今对运筹学的研究大致在三个领域发展：运筹学应用，运筹科学如今对运筹学的研究大致在三个领域发展：运筹学应用，运筹科学和运筹数学。一般的共识是，运筹学的研究不能忘记其原有的应用性强和运筹数学。一般的共识是，运筹

15、学的研究不能忘记其原有的应用性强和运筹数学。一般的共识是，运筹学的研究不能忘记其原有的应用性强和运筹数学。一般的共识是，运筹学的研究不能忘记其原有的应用性强的特色，必须强调多学科的交叉联系和解决实际问题的研究。我们面临的特色，必须强调多学科的交叉联系和解决实际问题的研究。我们面临的特色，必须强调多学科的交叉联系和解决实际问题的研究。我们面临的特色，必须强调多学科的交叉联系和解决实际问题的研究。我们面临的很多系统通常涉及到大量的经济，技术，社会，政治和心理等综合因的很多系统通常涉及到大量的经济，技术，社会，政治和心理等综合因的很多系统通常涉及到大量的经济，技术，社会，政治和心理等综合因的很多系统

16、通常涉及到大量的经济，技术，社会，政治和心理等综合因素，这些综合因素受到人的影响和干预，存在非结构性的复杂问题，仅素，这些综合因素受到人的影响和干预，存在非结构性的复杂问题，仅素，这些综合因素受到人的影响和干预，存在非结构性的复杂问题，仅素，这些综合因素受到人的影响和干预，存在非结构性的复杂问题，仅用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步，用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步，用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步，用数学模型是很难加以描述和解决的。总之随着社会的不断发展和进步，实践将对运筹学提出更新更多的研究课题，运筹学

17、正处于不断发展，不实践将对运筹学提出更新更多的研究课题，运筹学正处于不断发展，不实践将对运筹学提出更新更多的研究课题，运筹学正处于不断发展，不实践将对运筹学提出更新更多的研究课题，运筹学正处于不断发展，不断进步的时期。断进步的时期。断进步的时期。断进步的时期。问题的提出：问题的提出：在在生生产产管管理理的的经经营营活活动动中中，通通常常需需要要对对“有有限限的的资资源源”寻寻求求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达到最小。最佳：有一个标准或目标，使利润达到

18、最大或成本达到最小。有限资源的合理配置有两类问题有限资源的合理配置有两类问题l如何合理的使用有限的资源，使生产经营的效益达到最大；如何合理的使用有限的资源，使生产经营的效益达到最大；l在生产或经营的任务确定的条件下，合理的组织生产，安排经在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。营活动，使所消耗的资源数最少。线性规划问题及其数学模型线性规划问题及其数学模型 与规划问题有关的数学模型总有两部分组成：与规划问题有关的数学模型总有两部分组成：l约束条件：反映了有限资源对生产经营活动的种种约束，约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须

19、完成的任务；或者生产经营必须完成的任务；l目标函数：反映生产经营者在有限资源条件下希望达到目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。的生产或经营的目标。例，例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）3030202016016

20、0设备（台班）设备（台班）5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万元。但根据万元。但根据市场需求调查的结果，甲药品每周的产量不应超过市场需求调查的结果，甲药品每周的产量不应超过4 4吨。问该厂应如何安吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？排两种药品的产量才能使每周获得的利润最大？定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。目标：目标：使总利润使总利润 Z=5xZ=5x1 1+2x+2x2 2

21、极大化极大化 约束：约束：每周资源总量的限制，每周资源总量的限制，30 x30 x1 1+20 x+20 x2 2160160 5x5x1 1+x+x2 2 1515甲种药品每周产量不应超过甲种药品每周产量不应超过4 4吨的限制吨的限制 x x1 144计划生产数不可能是负数，计划生产数不可能是负数，x x1 10 x0 x2 200每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 5 数学模型为数学模型为 s.t.s.t.（subject to

22、)subject to)(such that)(such that)这是一个如何合理的使用有限的资源，使生产经营的效益达到最大这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。的数学规划问题。在满足一组约束条件的限制下，寻求决策变量在满足一组约束条件的限制下，寻求决策变量x x1 1，x x2 2的决策值，使目的决策值，使目标函数达到最大值。标函数达到最大值。每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 5例例：某某化

23、化工工厂厂根根据据一一项项合合同同要要求求为为用用户户生生产产一一种种用用甲甲、乙乙两两种种原原料料混混合合配配制制而而成成的的特特种种产产品品。已已知知甲甲、乙乙两两种种原原料料都都含含有有A A、B B、C C三三种种化化学学成成分分，两两种种原原料料分分别别所所含含三三种种化化学学成成分分的的百百分分比比含含量量，以以及及按按合合同规定的产品中三种化学成分的最低含量如下表所示：同规定的产品中三种化学成分的最低含量如下表所示：已已知知甲甲、乙乙两两种种原原料料的的成成本本分分别别是是每每公公斤斤3 3元元和和2 2元元，厂厂方方希希望望总成本达到最小，问如何配置该产品？总成本达到最小，问如

24、何配置该产品？原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化学成分化学成分定义定义x x1 1，x x2 2分别为每公斤产品中甲，乙两种原料的数量，分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本目标：使总成本 Z=3xZ=3x1 1+2x+2x2 2 极小化极小化 约束：配料平衡条件，约束：配料平衡条件，x x1 1+x+x2 2=1=1产品中产品中A A、B B、C C三种化学成分的最低含量三种化学成分的最低含量 12x12x1 1+3x+3x2 24

25、4 2x2x1 1+3x+3x2 222 3x3x1 1+15x+15x2 255非负性条件非负性条件 x x1 10,x0,x2 200 原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分 数学模型：数学模型：s.t.s.t.这是一个原料配制问题，是在生产任务确定的条件下，合理的组织这是一个原料配制问题，是在生产任务确定的条件下，合理的组织 生产，使所消耗的资源数最少的数学规划问题。生产，使所消耗的资源数最少的数学规划问题

26、。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1 1和和x x2 2的值使目标函数取得最小的值使目标函数取得最小 值。值。原料原料化学成分含量（化学成分含量（%）产品中化学成分的最低含量产品中化学成分的最低含量（%）甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分例例，某某铁铁器器加加工工厂厂要要制制作作100100套套钢钢架架，每每套套要要用用长长为为2.92.9米米，2.12.1米米和和1.51.5米米的的圆圆钢钢各各一一根根。已已知知原原料料长长为为7.47.4米米，问问应应如如何何

27、下下料料，可可使使材材料最省？料最省？分分析析：在在长长度度确确定定的的原原料料上上截截取取三三种种不不同同规规格格的的圆圆钢钢，可可以以归归纳纳出出8 8种不同的下料方案：种不同的下料方案：圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.1.1.41.4 问题归纳为如何混合使用这问题归纳为如何混合使用这8 8种不同的下料方案，来制造种不同的下料方案，来制

28、造100100套套钢架，且要使剩余的料头总长为最短。钢架，且要使剩余的料头总长为最短。设设x xj j表示用第表示用第j j种下料方案下料的原料根数，种下料方案下料的原料根数，j=1,2j=1,28,8,目标：使料头总长度目标：使料头总长度Z=0.1xZ=0.1x2 2+0.2x+0.2x3 3+0.3x+0.3x4 4+0.8x+0.8x5 5+0.9x+0.9x6 6+1.1x+1.1x7 7+1.4x+1.4x8 8极小化极小化约束：三种规格圆钢根数约束：三种规格圆钢根数 x x1 1+2x+2x2 2+x+x4 4+x+x6 6=100=100 2x2x3 3+2x+2x4 4+x+x

29、5 5+x+x6 6+3x+3x7 7=100=100 3x 3x1 1+x+x2 2+2x+2x3 3+3x+3x5 5+x+x6 6+4x+4x8 8=100=100非负取整条件非负取整条件 x xj j0(j=1,20(j=1,28)8)且取整数且取整数圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30.30.80.80.90.91.1.1.41.4 数学模型数学模型 s.t.s.t

30、.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1 1至至x x8 8的值的值,使目标函数取得最使目标函数取得最 小值。小值。圆钢（米）圆钢（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料头（米）料头（米）0 00.10.10.20.20.30

31、.30.80.80.90.91.11.11.41.4且为整数且为整数n 线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1 1）用一组决策变量）用一组决策变量x x1 1，x x2 2，x xn n表示某一方案，且在一般情况下，表示某一方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2 2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3 3）存在若干个约束条件，约束条件用决策变量的线性等式或线）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。性不等

32、式来表达。（4 4）要求目标函数实现极大化（）要求目标函数实现极大化（maxmax）或极小化（）或极小化（minmin）。）。满足上述满足上述4 4个特征的规划问题称为线性规划问题个特征的规划问题称为线性规划问题 线性规划的模型的一般形式线性规划的模型的一般形式:目标函数目标函数 满足约束条件满足约束条件 通常称通常称 为决策变量，为决策变量，为价值系数，为价值系数，为消耗系数为消耗系数,为资源限制系数。为资源限制系数。线性规划的图解法线性规划的图解法 适用于求解两个变量的线性规划问题适用于求解两个变量的线性规划问题n 图解法的基本步骤图解法的基本步骤例例4,4,利用例利用例1 1说明图解法的

33、主要步骤，说明图解法的主要步骤，例例1 1的数学模型为的数学模型为 s.t.O51015x1x1=4x25101AB(2,5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5 线性规划图解法的基本步骤：线性规划图解法的基本步骤：（1 1）建立以）建立以x x1 1,x,x2 2为坐标轴的直角坐标系，画出线性规划为坐标轴的直角坐标系，画出线性规划 问题的可行域问题的可行域,（2 2）求目标函数）求目标函数 Z=CZ=C1 1x x1 1+C+C2 2x x2 2 的梯度的梯度Z=Z=（c c1 1,c,c2 2）,（3 3）任取等值线）任取等值线 C C1 1x x1 1+

34、C+C2 2x x2 2=Z=Z0 0,沿梯度沿梯度Z Z正方向平移正方向平移,（若是极小化问题，则沿负梯度方向（若是极小化问题，则沿负梯度方向-Z-Z平移），平移），求等直线将离未离可行域时与可行域的交点。求等直线将离未离可行域时与可行域的交点。（4 4）若交点存在，则该点坐标就是最优解）若交点存在，则该点坐标就是最优解 。n 图解法的几种可能结果图解法的几种可能结果 (1(1）有唯一最优解，如例）有唯一最优解，如例1 1。（2 2）有无穷多最优解）有无穷多最优解 如例如例1 1中的目标函数设为中的目标函数设为 maxZ=10 xmaxZ=10 x1 1+2x+2x2 2 则目标函数等值线则

35、目标函数等值线10 x10 x1 1+2x+2x2 2=Z=Z 与第二约束与第二约束 5x5x1 1+x+x2 21515 的边界线平行。将等值线沿梯度的边界线平行。将等值线沿梯度Z=Z=（1010，2 2）正方向平移）正方向平移 至至B B点时与可行域点时与可行域OABCOABC的整条边界线的整条边界线ABAB重合。重合。这表明线段这表明线段ABAB上的每一点都使目标函数取得同样的最大值，上的每一点都使目标函数取得同样的最大值，因而都是最优解。因而都是最优解。O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5例例5 5

36、，试用图解法求解下列线性规划问题试用图解法求解下列线性规划问题 st.（3 3）无界解（或称无最优解）无界解（或称无最优解）无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值若是极大化问题，则可使目标函数值Z+,Z+,极小化问题极小化问题 则可使目标函数值则可使目标函数值Z-Z-，有无界解的线性规划问题的可行域通常是无界区域，但反之则有无界解的线性规划问题的可行域通常是无界区域，但反之则不必然。不必然。-1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O33（4 4）无可行解）无可行解 某些线性规划问题的可行域

37、是空集，既不存在满足所有约束条某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求，在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。既不存在可行方案。标准线性规划模型标准线性规划模型 线性规划问题的标准形式：线性规划问题的标准形式：s.t s.t 其中其中(1.1)(1.1)为目标函数，为目标函数，(1.2)(1.2)为约束条件，为约束条件，(1.3)(1.3)为非负条件，为非负条件，为称呼方便，有时将为称呼方便，有时

38、将(1.3)(1.3)也称为约束条件。也称为约束条件。（1.21.2）（1.31.3）线性规划的标准形式线性规划的标准形式（1.11.1）（一）、整数规划问题实例（一）、整数规划问题实例 例一、合理下料问题例一、合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A1,A2,Am 的毛坯。在一根圆钢的毛坯。在一根圆钢上下料的方式有上下料的方式有B1,B2,Bn 种，每种下料方式可以得到各种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少样安排下料方式，使得即满足需要

39、，所用的原材料又最少？零件方个数式零件零件毛坯数二、整数规划的模型二、整数规划的模型 设：设：xj 表示用表示用Bj(j=1.2n)种方式下料根数种方式下料根数 模型：模型：例二、例二、某公司计划在某公司计划在m个地点建厂，可供选择的地点有个地点建厂，可供选择的地点有A1,A2Am，他们的生产能力分别是他们的生产能力分别是a1,a2,am（假设生（假设生产同一产品）。第产同一产品）。第i i个工厂的建设费用为个工厂的建设费用为fi(i=1.2m),又有又有n个地点个地点B1,B2,Bn 需要销售这种产品，其销量分需要销售这种产品，其销量分别为别为b1.b2bn。从工厂运往销地的单位运费为。从工

40、厂运往销地的单位运费为Cij。试。试决定应在哪些地方建厂，即满足各地需要，又使总建决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？设费用和总运输费用最省？单 销地厂址 价生产能力建设费用销量 设：设：xij 表示从工厂运往销地的运量表示从工厂运往销地的运量(i=1.2m、j=1.2n),1),1 在在Ai建厂建厂 又设又设 Yi （i=1.2m）0 0 不在不在Ai建厂建厂 模型：模型：序号序号序号序号1 12 23 34 45 56 67 7物品物品物品物品 食品食品食品食品 氧气氧气氧气氧气 冰镐冰镐冰镐冰镐 绳索绳索绳索绳索 帐篷帐篷帐篷帐篷 相机相机相机相机 设备

41、设备设备设备重量重量重量重量5 55 52 26 612122 24 4重要重要重要重要系数系数系数系数20201515181814148 84 41010 一登山队员做登山准备，他需要携带的物品有：食一登山队员做登山准备，他需要携带的物品有：食一登山队员做登山准备，他需要携带的物品有：食一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带种物品的重要性系数和重量如

42、下：假定登山队员可携带种物品的重要性系数和重量如下：假定登山队员可携带种物品的重要性系数和重量如下：假定登山队员可携带最大重量为最大重量为最大重量为最大重量为25252525公斤。公斤。公斤。公斤。解：解：解：解：如果令如果令如果令如果令x xi i=1=1表示登山队员携带物品表示登山队员携带物品表示登山队员携带物品表示登山队员携带物品i i，x xi i=0=0表示表示表示表示登山队员不携带物品登山队员不携带物品登山队员不携带物品登山队员不携带物品i i，则问题表示成，则问题表示成，则问题表示成，则问题表示成0-10-1规划规划规划规划:Max Z=20 xMax Z=20 x1 1+15x

43、+15x2 2+18x+18x3 3+14x+14x4 4+8x+8x5 5+4x+4x6 6+10 x+10 x7 7s.t.5xs.t.5x1 1+5x+5x2 2+2x+2x3 3+6x+6x4 4+12x+12x5 5+2x+2x6 6+4x+4x7 7 2525 x xi i=1=1或或或或x xi i=0 i=1,2,.7=0 i=1,2,.7例例例例 背包问题背包问题背包问题背包问题(Knapsack Problem)(Knapsack Problem)(Knapsack Problem)(Knapsack Problem)一个旅行者一个旅行者一个旅行者一个旅行者,为了准备旅行的

44、必须用品为了准备旅行的必须用品为了准备旅行的必须用品为了准备旅行的必须用品,要在背包内装一些要在背包内装一些要在背包内装一些要在背包内装一些最有用的东西最有用的东西最有用的东西最有用的东西,但有个限制但有个限制但有个限制但有个限制,最多只能装最多只能装最多只能装最多只能装b b b b公斤的物品公斤的物品公斤的物品公斤的物品,而每件物而每件物而每件物而每件物品只能整个携带品只能整个携带品只能整个携带品只能整个携带,这样旅行者给每件物品规定了一个这样旅行者给每件物品规定了一个这样旅行者给每件物品规定了一个这样旅行者给每件物品规定了一个“价值价值价值价值”以表示其有用的程度以表示其有用的程度以表示

45、其有用的程度以表示其有用的程度,如果共有如果共有如果共有如果共有n n n n件物品件物品件物品件物品,第第第第j j j j件物品件物品件物品件物品a a a aj j j j公斤公斤公斤公斤,其其其其价值为价值为价值为价值为c c c cj j j j.问题变成问题变成问题变成问题变成:在携带的物品总重量不超过在携带的物品总重量不超过在携带的物品总重量不超过在携带的物品总重量不超过b b b b公斤条件下公斤条件下公斤条件下公斤条件下,携带哪些物品携带哪些物品携带哪些物品携带哪些物品,可使总价值最大可使总价值最大可使总价值最大可使总价值最大?解：解：解：解：如果令如果令如果令如果令x xj

46、 j=1=1表示携带物品表示携带物品表示携带物品表示携带物品j j，x xj j=0=0表示不携带物品表示不携带物品表示不携带物品表示不携带物品j j，则，则，则，则问题表示成问题表示成问题表示成问题表示成0-10-1规划规划规划规划:Max Z=Max Z=c cj jx xj j s.t.a s.t.aj jx xj j b b x xj j=0 =0 或或或或1 1（二）、整数规划的数学模型（二）、整数规划的数学模型一般形式一般形式 依照决策变量取整要求的不同，整数规划可分为纯整依照决策变量取整要求的不同，整数规划可分为纯整数规划、全整数规划、混合整数规划、数规划、全整数规划、混合整数规

47、划、0 01 1整数规划。整数规划。纯整数规划：纯整数规划：所有决策变量要求取非负整所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要数（这时引进的松弛变量和剩余变量可以不要求取整数）。求取整数）。全整数规划：全整数规划：除了所有决策变量要求取非负除了所有决策变量要求取非负整数外，系数整数外，系数aij和常数和常数bi也要求取整数（这时引也要求取整数（这时引进的松弛变量和剩余变量也必须是进的松弛变量和剩余变量也必须是 整数）。整数）。混合整数规划：混合整数规划：只有一部分的决策变量要只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。求取非负整数，另一部分可以取非负实数。

48、01整数规划：整数规划：所有决策变量只能取所有决策变量只能取 0 或或 1 两个整数两个整数。（三）、整数规划与线性规划的关系（三）、整数规划与线性规划的关系 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。至不能保证

49、所得倒的解是整数可行解。0-1规划规划一些变量的取值被限定为一些变量的取值被限定为0或或1。整数规划的特例。整数规划的特例。0-1规划的一般模型：规划的一般模型：s.t.Xj=0,1 j=1,2,n （X=0,1 等价于等价于 X1,X0 且取整数。）且取整数。）0-1规划问题求解要求：软件求解。规划问题求解要求：软件求解。在实际中经常会遇到这样的问题，有在实际中经常会遇到这样的问题，有n 项不同的任务，项不同的任务，需要需要n 个人分别完成其中的一项，但由于任务的性质和个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率各人的专长不同，因此各人去完成不同的

50、任务的效率（或花费的时间或费用）也就不同。于是产生了一个（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成问题，应指派哪个人去完成哪项任务，使完成 n 项任项任务的总效率最高（或所需时间最少），这类问题称为务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。指派问题或分派问题。（一）、指派问题的数学模型（一）、指派问题的数学模型 设设n 个人被分配去做个人被分配去做n 件工作，规定每个人只做一件件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第工作，每件工作只有一个人去做。已知第I 个人去做第个人去做第j 件工作的的效率（件工作的的