运筹学绪论要点.pptx

运筹学运筹学主讲：黄建华主讲老师简介主讲老师简介 黄建华，博士、副教授。东南大学管理学硕士，大连理工大学工学博士。研究方向：复杂网络与复杂系统、供应链管理。主持课题：（1）国家社科基金：干扰模拟与基于二维网络视角的农产品供应链脆弱性研究；（2）教育部人文社科基金：农产品供应链网络的抗毁性能研究-基于复杂网络理论的研究视角；（3）福建省社科基金：区域农产品供应链的抗毁性能及农业产业安全策略研究。第一作者在系统工程理论与实践、系统管理学报、系统工系统工程理论与实践、系统管理学报、系统工程、北京理工大学学报程、北京理工大学学报等国内外核心期刊发表学术论文20余篇，其中EI收录5篇。绪绪 论论一、运筹学的简史 1、运筹学的早期发展历史v1914年提出兰彻斯特（Lanchester）战斗方程。v1917年丹麦工程师爱尔朗（Erlang）提出排队论的部分著名公式、v20世纪20年代，提出存储论的最优批量公式。2、二战期间的运筹学发展v20世纪30年代，运筹学（Operational research）作为科学名字出现。v运用于雷达防空系统。v应用于护航舰队保护商船的编队问题。v应用于反潜深水炸弹的合理爆炸深度研究。v应用于船只遭受敌机攻击时，转向逃避的问题研究。该阶段运筹学研究和解决的问题，大部分都是些短期的和战术性的问题。3、二战之后的发展v正式的运筹研究组织成立，开始着重研究战略性的问题。v60年代后，除了军事方面的研究，运筹学在工业、农业、经济和社会问题等各领域都有广泛应用。v运筹学技术自身得到飞速发展，并且形成了许多分支。二、运筹学的主要内容1 1、数学规划、数学规划v线性规划（线性规划（19471947年由丹捷格提出）年由丹捷格提出）v非线性规划非线性规划v整数规划整数规划v目标规划（目标规划（19611961年由查恩斯、库伯提出）年由查恩斯、库伯提出）v动态规划（动态规划（19511951年由贝尔曼提出）年由贝尔曼提出）v随机规划随机规划2 2、图论与网络、图论与网络3 3、排队论（随机服务系统理论）、排队论（随机服务系统理论）4 4、存储论、存储论5 5、对策论（竞赛论、博弈论）、对策论（竞赛论、博弈论）6 6、决策论（多目标决策）、决策论（多目标决策）三、运筹学的工作步骤1、提出和形成问题（目的、约束、可控变量）。2、建立模型。3、求解（利用各种数学方法或者计算机）。4、解的检验。5、解的控制。6、解的实施。第一章第一章 线性规划及单纯形法线性规划及单纯形法1线性规划问题及其数学模型一、问题的提出：问题1：合理利用资源问题例1：产品一产品一产品二产品二设备设备128台时台时原材料原材料A4016kg原材料原材料B0412kg每件产每件产品利润品利润2元元3元元线性规划数学模型的三个条件（特征）每一个问题都用一组决策变量表示某一方案，每一个问题都用一组决策变量表示某一方案，一般这些变量的取值是非负。一般这些变量的取值是非负。存在一定的约束条件，这些约束条件可以用一存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。组线性等式或不等式来表示。都有一个都有一个要求达到的目标，它可以用决策变量达到的目标，它可以用决策变量的线性函数（称为目标函数）来表示。按照问的线性函数（称为目标函数）来表示。按照问题的不同要求实现最大或者最小化。题的不同要求实现最大或者最小化。课堂练习：课堂练习：某饲养场饲养动物出售，设每头动物每天至少需某饲养场饲养动物出售，设每头动物每天至少需700克克蛋白质、蛋白质、30克矿物质、克矿物质、100毫克维生素。现有五种饲料毫克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如表可供选用，各种饲料每公斤营养成分含量及单价如表所示：所示：要求确定既满足动物生长的营养需要，又使费用最省要求确定既满足动物生长的营养需要，又使费用最省的选料方案。的选料方案。饲料饲料蛋白质蛋白质（克）（克）矿物质矿物质（克）（克）维生素维生素(毫克毫克)价格价格（元（元/千克）千克）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8第一章第一章 线性规划及单纯形法线性规划及单纯形法问题问题2：下料问题：下料问题问题问题3：配料问题：配料问题 问问题题4：成成批批生生产产企企业业年年度度生生产产计计划划的的按按月分配月分配问题问题5：连续投资问题：连续投资问题二、二、数学模型数学模型：第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法第一章 线性规划及单纯形法线性规划数学模型的标准化线性规划数学模型的标准化变变量量 =0不处理不处理 =0取相反数取相反数 无约束无约束两非负数之差两非负数之差约约束束条条件件b大于等于大于等于0不处理不处理b小于等于小于等于0两边乘以两边乘以-1小于等于号小于等于号加松弛变量加松弛变量等于号等于号加人工变量加人工变量大于等于号大于等于号减去剩余变量，加上人减去剩余变量，加上人工变量工变量目目标标函函数数Max z不处理不处理Min z取相反数取相反数加入变量的系数加入变量的系数松弛、剩余变量松弛、剩余变量人工变量人工变量0-M第一章 线性规划及单纯形法四、线性规划问题的解：四、线性规划问题的解：1 可行解、可行域2 最优解第一章第一章 线性规划及单纯形法线性规划及单纯形法1 基阵2 基向量、非基向量、基变量、非基变量3 基解、基可行解、可行解2 图解法图解法一、图解法步骤：一、图解法步骤：第一章第一章 线性规划及单纯形法线性规划及单纯形法第一章 线性规划及单纯形法二、线性规划解的几种情形二、线性规划解的几种情形1无无穷穷多多最最优优解解。目目标标函函数数执执行行平平行行于于可可行域某一边行域某一边2唯一解唯一解3无界解无界解4.无可行解无可行解 第一章 线性规划及单纯形法三、图解法得到的启示：三、图解法得到的启示：1解的情形2可行域为一凸集3最优解一定在可行域凸集的某个顶点处获得4解题思路 第一章 线性规划及单纯形法3 单纯形法原理单纯形法原理一、凸集及顶点凸集、顶点二、几个基本定理定理1 若（LP）存在可行解，则其可行域为凸集 引理：线性规划问题的可行解 第一章 线性规划及单纯形法 为基可行解充要条件是X的正分量所对应的系数列向量是线性无关的。定理2 线性规划问题基可行解X对应线性规划问题可行域（凸集）的顶点定理3 若线性规划问题有最优解，一定存在一个基可行解是最优解。三、单纯形法迭代原理1、确定初始基可行解（顶点）1 约束为“”2 约束为“”、“=”第一章 线性规划及单纯形法2、第一章 线性规划及单纯形法第一章线性规划及单纯形法为对应于基B的一个基可行解，且对于一切 为最优解。定理2：若存在 则线性规划有无穷多解。定理3：若 为一基可行解，存在 且 则线性规划问题无解。3 寻找改进的基可行解 换入变量的确定：若存在 则令 则 为换入变量。第一章线性规划及单纯形法换出变量的确定 第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划及单纯形法5 单纯形法的进一步讨论单纯形法的进一步讨论 一、找初始基可行解的两阶段法：第一阶段：对约束为：加入人工变量 求解：第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划及单纯形法6 应用举例应用举例例一（下料问题）：例一（下料问题）：现要做现要做100套钢架，每套用长套钢架，每套用长为为2.9m，2.1m，1.5m的元钢各一根，已知料长的元钢各一根，已知料长为为7.4m，问应该如何下料，使用的原材料最省。，问应该如何下料，使用的原材料最省。第一章线性规划及单纯形法2.92.11.5例二（配料问题）：例二（配料问题）：某工厂要用三种原材料某工厂要用三种原材料C、P、H混合混合调配出三种不同规格的产品调配出三种不同规格的产品A、B、D。已知产品的规格已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表一、表二，该工厂应该如何安排生产，使价，分别见表一、表二，该工厂应该如何安排生产，使利润收入最大？利润收入最大？第一章线性规划及单纯形法产品名称产品名称规格要求规格要求单价（元单价（元/kg）A原材料原材料C不少于不少于50%，P不超过不超过25%50B原材料原材料C不少于不少于25%，P不超过不超过50%35D不限制不限制25原材料名称原材料名称每天最多供应量（每天最多供应量（kg）单价（元单价（元/kg）C10065P10025H6035人力资源分配问题人力资源分配问题 例3某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?第一章线性规划及单纯形法例例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：Min f=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 0 (i=1、2；j=1、2、3）运运 输输 模模 型型建模步骤建模步骤第第第第一一一一步步步步：决决决决策策策策变变变变量量量量。决决决决策策策策变变变变量量量量选选选选取取取取得得得得当当当当，不不不不仅仅仅仅能能能能顺顺顺顺利利利利地地地地建建建建立立立立模模模模型型型型而而而而且且且且能能能能方方方方便便便便地地地地求求求求解解解解，否否否否则则则则很很很很可可可可能事倍功半。能事倍功半。能事倍功半。能事倍功半。第第第第二二二二步步步步：约约约约束束束束条条条条件件件件。并并并并用用用用决决决决策策策策变变变变量量量量的的的的线线线线性性性性方方方方程程程程或或或或线线线线性性性性不不不不等等等等式式式式来来来来表表表表示示示示。当当当当限限限限制制制制条条条条件件件件多多多多，背背背背景景景景比比比比较较较较复复复复杂杂杂杂时时时时，可可可可以以以以采采采采用用用用图图图图示示示示或或或或表表表表格格格格形形形形式式式式列列列列出出出出所所所所有有有有的的的的已已已已知知知知数数数数据据据据和和和和信信信信息息息息，以以以以避避避避免免免免“遗遗遗遗漏漏漏漏”或或或或“重重重重复复复复”所造成的错误。所造成的错误。所造成的错误。所造成的错误。第三步：目标函数。第三步：目标函数。确定对函数是取极确定对函数是取极大还是取极小的要求。大还是取极小的要求。决策变量的非负要求可以根据问题决策变量的非负要求可以根据问题的实际意义加以确定。的实际意义加以确定。讨论：这三步的顺序可以颠倒吗？讨论：这三步的顺序可以颠倒吗？为什麽？为什麽？经济管理领域中经济管理领域中 几类典型的几类典型的LPLP问题问题 经经经经济济济济管管管管理理理理领领领领域域域域中中中中有有有有大大大大量量量量的的的的实实实实际际际际问问问问题题题题可可可可以以以以归归归归结结结结为为为为线线线线性性性性规规规规划划划划问问问问题题题题来来来来研研研研究究究究，这这这这些些些些问问问问题题题题背背背背景景景景不不不不同同同同，表现各异，但数学模型却有着完全相同的形式。表现各异，但数学模型却有着完全相同的形式。表现各异，但数学模型却有着完全相同的形式。表现各异，但数学模型却有着完全相同的形式。尽尽尽尽可可可可能能能能多多多多地地地地掌掌掌掌握握握握一一一一些些些些典典典典型型型型的的的的模模模模型型型型不不不不仅仅仅仅有有有有助助助助于于于于深深深深刻刻刻刻理理理理解解解解线线线线性性性性规规规规划划划划本本本本身身身身的的的的理理理理论论论论和和和和方方方方法法法法，而而而而且且且且有有有有利利利利于于于于灵灵灵灵活活活活地地地地处处处处理理理理千千千千差差差差万万万万别别别别的的的的实实实实际际际际问问问问题题题题，提提提提高高高高解决实际问题的能力。解决实际问题的能力。解决实际问题的能力。解决实际问题的能力。例题例题1：人力资源分配问题：人力资源分配问题公交线路需要公交线路需要24小时值班，每次值班小时值班，每次值班8小小时。不同时段需要的人数不等。时。不同时段需要的人数不等。序号序号时段时段最少人数最少人数106106021014703141860418225052202206020630问题：如何安排，所需人数最少问题：如何安排，所需人数最少？例题例题1：人力资源分配问题：人力资源分配问题设设xi为第为第i班次开始上班的人数班次开始上班的人数目标函数：目标函数：min Z=x1+x2+x3+x4+x5+x6约束条件：约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1+x6 60非负性约束：非负性约束：xj 0,j=1,2,6例题例题2：人力资源分配问题：人力资源分配问题福安商场是个中型的百货商场，它对售货人福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下所示员的需求经过统计分析如下所示例题例题2：人力资源分配问题：人力资源分配问题为了保证售货人员充分休息，售货人员每周工作为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作问应该如何安排售货人员的作息，既满足了工作需要，又使配备的售货人员的人数最少需要，又使配备的售货人员的人数最少?分析：设分析：设xi为星期为星期i开始休息的人数，开始休息的人数，i=1,2,3,7，目标是要求售货人员的总数最少目标是要求售货人员的总数最少,因为每个百货员因为每个百货员都工作五天，休息两天，所以只要计算出连续休都工作五天，休息两天，所以只要计算出连续休息两天的售货员人数，也就计算出了售货员的总息两天的售货员人数，也就计算出了售货员的总数。把连续休息两天的售货员按照开始休息的时数。把连续休息两天的售货员按照开始休息的时间分成间分成7类，类，例题例题2：人力资源分配问题：人力资源分配问题 解：设解：设 x xi i(i=1,2,(i=1,2,7),7)表示星期表示星期i i开始休息的人数。开始休息的人数。目标函数：目标函数：Min Min x x1 1+x x2 2+x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 约束条件：约束条件：s.t.s.t.x x1 1+x x2 2+x x3 3+x x4 4+x x5 5 28 28 x x2 2+x x3 3+x x4 4+x x5 5+x x6 6 15 15 x x3 3+x x4 4+x x5 5+x x6 6+x x7 7 24 24 x x4 4+x x5 5+x x6 6+x x7 7+x x1 1 25 25 x x5 5+x x6 6+x x7 7+x x1 1+x x2 2 19 19 x x6 6+x x7 7+x x1 1+x x2 2+x x3 3 31 31 x x7 7+x x1 1+x x2 2+x x3 3+x x4 4 28 28 x1,x2,x3,x4,x5,x6,x7 0例题例题3 生产计划问题生产计划问题明兴公司面临一个是外包协作还是自行生产的明兴公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，这三问题。该公司生产甲、乙、丙三种产品，这三种产品都要经过铸造、机加工和装配三个车间。种产品都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质自行生产，但产品丙必须本厂铸造才能保证质量。公司可利用的总时数：铸造量。公司可利用的总时数：铸造80008000小时；机小时；机加工加工1200012000小时；装配小时；装配1000010000小时。有关搞况见小时。有关搞况见下表：下表：例题例题3 生产计划问题生产计划问题例题例题3 生产计划问题生产计划问题设设x1，x2，x3分别为三道工序都由本公司加工分别为三道工序都由本公司加工的甲、乙、丙三种产的件数，设的甲乙、丙三种产的件数，设x4，x5分别为分别为由外协铸造再由本公司机加工和装配的甲、乙由外协铸造再由本公司机加工和装配的甲、乙两种产品的数量：两种产品的数量：计算每件产品的利润：计算每件产品的利润：产品甲全部自制的利润产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润产品甲铸造外协，其余自制的利润=23-(5+2+3)=13 产品乙全部自制的利润产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协，其余自制的利润产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润产品丙的利润 =16-(4+3+2)=7 可得到可得到 xi（i=1,2,3,4,5）的利润分别为的利润分别为 15、10、7、13、9 元。元。例题例题3 生产计划问题生产计划问题数学模型数学模型:目标函数：目标函数：Max 15Max 15x x1 1+10+10 x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 约束条件：约束条件：5 5x x1 1+10+10 x x2 2+7+7x x3 3 8000 8000 6 6x x1 1+4+4x x2 2+8+8x x3 3+6+6x x4 4+4+4x x5 5 12000 12000 3 3x x1 1+2+2x x2 2+2+2x x3 3+3+3x x4 4+2+2x x5 5 10000 10000 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 0 0例例4 4 生产计划的问题生产计划的问题 某机械厂生产某机械厂生产、三种产品，均要经过三种产品，均要经过A A、B B两道两道工序加工。设有两种规格的设备工序加工。设有两种规格的设备A A1 1、A A2 2能完成能完成 A A 工序；工序；有三种规格的设备有三种规格的设备B B1 1、B B2 2、B B3 3能完成能完成 B B工序。工序。可在可在A A、B B的任何规格的设备上加工；的任何规格的设备上加工；可在任意规格的可在任意规格的A A设备上加工，但对设备上加工，但对B B工序，只能在工序，只能在B B1 1设备上加工；设备上加工；只能在只能在A A2 2与与B B2 2设备上加工。数据如表。设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？问：为使该厂获得最大利润，应如何制定产品加工方案？例例4 4 生产计划的问题生产计划的问题解：设解：设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序上的第种工序上的第 k k 种设备上加工的种设备上加工的数量。建立如下的数学模型数量。建立如下的数学模型:s.t.5s.t.5x x111111+10+10 x x211 211 6000 6000 （设备设备 A A1 1 ）7 7x x112112+9+9x x212212+12+12x x312312 10000 10000 （设备设备 A A2 2 ）6 6x x121121+8+8x x221221 4000 4000 （设备设备 B B1 1 ）4 4x x122122 +11 +11x x322322 7000 7000 （设备设备 B B2 2 ）7 7x x123123 4000 4000 （设备设备 B B3 3 ）x x111111+x x112112-x x121121-x x122122-x x123123=0 =0（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x x211211+x x212212-x x221221 =0 =0（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x x312 312 -x x322322 =0 =0（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x xijkijk 0 ,i=1,2,3;j=1,2;k=1,2,3 0 ,i=1,2,3;j=1,2;k=1,2,3例例4 4 生产计划的问题生产计划的问题目标函数为计算利润最大化，利润的计算公式为：目标函数为计算利润最大化，利润的计算公式为：利润利润 =（销售单价（销售单价 -原料单价）原料单价）*产品件数产品件数 之和之和 -（每台时的设备费用（每台时的设备费用*设备实际使用的总台时数）之和。设备实际使用的总台时数）之和。这样得到目标函数：这样得到目标函数：Max(1.25-0.25)(xMax(1.25-0.25)(x111111+x+x112112)+(2-0.35)x)+(2-0.35)x221221+(2.80-0.5)x+(2.80-0.5)x312312 300/6000(5x 300/6000(5x111111+10 x+10 x211211)-321/10000(7x)-321/10000(7x112112+9x+9x212212+12x+12x312312)-)-250/4000(6x 250/40006x121121+8x+8x221221)-783/7000(4x)-783/7000(4x122122+11x+11x322322)-)-200/4000(7x200/4000(7x123123).).经整理可得：经整理可得：Max0.75Max0.75x x111111+0.7753+0.7753x x112112+1.15+1.15x x211211+1.3611+1.3611x x212212+1.9148+1.9148x x312312-0.375-0.375x x121121-0.50.5x x221221-0.4475-0.4475x x122122-1.2304-1.2304x x322322-0.35-0.35x x1231232.9m钢筋架子钢筋架子1002.1m，原料长，原料长7.4m1.5m 2.9m 1 2 0 1 0 1 0 0 2.9m 1 2 0 1 0 1 0 0 2.1m 0 0 2 2 1 1 3 0 2.1m 0 0 2 2 1 1 3 0 1.5m 3 1 2 0 3 1 0 4 1.5m 3 1 2 0 3 1 0 4 合计合计 7.4 7.3 7.2 7.1 6.6 6.5 6.3 67.4 7.3 7.2 7.1 6.6 6.5 6.3 6 料头料头 0 0.1 0.2 0.3 0.8 0.9 1.1 1.40 0.1 0.2 0.3 0.8 0.9 1.1 1.4例例5合理下料问题合理下料问题解：设按第解：设按第i种方案下料的原材料为种方案下料的原材料为xi根根minZ=x1+x2+x3+x4+x5+x6+x7+x8 x1+2x2+x4+x6 100 2x3+2x4+x5+x6+3x7 1003x1+x2+2x3 +3x5+x6+x8 100 xi 0(i=1,8)，且为整数且为整数 例例6 6 配料问题配料问题 某工厂要用三种原料某工厂要用三种原料1 1、2 2、3 3混合调配出三种不同规混合调配出三种不同规格的产品甲、乙、丙，数据如下表。格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？问：该厂应如何安排生产，使利润收入为最大？例例6 6 配料问题配料问题解：设解：设 xij 表示第表示第 i 种（甲、乙、丙）产品中原料种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：的含量。这样我们建立数学模型时，要考虑：对于甲：对于甲：x11，x12，x13；对于乙：对于乙：x21，x22，x23；对于丙：对于丙：x31，x32，x33；对于原料对于原料1：x11，x21，x31；对于原料对于原料2：x12，x22，x32；对于原料对于原料3：x13，x23，x33；目标函数：目标函数：利润最大，利润利润最大，利润=收入收入-原料支出原料支出 约束条件：约束条件：规格要求规格要求 4 个；个；供应量限制供应量限制 3 个。个。例例6 6 配料问题配料问题利润利润=总收入总收入-总成本总成本=甲乙丙三种产品的销售单价甲乙丙三种产品的销售单价*产品数量产品数量-甲乙丙使用甲乙丙使用的原料单价的原料单价*原料数量，故有原料数量，故有目标函数目标函数Max 50Max 50（x x1111+x x1212+x x1313）+35+35（x x2121+x x2222+x x2323）+25+25（x x3131+x x3232+x x3333）-65-65（x x1111+x x2121+x x3131）-25-25（x x1212+x x2222+x x3232）35-35（x x1313+x x2323+x x3333）=-15=-15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 约束条件：约束条件：从第从第1个表中有：个表中有：x x11110.5(0.5(x x1111+x x1212+x x1313)x x12120.25(0.25(x x1111+x x1212+x x1313)x x21210.25(0.25(x x2121+x x2222+x x2323)x x22220.5(0.5(x x2121+x x2222+x x2323)例例6 6 配料问题配料问题 从第从第2个表中，生产甲乙丙的原材料不能超过原个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有材料的供应限额，故有 (x x1111+x x2121+x x3131)100)100 (x x1212+x x2222+x x3232)100)100 (x x1313+x x2323+x x3333)60)60 通过整理，得到以下模型：通过整理，得到以下模型：例例6 6 配料问题配料问题例例6 6（续）（续）目标函数：目标函数：Max z=-15Max z=-15x x1111+25+25x x1212+15+15x x1313-30-30 x x2121+10+10 x x2222-40-40 x x3131-10-10 x x3333 约束条件：约束条件：s.t.0.5 s.t.0.5 x x1111-0.5-0.5 x x12 12-0.5-0.5 x x1313 0 0（原材料（原材料1 1不少于不少于50%50%）-0.25-0.25x x1111+0.75+0.75x x1212-0.25-0.25x x1313 0 0（原材料（原材料2 2不超过不超过25%25%）0.750.75x x2121-0.25-0.25x x2222-0.25-0.25x x2323 0 0（原材料（原材料1 1不少于不少于2525%）-0.5-0.5 x x2121+0.5+0.5 x x2222-0.5 -0.5 x x2323 0 0（原材料（原材料2 2不超过不超过50%50%）x x1111+x x2121+x x3131 100 (100 (供应量限制）供应量限制）x x1212+x x2222+x x3232 100 (100 (供应量限制）供应量限制）x x1313+x x2323+x x3333 60 (60 (供应量限制）供应量限制）x xijij 0 ,i=1,2,3;j=1,2,3 0 ,i=1,2,3;j=1,2,3例例7 7 配料问题配料问题 汽油混合问题。一种汽油的特性可用两种指标汽油混合问题。一种汽油的特性可用两种指标描述，用描述，用“辛烷数辛烷数”来定量描述其点火特性，来定量描述其点火特性，用用“蒸汽压力蒸汽压力”来定量描述其挥发性。某炼油来定量描述其挥发性。某炼油厂有厂有1 1、2 2、3 3、4 4种标准汽油，其特性和库存量种标准汽油，其特性和库存量列于表中，将这四种标准汽油混合，可得到标列于表中，将这四种标准汽油混合，可得到标号为号为1 1，2 2的两种飞机汽油，这两种汽油的性能的两种飞机汽油，这两种汽油的性能指标及产量需求列于表中。指标及产量需求列于表中。问应如何根据库存情况适量混合各种标准汽油，问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标又使既满足飞机汽油的性能指标，又使2 2号汽油满号汽油满足需求，并使得足需求，并使得1 1号汽油产量最高？号汽油产量最高？例例7 7 配料问题配料问题 标准汽标准汽油油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)库存量库存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24081004108.028.45 10-2130100飞机汽油飞机汽油辛烷数辛烷数蒸汽压力蒸汽压力(g/cm2)产量需求产量需求1不小于不小于91不大于不大于9.96 10-2越多越好越多越好2不小于不小于100不大于不大于9.96 10-2不少于不少于250000例例7 7 配料问题配料问题 解：设解：设x xijij为飞机汽油为飞机汽油i i中所用标准汽油中所用标准汽油j j的数量的数量(L)(L)。目标函数为飞机汽油目标函数为飞机汽油1 1的总产量：的总产量：库存量约束为：库存量约束为：产量约束为飞机汽油产量约束为飞机汽油2的产量：的产量：由物理中的分压定律，由物理中的分压定律，可得有关蒸汽压力的约束条可得有关蒸汽压力的约束条件：件：同样可得有关辛烷数的约束条件同样可得有关辛烷数的约束条件为：为：例例7 7 配料问题配料问题 综上所述，得该问题的数学模型为：综上所述，得该问题的数学模型为：例例7 7 配料问题配料问题 由管理运筹学软件求解得：由管理运筹学软件求解得：例例8 8 投资问题投资问题 某部门现有资金某部门现有资金200200万元，今后五年内考虑给以下的项目投资。万元，今后五年内考虑给以下的项目投资。项目项目A A：从第一年到第五年每年年初都可投资，当年末能收回本：从第一年到第五年每年年初都可投资，当年末能收回本利利110%110%；项目项目B B：从第一年到第四年每年年初都可投资，次年末能收回本：从第一年到第四年每年年初都可投资，次年末能收回本利利125%125%，但规定每年最大投资额不能超过，但规定每年最大投资额不能超过3030万元；万元；项目项目C C：需在第三年年初投资，第五年末能收回本利：需在第三年年初投资，第五年末能收回本利140%140%，但规，但规定最大投资额不能超过定最大投资额不能超过8080万元；万元；项目项目D D：需在第二年年初投资，第五年末能收回本：需在第二年年初投资，第五年末能收回本利利155%155%，但规定最大投资额不能超过，但规定最大投资额不能超过100100万元。万元。据测定每万元每次投资的风险指数如下表：据测定每万元每次投资的风险指数如下表：例例8 8 投资问题投资问题 问：问：a a）应如何确定这些项目的每年投资额，使得第五年年末拥有）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？资金的本利金额为最大？b b）应如何确定这些项目的每年投资额，使得第五年年末拥有）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在资金的本利在330330万元的基础上使得其投资总的风险系数为万元的基础上使得其投资总的风险系数为最小？最小？解：解：1 1）确定决策变量：连续投资问题）确定决策变量：连续投资问题 设设 x xijij(i=1(i=15 5，j=1j=14)4)表示第表示第 i i 年初投资于年初投资于A(j=1)A(j=1)、B(j=2)B(j=2)、C(j=3)C(j=3)、D(j=4)D(j=4)项目的金额。这样我们建立项目的金额。这样我们建立如下的决策变量：如下的决策变量：A xA x11 11 x x21 21 x x3131 x x4141 x x5151 B x B x12 12 x x22 22 x x3232 x x4242 C C x x3333 D D x x24242 2）约束条件：）约束条件：第一年：第一年：A A当年末可收回投资，故第一年年初应把全部资金投出当年末可收回投资，故第一年年初应把全部资金投出去，于是去，于是 x x1111+x x12 12=200=200；第二年：第二年：B B次年末才可收回投资，故第二年年初有资金次年末才可收回投资，故第二年年初有资金1.1 1.1 x x1111，于是于是 x x21 21+x x2222+x x2424=1.1=1.1x x1111；第三年：年初有资金第三年：年初有资金 1.11.1x x2121+1.25+1.25x x1212，于是，于是 x x31 31+x x3232+x x3333=1.11.1x x2121+1.25+1.25x x1212；第四年：年初有资金第四年：年初有资金 1.11.1x x3131+1.25+1.25x x2222，于是，于是 x x41 41+x x4242=1.11.1x x3131+1.25+1.25x x2222；第五年：年初有资金第五年：年初有资金 1.11.1x x4141+1.25+1.25x x3232，于是，于是 x x51 51=1.1=1.1x x4141+1.251.25x x3232；B B、C C、D D的投资限制：的投资限制：x xi2 i2 30(i=1 30(i=1、2 2、3 3、4)4)，x x3333 8080，x x2424 100 100 例例8 8 投资问题投资问题3 3）目标函数及模型：）目标函数及模型：a)Max z=1.1a)Max z=1.1x x5151+1.25+1.25x x4242+1.4+1.4x x33 33+1.55+1.55x x24 24 s.t.s.t.x x1111+x x12 12=200=200 x x21 21+x x2222+x x2424=1.1=1.1x x1111；x x31 31+x x3232x x3333=1.1=1.1x x2121+1.25+1.25x x1212；x x41 41+x x4242=1.1=1.1x x3131+1.25+1.25x x2222；x x51 51=1.1=1.1x x4141+1.25+1.25x x3232；x xi2 i2 30(i=1 30(i=1、2 2、3 3、4)4)，x x3333 80 80，x x2424 100 100 x xijij 0 (i=1 0 (i=1、2 2、3 3、4 4、5 5；j=1j=1、2 2、3 3、4 4）例例8 8 投资问题投资问题例例8 8 投资问题投资问题b)b)所设变量与问题所设变量与问题a a相同，目标函数为风险最小，有相同，目标函数为风险最小，有 Min f=Min f=x x1111+x x2121+x x3131+x x4141+x x5151+3(+3(x x1212+x x2222+x x3232+x x4242)+4)+4x x3333+5.5+5.5x x24 24 在问题在问题a a的约束条件中加上的约束条件中加上“第五年末拥有资金本利在第五年末拥有资金本利在330330万元万元”的条件，的条件，于是模型如下：于是模型如下：Min f=(Min f=(x x1111+x x2121+x x3131+x x4141+x x5151)+3()+3(x x1212+