《运筹学》全册配套完整教学课件3.pptx

1、运筹学运筹学全册配运筹学全册配套完整教学课件套完整教学课件32v 运筹学运筹学，清华大学出版社，清华大学出版社(比较经典比较经典,经常作为考试经常作为考试用书用书)v David et al. 数据、模型与决策数据、模型与决策，机械工业出版社，机械工业出版社，2004v 管理运筹学管理运筹学，高等教育出版社，高等教育出版社 韩伯棠韩伯棠v 韩大卫韩大卫 ，管理运筹学管理运筹学，大连理工大学出版社，大连理工大学出版社，200231.成绩评定及考核方法成绩评定及考核方法(考试课程考试课程)v 平时作业平时作业(10)v 考勤考勤(10)v 课堂成绩及学习态度课堂成绩及学习态度(10)v 大作业或课

2、堂测验大作业或课堂测验(70)2.成绩评定及考核方法成绩评定及考核方法(考查课程考查课程)v 平时作业平时作业(20)v 课堂成绩及考勤课堂成绩及考勤(20)v 大作业或课堂测验大作业或课堂测验(60)4v 20世纪世纪40年代诞生于英美年代诞生于英美v 1940年，英国为对付德国空军的空袭，使用了雷达，但年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好，为解决这个问题，成立了运没有科学布局，效果不好，为解决这个问题，成立了运筹学小组。称为筹学小组。称为Operational Research，意为作战研究。，意为作战研究。 v 美国和加拿大也在军队设立了运筹学小组，称之为美

3、国和加拿大也在军队设立了运筹学小组，称之为Operations Research，协助指挥官研究战略及战术问题。，协助指挥官研究战略及战术问题。v 战后许多从事运筹学研究的科学家转向了民用问题的研战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。究，使运筹学在企业管理方面的应用得到了长足进展。 一、运筹学的发展历史一、运筹学的发展历史5 英文：英文： Operations Research 缩写：缩写： ORv 日本译作日本译作“运用学运用学”，v 香港、台湾译为香港、台湾译为“作业研究作业研究”，v 我国学者从古语我国学者从古语“运筹帷幄之中，决

4、胜千里之外运筹帷幄之中，决胜千里之外”取取“运筹运筹”二字，充分体现了这门学科运心筹谋、二字，充分体现了这门学科运心筹谋、策略取胜的精髓。译作策略取胜的精髓。译作“运筹学运筹学”。v Management Science 管理科学管理科学二、运筹学的称谓二、运筹学的称谓 6v 运筹学在国外也被当作管理科学运筹学在国外也被当作管理科学v 管理科学是对与定量因素有关的管理问题通过应用科学管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。的方法进行辅助管理决策的一门学科。 管理者管理者 制定决策制定决策 管理科学管理科学 运用合理的分析来改善决策的制定运用合理的分析来

5、改善决策的制定v 定量分析在组织决策中的位置定量分析在组织决策中的位置三、运筹学的学科性质三、运筹学的学科性质组织中存组织中存在的问题在的问题定性分析定性分析定量分析定量分析评价与评估评价与评估决策决策7v 科学的方法科学的方法三、运筹学的学科性质三、运筹学的学科性质(续续)问题的确定结果分析实施方案分析问题建立模型软件求解确定解决方案8v 运筹学是用数量方法研究管理系统最优化问题的学科。运筹学是用数量方法研究管理系统最优化问题的学科。 是一门应用学科，实用性强是一门应用学科，实用性强 。 对经济管理系统中人力、物力、财力等资源进行统对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者

6、提供有依据的最优方案，以实现筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。最有效的管理。 是是“科学的科学的”、“量化的量化的”、“决策决策”方法。方法。三、运筹学的学科性质三、运筹学的学科性质(续续)9四、工作程序四、工作程序 v 提出问题提出问题 弄清要解决的问题弄清要解决的问题 明确实现目标明确实现目标 分析所处的环境和约束条件分析所处的环境和约束条件 取得统计数据资料取得统计数据资料v 建立数学模型建立数学模型 确定决策变量确定决策变量 建立目标函数建立目标函数 构造约束方程构造约束方程v 问题求解问题求解v 解的评价解的评价v 决策与实施决策与实施提出问题提出问题建立模型

