1、线性规划应用案例板材下料优化方法案例本案例以上海某柴油机厂某车间某年某月所需3种2mm厚度的板材零件下料为例，说明线性规划在下料中的应用及其在提高材料利用率方面所能产生的显著经济效益。同时，该案例所介绍的工作流程还是一种非常简单实用、便于操作、效果良好的板材下料优化方法，可供各企业在生产中参考运用。一板材下料优化方法的特点及其工作流程用线性规划求解最优下料方案，通常要求首先设计出所有可行合理的下料方式，然后建立LP模型求解最优下料方案。由于板材下料是典型的二维下料，每一种下料方式对应一张排料图，在零件种类较多的情况下，要绘制出所有可行且合理的排料图，不仅工作量非常巨大，而且也是不现实的。为减少
2、绘制排料图的工作量，同时又能达到良好的效果，我们在此给出了一种高效的板材下料优化方法的工作流程。该工作流程有如下特点：1.对绘制排料图的要求不高。开始时，只需选作少量包含各种零件且材料利用率较高的排料图，这不仅可简化绘图工作量，还可简化模型。2.对所得最优解进行最优化后分析。若初始最优解效果不理想，则通过有针对性地再增绘少量排料图后重新求解，通常就可达到事半功倍的效果（该步骤属于将在第十一章介绍的敏感性分析中的“增加新的决策变量”，但我们是用计算机求解，故可不涉及敏感性分析的概念）。3.通常板材下料问题中的变量应当是整数，若采用整数规划求解，则显然会使材料利用率降低。这里我们先采用线性规划求解
3、，对得到的最优解通过舍去小数部分取整，对取整后的零件短缺数，再绘制少量排料图解决。此“取整修正”方法可比使用整数变量求解得到更高的材料利用率。图1 板材下料优化方法工作流程二实际操作中的几点注意事项1.绘制排料图时的注意事项为简化排料图的绘制，排料前应先将零件进行分类，一般可分为以下三类：（1）零件边长大于钢板短边的一类。此类零件在钢板上只有一种排法，对材料利用率影响较大，应注意利用余料安排其他尺寸较小的零件。（2）零件两边均小于钢板短边的一类。此类零件排料组合情况较多，应注意不同零件的搭配。（3）零件尺寸较小、或某边长与钢板某边长成倍比关系的一类，此类零件单一下料利用率高。绘制排料图时，应先
4、考虑第一类零件，其次搭配好第二类零件，最后将第三类零件作为余料的填充件，数量较大的第三类零件则还应绘制单一下料图。2简化模型的方法在下料问题的LP模型中，每种零件对应一个约束条件，当一批下料任务中零件种类较多时，不仅会使排料工作复杂化，而且LP模型也会相应复杂，此时可按以下方法进行简化处理。 （1）对尺寸不大且数量较少的零件，在排料时可暂不考虑，它们通常可在取整修正阶段一起解决。 （2）对数量相同，且某边长也相同或相近的两种或多种零件，可组合成一种“新零件”进行排料和建模。三. 应用案例上海某柴油机厂某月需要3种2mm厚的板材零件，其工艺尺寸、需要量和单一下料利用率等数据见表1。表1 零件尺寸
5、、需要量和单一下料利用率材料尺寸（mm）零件号零件尺寸（mm）需要量每张钢板可下料数钢板需要量单一下料利用率%1000200021#260258500212469.882#240257.6600282284.313#840195250112389.02合 计6980.86可见，如果采用以往的单一下料方法，则这三种零件总共需要69张钢板，总的材料利用率仅为80.86%。下面，我们采用上述工作流程进行优化。1. 选作排料图图2是选作的4张排料图，分别用X1、X2、X3、X4 表示；表9.10给出了各种排料方式下每张钢板可切割的零件数。表2 各种排料方式下每张钢板可得零件数零件x1x2x3x4需要量
6、1#210005002#028406003#211011250 2. 建立LP模型并求最优解设x1、x2、x3、x4 分别为上述各种排料方式的切割钢板数，目标是所耗用的钢板最少。由表2，可得LP模型为 min x0 = x1 + x2 + x3 + x4 21x1 500s.t. 28x2 + 4x3 600 2x1 + x2 +10x3 +11x4 250 x1、x2 、 x3 、x4 0用Excel软件求解，可得最优解为x0* = 60.973，x1* = 23.810，x2* =18.806，x3* =18.357，x4* = 0 即按排料图x1切割24张、按x2和x3各切割19张，可满
7、足3种零件的需求，总共需62张钢板，可比单一下料方式少用7张钢板，材料利用率提高到89.99%，但材料利用率仍然偏低，效果还不够理想。 3. 下料方案的最优化后分析板材下料问题LP模型最优解的效果取决于所绘制的排料图。由于该方法一开始只要求选作若干排料图，因此其初始最优解的效果往往是欠佳的，但这一缺陷可在最优化后分析阶段弥补。获得初始最优解后，首先应计算其材料利用率，若效果欠佳，则一般有以下两个原因： （1）最优解中含有某些材料利用率较低的排料图； （2）各零件在排料图中的数量配比不当（反映在最优解中就是存在较大的剩余变量）。出现上述情况时，可有针对性地再绘制少量排料图，以它们作为新增变量加入
8、原模型中，重新运算后通常即可得到令人满意的下料方案。本案例中由于3个剩余变量都为0（都是非基变量，在模型中并未给出，这是由于用软件求解并不要求化为标准型），故不存在数量配比不当的问题。进一步分析可知，x1 = 23.81，数量最大，但排料图x1的材料利用率仅为86.81%，可见这是影响材料利用率的主要原因。分析4张排料图后，可发现仅x1中含有1# 零件，显然应对1# 零件重新设计排料图。再看2# 零件，其需求量最大，且与1# 零件有一边长相近，两者的另一边长之和又恰好与钢板短边成倍比（260+240=500），故可将两者组合后绘制一张新的排料图x5 ，见图3。该排料图每张可得1# 和2# 零件
9、各14块，3# 零件1块，材料利用率达98.92%。 将x5 加入模型，用Excel重新求解，可得新的最优解为x0* = 57.609，x2* =0.518，x3* =21.377，x5* =35.714，x1*=x4* = 0经进位取整后，只需59张钢板，比初始最优方案又减少了3张，材料利用率则提高到94.56%，已达到令人满意的效果。 4. 对最优方案的取整修正当最优解中切割方式较多，且钢板总量不是很大时，简单地采用进位取整处理往往会影响材料利用率。下面我们介绍一种简便易行且效果很好的“取整修正法”，步骤如下：（1）对最优解舍去小数部分取整。本案例经取整后得x2 = 0，x3 = 21，x
10、5 = 35 （2）计算零件短缺数，见表3。表3 取整后零件短缺数计算表零件可得到的零件数需求量短缺数1#1435=490500102#421+1435=574600263#1021+135=2452505 （3）对零件短缺数进行套料。通常经取整后的短缺数不会很大，故套料工作量也不会很大。 对于本案例，首先考虑现有排料图。由于x2每张可得2# 零件28块，3# 零件1块，故应取x2 =1。这样就只缺1# 零件10块，3# 零件4块，据此再绘制一张排料图x6 ，见图4，它可裁得1# 零件12块，3# 零件6块，已满足要求。 图3 排料图X5 图4 排料图X6现在已得到最终下料方案：分别按排料图x
11、2、x3、x5、x6 各切割1、21、35、1张，总计耗用58张钢板，比进位取整方法又少用1张，材料利用率则进一步提高到96.19%。仅此3个零件，就比单一下料法节约11张钢板，材料利用率提高了15.33%，其经济效益可见一斑。某金属罐制造厂生产方案的优化案例 一问题的提出 某金属罐制造厂是制造金属罐的专业厂家，其主要产品有A、B、C、D四种型号的金属罐。近年来，产品销售情况良好，市场对这4种产品的需求量很大，且预测结果表明，需求还有进一步扩大的趋势，许多用户还希望能提供更多的不同功能的新产品。此外，现有产品在质量、性能、成本、工艺等方面也存在进一步改善的余地。对此，该厂已做了一些基本的分析，
12、比如对引进新的制罐技术的可行性分析，对目前产品的成本核算及分析等。但对如何优化当前的生产计划，以获得更大的经济效益；企业目前的各项资源配置是否合理；应如何进一步改进生产条件以满足市场需求；是否下决心引进新技术开发新产品等等一系列问题尚缺乏科学的定量分析依据。为适应日趋激烈的市场竞争环境，不断提高企业的竞争能力和赢利能力，该企业决策者决定聘请某高校的定量分析专家协助，对当前和未来的生产计划进行最优化分析。 二案例分析 1产品生产主要过程及其模型的建立该企业生产的A、B、C、D四种金属罐要经过四道工序：第一道工序是冲压下料，金属板材在冲压车间经冲压机冲压，加工成金属罐所需要的各种板材零件；第二道工
13、序是成形加工，在成形车间里把板材零件冲压成符合要求的形状；第三道工序是焊接装配，在焊接车间将各种成形的零件按技术要求焊接装配成为完整的金属罐；最后一道工序是喷漆，装配好的金属罐送到喷漆车间被喷上防火的瓷漆。根据工艺要求及成本核算，各单位产品所需的加工时间、利润及目前可供使用的总工时如表11.3所示。表11.3 单位产品所需加工时间、利润及可利用的工时产品工序ABCD可利用总工时（min/天）冲压1111480成形48252400装配42552000喷漆64843000单位利润（元）96118该厂仅有一台冲压机，每天工作8小时，共计480 min可供加工使用；另有若干条成形、装配、喷漆生产线分属
14、各车间，除承担本厂生产任务外，还承担着科研实验、新产品开发试制等工作，因此这些生产线每天可利用的总工时分别不超过2400 min、2000 min和3000 min。由以上分析，可设x1 为A型金属罐的日产量；x2 为B型金属罐的日产量；x3 为C型金属罐的日产量；x4 为D型金属罐的日产量；并设目标函数为每天的总利润，就可建立日产品计划的线性规划模型如下： max x0 = 9x1+6x2+11x3+8x4 x1+ x2+ x3+ x4480 4x1+8x2+ 2x3 + 5x42400 s.t. 4x1+2x2+5x3+ 5x4 2000 6x1+4x2+8x3+ 4x43000 x1,
15、x2 , x3 , x4 0 2求解最优生产计划 用Excel软件求解该LP问题，图11.2是软件输出的“运算结果报告”。图11.2 运算结果报告由图11.2可知，最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 400，0，70，10，0，610，0，0 ) x0 * = 4450。 其中s1，s2，s3，s4为松弛变量。由软件运行结果可知，为使总利润最大，每天的生产计划应如下安排：A型金属罐400个，C型金属罐70个，D型金属罐10个，不生产B型金属罐，这样日总利润可达4450元。 3对最优解的初步分析 （1）由最优解中4个松弛变量的值s1 = s3 =
16、s4 =0，s2 =610，说明冲压、装配和喷漆3个工序可利用的加工时间全部用完，但成形工序还剩余610min时间闲置而未被利用。 （2）图11.3是软件输出的“敏感性报告”。图11.3 敏感性报告 由图11.3可知，冲压时间的影子价格是2.5元，装配时间的影子价格是0.5元，喷漆时间的影子价格是0.75元，其经济意义是上述3道工序资源每增加或减少1min，分别会使利润增加或减少2.5元、0.5元和0.75元。而成形工序的影子价格为0，这是因成形工序有闲置的610min未被利用。由此可知冲压工序是当前生产的关键所在，增加冲压能力将使产品总利润得到较大提高。4敏感性分析为便于分析，下面给出该LP
17、问题的最优单纯型表格，见表11.4。表11.4 最优单纯型表格基x1x2x3x4s1s2s3s4解x000.5002.500.50.7544500x1130050-10400s201.500-10.510.50.75610x40-0.501-0.500.5-0.2510x30-1.510-3.500.50.2570（1）B型金属罐的投产条件分析 在当前的最优生产计划中，不安排B型金属罐的生产，但当前市场对该产品是有需求的，若放弃B型金属罐的市场，将对企业的长期发展产生不利的影响。这就需要分析，在什么条件下，生产B型罐才能与企业利润最大化的目标相一致。从敏感性分析的角度考虑这一问题，其途径有以下
18、三个：一是通过降本增效，提高B型金属罐的单位利润；二是改进工艺，降低B型金属罐的各工序的加工时间，由此也必将降低B型罐的生产成本从而提高单位利润；三是设法增加某些工序的加工能力，优化配置企业的设备资源，使B型罐得以生产。下面就从这三个方面分别进行分析。1增加B型金属罐单位利润的分析由图11.3可知，在不改变当前最优基的条件下，c2允许的增量为0.5；此外由表11.4中x2 的检验数 = CB B-1 P2 - c2 = 0.5也可知，只要B型金属罐的单位利润c2 再增加0.5元以上，则原解就非最优，x2 将被调入基。再由表11.4中不难看出，调入x2 后，x1 将被调出基（由最小比值法），结果
19、并不能令人满意。下面假定通过降低物料消耗或提高价格等措施，可将B型金属罐的单位利润由6元增加至7元，用Excel软件重新求解，可得新的最优解为 X* =( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 0，133.33，270，76.76，0，410，0，0 ) x0 * = 4516.67 即此时新的最优生产计划将调整为：不生产A型金属罐，B、C、D型金属罐的日产量分别为133.33、270、76.76个。日总利润增加为4516.67元，每天仍有410min的成形工序时间闲置。由于该方案将放弃A型金属罐市场，同样可能对企业的长期发展产生不利的影响，故并不能从根本上解决问题。2降
20、低B型金属罐单位资源消耗的分析设1、2、3、4分别为B型金属罐各道工序单位加工时间的减少量， 则由 = CB B-1 P2 - c2 = ( 2.5，0，0.5，0.75 ) - 6 = 0.5 -2.51 -0.53 - 0.754可知，只要满足以下三个条件之一， 就将 0.2，或3 1，或4 0.67即冲压时间由1min降低到1-0.2 = 0.8min以下；或装配时间由2min降低到 2-1=1min以下；或喷漆时间由4min降低到4 - 0.67 = 3.33 min以下。下面我们分别对以上3种情况用Excel软件进行试算。 a设.冲压时间由1min降低到0.7min，其他工序时间不变
21、，用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 203.23，131.18，129.03，55.91，0，0，0，0 ) x0 * = 4482.80既A、B、C、D四种金属罐都将投入生产，最优日产量分别为203.23、131.18、129.03、55.91个，每天总利润为4482.80元。此时4道工序都恰好用完，资源也得到了充分利用。b设.装配时间由2min降低到0.9min，其他工序时间不变，用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 0，97.
22、56，270，112.44，0，517.32，0，0 ) x0 * = 4454.88即不生产A型罐，B、C、D三种金属罐的日产量分别为97.56、270、112.44个，此时成型工序每天有517.32min空闲时间。c设.喷漆时间由4min降低到2.9min，其他工序时间不变，用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 0，133.33，306.67，40，0，520，0，0 ) x0 * = 4453.33同样不生产A型罐，B、C、D三种金属罐的日产量分别为133.33、306.67、40个，此时成型工序每天有520
23、min空闲时间。 由以上分析可知，只要将B型罐的冲压时间由1min降低到0.7min，4种产品就可同时投入生产，且4种产品的产量相对比较均衡，四道工序时间也都将得到充分利用；而如果采用降低装配或喷漆时间的改进措施，则将导致停产A型罐，成型工序能力也都不能充分利用，放弃A型金属罐市场，同样可能对企业的长期发展产生不利的影响，而且企业资源配置不合理的状况也得不到解决。由此可见，为使B型罐能够生产，设法降低B型罐冲压时间是很好的解决方案。3增加工序加工能力（优化资源配置）的分析由图11.3可知，只要将冲压能力增加20min/天以上，或将装配能力增加400min/天以上，或将喷漆能力增加40min/天
24、以上，就将影响当前的最优基。下面我们仍采用试算的方法进行分析。a设将冲压能力每天增加60min（可通过加班解决），用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 887.86，66.67，0，19.05，11.43，0，0，0 ) x0 * = 4538.10即不生产C型罐，A、B、D三种金属罐的日产量分别为887.86、66.67、19.05个，此时冲压工序每天有11.43min空闲时间。由此可知，冲压能力每天只需增加48min，即可使4道工序能力都得到充分利用，但此时将退出C型罐市场，同样将对企业的长期发展产生不利影响。
25、b设将装配能力每天增加480min（可通过加班或购置新设备等方法解决），用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 0，0，270，210，0，810，80，0 ) x0 * = 4650此时不仅B型罐仍不能生产，而且A型罐也将停止生产，成型和装配工序每天将有810min和80min的空闲时间，资源配置更不合理。可见此方案并不能解决问题。c设将喷漆能力每天增加60min（可通过加班解决），用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，s1，s2，s3，s4 ) = ( 370，10，1
26、00，0，0，640，0，0 ) x0 * = 4490可见增加喷漆能力也不是一个好的解决方案，将放弃D型罐的市场，成型工序每天仍将有640min的空闲时间。 从上述三个不同角度的敏感性分析结果可知，要使B型罐的生产符合利润最大化的目标，而且使所有四种产品都能生产，同时使所有工序能力都得到充分利用的最佳且最容易实现的方案是通过改进工艺，降低B型罐的冲压时间。（2）关于产品单位利润变动的敏感性分析由图11.3可知，在不改变原最优解的条件下各产品单位利润的变动范围为8.83c19.5，-c26.5，10c311.33，7c49由此可知，在不影响当前最优基的条件下，各产品单位利润的可变动范围都不大，
27、也即当前最优解对产品单位利润的变化比较敏感，故当企业内外部环境发生变化而引起产品单位利润有较大变化（超出上述范围）时，应重新进行生产计划的优化分析。 （3）关于是否应当引进新产品生产技术的分析 为了满足市场需求，增强企业的发展后劲，该企业计划引进一种新型金属罐（E型罐）的生产技术，生产该产品无需增加新的设备投资。经测算，生产一个该金属罐需要冲压、成型、装配、喷漆的时间分别为1min、2min、6min、12min，产品单位利润为13元。在作出是否引进该金属罐生产技术的决策之前，需要从企业的整体经济效益出发对引进该产品的效益进行分析。 此问题属于增加一个新的决策变量。可设E型罐的日产量为x5 ，
28、由所给条件，c5 =13，P5 =（1，2，6，12 ），则x5 的检验数为 = CB B-1 P5 - c5 = ( 2.5，0，0.5，0.75 ) -13 =1.5 0故不影响原最优解。 = 1.5表明，若将E型罐投入生产，则每生产一个将使企业的总利润减少1.5元。可知从利润最大化的角度考虑不应投产E型罐。 要使E型罐的生产符合企业的整体经济效益，与前面（1）中关于B型罐的生产条件分析完全类似地，可从以下几个方面进行分析。 增加E型金属罐单位利润的分析 由 = 1.5可知，如果能通过降低生产成本等措施，将E型罐的单位利润提高1.5元以上，生产E型罐就能为企业带来更大的经济效益。下面假定可
29、将B型金属罐的单位利润由13元增加至15元，用Excel软件重新求解，可得新的最优解为 X* = ( x1，x2，x3，x4，x5，s1，s2，s3，s4 ) = ( 428，0，0，24，28，0，512，0，0 ） x0 * = 4464此时将不生产B型和C型金属罐，A、D、E型金属罐的日产量分别为428、24、28个，日总利润为4464元，每天仍有512min的成形工序时间闲置。由于该方案将放弃B型和C型金属罐市场，需要慎重考虑。 降低E型金属罐单位资源消耗的分析设1、2、3、4分别为E型金属罐各道工序单位加工时间的减少量， 则由 = CB B-1 P5 -c5 = ( 2.5，0，0.
30、5，0.75 ) - 13 = 1.5 - 2.51 - 0.53 - 0.754可知，只要满足1 0.6，或3 3，或4 2三个条件之一，E型罐就可投入生产，即：冲压时间由1min降低到0.4min以下；或装配时间由6min降低到3min以下；或喷漆时间由12min降低到10min以下。下面是分别对以上3种情况用Excel软件进行试算的结果。 a设.冲压时间由1min降低到0.3min，其他工序时间不变，则新的最优解为 X* =（x1，x2，x3，x4，x5，s1，s2，s3，s4 ） = ( 463.64，0，0，12.12，14.14，0，456.57，0，0 ） x0 * = 4453.54同样将不生产B型和C型金属罐，A、D、E型金属罐的日产量分别为463.64、1
