《01 管理运筹学问题01.ppt》由会员分享，可在线阅读，更多相关《01 管理运筹学问题01.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学运筹学 管理决策问题管理决策问题12/29/20221Chapter 1 线性规划线性规划Linear Programming Page 2【例例1.1】最最优优生生产产计计划划问问题题。某某企企业业在在计计划划期期内内计计划划生生产产甲甲、乙乙、丙丙三三种种产产品品。这这些些产产品品分分别别需需要要要要在在设设备备A、B上上加加工工，需需要要消消耗耗材材料料C、D，按按工工艺艺资资料料规规定定，单单件件产产品品在在不不同同设设备备上上加加工工及及所所需需要要的的资资源源如如表表1.1所所示示。已已知知在在计计划划期期内内设设备备的的加加工工能能力力各各为为200台台时时，可可供供材材料
2、料分分别别为为360、300公公斤斤；每每生生产产一一件件甲甲、乙乙、丙丙三三种种产产品品，企企业业可可获获得得利利润润分分别别为为40、30、50元元，假假定定市场需求无限制。市场需求无限制。企企业业决决策策者者应应如如何何安安排排生生产产计计划划，使使企企业业在在计计划划期期内内总总的的利润收入最大？利润收入最大？一、生产计划的问题一、生产计划的问题12/29/20222Chapter 1 线性规划线性规划Linear Programming Page 3 产品产品 资源资源 甲甲 乙乙 丙丙现有资源现有资源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1
3、 360材料材料D 2 3 5 300利润（元利润（元/件）件）40 30 50表表1.1 产品资源消耗产品资源消耗12/29/20223Chapter 1 线性规划线性规划Linear Programming Page 4【解解】设设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型分别为甲、乙、丙三种产品的产量数学模型为：为：产品产品 资源资源 甲甲 乙乙 丙丙现有资现有资源源设备设备A 3 1 2 200设备设备B 2 2 4 200材料材料C 4 5 1 360材料材料D 2 3 5 300利润（元利润（元/件）件）40 30 50最优解最优解X=(50,30,10);Z=340
4、012/29/20224Chapter 1 线性规划线性规划Linear Programming Page 5【例例1.2】某某商商场场决决定定：营营业业员员每每周周连连续续工工作作5天天后后连连续续休休息息2天天，轮流休息。根据统计，商场每天需要的营业员如表轮流休息。根据统计，商场每天需要的营业员如表1.2所示。所示。表表1.2 营业员需要量统计表营业员需要量统计表商场人力资源部应如何安排每天的上班人数，使商场总的营业员商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。最少。星期星期需要人数需要人数星期星期需要人数需要人数一一300五五480二二300六六600三三350日日55
5、0四四400二、人力资源分配的问题二、人力资源分配的问题12/29/20225Chapter 1 线性规划线性规划Linear Programming Page 6【解解】设设xj(j=1，2，7)为休息为休息2天后星期一到星期日开始上天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为班的营业员，则这个问题的线性规划模型为 星星期期需要需要人数人数星星期期需要需要人数人数一一300五五480二二300六六600三三350日日550四四40012/29/20226Chapter 1 线性规划线性规划Linear Programming Page 7 1 1 X1X10 0 C1C14
6、04404=3003001041042 2 X2X26767 C2C2301301=3003001 13 3 X3X3146146 C3C3350350=3503500 04 4 X4X4170170 C4C4400400=4004000 05 5 X5X59797 C5C5480480=4804800 06 6 X6X6120120 C6C6600600=6006000 07 7 X7X71717 C7C7550550=5505500 0最优解：最优解：Z617（人）人）12/29/20227Chapter 1 线性规划线性规划Linear Programming Page 8【例例1.3】
7、某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7（m），），这些轴需要用同一种圆钢来做，圆钢长度为这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要现在要制造制造1000辆汽车，最少要用多少圆钢来生产这些轴？辆汽车，最少要用多少圆钢来生产这些轴？【解解】这是一个条材下料问题这是一个条材下料问题，设切口宽度为零，设切口宽度为零。设一根圆钢切割成甲、设一根圆钢切割成甲、乙、丙三种轴的根数分别为乙、丙三种轴的根数分别为y1，y2，y3,则切割方式可用不等式则切割方式可用不等式 1.5y1+y2+0.7y34
8、表示，表示，求这个不等式关于求这个不等式关于y1，y2，y3的非负整数解。象这样的非负整数解共有的非负整数解。象这样的非负整数解共有10组，组，也就是有也就是有10种下料方式，如表种下料方式，如表1.3所示。所示。三、合理用料问题三、合理用料问题12/29/20228Chapter 1 线性规划线性规划Linear Programming Page 9 方案方案规格规格 1234 5678910需求量需求量y1(1.5m)221 11 0 00001000y2(1m)102 10 4 32101000y3(0.7m)010 23 0 12451000余料余料（m）00.30.5 0.1o.4
9、00.30.60.20.5表表13 下料方案下料方案12/29/20229Chapter 1 线性规划线性规划Linear Programming Page 10 设设xj(j=1,2,10)为为第第j种种下下料料方方案案所所用用圆圆钢钢的的根根数数。则则用用料料最最少数学模型少数学模型为为为为:方方案案规格规格 1234 5678910需求量需求量y1 221 11 0 00001000y2 102 10 4 32101000y3 010 23 0 12451000余料（余料（m）00.30.5 0.1o.4 00.30.60.20.512/29/202210Chapter 1 线性规划线性
10、规划Linear Programming Page 11 注意注意求下料方案时应注意，余料不能超过最短毛求下料方案时应注意，余料不能超过最短毛坯的长度；最好将毛坯长度按降的次序排坯的长度；最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的，不能遗漏了方案长的，最后切割最短的，不能遗漏了方案。如果方案较多，用计算机编程排方案，。如果方案较多，用计算机编程排方案，去掉余料较长的方案，进行初选。去掉余料较长的方案，进行初选。12/29/202211Chapter 1 线性规划线性规划Linear Programming Page 1
11、2 1 1 X1X15005002 2 X2X20 03 3 X3X30 04 4 X4X40 05 5 X5X50 06 6 X6X662.562.57 7 X7X70 08 8 X8X80 09 9 X9X92502501010 X10X100 0Z812.512/29/202212Chapter 1 线性规划线性规划Linear Programming Page 13【例例1.4】某某钢钢铁铁公公司司生生产产一一种种合合金金，要要求求的的成成分分规规格格是是：锡锡不不少少于于28%，锌锌不不多多于于15%，铅铅恰恰好好10%，镍镍要要界界于于35%55%之之间间，不不允允许许有有其其他他
12、成成分分。钢钢铁铁公公司司拟拟从从五五种种不不同同级级别别的的矿矿石石中中进进行行冶冶炼炼，每每种种矿矿物物的的成成分分含含量量和和价价格格如如表表1.4所所示示。矿矿石石杂杂质质在在治治炼炼过过程程中中废废弃弃，现现要要求求每每吨吨合合金金成成本本最最低低的的矿矿物物数数量量。假假设设矿矿石石在在冶冶炼过程中，合金含量没有发生变化。炼过程中，合金含量没有发生变化。表表1.4 矿石的金属含量矿石的金属含量 合金合金矿石矿石锡锡%锌锌%铅铅%镍镍%杂质杂质费用（元费用（元/t）125101025303402400030302603015520601804202004020230585151755
13、190四、配料问题四、配料问题12/29/202213Chapter 1 线性规划线性规划Linear Programming Page 14 解解:设设生产一单位合金需要第生产一单位合金需要第j 种矿石数量为种矿石数量为xj（j=1,2，5），），则得到下列线性规划模型则得到下列线性规划模型 12/29/202214Chapter 1 线性规划线性规划Linear Programming Page 15 注意，矿石在实际冶炼时金属含量会发生变化，注意，矿石在实际冶炼时金属含量会发生变化，建模时应将这种变化考虑进去，有可能是非线性关系。建模时应将这种变化考虑进去，有可能是非线性关系。配料问题也
14、称配方问题、营养问题或混合问题，配料问题也称配方问题、营养问题或混合问题，在许多行业生产中都能遇到。在许多行业生产中都能遇到。12/29/202215Chapter 1 线性规划线性规划Linear Programming Page 16 1 1 X1X10 02 2 X2X20.33330.33333 3 X3X30 04 4 X4X40.58330.58335 5 X5X50.66670.6667最优解：最优解：Z=347.512/29/202216Chapter 1 线性规划线性规划Linear Programming Page 17【例例1.5】。某某投投资资公公司司在在第第一一年年有
15、有200万万元元资资金金，每每年年都都有有如如下下的的投投资资方方案案可可供供考考虑虑采采纳纳：“假假使使第第一一年年投投入入一一笔笔资资金金，第第二二年年又又继继续续投投入入此此资资金金的的50%，那那么么到到第第三三年年就就可可回回收收第第一一年年投投入入资资金金的的一一倍倍金金额额”。投资公司决定最优的投资策略使第六年所掌握的资金最多。投资公司决定最优的投资策略使第六年所掌握的资金最多。【解解】设设 x1：第一年的投资；第一年的投资；x2：第一年的保留资金第一年的保留资金 x3：第二年新的投资；第二年新的投资；x4：第二年的保留资金第二年的保留资金 x5：第三年新的投资；第三年新的投资；
16、x6：第三年的保留资金第三年的保留资金 x7：第四年新的投资第四年新的投资 x8：第四年的保留资金第四年的保留资金 x9：第五年的保留资金第五年的保留资金 五、投资问题五、投资问题12/29/202217Chapter 1 线性规划线性规划Linear Programming Page 18 第五年：第五年：(x7/2+x9)=x8+2x5第二年：第二年：(x1/2+x3)+x4=x2第三年第三年:(x3/2+x5)+x6=x4+2x1第四年：第四年：(x5/2+x7)+x8=x6+2x3到第六年实有资金总额为到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型整理后得到下列线性规划
17、模型 第一年：第一年：x1+x2=200(万元万元)12/29/202218Chapter 1 线性规划线性规划Linear Programming Page 19 1.1 线性规划的数学模型线性规划的数学模型 Mathematical Model of LP1 1 X1X155.284655.28462 2 X2X2144.7155144.71553 3 X3X3117.0732117.07324 4 X4X40 05 5 X5X552.032552.03256 6 X6X60 07 7 X7X7208.1301208.13018 8 X8X80 09 9 X9X90 0最优解：最优解：Z
18、416.26万元万元x1：第一年的投资；第一年的投资；x2：第一年的保留资金第一年的保留资金 x3：第二年新的投资；第二年新的投资；x4：第二年的保留资金第二年的保留资金 x5：第三年新的投资；第三年新的投资；x6：第三年的保留资金第三年的保留资金 x7：第四年新的投资第四年新的投资 x8：第四年的保留资金第四年的保留资金 x9：第五年的保留资金第五年的保留资金 12/29/202219Chapter 1 线性规划线性规划Linear Programming Page 20【例例1.6】某某产产品品由由2件件甲甲、3件件乙乙零零件件组组装装而而成成。两两种种零零件件必必须须经经过过设设备备A、
19、B上上加加工工，每每件件甲甲零零件件在在A、B上上的的加加工工时时间间分分别别为为5分分钟钟和和9分分钟，每件乙零件在钟，每件乙零件在A、B上的加工时间分别为上的加工时间分别为4分钟和分钟和10分钟。分钟。现现有有2台台设设备备A和和3台台设设备备B，每每天天可可供供加加工工时时间间为为8小小时时。为为了了保保持持两两种种设设备备均均衡衡负负荷荷生生产产，要要求求一一种种设设备备每每天天的的加加工工总总时时间间不不超超过过另另一一种设备总时间种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大。小时。怎样安排设备的加工时间使每天产品的产量最大。六、均衡配套生产问题六、均衡配套生产问题
20、12/29/202220Chapter 1 线性规划线性规划Linear Programming Page 21 设备设备A、B每天加工工时的约束为每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备要求一种设备每台每天的加工时间不超过另一种设备1小时的约束小时的约束为为【解解】设设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是为每天加工甲、乙两种零件的件数，则产品的产量是12/29/202221Chapter 1 线性规划线性规划Linear Programming Page 22 目标函数线性化。目标函数线性化。约束线性化。将绝对值约束写成两个不等式约束线性化。将绝
21、对值约束写成两个不等式产品的产量产品的产量 y 等价于等价于12/29/202222Chapter 1 线性规划线性规划Linear Programming Page 23 整理得到线性规划模型整理得到线性规划模型 12/29/202223Chapter 1 线性规划线性规划Linear Programming Page 24 1.1.2 线性规划的一般模型线性规划的一般模型一一般般地地，假假设设线线性性规规划划数数学学模模型型中中，有有m个个约约束束，有有n个个决决策策变变量量xj,j=1,2,n，目目标标函函数数的的变变量量系系数数用用cj表表示示,cj称称为为价价值值系系数数。约约束束条条件件的的变变量量系系数数用用aij表表示示，aij称称为为工工艺艺系系数数。约约束束条条件件右右端端的的常常数数用用bi表表示示，bi称称为为资资源源限限量量。则则线线性性规规划划数数学学模模型型的的一一般般表表达达式可写成式可写成 为了书写方便，上式也可写成：为了书写方便，上式也可写成：12/29/202224Chapter 1 线性规划线性规划Linear Programming Page 25 在实际中一般在实际中一般 xj0,但有时但有时 xj0 或或 xj 无无符号限制。符号限制。12/29/202225