线性规划模型.pptx

《线性规划模型.pptx》由会员分享，可在线阅读，更多相关《线性规划模型.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 线性规划模型2.1 拟订生产计划问题拟订生产计划问题2.2 运输问题运输问题2.3 食谱问题食谱问题2.4 作物布局问题作物布局问题2.5 配料问题配料问题2.6 LP模型的一般形式与标准形式模型的一般形式与标准形式2.7 LP模型的几何解释和图解法模型的几何解释和图解法2.8 一些实例一些实例第1页/共59页实例1某化工厂生产四种化工产品 ,每种产品生产1吨消耗的工时、能源和获得的利润如表2-1所示 表2-1 生产1t产品的消耗和收益 1 8 5 2利润/万元 0.1 0.5 0.3 0.2能耗/t标准煤 75 380 250 100工时/h 产品第2页/共59页问 题 已知该厂明年

2、的工时限额为18480h，能耗限额为100t标准煤，欲使该厂明年的总利润最高，请确定定各种产品的生产数量，试建立数学模型。第3页/共59页模型假设四种产品的每吨获利是与它们各自的生产数量无关的常数；每种产品生产一吨消耗的工时，能耗是与各种产品的产量无关的常数。四种产品每吨的获利是与它们相互间产量无关的常数。每种产品所消耗的工时，能耗是与它们相互间产量无关的常数。生产产品的数量可以是任意实数。第4页/共59页问题分析决策变量：四种产品明年的生产数量目标：该厂明年的总利润最大 利润函数：约束条件：工时限制 能耗限制 蕴含约束：四种产品产量非负 第5页/共59页模型建立由于目标函数 是变量 的线性函

3、数，约束条件是的线性不等式，所以该问题为线性规划问题，简写为LP.第6页/共59页线性规划问题的特征比例性 可加性 连续性 xi对目标函数的“贡献”与xi取值成正比 xi对约束条件的“贡献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 第7页/共59页实例2一般的拟定生产计划问题|例2 设有m种资源：，拟生产n种产品：.用表示生产1个单位第j种产品所需要的第i种资源的数量，用 表示第i种资源的使用限额，用 表示销售一个单位的第j种产品获得的利润，用 表示第j种产品的生产数量，则就代表一个生产计划，我们的问题是：要设法安排一个生产

4、计划，使该厂获得的总利润最高。第8页/共59页问题分析|决策变量:n种产品的生产数量|目标：该厂获得的总利润最大 利润函数：|约束条件：资源 的使用限额 蕴含约束：n种产品产量非负第9页/共59页模型建立 当拟订的生产计划规模较大时,我们通常采用向量、矩阵记号，则该模型变成什么样了呢？第10页/共59页|设有3个化肥厂：甲、乙、丙，供应3个地区:A,B,C化肥，各厂的化肥年产量、各地区需求量及各厂到3个地区的单位运价见表所示；假设各地区需求量没有满足会造成经济损失:B,C区的单位损失分别为3万元/万吨和2万元/万吨，A区的需求量必须保证，求使得总运费和经济损失费最少的调运方案。实例1 化肥的供

5、应与销售第11页/共59页 A B C年产量（万吨）甲 5 1 7 10 乙 6 4 6 80 丙 3 2 5 15销量（万吨）75 20 50销地运价产地万元/万吨第12页/共59页问题分析总产量为10+80+15=105，总销量为75+20+50=145因为总产量总销量，故该问题为产销不平衡的运输问题。目标函数：总运费与经济损失费之和决策变量：从产地运往销地的化肥量约束条件：必须保证A区的需求量，即A区无损失费；B,C有损失费；三个厂生产的化肥全部运出无剩余。第13页/共59页 设从甲、乙、丙三个工厂向A,B,C三个地区运送的化肥量为 总运费与经济损失费之和为 .三个工厂到三地的运费之和记

6、为 销地A必须满足需要量，无损失费 销地B损失费为 销地C损失费为|1Z第14页/共59页模型建立第15页/共59页 实例2 一般的运输问题|假设某种物资有m个产地，n个销地.第i个产地的产量为 ；第 个产地的需要量为 .其中 .由产地i到销地j的距离已知为 ，问应如何分配该种物资，使既能满足各地的需要，又使所花费的运输总吨公里数最少？什么是吨公里数呢？吨公里数=运载量*运载公里数第16页/共59页模型建立用 表示产地i供给产地j的物资数量，设s为运输的总吨公里数，则上述问题的数学模型为 对运输问题感兴趣的同学可以查阅相关书籍，例如由前苏联数学家编写的生产组织与计划中的数学方法一书提出了这一类

7、问题的数学模型和求解方法。第17页/共59页一一般食谱问题般食谱问题|假定有n种食品，每种食品中含有m种营养成分.其中：问：应该怎样选配食品，才能保证在满足m种营养成分需要的条件下，使食品总成本y最低？第18页/共59页模型建立第19页/共59页例 红星农场要在n块土地 上，种植m 种作物 ，各块土地的面积、各种作物计划种植面积和在各块地上的每平方米产量如下表，问 应如何合理安排种植计划，才能使总产量最高.这里假设计划播种的种面积等于土地的总面积，即2.4 作物布局问题第20页/共59页计划播种面积/平方米 土地面积/平方米土地每平产量/kg作物第21页/共59页问题分析决策量：各块土地种植某

