——————————————————————————————————————————————————
参数线性规划的算法研究
第一章 绪论
1.1参数线性规划的研究背景
1.1.1什么是线性规划
线性规划是运筹学的一个基本的，也是成熟的分支。为了解决二次世界大战中的后勤供应问题，早在20世纪30年代末期康托洛维奇和希奇柯克等在生产的组织和运输问题等方面就开始研究应用这一数学方法。10多年后Dantzig等人提出的单纯形方法给线性规划这一数学方法的成熟与发展奠定了坚实的理论基础。随着时间的推移，能用线性规划解决问题的类型在大量的增加。现在几乎所有的工业领域、商业领域、军事领域及科学技术的研究领域都在不同程度地运用这一方法。正是由于它的应用，全球每年各个领域节省了上亿万美元的资金，而各个生产部门也创造了大量的经济效益。我国在建国初期就开始应用线性规划这一数学方法。
线性规划方法是一种重要的数学方法，线性规划方法是企业进行总产量计划时常用的一种定量方法。线性规划是运筹学的一个最重要的分支，理论上最完善，实际应用得最广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源作出最佳方式地调配和最有利地使用，以便最充分地发挥资源的效能去获取最佳的经济效益。由于有成熟的计算机应用软件的支持，采用线性规划模型安排生产计划，并不是一件困难的事情。在总体计划中，用线性规划模型解决问题的思路是，在有限的生产资源和市场需求条件约束下，求利润最大的总产量计划。该方法的最大优点是可以处理多品种问题，可解决如运输问题、生产的组织与计划问题、合理下料问题、配料问题、布局问题、分派问题等。
1.1.2参数线性规划的内容
在线性规划的实际应用中，由于某种原因，有时线性规划问题的目标函数的系数c和约束条件的常数项b的数据不是固定的常数，而有所波动。例如在制订生产计划时，一个工厂生产的各种产品的价格，由于原材料的供应价格有所波动，因而也有所波动。这样，代表总利润的目标函数中的价格系数c便会随某个参数（即原材料的价格升降百分数）而改变。又例如，在同样的问题中，由于供应原材料的单位的生产发生改变，原材料的限制量产生波动时，那么约束条件右端的常数项b也将随某个参数（即原材料生
1
——————————————————————————————————————————————————
产增长的百分数）而有所改变。再比如，该工厂的工艺技术条件发生变化，那么原线性规划问题约束条件的系数矩阵的系数就随之改变。这样的一些线性规划问题，便是所谓的“参数线性规划”。对于这种线性规划，我们所关心的时在参数的可能范围内，求出问题的最优解，即可以用原来数学模型按实际出现的目标函数的系数或约束条件右端的常数项来决策最优方案【2】。
在实际的生产或经济活动中，应用线性规划方法解决实际问题时，仅仅求出最优解或最佳决策是不够的，还必须掌握参数变化对最优解或最佳决策的影响，即要做灵敏性分析。依据变化了的情况，采取相应的措施，做好相应预案，争取更好的经济利益。否则，如果事先对这方面的情况没有充分的了解和准确的估计，难免导致决策失误，造成经济上的损失。
当线性规划中的工艺系数aij、价值系数cj、资源限量bi中一个量或多个量变成确定或不确定区间里的一个参数时，这时线性规划模型就变成一个参数线性规划的模型。当对参数线性规划模型模型里的参数赋予具体的值的时候，这时又变成了线性规划模型。线性规划模型是研究参数线性规划的依据，所有的参数线性规划模型的建立于解决都是建立在线性规划模型的基础上。但现实中市场瞬息万变，变化是绝对的，工艺系数、新产品的加入、市场价格、资源需求等因素都在改变，原生产计划建立的线性规划模型也就不适用于实际生产中去了，这时候就需要建立参数线性规划模型，所以参数线性规划模型较线性规划模型在实际生产中更有实际意义。
1.2参数线性规划的研究现状
线性规划作为运筹学的一个重要分支，从解决问题的最优化设计到工业、农业、交通运输军事等许多领域都有着重要的应用。参数线性规划是线性规划的重要组陈部分之一，几乎在Dantzig的单纯形法出现后不久，就开始了对参数线性规划的研究。参数线性规划的研究源于实际问题的需要，比如运输问题中的单位货物运价的变化（对应目标函数的价值系数cj的变化）；资源利用数量的变化（对应约束条件右端的资源限量bi的变化）；生产工艺改进（对应约束条件的工艺系数aij的变化）；甚至其中两者或三者皆变，所以对参数线性规划的研究有其现实意义。所以在1954年S.加斯和T.萨迪等人在C.莱姆基提出对偶单纯形法的基础上解决了线性规划的灵敏度分析和参数规划问题。
目前，处理参数线性规划的主要方法仍然是单纯形表上作业法，或是从对偶理论出
2
——————————————————————————————————————————————————
发建立对偶单纯形表进行求解。此类方法属于对参数线性规划求解的传统方法，如当参数线性规划的决策变量和约束条件都比较多的时候，也就是所谓的规模比较大的时候，单纯形表上作业法的缺点就十分突出，处理起来非常困难，甚至求解失败，得不到最优决策。随着计算机软件功能的日渐增强，新的算法设计思想的日益活跃，给计算工作带来了更多的便利。
经过许多科学家的努力，现在参数线性规划在以单纯形表法的基础上得到许多新的算法。如当参数、约束条件、决策变量都比较多的时候，也就是大型参数线性规划模型求解时，可以用搜索法确定参数变化区间，从而确定最优决策；分块矩阵方法求解参数线性规划；利用进化策略和神经网络模型建立参数线性规划的数学模型，采用精英保留策略的方法求的最优解。但是以上各种方法都存在局限性，局部使用，没有完整的理论体系，所以参数线性规划的算法研究还有很地方需要改进和努力。
1.3参数线性规划研究的意义
线性规划应用于工业、农业、商业、行政、军事、公用事业等各个领域，从各种限制条件的组合中，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果。在实际生产、经营、管理等活动中会因各种因素的变化而导致最优决策而改变，所以一般的线性规划模型为企业管理提供了理论基础，但该线性规划下建立的数学模型不适合应用于实际生产活动中去，所以用一些不确定的参数来代表目标函数或约束条件中的不确定因子，从而引出了参数线性规划的概念。参数线性规划，在实际工作中有较广泛的应用价值，解决了参数连续变化时，最优解的变化规律，确定了最优解发生变化的各个的取值，最终解决实际工作中的各类问题。
3
——————————————————————————————————————————————————
第二章 参数线性规划的理论
2.1参数线性规划研究的常用方法
2.1.1目标函数的系数含有参数的线性规划问题
一般地，假定线性规划问题的目标函数的系数向量C变成C?C??C*，其中
***C*?(c1,c2,?cn)，??R 2-1
^这时，可行域一般不变化，故原问题的最优解还是新问题的基本可行解。但是，需要修改目标行。新检验数为?j?CBBaj?Cj??j???*j， 其中??CBaj?C^^^?1^*j*B?1*j；新目标函数值为
CBB?1b。要使原问题的最优解还是新问题的
^最优解，则要求?j?0。
?j 若??0，则?j?0等价于???*；
?j*j^ 若??0，则?j?0等价于??? 令
*j^?j。 ?*j?????j*?max?|??0???j?*'? ?B?????j??*??，?,2,?,n)?j?0(j?1??????j*?min?|??0???j?*\? 2-2 ?B?????j??*??，?,2,?,n)?j?0(j?1?'\则要使?j?0成立，便要?B。 ????B'\'\ ?B与?B分别称为B的下特征数和上特征数，而闭区间?B称为B的最优区间。 ,?B^?? 因此对于B的最优区间中的每个?所对应的解B?1b都是新问题的最优解，目标函数
*?1Bb。即对于B的最优区间中每个?所对应的最的最大值为f?f0??f0*，其中f0*?CB优解是相同的，但目标函数的最大值为?的函数【1】。
4
——————————————————————————————————————————————————
现在考察对于最优区间外的?值，最优解的变化情况。
\\ 首先，当???B（?B为一有限数）时，求解所给线性规划问题。
^?s*\ 假设j=s时，???*，则?s?0。于是当???B时，得?s?0。这时，如果单纯
?s\B形表中xs对应的列没有正数，则目标函数无上届，新问题无最优解，否则用单纯形方法进行换基迭代,从而得到一个新的最优解。
'' 其次，当???B（?B为一有限数）时，求解所给线性规划问题。
^?t*' 假设j=t时，???*，则?t?0。于是当???B时，得?t?0。同上面一样用单
?t'B纯形方法进行换基迭代，从而得到一个新的最优解，或判明此问题无最优解。
2.1.2约束条件右端的常数项含有参数的线性规划问题
假定线性规划问题的约束条件的右端常数项b变成b?b??b*，其中
**b*?(b1*,b2,?,bm),??R。这时，只需修改右端一列，便可得到新问题的单纯形表，新
^表右端一列为
b?Bb f0?CBb 2-3
检验数均不改变，故仍然有?j?0。要使原问题的最优基还是新问题的最优基，则要求
??1^?bi?bi??bi*?0 2-4
如果bi*?0，那么bi*?bi??bi*?0等价于???^bi； *bibi。 bi*如果bi*?0，那么bi*?bi??bi*?0等价于?????bi*?max?|b?0??*i?'b??令 ?B ?i??*???，bi?0(i?1,2,?,m)??bi*?min?|b?0???i\?B???bi* 2-5 ??*???，bi?0(i?1,2,?,m)5