第2章-线性规划模型ppt课件.ppt





《第2章-线性规划模型ppt课件.ppt》由会员分享,可在线阅读,更多相关《第2章-线性规划模型ppt课件.ppt(59页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外线线 性性 规规 划划Linear ProgrammingLinear Programming第一篇第一篇 运筹学模型运筹学模型第第2页页第第2章章 线性规划模型线性规划模型2.1 拟订生产计划问题拟订生产计划问题2.2 运输问题运输问题2.3 食谱问题食谱问题2.4 作物布局问题作物布局问题2.5 配料问题配料问题2.6 LP模型的一般形式与标准形式模型的一般形式与标准形式2.7 LP模型的几何解释和图解法模型的几何解释和图解法2.8 一些实例一些实例第第3页页实例1|某化工厂生产四种化工产品某化工厂生产四种化工产
2、品 ,每种产品生产每种产品生产1吨吨消耗的工时、能源和获得的利润如表消耗的工时、能源和获得的利润如表2-1所示所示 表表2-1 生产生产1t产品的消耗和收益产品的消耗和收益 1 8 5 2利润利润/万万元元 0.1 0.5 0.3 0.2能耗能耗/t标准煤标准煤 75 380 250 100工时工时/h 产品产品第第4页页问问 题题 已知该厂明年的工时限额为已知该厂明年的工时限额为18480h,能耗限额为,能耗限额为100t标准煤,欲使该厂明年的总利润最高,请确定标准煤,欲使该厂明年的总利润最高,请确定定各种产品的生产数量,试建立数学模型。定各种产品的生产数量,试建立数学模型。第第5页页模型假
3、设|四种产品的每吨获利是与它们各自的生产数量无四种产品的每吨获利是与它们各自的生产数量无关的常数;每种产品生产一吨消耗的工时,能耗关的常数;每种产品生产一吨消耗的工时,能耗是与各种产品的产量无关的常数。是与各种产品的产量无关的常数。|四种产品每吨的获利是与它们相互间产量无关的四种产品每吨的获利是与它们相互间产量无关的常数。每种产品所消耗的工时,能耗是与它们相常数。每种产品所消耗的工时,能耗是与它们相互间产量无关的常数。互间产量无关的常数。|生产产品的数量可以是任意实数。生产产品的数量可以是任意实数。第第6页页问题分析问题分析|决策变量决策变量:四种产品明年的生产数量四种产品明年的生产数量|目标
4、目标:该厂明年的总利润最大该厂明年的总利润最大 利润函数:利润函数:|约束条件约束条件:工时限制工时限制 能耗限制能耗限制 蕴含约束蕴含约束:四种产品产量非负四种产品产量非负 第第7页页模型建立模型建立由于目标函数由于目标函数 是变量是变量 的线性函数,约束条件是的的线性函数,约束条件是的线性不等式,所以该问题为线性不等式,所以该问题为线性规划问题线性规划问题,简写为,简写为LP.第第8页页线性规划问题的特征线性规划问题的特征比比例例性性 可可加加性性 连续性连续性 xi对目标函数的对目标函数的“贡献贡献”与与xi取值成取值成正比正比 xi对约束条件的对约束条件的“贡献贡献”与与xi取值成取值
5、成正比正比 xi对目标函数的对目标函数的“贡献贡献”与与xj取值无取值无关关 xi对约束条件的对约束条件的“贡献贡献”与与xj取值无取值无关关 xi取取值连续值连续 第第9页页实例2一般的拟定生产计划问题|例例2 设有设有m种资源:种资源:,拟生产,拟生产n种产品:种产品:.用用表示生产表示生产1个单位第个单位第j种产品种产品所需要的第所需要的第i种资源的数量,用种资源的数量,用 表示第表示第i种资源种资源的使用限额,用的使用限额,用 表示销售一个单位的第表示销售一个单位的第j种产品种产品获得的利润,用获得的利润,用 表示第表示第j种产品的生产数量,则种产品的生产数量,则就代表一个生产计划,我
6、们的就代表一个生产计划,我们的问题是:要设法安排一个生产计划,使该厂获得的问题是:要设法安排一个生产计划,使该厂获得的总利润最高。总利润最高。第第10页页问题分析|决策变量决策变量:n种产品的生产数量种产品的生产数量|目标目标:该厂获得的总利润最大该厂获得的总利润最大 利润函数:利润函数:|约束条件约束条件:资源资源 的使用限额的使用限额 蕴含约束蕴含约束:n种种产品产量非负产品产量非负第第11页页模型建立 当拟订的生产计当拟订的生产计划规模较大时划规模较大时,我我们通常采用向量、们通常采用向量、矩阵记号,则该矩阵记号,则该模型变成什么样模型变成什么样了呢?了呢?第第12页页|设有设有3个化肥
7、厂:甲、乙、丙,供应个化肥厂:甲、乙、丙,供应3个地区个地区:A,B,C化肥,各厂的化肥年产量、各地区需求量化肥,各厂的化肥年产量、各地区需求量及各厂到及各厂到3个地区的单位运价见表所示;假设各个地区的单位运价见表所示;假设各地区需求量没有满足会造成经济损失地区需求量没有满足会造成经济损失:B,C区的区的单位损失分别为单位损失分别为3万元万元/万吨和万吨和2万元万元/万吨,万吨,A区区的需求量必须保证,求使得总运费和经济损失费的需求量必须保证,求使得总运费和经济损失费最少的调运方案。最少的调运方案。实例1 化肥的供应与销售第第13页页 A B C年产量(万吨)甲 5 1 7 10 乙 6 4
8、6 80 丙 3 2 5 15销量(万吨)75 20 50销地运价产地万元万元/万吨万吨第第14页页问题分析问题分析|总产量为总产量为10+80+15=105,总销量为,总销量为75+20+50=145因为总产量因为总产量总销量,故该问题为产销不平衡的运总销量,故该问题为产销不平衡的运输问题。输问题。|目标函数:总运费与经济损失费之和目标函数:总运费与经济损失费之和|决策变量:从产地运往销地的化肥量决策变量:从产地运往销地的化肥量|约束条件:必须保证约束条件:必须保证A区的需求量,即区的需求量,即A区无损失区无损失费;费;B,C有损失费;三个厂生产的化肥全部运出无有损失费;三个厂生产的化肥全部
9、运出无剩余。剩余。第第15页页 设从甲、乙、丙三个工厂向设从甲、乙、丙三个工厂向A,B,C三个地区运送的三个地区运送的化肥量为化肥量为 总运费与经济损失费总运费与经济损失费之和为之和为 .三个工厂到三地的运费之和记为三个工厂到三地的运费之和记为 销地销地A必须满足需要量,无损失费必须满足需要量,无损失费 销地销地B损失费为损失费为 销地销地C损失费为损失费为|1Z第第16页页模型建立第第17页页 实例2 一般的运输问题|假设某种物资有假设某种物资有m个产地,个产地,n个销地个销地.第第i个产地的个产地的产量为产量为 ;第;第 个产地的需要量为个产地的需要量为 .其中其中 .由产地由产地i到销地
10、到销地j的距离已知为的距离已知为 ,问应如何分配该种物资,使既能满足各地的需,问应如何分配该种物资,使既能满足各地的需要,又使所花费的运输要,又使所花费的运输总吨公里数总吨公里数最少?最少?什么是吨公里数呢?什么是吨公里数呢?吨公里数吨公里数=运载量运载量*运载运载公里数公里数第第18页页模型建立模型建立|用用 表示产地表示产地i供给产地供给产地j的物资数量,设的物资数量,设s为运输为运输的总吨公里数,则上述问题的数学模型为的总吨公里数,则上述问题的数学模型为 对运输问题感兴趣的同学可以对运输问题感兴趣的同学可以查阅相关书籍,例如由前苏联数学查阅相关书籍,例如由前苏联数学家编写的家编写的生产组
11、织与计划中的数生产组织与计划中的数学方法学方法一书提出了这一类问题的一书提出了这一类问题的数学模型和求解方法。数学模型和求解方法。第第19页页一般食谱问题|假定有假定有n种食品,每种食品中含有种食品,每种食品中含有m种营养成分种营养成分.其中:其中:问:应该怎样选配食品,才能保证在满足问:应该怎样选配食品,才能保证在满足m种营种营养成分需要的条件下,使食品总成本养成分需要的条件下,使食品总成本y最低?最低?第第20页页模型建立模型建立第第21页页例例 红星农场要在红星农场要在n块土地块土地 上,种植上,种植m 种作物种作物 ,各块土地的面积、各,各块土地的面积、各种作物计划种植面积和在各块地上
12、的每平种作物计划种植面积和在各块地上的每平方米产量如下表,问方米产量如下表,问 应如何合理安排种植应如何合理安排种植计划,才能使总产量最高计划,才能使总产量最高.这里假设计划播种的种面积等于土地的总面这里假设计划播种的种面积等于土地的总面积,即积,即2.4 作物布局问题作物布局问题第第22页页计划播种面积/平方米 土地面积/平方米土地土地每平产量每平产量/kg作物作物第第23页页问题分析问题分析决策量:各块土地种植某种作物的面积,且非负决策量:各块土地种植某种作物的面积,且非负.目标:总产量最高目标:总产量最高约束:约束:各块土地上种植作物各块土地上种植作物 面积总和面积总和=作物作物 计计划
13、种植面划种植面 积积 ;第第j块土地种植各种作物面积总和块土地种植各种作物面积总和=土地面积土地面积 种植面积非负种植面积非负第第24页页模型建立模型建立这是等式约束这是等式约束第第25页页一一 般般 形形 式式目标函数目标函数约束条件约束条件第第26页页注注 释释第第27页页规规 范范 形形 式式第第28页页标标 准准 形形 式式第第29页页概概 念念第第30页页模模 型型 转转 换换v约束转换约束转换v实例实例v目标转换目标转换v变量转换变量转换第第31页页约约 束束 转转 换换v不等式变等式不等式变等式v不等式变不等式不等式变不等式v等式变不等式等式变不等式第第32页页不不 等等 式式
14、变变 等等 式式松弛变量松弛变量剩余变量剩余变量第第33页页不等式变不等式不等式变不等式第第34页页 例例2.1.3 把问题转化为标准形式把问题转化为标准形式把问题转化为标准形式把问题转化为标准形式第第35页页图图 解解 法法第第36页页例例 解线性规划解线性规划 第第37页页第第38页页注注 释释可能出现的情况可能出现的情况:|可行域是空集可行域是空集|可行域无界无最优解可行域无界无最优解|最优解存在且唯一,则一定在顶点上达到最优解存在且唯一,则一定在顶点上达到|最优解存在且不唯一,一定存在顶点是最优解最优解存在且不唯一,一定存在顶点是最优解第第39页页其他费用其他费用:450元元/千吨千吨
15、 应如何分配水库供水量,公司才能获利最多?应如何分配水库供水量,公司才能获利最多?若水库供水量都提高一倍,公司利润可增加到多少?若水库供水量都提高一倍,公司利润可增加到多少?元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例例例1 1 1 1 自来水输送自来水输送自来水输送自来水输送收入:收入:900元元/千吨千吨 支出支出A:50B:60C:50甲:甲:30;50乙:乙:70;70丙:丙:10;20丁:丁:10;40水水库库供供水水量量(千千吨吨)小小区区基基本本用用水水量量(千千吨吨)小小区区额额外外用用水水量量
16、(千千吨吨)(以天计)(以天计)第第40页页总总供水量:供水量:160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A:50B:60C:50甲:甲:30;50乙:乙:70;70丙:丙:10;20丁:丁:10;40 总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润 =收入收入(900)其它费用其它费用(450)引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C 类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润
17、最大需求约束可以不变需求约束可以不变第第44页页求解求解 OBJECTIVE FUNCTION VALUE 1)88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000
18、 X32 0.000000 20.000000 X33 30.000000 0.000000 这类问题一般称为这类问题一般称为“运输问题运输问题”(Transportation Problem)总利润总利润 88700(元)(元)A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030第第45页页例例2 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 模型 ppt 课件

限制150内