《最优化方法论文》由会员分享，可在线阅读，更多相关《最优化方法论文（8页珍藏版）》请在金锄头文库上搜索。
1、1弹性约束下的线性规划之最优化方法摘 要：线性规划方法是解决最优化问题的有效方法之一，有着极其广泛的应用，在管理学的应用过程中也时常穿插着关于最优化的问题。本文将在古典的线性规划方法的基础上，引入弹性约束一词，以弹性约束下的线性规划类型为对象建立新的数学模型，在解决具体的管理学案例的过程中，寻求其最优化方法，同时为管理决策提供依据。关键词：线性规划；最优化；单纯形法；弹性约束； 保证率前言在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，活得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”
2、。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。线性规划方法是最优化方法中的一个重要部分。但是，经典的线性规划方法，常将目标函数和约束条件都视为确定的。然而，在实际问题中不论目标函数还是约束条件都具有不同形式的不确定性。本文重点引入新的名词弹性约束，以弹性约束下的线性规划类型为对象建立新的数学模型，从而寻求其最优化方法。1、问题的提出某工厂生产甲、乙、丙、丁共4种产品，需用到A,B,C共3种原料，每种产品需要使用的各种原料的数量及其可能获得的利润如表1所示。又A,B两种原料供应量有限，单位生产周期内只能提
3、供一定的数量，而C种原料一经开包使用就必须用足一定量后方可停止使用，且不能单独使用。现有关数据均见下表。问应如何安排生产，方能使该厂所获利润达到最大值?表1：加工产品所需原料及可能获得的利润加工每件产品所需原料原料甲 乙 丙 丁单位周期内原料的供应量或必须使用量2A 1.0 1.2 1.4 1.5 2100B 0.5 0.6 0.6 0.8 1000C 0.7 0.7 0.8 0.8 1300每件利润 12 15 8 10现设甲、乙、丙、丁 4 种产品各自产量分别为 ， ， , 。依题意有 max =121x234xf+15 +8 +101x23x+1.2 +1.4 +1.5 21001234
4、s.t 0.5 +0.6 +0.6 +0.8 1000 (1-1)x0.7 +0.7 +0.8 +0.8 13001x234, , , 034这是一个经典的线性规则问题。可直接利用单纯形法对其进行求解。在以上问题中，现因交通条件的改善，单位生产周期内A,B两种原料的供应量可分别保证在21002200与10001050之间；因技术的改进，C原料的使用量可变为12501300之间。问:在此情况下，应如何安排生产，方能使该厂所获利润Z尽可能地达到最大?显然，这是一个目标函数和约束条件都具有一定的不确定性的线性规划问题。为得到其最优化方法，先给出以下标记、定义和命题。2、标记、定义和命题记C( , ,
5、 ),x( , , )T,b( , , )T,1c2n1x2n1b2nA( )mn,X | Rn, 0.ija允许有一定的变动范围的约束条件，称为弹性约束。所有满足弹性约束条件的元素组成的集合，称为弹性约束集。记加粗的“”表示弹性约束，我们可理解为大约小于的意思。 | , （i=1,2，,m） ；M= |0。0d用于表示约束条件变化范围的量，称为伸缩指标，记为0（i=1 ， 2，m）记 =( , , )Ti d12md弹性约束集中的元素与满足弹性约束条件的程度之间的对应关系，称为满足程度函数。记 ( )表示任意的 ，满足 （i 1，2，m）的程度，DiuxxiD1nijjaxb且1， ,1ni
6、jjaxib( ) 11/ ( - ) ， + ,Diux0d1nijjaxibi1nijjid0， + .1nijjaxib记 ( )表示任意 X 函数在 X 处取得最大值的程度，且Muxx0, ,1njcx0f( ) 1/ ( - ), + ,Mux0d1njcx0f0f1nj0fd1, + .0fd1njcx记 = ， (X)=inf ( ) , ( ), , ( )。D12mDu1Dx2uDmu“”运算符定义为 ab=maxa,b， “”定义为 =min , ，其中 ,aba0,1.b 表示弹性约束下的目标函数最优值的保证率，0,1。3、模型的建立与求解对应于弹性约束的线性规划问题可以
7、写成：求 maxf= ,st b, 0, (3-1)xCxA4对应于其中的约束条件，可转化为 max ；目标函数可转为求 max ,模型()Dxu()Mxu（3-1） ，可转换成如下模型：max（ ） (3-2)()Mxu()Dx根据命题 1，模型(3-2)可进一步转换成如下线性规划问题：max =g1-1/ （ ),（i=1，2，m）id1nijjaxibs.t 1/ ( - )01njc0f01, , , 0.x2n将上式整理可得以下模型：max =g+ ,（ i=1，2，m）,1nijjaxidibs.t - (3-3)1njc00f01, , , 0.1x2n假设( , , , , )
8、 T 是问题(3-3)的最优解，则 =( , , , )T 是问题*1x2*nx *x1*2*nx(3-1)在限定条件 + 之后的解， = 是问题(3-1)在条件 0f0fd*f*1njc0f+ 下所得目标函数的最大值。0fd关于问题(3-3) 中 与 + 的确定，可由实际问题给出，也可参照生产实践经验0f0d或平时生产统计数据给定，还可以根据以下问题 +AxbAxbd求 max = , s.t 0 （1） s.t 0 （2）fCx5的解，决策者采用悲观、乐观、等可能、折衷主义等策略进行确定：设问题（1）的解为 ，问题（2）的解为 ，因 0，故问题（2）放宽了问题（1）的约束条件，*f *fd
9、从而有 0。弹性约束使用的目标在于希望在一定“保证率”下适当扩大收益（即增*d大目标函数值） ，故应取 + ，但 取值越大，所冒风险越大，当 时，0f*f0f 0f*d实现 的可能性只能是 0，故还应取 。一般地，可令 表示乐观系数0f *da（0 1） ， = ( )+(1- ) ,则有：a1fa*daf（1） 若采用悲观主义决策准则，可取 ， + ；0f*0f1f（2） 若采用乐观主义决策准则，可取 ， + 。1d*4、案例求解下面对本文开始所提出的问题基础具体的求解： 利用单纯形法，首先求得问题（11）的最佳基可行解 和最优函数值为x( , , , )T(8100/7,5000/7,0,
10、0) T, 171000/7.x23x4 *f 利用单纯形法，求解以下问题：求 max 12 +15 +8 +10f1234+1.2 +1.4 +1.5 2100xxs.t 0.5 +0.6 +0.6 +0.8 1000 (4-1)12340.7 +0.7 +0.8 +0.8 1300, , , 01x234得其最优基可行解 及最优解 为：*fd( , , , )T(1500/7,11000/7,0,0) T,x123x418700/7, 1200/7*fd* 最后求解弹性约束线性规划问题：max 12 +15 +8 +10f1x234x6+1.2 +1.4 +1.5 21001x23x40.
11、5 +0.6 +0.6 +0.8 1000s.t 0.7 0.7 0.8 0.8 13001234x, , , 0x234给定 100， 50。为得到以上问题的解答，先令 1/3，得1dd a17500/7，采用乐观主义决策准则取 17500/7， 8000/7 ，且有式(3-3)将问*f 0f0d题(4-1 )转换为如下经典线性规划问题：求 max g+1.2 +1.4 +1.5 +1002100+100,1x23x40.5 +0.6 +0.6 +0.8 +501000+50s.t 0.7 0.7 0.8 0.8 +501300+50,1234x12 +15 +8 +10 8000/7175
12、00/7x3401, , , 0234将其化为标准形式，利用单纯形法同样可求得其最优基可行解为：( , , , ,) T(4100/7,8600/7,0,0, 2/5 )T.x123x4因此得 ( , , , )T(4100/7,8600/7,0,0) T是问题(4-1)在选择17500/7， 8000/7 时的最优解，且保证率 =2/5 获得最优目标值0f0d124100/7+15 8600/7178200/7。与问题(1-1 )相比，收益增加了 1028 元，增幅为 4.2%。在问题(4-1) 中，采用悲观主义决策准则取 17500/7， 8000/7，则得0f0d3/4， 17400/7
13、；若由生产经验直接取 16500/7， 15000/7，则得f2/3，最优值 175000/725000。f75、总结需要指出的是，使用模型(3-3)所得结果与 和 的选取有关。一般地，若 0fd0f和 ，则 将取得最大化。但所得 值增幅不大，若 或 ，因 *f0d* 0f*0d*将取较小值，故 值增幅较大。但在具体的操作中，将取决于决策者的胆识和敢于承f担风险的能力，因此这种方法在管理学的应用中占有重要一席。8参考文献1运筹学)教材编写组 .运筹学 (修订版)M. AL 京:清华大学出版社，1990.2吴良刚主编.运筹学 M.长沙: 湖南人民出版社，2001.3.3于春田 李法朝主编.运筹学 M. 北京: 科学出版社，2006.2.4王文博编著.计量经济学 M.西安: 西安交通大学出版社，2004.10.
