线性规划整数规划_.ppt

  1. 1、本文档共27页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
线性规划整数规划_.ppt

* 线性规划模型 第一节 线性规划模型 一、线性规划及其数学模型 1.线性规划问题 在生产管理和经营活动中,经常提出一类问题,既如何合理地 利用有限的人力、物力、财力等资源,以便得到最好的经济效益。 问题1拟定生产计划 问题提出 某公司生产炊事用具需要两种资源—劳动力和原材 料,某公司计划生产三种不同产品,生产管理部门提供的数据如下: 3 2 4 利润(元/件) 5 4 4 原材料(千克/件) 6 3 7 劳动力(小时/件) C B A 每天可供应原材料为200千克,每天可使用的劳动力为150小 时,问如何安排生产计划,才能是公司总收益最大? 模型建立 设每天生产A、B、C三种产品的件数分别为 最大利润为 则该问题就是在条件 下,求利润 的最大值。 问题2运输问题 问题的提出 两个煤炭厂 每月进煤分别为60t和100t, 联合供应三个居民区 三个居民区每月对煤的需求量依次 为50t、70t、40t,煤厂 离居民区 的距离分别为10km、 5km、 6km,煤厂 离居民区 的距离分别为4km、8km、 12km,如何分配供煤量才能使总运输量 达到最小? 模型建立 设 表示煤厂 提供给居民区 的煤量, 表示总运输量,则所求问题就是在条件 下,求总运输量 的最小值。 2.线性规划问题的特点和数学模型 从以上两个实例可以看出,它们都属于一类优化问题,其共同 特点是: (1)所给问题都用一组决策变量 表示某一方案, 这组决策变量的值就代表一个具体方案,一般这些变量的取是非 负的; (2)存在一定的约束条件,这些约束条件可以用一组线性 等式或线性不等式来表示; (3)都有一个要求达到的目标,它可以用决策变量的线性 函数来表示,这个函数称为目标函数。按问题的不同,要求目标 函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划问题的数学模型, 其一般形式为: 目标函数: 约束条件: 3.线性规划模型的标准型 实际问题的线性规划模型是多种多样的,在多种多样的模型中, 可规定一种形式为标准型,以便于研究和求解。 (1)线性规划模型的标准型 如果在线性规划模型中,有n个决策变量m个约束条件,约束 条件为等式约束,决策变量非负,求目标函数的最小值,这种线性 规划模型就叫做标准型。其表达式为: 在标准型中,规定 否则等式两端乘以“-1”,其 矩阵形式为: 其中, 称为约束条件的系数矩阵,一般有 称为价值向量;向量 称为资源向量; 称为决策向量; 为零向量。 (2)任意一线性规划模型都可以化为标准型 若原模型要求目标函数实现最大化,即 则 即目标函数可化为 这就 与标准型的目标函数一致了。 若原模型中的约束条件为不等式,有两种情况: ①若原模型中的约束条件为不等式:左端 右端,则在左端加 上“非负松弛变量”使不等式化为等式:左端+非负松弛变量=右端。 ②若原模型中的约束条件为不等式:左端 右端,则在左端减 去“非负松弛变量”使不等式化为等式:左端-非负松弛变量=右端。 例1将问题1的模型 化为标准型。 二、应用举例 1.食谱问题  问题提出 一饲养场饲养供实验用的动物,已知动物的生长对 饲料中的三种营养成分:蛋白质、矿物质和维生素特别敏感,每个 动物每天至少需要蛋白质70克,矿物质3克,维生素10毫克。 该场能买到5种饲料,各种饲料每千克的成本及所含营养成分如下 表所示,请确定既能满足动物需要,又使总成本最低的饲料配方。 0.08 0.05 1.80 0.5 0.20 0.20 0.60 0.3 0.02 0.02 1.00 0.4 0.10 0.05 2.00 0.7 0.05 0.10 0.30 0.2 维生素(克) 矿物质(克) 蛋白质(克) 成本(元) 饲料 设每个动物每天食用的混合饲料中所含的第 种饲料 的数量 为 千克,混合饲料的总成本为z,则上述问题的数学模型为 2.连续投资问题 问题提出 某部门在今后五年内考虑给下列四个项目投资,项 目A,从第一年到第四年年初需要投资,并于次年末回收本利的 115%;B项目,第三年年初需要投资,到第五年年末能回收本利 125%,但规定最大投资不超过4万元;C项目,第二年年初需要 投资,到第五年年末能回收本利140%,但规定最大投资不超过3万 元;项目D,五年内每年年初购买公债,于当年末归还,并加利息 6%。 该部门现有资金10万元,问如何分配这些项目每年的投资额,使 到第五年末拥有资金的本利总额最大? 问题分析 (1)五年中每年年初该部门拥有的资金是变化的,设 表示第i年年初给第j项项目的投资额,显然 (2)该部门每年的投资额等于部门年初所拥有的资金,下面 分年度讨论: 第一年,年初拥有资金10万元,所以有 第二年,年初拥有资金仅为项目D在第一年末回收的本息 所以有 第三年,年初拥有资金

文档评论(0)

ygxt89 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档