7、建立模型求解求解评价决策实施评价决策实施10结论决策执行结果管理者信息收集模型反馈运筹学方法的求解过程运筹学方法的求解过程11五、管理运筹学模型五、管理运筹学模型 v 运筹学使用的主要是数学模型和模拟模型运筹学使用的主要是数学模型和模拟模型 v 数学模型：用数学符号建立的、用以描述客观事物特征数学模型：用数学符号建立的、用以描述客观事物特征及其内在联系的模型。及其内在联系的模型。 变量描述：可控变量变量描述：可控变量xi ，已知参数，已知参数rj， 随机因素随机因素k 目标函数：目标函数：Z=f(xi, rj,k) 约束条件：约束条件：g(xi, rj,k)(,)0 v 模型说明：模型说明：

8、目标函数可以是单目标，也可以是多目标；目标可目标函数可以是单目标，也可以是多目标；目标可以是极大，也可以是极小。以是极大，也可以是极小。 约束条件可以是单个，也可以是多个。约束条件可以是单个，也可以是多个。 不包含随机因素时为确定性模型，有随机因素时为不包含随机因素时为确定性模型，有随机因素时为随机性模型；随机性模型； 当变量只取离散数值时为离散模型，否则为连续模当变量只取离散数值时为离散模型，否则为连续模型。型。12v 规划论规划论 线性规划（运输问题）线性规划（运输问题） 整数规划整数规划 目标规划目标规划 非线性规划非线性规划 动态规划动态规划 v 图与网络图与网络v 存储论存储论v 决

9、策论决策论v 对策论对策论v 排队论排队论六、运筹学学科体系六、运筹学学科体系 13七、运筹学的地位七、运筹学的地位 14v 生产计划：生产作业的计划、日程表的编排、合理下料、配料生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等问题、物料管理等v 库存管理：库存控制策略、仓储选址等库存管理：库存控制策略、仓储选址等v 运输问题：成本最小的运输线路、物流配送优化、运输工具的运输问题：成本最小的运输线路、物流配送优化、运输工具的调度、物流设施选址等调度、物流设施选址等v 人事管理：人员需求预测、确定人员编制、人员合理分配、人人事管理：人员需求预测、确定人员编制、人员合理分配、

10、人才评价才评价v 市场营销：广告预算、媒介选择、产品定价、产品开发与销售市场营销：广告预算、媒介选择、产品定价、产品开发与销售计划等计划等v 财务和会计：预测、贷款、成本分析、定价、投资分析、现金财务和会计：预测、贷款、成本分析、定价、投资分析、现金管理等管理等v 设备维修与更新设备维修与更新v 项目选择、评价，工程优化设计与管理等项目选择、评价，工程优化设计与管理等八、运筹学在工商管理中的应用八、运筹学在工商管理中的应用15九、运筹学学习的特点九、运筹学学习的特点v 要把重点放在结合实际的应用上，不要被一些概念、理要把重点放在结合实际的应用上，不要被一些概念、理论的困难吓倒，要用好计算机这个

11、强有力的工具。论的困难吓倒，要用好计算机这个强有力的工具。v 要充分发挥自己管理实践经验丰富和理论联系实际能力要充分发挥自己管理实践经验丰富和理论联系实际能力强的优势。强的优势。v 要把注意力放在要把注意力放在“入口入口”和和“出口出口”两头，中间过程尽两头，中间过程尽可能让计算机软件去完成：可能让计算机软件去完成： 入口即结合实际问题建立管理优化模型；入口即结合实际问题建立管理优化模型； 出口即解决问题的方案或模型的解的分析与应用。出口即解决问题的方案或模型的解的分析与应用。v 充分借用管理运筹学教学软件。充分借用管理运筹学教学软件。16十、关于运筹学软件十、关于运筹学软件 目前国内外各种版

