运筹学线性规划与非线性规划线性规划与非线性规划是运筹学的.docVIP

运筹学 ——线性规划与非线性规划 线性规划与非线性规划是运筹学的一个分支. 运筹学研究什么呢?运筹学是研究“如何做出正确决策或选择，以达到最好结果”的一门数学学科. 有一句成语形象地说明了运筹学的特点：运筹帷幄，决胜千里. 数学因实际的需要而产生，数学的很多重大发现也因实际的需要而出现. 数学建模竞赛既因实际的重要需要而在世界范围内(在我国近十几年)各大学蓬勃开展.没有受到条条框框制约、富有聪明才智的大学生们，在每次竞赛中都能对实际中的一些重要问题与难题给出富有新鲜创意的解决办法，往往因此产生重大的社会效益和经济效益.建模竞赛就是知识的“强行军”.竞赛会极大地激发学生们的创造性思维，是对学生们思考能力和动手能力的考验.竞赛能让学生们切身感受到学习各科知识的必要性、重要性，成为学生们认真学习的推动力. 数学建模会涉及数学的众多学科：微分方程，运筹学，概率统计，图论，层次分析，变分法……，要求建模者有较高的数学素养，有综合应用已学到的数学方法和思维对问题进行分析、抽象及简化的能力. 数学建模既是建立实际问题的数学模型. 一、最优化模型 数学建模的目的是使决策人的“利益”最大化，因此而建立的数学模型即所谓的最优化模型. 决策人在作决策时要有“科学观”，为实现目标(“利益”最大化)应进行“科学决策”.最优化模型正是为实现科学决策而建立的数学模型，是科学决策的科学体现. 科学决策的目的是要对为实现目标而提出的设计和操作最佳化，最终实现决策人的“利益”最大化. 一个最优化模型包括决策变量、目标函数和约束条件，它将“说明”决策变量在满足约束条件的前提下应使目标函数值最优化(最大或最小). 决策变量是指影响并决定目标实现的变量，其变化范围一般是可控制的. 目标函数是指根据决策变量建立的目标的函数表达式. 约束条件是指决策变量所受的限制(用等式、不等式的函数方程表示). 人们建立最优化模型的目的是，希望通过科学的计算方法(称为最优化方法)找出使目标函数值最优(最大或最小)的决策变量的值(称为最优决策). 实际问题的7步建模过程： 第1步：表述问题.说明目标及各种因素. 第2步：分析数据或采集(或收集)并分析数据. 第3步：建立数学模型. 第4步：对模型求解.即寻找最优决策. 第5步：检验、评价模型.如果与实际情况(或实际数据)吻合，则转到第7步，否则转到第6步. 第6步：修改或矫正模型，并返回到第1步、第2步或第3步. 第7步：模型应用，提出合理化建议. 最优化数学模型的一般形式为 (1.1) 其中， 是决策变量； 是目标函数； 和是约束条件，前者称为等式约束，后者称为不等式约束. 不带约束条件的(1)式是无约束问题的模型. 由满足所有约束条件的决策向量组成的集合称为可行域，通常记为. 求解(1)是指，寻找使为目标函数f在可行域上的最小值(或最大值).称为最优解，称为最优值. 最优解有严格与非严格和全局与局部之分.优化模型的最优解是指全局最优解. 严格极小点 严格极小点 局部 全局 非严格极小点 非严格极小点 图1 一维函数的最优解图示 这里指出：最优化方法解出的多是优化模型的局部最优解.由于最优化方法多为迭代法，所以取不同的初始点一般会得到一个或多个局部最优解，然后再从这些局部最优解中找出“全局”最优解. 二、线性规划(LP) 线性规划在银行、教育、林业、石油、运输……等各种行业以及科学的各个领域中有着广泛的应用. 1. 线性规划模型 目标函数、约束函数均为线性函数的最优化模型既是所谓的线性规划模型. (1)标准形式 (2.1) 这里， 约束是对决策变量的主要约束，称为主约束，而约束(称为非负变量)是对决策变量的符号约束； 是主约束的右端常数项(通常不妨设为非负数)；称为价值系数. (2.1)式可以写成如下矩阵形式 (2.2) 其中， . ——决策向量，——主约束右端常数向量，——价值向量. (2)一般形式 (2.3) 这里， 约束、和是主约束，而约束和任意是符号约束，其中称为自由变量. 一般形式可以(通过如下办法)转化为标准形式. (i)将不等式约束转化为等式约束 引入剩余变量，将不等式约束改写为 ，. (2.4) 引入松弛变量，将不等式约束改写为 ，. (2.5) (ii)去除自由变量 去掉自由变量有两种办法： ①用非负变量的差表示自由变量 设 ， (2.6) 其中，，代入到目标函数和其它约束中便可去掉. ②取一个包