基于0~1整数规划的生产过程决策研究

Research on Production Process Decision Making Based on 0-1 Integer Programming

摘要: 为提高畅销的电子产品企业的生产效率及产品质量，针对企业的生产过程，本文通过引入0~1变量，运用0~1整数规划模型对生产过程进行优化决策。首先，利用假设检验计算不同置信度下所需检测的最小零件数，从源头保证产品质量，既降低了后续生产的次品率，又降低了企业的生产成本。其次，以销售的总利润最大为目标，并以企业信誉为最主要的限制设定相关约束条件，构建最优化模型。然后，利用贪心算法对上述优化模型进行求解。具体地，对生产过程中有m道工序，n个零配件的问题，确定了6种可能的决策方案。最后，通过分别计算6种决策方案的销售总利润，为企业确定最优的决策方案。研究得出，在对部分零配件和半成品进行检测、部分不合格半成品进行拆解，而成品不检测、不合格成品不拆解的策略下，企业信誉可保持在75%以上，企业利润也较为可观。本研究通过对所建立优化模型的求解来提高企业的生产效率和产品质量，对提高企业收益和增加企业信誉具有实际的指导意义。

Abstract: In order to improve the production efficiency and product quality of popular electronic product enterprises, this article introduces 0-1 variables and uses 0-1 integer programming models to optimize the production process of the enterprise. Firstly, using hypothesis testing to calculate the minimum number of parts required for testing at different confidence levels ensures product quality from the source, which not only reduces the defect rate in subsequent production but also lowers the production cost of the enterprise. Secondly, with the goal of maximizing the total profit of sales and the enterprise reputation as the main constraint, relevant constraints are set to construct an optimization model. Then, the greedy algorithm is used to solve the optimization model mentioned above. Specifically, for the problem of m processes and n spare parts in the production process, 6 possible decision options have been identified. Finally, by calculating the total sales profit of the six decision options separately, the optimal decision option is determined for the enterprise. Research has shown that by testing some spare parts and semi-finished products, dismantling some non-conforming semi-finished products, and not testing finished products or dismantling non-conforming products, a company’s reputation can be maintained at over 75%, and its profits are also considerable. This study aims to improve the production efficiency and product quality of enterprises by solving the established optimization model, which has practical guiding significance for increasing enterprise profits and reputation.

1. 引言

在当今竞争激烈的市场环境中，企业的生产效率、产品质量以及信誉成为了影响其生存与发展的关键因素。优化生产过程决策，不仅能够降低生产成本，还能显著提升产品质量和企业的市场信誉，进而增强企业的核心竞争力。

生产过程的优化涉及到多个环节，包括原材料的采购与检测、零部件的装配、成品的检测与处理等，每个环节都充满了不确定性与复杂性。因此，构建科学合理的决策模型，为企业提供有效的生产策略，成为了企业管理与运筹学领域的重要课题。

生产过程优化和整数规划在工业领域有广泛应用。文献[1]提出了基于整数规划的生产调度方法，文献[2]利用贪心算法解决了资源分配问题。本文的创新点在于：将0~1整数规划与贪心算法结合，解决了多阶段生产决策问题。通过假设检验确定抽样方案，通过降低次品率来减少检测成本，进而提高销售的总利润。因此，本文结合所提出的0~1整数规划模型，对此单目标优化问题进行探究。

2. 生产过程中优化问题的描述

某企业生产某种畅销的电子产品，需要分别购买若干零配件，在企业将零配件装配成成品。在装配的成品中，只要其中一个零配件不合格，则成品一定不合格；如果两个零配件均合格，装配出的成品也不一定合格。对于不合格成品，企业可以选择报废，或者对其进行拆解，拆解过程不会对零配件造成损坏，但需要花费拆解费用。

已知零配件、半成品和成品的次品率如下表所示。为企业生产过程的各个阶段做出决策：

• 对零配件是否进行检测，如果对某种零配件不检测，这种零配件将直接进入到装配环节；否则将检测出的不合格零配件丢弃；

• 对装配好的每一件成品是否进行检测，如果不检测，装配后的成品直接进入到市场；否则只有检测合格的成品进入到市场；

• 对检测出的不合格成品是否进行拆解，如果不拆解，直接将不合格成品丢弃；否则对拆解后的零配件，重复步骤(1)和步骤(2)；

• 对用户购买的不合格品，企业将无条件予以调换，并产生一定的调换损失(如物流成本、企业信誉等)；对退回的不合格品，重复步骤(3)。