12、本的运筹学软件很多。到目前为止，还没目前国内外各种版本的运筹学软件很多。到目前为止，还没有一种软件包将运筹学的所有计算都包含其中，只能根据不同有一种软件包将运筹学的所有计算都包含其中，只能根据不同内容使用不同的软件。本课程主要介绍内容使用不同的软件。本课程主要介绍WinQSB软件，该软件软件，该软件包含了运筹学的大部分计算，具体应用各章都有详细介绍。包含了运筹学的大部分计算，具体应用各章都有详细介绍。 其它软件如其它软件如excel、matlab也可以进行运筹学相关计算。也可以进行运筹学相关计算。 运筹学运运 筹筹 学学运筹学运筹学Operations ResearchChapter 1 线性

13、规划线性规划Linear Programming1.1 LP的数学模型的数学模型 Mathematical Model of LP1.2 图解法图解法 Graphical Method1.3 标准型标准型 Standard form of LP1.4 基本概念基本概念 Basic Concepts1.5 单纯形法单纯形法 Simplex Method1.1 数学模型数学模型 Mathematical Model 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 线性规划通常研究资源的最优利用、设备最佳运行等问线性规划通常研究资源的最优利用、设备最佳

14、运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源排，用最少的资源 （如资金、设备、原标材料、人工、时（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品限制下，如何组织安排生产获得最好的经济效益（如产品量最多量最多 、利润最大）。、利润最大）。线性规划线性规划（Linear Programming,缩写为LP）是运筹学的重要是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助

15、分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。计算机，使得计算更方便，应用领域更广泛和深入。【例例1.1】最优生产计划问题。某企业在计划期内计划生产甲、最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需上加工，需要消耗材料要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表工及所需要的资源如表1.1所示。已知在计划期内设备的加工能所示。已知在计划期内设备的加工能力各为力各为200台时，可供材

16、料分别为台时，可供材料分别为360、300公斤；每生产一件甲、公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为乙、丙三种产品，企业可获得利润分别为40、30、50元，假定元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？计划期内总的利润收入最大？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.1.1 应用模型举例应用模型举例 产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C

17、 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件） 40 30 50表表1.1 产品资源消耗产品资源消耗1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【解解】设设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为：1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 产品产品 资源资源 甲甲 乙乙 丙丙现有资现有资源源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5

18、300利润（元利润（元/件）件） 40 30 50最优解最优解X=(50,30,10);Z=3400线性规划的数学模型由线性规划的数学模型由决策变量决策变量 Decision variables 目标函数目标函数Objective function及约束条件及约束条件Constraints构成。称为三个要素构成。称为三个要素。n其特征是：其特征是：n1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n2解决问题的解决问题的是一组多个决策变量是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样

19、辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【例例1.2】某商场决定：营业员每周连续工作某商场决定：营业员每周连续工作5天后连续休息天后连续休息2天，天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示。表表1.2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。 星期星期需要人数需要人数星期星期需要人数需要人数一一30

20、0五五480二二300六六600三三350日日550四四4001.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【解解】 设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上班天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为的营业员，则这个问题的线性规划模型为 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四4001 1X1X10 0C1C1404404=3003001

21、041042 2X2X26767C2C2301301=3003001 13 3X3X3146146C3C3350350=3503500 04 4X4X4170170C4C4400400=4004000 05 5X5X59797C5C5480480=4804800 06 6X6X6120120C6C6600600=6006000 07 7X7X71717C7C7550550=5505500 0最优解：最优解：Z617（人）（人）【例例1.3】合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是些轴的规格分别是1.5，

22、1，0.7（m），），这些轴需要用同一种圆钢来做，圆钢长这些轴需要用同一种圆钢来做，圆钢长度为度为4 m。现在要制造。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？ 【解解】这是一个条材下料问题这是一个条材下料问题 ，设切口宽度为零。，设切口宽度为零。 设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式1.5y1+y2+0.7y34表示，求这个不等式关于表示，求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解。象这样的非负整数解共有的非负

