最优化方法论文

1、弹性约束下的线性规划之最优化方法摘要：线性规划方法是解决最优化问题的有效方法之一，有着极其广泛的应用，在管理学的应用过 程中也时常穿插着关于最优化的问题。本文将在古典的线性规划方法的基础上，引入弹性约束一词， 以弹性约束下的线性规划类型为对象建立新的数学模型，在解决具体的管理学案例的过程中，寻求 其最优化方法，同时为管理决策提供依据。关键词：线性规划；最优化；单纯形法；弹性约束；保证率前言在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和 时间去办更多的事，活得最大的效益，在管理学中被看作是生产者的利润最大化和消费 者的效用最大化，如果从数学的角度来看就被看作是“最优化问

2、题”。在最优化的研究 生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函 数”的最大（或最小）值，其解法称为最优化方法。线性规划方法是最优化方法中的一个 重要部分。但是，经典的线性规划方法，常将目标函数和约束条件都视为确定的。然而， 在实际问题中不论目标函数还是约束条件都具有不同形式的不确定性。本文重点引入新 的名词弹性约束，以弹性约束下的线性规划类型为对象建立新的数学模型，从而寻求其 最优化方法。1、问题的提出某工厂生产甲、乙、丙、丁共4种产品，需用到A,B,C共3种原料，每种产品需要使 用的各种原料的数量及其可能获得的利润如表1所示。又A,B两种原料供应量有限，单

3、位 生产周期内只能提供一定的数量，而C种原料一经开包使用就必须用足一定量后方可停 止使用，且不能单独使用。现有关数据均见下表。问应如何安排生产，方能使该厂所获 利润达到最大值？表1：加工产品所需原料及可能获得的利润原料加工每件产品所需原料单位周期内原料的供应量或必须使用量甲乙丙丁A1.01.21.41.52100B0.50.60.60.8*00C0.70.70.80.81300每件利润1215810现设甲、乙、丙、丁 4种产品各自产量分别为土，七，七，。依题意有 TOC o 1-5 h z max f =12 x +15 x +8 x +10 x 1234,x +1.2x +1.4x +1.5

4、x 21001234s.t0.5 x +0.6x +0.6x +0.8 x 500(1-1)12341 0.7 x +0.7 x +0.8 x +0.8 x 13001234x , x , x , x 00).允许有一定的变动范围的约束条件，称为弹性约束。所有满足弹性约束条件的元 素组成的集合，称为弹性约束集。记加粗的“W丝”表示弹性约束，我们可理解为大约 小于的意思。D = x l 才j=1a x Wb ,x E X (i=1,2,，m)； M= f l f f 0。 0000用于表示约束条件变化范围的量，称为伸缩指标，记为d, 0 (i=1，2,，m)记d =(d ,d，d )T弹性约束集

