《优化问题与规划模型》由会员分享，可在线阅读，更多相关《优化问题与规划模型（9页珍藏版）》请在金锄头文库上搜索。
1、3.6 优化问题与规划模型 与最大、最小、最长、最短等等有关的问题都是优化问题。 优化问题分类：（非）线性规划、整数规划、0-1规划、（多）目标规划、（与时间有关的）动态规划、（系数是随机变量的）随机规划。6.0 多变量优化 一个城郊的社区计划更新消防站。原来的消防站在旧城中心。规划要将新的消防站设置得更科学合理。在前一个季度收集了消防队对火警反应时间的资料：平均要用3.2分钟派遣消防队员；消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。行车时间的资料列于表1Distance（miles）：距离（英里）Drive Time（minutes）：行车时间（分）表1 关于设备位置问题的反
2、应时间资料从消防官员处得到的从城区的不同区域打来的求救电话频率的数据列于图1。其中每一格代表一平方英里，格内的数字为每年从此区域打来的紧急求救电话的数量。1）求反应时间。消防队对离救火站r英里处打来的一个求救电话需要的反应时间估计为d分钟。2）求平均反应时间。设城区位区域0,60,6内，(x,y)是新的消防站的位置。根据求救电话频率，确定消防队对求救电话的平均反应时间z=f(x,y) 3）求新的消防站的最佳位置。即确定函数f(x,y)的极小值点。首先， 用随机搜索算法：在可行域0,60,6内简单地选取n个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用Matlab求最值
3、点程序求出精确的最小值点: 求函数fun在x0点附近的最小值点 x，f = fminsearch(fun, x0)6.1 线性规划 1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.1. 问题例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以取得最高的产值的方式达到收益最大的目标.1. 求什么？分别安排多少亩地种蔬菜、棉花
4、、水稻？ x1 亩、 x2 亩、 x3 亩 2. 优化什么？ 产值最大 max f=10x1+75x2+60x33. 限制条件？ 田地总量 x1+x2+x3 50 劳力总数 1/2x1+1/3x2+1/4x3 20模型 I : 设决策变量：种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩，求目标函数 f=110x1+75x2+60x3在约束条件x1+x2+x3 50 1/2x1+1/3x2+1/4x3 20 下的最大值规划问题：求目标函数在约束条件下的最值,规划问题包含3个组成要素: 决策变量、目标函数、约束条件。当目标函数和约束条件都是决策变量的线性函数时，称为线性规划问题, 否则称为
5、非线性规划问题。2. 线性规划问题求解方法 称满足约束条件的向量为可行解,称可行解的集合为可行域,称使目标函数达最值的可行解为最优解.命题 1 线性规划问题的可行解集是凸集.因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。命题2 线性规划问题的最优解一定在可行解集的某个极点上达到.图解法： 解两个变量的线性规划问题，在平面上画出可行域，计算目标函数在各极点处的值，经比较后，取最值点为最优解。命题3 当两个变量的线性规划问题的目标函数取不同的目标值时，构成一族平行直线,目标值的大小描述了直线离原点的远近。于是穿过可行域的目标直线组中最远离(或接近)原点的直
6、线所穿过的凸多边形的顶点即为取的极值的极点最优解。单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 正则模型: 决策变量: x1,x2,xn. 目标函数: Z=c1x1+c2x2+cnxn. 约束条件: a11x1+a1nxnb1, am1x1+amnxnbm,模型的标准化10. 引入松弛变量将不等式约束变为等式约束. 若有 ai1x1+ainxnbi, 则引入 xn+i 0, 使得 ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 则引入 xn+j 0, 使得 aj1x1+ajnxn- xn+j =bj. 且有
7、Z=c1x1+c2x2+cnxn+0xn+1+0xn+m. 20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z=Z, 则问题变为 max Z .30. 引入人工变量,使得所有变量均为非负. 若 xi 没有非负的条件,则引入 xi 0 和 xi0, 令 xi= xi xi, 则可使得问题的全部变量均非负. 标准化模型 求变量 x1, x2, xn, max Z = c1x1+ cnxn, s. t. a11x1+ a1nxn= b1, am1x1+ amnxn= bm, x1 0, xn 0, 定义: 若代数方程AX=B的解向量有n-m个分量为零, 其余m个分量对应A的m
8、个线性无关列, 则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解. 命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法，改进单纯形方法等。按这些计算方法编制程序，产生了Matlab优化工具箱和专门解优化问题的软件 Lindo、Lingo 。 用Matlab求解：标准的线性规划的模型： min f=cTxs.t. Ax b A1x=b1 LB x UBMatlab求解程序: x,f=lin
9、prog(c,A,b,A1,b1,LB,UB)还有软件Excel 也可应用于解优化问题。3 对偶问题例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大. 分析：以最经济的投入达到收益最大的目标.（或者说以直接出售土地和劳动力的方式达到收益最大的目标.）1 求什么？土地成本价格 y1 劳动力成本价格 y22. 优化什么？ 成本价格最低 Min g=50y1+20y2 3. 限制条件？蔬菜的市场价 y1+1/2y2 110
10、棉花的市场价 y1+1/3y2 75水稻的市场价 y1+1/4y2 60模型 II . 设决策变量: 对单位土地和对单位劳力投入成本价格分别为 y1 y2求目标函数 g=50y1+20y2在约束条件 y1+1/2y2 110 y1+1/3y2 75 y1+1/4y2 60 下的最小值.设 A 是m n 矩阵， c 是 n 1向量，b 是 m 1向量x是 n 1向量, y是1 m 向量问题: max f=cTx s.t. Ax b xi0, i=1,2,n.对偶问题: min f=yb s.t. yA c yi0, i=1,2,m.对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优
11、解, 则另一个也有有穷的最优解, 且最优值相等. 若两者之一有无界的最优解, 则另一个没有可行解模型 I II构成对偶问题.模型 I 解得最优解(optimun solution) Xopt=(30 0 20), 最大值 f(xopt)=4500模型 II 解得最优解 yopt=(10 200), 最小值 g(yopt)=4500.模型I 给出了生产中的资源最优分配方案模型 II 给出了生产中资源的最低估价. 进一步问：如果增加对土地和劳动力的投入，每种资源的单位投入增加会带来多少产值？由最优解 y=(10,200) 可见, 多耕一亩地增加10元收入，多一个劳动力增加200元收入。也就是说,
12、此时一个劳动力的估价为200元,而一亩土地估价为10元.这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出的贡献确定的估价, 被称为“影子价格”. 再进一步问，棉花价格提高到多少才值的生产？ 由 y1+1/3y2=10+200/3=76.675, （而其它两个约束条件是等式）可见，只有当棉花价格提高到 76.6元时才值得生产.Lingo命令Model:Max=110*x1+75*x2+60*x3;x1+x2+x3=50;1/2*x1+1/3*x2+1/4*x3=20;end输出结果Global optimal solution found at iteration: 2
13、 Objective value:最优值 4500.000 Variable Value最优解 Reduced Cost X1 30.00000 0.000000 X2 0.000000 1.666667 X3 20.00000 0.000000 Row Slack or Surplus Dual Price对偶价格 1 4500.000 1.000000 2 0.000000 10.00000 3 0.000000 200.0000结果解释reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量Row Slack or Surplus 松弛量或剩余量，土地、劳动力剩余量为零。“资源” 剩余为零的约束为紧约束（有效约束）4 灵敏度分析当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时, 最优解是否会随之变化?通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题, 被称为参数线性规划. 例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规划书籍将实际问题