8、种作物的面积，且非负.目标：总产量最高约束：各块土地上种植作物 面积总和=作物 计划种植面 积 ；第j块土地种植各种作物面积总和=土地面积 种植面积非负第22页/共59页模型建立这是等式约束第23页/共59页一 般 形 式目标函数约束条件第24页/共59页注 释第25页/共59页规 范 形 式第26页/共59页标 准 形 式第27页/共59页概 念第28页/共59页模 型 转 换v约束转换v实例v目标转换v变量转换第29页/共59页约 束 转 换v不等式变等式v不等式变不等式v等式变不等式第30页/共59页不 等 式 变 等 式松弛变量剩余变量第31页/共59页不等式变不等式第32页/共59页

9、 例2.1.3 把问题转化为标准形式第33页/共59页图 解 法第34页/共59页例 解线性规划 第35页/共59页第36页/共59页注 释可能出现的情况可能出现的情况：可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是最优解第37页/共59页其他费用:450元/千吨 应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例例例例1 1 1 1 自来水输送自来水输送自来水输送自来水输送收入：900元/千吨 支

10、出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）第38页/共59页总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40 总需求量(300)每个水库最大供水量都提高一倍利润 =收入(900)其它费用(450)引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C 类似处理问题讨论 确定送水方案使利润最大需求约束可以不变第42页/共59页求解 OBJEC

11、TIVE 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 X32 0.000000 20.000000 X33 30.000

12、000 0.000000 这类问题一般称为“运输问题”(Transportation Problem)总利润 88700（元）A(100)B(120)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)4010050305030第43页/共59页例2 加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到 30元/公斤，应否改

13、变生产计划？每天：第44页/共59页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)时间480小时 至多加工100公斤A1 50桶牛奶 每天第45页/共59页模型分析与假设 比例性 可加性 连续性 xi对目标函数的“贡献”与xi取值成正比 xi对约束条件的“贡献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 A1,A

14、2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数 线性规划模型第46页/共59页模型求解 图解法 x1x20ABCDl1l2l3l4l5约束条件目标函数 Z=0Z=2400Z=3600z=c(常数)等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得。第47页/共59页模型求解 软件实现 LINDO 6.1 max

15、72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No20桶牛奶

16、生产A1,30桶生产A2，利润3360元。第48页/共59页结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x

17、1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）第49页/共59页结果解释 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量 原料

18、增加1单位,利润增长48 时间增加1单位,利润增长2 加工能力增长不影响利润影子价格 35元可买到1桶牛奶，要买吗？35 48,应该买！聘用临时工人付出的工资最多每小时几元？2元！第50页/共59页RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE

19、RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最优解不变时目标函数系数允许变化范围 DO RANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x2系数范围(48,72)A1获利增加到 30元/千克，应否改变生产计划 x1系数由24 3=72增加为303=90，在允许范围内 不变！(约束条件不变)第5

20、1页/共59页结果解释 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.66

21、6667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围 原料最多增加10 时间最多增加53 35元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)第52页/共59页例3 奶制品的生产销售计划 在例2基础上深加工1桶牛奶 3千克A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 0.8千克B12小时,3元1千克获利44元/千克 0.75千克B22小时,3元1千克获利32元/千克 制订生产计划，使每天净利润最大 30元可增加1桶牛奶，3元可增

22、加1小时时间，应否投资？现投资150元，可赚回多少？50桶牛奶,480小时 至多100公斤A1 B1，B2的获利经常有10%的波动，对计划有无影响？第53页/共59页1桶牛奶 3千克 A1 12小时 8小时 4千克 A2 或获利24元/千克 获利16元/kg 0.8千克 B12小时,3元1千克获利44元/千克 0.75千克 B22小时,3元1千克获利32元/千克 出售x1 千克 A1,x2 千克 A2，X3千克 B1,x4千克 B2原料供应 劳动时间 加工能力 决策变量 目标函数 利润约束条件非负约束 x5千克 A1加工B1，x6千克 A2加工B2附加约束 第54页/共59页模型求解 软件实现

23、 LINDO 6.1 OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)

24、0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2DO RANGE(SENSITIVITY)ANALYSIS?No第55页/共59页 OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK

25、OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2结果解释每天销售168 千克A2和19.2 千克B1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1 除加工能力外均为紧约束第56页/共59页结果解释 OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCE

26、D COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000增加1桶牛奶使利润增长3.1612=37.92增加1小时时

27、间使利润增长3.26 30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）第57页/共59页结果解释B1,B2的获利有10%的波动，对计划有无影响 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE(SENSITIVITY)ANALYSIS?YesB1获利下降10%，超出X3 系数允许范围B2获利上升10%，超出X4 系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。第58页/共59页感谢您的观看！第59页/共59页