毕业论文(设计)：线性规划问题的解法.doc

1、 本科毕业论文（设计）模板 本科毕业论文 (设计 ) 论文题目 ： 线性规划问题的解法 学生姓名 ： 学 号 ： 1004970101 专 业 ： 数学与应用数学 班 级 ： 数学 1001 指导教师 ： 完成日期 ： 2014 年 5月 20日 线性规划问题的解法 内 容 摘 要 线性规划，是在运筹学的研究历程中涉及早、发展快、应用广的一个核心部分，它是帮助人类进行科学管理的一种数学方法 ,是研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写 LP。 为合理地利用有限的人力、物力、财力等资源作出的最优决策 、 提供科学的依据。 通常 ，线性目标函数在 对应 约束条件 下的最大

2、值 和 最小值的问题，统称为线性规划问题。 求解线性规划问题的基本方法是单纯形法 ，现已有单纯形法的标准软件，例如 MATLAB 等。利用计算机，可以解决线性规划的问题。 为了提高 求解效率 ， 线性规划的解法 又有 人工变量法 、对偶单纯形法。对于只有两个 或三个 变量的 简单的线性规划 问题，也可采用图解法求解。 本篇论文主要针对线性规划问题的一 般解法和特殊解法进行归纳、总结和改进，并简单阐述线性规划的常用模型及应用。 关键词： 线性规划 目标函数 一般解法 特殊解法 单纯形法 I The Solution to Linear Programming Problem Abstract L

3、inear programming, is a core part which involved in the earlier, rapid development,wide application in the course of operations research study. It is a kind of mathematical method that it can help people to make scientific management . It also is mathematical theory and method that research linear o

4、bjective function extremum problems under the condition of linear constraints,English abbreviation is LP. It makes the optimal decision and provides scientific basis for reasonable use of the limited manpower, material resources and financial resources,etc. Generally, the maximum and minimum value p

5、roblems about linear objective function in the corresponding conditions referred to as linear programming problem. The basic method to solve the linear programming problem is simples method. Now it has had standard software of simples method, such as MATLAB. We can take advantage of computer to solv

6、e linear programming problem . In order to improve the efficiency of solving, the solutions of linear programming also have artificial variable method, dual simplex method. It also has graphic method to solve linear programming problem which only has two variables. This thesis focused on summarize a

7、nd improvements which the general solution and special solution of linear programming problems. Simultaneously briefly discusses commonly used linear programming model and application. Key words： linear programming linear objective function general solution special solutions simples method II 目录 序 言

8、 . 1 一、 研究基础 . 1 （一）解决线性规划问题的一般思路 . 1 （二）线性规划数学模型建立的条件 . 1 （三）线性规划数学模型的建立 . 1 （四）线 性规划数学模型的特点 . 2 （五）线性规划解的有关概念及其关系 . 2 （六） LP模型的表达形式 . 2 二、 线性规划的一般解法及实例 . 3 （一 ）图解法 . 3 （二）单纯形法 . 5 （三）人工变量法 . 7 1.大 M 法 . 8 2. 两阶段法 . 10 （四）对偶单纯形法 . 12 三、 线性规划的特殊求解及实例 . 14 运输问题 表上作业法 . 14 四、 模型及其解法的应用 . 17 五、 总结 . 18

9、 参 考 文 献 . 19 1 序 言 在现实经济活动中，我们不断碰到诸如此类的问题：什么是最好的决策或者最佳的方案。例如企业在外在条件不变的情况下下，如何通过合理安排，改进生产计划，合理安排人、物和资源，使得成本最低。这些问题都可以建立一些数学模型，转化为线性规划问题，通过数学运 算得到最佳解决方法。 线性规划在工业、商业的管理中，可以用来解决以下问题：人员分配问题、生产计划问题，配料问题、动态投资问题以及运输问题等。实际上存在大量的具体问题，但一般解决的问题为以下两种： 一种是给定了一定数量的资源，研究如何合理地使用它们，才能使完成的任务量最大。 另一种是确定了一项任务以后，研究如何统筹安

