最优化计算方法

第三章最优化计算方法 单变量优化多变量优化线性规划离散最优化 单变量优化 例3 1再来考虑售猪问题 但现在考虑到猪的生长率不是常数的事实 假设现在猪还小 生长率是增加的 什么时候将猪售出从而获得最大收益 求解模型 图像法 clearall closeall symsxy 0 65 0 01 x 200 exp 0 025 x 0 45 x ezplot y 0 20 gridon ezplot y 0 20 ezplot y 0 40 ezplot y 18 22 gridon ezplot y 19 20 gridon 数值方法求解 Matlab dydx diff y x xmax solve dydx xmax double xmax xmax xmax 1 ymax subs y x xmax Newton法 求方程F x 0的根 牛顿法 x n x n 1 F x n 1 F x n 1 F dydx F1 diff F x formatlongN 10 numberofiterationsx0 19 initialguessfprintf iterationxvalue n n fori 1 Nx1 x0 subs F x x0 subs F1 x x0 fprintf 5 0f 1 16f n i x1 x0 x1 enddisplay Hence thecriticalpoint solutionofF 0 is approx x1 灵敏性分析 考虑最优售猪时间关于小猪增长率c 0 025的灵敏性 xvalues 0 forc 0 022 0 001 0 028y 0 65 0 01 x 200 exp c x 0 45 x dydx diff y x xmaxc solve dydx xmaxc double xmaxc xmaxc xmaxc 1 xvalues xvalues xmaxc endxvalues xvalues 2 end cvalues 0 022 0 001 0 028 cvalues cvalues transposestherowintoacolumnformatshort display cvalues xvalues 例3 2更新消防站的位置 对响应时间数据的统计分析给出 对离救火站r英里打来的求救电话 需要的响应时间估计为 下图给出了从消防管员处得到的从城区不同区域打来的求救电话频率的估计数据 求新的消防站的最佳位置 3 2多变量最优化 设 x y 为新消防站的位置 对求救电话的平均响应时间为 问题为在区域0 x 6 0 y 6上求z f x y 的最小值 绘制目标函数图形 clearallsymsxyr1 sqrt x 1 2 y 5 2 0 91 r2 sqrt x 3 2 y 5 2 0 91 r3 sqrt x 5 2 y 5 2 0 91 r4 sqrt x 1 2 y 3 2 0 91 r5 sqrt x 3 2 y 3 2 0 91 r6 sqrt x 5 2 y 3 2 0 91 r7 sqrt x 1 2 y 1 2 0 91 r8 sqrt x 3 2 y 1 2 0 91 r9 sqrt x 5 2 y 1 2 0 91 z 3 2 1 7 6 r1 8 r2 8 r3 21 r4 6 r5 3 r6 18 r7 8 r8 6 r9 84 ezmesh z 绘制等值线图 ezcontourf z 0606 colorbar gridon 随机搜索算法 算法 随机搜索算法变量 a x的下限 b x的上限c y的下限 d y的上限xmin ymin zmin输入 a b c d N过程 开始x random a b y random c d zmin f x y 对n 1到N循环开始x random a b y random c d z f x y 若z zmin 则xmin x ymin y zmin z结束结束输出 xmin ymin zmin 代码实现 a 0 b 6 c 0 d 6 N 1000 x0 a b a rand 1 y0 c d c rand 1 zmin subs z x y x0 y0 fprintf Iterationxminyminzminvalue n n forn 1 Nxnew a b a rand 1 ynew c d c rand 1 znew subs z x y xnew ynew ifznew zminxmin xnew ymin ynew zmin znew fprintf 4 0f 1 6f 1 6f 1 6f n n xmin ymin zmin endend 灵敏性分析 a 1 5 b 2 c 2 5 d 3 N 100 x0 a b a rand 1 y0 c d c rand 1 zmin subs z x y x0 y0 fprintf Iterationxminyminzminvalue n n forn 1 Nxnew a b a rand 1 ynew c d c rand 1 znew subs z x y xnew ynew ifznew zminxmin xnew ymin ynew zmin znew fprintf 4 0f 1 6f 1 6f 1 6f n n xmin ymin zmin endend 例3 3一家草坪家俱厂商生产两种草坪椅 一种是木架的 一种是铝管架的 木架椅的生产价格为每把18美元 铝管椅为每把10美元 在产品出售的市场上 可以售出的数量依赖于价格 据估计 若每天售出x把木架椅 y把铝管椅 木架椅和铝管椅的出售价格分别不能超过 求最优生产量 问题 在生产量的可行域x 0 y 0上求利润函数z f x y 的最大值 绘制目标函数及等值线图 clearall closeallsymsx1x2z x1 10 31 x1 0 5 1 3 x2 0 2 18 x1 x2 5 15 x2 0 4 8 x1 0 08 10 x2 ezsurfc z 0 1100 110 title ObjectiveFunctionz 最优值点大致位于x 5 y 6 随机搜索求近似最优值 a 0 b 10 c 0 d 10 N 1000 x10 a b a rand 1 x20 c d c rand 1 zmin subs z x1 x2 x10 x20 fprintf Iterationx1minx2minzminvalue n n forn 1 Nx1new a b a rand 1 x2new c d c rand 1 znew subs z x1 x2 x1new x2new ifznew zminx1min x1new x2min x2new zmin znew fprintf 4 0f 1 6f 1 6f 1 6f n n x1min x2min zmin endend 牛顿法求较精确的近似值 牛顿法见书p 56x x1 x2 F diff z x1 G diff z x2 Dz F G thegradientvectorofz即求方程组Dz 0的解 牛顿法代码实现 dFdx1 diff F x1 dFdx2 diff F x2 dGdx1 diff G x1 dGdx2 diff G x2 D2z dFdx1dFdx2 dGdx1dGdx2 JacobianofDz sameasHessianofD2z x0 5 5 initialguessN 10 numberofiterationsfori 1 NDz0 subs Dz x1 x2 x0 1 x0 2 D2z0 subs D2z x1 x2 x0 1 x0 2 xnew x0 inv D2z0 Dz0 x0 xnew endxmax xnewzmax subs z x1 x2 xmax 1 xmax 2 xmaxfigure ezcontourf z 0 1100 110 holdonplot3 xmax 1 xmax 2 zmax mo LineWidth 2 MarkerEdgeColor k MarkerFaceColor 491 63 MarkerSize 12 title Countourplotandoptimalvalue 3 3线性规划 例3 4一个家庭农场有625英亩的土地可用来种植农作物 这个家庭可考虑种植的农作物有玉米 小麦 燕麦 预计有1000英亩 英尺的灌溉用水 农场工人每周可以投入的工作时间为300小时 其他数据如下表 为获得最大收益 每种作物应各种植多少 农场问题的有关数据 变量 x1 x2 x3 种植玉米 小麦 燕麦的亩数w 需要的灌溉用水 英亩 英尺 l 需要的劳力 人 小时 周 t 种植作物的总英亩数y 总收益 美元 假设 w 3 0 x1 1 0 x2 1 5x3 0目标 求y的最大值 建模方法 线性规划 线性规划简介见书p 59可以用lindo lingo软件求解 模型求解 MAX400X1 200X2 250X3SUBJECTTO3X1 X2 1 5X3 10000 8X1 0 2X2 0 3X3 300X1 X2 X3 625END reducedcost值表示当该非基变量增加一个单位时 其他非基变量保持不变 目标函数减少的量 对max型问题 也可理解为 为了使该非基变量变成基变量 目标函数中对应系数应增加的量 灵敏性分析 增加1英亩 英尺灌溉水量对最优解的影响MAX400X1 200X2 250X3SUBJECTTO3X1 X2 1 5X3 10010 8X1 0 2X2 0 3X3 300X1 X2 X3 625END 玉米收益的少量提高对最优解的影响 农作物每英亩收益会随气候及市场变化MAX450X1 200X2 250X3SUBJECTTO3X1 X2 1 5X3 10000 8X1 0 2X2 0 3X3 300X1 X2 X3 625END 燕麦收益的少量提高对最优解的影响 MAX400X1 200X2 260X3SUBJECTTO3X1 X2 1 5X3 10000 8X1 0 2X2 0 3X3 300X1 X2 X3 625END 新品种玉米 这种玉米新品种需要较少的灌溉用水2 5英亩 英尺 而不是3 0 MAX400X1 200X2 250X3SUBJECTTO2 5X1 X2 1 5X3 10000 8X1 0 2X2 0 3X3 300X1 X2 X3 625END 新增另一新的作物 大麦 一英亩大麦需要1 5英亩 英尺的水和0 25人 小时的劳力 预期可获得200美元的收益 用一个新的决策变量x4表示种植大麦的英亩数 MAX400X1 200X2 250X3 200 x4SUBJECTTO3X1 X2 1 5X3 1 5x4 10000 8X1 0 2X2 0 3X3 0 25x4 300X1 X2 X3 x4 625END 例3 5运输问题 一家大建筑公司正在三个地点开掘 同时又在其他4个地点建筑 这里需要土方的填充 在1 2 3处挖掘产生的土方分别为每天150 400 325立方码 建筑地点A B C D处需要的填充土方为每天175 125 225 450立方码 也可以从地点4用每立方码5美元的价格获得额外的填充土方 填充土方运输的费用约为一货车容量 10立方码 每英里20美元 下表给出了各地点间距离的英里数 求使公司花费最少的运输计划 建筑地点间的距离 变量 xij 从地点i运到地点j的土方量 立方码 si 从地点i运出的土方量 立方码 rj 运到地点j的土方量 立方码 cij 从地点i运到地点j的土方运输费用 美元 立方码 dij 地点i到地点j的距离 英里 C 总运费 美元 假设 s1 x1A x1B x1C x1Ds2 x2A x2B x2C x2Ds3 x3A x3B x3C x3Ds4 x4A x4B x4C x4DrA x1A x2A x3A x4ArB x1B x2B x3B x4BrC x1C x2C x3C x4CrD x1D x2D x3D x4D S1 175 rB 125 rC 225 rD 450 cij 2dij i 1 2 3cij 2dij 5 i 4C c1Ax1A c1Bx1B c1Cx1C c1Dx1D c2Ax2A c2Bx2B c2Cx2C c2Dx2D c3Ax3A c3Bx3B c3Cx3C c3Dx3D c4Ax4A c4Bx4B c4Cx4C c4Dx4D目标 求C的最小值 线性规划的标准形式 Miny 10 x1A 4x1B 12x1C 20 x1D 8x2A 10 x2B 14x2C 10 x2D 14x3A 12x3B 8x3C 8x3D 23x4A 25x4B 17x4C 9x4D约束条件 x1A x1B x1C x1D 175x1B x2B x3B x4B 125x1C x2C x3C x4C 225x1D x2D x3D x4D 450 xij 0 i 1 2 3 4 j A B C D 问题求解 MIN10 x1A 4x1B 12x1C 20 x1D 8x2A 10 x2B 14x2C 10 x2D 14x3A 12x3B 8x3C 8x3D 23x4A 25x4B 17x4C 9x4DSUBJECTTOx1A x1B x1C x1D 175x1B x2B x3B x4B 125x1C x2C x3C x4C 225x1D x2D x3D x4D 450END 稳健性分析 MIN10 x1A 4x1B 12x1C 20 x1D 8x2A 10 x2B 14x2C 10 x2D 14x3A 12x3B 8x3C 8x3D 23x4A 25x4B 17x4C 9x4DSUBJECTTOx1A x1B x1C x1D 150 x2A x2B x2C x2D 400 x3A x3B x3C x3D 325x1A x2A x3A x4A 175x1B x2B x3B x4B 125x1C x2C x3C x4C 225x1D x2D x3D x4D 450END 3 4离散最优化 例3 6仍考虑农场问题 这个家庭有625英亩的土地用来种植 有5块每块120英亩的土地和另一块25英亩的土地 这家人想在每块地上种植一种作物 玉米 小麦或燕麦 与前面一样 有1000英亩 英尺可用的灌溉用水 每周农场工人可提供300小时的劳力 其他数据下表给出 求应在每块地中种哪种植物 从而使总收益达最大 农场问题的有关数据 变量 x1 种植玉米的120英亩地块数x2 种植小麦的120英亩地块数x3 种植燕麦的120英亩地块数x4 种植玉米的25英亩地块数x5 种植小麦的25英亩地块数x6 种植燕麦的25英亩地块数w 需要的灌溉用水 英亩 英尺 l 需要的劳力 人 小时 周 t 种植作物的总英亩数y 总收益 美元 假设 w 120 3 0 x1 1 0 x2 1 5x3 25 3 0 x4 1 0 x5 1 5x6 l 120 0 8x1 0 2x2 0 3x3 25 0 8x4 0 2x5 0 3x6 t 120 x1 x2 x3 25 x4 x5 x6 y 120 400 x1 200 x2 250 x3 25 400 x4 200 x5 250 x6 w 1000 l 300 t 625x1 x2 x3 5 x4 x5 x6 1 x1 x6为非负整数 目标 求y最大值 整数规划的标准形式 maxy 48000 x1 24000 x2 30000 x3 10000 x4 5000 x5 6250 x6s t 375x1 125x2 187 5x3 75x4 25x5 37 5x6 1000100 x1 25x2 37 5x3 20 x4 5x5 7 5x6 300 x1 x2 x3 5x4 x5 x6 1x1 x6为非负整数 问题求解 MAX48000 x1 24000 x2 30000 x3 10000 x4 5000 x5 6250 x6SUBJECTTO375x1 125x2 187 5x3 75x4 25x5 37 5x6 1000100 x1 25x2 37 5x3 20 x4 5x5 7 5x6 300 x1 x2 x3 5x4 x5 x6 1ENDGIN6 灵敏性分析 有100英亩 英尺的额外灌溉水量可用 只要灌溉水量不低于1000 25 975 最优解不会改变 可用水量只有950时 又如何 以上灵敏性分析显示 IP问题解的不可预期的特点 稳健性分析 例如最小地块为2时 问题为 Maxy 800 x1 400 x2 500 x3s t 6 0 x1 2 0 x2 3 0 x3 10001 6x1 0 4x2 0 6x3 300 x1 x2 x3 312x1 x2 x3为非负整数 问题求解 MAX800 x1 400 x2 500 x3SUBJECTTO6 0 x1 2 0 x2 3 0 x3 10001 6x1 0 4x2 0 6x3 300 x1 x2 x3 312ENDGIN3 例3 7 仍考虑例3 5中的土方问题 在使用10立方码载重量的卡车运输的情况下 公司已经确定了最优的运输方案 公司又有3辆更大的卡车可用于运输 载重量为20立方码 使用这些车辆可能会在运输中节省一些资金 载重10立方码的卡车平均用20分钟装车 5分钟卸车 每小时平均开20英里 费用为每英里单位重量20美元 载重量20立方码的卡车30分钟装车 5分钟卸车 每小时平均开20英里 费用为每英里单位重量30美元 为最大限度地节省运输费用 应如何安排车辆的使用 第一步 提出问题 哪条路上使用哪种卡车 假设每条路上只使用一种类型的卡车 由于大卡车运量是小卡车的2倍 而费用却不到小卡车的2倍 因此 我们希望将这些卡车安排到能节约资金最多的路线上 计算每条路上使用不同类型的卡车能节约的费用 例如路线1 从1到B运125立方码 距离2英里 小卡车一次装车20分钟 卸车5分钟 每小时20英里要开6分钟 因此运一次需要31分钟 125立方码的土需要运13次 共需13 31 403分钟 假设一个工作日是8小时 这样每辆卡车工作时间不超过480分钟 因此 路线1用一辆卡车就足够 小卡车运输费用 13 次 2 英里 次 20 美元 英里 520美元如果线路1用大卡车 运一次需要30 5 6 41分钟 为运走125立方码的土 需要7次 共需7 41 287分钟 因此一辆大卡车足够 大卡车运输费用为420美元 比用小卡车节省100美元 类似计算其他路线上的情况 路线2 需要大卡车1辆 节约费用360美元路线3 需要大卡车2辆 节约费用400美元路线4 需要大卡车1辆 节约费用200美元路线5 需要大卡车2辆 节约费用640美元 变量及假设 变量 xi 1如果在路线i上使用大卡车xi 0如果在路线i上使用小卡车T 用的大卡车总数y 节约的总费用 美元 假设T 1x1 1x2 2x3 1x4 2x5y 100 x1 360 x2 400 x3 200 x4 6