最优化课程论文
- 格式：doc
- 大小：185.00 KB
- 文档页数：9
-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享----
最优化方法课程设计
——线性规划模型理论与发展
学院：理学院
班级：信息102班
学号：
姓名：
-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享----
1理论与发展
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.在企业的各项管理活动中,例如计划、生产、运输、技术等问题，线性规划是指从各种限制条件的组合中，选择出最为合理的计算方法，建立线性规划模型从而求得最佳结果。
解线性规划问题有很多种方法，内点法、单纯形法、对偶单纯形法等等，而具体求解则可用图解法等。
法国数学家J.- B.- J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。
1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。
1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。
1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。
1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。
50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。
1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。
1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。
2模型建立
（一）结构
线性规划的模型决定于它的定义，线性规划的定义是：求一组变量的值，在满足一组约束条件下，求得目标函数的最优解。根据这个定义，就可以确定线性规划模型的基本结构。
（1）变量。变量又叫未知数，它是实际系统的未知因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如Xl，X2，X3，Xmn等。
（2）目标函数。将实际系统的目标，用数学形式表现出来，就称为目标函数。线性规划的目标函数是求系统目标的数值，即极大值，如产值极大值、利润极大值或者极小值，如成本极小值、费用极小值、损耗极小值等等。
（3）约束条件。约束条件是指实现系统目标的限制因素。
（二）建立模型
而应用线性规划建立数学模型的三步骤：
(1) 明确问题，确定问题，列出约束条件。
(2) 收集资料，建立模型。
(3) 模型求解(最优解)，进行优化后分析。
其中，最困难的是建立模型，而建立模型的关键是明确问题、确定目标，在建立模型过程中花时间、花精力最大的是收集资料。
所建立的数学模型具有以下特点：
1、每个模型都有若干个决策变量（x1，x2，x3……，xn），其中n为决策变量个数。决策变量的一组值表示一种方案，同时决策变量一般是非负的。
2、目标函数是决策变量的线性函数，根据具体问题可以是最大化（max）或最小化（min），二者统称为最优化（opt）。 -----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- 3、约束条件也是决策变量的线性函数。
当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
（三）线性规划的数学模型的一般形式为：
目标函数 nnXcXcXcz...max(min)2211
满足约束条件：
11212111),(...bXaXaXann
22222121),(...bXaXaXann
……
mnmnmmbXaXaXa),(...2211
0,...,,21nXXX
线性规划模型的矩阵形式：
目标函数 cXzmax(min)约束条件 bAX),(
其中， ),...,,(21ncccc,TnXXXX),...,,(21，Tmbbbb),...,,(21
mnmmnnaaaaaaaaaA.....................212222111211
3实例
为了具体的了解线性规划问题，可以举一个实例，我们来看生产计划问题：
生产计划是控制生产装置运行的命令，要利用有限的资源获得最大的经济效益，就必须制定最佳生产计划。随着公司生产装置的不断增多，生产计划的制定变得越来越复杂。采用现代管理技术，建立数学模型，利用电子计算机求解，很容易得出最优生产计划。
下面举一案例说明：
某工厂计划用现有的木材、钢铁两种资源生产A、B、C三种型号的零件。A、B、C三种型号的零件单位售价分别为2万元、3万元和4万元。市场对A型零件的需要量无-----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- 限制，对B零件的最大需求量为7单位，对C零件的最大需求量是10单位。生产单位产品A、B、C两种型号零件对木材、钢铁的消耗量及可利用的木材、钢铁数量如下表所示：
表1：基本信息表
A型零件 B型零件 C型零件 资源提供限量
消耗：木材（吨） 2 1 1 12
消耗：钢铁（吨） 3 2 1 10
产品需要限量 7 10
售价（万元） 6 4 2
工厂应该如何让安排生产，才能使工厂总收入最大？
4求解
解答过程如下：
(1)决策变量
设321,,xxx分别代表A、B、C三种型号零件的生产量，f(x)为工厂总收入。
(2) 目标函数
本问题的目标是工厂收益最大值
321246)(maxxxxxf
(3)约束条件：
A型零件 B型零件 C型零件 资源提供限量
消耗：木材（吨） 2 1 1 12
消耗：钢铁（吨） 3 2 1 10
产品需要限量 7 10
售价（万元） 6 4 2
则上述问题可以用如下数学模型（线性规划模型）来表示：
321246)(maxxxxxf
122321xxx 木材资源约束
1023321xxx 钢铁资源约束 -----WORD格式--可编辑--专业资料-----
--完整版学习资料分享---- 72x 产量数量约束
103x 产量质量约束
0,,321xxx
我们可以用Excel辅助计算求解，也可用matlab，lingo等软件，这里我们用excel示例一下。
首先，建立了起电子表格模型：
再进行规划求解：
最后，保存求解结果： -----WORD格式--可编辑--专业资料-----
--完整版学习资料分享----
最终结果如下图所示：
可以还利用Excel中的“规划求解”功能可以直接到“敏感性分析”，利用该报告可以很方便地进行灵敏度分析： -----WORD格式--可编辑--专业资料-----
--完整版学习资料分享----
敏感性报告的内容由两部分组成：
（1）位于报告上部的“可变单元格”部分反映了目标函数中的系数变化对最优解产生的影响。
第一列“单元格”是指决策变量所在单元格地址。
第二列“名字”是这些决策变量的名称。
第三列“终值”是决策变量的终值，即最优解。
第四列是“递减成本”，它的绝对值表示目标函数中决策变量的系数必须改进多少，才能得到该决策变量的正数解。
第五列“目标式系数”是指目标函数中的系数。
第六列与第七列分别是“允许的增量”和“允许的减量”它们表示目标函数中的系数在允许的增量和减量范围内变化时，最优解不变。
（2）位于报告下部的“约束”部分反映了约束条件右端值变化目标值产生影响。
目标函数系数同时变动的情况：
当各个系数变动的百分比之和小于100%时，最优解不发生变化；
当各个系数变动的百分比之和等于100%时，最优解不发生变化； 当各个系数变动的百分比之和大于100%时，不能确定最优解的变化，可能改变，也可能不变。约束右端值同时变动：
当各个右端值变动的百分比之和小于100%时，影子价格有效；
当各个右端值变动的百分比之和等于100%时，影子价格有效；