10、排，能够使完成此项任务所耗费的资源量为最少。 实际上，上述两类问题本质是相同的，都是求问题的最优解（ max或 min），只是求解方向不同。 一、 研究基础 （一）解决线性规划问题的一般思路 1.对问题进行系统分析，搞清决策什么和决策目标是什么？ 2.明确影响决策目标（大小变化）的因素（人为可控制的，决策变量），确定决策变量对目标（函数）影响系数，且与目标函数是否成线性关系。 3.制约目标的条件有哪些？ 4.建立线性规划数学模型。 5.模型求解与解的调试。 6.方案实施与调整。 （二）线性规划数学模型建立的条件 1 1.优化条件：线性规划问题要达到的目标能够用线性目标函数描述，且能够用极值（

11、max或 min）来表示。 2.限定条件：满足目标需存在一些限定，这些限制能够用 决策变量的线性等式或不等式表示。 3.选择条件：存在多重选择的方案供决策者参考决定，以便找出最优方案。 （三）线性规划数学模型的建立 从实际问题中建立数学模型一般有一下三个步骤： 2 1.找到决策变量 ， 根据影响达到目的的因素； 2.确定目标函数 ，取决于 决策变量和 要 达到 的 目的之间的 函数 关系； 3.确定决策变量所要满足的约束条件 ，根据 决策变量所 受限的 条件。 （四）线性规划数学模型的特点 1.每个模型都有 一定量的 决策变量（ 1x ， 2x ， 3x ， nx ），其中 n 为决策变量个数

12、。 它 的一组 数 值表示一种 决策 方案，同时决策变量一般是非负的。 2.目标函数是决策变量的 线性函数 ，根据具体问题 可能为 最大化（ max）或最小化（ min），二者统称为最优化（ opt）。 3.约束条件也是决策变量的 线性函数 。 我们得到的数学模型的目标函数 被称 为线性函数，约束条件为线性等式或不等式时 ， 称此数学模型为线性规划模型。 （五）线性规划解的有关概念及其关系 2 1.有关概念 （ 1） 可行解：能够满足约束条件的全部解。 （ 2）最优解： 使某 线性规划 的目标函数达到最优值（最大值或最小值）的任一 可行解 。 （ 3）基本解 :在约束方程组系数矩阵中找到一个基

13、，令这个基的非基变量为零，再求 解这个 m元线性方程组就可得到唯一的解，这个解称之为线性规划的基本解。 （ 4）基本可行解：满足非负约束的基本解称为基本可行解。 2.解之间的关系 （ 1）最优解一定是可行解，但可行解不一定是最优解。 （ 2）基本解不一定是可行解，可行解也不一定是基本解。 （ 3）基本可行解一定是可行解，但可行解不一定是基本可行解。 （ 4）基本可行解一定是基本解，但基本解不一定是基本可行解。 （ 5）最优解不一定是基本解，基本解也不一定是最优解。 （六） LP 模型的表达形式 1.一般模型 决策变量： X=（ x1,x2,.xn） T . 目标函数： max(min)z=c1