5、中的元素与满足弹性约束条件的程度之间的对应关系，称为满足程度函数。记u (x)表示任意的xED,满足EDia x Wb (i=1, 2,，m)的程度，且j=1EaxW b , j =1j j1 1/d (a xj=1b W E a x W b + d ,i ij j i ij=1I。，Eax b +d .ij j i i j=1记 (x)表示任意x EX函数在X处取得最大值的程度，且乙 x V f , j j oj=11/d (乙 x.j=1fo)，f W E c x V f + d ,0j j 00j=1I1，f + d W Ec xj=1记d = q n D2 nn d ,u (X)=in

6、f uD1(x) ,u (x),，u (x)。“V”运算符定义为aVb=maxa,b, “八”定义为a A b =min a, b ,其中a, b E 0,1.入表示弹性约束下的目标函数最优值的保证率，入e0,1o3、模型的建立与求解对应于弹性约束的线性规划问题可以写成:(3-1)求 maxf= C ,sXt A Vb, x N0,对应于其中的约束条件，可转化为maxuD( ) ；目标函数可转为求 maxu(),模型(3-1),可转换成如下模型:max (u A u )(3-2)根据命题1,模型(3-2 )可进一步转换成如下线性规划问题:max g =K1-1/d (才 a x b )入，(i

7、=1, 2,，m)i ij j ij=1s.t1/d (c x - f )入0 j j 0j=1L 0忍入 1, X , X ,，x 0.、一12n将上式整理可得以下模型:max g =Ka.x. +d入j =1 j j(i=1, 2,，m),s.t J二x-d入jj 0j=1f0(3-3)0W入 W1, x1x 0.假设（x*, x *，x *,入）T是问题（3-3）的最优解，则x*=（x*,12n1（3-1）在限定条件f V f V f + d之后的解，f * = cx *是问题（3-1）在条件f V f V 000j j0j=1f0 + d0下所得目标函数的最大值。关于问题（3-3）中f

8、0与了网 的确定，可由实际问题给出，也可参照生产实践经验或平时生产统计数据给定，还可以根据以下问题* Ax V bAx V b + d求 max f = Cx, s.tx N0(1) s.tx N0(2)的解，决策者采用悲观、乐观、等可能、折衷主义等策略进行确定：设问题（1）的解 为f *，问题（2）的解为f* + d*，因d 0，故问题（2）放宽了问题（1）的约束条件， 从而有d* 0。弹性约束使用的目标在于希望在一定“保证率”下适当扩大收益（即增 大目标函数值），故应取f + d f，但f取值越大，所冒风险越大，当f f + d时， 00*00*实现f的可能性只能是0,故还应取f V f

9、+ d。一般地，可令a表示乐观系数 00*(0忍a 1), f = a(f* + d*)+(1-a)f*,则有:(1)若采用悲观主义决策准则，可取f0 = f*f0 + d0 = fi；(2)若采用乐观主义决策准则，可取f0 = f,4、案例求解下面对本文开始所提出的问题基础具体的求解:利用单纯形法，首先求得问题(11)的最佳基可行解和最优函数值为 TOC o 1-5 h z x = (x , x , x , x )t= (8100/7, 5000/7, 0, 0)t, f =171000/7. 1234*利用单纯形法，求解以下问题：求 max f =12七+15x2 +8x3 +10 x4C

10、 x +1.2x +1.4x +1.5x 2100 1234s.t0.5 x +0.6x +0.6x +0.8 x 1000(4-1)12340.7 x +0.7 x +0.8 x +0.8 x 13001234x x x x 0:1 523 4得其最优基可行解x及最优解f +d为：x = ( x , x , x, x )t= (1500/7, 11000/7, 0, 0)t, 1234f + d =18700/7, d = 1200/7最后求解弹性约束线性规划问题：max f =12 x +15 x +8 x +10 x1234C x +1.2x +1.4x +1.5x 210012340.

11、5 x +0.6 x +0.6 x +0.8 x 310001234s.t一 0.7七0.7x2 0.8七0.8x4 3 1300 x x x x 0i 1 2 3 4给定d1 =100, d2 = d3 =50。为得到以上问题的解答，先令a =1/3,得f* =17500/7, 采用乐观主义决策准则取f = 17500/7, d0 =8000/7，且有式(3-3)将问题(4-1)转换为如 下经典线性规划问题：求 max g =K TOC o 1-5 h z C X +1.2% +1.4% +1.5x +100入 2100+100, 12340.5 % +0.6 % +0.6 % +0.8 %

12、 +50入 1000+50 1234s.t 0.7% 0.7% 0.8% 0.8% +50入 1300+50,123412 % +15 % +8 % +10 % 8000/7A N17500/712340忍入1% % % % 0-1，2，3，4 0将其化为标准形式，利用单纯形法同样可求得其最优基可行解为:% = (% , % , % , %，入)t= (4100/7, 8600/7, 0, 0, 2/5)t. 1234因此得 % = (% , % , % , % )t = (4100/7, 8600/7, 0, 0)t 是问题(4-1)在选择 f =1234017500/7, d0 =8000

13、/7时的最优解，且保证率入=2/5获得最优目标值f =12X4100/7+15 X8600/7 = 178200/7。与问题(1-1)相比，收益增加了 1028元，增幅为4.2%。在问题(4-1)中，采用悲观主义决策准则取f = 17500/7, d0 =8000/7,则得入=3/4, f =17400/7；若由生产经验直接取f = 16500/7, d0 =15000/7,则得入=2/3,最优值f =175000/7=25000。5、总结需要指出的是，使用模型(3-3)所得结果与f和d的选取有关。一般地，若f V f和 000*d V d，则入将取得最大化。但所得f值增幅不大，若f f或d d，因入将取较 0*0