最优化方法论文

1弹性约束下的线性规划之最优化方法摘要：线性规划方法是解决最优化问题的有效方法之一，有着极其广泛的应用，在管理学的应用过程中也时常穿插着关于最优化的问题。本文将在古典的线性规划方法的基础上，引入弹性约束一词，以弹性约束下的线性规划类型为对象建立新的数学模型，在解决具体的管理学案例的过程中，寻求其最优化方法，同时为管理决策提供依据。关键词：线性规划；最优化；单纯形法；弹性约束；保证率前言在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，活得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。线性规划方法是最优化方法中的一个重要部分。但是，经典的线性规划方法，常将目标函数和约束条件都视为确定的。然而，在实际问题中不论目标函数还是约束条件都具有不同形式的不确定性。本文重点引入新的名词弹性约束，以弹性约束下的线性规划类型为对象建立新的数学模型，从而寻求其最优化方法。1、问题的提出某工厂生产甲、乙、丙、丁共4种产品，需用到A,B,C共3种原料，每种产品需要使用的各种原料的数量及其可能获得的利润如表1所示。又A,B两种原料供应量有限，单位生产周期内只能提供一定的数量，而C种原料一经开包使用就必须用足一定量后方可停止使用，且不能单独使用。现有关数据均见下表。问应如何安排生产，方能使该厂所获利润达到最大值?表1：加工产品所需原料及可能获得的利润原料加工每件产品所需原料单位周期内原料的供应量或必须使用量甲乙丙丁2A1.01.21.41.5≤2100B0.50.60.60.8≤1000C0.70.70.80.8≤1300每件利润1215810现设甲、乙、丙、丁4种产品各自产量分别为1x，2x，3x,4x。依题意有maxf=121x+152x+83x+104x1x+1.22x+1.43x+1.54x≤2100s.t0.51x+0.62x+0.63x+0.84x≤1000(1-1)0.71x+0.72x+0.83x+0.84x≥13001x,2x,3x,4x≥0这是一个经典的线性规则问题。可直接利用单纯形法对其进行求解。在以上问题中，现因交通条件的改善，单位生产周期内A,B两种原料的供应量可分别保证在2100～2200与1000～1050之间；因技术的改进，C原料的使用量可变为1250～1300之间。问:在此情况下，应如何安排生产，方能使该厂所获利润Z尽可能地达到最大?显然，这是一个目标函数和约束条件都具有一定的不确定性的线性规划问题。为得到其最优化方法，先给出以下标记、定义和命题。2、标记、定义和命题①记C＝(1c,2c,…,nc),x＝(1x,2x,…,nx)T,b＝(1b,2b,…,nb)T,A＝(ija)m×n,X＝{x|x∈Rn,x≥0}.②允许有一定的变动范围的约束条件，称为弹性约束。所有满足弹性约束条件的元素组成的集合，称为弹性约束集。记加粗的“≤≌”表示弹性约束，我们可理解为大约小于的意思。iD＝｛x|1nijjjax≤ib,x∈X｝（i=1,2，…,m）；M=｛f|0ff0f+0d,x∈X｝,其中f表示目标函数，0f+0d与0f分别表示希望目标函数值达到的最优的上下界，0d0。③用于表示约束条件变化范围的量，称为伸缩指标，记为id≥0（i=1，2，…，m）3记d=(1d,2d,…,md)T④弹性约束集中的元素与满足弹性约束条件的程度之间的对应关系，称为满足程度函数。记Diu(x)表示任意的x∈iD，满足1nijjjax≤ib（i＝1，2，…，m）的程度，且1，1nijjjax≤ib,Diu(x)1－1/0d(1nijjjax-ib)，ib≤1nijjjax≤ib+id,0，1nijjjax＞ib+id.记Mu(x)表示任意x∈X函数在X处取得最大值的程度，且0,1njjjcx＜0f,Mu(x)1/0d(1njjjcx-0f),0f≤1njjjcx＜0f+0d,1,0f+0d≤1njjjcx.⑤记D=1D∩2D∩…∩mD，Du(X)=inf{1Du(x),2Du(x),…,Dmu(x)}。⑥“∨”运算符定义为a∨b=max{a,b}，“∧”定义为a∧b=min{a,b}，其中a,b∈[0,1].⑦λ表示弹性约束下的目标函数最优值的保证率，λ∈[0,1]。3、模型的建立与求解对应于弹性约束的线性规划问题可以写成：求maxf=xC,s×txA＜≌b,x≥0,(3-1)对应于其中的约束条件，可转化为max()Dxu；目标函数可转为求max()Mxu,模型（3-1），可转换成如下模型：max（()Mxu∧()Dxu）(3-2)根据命题1，模型(3-2)可进一步转换成如下线性规划问题：4maxg=λ1-1/id（1nijjjax－ib)≥λ,（i=1，2，…，m）s.t1/0d(1njjjcx-0f)≥λ0≤λ≤1,1x,2x,…,nx≥0.将上式整理可得以下模型：maxg=λ1nijjjax+idλ≤ibid,（i=1，2，…，m）,s.t1njjjcx-0dλ≥0f(3-3)0≤λ≤1,1x,2x,…,nx≥0.假设(*1x,*2x,…,*nx,λ)T是问题(3-3)的最优解，则*x=(*1x,*2x,…,*nx)T是问题(3-1)在限定条件0f＜f＜0f+0d之后的解，*f=*1njjjcx是问题(3-1)在条件0f＜f＜0f+0d下所得目标函数的最大值。关于问题(3-3)中0f与0f+0d的确定，可由实际问题给出，也可参照生产实践经验或平时生产统计数据给定，还可以根据以下问题Ax＜bAx＜b+d求maxf=Cx,s.tx≥0（1）s.tx≥0（2）的解，决策者采用悲观、乐观、等可能、折衷主义等策略进行确定：设问题（1）的解为*f，问题（2）的解为**fd，因d＞0，故问题（2）放宽了问题（1）的约束条件，从而有*d＞0。弹性约束使用的目标在于希望在一定“保证率”下适当扩大收益（即增大目标函数值），故应取0f+0d＞*f，但0f取值越大，所冒风险越大，当0f＞**fd时，5实现0f的可能性只能是0，故还应取0f＜**fd。一般地，可令a表示乐观系数（0≤a≤1），1f=a(**fd)+(1-a)*f,则有：（1）若采用悲观主义决策准则，可取0f＝*f，0f+0d＝1f；（2）若采用乐观主义决策准则，可取0f＝1f，0f+0d＝**fd。4、案例求解下面对本文开始所提出的问题基础具体的求解：①利用单纯形法，首先求得问题（1—1）的最佳基可行解x和最优函数值为x＝(1x,2x,3x,4x)T＝(8100/7,5000/7,0,0)T,*f＝171000/7.②利用单纯形法，求解以下问题：求maxf＝121x+152x+83x+104x1x+1.22x+1.43x+1.54x≤2100s.t0.51x+0.62x+0.63x+0.84x≤1000(4-1)0.71x+0.72x+0.83x+0.84x≥13001x,2x,3x,4x≥0得其最优基可行解x及最优解**fd为：x＝(1x,2x,3x,4x)T＝(1500/7,11000/7,0,0)T,**fd＝18700/7,*d＝1200/7③最后求解弹性约束线性规划问题：maxf＝121x+152x+83x+104x1x+1.22x+1.43x+1.54x≤≌21000.51x+0.62x+0.63x+0.84x≤≌1000s.t－0.71x－0.72x－0.83x－0.84x≤≌－13001x,2x,3x,4x≥06给定1d＝100，2d＝3d＝50。为得到以上问题的解答，先令a＝1/3，得*f＝17500/7，采用乐观主义决策准则取0f＝17500/7，0d＝8000/7，且有式(3-3)将问题(4-1)转换为如下经典线性规划问题：求maxg＝λ1x+1.22x+1.43x+1.54x+100λ≤2100+100,0.51x+0.62x+0.63x+0.84x+50λ≤1000+50s.t－0.71x－0.72x－0.83x－0.84x+50λ≤－1300+50,121x+152x+83x+104x－8000/7λ≥17500/70≤λ≤11x,2x,3x,4x≥0将其化为标准形式，利用单纯形法同样可求得其最优基可行解为：x＝(1x,2x,3x,4x,λ)T＝(4100/7,8600/7,0,0,2/5)T.因此得x＝(1x,2x,3x,4x)T＝(4100/7,8600/7,0,0)T是问题(4-1)在选择0f＝17500/7，0d＝8000/7时的最优解，且保证率λ=2/5获得最优目标值f＝12×4100/7+15×8600/7＝178200/7。与问题(1-1)相比，收益增加了1028元，增幅为4.2%。在问题(4-1)中，采用悲观主义决策准则取0f＝17500/7，0d＝8000/7，则得λ＝3/4，f＝17400/7；若由生产经验直接取0f＝16500/7，0d＝15000/7，则得λ＝2/3，最优值f＝175000/7＝25000。5、总结需要指出的是，使用模型(3-3)所得结果与0f和0d的选取有关。一般地，若0f＜*f和0d＜*d，则λ将取得最大化。但所得f值增幅不大，若0f＞*f或0d＞*d，因λ将取较小值，故f值增幅较大。但在具体的操作中，将取决于决策者的胆识和敢于承担风险的能力，因此这种方法在管理学的应用中占有重要一席。7参考文献[1]《运筹学)教材编写组.运筹学(修订版)[M].AL京:清华大学出版社，1990.[2」吴良刚主编.运筹学M].长沙:湖南人民出版社，2001.3.[3」于春田李法朝主编.运筹学〔M].北京:科学出版社，2006.2.[4」王文博编著.计量经济学〔M].西安:西安交通大学出版社，2004.10.