第二章-线性规划基本概念-精选课件.ppt

1、 任何有用的资源都不是取之不尽，用之不竭的。水和空气都是这样。既然如此，人类每一个组织的管理都必须面对向不同的活动分配有限资源的问题。那么，如何分配才能达到组织的目标，就是一个经常需要面对的问题，而线性规划（Linear Programming）使得作出这些决策成为可能。l确定潘德罗索工业公司的产品组合l联合航空公司的员工排程lCitgo石油的供应、配送和营销规划l茫然l惊奇l冲动问题头绪较多，不 知道如何下手线性规划究竟是什么样子？有这 么神奇的“功效”我得尽快搞清楚这个东西，它太诱人了l公司背景资料 Wyndor玻璃制品公司有三个工厂工厂1：生产铝框和硬制件工厂2：生产木框工厂3：生产玻璃

2、和组装窗和门他们的新产品开发部最近开发出两种新产品：8英尺的铝框玻璃门 4英尺6英尺的双把木框窗 由于公司某些产品销售量的下降，公司高层决定调整公司的生产线。即停掉一些产品的生产。但是否将腾出来的一部分生产能力来生产这两种新产品还需要作进一步的论证。公司管理部门现在需要考虑下列两个问题：1.公司是否应该生产这两个新产品？2.如果生产，两个新产品的生产组合如何？带着这些问题，公司总裁召集有关人员开会讨论。结果是，第一个问题作出了肯定的决策，而第二个问题，则需要管理小组利用管理科学方法先作出建议，而总裁的要求是我们需要对公司而言赢利最大的两种产品的组合。l定义问题和收集数据 问题：两种新产品的生产

3、率（每周生产数量）的哪种组合能最大化两种产品的总利润 所需要的数据：1.每家工厂的生产能力；2.生产每一产品各需要每家工厂多少生产能力；3.每一产品的单位利润。生产每个单位所需要的时间工厂门窗每周可得时间1231小时03小时02小时2小时4小时12小时18小时单位利润（美元）$300$500l如果Wyndor玻璃制品公司的产品组合问题在以上条件下就能够解决的话，你是否觉得潘德罗索工业公司的产品组合问题也有些头绪了?l对于潘德罗索工业公司的产品组合问题，你确定的目标是什么?你需要哪些数据？lExcel工作表伟恩德公司问题模型.xlsl线性规划代数模型的建立方法 1.设出决策变量；2.写出目标函数

4、；3.确定约束条件。对Wyndor公司问题而言，设D为每周应生产的门数，W为每周应生产的窗数，那么，目标函数就是P=300D+500W,而约束条件则为：l我们的目的就是确定D和W的值，在（）条件下，使得目标函数P300D500W达到最大。0,018231224WDWDWDl代表特定活动程度决策的一个代数变量，称为决策变量；l由决策变量的线性表达式表达的绩效称为目标函数；l决策变量须受到的限制（通常为关于决策变量的线性等式或不等式）称为约束条件；l决策变量的任何一个取值称为模型的一个解；l满足所有约束条件的解，称为可行解；l所有的可行解构成的集合，称为可行域；l是目标函数达到最大的可行解，称为最

5、优解。l 某工厂有一批长度为5米的钢管（数量充分多），为制造零件的需要，要将它们截成长度分别为1400毫米，950毫米，650毫米的管料，而且这三种管料要按2：4：1的比例配套生产，就是说每制造一个成品分别需要2根1400毫米，4根950毫米，1根650毫米的管料。l把一根一定长度的钢管截成n段需要的管料时，一般要产生残料，例如，把5米的管料截成1400毫米的3根和650毫米的1根，要剩残料150号毫米；如果截成1400毫米的2根和950毫米的两根剩残料300毫米。现在的问题是如何截分才能使剩下来的三种管料，既能配套，又使残料最少。8种不错的截法：截 法1 2 3 4 5 6 7 8 长度14

6、00mm950mm650mm3 2 2 1 1 0 0 00 2 0 3 1 5 3 11 0 3 1 4 0 3 6残料（mm）150 300 250 100 50 250 200 150 用xi(i=1,2,，8)表示采用第i种截法的钢管数目，那么截出1400mm的管料数目是：3x1+2x2+2x3+x4+x5 截出900mm的管料数目是：2x2+3x4+x5+5x6+3x7+x8 截出650mm的管料数目是：x1+3x3+x4+4x5+3x7+6x8 根据配套要求，它们应分别等于2a,4a,a(a是套数)，我们先让a等于某一个正整数，例如a=1,求出xi以后，如果xi是分数，就乘以xi的

7、分母的最小公倍数，这时候残量 S=150 x1+300 x2+250 x3+100 x4+50 x5+250 x6+200 x7+150 x8 246240DW可行域最优解（2，6）P=3600P=3000P=1500l建立问题的Excel电子表格；l在工具菜单中选择“规划求解”得到“规划求解参数”对话框；l确定目标单元格（键入或点击），选择最大值（或最小值），确定可变单元格（键入或点击），添加约束条件（键入或点击）；l点及“选项”，选择“假定线性模型”和“假定非负条件”；l点及“规划求解参数”对话框中的“求解”，即可得到线性规划的最优解（存在的话）。l利博公司生产家用的清洁产品，这是一个高度

8、竞争的市场，为此，公司高层决定通过广告增加三种主要产品的销售量，这三种主要产品是：1.一种喷雾去污剂 2.一种新的液体洗涤剂 3.一种成熟的洗衣粉管理部门的目标是以最低的总成本来达到预定的产品销售量的增加值。l管理部门选定广告的媒体是电视和印刷出版物，且设定了广告的最低目标：1.喷雾去污剂必许再增加3的市场份额；2.新的液体洗涤剂必须在西低级市场中获得18的份额；3.洗衣粉占洗涤剂市场的份额必须增加4。通过市场调查，可得到一个单位电视广告的费用为100万元，一个单位印刷广告的费用为200万元。此外，问题中的其它数据也是可以得到的（尽管都是估计值）。l利博公司广告组合问题的数据每单位广告增加的市场份额产品电视印刷出版物需要最小的增加量去污剂液体洗涤剂洗衣粉0311243184单位成本100万美元200万美元Excel工作表利博公司广告组合问题模型.xls设TV和PM分别是公司应做的电视和印刷出版物广告的数量，C为总成本，则有利博公司广告组合问题的代数模型0,0%4%4%1%18%2%3%3%1.2minPMTVPMTVPMTVPMtsPMTVC3TV+2PM=18可行域PM=3-TV+4PM=4TVPMO