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