线性规划的实际应用.doc

密 封 线

线性规划的实际应用

摘要 线性规划模型是科学与工程领域广泛应用的数学模型。本文应用线性规划模型，以某水库输水管的选择为研究对象，以实现输水管的选择既能保证供水，又能使造价最低为目标，根据水库的特点和实际运行情况，分析了其输水管选择过程中线性规划模型的建立方法，并分别通过单纯形法和MATLAB软件进行求解。
关键词 线性规划 模型 单纯形法 MATLAB
一、专著背景简介
《最优化方法》介绍最优化模型的理论与计算方法，其中理论包括对偶理论、非线性规划的最优性理论、非线性半定规划的最优性理论、非线性二阶锥优化的最优性理论；计算方法包括无约束优化的线搜索方法、线性规划的单纯形方法和内点方法、非线性规划的序列二次规划方法、非线性规划的增广Lagrange方法、非线性半定规划的增广Lagrange方法、非线性二阶锥优化的增广Lagrange方法以及整数规划的Lagrange松弛方法。《最优化方法》注重知识的准确性、系统性和算法论述的完整性，是学习最优化方法的一本入门书。
最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用-运输问题；以及动态规划的模型、求解、应用-资源分配问题。
二、专著的主要结构内容
《最优化方法》是一本着重实际应用又有一定理论深度的最优化方法教材，内容包括线性规划、运输问题、整数规划、目标规划、非线性规划（无约束最优化与约束最优化）、动态规划等最基本、应用最广又最有代表性的最优化方法。各章都由实例引入，对主要定理进行证明，引入相应的数学模型与算法，配有算法例题与详细步骤.章末附有习题，书末有习题解答与提示。《最优化方法》还专辟一章，列举了用新版本的MATLAB软件包及LINDO/LINGO优化软件包来计算的实例。本教材在阐述基本概念与基本理论时，力求清晰、透彻，在适当地方配置了一些思考题，以促使读者深入思考，加深对内容的理解.在文字叙述方面力求语言浅显、简易明了、深入浅出，以便于学生学习。内容概况如下：
第1章 线性规划主要内容包括： 1.1线性规划问题的基本概念；1.2单纯形法；1.3 线性规划的对偶理论；1.4 运输问题；1.5 线性目标规划；1.6 线性规划应用实例。
第2章 整数规划主要内容包括：2.1 整数规划问题的数学模型；2.2 分枝定界法；2.3 割平面法；2.4 0.1型整数规划；2.5 指派问题与匈牙利解法。
第3章 非线性规划的基本概念与基本原理主要内容包括：3.1 非线性规划的数学模型；3.2 无约束问题的最优性条件；3.3 凸函数与凸规划；3.4 解非线性规划的基本思路；3.5 一维搜索。
第4章 无约束问题的最优化方法主要内容包括：4.1 变量轮换法；4.2 最速下降法；4.3 牛顿法；4.4 共轭梯度法；4.5 变尺度法简介。
第5章 约束问题的最优化方法主要内容包括：5.1 约束极值问题的最优性条件；5.2 可行方向法；5.3 近似规划法；5.4 制约函数法；5.5 二次规划。
第6章 动态规划主要内容包括：6.1 动态规划问题实例；6.2 动态规划的基本概念；6.3 最优性定理与基本方程；6.4 动态规划的应用举例。
第7章 用优化软件计算实例主要内容包括：7.1 用MATLAB 7.0优化工具箱计算实例；7.2 用LINDO/LINGO软件计算实例。
三、重点分析与心得体会
《最优化方法》[1]这本书，着重实际应用又有一定理论深度的最优化方法教材，内容包括：线性规划[1-5]、运输问题[1-5]、整数规划[1-5]、目标规划[1-5]、非线性规划[1-5]（无约束最优化与有约束最优化），动态规划[1-5]等最基本、应用最广最有代表性的最优化方法。本人在此着重分析一下线性规划应用的相关问题。
线性规划，是自1947年丹齐格提出了求解线性规划一般放法-单纯性法以来，线性规划在理论上趋向成熟，日臻完善。线性规划辅助人们进行科学管理，是国际应用数学经济管理计算机科学界所关注的重要研究领域。线性规划主要研究有限资源的最佳分配问题，即如何对有限的资源进行最佳地调配和最有利地使用，以便于最充分发挥资源的效能来获取最佳的经济效益。
线性规划运用数学语言描述某些经济活动的过程，形成数学模型，以一定的算法对模型进行计算，为制定最优计划方案提供依据。其解决问题的关键是建立符合实际情况的数学模型，即线性规划模型。在各种经济活动中，常采用线性规划模型进行科学定量分析，安排生产组织与计划，实现人力物力资源的最优配置，获得最佳的经济效益。目前，线性规划模型被广泛应用于经济管理交通运输工农业生产等领域。
3.1线性规划的数学模型[6-9]
线性规划问题是求线性目标函数在线性约束条件下的最大值或最小值的问题。这类问题的数学表达式称为线性规划模型。线性规划模型的一般形式包括决策变量、约束条件和目标函数三部分。决策变量都是非负的，其值代表待解决问题的一个具体方案，形式如下：