根据下表1中零配件、半成品和成品的次品率等相关数值，对m道工序，n个零配件给出具体决策方案。零配件、半成品和成品的次品率等相关数值见表1，决策变量见表2，参数及释义见表3。

Figure 1. Component composition diagram of a certain electronic product

图1. 某电子产品零件构成图

Table 1. Related numerical values

表1. 相关数值

零配件	次品率	购买单价	检测成本	半成品	次品率	装配成本	检测成本	拆解费用
1	10%	2	1	1	10%	8	4	6
2	10%	8	1	2	10%	8	4	6
3	10%	12	2	3	10%	8	4	6
4	10%	2	1
5	10%	8	1	成品	10%	8	6	10
6	10%	12	2
7	10%	8	1		市场售价		调换损失
8	10%	12	2	成品	200		40

Table 2. Decision variables

表2. 决策变量

$x_i$	$z_f$	$z_b$	$z_k$	$y_i$	${\overline{z}}_b$
零配件是否检测	成品是否检测	不合格成品是否拆解	退回的不合格成品是否拆解	半成品是否检测	不合格半成品是否拆解

Table 3. Parameters and their explanations

表3. 参数及释义

符号	含义	单位
$n_1$	零配件1的数量	件
$p_1$	零配件1的次品率	-
$C_b$	零配件的购买成本	元
$C_d$	零配$C_a$ 件的检测成本	元
	成品的装配成本	元
$C_f$	成品的检测成本	元
$C_t$	不合格成品的调换损失	元
$W$	不合格成品的拆解费用	元
$V$	成品的总利润	-

由于电子产品畅销，本文假设生产的成品全部售出。因不同供应商生产的零配件质量稍有波动，本文根据参考文献[1]假设零配件中的次品数量服从二项分布。

3. 模型建立与求解

为保证售出产品的质量以及企业的收益，需要从生产源头进行管控，因此在确定供应商后，需对零配件进行抽样检测，由于检测费用需企业自行承担，所以为企业设计出检测次数尽可能少的抽样检测方案，对保证产品的质量以及企业收益至关重要。本文约束零配件的次品率不超过10%，针对置信度低于95%和置信度低于90%两种情形，分别给出具体的结果。假设样本中的次品数量服从二项分布[2]，同时引入了单侧检验和最小样本容量，提出原假设和备择假设，选择合适的检验统计量并确定拒绝域，计算出最大实际次品率，并结合题目给出的标称次品率，利用系统抽样进行样本检测，使用单侧检验计算两种情形下的最小样本容量，设计出最合理的抽样检测方案。

3.1. 最小抽样数量的确定

本文假设样本量n取值为200，在此基础上计算出对应置信度下的最大允许次品率[3] $\overline{p}$ ，并将此作为任意样本的实际次品率。

3.1.1. 计算实际最大允许次品率

在计算最大允许次品率时，首先需要计算样本的标准误差(SE)，这是一个衡量估计比例或概率精度的指标，其计算方式如下：

$SE=\sqrt{\frac{p\left(1-p\right)}{n}}$

最大允许次品率的计算方式如下：

$\overline{p}=p_0+Z\times SE$

其中$p_0$ 为样本中的标称次品率，即$p_0=10\%$ ，$Z$ 是标准正态分布下的临界值，根据参考文献[4]可知，在95%的置信水平下$Z$ 的取值为1.96，在90%的置信水平下$Z$ 的取值为1.645。

3.1.2. 最小抽样量的求解

基于上文求解出的最大允许次品率$\overline{p}$ ，结合样本中的标称次品率$p_0$ 和不同置信水平下$Z$ 的取值，将各项系数带入到公式中，求解得出以下结果：

在95%信度下，所需的最小样品量数目为141件。

在90%信度下，所需的最小样品量数目为122件。

3.1.3. 抽样方案

本文认为，对于任意一个样本，只要它服从二项分布，那么在95%信度下，只需随机抽取141件样品，就可以确定是否接收从供应商购买的这批零配件；在90%信度下，只需随机抽取122件样品，就可以确定是否接收从供应商购买的这批零配件。

3.2. 0~1整数规划模型的建立

我们需要对企业生产过程中的各个阶段做出具体且合理的决策，决策过程中涉及到零配件的检测问题、半成品成品的检测问题、成品的检测问题、不合格半成品的拆解问题、不合格成品的拆解问题和退回的不合格成品的拆解问题，由于六种决策变量均只涉及两种结果，因此引入0~1整数规划模型[5]对该问题进行模型建立。

3.2.1. 决策变量的确定

(1) 零配件是否检测$x_i$

