《优化问题与规划问题》由会员分享，可在线阅读，更多相关《优化问题与规划问题（56页珍藏版）》请在金锄头文库上搜索。
1、3.6 优化问题与规划模型,综合问题,一个城郊的社区计划更新消防站。 原来的消防站在旧城中心。 规划要将新的消防站设置得更科学合理 在前一个季度收集了火警反应时间的资料：平均要用3.2分钟派遣消防队员；消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离。 行车时间的资料列于表1,表1 行车时间,从社区的不同区域打来的求救电话频率的数据列于图1。 其中每一格代表一平方英里， 格内的数字为每年从此区域打来的紧急求救电话的数量。,1）求反应时间。 消防队对离救火站r英里处打来的一个求救电话需要的反应时间估计为d分钟。 给出消防队对求救电话的反应时间的模型d(r) 2）求平均反应时间。 设社区
2、位区域0,60,6内，(x,y)是新的消防站的位置。 根据求救电话频率，确定消防队对求救电话的平均反应时间z=f(x,y),3）求新的消防站的最佳位置。 即确定函数f(x,y)的极小值点。 首先，,3.6 优化问题与规划模型,优化问题：与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法： 运筹学 运筹学主要分支：线性规划、非线性规划、动态规划、图与网络分析、存贮论、排队伦、对策论、决策论。,6.1 线性规划1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.,1. 问题 例1 家具生产的安排一. 家
3、具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米每张桌子要使用15个工时，0.2立方木材 售价80元。每张椅子使用10个工时，0.05立方木材售价45元。问为达到最大的收益，应如何安排生产？,分析：1. 求什么？生产多少桌子？生产多少椅子？2. 优化什么？收益最大3. 限制条件？原料总量劳力总数,x1 x2Max f=80 x1+45 x20.2 x1 +0.05 x2 4 15 x1 +10 x2 450,模型I ：以产值为目标取得最大收益. 设：生产桌子 x1张, 椅子 x2张,(决策变量) 将目标优化为：max f=80x1+45x2对决策变量的约束：0.2x1+0
4、.05x2415x1+10x2 450,x1 0, x2 0,规划问题：在约束条件下求目标函数的最优值点。 规划问题包含3个组成要素:决策变量、目标函数、约束条件。 当目标函数和约束条件 都是决策变量的线性函数时，称为线性规划问题, 否则称为非线性规划问题。,2. 线性规划问题求解方法 称满足约束条件的向量为可行解, 称可行解的集合为可行域 , 称使目标函数达最优值的可行解为最优解. 图解 法：(解两个变量的线性规划问题) 在平面上画出可行域（凸多边形）， 计算目标函数在各极点(多边形顶点)处的值 比较后，取最值点为最优解。,命题 1 线性规划问题的可行解集是凸集可行解集：线性不等式组的解,0
5、.2x1+0.05x2=4,15x1+10x2=450,命题2 线性规划问题的目标函数(关于不同的目标值是一族平行直线,目标值的大小描述了直线离原点的远近,命题3 线性规划问题的最优解一定在可行解集的某个极点上达到 (穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).,单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 模型的标准化正则模型:决策变量: x1,x2,xn.目标函数: Z=c1x1+c2x2+cnxn.约束条件: a11x1+a1nxnb1,am1x1+amnxnbm,模型的标准化10. 引入松弛变量将不等
6、式约束变为等式约束若有 ai1x1+ainxnbi, 则引入xn+i 0, 使得ai1x1+ainxn+ xn+i =bi 若有 aj1x1+ajnxnbj, 则引入xn+j 0, 使得aj1x1+ajnxn- xn+j =bj. 且有 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
7、, xn,max Z = c1x1+ cnxn,s. t. a11x1+ a1nxn= b1,am1x1+ amnxn= bm,x1 0, xn 0,定义: 若代数方程AX=B的解向量有n-m个分量为零, 其余m个分量对应A的m个线性无关列, 则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解,则称之为基本可行解 命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解.,一般线性规划的数学模型及解法：min f=cTx s.t. Ax bA1x=b1LB x UB Matlab求解程序 x,f=linprog
8、(c,A,b,A1,b1,LB,UB),模型 II . 在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。设每立方木材和每个工时投入“成本”分别为 y1 y2(决策变量) 则目标函数为： g=4y1+450y2 对决策变量的约束0.2y1+15y2 800.05y1+10y2 45 y1 0, y2 0得 y1=100（元/m3），y2=4（元/工时）,3. 对偶问题： A 是m n 矩阵， c 是 n 1向量，b 是 m 1向量 x 是 n 1向量, y 是 m 1向量,问题 max f=cTx s.t. Ax bxi 0, i=1,2,n.,对偶问题 min f=bTy s.
9、t. ATy c yi 0, i=1,2,m.,对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一个也有有穷的最优解, 且最优值相等.若两者之一有无界的最优解, 则另一个没有可行解,模型I 给出了生产中的产品的最优分配方案 模型 II 给出了生产中资源的最低估价. 这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出 的贡献确定的估价, 被称为“影子价格”.,例2. 生产5种产品P1, P2, P3,P4,P5 单价为550, 600, 350, 400, 200. 三道工序:研磨、钻孔、装配。所需工时为P1 P2 P3 P4 P5I 12 20
10、 0 25 15II 10 8 16 0 0III 20 20 20 20 20 各工序的生产能力（工时数）288 192 384 如何安排生产，收入最大。,模型：设 xi 生产 Pi 的件数。 则max Z=550 x1+600 x2+350 x3+400 x4+200 x5。 s. t. 12 x1+20 x2+0 x3+25 x4+15 x5 28810 x1+8 x2+16 x3+0 x4+0 x5 19220 x1+20 x2+20 x3+20 x4+20 x5 384xi 0 有解 x1=12， x2 =7.2， x3 = x4 = x5 = 0Z=10920,1. 如果增加三个工
11、序的生产能力，每个工序的单位增长会带来多少价值？ 2. 结果表明与 P1, P2相比 P3, P4, P5，定价低了. 价格提到什么程度,它们才值得生产? 对偶问题有解:w1=6.25, w2=0, w3=23.75Zopt=6.25288+0192+23.75384 X3的成本: 0 6.25+16 0+20 23.75=475350,4. 非线性规划min z=f(z)s.t. A1xb1, A2x=b2,c1(x)0, c2(x)=0LB x UB MATLAB 程序x,z=fmincon(fun,x0,A1,b,A2,b2,LB,UB,nonlcon）,例3.某公司有6个建筑工地，位置
12、坐标为(ai, bi) (单位：公里),水泥日用量di (单位：吨）,建两个日储量e为20吨的料场，需要确定料场位置(xj,yj)和运量cij ，使总吨公里数最小。,min z=f(z)s.t. A1xb1, A2x=b2,c1(x)0, c2(x)=0LB x UB MATLAB 程序x,z=fmincon(fun,x0,A1,b,A2,b2,LB,UB,nonlcon）,用随机搜索算法确定初始点：在可行域0.5,8.750.75,7.75内简单地选取n个随机的的点，计算目标函数在这些点的值，选择其中最小的点即可。然后，可采用Matlab求最值点程序求出精确的最小值点: 求函数fun在x0点
13、附近的最小值点,随机搜索程序的为代码,算法：随机搜索法 变量：xl=x的下限xu=x的上限yl=y的下限yu=y的上限N =迭代次数xm=极小点x的近似值ym=极小点y的近似值zm=极小点f(x,y)的近似值 输入：xl，xu，yl，yu 过程：开始xrandomxl，xuyrandomyl，yuzmf(x,y),对n=1到N循环开始xrandomxl，xuyrandomyl，yuzf(x,y)若zzm，则xmxymyzm z结束结束 输出：xm，ym，zm,5. 0-1规划如果要求决策变量只取0 或 1的线性规划问题, 称为整数规划.0-1 约束不一定是由变量的性质决定的, 更多地是由于逻辑
14、关系引进问题的,例4 背包问题一个旅行者的背包最多只能装 6 kg 物品. 现有4 件物品重量为 2 kg , 3 kg, 3 kg, 4 kg, 价值为 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大?建模: 记xj：旅行者携带第 j 件物品的件数, xj = 0, 1.约束条件2x 1 +3x 2 +3x 3 +4x 4 6求xj 使目标函数 f=x1+1.2x2+0.9x3+1.1x4最大.,用Lingo 软件求解0-1规划 Linear Interactive and General Optimizer Model: Max=x1+1.2*x2+0.
15、9*x3+1.1*x4; 2*x1+3*x2+3*x3+4*x4=6; bin(x1); bin(x2); bin(x3); bin(x4); end,例 5 供货问题一家公司生产某种商品.现有n 个客户, 第 j 个客户需要货物量至少为 bj,可在m 各不同地点设厂供货. 在地区 i 设厂的费用为 di ,供货能力为 hi , 向第 j 个客户供应单位数量的货物费用为 cij. 如何设厂与供货使总费用最小.,模型： 记 xij 为在地区 i 向第 j 个客户供货数量,记 yi =1 , 在地区 i 设厂，记 yi =0 不在地区 i 设厂， 求设厂和供货分配方案yi， xij 使得目标函数 f= yi (j cij xij + di ) 在约束条件 i yi xij bj, j=1,nj xij hi 0, I=1,m xij0, yi =0, 1 下达到最小,6. 整数规划如果要求决策变量取整数, 或部分取整数的线性规划问题, 称为整数规划.,
