运筹学练习题.pdf

第一章第一章 线性规划线性规划 1 已知我系有三种不同体系的建筑应予以修建 其耗用资源数量及可用的资源数量如下表 问不同体系的建 筑面积各为多少 才能使提供的建筑面积达到最大 造价 元 m2 钢材 kg m2 水泥 kg m2 砖块 块 m2 人工 工 日 m2 砖混结构105121102104 5 钢混结构137301903 0 框架结构122251803 5 资源限量11000 万元2000 万 kg15000 万 kg14700 万块400 万工日 解 设三种不同体系建筑面积依次为 1 x 2 x 3 x万 m2 则 123 maxZxxx 123 123 123 1 123 123 10513712211000 1230252000 11019018015000 210147000 4 53 03 5400 0 xxx xxx xxx x xxx x x x 其中 1 x 2 x 3 x为决策变量 2 把下列线性规划问题化为标准型 123 min23Zxxx 123 123 123 123 29 324 3236 0 0 xxx xxx xxx xxx 无约束 解 令ZZ 11 xx 333 xxx 3 0 x 3 0 x 则问题转化为 123345 max23300Zxxxxxx 12334 12335 1233 123345 29 3224 32336 0 xxxxx xxxxx xxxx xx xxx x 3 3 3 3 求下列求下列 LpLpLpLp 问题的所有基解 基可行解 最优解问题的所有基解 基可行解 最优解 12 max23Zxx 12 1 2 12 2212 416 515 0 0 xx x x xx 解 化为标准型 12345 max23000Zxxxxx 123 14 25 2212 416 515 0 1 2 5 j xxx xx xx xj 系数矩阵 22100 40010 05001 A 1 取 1123 221 400 050 Bp pp 则 145 01 10 01 Npp 1123 T B Xx x x 则 145 T N Xx x 当 145 0 0 TT N Xx x 时 1 1 1 112 3 221124 400163 050152 B x XB bx x 1 43200 T X 2 取 2124 220 401 050 Bp pp 则 235 10 00 01 Npp 2124 T B Xx x x 则 235 T N Xx x 当 235 0 0 TT N Xx x 时 1 1 1 222 4 220123 401163 050154 B x XBbx x 2 33040 T X 3 取 3125 220 400 051 Bp pp 则 334 10 01 00 Npp 3125 T B Xx x x 则 334 T N Xx x 当 334 0 0 TT N Xx x 时 1 1 1 332 5 220124 400162 051155 B x XBbx x 3 42005 T X 4 取 4135 210 400 001 Bp pp 则 424 20 01 50 Npp 4135 T B Xx x x 则 424 T N Xx x 当 424 0 0 TT N Xx x 时 1 1 1 443 5 210124 400164 0011515 B x XBbx x 3 404015 T X 5 取 5145 200 410 001 Bp pp 则 523 21 00 50 Npp 5145 T B Xx x x 则 523 T N Xx x 当 523 0 0 TT N Xx x 时 1 1 1 554 5 200126 410168 0011515 B x XBbx x 5 6 0 0 8 15 T X 6 取 6234 210 001 500 Bppp 则 615 20 40 01 Np p 6234 T B Xx x x 则 615 T N Xx x 当 615 0 0 TT N Xx x 时 1 2 1 663 4 210123 001166 5001516 B x XBbx x 6 036160 T X 7 取 7245 200 010 501 Bppp 则 713 21 40 00 Np p 7245 T B Xx x x 则 713 T N Xx x 当 713 0 0 TT N Xx x 时 1 2 1 774 5 200126 0101616 5011515 B x XBbx x 7 0 6 0 16 15 T X 8 取 8345 100 010 001 Bppp 则 812 22 40 05 Np p 8345 T B Xx x x 则 812 T N Xx x 当 812 0 0 TT N Xx x 时 3 1 884 5 12 16 15 B x XBbIbx x 8 00121615 T X 基 基解 是否可行解目标函数值 1 x 2 x 3 x 4 x 5 x 1 p 2 p 3 p43 200否17 1 p 2 p 4 p33040是15 1 p 2 p 5 p42005是14 1 p 3 p 5 p404015是8 1 p 4 p 5 p600 815否12 2 p 3 p 4 p036160是9 2 p 4 p 5 p06016 15否18 3 p 4 p 5 p00121615是0 4 4 4 4 求下列求下列 LpLpLpLp 问题的所有基解 基可行解 最优解问题的所有基解 基可行解 最优解 1234 min5232Zxxxx 1234 1234 1234 2347 2223 0 xxxx xxxx x x x x 解 系数矩阵 1234 2212 A 1 取 112 12 22 Bp p 则 134 34 12 Npp 112 T B Xx x 则 134 T N Xx x 当 134 0 0 TT N Xx x 时 1 11 11 2 4 127 11 223 2 B x XB b x 1 11 400 2 T X 2 取 213 13 21 Bp p 则 224 24 22 Npp 213 T B Xx x 则 224 T N Xx x 当 224 0 0 TT N Xx x 时 1 11 22 3 1372 5 21311 5 B x XBb x 2 2 5011 50 T X 3 取 314 14 22 Bp p 则 323 23 22 Npp 314 T B Xx x 则 323 T N Xx x 当 323 0 0 TT N Xx x 时 1 11 33 4 1471 3 22311 6 B x XBb x 3 1 30011 6 T X 4 取 423 23 21 Bpp 则 414 14 22 Np p 423 T B Xx x 则 414 T N Xx x 当 414 0 0 TT N Xx x 时 1 21 44 3 2371 2 2132 B x XBb x 3 01 220 T X 5 取 524 24 22 Bpp 则 513 13 21 Np p 524 T B Xx x 则 513 T N Xx x 当 513 0 0 TT N Xx x 时 1 21 55 4 2471 2 2032 B x XBb x 5 01 202 T X 6 取 634 34 12 Bpp 则 612 12 22 Np p 634 T B Xx x 则 612 T N Xx x 当 612 0 0 TT N Xx x 时 1 31 66 4 3471 1231 B x XBb x 6 0010 T X 基 基解 是否可行解目标函数值 1 x 2 x 3 x 4 x 1 p 2 p 411 200否 31 1 p 3 p2 5011 50是43 5 1 p 4 p 1 30011 6否2 2 p 3 p01 220是5 2 p 4 p0 1 202否5 3 p 4 p0011是5 此时 Lp 问题的最优值 Z 5 图解法 图解法 1 用图解法求解下列线性规划问题 12 max23Zxx 12 1 2 12 2212 416 515 0 0 xx x x xx 24 8 2 4 6 8 10 10 12 2212xx 1 416x 2 515x 21 2 33 Z xx 6 1 绘制可行区域图形 2 将等值线 21 2 33 Z xx 沿法线方向向右上方平移到离原点最远且在可行域内的点 12 2 2212 515 xx x 1 2 3 3 x x 最优解 3 3 TX 最优值 Z 15 2 用图解法求解下列线性规划问题 12 max23Zxx 12 12 12 466 424 0 0 xx xx xx 12 1 2 12 424xx P Q 所以 为无界解 2 若求 12 min23Zxx 则等值线 21 2 33 Z xx 与可行域交于一条线段 PQ 所以有无穷多最优解 最优值3Z 3 用图解法求解下列线性规划问题 12 maxZxx 12 12 12 24 2 0 0 xx xx xx 21 2 33 Z xx 12 466xx 24 8 2 4 6 8 10 10 12 2xx 6 存在无界解 4 用图解法求解下列线性规划问题 12 max32Zxx 12 12 12 22 3412 0 0 xx xx xx 解 12 1 3 12 3412xx 12 22xx 2 4 34 所以 无可行解 单纯形法单纯形法 1 用单纯形法求解下列线性规划问题 12345 max23000Zxxxxx 12 24xx 21 xxZ 21 3 22 Z xx 123 14 25 2212 416 515 0 1 2 5 j xxx xx xx xj 解 0345 100 010 001 BP P P 0 345 T B Xx x x 0 0 0 0 B C 令 0 12 0 0 TT N Xx x 则 0 B X 1 B b Ib 12 16 15 T 0 0Z 单纯形表为 j c23000 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 3 x122210012 2 0 0 4 x 5 x 16 15 4 0 0 5 0 0 1 0 0 1 15 5 j 23000 1 0Z 0 3 x6 2 010 2 56 2 0 3 4 x 2 x 16 3 4 0 0 1 0 0 1 0 0 1 5 16 4 j 2000 3 5 2 9Z 2 1 x3101 20 1 5 0 3 4 x 2 x 4 3 0 0 0 1 2 0 1 0 4 5 1 5 j 00 10 1 5 15Z 最优解为 3 3 0 4 0 T X 最优值 15Z 大大 MMMM 法 单纯形法的扩展法 单纯形法的扩展 2 单纯形法求解线性规划问题 13 max3Zxx 123 123 23 123 4 21 39 0 xxx xxx xx x xx 化为标准型 1345 max300Zxxxx 1234 1235 23 4 21 39 0 1 2 5 j xxxx xxxx xx xj 11110 21101 03100 A 加入人工变量得 134567 max300ZxxxxMxMx 1234 12356 237 4 21 39 0 1 2 7 j xxxx xxxxx xxx xj j c 30100M M B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x411110004 M M 6 x 7 x 1 9 2 0 1 3 1 1 0 0 1 0 1 0 0 1 1 3 j 2M 34M10 M 00 0 10MZ 0 4 x3302 11 101 0 M 2 x 7 x 1 6 2 6 1 0 1 4 0 0 1 3 1 3 0 1 1 j 6M 304M 103M 4M0 1 6MZ 0 4 x0000 1 1 2 1 2 1 2 0 3 2 x 1 x 3 1 0 1 1 0 1 3 2 3 0 0 0 1 2 0 1 2 1 3 1 6 9 3 2 j 00303 2 M 3 2 M 1 2 2 3Z 0 4 x0000 1 1 2 1 2 1 2 0 2 x5 2 1 210 0 1 4 1 41 4 1 3 x3 23 201 03 4 3 41 4 j 3 2000 3 4 M 3 4 M 1 4 3 2Z 两阶段法 单纯形法的扩展两阶段法 单纯形法的扩展 3 单纯形法求解线性规划问题 13 max3Zxx 123 123 23 123 4 21 39 0 xxx xxx xx x xx 解 第一阶段 67 maxxx 1234 12356 237 4 21 39 0 1 2 7 j xxxx xxxxx xxx xj j c00000 1 1 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x411110004 1 6 x1 2 1 10 1101 1 7 x903100013 j 2400 1 00 0 10 0 4 x3302 11 101 0 2 x1 21 10 110 1 7 x6 6 0403 311 j 60403 40 1 6 0 4 x00001 1 21 2 1 2 0 2 x3011 30001 39 0 1 x110 2 3 01 2 1 21 63 2 j 00000 1 1 2 0 最优解为 1 3 0 0 0 0 0 T X 最优值 0 注 若0 说明原式存在可行解 0 说明原式不存在可行解 第二阶段 将第一阶段的最终表中的人工变量 6 x 7 x除去 再从第一阶段最终表出发 继续用单纯形法计算 此时 目标函数 1345 max300Zxxxx j c 30100 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 4 x0000 1 1 2 0 3 2 x 1 x 3 1 0 1 1 0 1 3 2 3 0 0 0 1 2 9 3 2 j 00303 2 1 0Z 0 4 x0000 1 1 2 0 2 x5 2 1 210 0 1 4 1 3 x3 23 201 03 4 j 3 2000 3 4 3 2Z 最优解为 0 0 3 2 0 0 T X 最优值 3 2Z 4 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示 求表中各括 弧内未知数的值 j c322000 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 0 4 x b 111100 0 5 x15 a 12010 0 6 x202 c 1001 j 3 d 2000 0 4 x5 400 e h 1 4 1 4 3 1 x25 410 f 03 4 i 2 2 x5 201 g 0 j 1 2 j 0 k m 0 5 4 n 解 1h 2d 0k 1 2 j 11 41 410 03 41 01 21 220 ia 2a 1 4 i 11 41 410 03 41 410 01 21 21c 3c 11 41 45 4 03 41 41525 4 01 21 2205 2 b 10b 11 41 41 03 41 42 01 21 21 e f g 1 4 e 5 4 f 1 2 g 3 4 m 1 4 n 第二章第二章 对偶问题及灵敏度分析对偶问题及灵敏度分析 1 写出下列问题的对偶问题 1 123 max743Zxxx 123 123 23 123 42624 36415 5330 0 0 xxx xxx xx xxx 无约束 其对偶问题 3 min241530 12 y y y 12 123 123 123 437 2654 6433 0 0 yy yyy yyy yyy 无约束 2 1234 min235Zxxxx 1234 124 234 1234 35 224 6 0 0 xxxx xxx xxx xxxx 无约束 其对偶问题 3 max546 12 Z y y y 12 123 13 123 123 22 23 35 1 0 0 yy yyy yy yyy yyy 无约束 互补松弛性 互补松弛性 1 已知 LP 问题 12345 min23523xxxxx 12345 12345 234 233 01 2 5 j xxxxx xxxxx xj 已知其对偶问题的最优解为 1 4 5 y 2 3 5 y 5Z 试用对偶理论找出原问题的最优解 解 原问题的对偶问题为 12 max43Zyy 12 12 12 12 12 12 221 32 2353 24 335 0 0 yy yy yy yy yy yy 将 1 y 2 y的值代入约束条件 得 2 3 4 为严格不等式 由互补松弛性得 234 0 xxx 又 1 4 0 5 y 2 3 0 5 y 由互补松弛性得 15 15 34 23 xx xx 解得 1 5 1 1 x x 故原问题的最优解为 1 0 0 0 1 T X 最优值 5Z 2 已知 LP 问题 1234 max24Zxxxx 124 12 234 123 38 1 26 2 6 3 9 4 01 2 3 4 j xxx xx xxx xxx xj 要求 1 写出其对偶问题 2 已知其原问题的最优解为 2 2 4 0 T X 试根据对偶理论直接 求出对偶问题的最优解 解 原问题的对偶问题为 1234 min8669yyyy 124 1234 34 13 22 34 1 1 01 2 3 4 j yyy yyyy yy yy yj 将原问题的最优解代入约束条件 得 4 为严格不等式 由互补松弛性得 4 0y 又 1 20 x 2 20 x 3 40 x 由互补松弛性得 12 123 3 22 34 1 yy yyy y 解得 1 2 3 4 5 3 5 1 y y y 故对偶问题的最优解为 4 3 1 0 5 5 Y 最优值 16 对偶单纯形法对偶单纯形法 1 用对偶单纯形法求解下列线性规划问题 123 min121615xxx 12 13 123 242 253 0 0 0 xx xx xxx 解 令 则 12345 max12161500 xxxxx 124 135 242 253 0 1 2 5 j xxx xxx xj 124 135 242 253 0 1 2 5 j xxx xxx xj 单纯形表 j c 12 16 1500 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 4 x 2 2 4010 0 5 x 3 20 5 01 j 12 16 1500 0 4 x 2 2 4010 15 3 x3 52 5010 1 5 j 6 1600 3 12 1 x1120 1 20 15 3 x1 50 4 511 5 1 5 j 0 40 3 3 2 已知线性规划 12 min64Zxx 12 12 2 12 2 21 3 0 0 xx xx x xx 1 写出对偶问题并求解 2 直接写出原问题的最优解 解 1 写出对偶问题并求解 123 max23yyy 12345 max2300yyyyy 12 123 123 6 24 0 0 yy yyy yyy 0 124 1235 12345 6 24 0 yyy yyyy y yyyy j c2 1 300 B C B Yb 1 y 2 y 3 y 4 y 5 y 0 4 y6 1 10106 0 5 y4 12101 j 2 1 300 2 1 y611110 0 5 y1003111 j 0 3 5 20 最优解为 6 0 0 0 10 Y 2 原问题的最优解为 2 0 TX 灵敏度分析灵敏度分析 引例 引例 资源限量 设备 A h 2212h 设备 B h 4016h 设备 C h 0515h 该工厂每生产一件产品 可获利 2 元 每生产一件产品 可获利 3 元 问应如何安排计划使该工厂获利最 多 解 设 1 x 2 x分别为 两产品的数量 则 12 max23Zxx 12 1 2 12 2212 416 515 0 xx x x x x 化为标准型 1245 max2300Zxxxx 124 15 26 2212 416 515 0 1 2 6 j xxx xx xx xj j c23000 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 3 x12221006 0 4 x1640010 0 5 x150 5 0013 j 23000 0 3 x6 2 010 2 53 0 4 x16400104 3 2 x301001 5 j 2000 3 5 2 1 x3101 20 1 5 0 4 x400 214 5 3 2 x301001 5 j 00 10 1 5 一 一 分析分析 j C变化变化 1 若产品 的利润增至 3 元 件 产品 的利润降至 2 元 件 此公司最优生产计划如何变化 j c32000 B C B Xb 1 x 2 x 3 x 4 x 5 x 3 1 x3101 20 1 5 0 4 x400 21 4 5 5 2 2 x301001 515 j 00 3 201 5 0 3 x41001 4016 0 5 x500 5 2 5 4 14 2 2 x2011 2 1 40 j 00 3 21 20 0 3 x3101 20 1 5 0 4 x400 214 5 2 2 x301001 5 j 0000 2 5 即 此时生产 0 件产品 生产 3 件产品 2 若产品 的利润不变 则产品 的利润在什么范围内变化时 该公司的最优生产计划将不发生变化 解 设产品 的利润为 3 元 反映到最终单纯形表中得 j c23 000 B C B Xb 1 x 2 x 3 x 4 x 5 x 2 1 x3101 20 1 5 0 4 x400 214 5 3 2 x301001 5 j 00 10 1 5 5 为使表中的解仍为最优解 应有 1 5 50 解得 1 即产品 的利润的变化范围应满足 3 2 二 二 分析分析 i b变化变化 原问题资源限量设备 A 12 设备 B 16 设备 C 15 1 若设备 B 和设备 C 的每天能力不变 而设备 A 每天的能力增加到 16 分析公司最优生产计划的变化 解 12 16 15 b 4 0 0 b 则在对应最优单纯形表中 1 1 2024 4100 0050 bBb 1 201 54 214 50 001 50 2 8 0 得单纯形表 j c23000 B C B Xb 1 x 2 x 3 x 4 x 5 x 2 1 x5101 20 1 5 0 4 x 400 2 14 5 3 2 x301001 5 j 00 10 1 5 2 1 x41001 40 0 3 x2001 1 2 2 5 3 2 x301001 5 j 000 1 2 3 5 所以最优生产计划变为 此时生产 4 件产品 生产 3 件产品 2 若设备 A 和设备 B 每天可用生产能力不变 则设备 C 的可用生产能力在什么范围内变化时 问题的最优 基不变 解 设设备 C 每天可用生产能力为 15 因有 1 1 2020 4100 005 bBb 1 201 50 214 50 001 5 5 4 5 5 将其反映到最终单纯形表中 其 b 列数字为 3 5 44 5 3 5 b 当0b 时 问题最优基不变 解得 515 由此 设备 C 的生产能力应在 10 25 之间 三 三 增加一个变量增加一个变量 j x的分析的分析 例 该公司又推出一种新产品 生产一件产品 所需设备 A B C 分别为 2 4 5 该产品的预期盈利为 4 元 试分析该种产品是否值得投产 如果投产 最优解将如何变化 解 设该公司生产产品 6 x件 则有 6 4c 6 2 4 5 p 1 66 1 201 520 214 544 001 551 pB p 6 0 42 0 3410 1 值得投产 j c230004 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 2 1 x3101 20 1 50 0 4 x400 214 5 4 1 3 2 x301001 513 j 00 10 1 5 1 2 1 x3101 20 1 50 4 6 x100 1 21 41 51 3 2 x2011 2 1 400 j 00 1 2 1 4 2 50 故新的解为 3 2 0 0 0 1 T X 即生产产品 3 件 产品 2 件 产品 1 件 可获得的总利润 16Z 四 四 增加一个约束条件的分析增加一个约束条件的分析 例 2 若生产产品 要求增加功能 需增设设备 D 且已知生产产品 需用设备 D3 生产产品 需用设 备 D2 设备的生产能力 资源限量 为 14 试分析最优解的变化 解 12 3214xx 把 1 3x 2 3x 代入得3 3 2 2 15 不满足约束条件 126 3214xxx j c230000 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 2 1 x3101 20 1 50 0 4 x400 214 50 3 2 x301001 50 0 6 x14320001 j 00 10 1 50 通过线性变换 构造单位矩阵 即 4 4 3 1 2 3 j c230000 B C B Xb 1 x 2 x 3 x 6 x 5 x 6 x 2 1 x3101 20 1 50 0 4 x400 214 50 3 2 x301001 50 0 6 x 100 3 201 51 j 00 10 1 50 2 1 x8 31000 2 151 3 0 4 x16 300018 15 4 3 3 2 x301001 50 0 3 x2 30010 2 15 2 3 j 0000 1 3 2 3 增设设备 D 后 问题的最优解 8 3 3 2 3 16 3 0 0 T X 43 3Z 即生产产品 3 件 产品 3 件能使利润最大 最大利润为 15 第三章 运输问题 1 设有 1 A 2 A 3 A三个产地生产某种物质 其产量分别为 7t 4t 9t 1 B 2 B 3 B 4 B四个销地需要该 种物质 销量分别为 3t 6t 5t 6t 又知各产销地之间的单位运价见下表 试确定总运费最少的调运方案 表表 3 13 13 13 1单位运价表单位运价表单位 元单位 元 t t t t 销地 产地 1 B 2 B 3 B 4 B 1 A 311210 2 A 1938 3 A 74105 问题 用最小元素法求解上述运输问题 解 销地 产地 1 B 2 B 3 B 4 B 产量 1 A437 3 2 A314 1 3 A639 3 销量 365 4 6 3 所以初始解为 13 x 4 14 x 3 21 x 3 23 x 1 32 x 6 34 x 3 2 用伏格尔法求解上述运输问题 销地 产地 1 B 2 B 3 B 4 B 产量 行罚数 1 A527 2 000 2 A314 1 1116 3 A639 3 12 销量 3656 3 2 列 罚 数 2 13 21 12 12 7 19 4 33 2 10 10 8 5 11 311310 1928 74105 所以初始解为 13 x 5 14 x 2 21 x 3 24 x 1 32 x 6 34 x 3 则 11 5 32 103 1 1 86 43 585 mn ijij ij zc x 3 某公司有三个水泥产地 分别向四个建筑工地运送水泥 已知各产地的产量分别为 1 16A 万吨 2 10A 万吨 3 22A 万吨 四个建筑工地的销量分别为 1 8B 万吨 2 14B 万吨 3 12B 万吨 4 14B 万吨 产销平衡表如下表所示 用最小元素法求得的总运费最小的初始运输方案为 销地 产地 1 B 2 B 3 B 4 B 产量 1 A106 16 2 A82 10 3 A148 22 销量 8141214 48 即方案最优解为 13 x 10 14 x 6 21 x 8 23 x 2 32 x 14 34 x 8 其余非 基变量取值为 0 求各决策变量对应的检验数 并判别此解是否为最优解 若不是最优解 进行解的调整 调整一次 求此 运输问题的另一组基本可行解 答案 用对偶变量法求各非基变量的检验数 并判别是否最优解 若不是最优解 进解的调整 此运输问题初始基本可行解为 13 x 10 14 x 6 21 x 8 23 x 2 32 x 14 34 x 8 又 ijijiij cuv 对所有基变量 检验数 0 13 14 21 23 32 34 4 11 2 3 5 6 uv uv uv uv uv uv 令 1 0u 得 3 4v 4 11v 2 1u 1 3v 3 5u 2 10v 非基变量检验数 111111 cuv 4031 121212 cuv 120 102 222222 10 1 101cuv 242424 cuv 9 1 111 2 10 5 4 4 3 11 9 12 8611 313131 8 5 310cuv 333333 11 5 412cuv 或者 销地 产地 1 B 2 B 3 B 4 B 产量 i u 1 A12 16 1 u 0 2 A1 1 10 2 u 1 3 A1012 22 3 u 5 销量 8141214 48 j v 1 v 3 2 v 10 3 v 4 4 v 11 非基变量 24 x的检验数 24 10 不是最优解 或者用闭合回路法求解 酌情给分 2 求运输问题的另一组基本可行解 24 1 24 x为换入变量 对应的闭回路如图 对闭回路上各点按逆时针顺序依次编号 其偶数点位于格 A1 B4 和 A2 B3 由于min 14 x 23 x min 6 2 2 故应作如下调整 24 x 0 2 14 x 6 4 13 x 10 12 23 x 2 0 得到新的基可行解是 13 x 12 14 x 4 21 x 8 24 x 2 32 x 14 34 x 8 整数规划整数规划 1 某公司拟于东 西 南三区建立门市部 有 7 个位置 1 2 7 i A i 可供选择 规定 1 在东区 由 1 A 2 A 3 A三点中至多选择 2 个 2 在南区 由 4 A 5 A两点中至少选择 1 个 3 在西区 由 6 A 7 A两点中至少选择 1 个 如选用 i A点 设备投资估计为 i b元 每年可获利估计为 i c元 但设备投资总额不能超过 B 元 问应选择 哪几个点可使年利润最大 试建立数学模型 解 引入 0 1 变量 i x 2 10 5 44 3 11 9 12 8611 1 1 2 7 0 i ij i A xi A 选 不选 则 7 1 max ii i zxc 7 1 123 45 67 2 1 1 01 1 2 7 ii i i x bB xxx xx xx xi 或 2 2 2 2 割平面法割平面法 对整数规划问题 12 maxZxx 12 12 12 12 26 4520 0 0 xx xx xx x x 为整数 不考虑整数条件 加入松弛变量得 1234 max00Zxxxx 123 124 1234 26 4520 0 0 0 0 xxx xxx xxxx 求得的最终单纯形表为 j c1100 B C B Xb 1 x 2 x 3 x 4 x 1 1 x5 3105 6 1 6 1 2 x8 301 2 31 3 j 00 1 6 1 6 用割平面法求解此整数规划问题 解 由最终单纯形表知 134 234 515 663 218 333 xxx xxx 即 1434 2334 255 1 366 211 2 333 xxxx xxxx 34 34 552 663 112 333 xx xx 345 345 554 2 xxx xxx 割平面方程为 34 2xx 所以引入松弛变量 得到新的约束条件 345 2xxx j c11000 B C B Xb 1 x 2 x 3 x 4 x 5 x 1 1 x5 3105 6 1 60 1 2 x8 301 2 31 30 0 5 x 200 1 11 j 00 1 6 1 6 0 1 1 x0100 1 5 6 1 2 x40101 2 3 0 3 x20011 1 j 0000 1 6 此时最优解 1 x 0 2 x 4 3 x 2 4 x 0 5 x 0 指派问题 指派问题 3 公司在各地有 4 项工程 选定了 4 位项目经理去分别处理 由于业务能力 经验和其他情况的不同 4 位项 目经理处理这 4 项业务的费用各不相同 费用估计如下表 应当怎样分配这 4 位项目经理 才能使 4 项工程都 得到处理 同时总的费用最小 业务 费用 项目经理 1234 A215134 B141415 C9141613 D78119 解 min 2151342 1414151 91416139 781197 ij c 142min 013112 0313 14 0574 0142 01270 02912 0432 0000 ij b 1270 02912 432 0 1270 02912 432 0 21270 0710 021 20 0001 0100 1000 0010 所以 14 1x 22 1x 31 1x 43 1x 即 指派项目经理 A 完成第 4 项任务 指派项目经理 B 完成第 2 项任务 指派项目经理 C 完成第 1 项任 务 指派项目经理 D 完成第 3 项任务 或者 A 4 B 2 C 1 D 3 动态规划动态规划 1 给定一运输网络 如图 两点之间直线上的数字表示两点间距离 试求一条从 A 到 E 的运轨路线 使总距 离为最短 解 1 当4k 时 状态变量 4 s可取两种状态 1 D 2 D 则 41 3fD 42 4fD 2 当3k 时 状态变量 3 s可取三种状态 1 C 2 C 3 C 这是经过中途点的二级决策问题 则 1141 31 1242 1 3 minmin4 44 d C DfD fC d C DfD 路径为 11 CDE 决策为 311 xCD 2141 32 2242 63 minmin7 34 d C DfD fC d C DfD 路径为 22 CDE 决策为 322 xCD 3141 33 3242 33 minmin6 34 d C DfD fC d C DfD 路径为 31 CDE 决策为 331 xCD 3 当2k 时 状态变量 2 s可取三种状态 1 B 2 B 3 B 这是经过中途点的三级决策问题 则 2 A B3 B2 B1 C1 C2 C2 E D1 D2 5 3 7 6 3 3 3 3 3 4 5 5 1 1 4 4 1234 1131 21 1333 74 minmin11 66 d B CfC fB d B CfC 路径为 111 BCDE 决策为 211 xBC 2131 222232 2333 34 min min 277 46 d B CfC fBd B CfC d B CfC 路径为 211 BCDE 决策为 221 xBC 3131 233232 3333 54 min min 1 78 56 d B CfC fBd B CfC d B CfC 路径为 322 BCDE 决策为 232 xBC 4 当1k 时 状态变量 1 s可取状态A 这是经过中途点的四级决策问题 则 121 1222 323 2 11 min min 5711 38 d A BfB fAd A BfB d A BfB 路径为 322 ABCDE 决策为 13 xAB 2 某施工单位拟在 3 年内开发三个项目 各年开发这些项目的盈利如下表 问如何安排开发计划 使该施工 单位的总盈利最大 最大盈利是多少 盈利年份 技术数 第一年第二年第三年 0000 1364 27106 3101211 解 阶段分为三个阶段 设决策变量 k x表示第k年开发的项目数 状态变量 k s表示第k年到第 3 年开发的项目总数 kk px 第k年开发 k x个项目的盈利 决策变量取值范围 33 22 11 0 0 sx xs xs 则状态转移方程 1kkk ssx 3 2 1k 基本方程 11 0 44 max 0 kk kkkkkk xs fspxfs fs 1 当3k 时 有 33 333344 max xs f sp xfs 33 3333 max xs p xp s 得 33 xs 2 当2k 时 对应 2 0 1 2 3s 有 22 222233 0 max xs fsp xf s 2 0s 时 22 223 0 0 max000 xs fpf 2 1s 时 2 22232 0 1 1 max 1 s fp xfx 23 23 0 1 04 maxmax5 1 0 50 pf pf 得 2 1x 2 2s 时 2 22232 0 1 2 2 max 2 s fpxfx 23 23 23 0 2 06 max 1 1 max 5410 100 2 0 pf pf pf 得 2 2x 2 3s 时 2 22232 0 1 2 3 3 max 3 s fp xfx 23 23 23 23 0 3 0 11 1 2 56 maxmax14 2 1 104 11 0 3 0 pf pf pf pf 得 2 2x 3 当1k 时 对应 1 3s 有 11 111122 0 max xs f sp xfs 1 11121 0 1 2 3 3 max 3 x fp xfx 12 12 12 12 0 3 0 14 1 2 3 10 maxmax14 2 1 75 90 3 0 pf pf pf pf 得 1 0 x 得最优方案 1 0 x 2 2x 3 1x 即第二年开发项目 2 项 第三年开发项目 1 项 总盈利为 14 万元 3 某一警卫部门共有 9 支巡逻队 负责 3 个要害部门 A B C 的警卫巡逻 每个部位可分别派出 2 4 支巡逻 队 并且由于派出的巡逻队数不同 各部位预期在一段时间内可造成的损失有差别 具体数字见表 问该警卫 部门应往各部位分别派多少支巡逻队 使总的预期损失为最少 部位 ABC预期损失 巡逻队数 2183824 3143522 4103121 解 3n 往 3 个部位派看作 3 个阶段 设决策变量 k x表示派往A B C三个部位的巡逻队数 状态变量 k s表示从第k阶段到第三阶段末可派出的巡逻队总数 1kkk ssx 1 2 3k kk px表示第k阶段派出 k x支巡逻队时 该部位的损失值 则状态转移方程 1kkk ssx 1 2 3k 基本方程 11 min kkk kkkkkk xDs fspxfs 1 0min kk kkkkk xs pxfsx 1 当3k 时 3 2 3 4 5s 1当 3 2s 时 3 x取 2 3 224f 3 2x 2当 3 3s