将某一成品所包含的零配件看为一个整体，将零配件$i$ 是否进行检测记为$x_i$ ，当零配件需要进行检测时取值为1，反之为0。

(2) 半成品是否检测$y_i$

如果其中一个零配件不合格，就会导致成品一定不合格；如果零配件全部合格，装配的半成品并不会一定合格。如果不对半成品进行检测，那么半成品将直接组装为成品进入市场；如果对半成品进行检测，那么检测合格的半成品才会组装为成品进入市场，因此在生产过程中半成品是否需要检测是一个重要的决策变量，本文将半成品是否需要检测记为$y_i$ ，若不合格半成品需要检测时取值为1，反之为0。

(3) 成品是否检测$z_f$

如果其中一个零配件不合格，就会导致半成品一定不合格；如果零配件全部合格，装配的半成品并不会一定合格。如果不检测成品，则该成品直接流入市场；如果检测成品，则合格的成品流入市场，因此在生产过程中成品是否需要检测是一个重要的决策变量，本文将成品是否需要检测记为$z_f$ ，若成品需要检测时取值为1，反之为0。

(4) 不合格半成品是否拆解${\overline{z}}_b$

在半成品进行检测的基础上，检测出的不合格半成品是否进行拆解是一项需要考虑的决策变量，如果对不合格半成品不进行拆解，则该半成品会被直接丢弃，造成原材料的浪费；如果进行拆解，则需要考虑检测费用，本文将不合格半成品是否需要拆解记为${\overline{z}}_b$ ，若不合格半成品需要拆解时取值为1，反之为0。

(5) 不合格成品是否拆解$z_b$

在成品进行检测的基础上，检测出的不合格成品是否进行拆解是一项需要考虑的决策变量，如果对不合格成品不进行拆解，则该成品会被直接丢弃；如果进行拆解，则需要考虑拆解成本以及检测成本，本文将不合格成品是否需要拆解记为$z_b$ ，若不合格成品需要拆解时取值为1，反之为0。

(6) 退回的不合格成品是否拆解$z_k$

在成品不进行检测的基础上，所有的成品均会进入市场，用户便有可能购买到不合格的成品，当用户购买到不合格成品时，会产生一定的调换费用。本文假设企业只无条件调换一次不合格成品，且调换的新成品一定是合格的，那么调换的不合格成品是否进行拆解需要进行讨论，如果退回的不合格成品不进行拆解，则该成品会被直接丢弃，如果进行拆解，则需要考虑拆解成本，本文将退回的不合格成品是否需要拆解记为$z_k$ ，若退回的不合格成品需要拆解时取值为1，反之为0。

3.2.2. 目标函数的建立

为实现在满足决策方案合理性的前提下，企业同时实现成本最小、利润最大和企业信誉足够良好的目标，因此本文以成品的总利润为研究对象，构建目标函数，建立单目标优化模型，其计算公式如下：

$W=n_{s}s-\left(C_b+C_d+C_{a-half}+C_{d-half}+C_{r-half}+C_a+C_f+C_r+C_t\right)$

已知利润是收益和成本的差值，因此，为了计算企业总利润，我们需要对企业总成本进行求解。通过分析目标函数的决策变量，本文认为企业的总成本由零配件检测费用、半成品的检测费用、成品检测费用、半成品的拆解费用、不合格成品的拆解费用、不合格成品的调换费用、零配件的购买费用、半成品的装配费用、成品的装配费用九部分组成，则总成本的计算方法如下：

$C=C_b+C_d+C_{a-half}+C_{d-half}+C_{r-half}+C_a+C_f+C_r+C_t$

成本中相关系数计算

(1) 零配件的购买成本$C_b$

$C_b={\displaystyle \sum _{i=1}^8{n}_i{c}_{bi}}$

其中$c_{bi}$ 为零配件$i$ 的购买成本，$n_i$ 为需要检测的零配件$i$ 的总数。

(2) 零配件的检测成本$C_d$

$C_d={\displaystyle \sum _{i=1}^8{x}_i{n}_i{c}_{di}}$

其中$c_{di}$ 为零配件$i$ 的检测成本，$n_i$ 为需要检测的零配件$i$ 的总数。

(3) 半成品的装配成本$C_{a-half}$

$C_{a-half}={\overline{c}}_a{N}_j$

其中${\overline{c}}_a$ 为每件半成品的装配成本，$N_j$ 为拆解的不合格半成品的数量。

(4) 半成品的检测成本$C_{d-half}$

$C_{d-half}={\overline{c}}_f{\displaystyle \sum _{j=1}^3{N}_j{y}_j}$

