《最优化方法练习题答案 .pdf》由会员分享，可在线阅读，更多相关《最优化方法练习题答案 .pdf（40页珍藏版）》请在金锄头文库上搜索。
1、练习题一 1 建立优化模型应考虑哪些要素 答 决策变量 目标函数和约束条件 2 讨论优化模型最优解的存在性 迭代算法的收敛性及停止准则 答 针对一般优化模型 min 0 1 2 0 1 i j f x stgxim h L L 讨论解的可行域 D 若存在一点 XD 对于XD 均有 fXfX则称 X 为优化模型最优解 最优解存在 迭 代算法的收敛性是指迭代所得到的序列 1 2 K XXXLL 满足 1 KK fXf X 则迭代法收敛 收敛的停止准则有 1 kk xx 1 kk k xx x 1 kk fxfx 1 kk k fxfx fx k fx等等 练习题二 1 某公司看中了例2 1 中厂家
2、所拥有的 3 种资源 R1 R2 和 R3 欲出价收购 可 能用于生产附加值更高的产品 如果你是该公司的决策者 对这3 种资源的收购报价 是多少 该问题称为例2 1 的对偶问题 解 确定决策变量对 3 种资源报价 123 y yy作为本问题的决策变量 确定目标函数问题的目标很清楚 收购价最小 确定约束条件资源的报价至少应该高于原生产产品的利润 这样原厂家才可能 卖 因此有如下线性规划问题 123 min170100150wyyy 123 123 123 5210 23518 0 yyy styyy yyy 2 研究线性规划的对偶理论和方法 包括对偶规划模型形式 对偶理论和对偶单 纯形法 答 略
3、 3 用单纯形法求解下列线性规划问题 1 0 4 32 22 min 321 31 321 321 321 xxx xx xxx xxx ts xxxz 2 5 2 1 0 5 22 22 4min 532 432 321 32 ix xxx xxx xxx ts xxz i 解 1 引入松弛变量x4 x5 x6 123456 min0 0 0 zxxxxxx 1234 123 2 2 25 3 13 6 4 1 2 3 4 5 60 xxxx xxxx st xxx xxxxxx cj 1 1 1 0 0 0 CB基b x1x2x3x4x5x6 0 x42 1 1 2 1 0 0 0 x53
4、 2 1 1 0 1 0 0 x64 1 0 1 0 0 1 cj zj1 1 1 0 0 0 因检验数 2 0 故确定 x2为换入非基变量 以x2的系数列的正分量对应去除常数 列 最小比值所在行对应的基变量x4作为换出的基变量 cj 1 1 1 0 0 0 CB基b x1x4x3x4x5x6 1 x22 1 1 2 1 0 0 0 x51 1 0 3 1 1 0 0 x64 1 0 1 0 0 1 cj zj2 0 1 1 0 0 因检验数 30 表明已求得最优解 0 8 3 1 3 0 0 11 3 X 去除添加的松弛变 量 原问题的最优解为 0 8 3 1 3 X 2 根据题意选取 x1
5、 x4 x5 为基变量 5 2 1 0 5 22 22 4min 532 432 321 32 ix xxx xxx xxx ts xxz i cj 0 1 1 0 0 CB基b x1x2 x3 x4x5 0 x12 1 2 1 0 0 0 x42 0 1 2 1 0 0 x55 0 1 1 0 1 cj zj0 1 1 0 0 因检验数 2 0 最小 故确定 x2为换入非基变量 以x2的系数列的正分量对应去除 常数列 最小比值所在行对应的基变量x4作为换出的基变量 cj 0 1 1 0 0 CB基b x1x2 x3 x4x5 0 x16 1 0 3 2 0 1 x22 0 1 2 1 0 0
6、 x53 0 0 3 1 1 cj zj0 0 1 1 0 因检验数 30 表明已求得最优解 9 4 1 0 0 X 4 分别用大 M法 两阶段法和 Matlab 软件求解下列线性规划问题 1 0 32 639 33 4min 21 21 21 21 21 xx xx xx xx ts xxz 2 0 52 151565 935 121510max 321 321 321 321 321 xxx xxx xxx xxx ts xxxz 解 1 大 M 法 根据题意约束条件1 和 2 可以合并为 1 引入松弛变量 x3 x4 构造新问题 1234 min z 4x x Mx 0 x 123 12
7、4 14 33 23 0 xxx stxxx xxL cj 4 1 M 0 CB基b x1x2x3x4 M x33 3 1 1 0 0 x43 1 2 0 1 cj zj4 3M 1 M 0 0 4 x11 1 1 3 1 3 0 0 x42 0 5 3 1 3 1 cj zj0 1 3 M 4 3 0 4 x13 5 1 0 2 5 1 5 1 x26 5 0 1 1 5 3 5 cj zj0 0 M 7 5 1 5 因检验数 j 0 表明已求得最优解 3 5 6 5 X Matlab 调用代码 f 4 1 A 9 3 1 2 b 6 3 Aeq 3 1 beq 3 lb 0 0 x fva
8、l linprog f A b Aeq beq lb 输出结果 Optimization terminated x 0 6000 1 2000 fval 3 6000 2 大 M 法 引入松弛变量 x4 x5 x6 x7构造新问题 1234567 max101512000zxxxxxxMx 1234 1235 12367 17 539 561515 25 0 xxxx xxxx st xxxxx xxL 单纯形表计算略 当所有非基变量为负数 人工变量 7 x 0 5 所以原问题无可行解 请同学们自己求解 Matlab 调用代码 f 10 15 12 A 5 3 1 5 6 15 2 1 1 b
9、 9 15 5 lb 0 0 0 x linprog f A b lb 输出结果 原题无可行解 5 用内点法和 Matlab 软件求解下列线性规划问题 0 52 622 2min 321 21 321 321 xxx xx xxx ts xxxz 解 用内点法的过程自己书写 参考答案 最优解 4 3 7 3 0 X 最优值 5 Matlab 调用代码 f 2 1 1 Aeq 1 2 2 2 1 0 beq 6 5 lb 0 0 0 x fval linprog f Aeq beq lb 输出结果 Optimization terminated x 1 3333 2 3333 0 0000 fv
10、al 5 0000 6 用分支定界法求解下列问题 1 且均为整数0 4595 6 85max 21 21 21 21 xx xx xx ts xxz 2 为整数且 121 21 21 21 0 357 63 97max xxx xx xx ts xxz 解 1 调用 matlab编译程序 bbmethod f 5 8 G 1 1 5 9 h 6 45 x y bbmethod f G h 0 0 1 1 1 x 3 3 y 39 最优解 3 3 最优值 39 2 调用 matlab编译程序 bbmethod f 7 9 G 1 3 7 1 h 6 35 x y bbmethod f G h 0
11、 0 1 0 1 x 5 0 y 35 最优解 5 0 最优值 35 7 用隐枚举法和Matlab 软件求解下列问题 1 3 2 1 10 1 334 4352 234min 32 321 321 321 jx xx xxx xxx ts xxxz j 或 2 5 2 1 10 133611 83437 42 32523max 5421 5431 54321 54321 jx xxxx xxxx xxxxx ts xxxxxz j 或 解 隐枚举法 1 将 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 分别带入到约束条件中 可以得到 原问题的最
12、优解是 0 0 1 目标函数最优值 2 2 将 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 分别带入到约束条件中 可以得到 原问题的最优解是 1 1 0 0 0 目标函数最优值 5 Matlab 软件求解 1 调用代码 f 4 3 2 价值向量 f A 2 5 3 4 1 3 0 1 1 不等式约束系数矩阵A 中的分号 为行分隔符 b 4 3 1 不等式约束右端常数向量b x fval bintprog f A b 调用函数 bintprog 注意两个空数组的占位作用 输出结果 x 0 0 1 fval 2 2 调用代码 f 3 2 5
13、2 3 价值向量 f A 1 1 1 2 1 7 0 3 4 3 11 6 0 3 3 不等式约束系数矩阵A 中的分号 为行分隔符 b 4 8 1 不等式约束右端常数向量b x fval bintprog f A b 调用函数 bintprog 注意两个空数组的占位作用 输出结果 x 1 1 0 0 0 fval 5 最优值 5 8 某地区有 A B C 三个化肥厂 供应本地甲 乙 丙 丁四个产粮区 已知各 化肥厂可供应化肥的数量和各产粮区对化肥的需要量 以及各厂到各区每吨化肥的运价 如表 2 28 所示 试制定一个使总运费最少的化肥调拨方案 表 2 1 运价 产粮 元 吨 区 化肥厂 甲乙丙
14、丁各厂供应量 万吨 A1 5 8 7 3 7 A24 9 10 7 8 A38 4 2 9 3 各区需要量 万吨6 6 3 3 解 设 A B C 三个化肥厂为 A1 A2 A3 甲 乙 丙 丁四个产粮区为B1 B2 B3 B4 cij为由 Ai运化肥至 Bj的运价 单位是元 吨 xij为由 Ai运往 Bj的化肥数 量 i 1 2 3 j 1 2 3 4 单位是吨 z 表示总运费 单位为元 依题意问题的数学模型为 34 11 min ijij ij zc x 112131 122232 132333 142434 11121314 21222324 31323334 6 6 3 3 7 8 7
15、 xxx xxx xxx stxxx xxxx xxxx xxxx 该题可以用单纯形法或matlab 自带工具箱命令 linprog 求解 9 求解下列不平衡运输问题 各数据表中 方框内的数字为单位价格 ij c 框外右 侧的一列数为各发点的供应量 i a 框底下一行数是各收点的需求量 j b 1 5 1 7 10 要求收点 3 的需求必须正好满足 6 4 6 80 3 2 5 15 75 20 50 2 5 1 0 20 要求收点 1 的需求必须由发点4 供应 3 2 4 10 7 5 2 15 9 6 0 15 5 10 15 解答略 10 一公司经理要分派4 位推销员去 4 个地区推销某
16、种商品 推销员各有不同的经 验和能力 因而他们在不同地区能获得的利润不同 其获利估计值如表2 29 所示 公 司经理应怎样分派才使总利润最大 表 2 2 地区 推销员 1234 1 35 27 28 37 2 28 34 29 40 3 35 24 32 33 4 24 32 25 28 解 用求极大值的 匈牙利法 求解 效率矩阵表示为 28253224 33322435 40293428 37282735 1215816 78165 011612 312135 M Cij M 40 行约简 4708 23110 011612 09102 44 0 8 2011 0 08612 0 6102 所画 0 元素少于 n n 4 未得到最优解 需要继续变换矩阵 求能覆盖所有 0 元素的最少数直线集合 44 0 8 2011 0 08612 0 6102 未被直线覆盖的最小元素为cij 2 在未被直线覆盖处减去2 在直线交叉处加上2 6408 40110 06410 0480 6408 4 0 110 06410 048 0 得最优解 0010 0100 1000 0001 使总利润为最
