业务流程管理中的大规模整数规划问题求解

1 概 述

    随着Internet在企业中的广泛应用，企业对信息化技术的依赖越来越强烈，使其必须充分利用内、外部资源，提高效率以适应不断变化的市场需要。在此背景下，美国管理学家哈默与钱皮提出了业务流程再造理论，在全世界掀起了一场流程再造革命。多年后，业务流程管理（business process management）继承了这种管理理念，在企业中运用并释放出活力。业务流程管理是对企业的业务流程进行规范管理的过程，它作为一种管理方法，对业务流程进行全面分析，最终确定企业内部的管理机制。

    业务流程管理就是在一个存在内部事件和外部事件的环境中，由一组相互依赖的业务流程出发，对业务进行描述、理解、表示、组织和维护。由于业务流程是相互依赖的，这就需要对业务流程进行优化配置，提高企业运行效率。业务流程最终可以抽象为一个大规模整数规划问题，规模一般达到几万个变量和十几万个约束以上。

    本文讨论的重点是如何利用计算机求解大规模整数规划问题。

2 整数规划概述

    整数规划是数学规划的一个重要分支，在线性规划中，如果它的某些变量（或全部变量）要求取整数时，这个规划问题就称为整数规划（integer programming）。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题（slack problem）。

    可先用单纯形法求解松弛问题，然后在所得的解中对每个要求取整数值的变量的值进行简单的舍入处理。不过，这样处理的结果很可能不再是整数规划的一个可行解。又因为对每个取整数值的变量都有舍或入2种可能，所以当问题中有3个取整数值的变量x₁，x₂和x₃时，就要考虑2³＝8种可能的舍入方案；当有60个变量x₁，x₂，…，x₆₀时，就要考虑2⁶⁰＝10¹⁸种可能的舍入方案，这时即使高速计算机也无法处理。

    到目前为止，整数规划问题还没有像求解线性规划问题的单纯形方法那样有一个通用且有效的解法，特别是当求解的模型中整数变量比较多时，各种算法计算起来都比较费时间。但是，由于在应用及理论方面提出的许多实际问题都可以归结为整数规划问题，因此，对整数规划的研究在理论和实践上都有着重大意义。

3 计算机求解大规模整数规划问题的整体思路

    在程序中构建一个整数规划问题，可以逐行添加变量及其系数，也可以通过读取固定格式文件（*．mps或*．1p）的方法将问题读入内存。

    问题构建好之后，程序将进入实际解题过程。剩用单纯形和对偶单纯形法求解该问题对应的松弛问题，判断最优解是否满足整数条件，如果满足则输出最优解，否则利用分枝定界法得到最优解。

    计算机求解大规模整数规划问题的程序流程见图1。

图1 计算机求解思路流程