23、整数解共有10组，也就是有组，也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。表表13 下料方案下料方案 方案方案规格规格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP设设xj(j=1,2,10)为第为第j种下料方案所用圆钢的根数。则用料最少种下料方案所用圆钢的根数。则用料最少数学模型数学模型求下料

24、方案时应注意，余料不能超过最短毛坯的长度；最好将毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案的，最后切割最短的，不能遗漏了方案 。如果方案较多，用计。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。算机编程排方案，去掉余料较长的方案，进行初选。102 , 1, 010005423210002342100022min10987542987643154321101，jxxxxxxxxxxxxxxxxxxxxxZjjj1.1

25、线性规划的数学模型线性规划的数学模型 Mathematical Model of LP 方案方案规格规格 1234 5678910需求量需求量y1(根根) 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.51 1 X1X15005002 2 X2X20 03 3 X3X30 04 4 X4X40 05 5 X5X50 06 6 X6X662.562.57 7 X7X70 08 8 X8X80 09 9 X9X92502501010 X10X100 0Z812.

26、5【例例1.4】配料问题。某钢铁公司生产一种合金，要求的成分规格配料问题。某钢铁公司生产一种合金，要求的成分规格是：锡不少于是：锡不少于28%，锌不多于，锌不多于15%，铅恰好，铅恰好10%，镍要界于，镍要界于35%55%之间，不允许有其他成分。钢铁公司拟从五种不同级之间，不允许有其他成分。钢铁公司拟从五种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表别的矿石中进行冶炼，每种矿物的成分含量和价格如表1.4所示。所示。矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数矿石杂质在治炼过程中废弃，现要求每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，合金含量没有发生变化。量。假设矿石

27、在冶炼过程中，合金含量没有发生变化。表表1.4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t ）1251010253034024000303026030155206018042020040202305851517551901.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP解解: 设设xj（j=1,2，5）是第是第j 种矿石数量，得到下列线性规划模种矿石数量，得到下列线性规划模型型 注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考

28、虑进去，有可能是非线性关系。配料问题也称配方问题、变化考虑进去，有可能是非线性关系。配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。营养问题或混合问题，在许多行业生产中都能遇到。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t ）1251010253034024000303026030155206018042020040202305851517551901 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.5

29、8335 5 X5X50.66670.6667最优解：最优解：Z=347.51.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【例例1.5】投资问题。某投资公司在第一年有投资问题。某投资公司在第一年有200万元资金，每年都有如下的万元资金，每年都有如下的投资方案可供考虑采纳：投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继假使第一年投入一笔资金，第二年又继续投入此资金的续投入此资金的50%，那么到第三年就可回收第一年投入资金的一，那么到第三年就可回收第一年投入资金的一倍金额倍金额”。投资公司决定最优的投资策略使第六年所掌握的资金最。投资公司

30、决定最优的投资策略使第六年所掌握的资金最多。多。第五年：第五年：(x7/2+x9)=x8+2x5第一年：第一年：x1+x2=200(万元万元)第二年：第二年：(x1/2 +x3)+x4=x2第三年第三年(x3/2+x5)+x6=x4+2x1第四年：第四年：(x5/2+x7)+x8=x6+2x3到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型整理后得到下列线性规划模型 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP【解解】设设 x1：第一年的投资；第一年的投资； x2：第一年的保留资金第一年的保留资金 x3：第二

31、年新的投资；第二年新的投资；x4：第二年的保留资金第二年的保留资金 x5：第三年新的投资；：第三年新的投资； x6：第三年的保留资金第三年的保留资金 x7：第四年新的投资第四年新的投资 x8：第四年的保留资金第四年的保留资金 x9：第五年的保留资金第五年的保留资金 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1 1X1X155.284655.28462 2X2X2144.7155144.71553 3X3X3117.0732117.07324 4X4X40 05 5X5X552.032552.03256 6X6X60 07 7X7X7208.1