约束条件都是线性等式或线性不等式，它们反映了待解决问题对资源的客观限制及对所要完成的任务的各类要求，形式如下：

其中，为第个约束条件中对应第个变量的约束条件系数，是第个约束条件的右边常数，它表示必须满足的某种要求。
目标函数是决策变量的线性函数，根据待解决问题的不同，可要求目标函数Z实现最大值或最小值，形式如下：

其中，是目标函数系数或价值系数。
3.2、线性规划模型在某地区水库调节水池中的应用[10-11]
（1）最优化问题的提出
某地区水源取自某水库，水库涵洞底标高为，水输送到调节水池距离为，调节水池最高水位(高) , 该段距离中要求输水量；另一段，从调节水池输水到某水厂的距离为，调节水池低水位标高为，水厂水池标高为，高差，要求输水量可供铺设的输水管有四种不同直径，它们的单位长度造价和水头损失列于表中。问应如何适当选择输水管进行铺设,既能保证供水，又能使造价最低。
表1　输水管道单位长度造价和水头损失
管径
单价
(元/m)
单位长度水头损失(m /1000m)
Q = 174L / s时的水头损失h /m
Q = 116L / s时的水头损失h /m
600
100
0.873
0.419
500
74
2.160
1.030
400
54
6.760
3.120
300
36
31.000
13.800
（2）线性规划模型的建立
对第一段水库到调节水池建立线性规划模型：
① 选取决策变量
根据水库的需要，选取管径为的输水营的铺设长度作为决策变量，并且决策变量分别设为。
② 确定目标函数
水库的目标是既能保证供水，又能使造价最低，目标函数如下：

③ 确定约束条件
约束条件是由水库的特点和输水管性能决定的，它反映了决策变量与水库参数之间必须遵循的关系。如果在建立模型时忽略了重要的约束条件，则求得的解不可信；但如果过于细微，约束条件数目增加，计算时间也将增加；同时由于变量多，关系复杂，比较容易给出互为矛盾的约束条件，造成模型无解。
供水保证约束：

要求输水量为时，该段总水头损失不超过：

非负约束：
得到如下线性规划模型为：

同理可得到第二段水库到调节水池建立线性规划模型：

3.3、线性规划问题的分析与求解[10-11]
（1）单纯形法求解线性规划问题
使用单纯形法求解线性规划时，首先要化问题为标准形式所谓标准形式是指下列形式：

当实际模型非标准形式时，可以通过以下变换化为标准形式：
① 当目标函数为

时，可令，而将其写成为:

求得最终解时，再求逆变换Z=-Z′即可。
② 当s•t•中存在形式的约束条件时，可引进变量：

便写原条件成为：

其中的称为松弛变量，其作用是化不等式约束为等式约束。
同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进剩余变量：

使原条件写成：

在将线性规划模型化为标准形后，便可使用单纯形法求解。所谓单纯形法，是指1947年美国数学家乔治·丹捷格发明的一种求解线性规划模型的一般性方法。
该模型的标准形式为：

得到线性规划化为标准形后，用最快的方法确定一个初始基本可行解。求中非基本变量的检验数 。若，则停止运算，（表示最优解），否则继续迭代。由确定进基，由确定出基，其中称为主元素；利用初等变换将化为1，并利用将同列中其它元素化为0，得新解，直至求得最优解为止。
现利用上述程序重新求解上例。为了方便明了，采用一种称为单纯形表的形式求解。为此，将问题的标准形式进一步表述为：求和，使满足方程组：

且要求各个非负，的值达最小。然后，将上述方程组写成如下表格形式：

CB
基
x1
x2
x3
x4
x5
Z
b
0
x3
0.873
2.16
6.76
31
1
0
10000
0
x4
1
1
1
1
0
0
1470
0
x5
(100)
70
54
36
0
0
810

+500
+350
0
0
0
-1
0

我们把这个表称作初始单纯形表，其特点是，从第三列起将约束方程组连同目标函数 一起按各变量位置写出，它把目标函数作为一个特殊的约束，实际上是各变量的检验数所在行。最左边两列则表明了目前解的基本变量及其相应的价值系数，最右边一列则给出了目前解的基本变量取值，右下角的数0给出这一解的目标值，由于,均为正数，故目前解非最优，按照上述步骤开始寻找另一个更好的解。令x1进基，然后以b列与x1所在列各正分量作比，求其最小值，得

故x5出基而主元素为6。为明确，将主元素加上括号便清楚地看到主元素所在列对应的进基，所在行对应的变量出基。