其中${\overline{c}}_f$ 为每件半成品的检测成本。

(5) 半成品的拆解费用$C_{r-half}$

$C_{r-half}={\overline{c}}_r{N}_{j}p$

其中${\overline{c}}_r$ 为每件半成品的检测成本。

(6) 成品的装配成本$C_a$

$C_a=c_a{N}_p$

其中$N_p$ 为装配成品的数量。

(7) 成品的检测成本$C_f$

$C_f={\displaystyle \sum z_f{N}_p}{c}_f$

其中$z_f$ 为成品是否需要检测，$N_p$ 为装配成品的数量，$c_f$ 为成品的检测成本。

(8) 不合格成品的调换损失$C_t$

$C_t=n_h{c}_t$

其中$n_h$ 为用户需要调换的成品数，$c_t$ 为不合格成品的调换损失。

(9) 不合格成品的拆解费用$C_r$

$C_r={\displaystyle \sum z_b{c}_r{N}_p}p$

其中$z_b$ 为不合格成品是否需要拆解，$c_r$ 为不合格成品的拆解费用，$p$ 为成品的次品率。

3.2.3. 约束条件的建立

基于目标函数，本文建立了以下约束条件。

(1) 利润的约束

利润约束是企业在追求利润的过程中必须要考虑的现实条件，本文要求该企业在生产电子产品和销售过程中，需要收益来保证该电子产品的可持续生产，要求利润大于0，定义利润如下：

$W>0$

(2) 企业信誉度

企业信誉度[6]是企业在长期的营业过程中积累的无形资产，企业信誉度的高低直接影响了企业的市场竞争力以及该电子产品的销量，进而间接地影响了企业的收益，由于企业对于零件、半成品和成品是否检测，决定了最终销售的成品是否会被客户退回，因此通过统计零件、半成品和成品是否检测的数量和全部检测的比值来表示更新后的企业信誉度，具体表达如下：

$V=\frac{{\displaystyle \sum _{i=1}^8{x}_i+{\displaystyle \sum _{j=1}^3{y}_j}+z_f}}{12}>0.7$

(3) 决策变量的约束

对于决策变量，本文使用0~1规划，所以决策变量的取值为0或1，定义如下0~1决策变量：$x_i$ 表示零配件是否检测，$z_f$ 表示成品是否检测，$z_b$ 表示不合格成品是否拆解，$z_k$ 表示退回的不合格成品是否拆解，$y_i$ 表示半成品是否检测，${\overline{z}}_b$ 表示不合格半成品是否拆解。

因此，关于利润的单目标优化模型如下所示：

$\begin{array}{c}\max W=n_{s}s-\left(C_b+C_d+C_{a-half}+C_{d-half}+C_{r-half}+C_a+C_f+C_r+C_t\right)\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}W>0\hfill \\ z_b=0或1\hfill \\ z_k=0或1\hfill \\ z_f=0或1\hfill \\ x_i=0或1,i=1\cdots 8\hfill \\ y_j=0或1,j=1\cdots 3\hfill \\ y_{bj}=0或1,j=1\cdots 3\hfill \\ V={\displaystyle \sum _{i=1}^8{x}_i+{\displaystyle \sum _{j=1}^3{y}_j+z_f>0.7}}\hfill \end{array}\end{array}$

其中各部分详细计算公式如下所示：

