运筹学与最优化方法期末论文资料.pdf

《运筹学与最优化方法》课程论文院系信息与控制专业系统科学姓名蔡珍妮学号 20151221370 指导教师叶小岭二O一 15年 12月 29日 1 运筹学思想与运筹学建模 运筹学建模的一般思路运筹学建模在理论上应是属于数学建模的一部分。因此, 运筹学建模所采用的手段、途径就是数学建模中所采用的。建模时一般思路如下: (1) 直接方法; (2) 类比方法; (3) 模拟方法; (4) 数据分析法; (5) 试验分析法。 运筹学建模举例例讨论某所大学在培养、教育中考虑为其毕业生安排工作位置的问题,这是很复杂的问题。为了简便,我们做如下假设: (1) 假设工作位置有 3 类:政府部门、工矿企业和科研院所。(2) 假设每个毕业生只接受一个工作位置。(3) 假设考虑几年的情况,第 j 年),..., 2,1(nj?毕业的人数为 jN 。要考虑的问题是找出分配工作位置的比例系数 321,,???,使得在安置工作时能较好地符合各类工作位置的要求。令jjjSIG,, 分别表示第 j 年进入政府部门、工矿企业和科研院所的人数。因此应该有 jjjjNSIG???。但是按照要找出的比例系数 321,,???,实际进入 3 类不同部门的人数为 jjNG 1 ^??,jjNI 2 ^??,jjNS 3 ^??。要得到与需求相符合的较好的比例, 一种考虑办法是使所有^jjGG?,^jjII?,^jjSS?的绝对值均为最小,那么可建立下面的目标函数])()() [(),,( 2 ^2 ^21 ^321jjjj nj jjSSIIGGf???????????把jjNG 1 ^??,jjNI 2 ^??,jjNS 3 ^??代入,得])()() [(),,( 23 22 21 1321jjjj nj jjNSNINGf??????????????要让),,( 321???f 最小。由于第 j 年毕业人数是 jN ,于是应有 1 321??????,又比例系数就它们的意义来说是非负的,即 0,0,0 321??????,这些就是问题的约束函数,于是得到下列非线性规划模型])()() [(),,( min 23 22 21 1321jjjj nj jjNSNINGf??????????????0),,( 0),,( 0),,( 01),,(. 33213 23212 13211 321321????????????????????????????????g g g hts 2 基本概念和基本理论 数学规划模型的一般形式数学规划模型的一般形式为)( fSSxts xf?. )( min 凸集、凸函数和凸规划 凸集设nRS?, 如果)1,0(,, )2()1(???Sxx , 均有Sxx???)2()1()1(??, 则称 S 为凸集。 凸函数设nRS?,非空,凸集,函数 RSf?: , 如果对)1,0(,, )2()1(?????Sxx ,恒有)()1()(])1([ )2()1()2()1(xfxfxxf?????????则称 f 为S 上的凸函数。如果上式为严格不等式,则称 f 为S 上的严格凸函数。 凸规划如果问题)( fS 中, S 为凸集, f 为凸函数,则称这个规划问题)( fS 是凸规划。 3 线性规划(单纯形法) 线性规划的概念线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大(或最小)的极值问题。 线性规划的标准型 nnxcxcxcz????... max 2211 0,..., 0,0 ... ... ... 21 2211 22222 121 11212 1 11??????????????? n mn mn mm nn nnxxx bxaxaxa bxaxaxa bxaxaxa 特点:目标函数求极大;等式约束;变量非负。令),..., ,( ?,Tnxxxx),..., ,( 21?,nm ijaA ??)( ,Tmbbbb),..., ,( 21?则线性规划标准形的矩阵表达式为: 0 max ???x b Ax cxz 约定: nmb??,0 ,秩mA?。如何化标准形: ?目标函数实现极大化,即 cxz? min ,令zw??,则 cxw?? max ; ?约束条件为不等式约束条件为“?”不等式,则在约束条件的左端加上一个非负的松弛变量; 约束条件为“?”不等式,则在约束条件的左端减去一个非负的松弛变量。?若存在无约束的变量 kx ,可令''' kxxx??,其中 0'',0'?? kkxx 。 单纯形法求解第一步:加入松弛变量, 化为标准形(要求 0?b ),确定初始基 B ,建立初始单纯形表: Bc Bx b 1c 2c ...n