论文部分内容阅读
摘要：目前，在生产过程中，如何用最少的人力、物力、财力和时间去生产更多的产品是生产行业的热点研究问题，有重要的研究意义。本文通过建立线性规划模型，用Lingo和matlab软件，实现了对生产时满足资源消耗限制、加工工序等条件下，生产时间最少、生产成本最低问题的求解。
针对问题一，采用0—1规划，设置25个0—1变量，建立各组件生产时间总和最小的目标函数，根据题目所给的资源消耗限制及组件生产数量限制建立约束条件，编写程序，用Lingo进行模型求解。求解完毕后，考虑不同生产线可同时生产，消去计算过程中叠加的时间，计算出最短生产时间，得出计划安排。
针对问题二，在问题一的基础上，改变目标函数中各变量系数的值，使求用时最短变为所用费用最少，增加每条生产线只能生产一种组件的约束，删去生产线B生产组件5对应的变量。再编写程序，用Lingo进行模型求解，得到满足资源消耗条件下，生产线费用与资源费用之和最小的生产计划安排。
针对问题三，先选用matlab软件编写程序，求出满足资源消耗限制的所有组件与生产线的组合情况，在此基础上，再根据组件与组件间加工的前驱工序要求及各组件在不同生产线生产的用时情况，固定某个组件在哪条生产线生产，用枚举法，多次试验，得出用时最短的生产计划安排。
最后，对所建模型及求解方法进行优客观评价。
关键词：0—1规划；生产优化 ；Lingo；MATLAB
中图分类号：O221文献标识码：A
1 问题重述
1.1 问题背景
组件生产是生产产品过程中重要的一部分，其生产时间的快慢及消耗成本的多少直接影响着工厂的获利情况。工业是国民经济的主导产业，随着经济的快速发展，我国工厂的数量持续增加，如何减少生产时间、降低生产成本、制定可行的生产方案，对生产行业具有重大的意义。
1.2 问题描述
某车间有五台生产线，生产5个组件，不允许两种组件同时在一个生产线上生产，已知每个组件在不同生产线上的生产时间与资源消耗情况，以及组件和组件间的加工的前驱工序要求。
试建立数学模型解决以下问题：
（1）不考虑组件加工顺序，求满足资源消耗限制的组件生产时间最少的计划安排；
（2）若假设每条生产线只能完成一种组件，且因工艺要求，5号组件不能再生产线B上加工，又知5条生产线每小时的运行成本及五种资源的单位成本，求在满足资源消耗限制条件下，组件生产费用最小的计划安排；
（3）考虑组件加工顺序，求满足资源消耗限制的组件生产时间最少的计划安排，并计算全部组件生产完毕的最短时间。
2 模型假设
（1）假设组件交接过程中即上一个组件生产完，下一个组件就开始生产，没有时间浪费；
（2）假设不同生产线上可以同时生产；
（3）假设每条生产线同一时间只能生产一个组件；
（4）假设每种组件生产的数量为1或0；
（5）假设工作中机器不会出现意外，会一直运行。
3 符号说明
Xij：生产线i（i=A，B，C，D，E）生产组件j（j=1，2，3，4，5）的数量；
Cij：生产线i（i=A，B，C，D，E）生产组件j（j=1，2，3，4，5）所需时间；
Fij：生产线i（i=A，B，C，D，E）生产组件j（j=1，2，3，4，5）每小时的运行成本；
Wk：Xij消耗资源k（k=1，2，3，4，5）的成本。
4 模型的建立与求解
4.1 问题一的建模与求解
（1）问题分析。
为求满足资源消耗限制的组件生产时间最少的计划安排，需利用0—1规划，建立求各组件生产时间总和最小的目标函数，再根据题目所给的资源消耗限制及组件生产数量限制建立约束条件，用Lingo进行模型求解。求解完毕后，再根据假设2.2，考虑不同生产线可同时生产，计算出最短生产时间，得出计划安排。
（2）模型的建立。
①目标函数的建立。
根据题目所给的信息，建立生产时间总和最少的目标函数：
minz=∑i=E，j=5i=A，j=1Cij*Xij
根据题目所给的数据，目标函数展开为：
z=10XA1+8XA2+20XA3+4XA4+8XA5+4XB1+10XB2+6XB3+12XB4+5XB5+22XC1+13XC2+4XC3+10XC4+8XC5+2XD1+16XD2+25XD3+8XD4+2XD5+6XE1+8XE2+13XE3+11XE4+16XE5
②约束条件的建立。
由题知，要求生产所消耗的各种资源满足现有的资源提供量，即5种资源消耗约束分别为：
2XA1+XA3+2XB2+XB3+XC1+2XC2+XC5+2XD2+XD3+2XE4+XE5
SymbolcB@ 3XA2+2XA5+2XB1+XB4+2XC2+3XD2+2XD4+3XD5+XE1+3XE5
SymbolcB@ 42XA1+2XA3+XB1+2XB2+2XC3+2XD3+3XE4
SymbolcB@ 3XA1+2XA2+3XA4+2XB3+3XB5+2XC3+XC4+XC5+XD1+3XD4+4XE2+XE4
SymbolcB@ 45XA2+5XA4+2XA5+5XB3+2XB4+4XC4+3XC5+2XD1+6XD5+2XE1+3XE3
SymbolcB@ 6
且5種组件都需生产1个：
XA1+XB1+XC1+XD1+XE1=1；XA2+XB2+XC2+XD2+XE2=1；XA3+XB3+XC3+XD3+XE3=1；XA4+XB4+XC4+XD4+XE4=1；XA5+XB5+XC5+XD5+XE5=1 组件j在生产线i上生产1个或不生产：
Xij=01；i=A，B，C，D，E，j=1，2，3，4，5
（3）模型的求解。
用Lingo软件求解得：最短时间为44小时，变量XB1，XB2，XC5，XD4，XE3值为1，其它变量值为0。
因不同生产线可同时生产，故消去计算过程中叠加的时间，取各生产线所用时间的最大值：
max（CB1+CB2，CC5，CD4，CE3）=max（4+10，8，8，13）=14，
因此，实际生产所用最短时间为14小时，生产计划安排为：
生产线A不生产；
生产线B生产组件1和组件2；
生产线C生产组件5；
生产线D生产组件4；
生产线E生产组件3。
4.2 问题二的建立与求解
（1）问题分析。
题目要求每条生产线只能完成一种组件，且5号组件不能在生产线B上加工，给出了各生产线每小时的运行成本及资源的单位成本，求满足资源消耗限制下，生产费用最小的计划安排。因此，只要在问题一的基础上，改变以下几个地方：
①取消变量XB5；
②改变目标函数中各变量系数的值，使求用时最短变为费用最少；
③增加每条生产线只能生产一种组件的约束。
（2）模型的建立。
①目标函数的建立。
根据题目所给信息，建立生产线运行成本与资源消耗成本费用之和最少的目标函数：
minz=∑i=E，j=5，k=5i=A，j=1，k=1（Cij*Fij+Wk）*Xij （不取XB5）
代入数值，展开化简为：
z=17900XA1+17000XA2+27400XA3+13300XA4+12000XA5+5200XB1+12400XB2+12800XB3+11600XB4+34000XC1+22300XC2+12900XC3+19700XC4+16900XC5+5500XD1+22400XD2+33400XD3+14900XD4+8400XD5+6800XE1+12400XE2+12800XE3+15900XE4+15000XE5
②约束条件的建立。
在问题一建立的对资源消耗和组件生产数量的约束上删去变量XB5：
XA1+XB1+XC1+XD1+XE1=1；XA2+XB2+XC2+XD2+XE2=1；XA3+XB3+XC3+XD3+XE3=1；XA4+XB4+XC4+XD4+XE4=1；XA5+XC5+XD5+XE5=1；
2XA1+XA3+2XB2+XB3+XC1+2XC2+XC5+2XD2+XD3+2XE4+XE5
SymbolcB@ 3XA2+2XA5+2XB1+XB4+2XC2+3XD2+2XD4+3XD5+XE1+3XE5
SymbolcB@ 42XA1+2XA3+XB1+2XB2+2XC3+2XD3+3XE4
SymbolcB@ 3XA1+2XA2+3XA4+2XB3+2XC3+XC4+XC5+XD1+3XD4+4XE2+XE4
SymbolcB@ 45XA2+5XA4+2XA5+5XB3+2XB4+4XC4+3XC5+2XD1+6XD5+2XE1+3XE3
SymbolcB@ 6
根据题目要求，建立每条生产线只能完成一种组件的约束，即各生产线生产的组件数为1：
XA1+XA2+XA3+XA4+XA5=1；XB1+XB2+XB3+XB4=1；XC1+XC2+XC3+XC4+XC5=1；XD1+XD2+XD3+XD4+XD5=1；XE1+XE2+XE3+XE4+XE5=1；
Xij=01；i=A，B，C，D，E，j=1，2，3，4，5
（3）模型的求解。
编写算法，用Lingo软件求解得：满足资源消耗的生产费用最小为86100元。生产计划安排为：
生产线A生产组件5；
生产线B生产组件2；
生产线C生产组件1；
生产线D生产组件5；
生产线E生产组件4。
4.3 问题三的建立与求解
（1）问题分析。
题目给出各生产线上生产5种组件对应的前驱组件生产情况，要求考虑组件生产情况，重新求解第一问，计算全部组件生产完毕的最短时间。因每条生产线对各种组件的前驱组件生产要求不同，要综合考虑以下几种情况：
①生产计划要满足资源消耗要求。
②不同生产线可同时生产。
③有前驱组件的要等前驱组件生产完才可以开始生产。
④若多个组件在同一条生产线上生产，需等上一个生产完才能生产下一个。因此，情况比较复杂，无法建立用时最短的目标函数，不能采用线性规划方法。
若用多阶段决策，人为进行判断，每次选取用时较少的组合方案，不确定性大，很难得到最优结果，且不一定满足资源消耗限制。
综上所述，选用matlab软件编写程序，求出满足资源消耗限制的所有组合情况，在此基础上，再根据组件与组件间加工的前驱工序要求及各组件在不同生产线生产的用时情况，固定某个组件在哪条生产线生产，用枚举法，多次试验，得出用时最短的生产计划安排。
（2）模型的建立与求解。
根据题目所给资源限制、各组件在不同生产线生产所需生产时间、5种资源消耗情况、和前驱工序要求，用matlab编写相关算法，运用for循环语句，算出满足资源消耗限制的所有组件与生产线安排情况。在此基础上，运用枚举法，每次给定不同的组件与生产线组合约束，计算生产完毕所用时间。经过多次试验，得出在组合约束为R1==2 & R5==2，即组件1在生产线B生产，组件5也在生产线B上生产为时，能求得用时最短方案：
5 模型评价
问题一与问题二所建模型运用0—1规划，思路清晰，模型严谨，简明易懂，且求解方法简单，结果准确，说服力强，具有很好的实用性。
问题三所建模型及求解方法具有可行性，但求解过程较复杂，耗时较长，计算结果容易出现偏差。
参考文献：
[1]陈皆妤，邹晶娜，胡瑜琳，陳俊璇.零件加工优化排序问题，职业教育，14：172，2015.
[2]陈忠实，蒋昱辰.0—1整数规划求解法，北京化工大学学报自然科学版，5965，1989.3.
[3]刁在筠.运筹学，北京：高等教育出版社，2016.7.
[4]谢金星.优化建模与LINGO.北京：清华大学出版社，2005.7.
作者简介：第一作者：李立欣（1998），女，汉族，本科。
*通讯作者：许健开（1978），男，汉族，博士研究生，副教授，主要研究微分方程与调和分析。
针对问题一，采用0—1规划，设置25个0—1变量，建立各组件生产时间总和最小的目标函数，根据题目所给的资源消耗限制及组件生产数量限制建立约束条件，编写程序，用Lingo进行模型求解。求解完毕后，考虑不同生产线可同时生产，消去计算过程中叠加的时间，计算出最短生产时间，得出计划安排。
针对问题二，在问题一的基础上，改变目标函数中各变量系数的值，使求用时最短变为所用费用最少，增加每条生产线只能生产一种组件的约束，删去生产线B生产组件5对应的变量。再编写程序，用Lingo进行模型求解，得到满足资源消耗条件下，生产线费用与资源费用之和最小的生产计划安排。
针对问题三，先选用matlab软件编写程序，求出满足资源消耗限制的所有组件与生产线的组合情况，在此基础上，再根据组件与组件间加工的前驱工序要求及各组件在不同生产线生产的用时情况，固定某个组件在哪条生产线生产，用枚举法，多次试验，得出用时最短的生产计划安排。
最后，对所建模型及求解方法进行优客观评价。
关键词：0—1规划；生产优化 ；Lingo；MATLAB
中图分类号：O221文献标识码：A
1 问题重述
1.1 问题背景
组件生产是生产产品过程中重要的一部分，其生产时间的快慢及消耗成本的多少直接影响着工厂的获利情况。工业是国民经济的主导产业，随着经济的快速发展，我国工厂的数量持续增加，如何减少生产时间、降低生产成本、制定可行的生产方案，对生产行业具有重大的意义。
1.2 问题描述
某车间有五台生产线，生产5个组件，不允许两种组件同时在一个生产线上生产，已知每个组件在不同生产线上的生产时间与资源消耗情况，以及组件和组件间的加工的前驱工序要求。
试建立数学模型解决以下问题：
（1）不考虑组件加工顺序，求满足资源消耗限制的组件生产时间最少的计划安排；
（2）若假设每条生产线只能完成一种组件，且因工艺要求，5号组件不能再生产线B上加工，又知5条生产线每小时的运行成本及五种资源的单位成本，求在满足资源消耗限制条件下，组件生产费用最小的计划安排；
（3）考虑组件加工顺序，求满足资源消耗限制的组件生产时间最少的计划安排，并计算全部组件生产完毕的最短时间。
2 模型假设
（1）假设组件交接过程中即上一个组件生产完，下一个组件就开始生产，没有时间浪费；
（2）假设不同生产线上可以同时生产；
（3）假设每条生产线同一时间只能生产一个组件；
（4）假设每种组件生产的数量为1或0；
（5）假设工作中机器不会出现意外，会一直运行。
3 符号说明
Xij：生产线i（i=A，B，C，D，E）生产组件j（j=1，2，3，4，5）的数量；
Cij：生产线i（i=A，B，C，D，E）生产组件j（j=1，2，3，4，5）所需时间；
Fij：生产线i（i=A，B，C，D，E）生产组件j（j=1，2，3，4，5）每小时的运行成本；
Wk：Xij消耗资源k（k=1，2，3，4，5）的成本。
4 模型的建立与求解
4.1 问题一的建模与求解
（1）问题分析。
为求满足资源消耗限制的组件生产时间最少的计划安排，需利用0—1规划，建立求各组件生产时间总和最小的目标函数，再根据题目所给的资源消耗限制及组件生产数量限制建立约束条件，用Lingo进行模型求解。求解完毕后，再根据假设2.2，考虑不同生产线可同时生产，计算出最短生产时间，得出计划安排。
（2）模型的建立。
①目标函数的建立。
根据题目所给的信息，建立生产时间总和最少的目标函数：
minz=∑i=E，j=5i=A，j=1Cij*Xij
根据题目所给的数据，目标函数展开为：
z=10XA1+8XA2+20XA3+4XA4+8XA5+4XB1+10XB2+6XB3+12XB4+5XB5+22XC1+13XC2+4XC3+10XC4+8XC5+2XD1+16XD2+25XD3+8XD4+2XD5+6XE1+8XE2+13XE3+11XE4+16XE5
②约束条件的建立。
由题知，要求生产所消耗的各种资源满足现有的资源提供量，即5种资源消耗约束分别为：
2XA1+XA3+2XB2+XB3+XC1+2XC2+XC5+2XD2+XD3+2XE4+XE5
SymbolcB@ 3XA2+2XA5+2XB1+XB4+2XC2+3XD2+2XD4+3XD5+XE1+3XE5
SymbolcB@ 42XA1+2XA3+XB1+2XB2+2XC3+2XD3+3XE4
SymbolcB@ 3XA1+2XA2+3XA4+2XB3+3XB5+2XC3+XC4+XC5+XD1+3XD4+4XE2+XE4
SymbolcB@ 45XA2+5XA4+2XA5+5XB3+2XB4+4XC4+3XC5+2XD1+6XD5+2XE1+3XE3
SymbolcB@ 6
且5種组件都需生产1个：
XA1+XB1+XC1+XD1+XE1=1；XA2+XB2+XC2+XD2+XE2=1；XA3+XB3+XC3+XD3+XE3=1；XA4+XB4+XC4+XD4+XE4=1；XA5+XB5+XC5+XD5+XE5=1 组件j在生产线i上生产1个或不生产：
Xij=01；i=A，B，C，D，E，j=1，2，3，4，5
（3）模型的求解。
用Lingo软件求解得：最短时间为44小时，变量XB1，XB2，XC5，XD4，XE3值为1，其它变量值为0。
因不同生产线可同时生产，故消去计算过程中叠加的时间，取各生产线所用时间的最大值：
max（CB1+CB2，CC5，CD4，CE3）=max（4+10，8，8，13）=14，
因此，实际生产所用最短时间为14小时，生产计划安排为：
生产线A不生产；
生产线B生产组件1和组件2；
生产线C生产组件5；
生产线D生产组件4；
生产线E生产组件3。
4.2 问题二的建立与求解
（1）问题分析。
题目要求每条生产线只能完成一种组件，且5号组件不能在生产线B上加工，给出了各生产线每小时的运行成本及资源的单位成本，求满足资源消耗限制下，生产费用最小的计划安排。因此，只要在问题一的基础上，改变以下几个地方：
①取消变量XB5；
②改变目标函数中各变量系数的值，使求用时最短变为费用最少；
③增加每条生产线只能生产一种组件的约束。
（2）模型的建立。
①目标函数的建立。
根据题目所给信息，建立生产线运行成本与资源消耗成本费用之和最少的目标函数：
minz=∑i=E，j=5，k=5i=A，j=1，k=1（Cij*Fij+Wk）*Xij （不取XB5）
代入数值，展开化简为：
z=17900XA1+17000XA2+27400XA3+13300XA4+12000XA5+5200XB1+12400XB2+12800XB3+11600XB4+34000XC1+22300XC2+12900XC3+19700XC4+16900XC5+5500XD1+22400XD2+33400XD3+14900XD4+8400XD5+6800XE1+12400XE2+12800XE3+15900XE4+15000XE5
②约束条件的建立。
在问题一建立的对资源消耗和组件生产数量的约束上删去变量XB5：
XA1+XB1+XC1+XD1+XE1=1；XA2+XB2+XC2+XD2+XE2=1；XA3+XB3+XC3+XD3+XE3=1；XA4+XB4+XC4+XD4+XE4=1；XA5+XC5+XD5+XE5=1；
2XA1+XA3+2XB2+XB3+XC1+2XC2+XC5+2XD2+XD3+2XE4+XE5
SymbolcB@ 3XA2+2XA5+2XB1+XB4+2XC2+3XD2+2XD4+3XD5+XE1+3XE5
SymbolcB@ 42XA1+2XA3+XB1+2XB2+2XC3+2XD3+3XE4
SymbolcB@ 3XA1+2XA2+3XA4+2XB3+2XC3+XC4+XC5+XD1+3XD4+4XE2+XE4
SymbolcB@ 45XA2+5XA4+2XA5+5XB3+2XB4+4XC4+3XC5+2XD1+6XD5+2XE1+3XE3
SymbolcB@ 6
根据题目要求，建立每条生产线只能完成一种组件的约束，即各生产线生产的组件数为1：
XA1+XA2+XA3+XA4+XA5=1；XB1+XB2+XB3+XB4=1；XC1+XC2+XC3+XC4+XC5=1；XD1+XD2+XD3+XD4+XD5=1；XE1+XE2+XE3+XE4+XE5=1；
Xij=01；i=A，B，C，D，E，j=1，2，3，4，5
（3）模型的求解。
编写算法，用Lingo软件求解得：满足资源消耗的生产费用最小为86100元。生产计划安排为：
生产线A生产组件5；
生产线B生产组件2；
生产线C生产组件1；
生产线D生产组件5；
生产线E生产组件4。
4.3 问题三的建立与求解
（1）问题分析。
题目给出各生产线上生产5种组件对应的前驱组件生产情况，要求考虑组件生产情况，重新求解第一问，计算全部组件生产完毕的最短时间。因每条生产线对各种组件的前驱组件生产要求不同，要综合考虑以下几种情况：
①生产计划要满足资源消耗要求。
②不同生产线可同时生产。
③有前驱组件的要等前驱组件生产完才可以开始生产。
④若多个组件在同一条生产线上生产，需等上一个生产完才能生产下一个。因此，情况比较复杂，无法建立用时最短的目标函数，不能采用线性规划方法。
若用多阶段决策，人为进行判断，每次选取用时较少的组合方案，不确定性大，很难得到最优结果，且不一定满足资源消耗限制。
综上所述，选用matlab软件编写程序，求出满足资源消耗限制的所有组合情况，在此基础上，再根据组件与组件间加工的前驱工序要求及各组件在不同生产线生产的用时情况，固定某个组件在哪条生产线生产，用枚举法，多次试验，得出用时最短的生产计划安排。
（2）模型的建立与求解。
根据题目所给资源限制、各组件在不同生产线生产所需生产时间、5种资源消耗情况、和前驱工序要求，用matlab编写相关算法，运用for循环语句，算出满足资源消耗限制的所有组件与生产线安排情况。在此基础上，运用枚举法，每次给定不同的组件与生产线组合约束，计算生产完毕所用时间。经过多次试验，得出在组合约束为R1==2 & R5==2，即组件1在生产线B生产，组件5也在生产线B上生产为时，能求得用时最短方案：
5 模型评价
问题一与问题二所建模型运用0—1规划，思路清晰，模型严谨，简明易懂，且求解方法简单，结果准确，说服力强，具有很好的实用性。
问题三所建模型及求解方法具有可行性，但求解过程较复杂，耗时较长，计算结果容易出现偏差。
参考文献：
[1]陈皆妤，邹晶娜，胡瑜琳，陳俊璇.零件加工优化排序问题，职业教育，14：172，2015.
[2]陈忠实，蒋昱辰.0—1整数规划求解法，北京化工大学学报自然科学版，5965，1989.3.
[3]刁在筠.运筹学，北京：高等教育出版社，2016.7.
[4]谢金星.优化建模与LINGO.北京：清华大学出版社，2005.7.
作者简介：第一作者：李立欣（1998），女，汉族，本科。
*通讯作者：许健开（1978），男，汉族，博士研究生，副教授，主要研究微分方程与调和分析。