线性规划-单纯形算法包文档

1、线性规划单纯形算法包文档本文档是关于线性规划单纯形算法包的说明和使用依据的描述。包括两个部分，第一部分是算法理论，第二部分是算法包的使用说明。第一部分：算法理论描述：线性规划属于优化问题，具有以下特征：每一个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的(也有可能是非正或没有约束的值)；存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示；有一个要求达到的目标，它可以用决策变量的线性函数(称为目标函数)来表示，按问题的不同，要求目标函数实现最大化或最小化。数学模型的一般形式为：目标函数：max(min)z=cx+cx+Cx(1.1)1

2、122nn约束条件：anxi+ai2X2+amXn(=，)Sa21X1+a22X2+a2nXn(=，)b2am1X1+am2X2+肚(=，bn(12)XX2，.,xn三(W，无约束)0(1.3)方程(1.1)称为目标函数；(1.2)、(1.3)称为约束条件求解理论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点。线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点得到。原则上枚举所有的基可行解，然后一一比较，最终就可能找到最优解。单纯形法是求解线性规划问题的一种可行办法，它通过从可行域中某个基可行解(一个顶点)开始，转换到另一个基可行解

3、，当目标函数达到最大值时，问题得到求解。计算步骤：(1)找出初始可行基，确定初始基可行解，建立初始单纯形表；(2)检验各非基变量xj的检验数是b=c-cai,若b.W0,j=m+l,m+2,，n;则已jjijji=1得到最优解,可停止计算,否则转入下一步；在b0,j=m+l,m+2,，n中若有某个b对应xk的系数列向量PkW0,则此问题是无jkkk界,停止计算,否则转入下一步；根据max(b0)=b，确定xk的换入变量，根据0规则计算jkkbb0=mm(-aik0)=i-aaiklk可确定xl为换出变量，转入下一步；(5)以alk为主元素进行迭代(高斯消去法)，把xk所对应的列向量ra)r0、

4、1ka02kP=*变换为ka1ikak丿mkCStandardElementCSiaplexEorClass-CStandardElementCSiaplexColiMnClass4CStandardElementCSiaplexEorClass-CStandardElementIDisposable、ICStaJidardCoUectioiiGenericClass日字段i*m_blsBas已VariableT-/m_d：alue，-ym_lrjudge日JI性日字段i*m_blsBas已VariableT-/m_d：alue，-ym_lrjudge日JI性雪Irjudge雪l5Base：a

5、i-iable雪V：alue日方法三CSimplexColuinn曲Disposea字段m_Col寸/m_daConstiaintsf*m_dJ；e三om_ce話m_OutJudge日BSF:沾eV：廿iableColunirL:舒ElaseVariableValue姿Outjudge督ResourceTSf8this日方法曲CSirnplcmRow+1重蓋）沖Dispose曲GetOutJudgeCSiaplexB.owCollectionClass-CCStandardCol1ectian0方法CSiBplexColumCollectionClass-tCStandardCollectia

6、na方注QCSimplexJLowCoilectioil+1重载）X/CSimplexColvunnCoilection（+1重载）OIDisposableCSiaplezTableClass曰字段，-j/rTi_colunins,ni_r:Table（+1重载D=VDispose占QGetMokTar驴t占。GetM：ikTai-getResillt占QGoToStatge2屈。Initial詐Optimize+1重载）Ti:HTLsfoim|CLineaiPrograaaingIStaticClass方法m_bITeedFreCheckElataermiTiOpSIsTart&inNeel

7、iFreCheckllatad：aJtescnxrce5daT：argetiJniConstrairLtsGetResiiltLlikekrtifici：alBaseFositivateFLesourcePreCheckllataSetilata（+1重载）VariableSubstitute在类CSimplexTable中包装了单纯形表的行集合和列集合，行集合CSimplexRowColleion是CSimplexRow类对象的集合，列集合CSimplexColumnColleion是CSimplexColumn类对象的集合，CSimplexRow和CSimplexColumn派生于基本元素

8、类CStandElement，CSimplexRowColleion和CSimplexColumnColleion派生于基本集合类CStandCollection。类CSimplexTable的全部属性和方法都是程序集内公开，只能由静态类CLinearProgramming调用。CLinearProgramming接受传入的参数后进行标准化处理，调用CSimplexTable的方法完成初始单始形表的构造和迭代处理，再将取得的结果进行转换并返回，实现线性规划问题的求解。算法的使用：在需要使用算法包项目中添加对LinearProgramming.dll程序的引用，在源码中加入对命名空间NSLine

9、arProgramming的引用：usingNSLinearProgramming;调用CLinearProgramming.SetData(.)传入数据，调用CLinearProgramming.GetResult(.)取得结果。示例：对于线性规划问题目标函数为minz=-3x+x+x123x-2x+xW11123-4x+x+2x三3123-2x+x=113x,x,12x三03约束条件为使用算法包求解的代码如下：doubledaTarget=newdouble-3,1,1;/目标函数的系数EnumTargetenumTartet二EnumTarget.min;/目标函数的类型(见注1)dou

10、ble,dmConstraints=newdouble,/约束条件(约束式左边的值)1,-2,1,-4,1,2,-2,0,1,;EnumOperatorenumOpS=newEnumOperator/约束式的运算符(见注2)EnumOperator.less_than_or_equal,EnumOperator.more_than_or_equal,EnumOperator.equal;doubledaResources=newdouble11,3,1;/资源量(约束式右边的值)CLinearProgramming.NeedPreCheckData=false;/是否需要对数据的长度之间是否匹

11、配进行检查，如果可以保证数据长度之间匹配，则可设为false，以减少处理时间，默认情况下CLinearProgramming.NeedPreCheckData=true，即会进行匹配检查/调用SetData()静态方法传入数据CLinearProgramming.SetData(daTarget,enumTartet,dmConstraints,enumOpS,daResources);doublel_daDecisionVariable;/决策变量的结果，顺序存放目标最优时的变量值doublel_dOptimize;/目标值/调用GetResult()静态方法，获取结果EnumResultr

12、es=CLinearProgramming.GetResult(outl_daDecisionVariable,outl_dOptimize);if(res=EnumResult.HaveResult)/检查是否有解(见注3)stringstrResult=最优解为+l_dOptimize.ToString()+rn;for(inti=0;il_daDecisionVariable.Length;i+)strResult+=x+(i+1).ToString()+:+l_daDecisionVariablei.ToString()+rn;MessageBox.Show(strResult,线性规

13、划结果);注1：目标函数的类型包括求最小值和求最大值两种，求最小值用EnumTarget.min表示，求最大值用EnumTarget.max；注2:约束式的运算符有W、2、=三种，分别用EnumOperator.less_than_or_equal、EnumOperator.more_than_or_equal、EnumOperator.equal表示；注3：结果的类型包括3种：有解(包括只有一个解和有多个解的情况)；问题无界；异常出错，无法继续求解。分别用EnumResult.HaveResult,EnumResult.NoBound,EnumResult.Exception表示；注4:上面的这个例子是决策变量全为20的情况(xl,x2,x320),当决策变量有W0或无约束的情况时，需要使用CLinearProgramming.SetData()的六个参数的重载版本，线性规划决策变量的约束条件做为一个参数传入，例如x20,xWO,x无约束时：123EnumVariableConstraintsenumVariableConstraints=newEnumVariableConstraints3;enumVariableConstraints0=EnumVariableConstraints.more_than_or_e