运筹管理4~6章.pptx

1、4. 线性规划在工商管理中的应用,人力资源分配问题 生产计划问题 套裁下料问题 配料问题 投资问题,一般而言，一个经济或管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数 存在着多种方案 要求达到的目标在一定条件下可以实现，这些约束可用线性等式或不等式描述,线性规划建模,1. 人力资源分配问题,例 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数最少?,线性规划建模,解：设xi

2、表示第i班次时开始上班的司机和乘务人员人数。,某企业生产l、2和3三种产品，每种产品需经过三道工序，每件产品在每道工序中的工时定额、每道工序在每周可利用的有效工时和每件产品的利润见下表。问每种产品各生产多少,可使这一周内生产的产品所获利润最大？,2. 生产计划问题,线性规划建模,线性规划及其数学模型,线性规划建模,3. 裁料问题,现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆

3、钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。,线性规划建模,设按方案、下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：,生产某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(假设切割损失不计),解：1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1, y2, y3, 则切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如：y1=2， y2

4、=0 ，则 y3 只能为1，余料为0.1。像这样的非负整数解共有8组，也就是有8种下料方式，如表1.4所示。,2、建立线性规划数学模型。设xj (j=1,2,8)为第 j 种下料方案所用圆钢的根数。,3. 裁料问题,min Z = x1+x2+x3 +x4+x5 +x6+x7 +x8,(x1=10, x2=50, x4=30, 余料16m),线性规划建模,4. 配料问题,例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？,线性规划建模,解：设Xj 表示Bj 种食物用量,4. 配料问题,例：某工厂要用三种原料1,2,3混合调配出不同

5、规格的产品甲、乙、丙，产品的规格要求、产品的单价、每天能供应的原材料数量以及原材料单价如表所示。该厂应该如何安排生产，才能使利润最大？,5、投资问题：某投资公司在第一年初有100万元资金，假设每年都有如下的投资方案：第一年初投入一笔资金，第二年初又继续投入此资金的50%，并从总资金中拿出一笔资金投入到项目中；第三年初就可回收第一年初投入资金的两倍，同时继续追加第二年投入金额的50%，并且还投入一笔资金，一直到整个投资计划完成。问：该投资公司应如何确定投资策略才能使第六年初所拥有的资金最多？,追加投资金额 + 新投资金额 + 保留资金=可利用的资金总额,线性规划建模,第三年：设 x5 为新的投资

6、，x6 为第三年的保留资金；,第四年：设新的投资 x7 ，第四年的保留资金 x8 ；,第五年：设 x9 为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。,第二年： 设x3为第二年新的投资，x4为第二年的保留资金，则：,解：设x1为第一年的投资，x2为第一年的保留资金，则：,x1 + x2 = 100,到第六年初，实有资金总额为x9 + 2x7，整理后得到下列线性规划模型：,max Z = 2x7 + x9,某企业现有资金200万元，计划在今后5年内给A，B，C，D 四个项目投资。根据有关情况的分析得知： 项目A：从第一年到第五年每年年初都可进行投资，当

7、年末就能收回本利110%； 项目B：从第一年到第四年每年年初都可进行投资，次年末能收回本利125%，但是要求每年最大投资额不能超过30万元； 项目C：若投资则必须在第三年年初投资，到第五年末能收回本利140%，但是限制最大投资额不能超过80万元； 项目D：若投资则需在第二年年初投资，到第五年末能收回本利155%，但是规定最大投资额不能超过100万元。 问：应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？,线性规划建模,除了投入与回报之外，还应该考虑每个项目的投资风险。应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在320万的基础上保证其投资的总风险系数为最

8、小？ 下表是预测每万元每次投资的风险指数。,线性规划建模,投资风险,线性规划建模,5. 单纯形法,单纯形法的思路 单纯形表求解,单纯形法解题的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解 （找出更大的目标函数值）,最优解,是,否,循 环,核心是：变量迭代,结束,线性规划的例子,线性规划-标准化,引入变量：s1，s2，s3,提取系数，填入表格：,s.t.,1x1+1 x2+1s1+0s2+0s3 =300,2x1+1 x2+0s1+1s2+0s3 =400,x1 0, x20, si0,0 x1+1x2+0s1+0s2+1s3 =250,初始单纯形表,初始单纯形表,目标系数区,约束

