线性规划问题的相关算法研究

曾国斌

（海口经济学院，海南海口571127）

线性规划问题的相关算法研究

曾国斌

（海口经济学院，海南海口571127）

本文主要是针对线性规划问题的相关算法进行了综述和原理的讲解，分别阐述了线性规划发展的历程和线性规划算法的主要数学模型，详细研究了线性规划的主要算法分为单纯形法和内点法的主要原理和算法，并为后续研究提供了一个借鉴方向.

线性规划；内点法；单纯形法

1 线性规划的发展历程

线性规划起源于苏联数学家L.V.Kantorovich，他与1939年在其代表性著作《Mathematical Methods in the Organization and Planning of Production》中发表了关于线性规划的思想，但是由于当时的条件限制使得这一思想并没有在数学领域产生轰动效应.[1]直到美国人G.B.Dantzig在1947年成功研究出解决线性规划问题的通用算法后，线性规划开始被人们所广泛接受.[1]实际上，线性规划问题的相关算法V.Klee和G.J.minth在1972年首次提出了单纯形法的迭代次数符合指数运算才开始研究的.

2 数学模型

线性规划可以分为以下两种模型，分别是标准型和非标准型.

2.1 标准型

线性规划的模型的标准型为：max Z=x1C1+x2C2+x3C3+

x4C4+…+xnCn，约束条件为，非负的

与决策变量相对应的价格系数设为cj，j=1,2,3,4…,n.技术系数设为aii，i=1,2,3…,m；j=1, 2,3…,n.右端项系数设为bi，i=1,2,3,4…,m.在线性规划规划模型的标准型中，约束条件是一组线性等式，利用向量和矩阵符号，线性规划的标准模型还可以表示为：目标函数maxZ=CX，约束条件.其中，C=(c1,c2,…cn)，A=，其中，X≥0是指X的各变量x1,x2,…xn≥0.而标准型线性规划模型具有的特点有：第一，目标函数是求最大值；第二，约束条件为线性方程组；第三，未知量都有非负限制.

2.2 非标准型

非标准性线性规划模型可以通过三种形式转化为标准型：

2.2.1 目标函数是求最小minZ

设minZ=c1x1+c2x2+…+cnxn，可设Z'=-Z，则很简单的将最小值问题转化为求最大值问题，即是将minZ转化为求max-Z，且maxZ'=-c1x1-c2x2-…-cnxn.

2.2.2 约束条件为不等式

如果约束条件为不等式，则可增加一个或减少一个非负变量，是约束条件变为等式，增加或减去的这个条件称为松弛变量.比如说，ai1x1+ai2x2+…+ainxn≤bi加一个非负变量xn+1，使不等式变为等式：ai1x1+ai2x2+…+ainxn+xx+1=bi,如果约束为ai1x1+ai2x2+…+ainxn≥bi，使不等式变为等式：ai1x1+ai2x2+…+ainxn-xx+1=bi.

2.2.3 模型中的某些变量没有非负限制

若某个变量xj可正可负，这是可设两个非负变量x'j和x"j，令xj=x'j-x"j，这样就可以满足标准型的要求.

3 单纯形法

单纯形法，求解线性规划问题的通用方法.它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到.顶点所对应的可行解称为基本可行解.单纯形法的计算步骤可以归纳为以下步骤[2]：

（1）找初始可行基，列出单纯形表.

（3）若存在某个σk>0(m+1≤k≤n)，且其对应的pk≤0，

则计算方可停止，此问题无界.否则必须进行步骤（4）

（5）换基迭代.以alk为主元素，用高斯消去法把xk所对应的系数列向量，将原表中的XB列中的xl换成xk，可以得到一张新的计算表.

（6）重复步骤（2）-（5），直到计算终止.

可以看出，退化解是指基可行解里至少还存在着一个为0的分量.若按照□规则去代换变量时，若最小比值的个数不止一个，那么在下一次迭代中就会出现数值为0的基变量，此时就发生了退化现象.在此退化解上迭代，下一次换出的将是为0的基变量，而目标函数值不会发生改变.迭代续下去，循环现象便会发生，永远达不到最优解.若按最大检验数法则选取进基变景，非基变景的非负检验数中最大值不止一个，又怎么选？为了解决上述这种情况，很多前辈都进行过相关研究，Bland法则可以很好地解决这个问题. Blank法则不走入：

（1）在所有检验数大于0的非基变暈屮，若最大检验数的存在不止一个吋，选取最小下标的xk换进基变量，即k=

（2）当按照规则确定换入变量吋，若最小比值不止一个时，选取最小下标的xl作为换出变量，即

如某番茄厂2010年种植了3种番茄3，分别是：石红二号、石红三号和新番九号，两条不同规格的番茄酱生产线，番茄可种植土地为4000平方米，但是至于300平方米适合种植新番九号.同时，由于生产需要，必须要求一号生产线产量达到5万吨，二号生产线达到10万吨，如何合理规划3种番茄品种的种植面积才能使番茄酱产量在满足订单的前提下达到最大.因此建立以下模型：maxz-y1+y2.满足约束条件：

x1+x2+x3≤4000.其中，石红二号种植面积为x1，石红三号种植面积为x2，新番九号种植面积为x3，y1为一号生产线产量，y2为2号生产线产量.在加上松弛变量之后可得到此线性规划的标准形式：maxz-50.37x1+52.71x2+44.13x3，满足约束条件：

x1+x2+x3+x6-4000.利用单纯形法，经过迭代运算，最终得到的基本可行解为：

x1-200,x2-3500,x3-300,s1-0,s2--3400,s3-0,s1-29966, s5--27832,s6-0，这时z-207798，由于σj≤0，可知z-207798为最优值.

4 内点法

内点法是一种求解线性规划或非线性凸优化问题的算法.它是由John von Neumann发明的，他利用戈尔丹的线性齐次系统提出了这种新的求解线性规划的方法.后被Narendra Karmarkar于1984年推广应用到线性规划，即Karmarkar算法[4].其基本原理如下：minf(x)s.t.c(x)≥0，x∈Rn， c(x)∈Rm，与其对应的对数型惩罚函数为是原始函数f(x)的梯度，且▽ci(x)是ci的梯度.除了原始变量x，还需要引入了拉格朗日乘子λ∈Rm：∀m i=1 ci(x)λi=μ，这有时也被称为为扰动互补条件，类似于KKT条件中的互补松弛.为了找到使得惩罚函数梯度为0的(xμ,λμ)，可以得到以下这么一个关于梯度的等式：δ-ATλ=0，其中，A是限制条c(x)的雅克比矩阵，应用牛顿法可以发现，这里μ是一个小的正参数，常被称作“惩罚因子”.惩罚函数的梯度为其中，W是f (x)的黑塞矩阵，B是λ的对角矩阵.内点法的研究热点主要转向于半定优化、半定互补、非凸优化及组合优化问题上.

在Karmarkar算法上深入研究并提出了各种修正内点法方法：仿射尺度法，对数障碍函数法，路径跟踪法算法等.原仿射比例调节法是从原问题出发，用一个仿射变换代替投影变换，把坐标系从一个非负象限(不是单纯形)映射到其本身.

〔1〕曾梅清,田大钢.线性规划问题的算法综述[J].科学技术与工程,2010,10(1):152-159.

〔2〕薛静芳.线性规划的单纯形算法研究及应用[D].大连海事大学,2013.

〔3〕Vershik A.L.V.Kantorovich and linear programming.arXiv preprint arXiv:0707.0491.2007.

O221.2

A

1673-260X（2014）05-0001-02