$\{\begin{array}{l}{C}_b={\displaystyle \sum _{i=1}^8{n}_i{c}_{bi}}\hfill \\ C_d={\displaystyle \sum _{i=1}^8{x}_i{n}_i{c}_{di}}\hfill \\ C_{a-half}={\overline{c}}_a{N}_j\hfill \\ C_{d-half}={\overline{c}}_f{\displaystyle \sum _{j=1}^3{N}_j{y}_j}\hfill \\ C_{r-half}={\overline{c}}_r{N}_{j}p\hfill \\ C_a=c_a{N}_p\hfill \\ C_f={\displaystyle \sum z_f{N}_p}{c}_f\hfill \\ C_t=n_h{c}_t\hfill \\ C_r={\displaystyle \sum z_b{c}_r{N}_p}p\hfill \end{array}$

详述为$W$ 成品的总利润，$n_s$ 为合格的成品数，$s$ 为成品单价，$C_b$ 为零配件的购买成本，$C_d$ 为零配件的检测成本，$C_{a-half}$ 为半成品的装配成本，$C_{d-half}$ 为半成品的检测成本，$C_{r-half}$ 为半成品的拆解费用，$C_a$ 为成品的装配成本，$C_f$ 为成品的检测成本，$C_r$ 为不合格成品的拆解费用，$C_t$ 为不合格成品的调换损失，$N_i$ 为零配件$i$ 的购买总数，$c_{bi}$ 为零配件$i$ 的购买成本，$n_i$ 为需要检测的零配件$i$ 的总数，$c_{di}$ 为零配件$i$ 的检测成本，$N_j$ 为拆解的不合格半成品数，${\overline{c}}_f$ 为每件半成品的检测成本，${\overline{c}}_r$ 为不合格半成品的拆解费用，$p$ 为成品的次品率，$N_p$ 为装配成品的数量，$c_a$ 为每件成品的装配成本，$z_f$ 为成品是否需要检测，$c_f$ 为成品的检测成本，$z_b$ 为不合格成品是否需要拆解，$p_c$ 为成品一定为正品的概率，$c_a$ 为每件成品的装配成本，$n_h$ 为用户需要调换的成品数，$c_t$ 为不合格成品的调换损失。

3.3. 基于贪心算法求解单目标优化模型的求解

贪心算法是一种用于求解优化问题的基本算法，通过在每一步选择当前状态下的最佳选择得到局部最优解，希望通过这种局部最优的选择最终能得到全局最优解[7]。贪心算法虽然不保证一定能找到全局最优解，但它能有效地找到最接近最优解的结果。本文我们选择的标准是在企业信誉不低于最低标准的基础上，同时使得企业利润最大化。贪心算法的求解步骤如下：

算法1：贪心算法

Step 1 明确问题目标为最大化利润，同时所有的决策结果使得企业信誉不低于0.7； Step 2 定义一个新的标准来对决策进行选择，该标准涉及最大化利润和企业信誉； Step 3 将所有决策根据新的标准所反馈的数值从高到低排序； Step 4 从排序后得出的列表中，依次选择利润最大的策略，同时对于所选择的项目，检查其企业信誉是否低于0.7，如果满足条件则加入最终选项中； Step 5 通过以上步骤，依次选择利润最大化的项目组合； Step 6 验证最终结果。

基于贪心算法，我们求解得出的最优策略方案为：针对各种零配件，对零配件1、零配件2、零配件3、零配件4、零配件5、零配件6、零配件8进行检测，零配件7不进行检测；针对各种半成品，对半成品2和半成品3进行检测，半成品1不进行检测；针对不合格半成品，对不合格的半成品3进行拆解，对不合格的半成品1和半成品2不进行拆解；针对成品我们不进行检测；针对次成品而言我们不进行拆解，该策略方案在企业信誉为0.75的基础上，具体在仅有200个零配件时，使得企业的利润达到11416元。

4. 结论

本文针对电子产品的生产过程，构建了基于0~1整数规划的单目标优化模型，对生产过程中所涉及到的零件，半成品和成品给出了具体决策，通过具体实例并利用贪心算法求解得到最优决策方案。研究得出，在对部分零配件和半成品进行检测、部分不合格半成品进行拆解，而成品不检测、不合格成品不拆解的策略下，企业信誉可保持在0.75，且在仅有200个零配件时，利润达11416元。在产量增大时，企业的利润也会随之增长，该研究为降低生产成本、提高生产效率和产品质量提供了实践指导，对提高企业收益，增强企业核心竞争力具有重要意义。

5. 算法分析与评估

本文研究的问题涉及到m道工序，n个零配件，复杂性高，涉及多阶段的零配件检测、半成品检测和成品拆解决策。贪心算法在这一问题中表现出了明显的优势。例如，在贪心算法的求解中，零配件7未被检测，半成品1未被拆解，最终利润为11416元，信誉度为0.75。这一方案即满足了基本约束，并且能够快速的得到结果，对于企业的决策提供了更高的效率。

相比较而言，遗传算法通过动态调整检测和拆解策略，建议检测零配件7，并拆解半成品1，最终利润提升至12140元，同时信誉度提高到0.78。这一优化虽然提高了利润，但是计算时间显著增加，求解时间从贪心算法的5秒左右延长到2分钟，这在实时性要求高的场景中可能成为瓶颈。

综合来看，贪心算法的核心优势在于其高效性，适用于需要快速决策的场景，例如在抽样方案设计的过程中，其计算复杂度低，能够在极短时间内提供可行解，适合实时或近实时的生产调度。然而，贪心算法的局部最优性使其在复杂问题中表现不佳，尤其是当目标函数非线性或约束条件复杂时。

NOTES

^*通讯作者。