线性规划得实际应用 摘要 线性规划模型就是科学与工程领域广泛应用得数学模型。本文应用线性规划模型,以某水库输水管得选择为研究对象,以实现输水管得选择既能保证供水,又能使造价最低为目标,根据水库得特点与实际运行情况,分析了其输水管选择过程中线性规划模型得建立方法,并分别通过单纯形法与 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] 这本书,着重实际应用又有一定理论深度得最优化方法教材,内容包括:线性规划[15] 、运输问题 [15] 、整数规划 [15] 、目标规划 [15] 、非线性规划 [15] (无约束最优化与有约束最优化),动态规划[15] 等最基本、应用最广最有代表性得最优化方法。本人在此着重分析一下线性规划应用得相关问题。

　线性规划,就是自 1947 年丹齐格提出了求解线性规划一般放法单纯性法以来,线性规划在理论上趋向成熟,日臻完善。线性规划辅助人们进行科学管理,就是国际应用数学经济管理计算机科学界所关注得重要研究领域。线性规划主要研究有限资源得最佳分配问题,即如何对有限得资源进行最佳地调配与最有利地使用,以便于最充分发挥资源得效能来获取最佳得经济效益。

　线性规划运用数学语言描述某些经济活动得过程,形成数学模型,以一定得算法对模型进行计算,为制定最优计划方案提供依据。其解决问题得关键就是建立符合实际情况得数学模型,

　即线性规划模型。在各种经济活动中,常采用线性规划模型进行科学定量分析,安排生产组织与计划,实现人力物力资源得最优配置,获得最佳得经济效益。目前,线性规划模型被广泛应用于经济管理交通运输工农业生产等领域。

　3、1 线性规划得数学模型[69]

　线性规划问题就是求线性目标函数在线性约束条件下得最大值或最小值得问题。这类问题得数学表达式称为线性规划模型。线性规划模型得一般形式包括决策变量、约束条件与目标函数三部分。决策变量都就是非负得,其值代表待解决问题得一个具体方案,形式如下:

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

　其中,为第个约束条件中对应第个变量得约束条件系数,就是第个约束条件得右边常数,它表示必须满足得某种要求。

　目标函数就是决策变量得线性函数,根据待解决问题得不同,可要求目标函数 Z 实现最大值或最小值,形式如下:

　其中,就是目标函数系数或价值系数。

　3、2、线性规划模型在某地区水库调节水池中得应用[1011] (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)线性规划模型得建立 对第一段水库到调节水池建立线性规划模型: ① 选取决策变量 根据水库得需要,选取管径为得输水营得铺设长度作为决策变量,并且决策变量分别设为。

　② 确定目标函数 水库得目标就是既能保证供水,又能使造价最低,目标函数如下:

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

　供水保证约束:

　要求输水量为时,该段总水头损失不超过: 1 2 3 40. 873

　2. 160

　 6. 706

　 31. 000 10 1000 x x x x     

　非负约束: 得到如下线性规划模型为: 1 2 3 41 2 3 41 2 3 41 2 3 4min 100

　 70

　 54

　 36. .0. 873

　2. 160

　 6. 760

　 31. 000 10 1000

　1470 ,

　,

　, 0x x x xs tx x x xx x x xx x x x          同理可得到第二段水库到调节水池建立线性规划模型:

　3、3、线性规划问题得分析与求解[1011] (1)单纯形法求解线性规划问题 使用单纯形法求解线性规划时,首先要化问题为标准形式所谓标准形式就是指下列形式:

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

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

　求得最终解时,再求逆变换 Z=Z′即可。

　② 当 s•t•中存在形式得约束条件时,可引进变量:

　便写原条件成为:

　 其中得称为松弛变量,其作用就是化不等式约束为等式约束。

　同理,若该约束不就是用“≤”号连接,而就是用“≥”连接,则可引进剩余变量:

　 使原条件写成:

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

　该模型得标准形式为:

　 1 2 3 41 2 3 4 51 2 3 41 2 3 4 5min 100

　 70

　 54

　 36. .0. 873

　2. 160

　 6. 760

　 31. 000 10 1000

　1470 ,

　,

　, , 0x x x xs tx x x x xx x x xx x x x x          

　 得到线性规划化为标准形后,用最快得方法确定一个初始基本可行解。求中非基本变量得检验数 。若,则停止运算,(表示最优解),否则继续迭代。由确定进基,由确定出基,其中称为主元素;利用初等变换将化为 1,并利用将同列中其它元素化为 0,得新解,直至求得最优解为止。

　现利用上述程序重新求解上例。为了方便明了,采用一种称为单纯形表得形式求解。为此,将问题得标准形式进一步表述为:求与,使满足方程组: 1 2 51 2 3 4 51 2 3 41 2 3 40. 873

　2. 160

　 6. 760

　 31. 000 10 1000

　1470100

　6 4 810 70

　 54

　 36 0x x x x xx x x xx xx xx xx            且要求各个非负,得值达最小。然后,将上述方程组写成如下表格形式: C B

　基 x 1

　x 2

　x 3

　x 4

　x 5

　Z b 0 x 3

　0、873 2、16 6、76 31 1 0 10000 0 x 4

　1 1 1 1 0 0 1470 0 x 5

　(100) 70 54 36 0 0 810

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

　故 x 5 出基而主元素为 6。为明确,将主元素加上括号便清楚地瞧到主元素所在列对应得进基,所在行对应得变量出基。

　C B

　基 x 1

　x 2

　x 3

　x 4

　x 5

　Z b 0 x 3

　0 1/3 1 0 1/3 0 30

　0 x 4

　0 (1/3) 0 1 2/3 0 60 500 x 1

　(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 求解线性规划问题 [1214] 根据上一节,建立得线性规划模型,我们可以利用 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)、

推荐访问:线性规划 实际应用