最优化方法论文.doc

弹性约束下的线性规划之最优化方法摘 要：线性规划方法是解决最优化问题的有效方法之一，有着极其广泛的应用，在管理学的应用过程中也时常穿插着关于最优化的问题。本文将在古典的线性规划方法的基础上，引入弹性约束一词，以弹性约束下的线性规划类型为对象建立新的数学模型，在解决具体的管理学案例的过程中，寻求其最优化方法，同时为管理决策提供依据。关键词：线性规划；最优化；单纯形法；弹性约束； 保证率前言在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，活得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。线性规划方法是最优化方法中的一个重要部分。但是，经典的线性规划方法，常将目标函数和约束条件都视为确定的。然而，在实际问题中不论目标函数还是约束条件都具有不同形式的不确定性。本文重点引入新的名词弹性约束，以弹性约束下的线性规划类型为对象建立新的数学模型，从而寻求其最优化方法。1、问题的提出某工厂生产甲、乙、丙、丁共4种产品，需用到A,B,C共3种原料，每种产品需要使用的各种原料的数量及其可能获得的利润如表1所示。又A,B两种原料供应量有限，单位生产周期内只能提供一定的数量，而C种原料一经开包使用就必须用足一定量后方可停止使用，且不能单独使用。现有关数据均见下表。问应如何安排生产，方能使该厂所获利润达到最大值?表1：加工产品所需原料及可能获得的利润原料加工每件产品所需原料单位周期内原料的供应量或必须使用量甲乙丙丁A1.01.21.41.52100B0.50.60.60.81000C0.70.70.80.81300每件利润1215810现设甲、乙、丙、丁4种产品各自产量分别为 ，,。依题意有max=12+15+8+10 +1.2+1.4+1.52100 s.t 0.5+0.6+0.6+0.81000 (1-1) 0.7+0.7+0.8+0.81300 ,0这是一个经典的线性规则问题。可直接利用单纯形法对其进行求解。在以上问题中，现因交通条件的改善，单位生产周期内A,B两种原料的供应量可分别保证在21002200与10001050之间；因技术的改进，C原料的使用量可变为12501300之间。问:在此情况下，应如何安排生产，方能使该厂所获利润Z尽可能地达到最大?显然，这是一个目标函数和约束条件都具有一定的不确定性的线性规划问题。为得到其最优化方法，先给出以下标记、定义和命题。2、标记、定义和命题记C(,),x(, )T,b(,)T,A()mn,X|Rn, 0.允许有一定的变动范围的约束条件，称为弹性约束。所有满足弹性约束条件的元素组成的集合，称为弹性约束集。记加粗的“”表示弹性约束，我们可理解为大约小于的意思。|,（i=1,2，,m）；M=|0。用于表示约束条件变化范围的量，称为伸缩指标，记为0（i=1，2，m）记=(, )T弹性约束集中的元素与满足弹性约束条件的程度之间的对应关系，称为满足程度函数。记()表示任意的，满足（i1，2，m）的程度，且 1， ,() 11/( - ) ， +, 0， +.记()表示任意X函数在X处取得最大值的程度，且 0, ,() 1/(- ), +, 1, +.记=，(X)=inf() ,(), , ()。“”运算符定义为ab=maxa,b，“”定义为=min,，其中,0,1.表示弹性约束下的目标函数最优值的保证率，0,1。3、模型的建立与求解对应于弹性约束的线性规划问题可以写成：求maxf=,stb, 0, (3-1)对应于其中的约束条件，可转化为max；目标函数可转为求max,模型（3-1），可转换成如下模型：max（） (3-2)根据命题1，模型(3-2)可进一步转换成如下线性规划问题： max=1-1/（),（i=1，2，m） s.t 1/(- ) 01, , 0.将上式整理可得以下模型： max= +,（ i=1，2，m）, s.t - (3-3) 01, , 0.假设(, , , )T是问题(3-3)的最优解，则=(, , ,)T是问题(3-1)在限定条件+之后的解，=是问题(3-1)在条件+下所得目标函数的最大值。关于问题(3-3)中与+的确定，可由实际问题给出，也可参照生产实践经验或平时生产统计数据给定，还可以根据以下问题 +求max=, s.t 0 （1） s.t 0 （2）的解，决策者采用悲观、乐观、等可能、折衷主义等策略进行确定：设问题（1）的解为，问题（2）的解为，因0，故问题（2）放宽了问题（1）的约束条件，从而有0。弹性约束使用的目标在于希望在一定“保证率”下适当扩大收益（即增大目标函数值），故应取+，但取值越大，所冒风险越大，当时，实现的可能性只能是0，故还应取。一般地，可令表示乐观系数（01），=()+(1-),则有：（1） 若采用悲观主义决策准则，可取，+；（2） 若采用乐观主义决策准则，可取，+。4、案例求解下面对本文开始所提出的问题基础具体的求解： 利用单纯形法，首先求得问题（11）的最佳基可行解和最优函数值为 (,)T(8100/7,5000/7,0,0)T, 171000/7. 利用单纯形法，求解以下问题：求max12+15+8+10 +1.2+1.4+1.52100 s.t 0.5+0.6+0.6+0.81000 (4-1) 0.7+0.7+0.8+0.81300 ,0得其最优基可行解及最优解为： (,)T(1500/7,11000/7,0,0)T, 18700/7, 1200/7 最后求解弹性约束线性规划问题：max12+15+8+10 +1.2+1.4+1.52100 0.5+0.6+0.6+0.81000 s.t 0.70.70.80.81300 ,0给定100，50。为得到以上问题的解答，先令1/3，得17500/7，采用乐观主义决策准则取17500/7，8000/7，且有式(3-3)将问题(4-1)转换为如下经典线性规划问题：求max +1.2+1.4+1.5+1002100+100, 0.5+0.6+0.6+0.8+501000+50 s.t 0.70.70.80.8+501300+50, 12+15+8+108000/717500/7 01 ,0将其化为标准形式，利用单纯形法同样可求得其最优基可行解为：(,)T(4100/7,8600/7,0,0, 2/5)T.因此得(,)T(4100/7,8600/7,0,0)T是问题(4-1)在选择17500/7，8000/7时的最优解，且保证率=2/5获得最优目标值124100/7+158600/7178200/7。与问题(1-1)相比，收益增加了1028元，增幅为4.2%。在问题(4-1)中，采用悲观主义决策准则取17500/7，8000/7，则得3/4，17400/7；若由生产经验直接取16500/7，15000/7，则得2/3，最优值175000/725000。5、总结需要指出的是，使用模型(3-3)所得结果与和的选取有关。一般地，若和，则将取得最大化。但所得值增幅不大，若或，因将取较小值，故值增幅较大。但在具体的操作中，将取决于决策者的胆识和敢于承担风险的能力，因此