32、301208.13018 8X8X80 09 9X9X90 0最优解：最优解：Z 416.26万元万元x1：第一年的投资；第一年的投资； x2：第一年的保留资金第一年的保留资金 x3：第二年新的投资；第二年新的投资；x4：第二年的保留资金第二年的保留资金 x5：第三年新的投资；：第三年新的投资； x6：第三年的保留资金第三年的保留资金 x7：第四年新的投资第四年新的投资 x8：第四年的保留资金第四年的保留资金 x9：第五年的保留资金第五年的保留资金 【例例1.6】均衡配套生产问题。某产品由均衡配套生产问题。某产品由2件甲、件甲、3件乙零件组装而成。件乙零件组装而成。两种零件必须经过设备两种零件

33、必须经过设备A、B上加工，每件甲零件在上加工，每件甲零件在A、B上的加工时上的加工时间分别为间分别为5分钟和分钟和9分钟，每件乙零件在分钟，每件乙零件在A、B上的加工时间分别为上的加工时间分别为4分分钟和钟和10分钟。现有分钟。现有2台设备台设备A和和3台设备台设备B，每天可供加工时间为每天可供加工时间为8小时。小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的小时。怎样安排设备的加工时间使每天产品的产量最大。产量最大。【解解】 设设x1

34、、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是设备设备A、B每天加工工时的约束为每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约小时的约束为束为 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP目标函数线性化。产品的产量目标函数线性化。产品的产量y等价于等价于整理得到线性规划模型整理得到线性规划模型 约束线性化。将绝对值约束写成两个不等式约束线性化。将绝对值约束写成两个不等式1.1 线性规划的数学模型线性规划的数学模型 Ma

35、thematical Model of LP121212121212m a x1213549 6 091 01 4 4 0466 0466 00Zyyxyxxxxxxxxxyxx、1.1.2 线性规划的一般模型线性规划的一般模型一般地，假设线性规划数学模型中，有一般地，假设线性规划数学模型中，有m个约束，有个约束，有n个决策变量个决策变量xj, j=1,2,n，目标函数的变量系数用目标函数的变量系数用cj表示表示, cj称为称为价值系数价值系数。约。约束条件的变量系数用束条件的变量系数用aij表示，表示，aij称为称为工艺系数工艺系数。约束条件右端的。约束条件右端的常数用常数用bi表示，表示，

36、bi称为称为资源限量资源限量。则线性规划数学模型的一般表达。则线性规划数学模型的一般表达式可写成式可写成为了书写方便，上式也可写成：为了书写方便，上式也可写成： 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP在实际中一般在实际中一般xj0,但有时但有时xj0或或xj无符号限制。无符号限制。1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1.什么是线性规划，掌握线性规划在管理中的什么是线性规划，掌握线性规划在管理中的几个应用例子几个应用例子2.线性规划数学模型的组成及其特征线性规划数学模型的组成及其特征

37、3.线性规划数学模型的一般表达式。线性规划数学模型的一般表达式。作业：教材作业：教材P31 T 2，3，4，5，61.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP下一节：图解法下一节：图解法1.2 图解法图解法 Graphical Method图解法的步骤：图解法的步骤：1.求可行解集合。求可行解集合。分别求出满足每个约束包括变量非分别求出满足每个约束包括变量非 负要求负要求的区域，其交集就是可行解集合，或称为的区域，其交集就是可行解集合，或称为可行域可行域；2.绘制目标函数图形。绘制目标函数图形。先过原点作一条矢量指向点（先过原点作一条矢量指向点

38、（c1,c2)，矢矢量的方向就是目标函数增加的方向，称为梯度方向，再作一量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。求最优解。依据目标函数求最大或最小移动目标函数直线，依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是直线与可行域相交的点对应的坐标就是最优解。最优解。一般地，将目标函数直线放在可行域中一般地，将目标函数直线放在可行域中 求最大值时直线沿着矢量方向移动求最大值时直线沿着矢量方向移动 求最小值时沿着矢量的反方向移动求最小值时沿着矢量的反方向移动

