运筹学复习题.pdf

运筹学 投资 1021 黄昕玥 1034401132 一 0 1 整数规划 为解决污水对河流污染问题 某城市拟建污水处站 备选站址有 ABC 三个 其投资技术经济参数见下表 投资 万元 处理能力 万吨 年 水处理成本 远 万吨 水处理指标 吨 万吨 污染物 1 污染物 2 A 500 800 500 80 60 B 400 500 800 50 40 C 300 400 1000 40 50 安环保部门要求 每年至少从污水中清除八万吨污染物 1 和六万吨污 染物 2 请构造问题使费用最小 设 x i 表示 i 地每年的污水处理数 y i 为 0 1 变量表示 i 地是否投资 n i 表示处理能力 w1 i 表示污物 1 指标 w2 i 表示污设 x i 表示 i 地每年的污水处理数 y i 为 0 1 变量表示 i 地是否投资 n i 表示处 理能力 w1 i 表示污物 1 指标 w2 i 表示污物 2 指标 注意单位 则模型为 min z 500y 1 400y 2 300y 3 0 05x 1 0 8x 2 0 1x 3 s t x i n i y i i 1 2 3 w1 i x i 80000 w2 i x i 60000 x i 0 y i 为 0 1 变量 i 1 2 3 求解结果 A C 投资 处理污水达到能力上限 B 不投资 总费用 880 万元 运用软件得出的文件后缀为 yinter 模型结构和形式是线性规划 只是决策变量取 0 或 1 二 纯整数规划 求解下列整数规划问题 广州某餐馆 一周营业 7 天 餐馆雇用的员工每周工作 5 天 休息 2 天 并且每个员工得到相同的周薪 基于过去的经验 一周内有些天 比较忙而有些天顾客相对较少 所以每天需要的员工数也不同 如表 所示 星期 一 二 三 四 五 六 日需求量 人 20 16 13 16 19 14 12 该问题就是要在满足每天员工需求量的条件下确定所需雇用的最少 员工总数 周 1 周 2 周 3 周 4 周 5 周 6 周 7 1 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 设 Xj 饭馆按照排班方案 j 雇佣的员工数 j 1 2 3 21 则有如下纯整数规划问题 MINf X1 X2 X21 ST X1 x2 x3 x4 X5 X7 X10 X12 X13 X14 X16 X17 X19 20 X1 X4 X6 X9 X11 X12 X13 X15 X16 X18 X20 16 X7 X21 12 X1 X2 X21 0 整数 求最小整数解 X X1 X2 X21 需要雇佣 的最小员工数为 f X1 X21 若 J 1 2 n 即全部的决策变量都取整数 称为纯整数线性规划 三 混合整数规划 例如某石化公司下属三个工厂各自独立 分别提出互斥型投资方案 如表 各投资方案的有效期均为 l0 年 基准收益率为 10 如果这 个公司仅有 80000 万元可供投资 应如何选择方案对公司最有利 工厂 A B C 方案 Al A2 A3 Bl B2 B3 B4 Cl C2 投资 30000 40000 50000 l0000 20000 30000 40000 20000 30000 年净收益 9700 10800 13800 l630 5100 7170 8660 5000 8400 解 设目标函数为净年值最大 则目标函数 math max NAV sum j 1 9 sum t 0 10 CI CO tj P F 10 t A P 10 10 cdot X j X j 0 1 约束条件 计算结果为 Xl 1 X2 0 X3 0 X4 0 X5 1 X6 0 X7 0 X8 0 X9 1 即应选择 Al B2 C2 三个方案 若 J 是 1 2 n 的非空真子集 即仅有部分决策变量要求取整数 称为 混合整数线性规划 四 指派问题 有一份中文的说明书 需翻译成英 日 德 俄四种文字 分别作为 E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成 不同语种的说明书所需时间如表 1 所示 问应指派何人去完成何工 作