9、条件系数区,右端系数,检验系数区,基变量区,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,0,0,0,0,0,初始单纯形表,50,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,x1,50,x1,50,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,初始单纯形表,表格中，检验系数j全部小于或等于0，根据判断规则，Z值为最优值（Z=27500），其解： X1=50,S2=50,X2=250,S1=S3=0为模型的最优解。,6. 灵敏度分析,单个目标函数系数变动 多个目标函数系数变动 单个

10、右端约束值变动 多个右端约束值变动 约束系数变动 增加变量 增加约束,线性规划模型的确定是以已知常数作为基础的，但在实际问题中，这些数据本身不仅很难准确得到，而且往往还要受到诸如市场价格波动，资源供应量变化，企业的技术改造的因素的影响，因此，当这些数据有一个或多个发生变化时，对已找到的最优解或最优基会产生怎样的影响；或者说这些数据在什么范围内变化，已找到的最优解或最优基不变；以及在原最优解或最优基不在是最优基时，如何用最简单的方法求出新的最优解或最优基。这就是灵敏度分析所要研究的问题。,例 某工厂要生产两种新产品：门和窗。经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一

11、扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。 已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？,最优解为（2，6），Max z3600,问题1：如果目标系数由原来的300元提升到500元，最优解是否会改变？对总利润又会产生怎样的影响? 问题2：如果两个目标系数都发生变化，最优解会不会发生改变？对总利润又会产生怎样的影响? 问题3：如果车间2的可用工时增加2

12、个小时，总利润是否会发生变化？如何改变? 最优解是否会发生变化? 问题4：如果同时改变多个车间的可用工时，总利润是否会发生变化？如何改变? 最优解是否会发生变化? 问题5：如果车间2更新生产工艺，生产一件产品由原来的2小时下降到1.5小时, 最优解是否会发生改变？总利润是否会发生变化？ 问题6：工厂考虑增加一种新产品，总利润是否会发生变化？ 问题7：如果工厂新增加用电限制，是否会改变原最优方案？,单个目标函数系数变动,假定只有一个系数cj改变，其他系数均保持不变的情况下，目标函数系数变动对最优解的影响。 如果当初对产品的单位利润估计不准确，如把它改成500元，是否会影响求得的最优解呢？ 方法1

13、：重新运行“规划求解” 方法2：运用“敏感性报告”寻找允许变化范围,单个目标函数系数变动,方法1：重新运行“规划求解” 当模型参数发生改变时，只要改变模型中相应的参数，再重新运行Excel“规划求解”，对比未改变参数时的结果就可以看出改变参数对最优解的影响。,单个目标函数系数变动,方法2：运用“敏感性报告”寻找允许变化范围 生成“敏感性报告”,单个目标函数系数变动,结果： 最优解没有发生改变，仍然是（2，6） 由于门的单位利润增加了200元，因此总利润增加了 （500300） 2400元。,多个目标函数系数同时变动,假如，以前把产品1的单位利润（300元）估计低了，现在把门的单位利润定为450

14、元；同时，以前把产品2的单位利润（500元）估计高了，现在定为400元。这样的变动，是否会导致最优解发生变化呢？ 方法1：重新运行“规划求解” 方法2：运用“敏感性报告”进行分析,多个目标函数系数同时变动,方法1：重新运行“规划求解”；最优解并没有发生变化,总利润由于门和窗的单位利润的改变相应地改变了 (450300)2(400500)6300,方法2：运用“敏感性报告”进行分析,200C2,系数的变动在允许范围之内，所以最优解不变，但利润改变,多个目标函数系数同时变动,单个约束右端值变动,如果车间2的可用工时增加2个小时，总利润是否会发生变化？如何改变? 最优解是否会发生变化? 方法1：重新