39、1.2 图解法图解法The Graphical Methodx1x2O1020304010203040(3,4)(15,10)最优解最优解X=(15,10)最优值最优值Z=85例例1.71.2 图解法图解法The Graphical Method246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)min Z=x1+2x2例例1.8(1,2)1.2 图解法图解法The Graphical Method246x1x2246X（2）（3,1）X（1）（1,3）(5,5)min Z=5x1+5x2例例1.9有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 0

40、1 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) 1.2 图解法图解法The Graphical Method246x1x2246(1,2)无界解无界解(无最优解无最优解)max Z=x1+2x2例例1.10 x1x2O10203040102030405050无无可行解可行解即无最优解即无最优解max Z=10 x1+4x2例例1.111.2 图解法图解法The Graphical Method由由以上例题可知，线性规划的解有以上例题可知，线性规划的解有4种形式种形式：1.有唯一最优解有唯一最优解(例例1.7例例1.8)2.有多重解有多重解(例例1.9)3.

41、有无界解有无界解(例例1.10)4.无可行解无可行解(例例1.11)1、2情形为有最优解情形为有最优解3、4情形为无最优解情形为无最优解1.2 图解法图解法The Graphical Method1.通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式2.作图的关键有三点作图的关键有三点 (1)可行解区域要画正确可行解区域要画正确 (2)目标函数增加的方向不能画错目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动目标函数的直线怎样平行移动作业：教材作业：教材P34 T7 1.2 图解法图解法The Graphical Method下一节：线性规划的标准型下一节：线

42、性规划的标准型1.3 线性规划的标准型线性规划的标准型Standard form of LP 在用单纯法求解线性规划问题时，为了讨论问题在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。方便，需将线性规划模型化为统一的标准形式。1.3 线性规划的标准型线性规划的标准型Standard form of LP线性规划问题的标准型为线性规划问题的标准型为:1目标函数求最大值（或求最小值）目标函数求最大值（或求最小值）2约束条件都为等式方程约束条件都为等式方程3变量变量xj非负非负4常数常数bi非负非负max(或min)Z=c1x1+c2x2+cnxn1.3 线性规划

43、的标准型线性规划的标准型Standard form of LP注：本教材默认目标函数是注：本教材默认目标函数是 max或写成下列形式或写成下列形式： 或用矩阵形式或用矩阵形式1.3 线性规划的标准型线性规划的标准型Standard form of LP通常通常X记为：记为： 称为约束方称为约束方程的系数矩阵，程的系数矩阵，m是约束方程的个数，是约束方程的个数，n是决策变量的个数，是决策变量的个数，一般情况一般情况mn，且，且r()m。其中其中:1.3 线性规划的标准型线性规划的标准型Standard form of LP【例例1.12】将下列线性规划化为标准型将下列线性规划化为标准型 【解解】

44、（）因为（）因为x3无符号要求无符号要求 ，即，即x3取正值也取正值也可取负值，标准型中要求变量非负，所以令可取负值，标准型中要求变量非负，所以令 1.3 线性规划的标准型线性规划的标准型Standard form of LP (3)第二个约束条件是第二个约束条件是号，在号，在号号 左左端减去剩余变量端减去剩余变量(Surplus variable)x5，x50。也称松驰变。也称松驰变量量1.3 线性规划的标准型线性规划的标准型Standard form of LP(2) 第一个约束条件是第一个约束条件是号，在号，在左端左端加入松驰变量加入松驰变量 (slack variable) x4，x4