CB
基
x1
x2
x3
x4
x5
Z
b
0
x3
0
-1/3
1
0
-1/3
0
30
0
x4
0
（1/3）
0
1
-2/3
0
60
500
x1
(1)
2/3
0
0
1/6
0
135
σj
0
50/3
0
0
-250/3
-1
-67500
由这一表易见，目前解，目标值为72500。由于，故仍非最优解。令进基，重复以上步骤。经过3次迭代后我们可以得到第一段总造价最低为79325.2元。同理我可以求出第二段总造价最低为276586元。
3.4、MATLAB求解线性规划问题[12-14]
根据上一节，建立的线性规划模型，我们可以利用MATLAB编程求解。MATLAB可以高效、方便地解决线性规划问题。线性规划是合理利用、调配资源的一种应用数学的方法。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。它的研究内容可归纳为两个方面：一是系统的任务已定,如何合理筹划，精细安排，用最少的资源去实现这个任务：二是资源的数量已定,如何利用、分配，使任务完成得最多。前者是求极小，后者是求极大。线性规划是在满足企业内、外部的条件下，实现管理目标和极值问题，就是要以尽少的资源输入来实现更多的社会需要的产品的产出。现在通过专门的数学MATLAB软件，只要将模型中的目标函数系数、约束条件系数、不等关系输入计算机，就会很快算出结果。
对第一段水库调节水池的线性规划模型编程如下：

运行结果如下：

对第二段水库调节水池的线性规划模型编程如下：

运行结果如下：

四、总结
本文通过对资源分配问题的分析，建立其线性化的目标函数，并运用线性规划的经典算法单纯形法对其进行求解，经分析演算，问题得到了很好的解决。通过本文，我们认识到线性规划问题在解决社会生产中的最优化问题的重要性，单纯形方法作为解决线性规划问题经典方法，发挥着重要的作用。下面是本人通过学习以上知识所做总结。
（1）单纯形法总结
本人觉得用单纯形法解决线性规划问题需要注意以下几点：1） 目标函数极小化时解的最优性判别当所求的线性规划问题的目标函数求极小值时，只需以所有检验数σj≥0作为判别表中解是否最优的标志； 2）退化与循环一个基可行解如果存在取0的基变量，则称为是退化的基本可行解，相应的基称为退化基。3）在退化情况下，用单纯形法进行迭代时，经过若干次后又回到原来的可行基：如B1,B2,…,B1，此时目标函数值并没用改变，这样的问题称为退化带来的循环问题。4）退化解出现的原因一般是模型中存在多余的约束，使多个基可行解对应同一顶点。这样，按最小比值来确定出基变量时，有时会存在两个以上相同的最小比值，从而使下一个表的基可行解中出现一个或多个基变量等于0的退化解。当存在退化解时，就有可能出现计算循环。5）在计算表格中填写其它量的时候须细心认真，千万不能算错，否则可能就一步错步步错了。
（2）MATLAB求解总结
线性规划为硬性约束,在一定的条件下存在最优解，用MATLAB线性约束优化函数,能求出满足所有约束条件的最优解。但在求解具有相互矛盾的约束条件时会出现无解的情况。 MATLAB 编程效率和计算效率极高，逐渐成为国际性的计算标准，在各个领域得到广泛应用。使用MATLAB工具箱，只须编写很简单的几行程序代码，即可进行线性规划的优化设计，且结果可靠，计算精度高，避免了应用其他语言程序过于复杂、调试困难等缺点,提高了计算效果。
五、展望
随着人们对线性规划理论认识的加深,以及对线性规划方法的进一步了解和它在实际中应用范围的扩展,人们将会逐渐把线性规划的方法应用到越来越广泛的适用领域.特别是最近几年,人们用线性规划的方法结合模糊理论、神经网络等学科，在金融数学、数据挖掘、临床检测等方面进行了大量的研究，取得很好的效果和预计。由于现实生活中一些问题的复杂性使得人们越来越注重对它们的研究.同样在生产,生活,科技,经济,交通,教育等各个方面,都可以采用几个理论相结合的线性规划方法.
参考文献
[1]何坚勇.最优化方法[M].清华大学出版社.2007.1.
[2]陈宝林．最优化理论与算法．清华大学出版社. 2005.
[3]傅英定，成孝予，唐应辉．最优化理论与方法.国防工业出版社. 2008.
[4]中国人民大学数学教研室编线性规划.经济应用数学基础.中国人民大学出版社.1981.
[5]束金龙，闻人凯．线性规划理论与模型应用．科学出版社.2003.
[6]吕蓬，潘志主．运筹学.数学规划篇．清华大学出版社.2011.
[7](美)瓦格纳（Wagner, Harvey M.）著运筹学原理与应用．国防工业出版社.1992．
[8]康跃．运筹学．首都经济贸易大学出版社200.
[9] 运筹学教材编写组.运筹学(修订版)[M].AL京:清华大学出版社,1990.
[10]吴良刚主编.运筹学[M].长沙:湖南人民出版社,2001.3.
[11]于春田 李法朝.运筹学[M].北京:科学出版社,2006.2.
[12]曹卫华,郭正.最优化技术方法及MATLAB的实现[M].北京:化学工业出版社, 2005.
[13]王沬然.MATLAB6. 0与科学计算[M].北京:电子工业出版社, 2001.
[14]王京仁,李淑红,黄春红,等.MATLAB优化设计在饲料配方上的应用[J].粮食与饲料工业, 2005(12).
第 11 页 共12页