线性规划应用案例Word文件下载.docx
《线性规划应用案例Word文件下载.docx》由会员分享，可在线阅读，更多相关《线性规划应用案例Word文件下载.docx（21页珍藏版）》请在冰点文库上搜索。
零件号
零件尺寸（mm）
需要量
每张钢板可下料数
钢板需要量
单一下料利用率%
1000×
2000×
2
1#
260×
258
500
21
24
69.88
2#
240×
257.6
600
28
22
84.31
3#
840×
195
250
11
23
89.02
合计
69
80.86
可见，如果采用以往的单一下料方法，则这三种零件总共需要69张钢板，总的材料利用率仅为80.86%。
下面，我们采用上述工作流程进行优化。
1.选作排料图
图2是选作的4张排料图，分别用X1、X2、X3、X4表示；
表9.10给出了各种排料方式下每张钢板可切割的零件数。
表2各种排料方式下每张钢板可得零件数
零件
x1
x2
x3
x4
4
1
10
2.建立LP模型并求最优解
设x1、x2、x3、x4分别为上述各种排料方式的切割钢板数，目标是所耗用的钢板最少。
由表2，可得LP模型为
minx0=x1+x2+x3+x4
21x1≥500
s.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张，可满足3种零件的需求，总共需62张钢板，可比单一下料方式少用7张钢板，材料利用率提高到89.99%，但材料利用率仍然偏低，效果还不够理想。
3.下料方案的最优化后分析
板材下料问题LP模型最优解的效果取决于所绘制的排料图。
由于该方法一开始只要求选作若干排料图，因此其初始最优解的效果往往是欠佳的，但这一缺陷可在最优化后分析阶段弥补。
获得初始最优解后，首先应计算其材料利用率，若效果欠佳，则一般有以下两个原因：
（1）最优解中含有某些材料利用率较低的排料图；
（2）各零件在排料图中的数量配比不当（反映在最优解中就是存在较大的剩余变量）。
出现上述情况时，可有针对性地再绘制少量排料图，以它们作为新增变量加入原模型中，重新运算后通常即可得到令人满意的下料方案。
本案例中由于3个剩余变量都为0（都是非基变量，在模型中并未给出，这是由于用软件求解并不要求化为标准型），故不存在数量配比不当的问题。
进一步分析可知，x1=23.81，数量最大，但排料图x1的材料利用率仅为86.81%，可见这是影响材料利用率的主要原因。
分析4张排料图后，可发现仅x1中含有1#零件，显然应对1#零件重新设计排料图。
再看2#零件，其需求量最大，且与1#零件有一边长相近，两者的另一边长之和又恰好与钢板短边成倍比（260+240=500），故可将两者组合后绘制一张新的排料图x5，见图3。
该排料图每张可得1#和2#零件各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，x5=35
（2）计算零件短缺数，见表3。
表3取整后零件短缺数计算表
可得到的零件数
需求量
短缺数
14×
35=490
4×
21+14×
35=574
26
10×
21+1×
35=245
5
（3）对零件短缺数进行套料。
通常经取整后的短缺数不会很大，故套料工作量也不会很大。
对于本案例，首先考虑现有排料图。
由于x2每张可得2#零件28块，3#零件1块，故应取x2=1。
这样就只缺1#零件10块，3#零件4块，据此再绘制一张排料图x6，见图4，它可裁得1#零件12块，3#零件6块，已满足要求。
图3排料图X5图4排料图X6
现在已得到最终下料方案：
分别按排料图x2、x3、x5、x6各切割1、21、35、1张，总计耗用58张钢板，比进位取整方法又少用1张，材料利用率则进一步提高到96.19%。
仅此3个零件，就比单一下料法节约11张钢板，材料利用率提高了15.33%，其经济效益可见一斑。
某金属罐制造厂生产方案的优化案例
一．问题的提出
某金属罐制造厂是制造金属罐的专业厂家，其主要产品有A、B、C、D四种型号的金属罐。
近年来，产品销售情况良好，市场对这4种产品的需求量很大，且预测结果表明，需求还有进一步扩大的趋势，许多用户还希望能提供更多的不同功能的新产品。
此外，现有产品在质量、性能、成本、工艺等方面也存在进一步改善的余地。
对此，该厂已做了一些基本的分析，比如对引进新的制罐技术的可行性分析，对目前产品的成本核算及分析等。
但对如何优化当前的生产计划，以获得更大的经济效益；
企业目前的各项资源配置是否合理；
应如何进一步改进生产条件以满足市场需求；
是否下决心引进新技术开发新产品等等一系列问题尚缺乏科学的定量分析依据。
为适应日趋激烈的市场竞争环境，不断提高企业的竞争能力和赢利能力，该企业决策者决定聘请某高校的定量分析专家协助，对当前和未来的生产计划进行最优化分析。
二．案例分析
1．产品生产主要过程及其模型的建立
该企业生产的A、B、C、D四种金属罐要经过四道工序：
第一道工序是冲压下料，金属板材在冲压车间经冲压机冲压，加工成金属罐所需要的各种板材零件；
第二道工序是成形加工，在成形车间里把板材零件冲压成符合要求的形状；
第三道工序是焊接装配，在焊接车间将各种成形的零件按技术要求焊接装配成为完整的金属罐；
最后一道工序是喷漆，装配好的金属罐送到喷漆车间被喷上防火的瓷漆。
根据工艺要求及成本核算，各单位产品所需的加工时间、利润及目前可供使用的总工时如表11.3所示。
表11.3单位产品所需加工时间、利润及可利用的工时
产品
工序
A
B
C
D
可利用总工时
（min/天）
冲压
480
成形
8
2400
装配
2000
喷漆
6
3000
单位利润（元）
9
该厂仅有一台冲压机，每天工作8小时，共计480min可供加工使用；
另有若干条成形、装配、喷漆生产线分属各车间，除承担本厂生产任务外，还承担着科研实验、新产品开发试制等工作，因此这些生产线每天可利用的总工时分别不超过2400min、2000min和3000min。
由以上分析，可设
x1为A型金属罐的日产量；
x2为B型金属罐的日产量；
x3为C型金属罐的日产量；
x4为D型金属罐的日产量；
并设目标函数为每天的总利润，就可建立日产品计划的线性规划模型如下：
maxx0=9x1+6x2+11x3+8x4
x1+x2+x3+x4≤480
4x1+8x2+2x3+5x4≤2400
s.t.4x1+2x2+5x3+5x4≤2000
6x1+4x2+8x3+4x4≤3000
x1,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=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问题的最优单纯型表格，见表11.4。
表11.4最优单纯型表格
基
s1
s2
s3
s4
解
x0
0.5
2.5
0.75
44500
3
-1
400
1.5
-10.5
610
-0.5
-0.25
-1.5
-3.5
0.25
70
（1）B型金属罐的投产条件分析
在当前的最优生产计划中，不安排B型金属罐的生产，但当前市场对该产品是有需求的，若放弃B型金属罐的市场，将对企业的长期发展产生不利的影响。
这就需要分析，在什么条件下，生产B型罐才能与企业利润最大化的目标相一致。
从敏感性分析的角度考虑这一问题，其途径有以下三个：
一是通过降本增效，提高B型金属罐的单位利润；
二是改进工艺，降低B型金属罐的各工序的加工时间，由此也必将降低B型罐的生产成本从而提高单位利润；
三是设法增加某些工序的加工能力，优化配置企业的设备资源，使B型罐得以生产。
下面就从这三个方面分别进行分析。
1增加B型金属罐单位利润的分析
由图11.3可知，在不改变当前最优基的条件下，c2允许的增量为0.5；
此外由表11.4中x2的检验数
=CBB-1P2-c2=0.5
也可知，只要B型金属罐的单位利润c2再增加0.5元以上，则原解就非最优，x2将被调入基。
再由表11.4中不难看出，调入x2后，x1将被调出基（由最小比值法），结果并不能令人满意。
下面假定通过降低物料消耗或提高价格等措施，可将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降低B型金属罐单位资源消耗的分析
设δ1、δ2、δ3、δ4分别为B型金属罐各道工序单位加工时间的减少量，
则由
=CBB-1P2’-c2=（2.5，0，0.5，0.75）
-6
=0.5-2.5δ1-0.5δ3-0.75δ4
可知，只要满足以下三个条件之一，
就将<
0，x2就可调入基，该产品就可投入生产。
δ1>
0.2，或δ3>
1，或δ4>
0.67
即冲压时间由1min降低到1-0.2=0.8min以下；
或装配时间由2min降低到2-1=1min以下；
或喷漆时间由4min降低到4-0.67=3.33min以下。
下面我们分别对以上3种情况用Excel软件进行试算。
a．设.冲压时间由1min降低到0.7min，其他工序时间不变，用Excel软件重新求解，可得新的最优解为
=（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软件重新求解，可得新的最优解为
=（0，97.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软件重新求解，可得新的最优解为
=（0，133.33，306.67，40，0，520，0，0）’
x0*=4453.33
同样不生产A型罐，B、C、D三种金属罐的日产量分别为133.33、306.67、40个，此时成型工序每天有520min空闲时间。
由以上分析可知，只要将B型罐的冲压时间由1min降低到0.7min，4种产品就可同时投入生产，且4种产品的产量相对比较均衡，四道工序时间也都将得到充分利用；
而如果采用降低装配或喷漆时间的改进措施，则将导致停产A型罐，成型工序能力也都不能充分利用，放弃A型金属罐市场，同样可能对企业的长期发展产生不利的影响，而且企业资源配置不合理的状况也得不到解决。
由此可见，为使B型罐能够生产，设法降低B型罐冲压时间是很好的解决方案。
3增加工序加工能力（优化资源配置）的分析
由图11.3可知，只要将冲压能力增加20min/天以上，或将装配能力增加400min/天以上，或将喷漆能力增加40min/天以上，就将影响当前的最优基。
下面我们仍采用试算的方法进行分析。
a．设将冲压能力每天增加60min（可通过加班解决），用Excel软件重新求解，可得新的最优解为
=（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型罐市场，同样将对企业的长期发展产生不利影响。
b．设将装配能力每天增加480min（可通过加班或购置新设备等方法解决），用Excel软件重新求解，可得新的最优解为
=（0，0，270，210，0，810，80，0）’
x0*=4650
此时不仅B型罐仍不能生产，而且A型罐也将停止生产，成型和装配工序每天将有810min和80min的空闲时间，资源配置更不合理。
可见此方案并不能解决问题。
c．设将喷漆能力每天增加60min（可通过加班解决），用Excel软件重新求解，可得新的最优解为
=（370，10，100，0，0，640，0，0）’
x0*=4490
可见增加喷漆能力也不是一个好的解决方案，将放弃D型罐的市场，成型工序每天仍将有640min的空闲时间。
从上述三个不同角度的敏感性分析结果可知，要使B型罐的生产符合利润最大化的目标，而且使所有四种产品都能生产，同时使所有工序能力都得到充分利用的最佳且最容易实现的方案是通过改进工艺，降低B型罐的冲压时间。
（2）关于产品单位利润变动的敏感性分析
由图11.3可知，在不改变原最优解的条件下各产品单位利润的变动范围为
8.83≤c1≤9.5，-∞≤c2≤6.5，10≤c3≤11.33，7≤c4≤9
由此可知，在不影响当前最优基的条件下，各产品单位利润的可变动范围都不大，也即当前最优解对产品单位利润的变化比较敏感，故当企业内外部环境发生变化而引起产品单位利润有较大变化（超出上述范围）时，应重新进行生产计划的优化分析。
（3）关于是否应当引进新产品生产技术的分析
为了满足市场需求，增强企业的发展后劲，该企业计划引进一种新型金属罐（E型罐）的生产技术，生产该产品无需增加新的设备投资。
经测算，生产一个该金属罐需要冲压、成型、装配、喷漆的时间分别为1min、2min、6min、12min，产品单位利润为13元。
在作出是否引进该金属罐生产技术的决策之前，需要从企业的整体经济效益出发对引进该产品的效益进行分析。
此问题属于增加一个新的决策变量。
可设E型罐的日产量为x5，由所给条件，c5=13，P5=（1，2，6，12）’，则x5的检验数为
=CBB-1P5-c5=（2.5，0，0.5，0.75）
-13=1.5>
故不影响原最优解。
=1.5表明，若将E型罐投入生产，则每生产一个将使企业的总利润减少1.5元。
可知从利润最大化的角度考虑不应投产E型罐。
要使E型罐的生产符合企业的整体经济效益，与前面
（1）中关于B型罐的生产条件分析完全类似地，可从以下几个方面进行分析。
①增加E型金属罐单位利润的分析
由
=1.5可知，如果能通过降低生产成本等措施，将E型罐的单位利润提高1.5元以上，生产E型罐就能为企业带来更大的经济效益。
下面假定可将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型金属罐各道工序单位加工时间的减少量，
=CBB-1P5-c5=（2.5，0，0.5，0.75）
-13
=1.5-2.5δ1-0.5δ3-0.75δ4
可知，只要满足
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
升级会员 