45、0,化为等式；化为等式；(4)第三个约束条件是第三个约束条件是号且常数项为负数，因此在号且常数项为负数，因此在左边加入松左边加入松驰变量驰变量x6，x60，同时两边乘以同时两边乘以1。 （5）目标函数是最小值，为了化为求最大值，令）目标函数是最小值，为了化为求最大值，令Z=Z,得到得到max Z=Z，即当即当Z达到最小值时达到最小值时Z达到最大值，反之亦然。达到最大值，反之亦然。 综合起来得到下列标准型综合起来得到下列标准型 1.3 线性规划的标准型线性规划的标准型Standard form of LP 当某个变量当某个变量xj0时时,令令x/j=xj 。 当某个约束是绝对值不等式当某个约束是

46、绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束时，将绝对值不等式化为两个不等式，再化为等式，例如约束 将其化为两个不等式将其化为两个不等式 再加入松驰变量化为等式。再加入松驰变量化为等式。 1.3 线性规划的标准型线性规划的标准型Standard form of LP【例例1.13】将下例线性规划化为标准型将下例线性规划化为标准型【解解】 此题关键是将目标函数中的绝对值去掉。此题关键是将目标函数中的绝对值去掉。令令 则有则有1.3 线性规划的标准型线性规划的标准型Standard form of LP得到线性规划的标准形式得到线性规划的标准形式 1.3 线性规划的标准型线性

47、规划的标准型Standard form of LP对于对于axb(a、b均大于零均大于零)的有界变量化为标准形式有两种方的有界变量化为标准形式有两种方法，一种方法是增加两个约束法，一种方法是增加两个约束xa及及xb，另一种方法是令，另一种方法是令=xa，则，则axb等价于等价于0ba，增加一个约束，增加一个约束ba并且将原问并且将原问题所有题所有x用用x=+a替换。替换。1.如何化标准形式？如何化标准形式？ 可以对照四条标准逐一判断！可以对照四条标准逐一判断！ 标准形式是人为定义的，目标函数可以是求最小值。标准形式是人为定义的，目标函数可以是求最小值。2.用用WinQSB软件求解时，不必化成标

48、准型。软件求解时，不必化成标准型。图解法时不必化为标准型。图解法时不必化为标准型。3.单纯形法求解时一定要化为标准型。单纯形法求解时一定要化为标准型。作业：教材作业：教材P34 T 81.3 线性规划的标准型线性规划的标准型Standard form of LP下一节：基本概念下一节：基本概念1.4 线性规划的有关概念线性规划的有关概念Basic Concepts of LP 设线性规划的标准型设线性规划的标准型 max Z=CX （1.1） AX=b （1.2） X 0 （1.3）式中式中A 是是mn矩阵，矩阵，mn并且并且r（A）=m，显然显然A中至少有中至少有一个一个mm子矩阵子矩阵B，

49、使得使得r（B）=m。1.4 基本概念基本概念Basic Concepts 基基 (basis)A中中mm子矩阵子矩阵B并且有并且有r（B）=m，则称则称B是线性规是线性规划的一个基（或基矩阵划的一个基（或基矩阵basis matrix ）。当）。当m=n时，基矩阵唯一，时，基矩阵唯一，当当mn时，基矩阵就可能有多个，但数目不超过时，基矩阵就可能有多个，但数目不超过【例例1.14】线性规划线性规划 求所有基矩阵求所有基矩阵。 【解解】约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 容易看出容易看出r(A)=2，2阶子矩阵有阶子矩阵有C52=10个，其中第个，其中第1列与第列与第3列构成列

50、构成的的2阶矩阵不是一个基，基矩阵只有阶矩阵不是一个基，基矩阵只有9个，即个，即1.4 基本概念基本概念Basic Concepts 由线性代数知，基矩阵由线性代数知，基矩阵B必为非奇异矩阵并且必为非奇异矩阵并且|B|0。当矩当矩阵阵B的行列式等式零即的行列式等式零即|B|=0时就不是基时就不是基 当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基基向量向量(basis vector)，其余列向量称为其余列向量称为非基向量非基向量 基向量对应的变量称为基向量对应的变量称为基变量基变量(basis variable)，非基向量非基向量对应的变量