运筹学课件第七节其他应用例子.ppt

第七节其他应用例子,一、使用线性规划方法处理实际问题必须具备的条件(建模条件)：,1、优化条件-问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。,2、选择条件-有多种可供选择的可行方案，以便从中选取最优方案。,3、限制条件-达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的。,二、建模步骤,第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。,第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。,第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。,三、典型的LP问题,经济管理领域中有大量的实际问题可以归结为线性规划问题来研究，这些问题背景不同，表现各异，但数学模型却有着完全相同的形式。尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。,1、生产组织与计划问题,问题的一般提法：用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。,如果用，单位产品所需资源数（如原材料、人力、时间等）、所得利润及可供应的资源总量已知，如表所示，问应如何组织生产才能使利润最大？,产品计划问题有关信息表,设出产品的计划数，可列出这类问题的数学模型如下：,例:某工厂生产甲、乙、丙3种产品，均需经过A,B两道工序。设A工序可分别在设备A1或A2上完成，有B1,B2,B3三种设备可用于完成B工序。已知（1）产品甲可在A，B任何一种设备上加工；（2）产品乙可在任何规格的A设备加工，但完成B工序，仅能在B1设备上加工；（3）产品丙仅能在A2和B2设备上加工。目标：试列出线性规划模型，如何安排生产，使工厂总的利润最大。,解：设产品甲乙丙的产量分别是x1,x2,x3件。产品甲有6种加工方案，分别利用设备（A1,B1）（A1,B2）（A1,B3）（A2,B1）（A2,B2）（A2,B2），各个方案加工的产品甲用数量x11,x12,x13,x14,x15,x16表示；产品乙有2种加工方案，分别利用设备（A1,B1）（A2,B1），各个方案加工的产品乙用数量x21,x22,表示；产品丙有1种加工方案，利用设备（A2,B2），方案加工的产品丙用数量x3表示；Xij-生产第i种产品采用第j种方案时产品的数量X1=x11+x12+x13+x14+x15+x16X2=x21+x22,产品甲可在A，B任何一种设备上加工,产品乙可在任何规格的A设备加工，但完成B工序，仅能在B1设备上加工,产品丙仅能在A2和B2设备上加工,产品利润,产品利润,产品利润,使用设备A1的加工费,设备A1的资源约束,使用设备A2,B1,B2,B3的加工费,A2,B1,B2,B3设备的资源约束,2、营养问题,要求制定一个既经济又合乎健康标准的食谱。一个简单的例子：现准备采购甲、乙两种食品，表中给出了已知价格及相关的营养成分。最右栏给出了按营养学标准每人每天的最低需要量。问应如何采购食品才能在保证营养要求的前提下花费最省？,营养问题已知数据表,设x1、x2分别为甲、乙两种食品的采购量，则购买两种食品的总费用为Z=1.2x1+1.9x2，依题意可列出下面的线性规划：,维生素,淀粉,蛋白质,3、混合配料问题,问题的一般提法：由多种原料配置成含有m种成分的产品，已知产品中所含各成分的需要量及每种原料的价格，同时知道各种原料中所含m种成分的数量，要求给出使产品成本最低的配料方案。如：伙食问题（也称营养问题）、饲料配比问题、化工产品中的混合问题等都属于这类问题。,某糖果厂用原料A,B,C生产三种不同型号的糖果甲，乙，丙。已知各种型号糖果中A,B,C的含量，原料成本，各种原料的每月限制用量，三种型号的糖果的单位加工费及售价如表所示。问题：每月生产这三种型号糖果各多少KG，利润最大？,x11,x12,x13,x21,x22,x23,x31,x32,x33,解:用i=1,2,3代表原材料A,B,C用j=1,2,3代表甲乙丙三种糖果。xij为生产第j种糖果所耗用的第i种原料的kg数量。甲乙丙三种糖果x甲、x乙、x丙。x甲=x11+x21+x31x乙=x12+x22+x32x丙=x13+x23+x33,原料A,原料B,原料C,原料限制,含量限制,产品甲,产品乙,产品丙,原料A,原料B,原料C,原料A在产品甲所占的成分要大于60%,原料C在产品甲所占的成分要小于20%,原料C在产品丙所占的成分要小于60%,原料C在产品乙所占的成分要小于50%,原料A在产品乙所占的成分要大于30%,某公司计划为某建设项目从2003年起的4年中每年年初分别提供以下数额的贷款：2003-100万元；2004-150万元；2005-120万元；2006-110万元；以上资金需要在2002年底筹集齐，为了充分发挥这笔资金的作用，可将多余的资金分别投资下列项目：（1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元。（2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，但限购90万元。（3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元。（4）于每年初将任意数额的资金存放于银行，年息4%，于每年底取出。问题：如何在2002年底使筹集的钱最小。,4、动态投资问题,解设x为公司在2002年底筹集的钱，y1,y2,y3为2003、