《自-数学建模竞赛中优化问题与规划模型》由会员分享，可在线阅读，更多相关《自-数学建模竞赛中优化问题与规划模型（6页珍藏版）》请在金锄头文库上搜索。
1、3.6 优化问题与规划模型 与最大、最小、最长、最短等等有关的问题都是优化问题。 解决优化问题形成管理科学的数学方法:运筹学。 运筹学主要分支: （非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。61 线性规划 139年苏联数学家康托洛维奇发表生产组织与计划中的数学问题 147年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.1 问题例1 作物种植安排 一个农场有50亩土地， 0个劳动力， 计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力 1/2 1/3 /4, 预计每亩产值分别为 10元,元，60元 如何规划经营使经济效益最大. 分析：以取得
2、最高的产值的方式达到收益最大的目标1. 求什么？分别安排多少亩地种蔬菜、棉花、水稻？ x 亩、 x2 亩、 x3 亩 .优化什么？产值最大 max f=10x1+75x20x33.限制条件？ 田地总量 x+x2+3 50 劳力总数 1/x+/3x21/4x3 20模型 I : 设决策变量：种植蔬菜 亩, 棉花 x2 亩,水稻 x 亩,求目标函数101+75xx3在约束条件x+x+x3 50 1/2x1+1/x2+1/4x3 下的最大值规划问题：求目标函数在约束条件下的最值,规划问题包含3个组成要素：决策变量、目标函数、约束条件。当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题,
3、否则称为非线性规划问题。. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域,称使目标函数达最值的可行解为最优解.命题 1 线性规划问题的可行解集是凸集.因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。命题2线性规划问题的最优解一定在可行解集的某个极点上达到.图解法： 解两个变量的线性规划问题,在平面上画出可行域，计算目标函数在各极点处的值,经比较后,取最值点为最优解。命题3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线，目标值的大小描述了直线离原点的远近。于是穿过可行域的目标直线组中最远离(或接近)原点
4、的直线所穿过的凸多边形的顶点即为取的极值的极点最优解。单纯形法: 通过确定约束方程组的基本解，并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x1,2,xn. 目标函数： Z=cx1+c2x2+nx 约束条件: 11x1+1nxnb1, am11+mxbm,模型的标准化10. 引入松弛变量将不等式约束变为等式约束若有ai1x+ainxnbi,则引入 n+i 0， 使得aix1+ainx+ n =bi 若有 a1x1+jnx， 则引入 xn+j 0, 使得 a1x1+ajnxn x+ =bj 且有Zc1xc2x2+cnxn+0+1+0xn+m. 20. 将目标函数
5、的优化变为目标函数的极大化. 若求 mn Z, 令 Z=Z, 则问题变为 mx .30. 引入人工变量,使得所有变量均为非负. 若 xi 没有非负的条件,则引入 xi 0 和 xi, 令 xi= i xi, 则可使得问题的全部变量均非负 标准化模型 求变量 x1, x2, ，max Z = c+cnx, s. t a1x1+a1nxn b, m1x1+amnxn= bm, x1 0,， xn , 定义： 若代数方程=B的解向量有n-m个分量为零， 其余m个分量对应A的m个线性无关列，则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可
6、行解命题 一个向量 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法,改进单纯形方法等。按这些计算方法编制程序，产生了专门解优化问题的软件 Lindo、Lingo 。 用atlab求解:标准的线性规划的模型: min f=cxs.t. Ax b A1b1 LB BMatab求解程序:x,lipo(,A，b,A,b1,LB,UB)还有软件xe 也可应用于解优化问题。 对偶问题例1 作物种植安排 一个农场有50亩土地, 20个劳动力， 计划种蔬菜,棉花和水稻 种植这三种农作物每亩
7、地分别需要劳动力 2 /3/， 预计每亩产值分别为10元, 75元, 0元 如何规划经营使经济效益最大. 分析:以最经济的投入达到收益最大的目标(或者说以直接出售土地和劳动力的方式达到收益最大的目标.)1求什么?土地成本价格 y 劳动力成本价格 y2优化什么? 成本价格最低 Min g0y20y 3. 限制条件?蔬菜的市场价 y1+1/22 10棉花的市场价 1+1/3 5水稻的市场价 y+1/y 60模型 I 设决策变量: 对单位土地和对单位劳力投入成本价格分别为 y1 y2求目标函数 =5y120y在约束条件y+12y2 11 y1+1/3y 75 y11/4y2 60下的最小值.设A 是
8、m n 矩阵，c 是 n 1向量， 是m 1向量x是 n1向量, y是1 m 向量问题: max fcx .A i0， i=，,对偶问题: mi f= t yA c i，i=1,2,.对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解,则另一个也有有穷的最优解, 且最优值相等若两者之一有无界的最优解， 则另一个没有可行解模型 I I构成对偶问题.模型 I 解得最优解(ptmun olution) pt=(30 0 2), 最大值 (xopt)=4500模型 I 解得最优解yopt=（0 200), 最小值 (op)=500.模型I给出了生产中的资源最优分配方案模型 给出了生产中
9、资源的最低估价. 进一步问:如果增加对土地和劳动力的投入，每种资源的单位投入增加会带来多少产值?由最优解y=(1,20）可见, 多耕一亩地增加10元收入,多一个劳动力增加20元收入。也就是说， 此时一个劳动力的估价为200元,而一亩土地估价为元.这种价格涉及到资源的有效利用,它不是市场价格， 而是根据资源在生产中做出的贡献确定的估价, 被称为“影子价格”. 再进一步问,棉花价格提高到多少才值的生产?由 +1/21000/3=6.675, （而其它两个约束条件是等式）可见，只有当棉花价格提高到76.6元时才值得生产灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时， 最
10、优解是否会随之变化?通常假定变化的常数是某参数的线性函数讨论参数取值与最优解的关系的问题, 被称为参数线性规划例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规划书籍将实际问题归结为线性规划模型是一个探索创造的过程。线性规划模型的求解仍是计算数学的一个难题。例 供货问题一家公司生产某种商品. 现有 个客户, 第 j 个客户需要货物量至少为 bj, 可在 各不同地点设厂供货. 在地区 设厂的费用为 di ,供货能力为i , 向第j个客户供应单位数量的货物费用为cij如何设厂与供货使总费用最小模型:设决策变量： xij 为在地区 i 向第j 个客户供货数量， 在地区i 设
11、厂,记 yi , 否则 记yi =0 求 目标函数 f= (j cix + yidi )在约束条件 iij = bj, j xij h 0, xj0, i 0，1 下的最小值例3 钢材截短 有一批钢材, 每根长7米 现需做100套短钢材.每套包括长2.9米，2.1米，15米的各一根 至少用掉多少根钢材才能满足需要, 并使得用料最省.分析: 可能的截法和余料第1种 7.3（2. +.5)=0第2种 .3-（2.9+1）=0.第3种 7.3-(2.9+1. )=.第4种 7.3（2.9+211.5)=0.8第种73(2.1 2+. )=0.1第6种 7.3-(2.1 )第7种 7.3（2.11.5
12、 )=0.7第8种 73(1 )=1.模型：设决策变量：按第i种方法截 x 根钢材。求目标函数f.2x+1.4+0.8+0.1x5+0.7x7+.3x8在约束条件2+x2x3+x40 2x2+4+x5+3x6+7=100 x1+2x+x+2x5x4x8100 xi , i=1,8 下的最小值用Mala程序解得 xop=(4, 20, , , 0, 0， ， 0) , f (xot）= 7 (实际上应要求i 为正整数。这是一个整数规划问题）。6 整数规划如果要求决策变量取整数, 或部分取整数的线性规划问题， 称为整数规划.例 . 飞船装载问题 设有种不同类型的科学仪器希望装在登月飞船上, 令cj0表示每件第 j 类仪器的科学价值; a0表示每件第 j类仪器的重量. 每类仪器件数不限, 但装载件数只能是整数 飞船总载荷不得超过数 b 设计一种方案, 使得被装载仪器的科学价值之和最大.建模 记 x 为第 j 类仪器的装载数. 求 目标函数 f=j j xj在约束条件jaj xjb， xj为正整数， 下的最大值.用分枝定界法求解整数规划问题基本思想:反复划分可行域并确定最优值的界限,将原问题不断地分枝为若干个子问题, 且缩小最优质的取值范围,直到求得最优解. 例：求目标函数f=3x1+2x
