Simplex 及其在数学建模中的应用.pdf

东北师范大学 硕士学位论文 Simplex method及其在数学建模中的应用 姓名 卢洁 申请学位级别 硕士 专业 应用数学 指导教师 李佐锋 20080501 摘要 线性规划 L i n e a rp r o g r a 晌i n g 简记为L P 模型是运筹学中的一个重要分 支 其基本解法 单纯形方法则是处理运筹学模型的一种重要方法 主要用于 研究解决有限资源的最佳分配问题 即如何对有限的资源做出最佳方式的调配和 最有利的使用 以便最充分地发挥资源的效能去获取最佳经济效益 在大量阅读相关文献的基础之上 本文就单纯形法作了详尽的综述 并将这 一最优化方法运用于解决实际问题 与相关单位合作完成的两个项目中均充分 涉及到了此种方法 本文大体上分三个章节 第一章主要是对线性规划进行了概 述 具体从线性规划发展简史和线性规划问题的数学模型两方面进行了较详尽的 综述 第二章进行了单纯形法的概述 这一部分主要涉及了单纯形法解题的基本 步骤 并且从引入人工变量和不引入人工变量两方面对改进的两阶段法进行了详 细的阐述 并配有典型的例题 最后介绍了单纯形法在计算机上的实践 第三章 是用单纯形法的具体应用 解决了两个实际问题 关键词 线性规划 单纯形法 单纯形法应用 A b s t r a c t L i n e a u rp r o g r a m m i n 甙L i 鹏a u rp r o 酉锄m i n g J a n er e c o r d e da SL P m o d e li s a I li m p o r t 觚tb 姗c hi no p e r a t i o I 试r e s e a r c h 孤dt h eb a s j cm 甜1 0 d 一 S i m p l e xm e t l l o d i sa ni m p o f t a n t V a yo fd e a l i n gw i t hm o d e lo fr e s e a r c h 麟I t h o d S I ti sm a i n l yl l s e dt 0 咖d ya n ds o h e 也eb e s ta l l o c a t i o no fl i m i t c dr e s o u r c e s w I l i c hi sh o wt om a k et h e d e p l o y m e n ta n dm a k et h ea d V a n t a g e o u su s eo fi tt o 也el i m j t e dr e s o u f c e ss ot o p e 哟n nt l l er e s o u r c e s 如l l yt 0a c q u i r et h eb e s tv a l u ef o rm o n e y T h ep a p e rm a d ead e t a i l e do v e r v i e wo nt h es i m p l e xm e m o do nm eb a s i so fa 1 a r g eq u a n t i 锣o fr e l e V 锄tr e a d i n g a n dt h eo p t i m i z a 0 nm 砒0 dW i l b eu s e dt 0s o l v e 肼枷c a Ip r o b l e m s T 1 1 e 柳op r o j e c t sc o o p e r a t i n g 埘t hr e l c v a n tu 疵sa r ef u l l yr e l e V a n t t 0i t T h i sp a p e ri sm a i n l yd i V i d e di m ot h r e es e c t i o I l s C h a p t e r0 n eo m l i n e sm em a i n 1 i n e a rp r o 斟锄m i n 蜀a n di th 嬲am o r ed e 哦l e do v e r v i e wf l r o mt h es p e c i f i cl l i s t o 巧o f 也ed e V e I o p l n e n to fl i n e a rp r o g r a m m i n ga n dl i n c a r 即g r 锄m i n gm O d e l T b es e c 硼l d 幽哪淝ro u t l i n e st h es i l I l p l e xm e t l l o d T 1 1 i sp a r tj sc o n c 锄e dw i t ht h eb a s i cg t e p so f m e s i m p l e Xm e t l l o d 跚dm a k c sad c t a j l e dd e s c r i p t i o n 舶m 她i n 仃 l d u c t i o no fv 撕a b l e 鼢dt h ei n t r o d 呶i o no ft 7 0V 嘶a b l e st 0i m p r o V et h et V o s t a g em 酬 da r l d 谢廿la 帅i c a le a m p l e F i I l a l l y I ti n t r o d l l c e s t h ep r a c t i c eo ft h es i m p l e xm e 也o do na c o m p u t e r C 1 1 a p t e rT h r e es o l V e st h et w op 眦t i c a p r o b l e m su s i n gt l l es i m p l e xr n e t l I o d 0 fa p p l i c a t i o n 墨沁yw o r d s L i n e a rp r o g r a 嘲i n g S i m p l e xm e m o d A p p l i c a t i 伽 o ft h es i m p l e X m e 廿l o d I I 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经 发表或撰写过的研究成果 也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意 卜 学位论文作者签名 翌型琵日期 迎盖 丛 趁 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留 使用学位论文的规定 即 东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘 允许论 文被查阅和借阅 本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索 可以采用影印 缩印或其它复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 日期 学位论文 工作单位 通讯地址 盈4 监 逝 鱼乡u 指导教师签名 日期 电话 世趁 邮编 删 东北师范大学硕士学位论文 引言 线性规划 L i n e a rp r o g r a 咖i n g 简记为L P 模型是运筹学中的一个重要分支 其基 本解法 单纯形方法则是处理运筹学模型的一种重要方法 主要用于研究解决有限资 源的最佳分配问题 即如何对有限的资源做出最佳方式的调配和最有利的使用 以便最 充分地发挥资源的效能去获取最佳经济效益 从数学的角度来说 就是在对决策变量施 加一组线性等式 不等式以及符号的约束下 求决策变量的线性目标函数的最大化或最 小化 与其他的数学分支相比 线性规划是一个相当年轻又非常活跃的应用数学分支 自1 9 4 7 年G B D a a t z i g 提出了一般线性规划问题求解的方法一单纯形法之后 线性规 划在理论上趋向成熟 在应用日益广泛与深人 特别是在电子计算机能处理成千上万个 约束条件和决策变量的线性规划问题之后 线性规划的适用领域更加广泛了 从解决技 术问题的最优化设计到工业 农业 商业 交通运输业 军事 经济计划和管理决策等 领域都可发挥了重要作用 线性规划的广泛应用以及所涉及到的数学理论和计算方法 都引起了专业人员和学者们很大的兴趣 在大量阅读相关文献的基础之已 本文就这些闯题作了详尽的综述 并将这一最优 化方法运用于艇决实际问题 与相关单位合作完成的两个项目中均充分涉及到了上述方 法 东北师范大学硕士学位论文 第一章线性规划概述 一 线性规划发展简史 作为运筹学的一个重要分支 线性规划问题是最早研究 理论较为完整 应用极其 广泛的一门数学规划学科 1 9 3 9 年 前苏联科学家兼经济学家康托洛维奇发表了 生产 组织与计划中的数学方法 一书n 1 第一次详细的介绍了线性规划问题 1 9 4 7 年 美国 贝尔电话公司工程师G B D a n t z i g 提出了单纯形法乜3 从而使线性规划在理论上趋于成 熟 在实际应用中日益广泛与深入 G B D an t z i g 还对线性规划理论的提炼和算法改 进做出了卓越的贡献 在1 9 5 0 年到1 9 6 0 年间 线性规划理论得到了进一步的发展和 丰富 1 9 7 5 年 瑞典皇家科学院把经济科学的诺贝尔奖授予了L V K 龇1 t o r o v i c 和T C K 0 0 p m a n s 以奖励他们对资源最优分配理论的贡献 1 9 7 9 年 L G K a n c h i a n 口1 证明了S h o r J u d i n 和N e m i r o v s k i i 的 椭球法 这种方法与逐次迭代的单纯形法是根本不同 的 椭球法是在一个多项式的时间限界内找到线性规划的一个最优解 遗憾的是椭球法 在理论上优越并不能在实践应用中得以实现 上世纪8 0 年代 N K a m a r k a r 的 投影尺度法 心舶1 使线性规划出现了真正的突破 这种新算法不仅在理论上优越于单纯形法 而且也显示出对求解大规模实际问题的巨大 潜力 K a r m a r k a r 算法的不同于单纯形法 它是从可行域的内部去逼近一个最优解 这 一内点法己经成为人们近几十年的研究的焦点 1 9 8 5 年 E B a 功e s m 和R V a n d e r b e i M M e k e t o n 和B F r e e f m a n 阳3 重新提出用 原来 仿射尺度算法来解标准的线形规划问题 并给出了算法的收敛性证明 后来 A d l e r 等人提出了类似的对偶仿射尺度算法嘲用来 解对偶线性规划问题 1 9 8 7 年 M 8 7 5 6 K oj i m a 等人提出并分析了第三种算法 即原始 一对偶仿射尺度算法n 叫 近二十几年 线性规划在国内也有了较大的发展 主要是针对 单纯形法和内点法的改进以及在各个学科的交叉研究 各个领域的具体应用 1 9 9 7 年 中科院的杨德庄提出的核心算法叭1 姚侗 何淦瞳提出的直接搜索迭代算法m 万朝燕 李晓峰等人提出的利用K T 条件和K S 函数来解线性规划n 钔的方法 彭跃辉等人的原始 基线算法n 踟 高培旺 范国兵的外点单纯形算法n 们涂为员的优面算法n 利 胡铁松等人应 用神经网络求解线性规划问题的解n 引等 总之 线性规划继单纯形法提出经历了几十年的发展 理论日益趋于成熟 应用日 益广泛 特别是电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后 线性规划的适用领域更为广泛 从解决技术问题的最优设计到工业 农业 商业 交通 运输 军事 经济计划和管理决策等领域也发挥各自作用 二 线性规划问题的数学模型 2 东北师范大学硕士学位论文 凡同时满足以下三个条件的问题 就叫做线性规划问题 1 可用一些变量表示问题的待定方案 这些变量的一组定值就代表一个具体的方 案 因此 可将这些变量称为决策变量 并往往要求它们为非负的 2 存在一定的约束条件 这些约束条件都能用关于决策变量的线性等式或不等式 来表示 3 有一个期望达到的目标 它可用决策变量的线性函数 称为目标函数 来表示 根据具体问题的不同 要求目标函数实现最大化或最小化 线性规划就是研究并解决上 述向题的一种理论和方法 满足以上三个条件的数学模型称为线性规划的数学模型 简 称线性规划模型 一 线性规划的一般形式 线性规划问题的一般形式n 钆矧为 求一维向量Z 工2 x r 使得 玎 m a m i n z 勺勺 1 1 一l 或 或 0 1 2 其中 6 I c l 2 聊 一l 2 刀 为已知常数 式 1 1 称为目标函数 式 1 2 称为约束条件 特别称工 0 为非负约束条件 以上给出的是线性规划问题的一般形式 对于不同的问题而言 目标函数可以是求 极大值或求极小值 约束条件可以是线性不等组 或者线性等式组 或者两者兼有之 变量可以有非负限制 也可没有 为了研究问题的方便 人们给出了下面形式的所谓标 准形式 二 线性规划的标准形式 线性规划问题的标准形式 则为 m i n z 勺勺 越 一 嘞t 岛 名 聊 n3 7 L 1 2 以j 其中要求假设饥 0 1 1 2 朋 否则将方程两边同乘以 一1 将右端常数化为非负 3 0 川勺 rl L r 东北师范大学硕士学位论文 数 e I 用矩阵描述线性规划的标准形式为 m i n 倒 IA X b S f x o 其中 4 口1 l口1 2 口1 n 1 口0 2 口 聊 置 足 乞 x 五 屯 屯 6 6 l 6 2 屯 C q c 2 巳 称A 为约束条件的m 九维系数矩阵 简称为约束矩阵 b 为资源向量 c 为价值向量 X 为决策向量 以后 我们提到的标准线性规划问题 记为 L P 三 线性规划问题解的一般理论 对于 1 4 式所示的标准线性规划问题 L P 凡是满足该问题所有约束条件的向量 z 我们就称之为 归 的可行解 而使得z c 7 x 达到最小值的可行解 称为 乙P 的最优 解 记为x x 所对应的目标函数值称为最优值 记为z 另外 约束矩阵A 为聊 刀维矩阵 朋s 不妨设其秩为m 即视其为满秩矩阵 若B 为矩阵A 中的一个m 阶非奇异子矩阵 则称B 为 L P 的一个基 构成B 的每个列向量均称之 为基向量 而以基向量为系数的相应变量称为基变量 其他变量称为非基变量 在约束 条件A x b 的各个约束方程中 令非基变量取值为O 所得的解称为基本解 满足非负约 柬的基本解 称为基本可行解 简称基解 相应的基称为可行基 关于标准线性规划问题 L P 的解 有下面两个基本性质 1 若 L P 有可行解 则它也一定有基本可行解 2 若 L P 有最优解 则它也一定有基本可行解是最优解 由以上这两条性质 我们可以知道 若想求出 L P 的最优解 不必考虑其所有可行 解 只需考虑 L P 的满足非负约束的基解 即基本可行解 即可 一个具有m 个独立约束 方程 n 个决策变量的线性规划问题 其基本可行解的数目最多为C 个 这样 既可缩 小所考虑问题的范围 又不会漏掉要求的解 因此 以后我们求解 L P 时 只考虑其满 足非负约束的基本可行解 4 东北师范大学硕士学位论文 第二章单纯形法概述 单纯形法的基本思路就是 先找到一个初始基可行解 如果不是最优解 设法转换 到另一个基本可行解 并使目标函数值不断减小 直至找到最优解为止 一 单纯形方法基本步骤 一 单纯形法的开始 寻找初始基本可行解 要求解一个给定的线性规划问题 单纯形法是从寻找一个初始基可行解开始的 确 定初始基可行解的一般方法是根据不同形式的约束条件添加一些变量来获得初始可行 基 在此基础上利用单纯形法的逻辑来求出初始基可行解 文献妇幻中P 2 2 2 3 给出了具体 的操作方法 比较常用的初始化方法有两阶段法和大M 法硷 二 单纯形法的停止 最优性检验及解的判别 对线性规划问题的求解结果可能出现唯一最优解 无穷多最优解 无界解 即无最 优解 无可行解四种情况 为此需要建立对解的判别准则 三 单纯形法的迭代 二 向改进方向移动 所谓向改进方向移动 也就是设法从已有的基可行解转换到另一个基可行解具体做 法就是从原可行基中换一个列向量 要保证线性无关 得到一个新的可行基 为了达到 这个目的 需要确定进基变量和离基变量 让它们相应的系数列向量进行对换 得到一 个新的基可行解 即找一个迭代主元进行G a u s s 消元变换 如何确定迭代主元昵 可见文 献 捌 这样 通过确定初始基可行解 检验是否为最优解 若不是 则设法转换到另一个 基可行解 并使得目标函数值不断减小 直至出现以上四种解的情况之一为止 由于一 个给定的线性规划问题 其基可行鳃的数目总是有限的 若迭代不出现循环 则最终必 可出现以上四种解的情况之一 四 计算步骤 综上 对于一个给定的线性规划问题 单纯形法的计算步骤如下 S T E P I 找出初始可行基 确定初始基可行解 S T E P 2 检验各非基变量的检验数丑 若旯 0 1 2 力一朋 则已得 最优解 停止计算 否则 转S T E P 3 S T E P 3 若有某个五 0 对应的屯的系数中对所有 l 2 朋均有 S 东北师范大学硕士学位论文 局 曲 O 则此问题无最优解 停止计算 否则 转S T E P 4 S T E P 4 令 叫n p l 乃 盼约束条僻方程组的系数矩阵申有一个可行基 这就要根据实际 问题 灵活运用两阶段法 看下面例子 解线性规划问题 m a x S 2 屯 工3 2 工l 3 x 2 一j c 3 9 2 屯 毛 4 五 b 6 j c l 之O c 2 之0 菇3 0 引入松弛变量 将问题化为标准形式 7 y 川 Z m m 东北师范大学硕士学位论文 I m i n S 一2 工l 一工2 一工3 2 3 工2 一屯 9 2 2 2 屯一工5 4 工l 十z 3 6 乃 0 1 2 5 问题 I 没有一个现成的可行基 因此要用两阶段法解 引进下面的辅助问题 一般的问题 I 中约束条件的方程组含有3 个方程就要引入3 个人工变量 而人工 变量越多 线性规划问题中的变量就越多 计算量就越大 因此 我们根据 I 中的 具体问题尽可能少的引入人工变量y 在此问题中注意到第一个方程中松弛变量x 前 的系数为 1 且其它两个方程中不含有工 为使技术简单 只引入两个人工变量y l y 2 辅助问题为 m i nZ M 弘 I I 其中 A 1O 0 0 01 00 02 O 2 0O 1l S 2 五 屯 屯 O 2 而 3 屯一为 而 9 M 2 恐 恐一屯 4 耽 五 屯 6 O 1 2 5 X M O f 1 2 ll 3 1 21 0l 0O 1O 0 1 00 与 昱 B 只 只 最 马 B 6 C 0l 1O OO OO 辅助问题 I I 有一现成的可行基置 丑 弓 昱 B 基变量为S M 和鲍 对应于 基且的单纯形表为 瞄 譬C 即有 8 东北师范大学硕士学位论文 r 且 S y ly 2j c lx 2屯z 4工5 Z1 0OOOl22O一1 s tOlOO211O0 j c 4 9 0 00 2 3一l l O y l 4Ol0O2l0一l 儿 6OO1lO10O 检验数有正数 进行换基迭代P 得对应于新基岛 职 只 B B 的单纯形表如下 丁 2 S My 2工l工2而屯j c 5 1l o oo o 三三一言 一lZ 2 S 一91 IOOO一22一lO 9 o oo 吾一丢圭 o 工l 2 y Z 冬 DlOO 2lO l 3 o olo 一吾吾一丢 M 2 检验数仍有正数 继续换基迭代 得对应于新基岛 只 只 层 忍 的单纯形表 丁 B s 1 y Ly z x Lx z x3 x4x s 9 o 一言 o oo 詈一丢一昙 Z 2 S 一51lOO03一l l 3 o 一三 o1o 一三圭詈 X l 2 X 2 2o l 兰 一兰 9 o 三 oo 昙一三一号 y 2 2 检验数仍有正数 继续换基迭代 得对应于新基目 五 只 忍 层 的单纯形表 9 东北师范大学硕士学位论文 丁 鼠 S y Iy 2x l冀2z 3z 4工5 ZOO一1 1OO0OO S 1 ll j o j一 ooo 一号 o X l 4o 一吾吾 1oo 吾吾 X 2 1o 三一吾 o1o 吾一 j c 3 2o 三吾 oo1 一吾一三 单纯表丁 成 中检验数已全非正 所以基层为辅助问题 I I 的最优基 m i n Z O 同时基且 月 只 忍 足 的基变量无人工变量 所以B 丑 忍 忍 为问题 I 的可行 基 对应的单纯形表为 毛屯 x 3h 屯 s t 一1 1ooo 一 o 而 41oo 吾 j c 2 1o1o 吉一孝 玛2oo l 一吾一 检验数已全非正 故B 丑 B B 为问题 I 的最优基 对应最优解为 五 4 屯 1 工3 2 工5 O 目标函数最小值为S 一l1 所以原线性规划问题的最优解为而 4 工2 l x 3 2 目标函数最大值为S 一S 1 1 由上面的解题过程 我们看到对于线性规划问题约束方程组的系数矩阵中不含有m 阶单位矩阵 求初始可行基的方法 问题化为 1 以后 注意约束条件的结构 尽可能 少的引入人工变量y 方法灵活一些 可使线性规划问题中两阶段法的解题过程简单明 了 二 不引入人工变量的方法 采用两阶段法 要把原线性规划问题化为两个线性规划问题来求解 这势必会增大 1 0 东北师范大学硕士学位论文 计算量 使得计算过程繁琐 冗长 并且计算机的存储量也随之增加 我们设想 对无 现成可行基的线性规划问题可否不引入人工变量 而像用初等变换求解线性方程组那样 直接找出原问题的可行基昵 答案是肯定的 事实上 一个基可行解就是约束方程组的 一个自由变量取零时的非负特解 1 对 1 3 线性规划标准型 由文献乜钔的分析知 可直接通过对约束条件的系数 矩阵A 进行一系列初等变换 变为含有m 阶的单位阵的形式 即上述线性规划的标准形 式 1 可通过高斯消去法或称为旋转运算进一步化为下列标准形式 m a X 勺t J l l 毛 叱 l l 笛 屯 柳 1 l 口 l 竹矗 6 三 S f 以二 1 l 如 虼 为 j c 2 之O 其中6 f 2 j f 6 6 二 o 基于这一思想 在文献陉2 3 中作者在求解线性规划问题时 通过对其约束条件的系数 矩阵和增广矩阵秩的讨论 得出原问题的一个可行基 进而得出基变量 然后经过一系 列代换 最终列出单纯形表 利用常规单纯形法求出原问题的最优解 这一思想是值得 我们借鉴的 但作者的求解过程均是通过铡题来说明的 并没有给出明确的算法 且列 出单纯形表前的一系列准备工作过于零散和繁琐 文献掣对其求解过程作了进一步的改 进 所有的计算均统一在单纯形表下完成 且给出了明确的算法 2 改进的线性规划两阶段算法 通过以上的分析可将原算法改为下列的简化算法 1 建立初始迭代表格 见表1 表1 初始迭代表格 C qc 2 q J 乡 c B X B b x x2 xR 6 l 口I la 2 l 口l l 如 口1 2 6 掰口埘1 口肼2 口棚l O j 东北9 币范大学硕士学位论文 2 观察l 若嘞 O 1 Z m 1 门 且6 0 此时第Z 行为矛盾方程 原问 题无可行解 停止计算 若口f j o 1 m 1 门 且岛 0 则第Z 行乘以 一1 后转入 3 否则直接转 3 3 从第一行开始 考虑所有口目 O 1s 的项 选取其中一项口膻 以其对 应的变量靠为基变量 确定出主列为第七列 4 计算 i 幢吣 k 由此确定主行为第z 行 若有几个鱼同时达到最小 选其中下标最小的为主行 即若 口掂 汹i n 怯哗封 则选主行为第Z 行 5 以口腩为主元进行迭代 得表2 表2 表l 的迭代表 以 为主元 巧 C lc 2气C H p C BX Bb并l工2 屯 6 l 1 口l f 1 口1 2 1 O 1 c kx k 6 2 1 1 1 O 1 2 一 6 1 钟 嘶2 1 l 口l n 1 6 m 1 疗 I 疗 1 O 1 棚 脚2 H m a j 6 依次类推 对其他各行重复 2 5 步 一般重复m 次就可得到一个明显 的可行基 东北师范大学硕士学位论文 7 按照单纯形法计算出检验数 m 口 c 厂 c J 1 2 以 J l 和目标函数值z G 6 此后完全与常规单纯形法相同 通过对检验数正负的考察来判断 是否为最优解 若是 停止计算 若否 确定出进基及出基变量 进行迭代 直至结束 例 用改进的简化算法求解 m a x z 一3 工1 z 3 Ix l x 2 而 4 s j j 一2 而 工2 一z 3 1 l3 工2 屯 9 工l 戈2 x j o 解 化为标准型后列出下列迭代表格 见表3 表3 用改进单纯形法求解例题的迭代表 一3010O口 c j c B X B 6 而屯 j c 3以 屯 4lll 1 O4 l一2l一1O l f 9O31OO o 一3O100 O 心 4llllO4 l一2 1 lO l1 9O310O3 o l 一301O0 O 屯 3 3 02lll O 屯 l一2l l0 l 6 6 O4031 O j 3O l OO 0 扎 1lO 封 1l 3 332 东北师范大学硕士学位论文 12l O X 2 3Ol 9 333 一3 玉 OOOO 2l o l 0D3 1 1 3j1l 1 X 3 0l 一 2222 5 l1l 0 X 2 1O 一 2 222 3 五 0OO0 2l 9 0 0 11 222 在表3 中 所有的检验数仃 O U 1 2 3 4 5 故已得到原问题的最优解 C02 x o 丢 昙 r 最优值z 丢 Z Z 二 比较线性规划两阶段法和本文的改进算法 很容易发现后者有以下优点 1 避免了引进辅助问题造成的运算量增大 可明显提高计算效率 2 可直观地判断线性规划问题是否有可行基 若有才进行换基迭代 克服了引 进辅助问题的盲目性 3 可以简化计算程序 便于上机操作 并且与文献相比 本文的优势也是显而 易见的 它更加简单直观 易于操作 而且将求可行基 换基迭代的过程统一于一张表 下进行 解的情况一目了然 三 单纯形法在计算机上的实现 对于以上的单纯形法的基本原理及解线性规划问题的主要步骤 当变量个数n 及 约束个数m 较大时 用手算是不可能的 现在已有了不少用来求解线性规划问题的数 学软件 如L I N G o 就是一种专门用来求解数学规划的软件包 其求解线性规划的过程 是采用单纯形法 L I N G O 软件可以用来求解线性规划 整数规划和二次规划 具体求解 过程可以参照文献曙副 1 4 东北师范大学硕士学位论文 第三章单纯形法在数学建模中的应用 在农业土地结构优化研究中的应用 虎林县位于黑龙江省东部的完达山南麓 地理坐标处于北纬4 5 2 3 至4 6 3 67 东经1 3 2 1 17 至1 3 3 5 67 之间 以鸟苏里江为界与俄罗斯联邦隔水相望 占地面积 9 3 3 0 平方公里 是全国面积的千分之一 人口3 l 万 土地作为人类生存最基本的自然资源 它与人类的生息 延续密切相关 虎林县 由于土地供需日趋严重 为了合理的利用和珍惜每一寸土地 促进土地结构的优化利用 发展本县经济 保护生态环境 因此 运用线性规划对虎林县土地结构进行优化研究 并提出土地结构调整的方案 对合理利用土地和充分挖掘土地生产潜力具有重大的现实 和深远的战略意义 一 农业土地结构优化的原则 对虎林的土地结构进行优化研究时 首先应坚持因地制宣 因时制宜的原则 益 农则农 宣林则林 宜牧则牧 按照自然规律办事 充分体现该县土地利用结构的地域 差异 其次 应坚持经济效益的原则 用最小的投入 或最大的收益 充分发挥该县土 地生产优势 第三i 应坚持保护生态环境的原刚j 防止土地污染 裨益当代 造福子孙 具体调整时 要把人口增长 经济发展与土地资源的数量 质量结合起来 充分 挖掘各类土地的生产潜力 吧综合开发利用和区域整治保护结合起来 协调好人地关系 建立起不同地域不同层次的复合宏观用地结构来 二 建立农业土地结构优化的数学模型 1 模型的一般形式 本县采用的线性规划模型是 求在满足约束条件下使目标函数取得最大时的一系 列变量 其中有些变量只能取整数 因此 模型的一般形式为 埘 m a x z 勺工 I I l 或 或 0 戊 0 口 一 川 r 六 东北师范大学硕士学位论文 2 设置变量 由于虎林县地面沟壑纵横 支离破碎 相对高差大 降水少丽集中 往往产生很 大的坡面径流 造成严重的水土流失 因此 在土地利用上应坚持与生物措施相结合 治坡与治沟相结合 做到梯田 川地 滩地同步 乔木 灌木 草地齐进 根据上述要 求 设置如下变量 墨 X X 丘为各等地面积 X X 6 为森林 牧草地面积 峭 似2 麟3 分别为规划期内 二等地升一等地 靠兴修水利工程 三等 地升二等地 靠修梯田 四等地升三等地 靠改良土壤 面积 k 为四等地退林地面积 从 为退牧草地面积 城为牧草地造林面积 3 规划期内线性规划模型 2 0 1 0 年规划期模型 1 各等地土地的约束条件 在虎林县土地评价中 已知该县现有总耕地5 5 万亩 其中一等地面积1 5 3 万亩 二等地面积2 0 2 万亩 三等地面积1 1 5 万亩 四等地面积8 万亩 林地面积3 3 7 9 万亩 牧草地面积1 5 4 万亩 由此可得出下列方程式 一等地 五一战 1 5 3 二等地 丘一战 从l 2 0 2 三等地 骂一麟3 趟2 1 1 5 四等地 r 4 X 3 灭 4 x 5 8 森林地 以一从4 一舣6 3 7 9 牧草地 X 6 一似5 从6 1 5 4 2 投资约束条件 在2 0 l O 年前的规划期内 考虑到虎林县的具体情况 靠兴修各种水利设施 来增 加水地面积 新增每万亩水地需要投资6 0 万元 大搞平整土地 修建梯田 新增每万宙 梯田需投资4 5 万元 靠改良土壤 增施有机肥 新增每亩需投资2 0 万元 靠采取各种措 施 封山育林 新增每万亩森林地需要投资1 0 万元 对于改良现有牧草地 进行人工种 1 6 东北师范大学硕士学位论文 草 新增每万亩牧草地需投资2 5 万元 在自然条件优越的牧草地上进行植树造林 新 增每万亩森林需要投资l O 万元 为了能改变虎林县的旧貌 在规划期内 该县可以自筹 资金和国家支援资金大约为1 0 0 卜1 3 0 0 万元 因此 虎林县规划期内的投资约束方程 是 其中弹性指标为3 0 6 必l O 4 5 腊2 O 2 从3 0 1 城 0 2 5 从5 O 1 从6 1 0 3 劳动力约束条件 该县在规划期内扩大水地每万母需投入l5 万个工 修筑梯田每万亩需投入2 0 万个 工 改良土壤每万亩需投入5 万个工 造林每万亩需投入5 万个工 种草每万亩需投入4 万个工 根据虎林县实际情况 预计1 9 9 5 年该县农村劳动力可达1 0 4 5 万人 可提供劳 动力3 0 5 4 万个 按每年3 0 0 个天计 除牧 副业尉工外 6 年大约可提供农 林 水土 保持用工1 4 0 6 8 百万一1 5 1 3 4 百万个工 由此可以建立起农田需要投工与可能提供投工 的方程式来 弹性指标为1 0 7 8 0 1 5 战l O 2 肼2 0 0 5 从3 O 0 5 战 O 0 4 麟5 O 0 5 战 1 4 0 6 8 4 粮食需求约束条件 根据虎林县人口规划得知 该县1 9 9 5 年人口可达到2 9 万人 用该人口数字乘以全国 人均消费标准 粮食标准 就可得出虎林县1 9 9 5 年时对粮食总需求为2 0 1 5 5 2 1 6 3 4 万斤 即1 0 0 8 一1 0 8 0 万吨 在充分挖掘本县土地生产潜力的基础上 预计该县到1 9 9 5 年 一等地单产可达1 0 0 0 斤 亩 将它们换算成为万吨 万亩为单位 因此有 弹性指标 O 7 2 方程 0 5 X l O 4 X 2 0 2 7 6 X 3 O 1 7 5 X 4 1 0 1 5 电力供应约束条件 虎林县一等地中包括水浇地的用电量比较大 每万亩需用电1 8 万度 二等地需用电 8 万度 三等地需用电5 万度 四等地需用店3 万度 根据虎林县电力工业局规划 2 0 1 0 年度国家可提供5 4 卜5 7 5 百万度 因此可以获得需电与用电之间的平衡方程式 弹性 指标O 3 O 1 8 墨 O 0 8 X 2 O 0 5 匕 0 0 3 爿 5 4 5 6 各种灾年最低限量约束条件 危害本县农业生产的主要自然灾害是春旱 夏秋旱 夏涝和霜冻 它们可以使农作 物分别减产2 5 4 0 4 5 3 0 按照每年人均最低需要量2 0 0 一2 2 5 公斤计 全县2 9 万人 大约需要粮食5 8 一 6 5 2 万吨 为了保证出现自然灾害的情况下 满足该县最低需要量 从而避免出现不必要的风险 可以建立起灾年粮食生产和需求量之间的平衡方程 弹性 指标为O 7 2 5 春 旱 O 3 7 5 Z l O 3 X 2 0 2 0 6 X 3 0 1 3 1 X 4 5 8 东北师范大学硕士学位论文 夏秋旱 O 3 Z l 0 2 4 X 2 O 1 6 6 托 O 1 0 5 2 4 5 8 夏秋涝 O 2 7 5 X l O 2 2 X 2 O 1 5 2 X 3 0 0 9 6 X 4 5 8 霜 冻 O 3 5 X l O 2 8 也 O 1 9 3 2 3 O 1 2 3 2 4 5 8 7 有机肥施用约束条件 根据虎林县统计资料获知 该县耕地中一等地每万亩需施用有机肥料4 8 万吨 二 等地每万亩需施有机肥4 万吨 三等地每万亩需施有机肥3 2 万吨 四等地每万亩需施有 机肥2 4 万吨 预计2 0 1 0 年可获有机肥料2 3 2 8 吨 至少可得2 1 2 8 万吨 因此有 弹性 指标为2 O 4 8 z 一彳2 3 2 X 3 2 4 X 4 2 1 2 8 8 生态环境约束条件 根据虎林农业 林业 畜牧业发展规划可知 到2 0 1 0 年该县的森林 草地 果园及 四旁绿化等面积将不会少于5 5 万亩这一约束条件 我们可以建立起如下方程式 X 5 饩 5 5 9 目标函数 根据虎林县的自然环境条件 劳动力生产水平和机械化程度 预计到1 9 9 5 年各等林 地及牧草地每万亩净增产分别为2 7 8 万元 1 8 4 万元 1 5 8 万元 1 2 3 万元 3 l 万元和2 9 0 万元 目标函数应该是规划年内诤增产值的极大值 这个净增产值等于规划年内各等土地 净增产值扣除规划期内各项投资额的回收值 因此 可以建立起如下方程式 资本回收 取0 1 M 彪 2 7 8 五 1 8 4 五 1 5 8 墨 1 3 3 丘 3 1 墨 2 9 0 以一0 6 战一0 4 5 战 一0 2 蝎一0 1 城一O 0 2 5 战一O I 战 虎林县2 0 1 5 年规划期模型 在2 0 1 0 年规划期预测结果的基础上 综合考虑所设置各变量系数与常数项到2 0 0 0 年的变化情况 可以建立如下规划模型 一等地 五一战 1 7 0 6 二等地 五一从2 战 2 2 6 4 三等地 Z 3 一城 麟2 8 四等地 Z 4 Z 3 五 5 6 东北师范大学硕士学位论文 林 地 X 5 一 Y 4 一 X 6s 3 9 草 地 Z 6 一厶X 5 X I 1 6 投 资 O 6 X l O 4 5 Z 2 0 2 爿I O 1 丘 O 0 2 5 X 5 0 1 瓦 1 2 劳动力 O 1 5 舣l O 2 似2 O 0 5 必 O 0 5 以4 O 0 4 从5 0 0 5 麟6 6 8 3 粮食 0 5 五 O 4 五 0 2 7 6 墨 O 1 7 5 2 4 1 2 5 电 力 0 1 8 x I 0 0 8 X 2 0 0 5 托 O 0 3 扎 5 6 2 春旱 O 3 7 5 置 O 3 五 0 2 0 6 墨 O 1 3 l x 4 6 4 3 夏秋早 0 3 五 O 2 4 X 2 O 1 6 6 也 O 1 0 5 五 6 4 3 夏秋涝 0 2 7 5 X l 0 2 2 X 2 0 1 5 2 托 O 0 9 6 丘 6 4 3 霜冻 O 3 5 X l 0 2 8 五 O 1 9 3 2 3 0 1 2 3 X 4 6 4 3 有机肥料 4 8 Z 4 X 2 3 2 X 3 2 4 托 2 1 4 4 生态 五 x 6 5 6 4 0 目标函数值 拖彪 2 9 3 五 1 9 2 恐 1 6 8 墨 1 3 9 墨 4 1 五 2 9 5 五一0 6 战一0 4 5 必 一0 2 峭一O 1 战一O 0 2 5 域一0 1 战 三 计算结果和分析 利用计算机求得结果 见表 并对计算结果进行综合分析与评价 为了能充分地说明本规划期模型的可靠性及科学性 现与2 0 0 4 年对比表如下 1 9 东北师范大学硕士学位论文 由四等地退草地面积 O 70 5 本规划模型是在满足虎林县各项约束条件下来获得取提高土地生产潜力 达到最 大生态效益和经济效益 在各规划期末 该县一等地面积将分别由2 0 0 4 年的1 5 3 万亩增 至1 7 0 6 万亩和1 8 万亩 二等地面积将分别由2 0 0 4 年的1 1 5 万亩减至8 万亩和6 1 万亩 这样 三等地逐渐被一 二等地所取代 这不仅有利于充分发挥虎林县土地生产潜力 而且还可以为水土保持工作创造一个有益条件 四等地面积将分别由2 0 0 4 年的8 万亩减 至5 6 万亩和3 7 万亩 该类土地由于自然条件差 多分布于陡坡和急陡坡上 为了能珍 惜每寸土地 使得土地的效益尽可能地发挥出来 我们将此类地的一部分改造为三等地 一部分进行造林绿化 另一部分为牧草地 为发展畜牧业提供草场 森林面积将由2 0 0 4 年的3 7 9 万亩增至4 0 万亩 草地砸积将分别由2 0 0 4 年的1 5 4 万亩分别增至1 6 万亩和1 6 4 万亩 植被覆盖率将由2 0 0 4 年得3 0 6 增至3 1 8 和3 2 4 水土流失面积将会有明 显的减少 因乱垦滥伐造成的土地恶性生态循环也会逐步向良性循环过渡 农业生产也 会逐步向稳产 高产方向发展 如果这一规划方案能够附诸于实施 该县的土地资源净 增值将会从2 0 0 4 年的1 3 5 0 万元提高到2 0 1 0 年的1 6 7 6 3 0 2 万元和2 0 1 5 年的1 7 9 1 6 4 4 万元 此时 虎林县的人民将会过上丰衣足食 安居乐业的生活 农村的经济状况及农村人口 人均收入就可以达到小康水平 东北师范大学硕士学位论文 参考文献 1 L V K a n t o r o v i c k M a t h e m a t i c a l m p r o d u c t i o n P u b l ic a t i o nH o u s eo f 1 9 9 3 e t h o d so f or g a n i z i n ga n d pl a n n i n g t h eL e n i n g r a ds t a t eu n i V e r s i t y L e n n i n g r a d 2 QB d a n 七西昏乙i n e a rp r o g r a 姗 n g a 时陕t e n 考叠D n s P r i n c e t o nu n i v e r sit y p r e s s P r i n c e t o n N e w J e r e y 1 9 9 6 1 2 6 3 L G Kh a c h i a n Ap0 1 y n o m i a l a1 9 0 r i t h mi n li n e a r pr o g r a 舶功i n g So v i e t M a t h e m a t i c sD o k l a d y 1 9 7 9 2 0 1 9 l 1 9 4 4 N K a r m a r An e wp o l y n o m i a lt i m ea l g o r i t h mf o rl i n e a rp r o g r a m m i n g P r o c e e d i n g o ft h e1 6 l A n n u a lA C Ms y m p o s i u mo nt h eT h e o r yo fc o m p u t i n g 1 9 8 4 3 0 2 3 1 1 5 N K a r m a r An e wp o l y n o m i a lt i m ea l g o r i t h mf o r1 i n e a rp r o g r a m m i n g c 乎 m b i n a t o r i a l 1 9 8 4 4 3 7 3 3 9 5 6 I A d l e r N K a r m a r A ni m p l e m e n t a t i o no f k a r m a 8a l g o r i t h mf o rl i n e a r p r o g r 锄i n g M a t h e 卿越i c d 蹿Q 驻锄i n g 土9 8 钆4 4 2 9 7 3 3 5 k 7 E R B a r n e s AV a r i a t i o no fk a r m a r k sa l g o r i t h mf o rs o l v i n gl i n e a r p r o g r a 咖i n g M a t h e m a t i c a lp r o g r a m m i n g 1 9 8 6 3 6 1 7 4 1 8 2 8 R Va n d e r b e i M S M e k e t o n a n dB A F r e e d m a n Am o d i f i c a t i o no fk a r m a r k a r s l i n e a rp r o g r 锄m i n ga l g o r i t h m A 1 9 0 r i t h m i c a 1 9 8 6 l 3 9 5 4 0 7 9 I A d l e r N K a r m a r k a r M G C R e a s e n d e a n dG V ei g a A ni m p l e m e n t a t i o no f k a r m a r k a r sa l g o r i t h mf o r1i n e a rp r o g r a m m i n g M a t h e m a t i c a l p r o g r a m m i