15、运行“规划求解” 方法2：从“敏感性报告”中获得关键信息（影子价格，Shadow Price）,单个约束右端值变动,方法1：重新运行“规划求解”,总利润为3750元，增加了：3750-3600=150元。由于总利润增加了，而目标函数系数不变，所以最优解一定会发生改变，从图中可以看出，最优解由原来的（2，6）变为（1.667，6.5）,单个约束右端值变动,方法2：从“敏感性报告”中获得关键信息 在给定线性规划模型的最优解和相应的目标函数值的条件下，影子价格（Shadow Price）是指约束右端值增加（或减少）一个单位，目标值增加（或减少）的数量,第二个约束条件（车间2的工时约束）的影子价格是1

16、50，说明在允许的范围6，18（即12-6，12+6）内，再增加（或减少）一个单位的可用工时，总利润将增加（或减少）150,多个约束右端值同时变动,将1个小时的工时从车间3移到车间2，对总利润所产生的影响 方法1：重新运行“规划求解” 方法2：运用“敏感性报告”进行分析,多个约束右端值同时变动,方法1：重新运行“规划求解”,总利润增加了3650-3600=50（元），影子价格有效。,多个约束右端值同时变动,方法2：运用“敏感性报告”进行分析 百分之百法则：如果约束右端值同时变动，计算每一变动占允许变动量（允许的增量或允许的减量）的百分比，如果所有的百分比之和不超过100%，那么，影子价格依然有

17、效，如果所有的百分比之和超过100，那就无法确定影子价格是否依然有效，只能通过重新进行规划求解来判断了,多个约束右端值同时变动,在影子价格有效范围内，总利润的变化量可以直接通过影子价格来计算。 比如将车间3的3个工时转移给车间2， 所以，总利润的变化量为,约束条件系数变化,如果车间2更新生产工艺，生产一扇窗户由原来的2小时下降到1.5小时, 最优解是否会发生改变？总利润是否会发生变化？ 重新运行“规划求解”,规划求解后，最优解发生了改变，变成了（2/3，8），总利润也由3600元增加到了4200元。可见，车间2更新生产工艺后，为工厂增加了利润。,增加一个新变量,如果工厂考虑增加一种新产品：防盗

18、门，其单位利润为400元。生产一个防盗门会占用车间1、车间2、车间3各2、1、1工时,总利润是否会发生变化？ 重新运行“规划求解”,最优解 (2,5.5,1）, 最大利润是3750元。可见新产品为工厂增加了100元利润,增加一个约束条件,假定生产两种新产品每件需要消耗电力分别为20kw、10kw，工厂总供电最多为90kw,最优解是否会发生变化? 重新运行“规划求解”,可见电力约束的确限制了新产品门和窗的产量，最优解变成(1.5,6),总利润也相应的下降为3450元。,某工厂用甲、乙、丙三种原材料可生产5种产品，其中有关数据如下，问怎样组织生产可以使工厂获得最大利润？,解 设 xi分别表示为各产

19、品的件数，建立线性规划模型为：,运用excel进行规划求解，得到最优解,得到敏感性报告,1、当c111,c222,c321, 0c421,19 c5时，C值变化对最优解没有影响，但利润会有变化，如果C值超出变化范围就得重新运行“规划求解”计算。 2、资源限量7.5b110.5，21.5b2 ，20b322.667，B值变化对最优解没有影响，但利润会有变化，如果B值超出变化范围就得重新运行“规划求解”计算。 3、在变动范围内，约束值每变动1个单位，对最优解没有影响，但利润增加 1个影子价格,1、当c111,c222,c321, 0c421,19 c5时，数值变化对最优解没有影响，但利润会有变化，

20、超出范围就得重新计算。 2、资源限量7.5b110.5，21.5b2 ，20b322.667，数值变化对最优解没有影响，但利润会有变化，超出范围就得重新计算。,雅致家具厂生产计划优化问题,雅致家具厂生产4种小型家具，由于该四种家具具有不同的大小、形状、重量和风格，所以它们所需要的主要原料（木材和玻璃）、制作时间、最大销售量与利润均不相同。该厂每天可提供的木材、玻璃和工人劳动时间分别为600单位、1000单位与400小时，详细的数据资料见下表。,应如何安排这四种家具的日产量，使得该厂的日利润最大？,表1 雅致家具厂基本数据,解：依题意，设置四种家具的日产量分别为决策变量,约束条件为三种资源的供应量限制和产品销售量限制。,据此，列出下面的线性规划模型：,，目标要求是日利润最大化，,其中,分别为