线性规划及其发展概况

线性规划及其发展概况本文初步阐述了线性规划产生的历史、社会背景,发展概述,以及线性规划在现实生活中的广泛应用及意义．以科学发展观的立场看线性规划在全球化过程中的巨大推动作用,特别是在合理配置资源方面所发挥的作用．从如何建立线性规划问题的数学模型出发,进而对线性规划有个理性的、深层次的认识．分析总结了线性规划问题中的几种基本解法的优、缺点,以及提出了新的求解线性规划问题的方法．关键词：线性规划；数学模型；解法前言线性规划是运筹学的一个基本的,也是最成熟的分支．为了解决二次世界大战中的后勤供应问题,早在20世纪30年代末期康托洛维奇和希奇柯克等在生产的组织和运输问题等方面就开始研究应用这一数学方法．10多年后Dantzing等人提出的单纯形方法给线性规划这一数学方法的成熟与发展奠定了坚实的理论基础．任何学科都是一个逐步完善的过程,线性规划也不例外,对于求解线性规划问题,也是一步一步趋于完善的．在求解线性规划问题时,各种求解方法也有其优、缺点．2线性规划问题及其数学模型在明白线性规划问题的概念之前,我们首先要明白什么是规划．通俗地讲,规划是对一种特定的活动（过程）可能产生的各种结果作出分析与评价,并从中找出那些对当事人（系统）最有利的结果,并了解应该限制（减少）哪些活动要素（单元）,加强（增加）那些活动要素（单元）,哪些资源显得剩余,哪些资源显得不足．规划的过程实质上就是为了实现某个特定目标对特定事物的发展进程进行优化分析的过程．小到一个人、一个家庭、一个课程组,大到一个企业、一个科研院所,甚至一个国家,只要是一个利益主体,要想在推进事物的过程中获得最多的利益或最优的结果就都要进行科学的运筹学的运筹和规划．比如说,在武器装备与弹药条件、作战样式一定的前提下,如何安排阵地或战法才能获得最好的攻击（防御）效果；在机器设备与原材料、生产方式一定的前提下,如何安排生产才能获得最大利润？可能获得的最大利润是多少？；在有限的精力、一定的课程设置以及学习方式不变的条件下,如何分配时间,才能获得尽可能好的学习效果、拿到更多的学分？；在土地资源和种植计划,才能获得更多的经济效益？如此等等,各行各业实际工作中遇到的类似问题,都可以用线性规划的方法来解决．线性规划是运筹学中数学规划（即最优化理论）的一个发展最早的,也是最成熟的分支．有一类实际问题需要将某些对象最大化（如利润、安全等）或最小化（如支出、风险等）,数学规划就是为这类实际问题提供数学模型的一种方法,具体地说,数学规划寻求函数在规定必须满足一定条件时的极小（或极大）值,称为“目标函数”,必须满足的条件称为“约束条件”,如果目标函数和约束条件都是线性的,就叫线性规划．即线性规划实质上是研究在一组线性约束条件下,把一个线性函数极小化或极大值的问题．下面我们来讨论一个线性规划问题的引例,由此得到线性规划的数学模型：例2.1（线性规划问题引例）某企业生产甲、乙两种产品,要用Ａ、Ｂ、Ｃ３种不同的原料．从工艺资料知道：每生产１吨甲产品需耗用３种原料分别为１,１,０单位,生产１吨乙产品,需耗用３种原料分别为１、２、１单位,每天原料供应的能力分别为６、８、３单位．又知道每生产１吨甲产品,企业利润收入为３００元,每生产１吨乙产品,企业利润收入为４００元．上述资料见表１表１ABC单位耗用（百元）甲１１０３乙１２１４供应量６８３问企业如何安排生产机划使一天的总利润最大？这样一个简单的生产计划安排问题,就属于我们所讨论为线性规划范围．为了准确地回答上述问题,我们用数学语言描述它这个过程称为建立其数学模型,简称建模．建模过程如下：①假设所求甲、乙产品每天生产的数量分别为、称为决策变量,简称变量．因为产量一般是一个非负数,所以有、≥０,称为非负约束．②假设该企业生产、的甲、乙产品后获得总利润值为Ｚ,显然．我们希望总利润Ｚ能达到最大,这个关系可以用下面的公式表达：③给出的规划问题往往讲明了一些限制条件．如本例中讲到的３种原料每天的耗用料分别不能超过每天的供应量６、８、３,这样就约束了产品的生产量、．生产、的甲、乙产品其原料约束如下：耗用量供应量A原料B原料C原料我们把上述所有数学公式归纳如下：s.t.(1)（１）式就是引例的线性规划模型．线性规划模型的一般形式及标准形式由（１）式可以看出线性规划模型是由三部分组成的：①一组决策变量．②一个线性目标函数．③一个线性约束方程．上述三点又称为线性规划问题的三要素．在（１）式中目标函数是求最大值（maximum）,而有些问题可能希望目标函数最小（minimum）,例如若目标函数表示生产费用,则希望生产费用最小,无论最大还是最小总之希望目标函数达到最优．在（１）式中约束条件的约束符号均为“”,但实际问题中有许多约束条件的约束符号是“”或“”或“＝”,因此我们一般设有n个决策变量,m个约束方程,则线性规划问题的一般表达形式为：max（或min）也可记为max(或min)s.t.线性规划问题的数学模型有许多种,我们希望能把各种不同形式的线性规划问题的数学模型化为一种统一的标准形式,这样只要对标准形式找出一种解法,就可以解决其余不同形式的规划问题了．线性规划问题的标准形式：mins.t.此标准形式可以写成矩阵的形式即：min,s.t.其中A=,b=X=b,0是n维零向量,表示.3线性规划问题的基本解法３.1图解法例３.1求解线性规划问题：s.t.解：作出可行域K的图形,如图１－１所示由于目标函数的等值线族恰与K的BC边平行,故沿正法向量的方向平推等值线时,最后与边重合．因此BC边上每一点都使目标函数取最大值．即知问题有无穷多个最优解．最优值为.由上例我们可以得出图解法的基本步骤：第一步：画出可行解域．第二步：画出等值双曲线．第三步：求最优解．注意：目标函数值的大小与“等值线”的移动关系遵照如下法则：假设目标函数为我们作该直线的法矢量以(则当“等值线”沿的正方向平行移动时,值就增加,沿着的负方向平行移动时,就递减．图解法它具有直观、简便的特点,同时它还有助于理解４个及４个以上决策变量线性规划问题的最优解的意义,而且,在当今的高中数学教学中占了相当的比重,其优化思想也作为重点去培养现代高中生的一种数学思想．但遗憾的是它一般只适合解含有三个或三个以下变量的线性规划问题,在解含有超过三个决策变量的线性规划问题,一般不能用图解法求解,而需要用代数的方法求解,常用的方法是单纯形法．3.2单纯形法单纯形法是求解线性规划问题的一般方法,原则上可适用任何线性规划问题,基本思想是：针对顶点可行解,建立一个便于检验最优性的准则,然后对可行域的有限个顶点,按照一定的法则依次加以检验,从中挑出最优解．3.2.1基B的典式的引入设为LP的一个基解,为叙述方便起见,不妨设对应基阵B=即为基变量,是非基变量．记,,N=.从而A=(B,N),相应地分划则线性规划问题可换成如下等价形式：（3.1）或写为（3.2）（3.1）或者（3.2）的表达形式称为LP对应于基B的典式．对于一般的基B,其典式若用矩阵表示,仍具（3.1）的形式．若用代数式表达,则应（3.2）稍加改变．如设基记基变量的下表集为S,记非基变量的下标集为R,即则LP对应基B的典式可写为其中上述诸称为基B的（或者说基解的）检验数,或者更清楚地说,是基B的对应于非基变量的检验数．等于目标函数的非基宾量表达式中的系数反号．对应于基变量的检验数视为零．于是全体检验数组成如下向量：＝亦即其中对应于基变量的检验数对应于非基变量的检验数亦即这一组检验数即可用来判别一个基可行解是否为最优解,因为有如下结论：3.2.2单纯形法定理3.1对于LP的一个基B,若,且则对应于B的基解便是LP的最优解．定理3.2若基可行解所对应的典式（4.3）～(4.5)中,有某个检验数,且相应地有则LP无最优解（此时目标函数在可行域上无下界）．定理3.3若基可行解所对应的典式（4.3）～(4.5)中,有某个检验数,而中至少有一个大于零,并且,则必存在另一基可行解,其对应目标函数值比小．综合定理3.1～3.3,便可得出求解线性规划问题LP的一种方法,称之为单纯形法,其基本过程是：如果已知的LP一个基可行解,首先求出LP相应于的典式,然后检查检验数是否全部为正．若是,则根据定理3.1,已为最优解；若不是,看定理3.2的条件是否成立．若成立,则LP无最优解；若不成立,则按定理3.3,构造一个新的基可行解．再对重复上述做法．如此反复进行．若LP是非退化的,根据定理3.3,每次得出的新基可行解使目标函数值严格下降,因此已出现过的基可行解不可能重复出现．又由于基可行解的个数有限,所以经有限次反复,必能得出LP的最优解（即最优基可行解）,或判断LP无最优解．当然单纯形法只能解决非退化的线性问题,关于退化的情形,则应以另一种方法求解．例3.2求解线性规划问题：解：取显见是一个基．为得出对应的典式,将第三个约束方程的（－２）倍加到第一个约束方程得用它代替第一个约束方程,然后,从第一、二方程分别解出代入目标函数表达式；或者,将第一个方程的（－１）倍和第二个方程的（－１）倍加到表达式两端,即可得出基对应的典式：显见是可行基,其对应基可行解为由对应于的检验数可知,应取为进基变量．这时即知故应取为离基变量．得新基为得出对应的典式,将对应典式中的第二个约束方程的２倍加到第一个约束方程上；将第二个方程的（－１）倍加到第三个约束方程上；将第二个方程的１倍加到的两端,即得对应的典式：对应的基可行解为由可知,应取为进基变量.由,可知,故应取为离基变量.得新基.为得出对应的典式,将对应的典式中的第三个约束方程两端同除以3；然后,用它的3倍和2倍分别加到第一个和第二个约束方程；用它的1倍加到的两端.即得对应的典式:,,,现在非基变量对应的检验数即知检验数全部非正．因此,对应的基可行解便是问题的最优解．目标函数的最小值为.单纯行法是一种即简便又有效,也适合于用计算机通用软件求解的一种通用方法．但是按上述单纯行法求解时,每次迭代单纯行表上的所有数据都参加运算．实际上,其中有些运算是不必要的,如果直接按这种方法编制程序上计算机解题,会在存储量和计算方面造成浪费．单纯形法是从某一规范型出发的,若标准形不是规范型,则不能直接用单纯形法求解．因为,对于不是规范型的标准型,我们看不出取哪组变量为基变量,可将标准型变换成规范型,也就是说,我门看不出取哪组变量为基变量,可得基可行解（因为对规范型而言,只要取单位矩阵所对应的变量为基变量,就可得一基可行解）．但经初等行变换可将标准形化为规范形,也就是人为的添加一些变量,使其标准型人为的变成规范型．这就是人工变量法．3.3人工变量法因为单纯形发要从某一规范形出发,对于不是规范型的标准型,用单纯形法求解的办法就是添加人工变量,使标准型人为的变成规范型形式．由于人工变量是人为地添加到原约束方程的虚拟变量,若人工变量不等于０,则不是原约束方程的可行解．有因为单纯形法是确定入基变量和出基变量的过程,只要人工变量由基变量逐个替换出变为非基变量,基变量中不再含有人工变量,这时就可得到不含有人工变量的基可行解．具体说来,人工变量法有两种：两阶段法和大M法．3.3.1两阶段法在通过添加人工变量后,把线性规划问题化为规范型,在求解过程中,如果人工变量不等于０,就不是原线性规划问题的可行解．因此,用单纯形法求解带有人工变量的线性规划问题,总是希望人工变量等于０．也就是说希望人工变量都变成非基变量．其步骤是：第一阶段：希望人工变量等于０,故此构造仅含有人工变量的目标函数要求实现最小化,然后用单纯形法求解其模型,若得到目标函数为０,则此时说明,所添加的人工变量都为０,原问题存在可行解,可以进行第二阶段计算,否则原问题无可行解,应停止计算．第二阶段：将第一阶段计算得到的最终表,去掉人工变量,将目标函数换回原问题的目标函数,作为第二阶段计算,继续单纯形法,直至求到最优解．3.3.2大M法大M法的思路与两阶段法基本一致,也是在添加人工变量之后用单纯形求解时希望人工变量等于０（即希望人工变量全部为非基变量）．为此需要人工变量对目标函数产生影响,一般设定人工变量在目标函数中的系数为M（对于目标为min型）或者-M（对于目标为max型）,M假定为任意大的数．大M法适用于规模较小和数字比较简单的线性规划问题．但对于规模大、数字大的线性规划问题,用它不仅运算量大,也容易出错．3.3.3对人工变量法的几点体会：１、所引入的人工变量并不是规定几个,而只需引进的个数与已存在的变量构成一个单位矩阵即可.２、在使用大M法时,目标函数若是求最大值（max）引入-M倍,求最小值（min）引入M倍．３、要求原问题的最优解,首先得把人工变量变为０．在求最大值时,非基变量全部为正数；在求最小值时,非基变量全不为负．倘使已达到所符合的要求时,但有人工变量还是某一个数时,则不存在最优解．４、当人工变量与松弛变量的比值相同时,首选人工变量做为变基．５、在确定出基变量与入基变量时,遵循勃兰特规则：１）选取检验数中下标最小的非基变量为入基变量．２）当按规则计算存在两个或两个以上最小值时,选取下标最小的基变量为出基变量．这样可避免出现计算过程的循环.3.4改进单纯形法3.4.1改进单纯形法（一）在实际生活中遇到的线性规划问题,变量与约束方程的个数往往大大超过我们书本中所接触的．解决实际问题都是用计算机来计算,所以怎样节约存储单元和减少计算时间就成了我们必须要考虑的问题．仔细分析单纯形法,就会发现在其迭代过程中,表格中的每列元素都参加了运算,其中有些运算是不必要的,如果直接按这种方法编制程序上计算机解题,会在存储和计算方面造成浪费．改进单纯形法就是针对这一问题的．对于一个写成矩阵形式的线性规划问题,已知它的一个可行基,则改进单纯形法计算步骤可归纳如下：第一步,计算出,从而得到相应的基可行解、目标函数值、检验数．第二步,验证基可行解是否为最优解．若检验数的分量皆为非负,则基可行解为最优解,而最优值为,问题得到解决,否则,继续进行下去．第三步,确定入基列向量．令,则确定为为入基列向量．并计算若所有的则此问题无最优解．若至少有一个,如将转入下一步．第四步,确定出基列向变量．令则确定为主元,令与对应的出基,继续进行下步．第五步,计算这里,而为由取代了单位方阵中后得来．第六步,判断新基可行解是否最优．再回到第二步．3.4.2改进单纯形法（二）设关于可行基的典式为s.t..其中S和R分别是对应的基变量下标集和非基变量下标集,但．检验数为实数,为实数．通过计算选择主元：计算△Z=﹒(A)若△Z,则任选使上式成立的为主元进行旋转运算；(B)若△Z=0,则选取,是使等式,成立的最小行下标,则以为主元旋转运算．其余步骤完全同单纯形方法．证明：（1）利用单纯形方法迭代一步后,目标函数改进,其中,．而利用上述方法,目标函数改进,显然,所以同任何单纯形法相比较,上述方法目标函数改进较快．（2）反证法．以和分别表示迭代的第阶段的基变量和非基变量下标集合．又假设出现了循环,不妨设为()…这个循环过程是从以为基变量和非基变量下标集的可行基开始的,经过次迭代后又回到了原来的可行基．由于在循环过程中目标函数始终没有改进,所以每次迭代△,因此主元的选取规则是按()进行的．这时与法则完全相同．因此不可能出现循环．3.5对偶单纯形法3.2节中所讲的单纯形法又称为原单纯形法．从原则上讲,它可以求任何线性规划问题．但在某些情况下,使用起来显得不大方便．我们知道任何一个线性规划问题都伴随着另一个线性规划问题,称为对偶问题．对于复杂的线性规划问题我们便从其对偶命题的最优单纯形表去寻求原问题的最优解．对偶单纯形法的基本思想是：原单纯形法是从一个正则基解迭代到另一个基解在迭代过程中始终保持可行性,使其非正则性（即对偶不可行性）逐步消失,一旦满足正则性（即对偶可行性）,便是最优解．由对偶关系的启发,考虑这样一个迭代过程：从一个基解迭代到另一个基解,在迭代过程中保持正则性,使其不可行性逐步消失,一旦满足可行性,便是最优解．对比原单纯形法与对偶单纯形法,两者都是从一个基解迭代到另一个基解,但前者是在基可行解中迭代,后者是在正则解中迭代．在每一次迭代中,原单纯形法是先确定进基变量后确定离基变量,而对偶单纯形法是先确定离基变量后确定进基变量．至于旋转变换方法,两者是相同的．因此对偶单纯形法也可通过单纯形表（或简化单纯形表）进行．确定了枢元以后,从旧表到新表的演化方法与原单纯形法完全相同．3.6改进的对偶单纯形法的思想及迭代步骤3.6.1改进对偶单纯形法（一）为引出改进对单纯形法的思想,先分析对偶单纯形法的迭代过程,取SLP的一个对偶可行基B,有如下步骤：①计算=,若0,则已得到最优解,停止计算；否则由,确定主元行和基变量．②若出基变量的的第列元素,问题无可行解,停止计算；否则计算确定进基变量为．③以为主元作转轴运算,返回（1）．如何计算,？如果把按行分块,即：=则=第r行事实上,因为只需而基变量故只需计算．当然,如果每一次迭代都必需从原始数据来构造,计算量并不少,但在每次转轴后,借助上一次迭代中的基阵之逆阵,通过简单计算获得转轴后基阵的逆阵,这样对偶单纯形法的迭代就可以继续下去,而其它无关的数据宾并不需要计算和存贮,从而减少计算存贮量,减少计算误差．现设出基,进基,在对偶单纯形迭代中,转轴前和转轴后的基阵分别为．．改进对偶单纯形法的关键在于如何由尽快产生,设为中第i个分量为1,其余分量为零的单位向量,由为单位阵,有=所以,=通过初等变换不难得到故用此公式来计算转轴后基阵的逆阵,可大大减少计算量．下面给出改进的对偶单纯形法的算法步骤．步骤0：选取SLP的一个对偶可行基B,基指标集为非基指标集,计算基阵的逆阵,一般说来,初始阵常为单位阵．步骤1：计算,若,则已得最优解,停止计算；若还存在,根据．确定基变量为出基变量,转下一步．步骤2：计算乘子,及检验数：为N的列向量,转下一步．步骤3：计算,其中为的第r个行向量,如果,则问题无可行解,停止计算,否则转下一步．步骤4：根据以下规则,选取进基变量,转下一步步骤5：换基运算,新基指标集新非基变量,按（1）,（2）计算,令=,返回步骤1．3.6.2改进对偶单纯形法（二）对于改进单纯行法（二）完全可推广到对偶单纯行法上,这就是改进对偶单纯形法（二