14、x1+c2x2+.+cnxn . 3 约束条件：0, . . . . . .,)(. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .)(. . . . . .)(. . . . . .2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa2.简约模型 max(min)z=nj jjxc1. nj ijij mibxa1 ),.,2,1( . ),.,2,1(0 njx j

15、. 3.矩阵形式 max(min)z=CX. AXb. X0. 其中， A= ijmnmmnnaaaaaaaaaa. . . . . . . . . . . . . . .212222111211mn， X=nxxx.21. C=(c1 c2 . Cn)， b=nbbb.21. 二、 线性规划的一般解法及实例 （一）图解法 3 1.图解法原理 图解法，通过作图的形式来求解线性规划问题的方法。此方法简单、直观，一般只适用于具有两个决策变量的线性规划问题。 选择用图解法对实际线性规划问题求解，基本步骤为： （ 1）建立直角坐标系； （ 2）根据约束条件画出可行域； （ 3）划过坐标原点的目标函数线

16、； 4 （ 4）判定目标函数值的增大方向； （ 5）目标函数线向着增大方向平移，与可行域相交，有最大目标函数值的顶点，即为线性规划问题的最优解。 2.图解法实例 例 1 某场生产两种产品，下表给出 了制造产品的单位所需资源及单位产品利润。问：应如何安排生产计划才能使总利润最大？ 表 -1 产品 资源 I II 可利用资源 设备 1 2 8 材料 A 4 0 16 材料 B 0 4 12 单位利润（元） 2 3 解 决策变量：设产品 I、 II的产量分别为 x1、 x2 设利润为 z，则有目标函数： max z=2x1+3x2 . 约束条件：0,12416482212121xxxxxx约束条件及

17、目标函数在坐标系中的表现： 由图解法中的坐标图可得出： 最优解 X*=（ 2,4） T, 最优值 Z*=14. 3.图解法解的种类 由图解法原理及实例可以得出，线性规划问题的解有 4种： x2 4x116 4x212 可行域 Z=0 x1 x1+2x2 8 5 （ 1）有唯一最优解。 （ 2）有多重解。 （ 3）有无界解。 （ 4）无 可行解。 4.图解法求解总结 （ 1）图解法求解线性问题的最优解一般在可行域的顶点中寻找。 （ 2）利用图解法进行求解时只可能出现四种解。 （ 3）线性规划的可行域通常为是凸集（凸多边形）。 （ 4）解题思路是，先找出凸集的任一顶点，计算函数值，再与周围顶点的函

18、数值相比较。如果不是最大，继续比较，直至找出最优解。 （二）单纯形法 1.单纯形法原理 单纯形算法必须解决的三个问题： （ 1）如何确定初始的可行解？ （ 2）如何进行解的最优性判别？ （ 3）如何寻找 改进的可行解？ 单纯性方法的基本思路： 单纯形法的核心：变量迭代。 2.单纯形法的步骤 4 （ 1）将线性规划问题化成标准型。 （ 2）找出或构造一个 m 阶单位矩阵作为线性规划问题的初始可行基，建立初始单纯性表。 （ 3）计算各非基变量 xj 的检验数 j ,若所有 j 0，则问题已得到最优解 ，停止计算，否则转入下步。 找出一个初始可行解 是否最优 是 循环 否 转移到另一个基本可行解 （

19、找出更大的目标函数值） 最优解 结束 6 （ 4）在大于 0 的检验数中，做某个 k 所对应的系数列向量 kp 0，则此问题是无界解，停止计算，否则转入下步。 （ 5）根据 kjj 0m ax 原则，确定 kx 为换入变量（进基 变量），再按 规则计算： iklikiki abaab 0m in 确定 lx 为换出变量。建立新的单纯形表，此时及变量中 kx 取代了lx 的位置。 （ 6）以 ika 为主元素进行迭代，把 kx 所对应的列向量变为单位列向量，即 ika 变为 1，同列中其他元素为 0，然后转到第（ 3）步。 3.单纯形法实例 例 2 用一般单纯形法求解下列线性规划问题 max Z

20、 =3 1x +4 2x 0,303402212121xxxxxx 解：将问题化为标准型，加入松弛变量 3x ， 4x ，则标准型如下： max Z =3 1x +4 2x 0,3034024321421321xxxxxxxxxx建立初始单纯性表： 表 -2 基 bc 1x 2x 3x 4x b j jc 3 4 0 0 3x 0 2 1 1 0 40 4x 0 1 3 0 1 30 j (检验数 ) 3 4 0 0 检验数计算公式： j =cj-ijiac . 由公式计算得 1 =3， 2 =4 两个检验数均大于 0，故进行下一步，从一个基可行解转换到两一个目标值更大的基可行解。 由于 2 1 ,且 3 =40/1=40， 4 =30/3=10， 3 4 ，所以以 2x 作为换入变量，以 4x 作为换出变量。新的单纯形表形成，如下。 表 -3