重庆大学最优化方法习题答案.pdf

习题一 1 1 利用图解法求下列线性规划问题 1 maxz x1 x2 3x 1 x2 2 s t x1 2x2 5 x1 x2 0 解 根据条件 可行域为下面图形中的阴影部分 有图形可知 原问题在 A 点取得最优值 最优值 z 5 2 minz x1 6x2 2x 1 x2 1 s t x1 x2 7 x1 x2 0 解 图中阴影部分表示可行域 由图可知原问题在点 A 处取得最优值 最优值 z 6 3 maxz 3x1 2x2 s t x1 2x2 4 x1 x2 0 解 如 图 所 示 可 行 域 为 图 中 阴 影 部 分 易 得 原 线 性 规 划 问 题 为 无 界 解 x 1 x2 1 4 minz 2x1 5x2 x 1 2x2 6 s t x1 x2 2 x1 x2 0 解 由图可知该线性规划可行域为空 则原问题无可行解 1 2对下列线性规划问题 找出所有的基解 基可行解 并求出最优解和最优值 1 minz 5x1 2x2 3x3 6x4 s t 2x1 x2 x3 2x4 3 x1 x2 x3 x4 0 x 1 2x2 3x3 4x4 7 解 易知x1的系数列向量p1 x2的系数列向量p2 x3的系数列向量p3 2 1 1 2 1 3 x4的系数列向量p4 2 4 因为p1 p2 线性无关 故有 2x1 x2 3 x3 2x4 x 1 2x2 7 3x3 4x4 令非基变量为x3 x4 0 得 x11 1 x 2 3 1 3 所以得到一个基解x 1 0 0 是非基可行解 3 3 1 11 因为p1 p3 线性无关 可得基解x 0 0 z2 555 211 2 43 因为p1 p4线性无关 可得基解x 0 0 是非基可行解 36 111 3 因为p2 p3线性无关 可得基解x 0 2 1 0 z4 1 4 因为p2 p4线性相关 x2 x4不能构成基变量 因为p3 p4线性无关 可得基解x 0 0 1 1 z6 3 6 所以x 2 x 4 x 6 是原问题的基可行解 x 6 是最优解 最优值是z 3 2 maxz x1 x2 2x3 x4 x5 x 1 x2 x3 x4 1 s t x1 2x2 x5 4 xi 0 i 1 2 3 4 5 解 易知x1的系数列向量p1 x2 的系数列向量p2 x3 的系数列向量 1 1 1 2 0 1 x 的系数列向量p 0 1 p3 44 x 的系数列向量p 0 55 1 因为p1 p2线性无关 故有 x1 2x2 4 x5 x 1 x2 1 x3 x4 令非基变量为x3 x4 x5 0 得 x5 1 x 2 3 2 3 所以得到一个基解x 1 0 0 0 是非基可行解 3 3 2 5 因为p1 p3 线性无关 可得基解x 4 0 5 0 0 是非基可行解 2 因为p1 p4线性无关 可得基解x 4 0 0 5 0 是非基可行解 3 因为p1 p5 线性无关 可得基解x 1 0 0 0 5 z4 4 4 因为p2 p3线性相关 得基解x 0 2 1 0 0 是非基可行解 5 因为p2 p4线性无关 可得基解x 0 2 0 1 0 是非基可行解 6 因为p2 p5线性无关 可得基解x 0 1 0 0 2 z7 1 7 因为p3 p4线性相关 x3 x4不能构成基变量 因为p3 p5线性无关 可得基解x 0 0 1 0 4 z9 6 9 因为p4 p5线性无关 可得基解x 0 0 0 1 4 z10 3 10 所以原线性规划的基可行解是x 4 x 7 x 9 x 10 最优解是x 7 最优值是z 1 1 3 用单纯形法求解下列线性规划问题 1 maxz 2x1 3x2 x 1 3x2 5 s t x1 x2 2 x1 x2 0 解 引入松弛变量x3 剩余变量x4和人工变量x5 把原问题化为规范式 maxz 2x1 3x2 Mx5 s t x1 x2 x4 x5 2 其中 M 无限大 xi 0 i 1 2 5 构造初始单纯形表并计算如下 x 1 3x2 x3 5 以x2作为换入基 x3作为换成基 计算得 以x1为换入基 x5作为换出基有 以x4换入 x2换出有 x1x2x3x4x5 2 M3 M0 M0 x3 131005 x5 110 112 x1x2x3x4x5 1 2 M 3 0 1 M 3 M0 x21 3 1 1 3 00 5 3 x52 3 0 1 3 11 1 3 x1x2x3x4x5 00 1 2 3 2 3 M 2 5 5 x2 01 1 2 1 2 1 2 1 5 x1 10 1 2 3 2 3 2 0 5 根据单纯形表可知 原问题的最优解为x 5 0 0 3 最优值为z 10 2 maxz x1 x2 2x3 3x 1 x2 x3 5 s t x1 4x2 x3 7 x1 x2 x3 0 解 引入松弛变量x4 剩余变量x5和人工 变量x6 把原问题规范化为 maxz x1 x2 2x3 Mx6 3x 1 x2 x3 x4 5 s t x1 4x2 x3 x5 x6 7 xi 0 i 1 2 6 以x1作为换入基 x4作为换出基有 x1x2x3x4x5 0 3 20 3 M 10 x4 0211 13 x1 131005 x1x2x3x4x5x6 1 M1 4M 2 M0 M0 x4 31 11005 x6 1 410 117 x1x2x3x4x5x6 以x3为换入变量 x6为换出变量 得 所以原问题最优解为x 3 0 4 最优值为z 5 3 minz 2x1 3x2 x3 x 1 4x2 2x3 8 s t 3x1 2x2 6 x1 x2 x3 0 解 引入剩余变量x4 x5和人工变量x6 x7 利用两阶段法得到辅助线性规划 maxw x6 x7 123 maxz 2x 3x x s t 3x1 2x2 x5 x7 6 xi 0 i 1 2 7 构造初始单纯形表 并计算 x 1 4x2 2x3 x4 x6 8 0 2 13M 33 4M 5 33 1 M 3 M0 x1 1 1 3 1 3 1 3 00 5 3 x6 0 13 3 4 3 1 3 11 16 3 x1x2x3x4x5x6 0 19 4M 4 0 1 12 5 4 5 4M 4 x1 1 5 6 0 1 4 1 3 3 x3 0 13 4 1 1 4 3 4 3 4 4 以x2为换入变量 x6为换出变量 得 以x1为换入变量 x7为换出变量 得 从单纯行表中可知 原问题有无限多个最优解 其中一个为x 0 8 1 8 0 最优值为 z 7 4 maxz 10 x1 15x2 12x3 x1x2x3x4x5x6x7 z 2 3 10000 w462 1 100 x6 142 10108 x7 3200 1016 x1x2x3x4x5x6x7 z 5 4 0 1 2 3 4 0 3 4 0 w 5 2 0 1 1 2 1 3 2 0 x21 4 1 1 2 1 4 0 1 4 02 x75 2 0 1 1 2 1 1 2 12 x1x2x3x4x5 z 000 1 2 1 2 x2 010 6 0 30 11 8 x1 10 0 40 2 0 40 8 x 2x 1 x2 x3 5 5x 6x 15x 15 5x 1 3x2 x3 9 s t 0 j 1 2 3 j 123 解 引入松弛变量x4 x5 剩余变量x6 人工变量x7 将原问题化为规范式 maxz 10 x1 15x2 12x3 Mx7 5x 1 3x2 x3 x4 9 x 2x 1 x2 x3 x6 x7 5 5x 6x 15x x 15 s t 0 j 1 2 7 j 1235 构造初始单纯形表并计算得 以x1为换入变量 x4为换出变量 得 以x1为换入变量 x4为换出变量 x1x2x3x4x5x6x7 z 10 2M15 M12 M00 M0 x4 53110009 x5 5615010015 x7 21100 115 x1x2x3x4x5x6x7 进一步计算知道 x7 0 所以原问题没有可行解 1 4设目标函数极大化的线性规划问题的单纯形表如下 表中无人工变量 当待定常数 a1 a2 b1 c1 c2为何值时 表中的解 1 为唯一最优解 2 为多重解 3 有无界解 4 为退化解 解 当b1 0 c1 c2 0 为唯一最优解 当b1 0 c1 0 c2 0或c1 0 c2 0 为多重解 当b1 0 a2 0 c1 0 c2 0 具有无界解 b1 0 c1 0或a2 0 c2 0 为退化的可行解 1 5 某商店要制定某种商品第二季度的计划 已知该商店仓库容纳此种商品的容量不超过 600 件 3 月底已存货 200 件 以后每月初进货一次 假定各月份此种商品买进售出的单价 如下 问各月进货 售货各多少件才能使利润最大 假设进货时受到仓库容量的限制 售货 z 09 M 5 10 3M 5 2 2M 5 0 M0 x1 10 60 20 20001 8 x5 0916110024 x7 0 0 20 6 0 40 111 4 x1x2x3x4x5x6 c1 0 c2 900 z0 x2a1 1 a2 1007 x5 10 50103 x6 40 2101 b1 时受到进货量的限制 不考虑货物存放在仓库的耗损与保管费用 解 设xi表示每个月进货量 yi表示相应月份售货量 其中i 1 2 3 则有数学模型 maxz 18y1 18y2 19y3 17x1 16 5x2 17x3 x 1 600 200 x y x y x y 200 x 1 y1 x2 y2 200 11223 s t x1 y1 200 xi yi 0 i 1 2 3 x y x y x 600 200 112 x y x 600 200 112233 经计算 当x1 400 y1 600 x2 500 y2 600 x3 600 y3 600时 即四月份进货 400 件 售货 600 件 五月份进货 500 件 售货 600 件 六月份进货 600 件售货 600 件时 最大利润为 6100 元 1 6 设市场上可买到 n 种不同的食品 第 j 种食品的单位售价为c j 每种食品含有 m种基本 营养成分 第 j 种食品每一个单位含第 i 种营养成分为aij 每人每天对第 i 种营养成分的需 要量不少于bi 试确定在保持营养成分要求条件下的最经济食谱 解 设没人每天需要第 j 种食品的数量为xj j 1 2 n 建立数学模型为 n minz cjxj j 1 月份买进单价 元 件 售出单价 元 件 41718 516 518 61719 xj 0 j 1 2 n aijxj bi i 1 2 m s t j 1 n 1 7A B 两种产品都需要经过前 后两道工序加工 每一个单位产品 A 需要前道工序 1h 和后道工序 2h 每一个位产品 B 需要前道工序 2h 和后道工序 3h 可利用的前道工序有 11h 后道工序有 17h 没加工一个单位产品 B 的同时 会产生 2 个单位的副产品 C 并且不需要 任何费用 产品 C 一部分可出售盈利 其余的只能加以销毁 出售单位产品 A B C 的利润 分别为 3 元 7 元 2 元 每单位产品 C 的销毁费为 1 元 预测表明 产品 C 最多只能出 售 13 个单位 试建立总利润最大的生产计划数学模型 解 设x1 x2分别为产品 A B 的产量 x3为副产品 C 的销售量 x4为副产品 C 的销毁量 于是有x3 x4 2x2 z 为总利润 则数学模型如下 maxz 3x1 7x2 2x3 x4 x 1 2x2 11 x3 13 s t 2x2 x3 x4 0 x1 x2 x3 x4 0 2x 3x 17 12 习题二 2 1 写出下列线性规划问题的对偶问题 1 minz 10 x1 5x2 x3 x 1 2x2 4x3 10 x x 1 x2 7 132 123 x 6x 5x 2 s t 0 x自由变量 解 原问题的对偶问题为 maxw 10y1 2y2 y3 7y4 y 1 y2 10 4y1 5y2 1 y1 0 y2 y3 y4 0 2 maxz x1 2x2 3x3 4x4 x 1 5x2 x3 2x4 6 2y 6y y y 5 s t 1234 x x x 0 x自由变量 4x1 2x2 3x3 x4 5 123 2x x x 5x 13 s t 4 1234 解 原问题的对偶问题是 minw 6y1 13y2 5y3 y 1 2y2 4y3 1 2y1 5y2 y3 4 s t 2 y1 y2 3y3 3 y1无约束 y2 0 y3 0 5y y 2y 2 123 2 2 证明下列线性规划为题为最优解 minz x1 2x2 2x3 s t x x 1 x2 7 12 123 x 2x 3x 2 2x 1 x2 2x3 3 0 x自由变量 3 证明 原问题的对偶问题为 maxw 3y1 2y2 2y 1 y2 1 2y1 3y2 2 y2 0 y1无约束 易知该对偶问题无可行解 由定理知则原问题无最优解 12 y 2y 2 s t 2 3对线性规划问题 minz 4x1 6x2 18x3 x 1 3x3 3 s t x2 2x3 5 x1 x2 x3 0 1 写出该线性规划问题的对偶问题 2 已知对偶为题的最优解为 2 6 试用互补松弛定理求其原问题的最优解 解 1 原问题的对偶问题为 maxw 3y1 5y2 3y12y2 18 y1 y2 0 2 根据互不松弛定理有 yA c x 0 则 y y 1 4 s t 6 2 1 3 5 2 6 0 2 3 x 1 x2 x3 0 10 3 有 13 x2 2x3 5 又因为y b cx有 x 3x 6 2 6 3 5 18 4 x x x3 12 即 2x1 3x2 9x3 18 x 1 0 联立 解得 x 3 即原问题的最优解为 0 3 1 x3 1 2 2 4对线性规划问题 maxz 2x1 x2 5x3 6x4 2x 1 x3 x4 8 s t 2x1 3x2 x3 2x4 12 x1 x2 x3 x4 0 1 写出该线性规划问题的对偶问题 2 已知原问题的最优解为 0 0 4 4 试用互补松弛定理求对偶问题的最优解 解 1 原问题的对偶问题为 minz 8y1 12y2 2y 1 2y2 2 y 1 2y2 6 s t y1 y2 5 y1 0 y2无约束 3y 1 2 2 利用互补松弛定理有 y A c x 0 0 有 2 1 5 6 0 4 4 0 2 3 12 2 0 1 1 y1 y2 有 y1 2y2 6 y2 1 12 y y 5 即 1 y 4 所以对偶问题的最优解为 4 1 2 5用对偶单纯形法求解下列线性规划问题 1 minz 2x1 4x2 5x3 x 1 x2 3x3 1 s t x1 x2 6 x1 x2 x3 0 解 利用对偶单纯形 添加松弛变量x4 x5 原问题化为规范式 123 maxz 2x 4x 5x s t x1 x2 x5 6 x1 x2 x3 x4 x5 0 x 1 x2 3x3 x4 1 则有对偶单纯形表 以x2为换入量 x5为换出量有 x1x2x3x4x5 2 4 500 x4 1 1310 1 x5 1 1001 6 x1x2x3x4x5 60 50 4 x4 2031 15 x2 1100 16 由表可知 原问题的最优解为 0 6 0 2 maxz x1 x2 2x3 x 1 5x2 3x3 4 x1 2x2 3x3 7 x x x 0 123 2x x 6x 10 s t 123 解 利用对偶单纯形 添加松弛变量x4 x5 x6 原问题化为规范式 123 maxz x x 2x x 0 i 1 2 3 4 5 6 x1 2x2 3x3 x6 7 i 2x x 6x x 10 x 1 5x2 3x3 x4 4 s t 1235 则有单纯形表 以x3为换入量 x5换出得 以x2为换入量 x4为换出量有 x1x2x3x4x5x6 1 1 2000 x4 1 531004 x5 2 1 6010 10 x6 1 230017 x1x2x3x4x5x6 1 3 2 300 1 30 x4 0 11 2011 20 1 x3 1 31 610 1 605 3 x6 0 5 2001 212 由表知原问题无最优解 2 6设有线性规划 minz 2x1 x2 x3 3x 1 x2 x3 60 x x x 0 x1 x2 x3 20 123 12 x x 2x 10 s t 3 求出最优解 并进行以下分析 1 c2在什么范围内变动而不影响最优解 2 b3从 20 变为 16 求最优解 3 x3的系数变为 1 3 1 其价值系数从 1 变为 5 试问最优解是否会发生变化 4 增加约束条件2x1 x2 x5 31 最优解有何变化 解 引入松弛变量x4 x5 x6 将原问题化为规范行 123 maxz 2x x x x 0 i 1 2 6 x1 x2 x3 x6 20 i 12 x x 2x x 10 3x 1 x2 x3 x4 60 s t 35 x1x2x3x4x5x6 1 3002 3 3 110 x2 010 2 11 1 1102 11 x3 1 3011 33 5 33054 33 x6 000 5 113 11127 11 x1x2x3x4x5x6 列单纯形表有 以x1为换入变量 x5为换出变量有 以x2为换入变量 x6为换出变量有 所以原问题的最优解为 15 5 0 10 0 0 1 因为x2是基变量 由书中 2 6 式有max 1 1 min 3 1 3 22 2 222 1 7 7 3 所以 1 c 7 时 最优解不变 即 2 c 4 所以当 4 c 2 2时 原问题最优 333 22 解不变 2 1 1000 x4 31110060 x5 1 1201010 x6 11 100120 x1x2x3x4x5x6 01 50 20 x4 04 51 3030 x1 1 1201010 x6 02 30 1110 x1x2x3x4x5x6 00 7 20 3 2 1 2 x4 0011 1 210 x1 101 201 21 215 x2 01 3 20 1 21 25 2 b B b 0 0 1 2 0 2 1 1 2 1 2 1 2 0 8 4 2 1 2 1 所以 5 23 b b b 15 2 13 8 18 10 此时原问题的最优解为 13 3 0 18 0 0 3 3 c3 cBB p3 1 2 1 1 0 0 所以原问题的最优解变 1 21 2 3 2 0 1 2 1 2 1 2 1 1 1 1 4 添加松弛变量x7 在原最终单纯形表中添加一行一列并计算有 以x3为换入量 x7为换出量有 x1x2x3x4x5x6x7 00 7 20 3 2 1 2 x4 0011 1 2010 x1 101 201 21 2015 x2 01 3 20 1 21 205 x7 00109 32 8 x1x2x3x4x5x6x7 000063 2 1213 2 x4 0001 101 218 x1 1000 42 119 x2 010013 43 7 以x6为换入量 x3为换出量有 得最优解为 41 3 11 3 0 46 3 0 8 3 0 最优值为 71 3 2 7某厂生产A1 A2 A3三种产品 需要B1 B2 B3三种设备加工 需要单位各种产品所需 要的设备台时 设备的现有加工能力及每件产品的预期利润如下表所示 1 求获利最大的产品生产计划 2 每件产品A3的利润增加到多大时 才值得安排生产 如果每件产品A3的利润增加到 50 6 求最优计划的变化 3 产品A1的利润在多大范围变化时原最优计划保持不变 4 如设备B1的能力为100 10 确定保持最优基不变的 的变化范围 5 如有一种新产品 加工一件需要设备B1 B2 B3的台时各为 1h 4h 3h 预期每件的利润 为 8 元 是否值得安排生产 台 h A1A2A3设备能力 B1 111100 B2 1045600 B3 226300 单位产品利润1064 x3 00109 32 8 x1x2x3x4x5x6x7 00 40 9 20 13 2 x4 001 31 701 346 3 x1 10 2 30201 341 3 x2 01 4 30101 311 3 x6 00 1 30 31 2 38 3 a 如合同规定该厂至少生产 10 件 产品A3 试确定最优计划的变化 解 设计划生产产品A1 A2 A3各x1 x2 x3件 则有 maxz 10 x1 6x2 4x3 x 1 x2 x3 100 2x1 2x2 6x3 300 x x x 0 123 1 构造单纯形表如下 10 x 4x 5x 600 s t 123 以x1为换入量 x5为换出量有 以x2为换入量 x4为换出量有 x1x2x3x4x5x6 1064000 x4 111100100 x5 1045010600 x6 226001300 x1x2x3x4x5x6 02 10 10 600 x4 03 51 21 1 10040 x1 12 51 201 10060 x6 06 550 1 51180 x1x2x3x4x5x6 得最优生产计划 即x 100 3 200 3 0 0 0 100 为最优解 获利 2200 3 元 2 由 于x3 为 非 基 变 量 则 只 有 0 才 值 得 生 产 即 c 即 c 8 3 即c 20 3时A 才值得生产 而当c 50 6 20 3 此时最优 3333 解发生变化 根据计算 当c 50 6时 5 3 0时 此时将x 作为换入变量 x 作 336 为换出变量 得 此时生产最优计划为 175 6 275 6 25 0 0 0 3 由于x1的生产量为基变量 则有max 4 min 1 61 6 8 3 2 3 5 即 2 3 10 3 c1 4 5 时 原最优生产计划保持不变 得c1 6 15 4 若矩阵 B p1 p2 p3 4 2 1 2 1 100 其逆矩阵B 2 3 2 1 0 5 3 1 1 6 1 60 为使最优基不发生 0 1 0 改变 根据 2 7 有 b 40 50 2 3 2 max 200 3 b min 100 3 100 5 3 1 1 即 4 5 时 最优基不发生改变 00 8 3 10 3 2 30 2200 3 x2 015 65 3 1 60200 3 x1 101 6 2 31 60100 3 x6 004 201100 x1x2x3x4x5x6 000 5 2 2 3 5 12 2325 3 x2 01025 12 1 6 5 24275 6 x1 100 7 121 6 1 24175 6 x3 001 1 201 425 5 经计算 0 1 1 1 B 1p7 c B 1p 6 10 0 0 6 1 B7 知 c c B 1P 8 6 2 0 则此时最优解发生变化 且该产品值得生产 77B7 6 原最优解不满足新的约束条件 x3 10 即 x3 10 引入松弛变量x7 在原最 终单纯形表中增加一行或一列有 将x7做为换出变量 x3作为换入变量 利用对偶单纯形有 得到此时最优生产计划x 95 3 175 3 10 0 0 60 2 8对所有 t 值 讨论以下参数线性规划问题最优解的变化范围 x1x2x3x4x5x6x7 00 8 3 10 3 2 300 2200 3 x2 015 65 3 1 600200 3 x1 101 6 2 31 600100 3 x6 004 2010100 x7 00 10001 10 x1x2x3x4x5x6x7 000 10 3 2 30 8 3 22120 3 x2 0105 3 1 605 6175 3 x1 100 2 31 601 695 3 x6 000 201460 x7 000100 110 maxz 7 2t x 1 12 t x2 10 t x3 x 1 x2 x3 20 s t 2x1 2x2 x3 30 x1 x2 x3 0 t 0 解 将上述问题转化为标准型有 maxz 7 2t x 1 12 t x2 10 t x3 x 1 x2 x3 x4 20 s t 2x1 2x2 x3 x5 30 x1 x2 x3 x4 x5 0 t 0 令 t 0 用单纯法求解如下 将 t 的变化直接反应到最终的单纯形表中 cj 7121000 CBXBbx1x2x3x4x5 0 x4 201111020 0 x5 302210115 z07121000 0 x4 5001 21 1 210 12 x2 15111 201 230 z 180 5040 6 10 x3 100012 1 12 x2 10110 11 z 220 500 8 2 cj 7 2t12 t10 t00 CBXBbx1x2x3x4x5 10 t x3 100012 15 12 t x2 10110 11 T 开始增大 当 t 8 3 时 首先出现 4 0 故当0 t 8 时 得最优解 0 10 10 0 3 目标函数的最优值为maxz 220 0 t 8 t 8 为第一临界点 33 0 x4作为换入变量 由 规则确定x3为换出变量 用单纯形法进行 当8 t 5时 3 迭代 4 由表可知 t 继续增大 当 t 5 时首先出现 1 0 故当 t 5时 得最优解 0 15 0 5 3 8 目标函数的最优值为 180 15t t 5 为第二临界点 当 t 5 时 1 0 x1作为换入变量 由 规则确定x2为换出变量 用单纯形法进行迭 代 由表知当 t 继续增大时 所有检验数都非正 所以当 t 5 时 得最优解 15 0 0 5 目标函数的最优值为 105 30t 2 9考虑下列问题 maxz 3x1 x2 x 1 x2 4 s t 2x1 x2 4 x1 x2 0 z 220T 5003t 8 2 2t cj 7 2t12 t10 t00 CBXBbx1x2x3x4x5 0 x4 5001 21 1 2 12 t x2 15111 201 215 z 180 15tT 504 3t 20 6 t 2 cj 7 2t12 t10 t00 CBXBbx1x2x3x4x5 0 x4 5001 21 1 2 7 2t x1 15111 201 2 z 105 30t05 t13 2 2t0 7 2 t 1 用单纯形方法求出最优解 2 将约束右端b 改变为 t t 0 对 t 的所有值求出问题的最优解 4 4 4 1 4 2 解 1 引入松弛变量x3 x4 把原问题化为标准形 maxz 3x1 x2 x 1 x2 x3 4 s t 2x1 x2 x4 4 建立初始单纯形表 x1 x2 x3 x4 0 以x1为换入变量 x4为换出变量 有 以x2为换入变量 x3为换出变量有 所以 原问题的最优解为 8 3 4 3 2t 2 b B b 1 3 将其加在最终单纯表中有 t 3 5t 3 1 3 2 3 1 3 t 1 x1x2x3x4 3100 x3 11104 x4 2 1014 x1x2x3x4 05 20 3 2 x3 011 1 22 x1 1 1 201 22 x1x2x3x4 00 5 3 2 3 x2 012 3 1 34 3 x1 101 31 38 3 由表可知当0 t 4 问题的最优解为 8 3 t 3 4 3 5t 3 5 当t 4 时 利用对偶单纯形有 5 由表可知当时 问题的最优解为 4 2t 0 当 t 2 时 原问题无解 x1x2x3x4 00 5 3 2 3 x2 012 3 1 34 3 5t 3 x1 101 31 38 3 t 3 x1x2x3x4 0 2 3 2 3 x4 0 3 215t 4 x1 11104 2t 习题三 3 1 用割平面法求解下列整数线性规划 1 minz 2x1 x2 x1 3x2 1 s t x1 x2 4 x1 x2 0且为整数 解 增加松弛变量x3 x4 将其化为标准形为 x1 3x2 x3 1 minw 2x1 x2 s t x1 x2 x4 4 x1 x2 x3 x4 0且为整数 形表如下 先不考虑整数条件 则对应线性规划单纯 以x4为换出基 x2为换入基 进一步得单纯形表 所以 原线性规划问题的最优解为x 0 4 是整数解所以也是原整数规划的整数解 2 maxz 12x1 9x2 2x 1 x2 10 3x1 2x2 3 x1 x2 0且为整数 解 增加松弛变量x3 x4 x5 将其化为标准形为 x 5x 6 s t 12 x1x2x3x4 w 2100 x3 1 3101 x4 11014 x1x2x3x4 w 300 1 x3 401313 x2 11014 maxz 12x1 9x2 s t 3x 1 2x2 x5 3 x1 x2 x3 x4 x5 0且为整数 x1 5x2 x4 6 2x1 x2 x3 10 先不考虑整数条件 则对应线性规划单纯形表如下 以x2作为换入变量 x4为换出变量得 所以线性规划的最优解为 0 6 5 44 5 0 27 5 分量 44 5 取整后分数最大 考虑单纯形表中该分量所对应的行约束11x x 55 1 x 44 则有割 5 413 平面方程 4 1x 4 x 0 增加松弛变量x 化为等式约束 555 146 555 1 x 4 x x 4 并加入上面最后的单纯形表中有 146 x1x2x3x4x5 z 129000 x3 2110010 x4 150106 x5 3 20013 x1x2x3x4x5 z 51 500 9 50 x3 11 501 1 5044 5 x2 1 5101 506 5 x5 13 5002 5127 5 x1x2x3x4x5x6 z 51 500 9 500 利用对偶单纯形法有 由表可知最优解为 0 1 最优值为 9 3 2用分支定界法求解下列整数线性规划问题 1 maxz x1 5x2 3x 1 4x2 11 s t 7x1 6x2 42 x1 x2 0且为整数 解 先不考虑x1 x2为整数的约束条件 求的相应线性规划问题的最优解为x 0 11 4 0 目标函数的最优值为z 0 55 4 由于x 0 2 3 4 构造两个线性规划子问题如下 1 maxz x1 5x2 x3 11 501 1 50044 5 x2 1 5101 5006 5 x5 13 5002 51127 5 x6 1 500 4 501 4 5 x1x2x3x4x5x6 z 203 200000 9 4 x3 43 200100 1 49 x2 4 2510001 41 x5 5 200011 25 x6 1 40010 5 41 1 x2 2 x1 x2 0且为整数 和maxz x1 5x2 7x1 6x2 42 3x 1 4x2 11 s t 2 x2 3 x1 x2 0且为整数 先不考虑整数的约束条件 求解 1 所对应的线性规划子问题得到最优解x1 1 2 最优 值为z1 11 2 所对应的线性规划子问题没可行解 故原整数规划的最优解为x1 1 2 最优值为z1 11 7x1 6x2 42 3x 1 4x2 11 s t 2 minz 3x1 2x2 x 1 2x2 7 s t 4x1 x2 9 x1 x2 0且为整数 3 3求解下列 0 1 规划问题 1 maxz 2x1 x2 3x3 5x4 x 1 3x2 x3 x4 1 x x 1 x2 x3 x4 3 x s t 0或1 j 1 2 3 4 2x 2 j 23 解 利用隐枚举法 显然 0 1 1 0 是原问题的一个解 增加约束条件 2x1 x2 3x3 5x4 4 则有表 由表可知 原问题的最优解为 0 1 1 0 最大值是 4 2 minz x1 x2 x3 x 1 x2 x3 2 x x 1 7x2 x3 0 4x x 2x 3 s t 0或1 j 1 2 3 j 123 解 显然 1 0 1 是原问题的一个解 增加约束条件 x1 x2 x3 1 建立下表 由表可知 原问题的最优解为 1 0 0 最优值为 1 点条件满足条件 是 否 Z 值 0 0 0 0 0 0 0 0 1 5 3 0 0 1 0 312 1 0 0 1 1 2 0 1 0 0 1 0 1 0 1 4 0 1 1 0 4 220 4 0 1 1 1 1 1 0 0 0 2 1 0 0 1 7 1 0 1 0 1 1 0 1 1 4 1 1 0 0 1 1 1 0 1 6 1 1 1 0 2 1 1 1 1 3 点条件满足条件 是 否 Z 值 0 0 0 0 0 1 0 111 7 0 1 1 0 1 0 0 1 141 1 1 0 1 2 1 1 0 005 6 1 1 1 1 17 5 4 1已知某运输问题的产销需求和单位运 价如下表 求解运输最少的方案和总运价 4 2某百货公司去外地采购 A B C D4 种规 格的服装 数量如下 A 为 1500 套 B 为 2000 套 C 为 3000 套 D 为 3500 套 有三个城 市可供应上述规格服装 各城市供应数量如 下 1 为 2500 套 II 为 2500 套 III 为 500 套 由于这些城市的服装质量 运价和销售 情况不同预计售出的利润也不同如下表所 示 请帮该公司确定一个预期盈利最大的采 购方案 4 3 甲乙 丙三个城市每年分别需要煤炭 320 万吨 250 万吨 350 万吨 由 A B 两处煤 矿负责供应 已知煤炭年供应量 A 为 400 万吨 B 为 450 万吨 由煤矿至各城市的单 位运价如下表 由于需大于供 经研究平衡 决定 甲城市供应量可减少 0 30 万吨 乙 城市需要量应全部满足 丙城市供应量不少 于 270 万吨 试用付格尔法求出初始调运方 案 4 4求解下列最小值的指派问题 1 c 1 33 683 1122 6 5 811 10 3 5 2 384152 33445921 30475625 314553 27 22 20 c 25 20 26 4 5 求解下列最大值的指派问题 96 15 14 10 20 1 c 1813 13 19 16 81226 9 65 10 4 85 2 c 710912 6 15716 9 868 17 10 产地销地 B1B2B3B4产量 A1 59315 A2 13418 A3 82617 销售181216 城市规格 ABCD I10567 II8276 III9348 甲乙丙 A151822 B212516 习题五 5 1利用最优性条件求解 min f x 1 x3 1 x3 x2 x 1221 33 f x f x 解 x2 1 x2 2x 由 f x 0得驻点 122 x1 x2 x 1 1 0 x 2 1 2 x 3 1 0 x 4 1 2 又 f 2 x 2x 1 02x2 2 0 得驻点处 的 Hesse 矩阵 2 f x 1 2 0 2 f x 2 2 0 2 0 2 0 2f x 3 0 2 0 2 2 f x 4 2 0 02 根据定理 5 8 知 局部最优解为 x 1 2 5 2试判断下列非线性规划是否为凸规划 1 min f x x2 x2 8 12 x 1 x2 0 s t x x2 2 12 x1 x2 0 解 由于等式约束 x x2 2不是线性函数 则有定义知原规划不是凸规划 12 2 min f x x1 x2 x3 x1x2 222 x 2 x2 4 12 s t 5x2 x 10 13 x1 x2 x3 0 解 同理由于5x2 x 10不是线性函数 则有定义知原规划不是凸规划 13 5 3分别利用二分法 Newton 法 试探法 黄金分割法 Fibonacci 方法在区间 0 3 上求 解如下问题 1 min f x x3 6x2 3x 7 2 min f x x3 2x2 x 5 解 1 f x 3x2 12x 3 f x 6x 12 为了计算简单 取精度 0 05 二分法 取初值 x0 1 5 计算过程如下 由表可知 b6 a6 0 046875 0 05 所以此时 x 2 9765625 Newton 切线法 取初值 x0 2 25 计算过程如下 此时 f x5 0 0455203 0 05 达到精度要求 可得 x 4 2394583 但所求的 x 并不在 0 3 区 间内 试探法 取初值 x0 2 25 计算过程如下 由表可知 k 13 时 达到精度要求 所以 x 4 2000000 也不在 0 3 区间 根据高等数学的 相关知识 该问题在此区间是单调函数 另外 Newton 切线法和试探法在计算中并没有利用 区间的相关信息 所以这两种方法此时是不适用的 kakbkxkf ak f xk bk ak 00 00000003 00000001 5000000 3 0000000 12 00000003 0000000 11 50000003 00000002 2500000 14 2500000 12 00000001 5000000 22 25000003 00000002 6250000 14 8125000 12 00000000 7500000 32 62500003 00000002 8125000 13 8281250 12 00000000 3750000 42 81250003 00000002 9062500 13 0195313 12 00000000 1875000 52 90625003 00000002 9531250 12 5361328 12 00000000 0937500 62 95312503 00000002 9765625 12 2746582 12 00000000 0468750 kxkf xk f xk 02 2500000 14 81250001 5000000 112 1250000292 546875060 7500000 27 309413669 569617731 8564815 35 125568614 307536918 7534115 44 36263881 746185714 1758326 54 23945830 045520313 4367497 64 23607050 000034413 4164233 kxkf xk h 02 2500000 18 73437500 200 12 4500000 21 65887500 400 22 8500000 27 13587500 800 33 6500000 35 25787501 600 45 2500000 29 4218750 0 800 52 8500000 27 13587500 400 64 0500000 37 13487500 800 74 8500000 34 6008750 0 400 83 6500000 35 25787500 200 94 2500000 37 35937500 400 104 6500000 36 1403750 0 200 114 0500000 37 13487500 100 124 3500000 37 2721250 0 050 134 2000000 37 35200000 025 144 2750000 37 3504531 黄金分割法 得到此时 x a9 b9 2 2 9802763 Fibonacci 法 因为精度 0 05 Fn b a 60 所以取 n 10 计算结果如下 此时 x a10 b10 2 2 9791667 2 为了计算简单 取精度 0 05 f x 3x2 4x 1 f x 6x 4 二分法 取 x0 0 5 这是经过反复计算确定的 计算中发现初值的选择对后面的计算影 响很大 易知 x 0 3281250 但是根据高等数学先关知识 发现改点为 f x 的一个极大值点 故此 算法在这里不适用或需重新选择初值 Newton 切线法 取初值 x0 2 25 计算过程如下 kakbk xk1xk2 f xk1 f xk2 bk ak 00 00000003 00000001 14600001 8540000 2 8128359 12 81311213 0000000 11 14600003 00000001 85422802 2917720 12 8165176 19 35174121 8540000 21 85422803 00000002 29191292 5623151 19 3538187 23 25692341 1457720 32 29191293 00000002 56240222 7295107 23 2581469 25 55442560 7080871 42 56240223 00000002 72956452 8328376 25 5551469 26 91489290 4375978 52 72956453 00000002 83287092 8966937 26 9153225 27 72940980 2704355 62 83287093 00000002 89671422 9361567 27 7296685 28 22191250 1671291 72 89671423 00000002 93616942 9605448 28 2220696 28 52192920 1032858 82 93616943 00000002 96055272 9756167 28 5220252 28 70563130 0638306 92 96055273 00000002 97562162 9849311 28 7056902 28 81849570 0394473 kakbk xk1xk2 f xk1 f xk2 bk ak 10 00000003 00000001 14583331 8541667 2 8107006 12 81560153 0000000 21 14583333 00000001 85416672 2916667 12 8156015 19 35018811 8541667 31 85416673 00000002 29166672 5625000 19 3501881 23 25952151 1458333 42 29166673 00000002 56250002 7291667 23 2595215 25 54981370 7083333 52 56250003 00000002 72916672 8333333 25 5498137 26 92129630 4375000 62 72916673 00000002 83333332 8958333 26 9212963 27 71857820 2708333 72 83333333 00000002 89583332 9375000 27 7185782 28 23852540 1666667 82 89583333