运筹学 1-4 线性规划的应用与指导.ppt

设x1、x2分别为甲、乙两种食品的采购量，则购买两种食品的总费用为Z=1.2x1+1.9x2，依题意可列出下面的线性规划： 营养问题适用范围： 运动员集训队食谱设计； 幼儿园、医院等特殊群体的营养配餐； 机关、学校、企业等企事业单位团体伙食设计； 家庭食谱设计； 课程设计选题建议：为所在班级同学设计不同要求的食谱 ?对不同对象的营养要求 ——从营养学资料和通过医生咨询得到； ?各种食品的价格 ——通过不同季节的市场调查获取； ?一些特殊要求，比如饮食习惯、偏好等 ——可通过适当处理，转化为约束条件加入模型； 资料获取渠道及特殊要求的处理建议： 1.4 线性规划的应用 一、使用线性规划方法处理实际问题 必须具备的条件(建模条件)： 优化条件---问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。 选择条件---有多种可供选择的可行方案，以便从中选取最优方案。 3）限制条件---达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。 此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的。 二、建模步骤： ? 第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。 ? 第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，以避免“遗漏”或“重复”所造成的错误。 ? 第三步：明确目标要求，并用决策变量的线性函数来表示，确定对函数是取极大还是取极小的要求。 决策变量的非负要求可以根据问题的实际意义加以确定。 讨论：这三步的顺序可以颠倒吗？ 三、 经济管理领域中 几类典型的LP问题 经济管理领域中有大量的实际问题可以归结为线性规划问题来研究，这些问题背景不同，表现各异，但数学模型却有着完全相同的形式。 尽可能多地掌握一些典型的模型不仅有助于深刻理解线性规划本身的理论和方法，而且有利于灵活地处理千差万别的实际问题，提高解决实际问题的能力。 （一）?生产组织与计划问题 1. 产品计划问题 2. 产品配套问题 1、产品计划问题 问题的一般提法：用若干种原材料（资源）生产某几种产品，原材料（或资源）供应有一定限制，要求制定一个产品生产计划，使其在一定数量的资源限制条件下能得到最大的收益。 产品计划问题有关信息表 设xj为生产Aj产品的计划数，可列出这类问题的数学模型如下： 一般的产品计划问题举例 例1-8：某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二道工序为24小时。 生产产品B的同时产出副产品C，每生产一吨产品B，可同时得到2吨产品C而毋需外加任何费用；副产品C一部分可以盈利，剩下的只能报废。 一般的产品计划问题举例 出售产品A每吨能盈利400元、产品B每吨能盈利1000元，每销售一吨副产品C能盈利300元，而剩余要报废的则每吨损失200元。经市场预测，在计划期内产品C最大销量为5吨。试列出线性规划模型，决定A、B两种产品的产量，使工厂总的利润最大。 信息整理： 利润与产量的关系图： 数学模型： 设：x1——产品A的产量， x2——产品B的产量，x3——产品C的销售量，x4——产品C的报废量。依题意，可得 2、产品配套问题 例1-9 某产品由两个零件I和三个零件II组成，每个零件均可由三个车间各自生产，但各车间的生产效率和总工时限制各不相同，表中给出了有关信息。试确定各车间生产每种零件的工作时间，使生产产品的件数最多。 例1-9有关信息表 其中：xij表示第i个车间生产第j个零件的时间 注意——Z是非线性表达式！ 处理： 于是得到该问题的LP模型为： 该LP求解可得： (二)??合理下料问题 在加工业中，经常遇到这类问题。 问题的一般提法是：已知某种尺寸的棒料或板材，需要将其切割成一定数量既定规格的几种零件毛坯，问应如何选