运筹学(第二版)课后答案.pdf

附录四习题参考答案 附录四 习题参考答案附录四 习题参考答案 第一章第一章 线性规划及单纯形法线性规划及单纯形法 1 1 1 解 第一 求可行解集合 令两个约束条件为等式 得到两条直线 在第一 象限划出满足两个不等式的区域 其交集就是可行集或称为可行域 如图 1 1 所示 交集为 1 2 0 第二 绘制目标函数图形 将目标函数的系数组成一个坐标点 6 4 过原点 O 作一条矢量指向点 6 4 矢量的长度不限 矢量的斜率保持 4 比 6 再作一条与矢量垂直的直线 这条直线就是目标函数图形 目标函 数图形的位置任意 如果通过原点则目标函数值 Z 0 如图 1 2 所示 第三 求最优解 图 1 2 的矢量方向是目标函数增加的方向或称梯度方 向 在求最小值时将目标函数图形沿梯度方向的反方向平行移动 在求最 大值时将目标函数图形沿梯度方向平行移动 直到可行域的边界 停止移 动 其交点对应的坐标就是最优解 如图 1 3 所示 最优解 x 1 2 0 目标函数的最小值 Z 3 X2 2x1 x2 1 3x1 4x2 1 5 O 1 2 X1 图 1 1 1 X2 2x1 x2 1 3x1 4x2 1 5 6 4 O 1 2 X1 图 1 1 2 附录四习题参考答案 2 无可行解 求解方法与 1 类似 3 无界解 4 无可行解 5 无穷多最优解 z 66 6 唯一最优解 z 92 3 x1 20 3 x2 3 8 1 2 1 解 由题目可知 其系数矩阵为 即 54321 PPPPP 1 0 0 2 3 0 1 0 2 0 0 0 1 0 1 因 321 PPP 0 2 3 0 2 0 1 0 1 线性独立 故有 521 42 31 1823 122 4 xxx xx xx 令非基变量0 54 xx得 1823 122 4 21 2 31 xx x xx 2 6 4 3 2 1 x x x 得到一个基可行解 T x 00262 1 36 1 Z X2 2x1 x2 1 3x1 4x2 1 5 6 4 O 1 2 X1 图 1 1 3 附录四习题参考答案 431 PPP 0 0 3 1 0 0 0 1 1 线性独立 故有 521 24 31 2183 212 4 xxx xx xx 令非基变量0 52 xx得 183 12 4 1 4 31 x x xx 2 12 6 3 4 1 x x x 得到一个基本解 但非可行解 T x 0 12 2 0 6 2 18 2 Z 同理可以求出 543 PPP 1 0 0 0 1 0 0 0 1 得基本可行解 T x 18 12 4 0 0 3 541 PPP 1 0 3 0 1 0 0 0 1 得基本可行解 T x 6 12 0 0 4 4 421 PPP 0 2 3 1 2 0 0 0 1 得基本可行解 T x 0 6 0 3 4 5 532 PPP 1 0 2 0 0 2 0 1 0 得基本可行解 T x 6 0 4 6 0 6 521 PPP 1 2 3 0 2 0 0 0 1 得基本非可行解 T x 6 0 0 6 4 7 432 PPP 0 0 2 1 0 2 0 1 0 得基本非可行解 T x 0 6 4 9 0 8 1 2 答案如下表所示 其中打三角符号的是基本可行解 打星 号的为最优解 附录四习题参考答案 x1 x2 x3 x4 x5 z x1 x2 x3 x4 x5 0 0 4 12 18 0 0 0 0 3 5 4 0 0 12 6 12 3 0 0 0 5 6 0 2 12 0 18 0 0 1 0 3 4 3 0 6 0 27 9 2 0 5 2 0 0 0 6 4 0 6 30 0 5 2 0 3 0 2 6 2 0 0 36 0 3 2 1 0 0 4 6 0 0 6 42 3 5 2 0 0 0 0 9 4 6 0 45 0 0 5 2 9 2 0 1 3 1 解 单纯形法 首先 将问题化为标准型 加松弛变量 x3 x4 得 0 825 943 510max 421 321 21 j x xxx xxx st xxz 其次 列出初始单纯形表 计算最优值 CB XB 10 5 0 0 b X1 X2 X3 X4 0 X3 3 4 1 0 9 0 X4 5 2 0 1 8 j 10 5 0 0 0 X3 0 14 5 1 3 5 21 5 10 X1 1 2 5 0 1 5 8 5 j 0 1 0 2 5 X2 1 1 5 14 3 14 3 2 10 X1 0 0 1 7 2 7 1 j 0 0 5 14 25 14 表一 由单纯形表一得最优解为 2 35 2 3 1 zx T 图解法 附录四习题参考答案 X2 4 5X1 2X2 8 第一步 相当于原点 0 0 3X1 4X2 9 9 4 1 3 2 O 8 5 3 x1 图 1 3 1 X2 4 5X1 2X2 8 第二步 相当于点 8 5 0 3X1 4X2 9 9 4 1 3 2 O 8 5 3 x1 图 1 3 2 附录四习题参考答案 2 略 1 4 1 解 大 M 法 首先将数学模型化为标准形式 5 1 0 5 42 1823 54max 321 521 4321 321 jx xxx xxx xxxx st xxxz j 式中 x4 x5为松弛变量 x5可作为一个基变量 第一 三约束分别加 入人工变量 x6 x7 目标函数中加入 Mx6 Mx7一项 得到大 M 单纯形法数 学模型 7 1 0 5 42 1823 54max 7321 521 64321 321 jx xxxx xxx xxxxx st xxxz j 由单纯形表计算 X2 4 5X1 2X2 8 第三步 相当于点 1 3 2 3X1 4X2 9 9 4 1 3 2 O 8 5 3 x1 图 1 3 3 附录四习题参考答案 CB XB 4 5 1 0 0 M M b X1 X2 X3 X4 X5 X6 X7 M X6 3 2 1 1 0 1 0 18 0 X5 2 1 0 0 1 0 0 4 M X7 1 1 1 0 0 0 1 5 j 4 4M 5 3M 1 M 0 0 0 M X6 1 0 1 1 2 1 0 10 5 X2 2 1 0 0 1 0 0 4 M X7 1 0 1 0 0 0 1 1 j 4 2M 0 1 M 2M 0 0 1 X3 1 0 1 1 2 0 10 0 X2 2 1 0 0 1 0 4 M X7 2 0 0 1 2 1 11 j 5 2M 0 0 1 M 2 2M 0 表 1 4 1 1 在迭代过程中 人工变量一旦出基后不会在进基 所以当人工变量 X6 出基后 对应第六列的系数可以不再计算 以减少计算量 当用大 M 单纯形法计算得到最优解并且存在人工变量大于零时 则表 明原线性规划无可行解 两阶段单纯形法 首先 化标准形同大 M 法 第一 三约束分别加入人工变量 x6 x7后 构造第一阶段问题 7 1 0 5 42 1823 min 7321 521 64321 76 jx xxxx xxx xxxxx st xxw j 用单纯形法求解 得到第一阶段问题的计算表 1 4 1 2 CB XB 0 0 0 0 0 1 1 b X1 X2 X3 X4 X5 X6 X7 1 X6 3 2 1 1 0 1 0 18 0 X5 2 1 0 0 1 0 0 4 1 X7 1 1 1 0 0 0 1 5 j 4 3 0 1 0 0 0 附录四习题参考答案 1 X6 0 1 2 1 1 3 2 1 0 12 0 X1 1 1 2 0 0 1 2 0 0 2 1 X7 0 1 2 1 0 1 2 0 1 3 j 0 1 0 1 2 0 0 1 X6 1 0 1 1 2 1 0 10 0 X2 2 1 0 0 2 0 0 4 1 X7 1 0 1 0 1 0 1 1 j 2 0 0 1 3 0 0 表 1 4 1 2 在第一阶段的最优解中人工变量不为零 则原问题无可行解 注 在第二阶段计算时 初始表中的检验数不能引用第一阶段最优表的检 验数 必须换成原问题的检验数 2 无穷多最优解 如 X1 4 0 0 X2 0 0 8 3 无界解 4 唯一最优解 X 5 2 5 2 5 2 0 5 唯一最优解 X 24 33 6 唯一最优解 X 14 0 4 1 5 1 X 仍为最优解 max z CX 2 除 C 为常数向量外 一般 X 不再是该问题的最优解 3 最优解变为 X 目标函数值不变 1 6 1 d 0 c1 0 c2 0 2 d 0 c1 0 c2 0 但c1 c2中至少一个为零 3 d 0 或d 0 而c1 0且d 4 3 a2 4 c1 0 d 4 3 a2 5 c2 0 a1 0 6 x5 为人工变量 且c1 0 c2 0 1 7 解 设 xj表示第 j 年生产出来分配用于作战的战斗机数 yj为第 j 年已 培训出来的驾驶员 aj xj 为第 j 年用于培训驾驶员的战斗机数 zj为第 j 年用于培训驾驶员的战斗机总数 则模型为 max z nx1 n 1 x2 2xn 1 xn s t zj zj 1 aj xj yj yj 1 k aj xj x1 x2 xj yj xj yj zj 0 j 1 2 n 1 8 附录四习题参考答案 提示 设出每个管道上的实际流量 则发点发出的流量等于收点收到 的流量 中间点则流入等于流出 再考虑容量限制条件即可 目标函数为 发出流量最大 设 xij 从点 i 到点 j 的流量 max z x12 x13 st x12 x23 x24 x25 x13 x23 x34 x35 x24 x34 x54 x46 x25 x35 x54 x56 以上为流量平衡条件 x12 x13 x46 x56 始点 收点 x12 10 x13 6 x23 4 x24 5 x25 3 x34 5 x35 8 x46 11 x54 3 x56 7 xij 0 对所有i j 1 9 提示 设每个区段上班的人数分别为 x1 x2 x6 即可 1 10 解 设男生中挖坑 栽树 浇水的人数分别为 x11 x12 x13 女生 中挖坑 栽树 浇水的人数分别为 x21 x22 x23 S 为植树棵树 由题意 模型为 max S 20 x11 10 x21 s t x11 x12 x13 30 x21 x22 x23 20 20 x11 10 x21 30 x12 20 x22 25 x13 15 x23 Xij 0 i 1 2 j 1 2 3 1 11 解 设各生产 x1 x2 x3 max z 1 2 x1 1 175x2 0 7x3 s t 0 6x1 0 15x2 2000 0 2x1 0 25x2 0 5x3 2500 0 2x1 0 6x2 0 5x3 1200 x1 x2 x3 0 1 12 解 设 7 12 月各月初进货数量为 xi件 而各月售货数量为 yi件 i 1 2 6 S 为总收入 则问题的模型为 max S 29y1 24y2 26y3 28y4 22y5 25y6 28x1 24x2 25x3 27x4 23x5 23x6 st y1 200 x1 500 y2 200 x1 y1 x2 500 y3 200 x1 y1 x2 y2 x3 500 y4 200 x1 y1 x2 y2 x3 y3 x4 500 y5 200 x1 y1 x2 y2 x3 y3 x4 y4 x5 500 y2 200 x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 500 附录四习题参考答案 xi 0 yi 0 i 1 2 6 整数 1 13 解 用 x1 x2 x3分别代表大豆 玉米 麦子的种植面积 hm2 公顷 x4 x5分别代表奶牛和鸡的饲养数 x6 x7分别代表秋冬和春夏季多余的 劳动力 人日 则有 鸡舍限制 牛栏限制 劳动力限制 资金限制 土地限制 71 0 3000 32 40003 0504017550 3500 6 0100103520 15000 3400 100 5 1 1 28 12400120300175max 5 4 754321 654321 54 4321 7654321 jx x x xxxxxx xxxxxx xx xxxx st xxxxxxxz j 第二章第二章 对偶理论和灵敏度分析对偶理论和灵敏度分析 2 1 对偶问题为 1 0 22 1 104 2010min 21 21 21 21 21 yy yy yy yy st yys 2 无约束 321 31 321 21 321 321 0 0 1 33 1 22 45min yyy yy yyy yy yyy st yyys 3 无约束 321 321 321 321 31 321 0 0 1 3733 232 32 253min yyy yyy yyy yyy yy st yyys 4 无约束 321 321 321 321 321 0 0 7103 665 55 52015max yyy yyy yyy yyy st yyys 附录四习题参考答案 2 2 1 因为对偶变量 Y CBB 1 第 k 个约束条件乘上 0 即 B 1的 k 列将为变化前的 1 由此对偶问题变化后的解 y 1 y 2 y k y m y1 y2 1 yk ym 2 与前类似 y r r kr r y bb b y i yi i r 3 y i yi i 1 2 m 4 yi i 1 2 m 不变 2 3 1 对偶问题为 无约束 3421 321 432 21 421 4321 0 6 3 62 83 2263max yyyy yyy yyy yy yyy st yyyys 2 由互补松弛性 0 Xys Xys分别为松弛变量和最优 解 可得0 765 yyy 从而可知 3 62 83 432 21 421 yyy yy yyy 又由对偶性质的最优性 bYCX 可得 202263 4321 yyyy 四方程联立即可求得对偶问题的最优解 Y 2 2 1 0 2 4 解 其对偶问题为 min w 8y1 12y2 附录四习题参考答案 2y1 2y2 2 1 2y2 1 2 y1 y2 5 3 y1 2y2 6 4 y1 y2 0 将 y1 y2 代入约束条件 得 1 与 2 为严格不等式 由互 补松弛性 YsX 0 得 x1 x2 0 又因为 y1 y2 0 由互补松弛性 Y Xs 0 得 Xs1 Xs2 0 即 原问题约束条件应取等号 故 x3 x4 8 解之得 x3 4 x3 2x4 12 x4 4 所以原问题最优解为 X 0 0 4 4 T 目标函数最优值为 Z 44 2 5 1 略 2 原问题的解 互补的对偶问题的解 第一步 0 0 0 60 40 80 0 0 0 2 4 3 第二步 0 15 0 0 25 35 1 0 0 1 0 1 第三步 0 20 3 50 3 0 0 80 3 5 6 2 3 0 11 6 0 0 3 对偶问题的解 对偶问题互补的对偶问题的解 第一步 0 0 0 2 4 3 0 0 0 60 40 80 第二步 1 0 0 1 0 1 0 15 0 0 25 35 第三步 5 6 2 3 0 11 6 0 0 0 20 3 50 3 0 0 80 3 4 比较 2 和 3 计算结果发现 对偶单纯形法实质上是将单 纯形法应用于对偶问题的求解 又对偶问题的对偶即原问题 因此两者计 算结果完全相同 2 6 1 15 4 c1 50 4 5 c2 40 3 2 24 5 b1 16 9 2 b2 15 3 X 8 5 0 21 5 0 4 X 11 3 0 0 2 3 2 8 1 a 40 b 50 c x2 d x1 e 22 5 f 80 g s 440 2 最大值 3 2 a b 90 a 2 b 80 2 9 1 x1 x2 x3 代表原稿纸 日记本和练习本月产量 建模求解最终单 纯形表如下 x1 x2 x3 x4 x5 x2 2000 0 1 7 3 1 10 10 附录四习题参考答案 x1 1000 1 0 4 3 1 10 40 cj zj 0 0 10 3 1 10 50 2 临时工影子价格高于市场价格 故应招收 招 200 人最合适 2 10 1 s 13x1 2x1 1 0 3x1 2 0 16x2 4x2 1 0 2x2 2 0 5x1 8x2 max z 5x1 8x2 s t 2x1 4x2 160 3x1 2x2 180 x1 x2 0 X 50 15 max z 370元 2 影子价格 A 7 4 B 1 2 3 CBB 1p c3 11 0 CB 73 4 18 25 4 b 160 a 180 B 1 b 3 8 a 15 50 a 4 0 得到 40 a 200 a 200 增加利润350元 X1 X2 X3 X4 X2 15 3 8 a 0 1 3 8 1 4 X1 50 a 4 1 0 1 4 1 2 s 370 7a 4 0 0 7 4 1 2 第三章第三章 运输问题运输问题 3 1 解 表 3 1 1 B1 B2 B3 B4 供应量 A1 10 6 7 12 4 A2 16 10 5 9 9 A3 5 4 10 10 5 需要量 5 3 4 6 18 西北角法是优先从运价表的西北角的变量赋值 当行或列分配完毕 后 再在表中余下部分的西北角赋值 以此类推 直到右下角元素分配完 毕 表 3 1 1 西北角元素是 x11 x11 min a1 b1 min 4 5 4 将 4 填 在 C11的左侧 表示 A1供应 4 单位给 B2 同时将第一行划去 表示 A1的 产量全部运出 得表 3 1 2 在表 3 1 2 中 西北角元素是 x21 x21 min 9 5 4 1 同时降第一列划去 表示 B1已满足需要 得到表 3 1 3 依次向 附录四习题参考答案 右下角安排运量 结果如表 3 1 4 所示 表 3 1 2 B1 B2 B3 B4 供应量 A1 4 10 6 7 12 4 A2 16 10 5 9 9 A3 5 4 10 10 5 需要量 5 3 4 6 18 表 3 1 3 B1 B2 B3 B4 供应量 A1 4 10 6 7 12 4 A2 1 16 10 5 9 9 A3 5 4 10 10 5 需要量 5 3 4 6 18 表 3 1 4 B1 B2 B3 B4 供应量 A1 4 10 6 7 12 4 A2 1 16 3 10 4 5 1 9 9 A3 5 4 10 5 10 5 需要量 5 3 4 6 18 最小元素法的思想是就近优先运送 即最小运价 cij对应的变量 xij优先 赋值 xij min ai bj 然后在剩下的运价中取最小运价对应的变量赋值并 满足约束 依次下去 直到最后得到一个初始基本可行解 表 3 1 1 中最小元素是 C32 令 x32 min a3 b2 min 5 3 3 同 时将第二列划去 得到表 3 1 5 在表 3 1 5 中 最小元素为 C23 C31 任 意选取其一 这里选 C31 令 x31 min 5 3 5 2 同时将第三行划去 得表 3 1 6 依次进行下去 其结果见表 3 1 7 表 3 1 5 B1 B2 B3 B4 供应量 A1 10 6 7 12 4 A2 16 10 5 9 9 A3 5 3 4 10 10 5 需要量 5 3 4 6 18 表 3 1 6 B1 B2 B3 B4 供应量 A1 10 6 7 12 4 A2 16 10 5 9 9 附录四习题参考答案 A3 5 3 4 10 10 5 需要量 5 3 4 6 18 表 3 1 7 B1 B2 B3 B4 供应量 A1 3 10 6 7 1 12 4 A2 16 10 4 5 5 9 9 A3 2 5 3 4 10 10 5 需要量 5 3 4 6 18 伏格尔法是最小元素法的改进 考虑到产地到销地的最小运价和此小 运价之间的差额 如果差额很大 就选最小运价处险调运 否则会增加总 运费 在表 3 1 1 中求行差额 3 2 1 i i 和列差额 4 1 j j 计算公式为 行最小运价行次小运价ii i 列最小运价列次小运价jj j 同时满足约束 和 这时所以先调运 价使最大 第一列的最小运即 131331 311 A55 5min min c 51 2 2 5 1 4 1max max Bbax ji 若同时将第三行与第一列划去 最后即变量个数比小于 3 4 1 6 个 因而 应再 x32 x33 x34和 x11 x12中任意选一个变量作为即变量 运量为零 这里 选 x11 如表 3 1 8 所示 求第二个基变量仍然是求差额 因为第三行和第一列已满足 所以只求 u1 u2和 v2 v3 v4即可 结果见表 3 1 9 此时 有两个最大差额 u2 v2 任选一个即可 这里选 v2 第二列最小运价为 c12 故 x12 min 4 3 3 同 时将第二列划去 这样依次下去 其结果见表 3 1 10 表 3 1 8 B1 B2 B3 B4 供应量 ui A1 0 10 6 7 12 4 1 A2 16 10 5 9 9 4 A3 5 5 4 10 10 5 1 需要量 5 3 4 6 18 vj 5 2 2 1 表 3 1 9 B1 B2 B3 B4 供应量 ui 附录四习题参考答案 A1 0 10 6 7 12 4 1 A2 16 10 5 9 9 4 A3 5 5 4 10 10 5 需要量 5 3 4 6 18 vj 4 2 3 表 3 1 10 B1 B2 B3 B4 供应量 A1 0 10 3 6 1 7 12 4 A2 16 10 3 5 6 9 9 A3 5 5 4 10 10 5 需要量 5 3 4 6 18 3 4 1 B1 B2 B3 B4 供应量 A1 8 6 7 0 5 8 8 A2 4 5 4 10 5 8 9 A3 2 6 9 1 7 3 7 需要量 8 6 5 5 24 2 B1 B2 B3 B4 供应量 A1 8 6 7 2 5 8 8 2 A2 4 5 4 10 5 8 9 A3 2 6 9 1 7 3 7 需要量 8 6 5 2 5 24 3 5 甲 乙 丙 丁 可供量 A 500 500 1000 B 1500 500 2000 C 500 1500 2000 销售量 1500 1500 1500 500 3 6 存贮能力大 即产大于销 虚拟一个销地 所需存取时间为 0 文件 数为 100 最优解为 x11 200 x21 100 x31 0 x32 100 x33 100 x34 100 最 优值为 200 5 100 2 8 100 8 4 100 6 2 14000 3 7 附录四习题参考答案 解 用伏格尔法初始解 28 5 29 6 34 7 35 4 128 2 赵 钱 张 王 周 仰 泳 37 7 32 9 33 8 37 0 35 4 1 蛙 泳 43 4 33 1 42 2 34 7 1 41 8 蝶 泳 33 3 0 28 5 1 38 9 30 4 33 6 自由泳 29 2 0 26 4 29 6 1 28 5 31 1 泳 0 1 0 0 0 0 0 赵 钱 张 王 周 仰 泳 37 7 32 9 33 8 2 37 0 35 4 1 蛙 泳 43 4 33 1 42 2 34 7 1 41 8 蝶 泳 33 3 0 28 5 1 38 9 30 4 33 6 自由泳 29 2 0 26 4 29 6 1 28 5 31 1 泳 0 1 0 0 0 0 0 赵 钱 张 王 周 仰 泳 37 7 32 9 33 8 1 37 0 35 4 0 蛙 泳 43 4 33 1 42 2 34 7 1 41 8 蝶 泳 33 3 0 28 5 1 38 9 30 4 33 6 自由泳 29 2 1 26 4 29 6 0 28 5 31 1 泳 0 0 0 0 0 0 1 赵 钱 张 王 周 仰 泳 37 7 32 9 33 8 37 0 35 4 蛙 泳 43 4 33 1 42 2 34 7 41 8 蝶 泳 33 3 28 5 38 9 30 4 33 6 自由泳 29 2 26 4 29 6 28 5 31 1 最优解 29 2 28 5 33 8 34 7 126 2 3 8 1 a 5 b 5 c 5 d 6 e 15 最优解略 2 c31 8 3 9 数学模型为 min z m i n j ijijx c 11 附录四习题参考答案 s t n j ij x 1 ai i 1 2 m m i ij x 1 bj j 1 2 n xij 0 上面第一个约束条件可以改写为 n j ij x 1 ai 则对偶问题为 max z n j jjv b 1 m i iiu a 1 s t vj ui cij i 1 2 m j 1 2 n ui vj 0 对偶变量 ui的经济意义为在 i 产地单位物资的价格 vj的经济意义为 在 j 销地单位物资的价格 对偶问题的经济意义为 如该公司欲自己将该 种物资运至各地销售 其差价不能超过两地之间的运价 否则买主将在 i 地购买自己运至 j 地 在此条件下 希望获利为最大 3 10 用 xj 表示每期 半年一期 的新购数 yij表示第 i 期更换下来送去修 理用于第 j 期的发动机数 显然当 j i 1 时 应一律送慢修 cij为相应的 修理费 每期的需要数 bj 为已知 而每期的供应量分别由新购与大修送回 来的满足 如第 1 期拆卸下来的发动机送去快修的可用于第 2 期需要 送 去慢修的可用于第 3 期及以后各期的需要 因此每期更换下来的发动机数 也相当于供应量 由此列出这个问题用运输问题求解时的产销平衡表与单 位运价表为 1 2 3 4 5 6 库存 供应量 新 购 10 10 10 10 10 10 0 660 第 1 期送修的 M 2 1 1 1 1 0 100 第 2 期送修的 M M 2 1 1 1 0 70 第 3 期送修的 M M M 2 1 1 0 80 第 4 期送修的 M M M M 2 1 0 120 第 5 期送修的 M M M M M 2 0 150 需 求 量 100 70 80 120 150 140 520 3 11 附录四习题参考答案 解 转运问题 最优解如下表 甲 乙 A B C 产 量 甲 1000 500 1500 乙 900 300 300 1500 A 1000 1000 B 1000 1000 C 100 900 1000 销 量 1000 1000 1300 1300 1400 第四章第四章 目标规划目标规划 4 1 分别用图解法和单纯形法求解下述目标规划问题 1 满意解为 X1 50 3 0 X2 88 9 62 9 间线段 2 满意解为 X 4 6 4 2 1 满意解 X 0 35 d 1 20 d 3 115 d 4 95 其余 d i d i 0 2 满意解 X 0 220 3 d 1 20 d 2 5 3 d 4 400 3 其 余 d i d i 0 3 满意解 X 0 35 d 1 20 d 3 115 d 4 95 d 5 27 其余 d i d i 0 4 满意解不变 4 3 设安排商业节目 x1 小时 新闻 x2 小时 音乐 x3 小时 模型为 min z p1 d 1 d 2 d 3 p2d 4 s t x1 x2 x3 d 1 12 x1 d 2 2 4 x2 d 3 1 250 x1 40 x2 17 5x3 d 4 d 4 600 x1 x2 x3 d 1 d 2 d 3 d 4 d 4 0 4 4 略 4 5 设 A B 型机的产量分别为 x1 x2台 模型为 附录四习题参考答案 5 1 0 0 7023 15064 15 10 10450300 min 21 5521 4421 332 221 4 1121 544332211 iddxx ddxx ddxx ddx ddx ddxx st dddPddPdPz ii 第五章第五章 整数规划整数规划 5 1 解 令 y 1 当 x2 x3 1 时 0 否则 故有 x2x3 y 又 x12 x33分别与 x1 x3等价 因此原模型可转换为 max z x1 y x3 st 2x1 3x2 x3 3 y x2 y x3 x2 x3 y 1 xj 0或1 j 1 2 3 y 0 或 1 5 2 min z 10 1j jjx c s t 10 1j j x 5 x1 x8 1 x3 x5 1 x7 x8 1 x4 x5 1 x5 x6 x7 x8 2 xj 1 选择钻探sj井位 0 否则 5 3 1 最优解 x1 2 x2 2 或 x1 3 x2 1 z 4 2 最优解 x1 4 x2 2 z 14 5 4 附录四习题参考答案 1 最优解 x1 4 x2 3 z 55 2 最优解 x1 2 x2 1 z 13 5 5 最优解 x1 x2 1 x3 x4 x5 0 z 5 5 6 最优解 1 0 1 和 0 1 1 Z 5 5 7 最优解为 x13 x22 x34 x41 1 最优值为 48 5 8 虚拟一人戊 完成各项工作时间取甲乙丙丁中最小者 构造下表 人 任务 A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 戊 24 27 26 20 32 最优分配方案 甲 B 乙 D 和 C 丙 E 丁 A 总计需要 131 小时 5 9 此问题是一个非平衡的纸牌问题 通过虚设一泳姿 而设运动员 的游泳成绩为零 化为平衡指派问题 5 10 解 设 xij 1 商贩从 i 直接去 j 0 否则 整数规划模型为 min z n i 1 n j 1 dijxij s t n i 1 xij 1 j 1 2 n n j 1 xij 1 i 1 2 n ui uj n xij n 1 ui 为连续变量 i 1 2 n 也可取整数值 i j 1 2 n i j 5 11 附录四习题参考答案 解 设 xij表示第 i 种产品在 j 机床上开始加工的时刻 模型为 min z max x13 t13 x23 t23 x33 t33 s t xij tij ti j 1 i 1 2 3 j 1 2 加工顺序约束 xij tij xi 1 j M i xi 1 j ti 1 j xij M 1 i 互斥性约束 i 1 2 j 1 2 3 i 0或1 xij 0 第六章第六章 非线性规划非线性规划 6 1 f X 2 221 2 1 21 2 xxxx xx 2 221 2 1 21 2 xxxx xx H X 22 221 2 1 1 xxxx 2 221 2 1 2 221 2 1 2 221 2 1 2 221 2 1 224 422 xxxxxxxx xxxxxxxx 6 2 在 0 3 1 0 1 1 2 1 1 2 3 1 各点二次型 不定 只有在 1 2 0 点二次型正定 故该点为极小点 6 3 为凸规划 6 4 f x 为严格凹函数 因 0 08 Fn 1 12 5 查表得 n 6 则 t1 b0 6 5 F F a0 b0 25 8 13 0 25 9 6154 t1 a0 6 5 F F b0 a0 0 8 13 25 0 15 3846 f t1 68 6715 f t1 376 7504 故取 a1 0 b1 15 3846 t2 9 6154 t2 b1 F4 F5 a1 b1 5 7692 因 f t2 25 7624 f t2 故取 a2 0 b2 9 6154 t3 5 7692 t3 b2 F3 F4 a2 b2 3 8462 因 f t3 39 698 f t3 故取 a3 0 b3 5 7692 t4 3 8462 t4 b3 F2 F3 a3 b3 1 9231 附录四习题参考答案 因 f t4 31 444 f t5 故取 a5 3 85 b5 5 7692 因 f t5 0 xi 0 i 1 2 n 然后利用动态规划来求解 令最优值函数为 f k y yxx k 1 max x1x2 xk xi 0 i 1 2 k 其中 y 0 因而 证明该不等式只需证明 f n a a n n 再用归纳 法证明之 附录四习题参考答案 7 4 用 xki表示从产地 i 分配给销地 k k 1 n 的物资的总数 则采用 逆推法时 动态规划的基本方程为 f k xk1 xkm ik x min m i ikik xh 1 f k 1 xk1 x1k xkm xmk 式中 0 xik xki m i ik x 1 bk k 1 2 n f n 1 0 并且有 x1i ai i 1 2 m 7 5 最优方案是每年均投资于 A 三年后的最大利润为 440 万元 7 7 最佳产量为 x1 110 x2 110 5 x3 109 5 总最低费用36321元 7 8 最优解有三个 1 x1 1 x2 3 x3 1 x4 0 2 x1 2 x2 1 x3 2 x4 0 3 x1 0 x2 5 x3 0 x4 0 最大价值为20千元 7 9 把往 4 个仓库派巡逻队划分成 4 个阶段 状态变量 sk为 k 阶段初拥有 的未派出的巡逻队 决策变量 uk为 k 阶段派出的巡逻