1、数 学 建 模1、 某 织 带 厂 生 产 A、 B 两 种 纱 线 和 C、 D 两 种 纱 带 ， 纱 带 由 专 门 纱 线 加 工 而成 。 这 四 种 产 品 的 产 值 、 成 本 、 加 工 工 时 等 资 料 列 表 如 下 ：产 品项 目A B C D单 位 产 值 (元 ) 168 140 1050 406单 位 成 本 (元 ) 42 28 350 140单 位 纺 纱 用 时 (h) 3 2 10 4单 位 织 带 用 时 (h) 0 0 2 0.5工 厂 有 供 纺 纱 的 总 工 时 7200h， 织 带 的 总 工 时 1200h， 列 出 线 性 规 划 模 型
2、 。解 ： 设 A 的 产 量 为 x1， B 的 产 量 为 x2， C 的 产 量 为 x3， D 的 产 量 为 x4， 则 有线 性 规 划 模 型 如 下 ：max f(x)=(16842)x1 +(14028)x2 +(1050350)x3 +(406140)x4=126 x1 +112 x2 +700 x3 +266 x4s.t. 4, ,5. 33ixi2、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天 500 万 m3，在两个工厂之间有一条流量为 200 万 m3 的支流。两化工厂每天排放某种有害物质的工业污水分别为 2 万 m3 和 1.4 万 m3。从第一化工厂排
3、出的工业污水流到第二化工厂以前，有 20%可以自然净化。环保要求河流中工业污水含量不能大于 0.2%。两化工厂处理工业污水的成本分别为 1000 元/万 m3 和 800 元/万 m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。解 ： 设 x1、 x2 分 别 代 表 工 厂 1 和 工 厂 2 处 理 污 水 的 数 量 (万 m3)。 则 问 题 的 目标 可 描 述 为min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x 203、 红 旗 商 场 是 个 中 型 的 百
4、货 商 场 ， 它 对 售 货 人 员 的 需 求 经 过 统 计 分 析 如 表 所示 。 为 了 保 证 售 货 人 员 充 分 休 息 ， 售 货 人 员 每 周 工 作 五 天 ， 休 息 两 天 ， 并 要 求休 息 的 两 天 是 连 续 的 ， 问 应 该 如 何 安 排 售 货 人 员 的 作 息 ， 既 满 足 了 工 作 需 要 又使 配 备 的 售 货 人 员 的 人 数 最 少 ？ （ 只 建 模 型 ， 不 求 解 ）工 厂1 工 厂2200 万 m3500 万 m3时 间 所 需 售 货 员 人 数星 期 日 28 人星 期 一 15 人星 期 二 24 人星 期
5、三 25 人星 期 四 19 人星 期 五 31 人星 期 六 28 人解 ： 设 x1 为 星 期 一 开 始 上 班 的 人 数 ， x2 为 星 期 二 开 始 上 班 的 人 数 ， x7 星 期 日 开 始 上 班 的 人 数 。min x1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x7 28x4+x5+x6+x7+x1 15x5+x6+x7+x1+x2 24x6+x7+x1+x2+x3 25x7+x1+x2+x3+ x4 19x1+x2+x3+x4+x5 31x2+x3+x4+x5+x6 28x1、 x2、 x3、 x4、 x5、 x6、 x7 04、 一 个 登
6、 山 队 员 ， 他 需 要 携 带 的 物 品 有 ： 食 品 、 氧 气 、 冰 镐 、 绳 索 、 帐 篷 、 照相 器 材 、 通 信 器 材 等 ， 每 种 物 品 的 重 量 及 重 要 性 系 数 见 表 所 示 ， 能 携 带 的 最 大重 量 为 25 kg， 试 选 择 该 队 员 所 应 携 带 的 物 品 。序 号 1 2 3 4 5 6 7物 品 食 品 氧 气 冰 镐 绳 索 帐 篷 照 相 器材 通 信 设备重 量 kg 5 5 2 5 10 2 3重 要 性 系 数 20 15 16 14 8 14 9解 ： 引 入 0 1 变 量 xi（ i 1， ， 7）i
7、i x不 携 带 物 品携 带 物 品则 0 1 规 划 模 型 为 ：max z 20x1 15x2 16x3 14x4 8x5 14x6 9x7s.t. 5x1 5x2 2x3 5x4 10x5 2x6 3x7 25xi 0 或 1， i 1， 0， ， 7标 准 化 问 题1、 将 下 列 线 性 规 划 化 为 标 准 形 式不321321 ,0 ,19| 576 .5)(minxxtsxxf 0, 191205736 0 . 25)(max 65433421xx xxtsf2、化下列线性规划为标准形max z=2x1+2x24x 3x1 + 3x23x 3 30x1 + 2x24x
8、380x1、x 20，x 3 无限制解：按照上述方法处理，得该线性规划问题的标准形为max z=2x1+2x24x 31+4x32x1 + 3x23x 31 + 3x32x 4 = 30x1 + 2x24x 31 + 4x32 + x5 = 80x1、x 2，x 31，x 32，x 4，x 5 0图 解 法1、用图解法求解下面线性规划。max z=2x1+2x2x1x 2 1x 1 + 2x2 0x1、x 2 0解 ： 图 13 中 阴 影 部 分 就 是 该问 题 的 可 行 域 ， 显 然 该 问 题 的可 行 域 是 无 界 的 。 两 条 虚 线 为目 标 函 数 等 值 线 ， 它
9、们 对 应 的目 标 值 分 别 为 2 和 4， 可 以 看出 ， 目 标 函 数 等 值 线 向 右 移 动 ，问 题 的 目 标 值 会 增 大 。 但 由 于可 行 域 无 界 ， 目 标 函 数 可 以 增大 到 无 穷 。 称 这 种 情 况 为 无 界解 或 无 最 优 解 。2、 用 图 解 法 求 解 下 述 LP 问 题 。1212max 3846. 0,jzxstx1 11z=42z=6OA图 132x1x解 ： 可 知 ， 目 标 函 数 在 B(4, 2)处 取 得 最 大 值 ， 故 原 问 题 的 最 优 解 为 ，*(4,2)TX目 标 函 数 最 大 值 为
10、。*314z3、 用 图 解 法 求 解 以 下 线 性 规 划 问 题 ：（ 1） max z= x1 +3x2s.t. x1 +x2 10-2x1 +2x2 12x1 7x1, x2 0x210(2,8)6x1-6 0 7 10最 优 解 为 （ x1,x2） =（ 2,8） ， max z=26(2) min z= x1 -3x2s.t. 2x1 -x2 4x1 +x2 3x2 5x1 4x1, x2 0x253x10 2 3 4最 优 解 为 （ x1， x2） =（ 0， 5） ， min z=-15（ 3） max z= x1 +2x2s.t. x1 -x2 1x1 +2x2 4x
11、1 3x1, x2 0x22x10 1 2 3 4多 个 最 优 解 ， 两 个 最 优 极 点 为 （ x1， x2） =（ 2， 1） ， 和 (x1， x2)=(0， 2)，max z=5（ 4） min z= x1 +3x2s.t. x1 +2x2 42x1 +x2 4x1, x2 0x2 x1=04x4=02x3=0x2=0 x10 2 4 最 优 解 为 （ x1， x2） =（ 4， 0） ， min z=4单 纯 形 法1、用单纯形法求解max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x 20解：首先将问题化为标准形式，然后将整个计算过
12、程列在一个表中Cj 50 100 0 0 0CB XB x1 x2 x3 x4 x5 b0 x3 1 1 1 0 0 3000 x4 2 1 0 1 0 400 0 x5 0 1 0 0 1 250z 50 100 0 0 0 0 0 x3 1 0 1 0 -1 500 x4 2 0 0 1 -1 150100 x2 0 1 0 0 1 250z 50 0 0 0 -100 2500050 x1 1 0 1 0 -1 500 x4 0 0 -2 1 1 50100 x2 0 1 0 0 1 250z 0 0 -50 0 -50 27500由于 j0（j=1，5） ，故 X*=（50，250，0
13、，50，0） T， Z*=275002、用单纯形法求解max z=2x1+x2 x1 + x252x15x 210x1、x 20解：用单纯形表实现如表 110表 110Cj 2 1 0 0CB XB x1 x2 x3 x4 b 0 x3 -1 1 1 0 5 0 x4 2 -5 0 1 10 10/4(min)z 2 1 0 0 00 x3 0 -3/2 1 1/2 102 x1 1 -5/2 0 1/2 5z 0 6 0 -1 10 2=6 0，且 p20，故该线性规划有无界解（无最优解） 。3、用单纯形法（大 M 法）求解下列线性规划max z=3x12x 2x 3x12x 2 + x3
14、114x 1 + x2 + 2x3 32x 1 + x3 = 1x1、x 2、x 30解：化为标准形式 max z=3x12x 2x 3x12x 2 + x3 + x4 = 114x 1 + x2 +2x3 x 5 = 32x 1 +x3 = 1x1、x 2、x 3 、x 4、x 50在第二、三个约束方程中分别加入人工变量 x6、x 7，构造如下线性规划问题max z=3x12x 2x 3Mx 6Mx 7x12x 2 + x3 + x4 = 114x 1 + x2 +2x3 x 5 + x6 = 32x 1 + x3 +x7 = 1x1、x 2、x 3、x 4、x 5、x 6、x 70用单纯形
15、进行计算，计算过程见表Cj 3 -1 -1 0 0 -M -MCB XB x1 x2 x3 x4 x5 x6 x7 b0 x4 1 -2 1 1 0 0 0 11-M x6 -4 1 2 0 -1 1 0 3-M x7 -2 0 1 0 0 0 1 1z 3-6M -1+M -1+3M 0 -M 0 0 4M0 x4 3 -2 0 1 0 0 -1 10-M x6 0 1 0 0 -1 1 -2 1-1 x3 -2 0 1 0 0 0 1 1z 1 -1+M 0 0 -M 0 -3M+1 M+10 x4 3 0 0 1 -2 2 -5 12-1 x2 0 1 0 0 -1 1 -2 1-1 x
16、3 -2 0 1 0 0 0 1 1z 1 0 0 0 -1 -M+1 -M-1 23 x1 1 0 0 1/3 -2/3 2/3 -5/3 4-1 x2 0 1 0 0 -1 1 2 1-1 x3 0 0 1 2/3 -4/3 4/3 -7/3 9z 00 0-1/3 -1/3-M+1/3-M+2/32由于 j0（j=1，7） ，且基变量中不含人工变量，故 X*=（4，1，9） T， z*=24、用单纯形法（大 M 法）求解下列线性规划max z=3x1+2x22x1+ x2 23x1 +4 x2 12x1、x 20解: 化为标准形式后引入人工变量 x5 得到max z=3x1+2x2Mx
17、52x1+ x2 +x3 = 23x1 +4 x2 x 4+x5 =12x1、x 50用单纯形法计算，过程列于表中。从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量x5=4，所以原问题无可行解。3 2 0 0 -MCB xB x1 x2 x3 x4 x5 b0-Mx3x52314100-101212-z 3+3M 2+4M 0 -M 0 12M2-Mx2x52-5101-40-10124-z -1-5M 0 -2-4M -M 0 -4+4M2、 用 单 纯 形 法 求 解 下 述 LP 问 题 。1212ma 3846. 0,jzxstx解 ： 首 先 将 原 问 题 转
18、 化 为 线 性 规 划 的 标 准 型 ， 引 入 松 弛 变 量 x3, x4,x5， 可 得 ： 1231425ma 86. 0,jzxstx构 造 单 纯 形 表 ， 计 算 如 下 ：jc2 3 0 0 0BXb1x23x45xi0 3x8 1 2 1 0 0 40 416 4 0 0 1 0 0 512 0 4 0 0 1 3j2 3 0 0 00 3x2 1 0 1 0 1/2 20 416 4 0 0 1 0 43 3 0 1 0 0 1/4 j2 0 0 0 3/42 1x2 1 0 1 0 1/2 0 48 0 0 4 1 2 43 3 0 1 0 0 1/4 12j0 0
19、 2 0 1/42 1x4 1 0 0 1/4 00 54 0 0 2 1/2 13 22 0 1 1/2 1/8 0j0 0 3/2 1/8 0原 问 题 的 最 优 解 为 ， 目 标 函 数 最 大 值 为*(,4)TX。*41z3、 用 单 纯 形 法 求 解 下 述 LP 问 题 。1212max 340. ,zxst解 ： 首 先 将 原 问 题 转 化 为 线 性 规 划 的 标 准 型 ， 引 入 松 弛 变 量 、3x， 可 得 ：4x123124ma z0. ,xst构 造 单 纯 形 表 ， 计 算 如 下 ：jc3 4 0 0BBXb1x23x4i0 3x40 2 1 1 0 400 430 1 3 0 1 10j3 4 0 00 3x30 5/3 0 1 -1/3 184 210 1/3 1 0 1/3 30j5/3 0 0 -4/33 1x18 1 0 3/5 -1/54 24 0 1 -1/5 2/5j0 0 -1 -1由 此 可 得 ， 最 优 解 为 ， 目 标 函 数 值 为*(8, )TX。*31847z
