混合线性规划问题模型的研究.doc

混合线性规划问题模型的研究
李骥昭 刘义山 1 问题的提出

以≤符号表示的函数约束称为资源约束,因为这些限制要求使用的资源必须小于或等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。混合线性规划问题模型的研究
李骥昭 刘义山 1 问题的提出

以≤符号表示的函数约束称为资源约束,因为这些限制要求使用的资源必须小于或等于所能提供的资源的数量。资源分配问题的共性就是它们的函数约束全部为资源约束。以≥符号表示的函数约束为收益约束,因为它们的形式为收益取得的水平必须大于或等于最低可接受水平。收益约束反映了管理层所规定的目标。以=符号表示的函数约束称为确定需要的约束,因为它们表示了一定数量的确定的需求的约束,提供的数量等于要求的数量。而许多线性规划问题并不能直接归入三类中的某一类,一些问题勉强归入一类,另一些问题却没有一类占主导地位的函数约束,不能归于这三类的任何线性规划的问题称为混合问题。混合问题的线性规划的建模过程与其他三类线性规划问题类似。但是,其他三种线性规划问题仅仅涉及到三类函数约束(资源约束、收益约束、确定需要的约束)的一种,并以之为特色,而混合问题可以同时包含三类约束,因此有必要探讨三种不同的函数约束是如何在同一个问题中产生的。

2 建立混合线性规划问题的数学模型

统利公司经营一个回收中心,专门从事四种固体废弃物的回收,并将回收物处理,混合成为可销售的产品。根据混合时各种材料的比例,可将该产品分成不同的等级(表1)。尽管在混合各种等级产品时允许一定的机动性,但每一等级产品中各种材料的最大值和最小值都必须符合下面质量标准的规定。这些规定与混合的成本以及每一等级产品的售价都在表1中给出。
表1(单位:元)

回收中心可以从一些渠道定期收集到所需的固体废弃物,因此,可以获得维持稳定作业的处理量。
表2

管理层决定在表1和表2所列的约束之内,有效的将各种材料分配到各等级的产品中去,以实现每周的总利润最大。这便是一个混合线性规划问题,因为资源有限,收益受到限制,以及确定的需求,该问题就有了相当多的约束,归纳如下:①有限的资源,表2的第2栏所示。此外,表1的第2栏还表明材料1与材料3的用量有限,这些有限的资源都将形成资源的约束条件。②规定的收益:表2的右边显示最低可接受的收益水平是可获得的材料的一半,而表1规定材料2的最低可接受的使用量,这些都是收益约束。③确定需求的约束:如表1第2栏所示的材料4的固定用量。表2右边所示的处理固体废弃物的固定开销。
建模的具体过程如下:
假定有12个决策变量:

3 建立和分析混合线性规划模型的标准体系

处理混合的线性规划问题是没有惟一正确的线性规划模型的,在整个研究的问题中,模型往往会被不断修改和扩展。许多实际的线性规划建模往往包含上百甚至上千个决策与约束。在这些情形中,常常会有要不要考虑进模型的许多模棱两可的问题,对于如此复杂的线性规划问题,管理层的投入与支持是至关重要的。如果最初的模型一旦被检验有效,就可以使用它的许多变异的模型。究竟使用哪一种变异的模型必须依赖于许多因素,包括问题最合理的假设、模型最