线性规划与LINGO编程

《线性规划与LINGO编程》由会员分享，可在线阅读，更多相关《线性规划与LINGO编程（79页珍藏版）》请在装配图网上搜索。

1、华 中 农 业 大 学 数 学 建 模 创 新 实 践 基 地 系 列 课 件第 2讲 线 性 规 划 与 LINGO编程华 中 农 业 大 学 内容说明 以 下 内 容 在 数 学建 模 与 数 学 实 验（ 第 二 版 ） （ 汪 晓 银 ， 周 保平 主 编 ） 第 3章 2.1 什 么 是 数 学 规 划2.2 连 续 性 线 性 规 划2.3 敏 感 性 分 析2.4 整 数 线 性 规 划2.5 0-1规 划内容说明 数 学 规 划 俗 称 最 优 化 ,首 先 是 一 种 理念 ,其 次 才 是 一 种 方 法 ,它 所 追 求 的 是 一 种“ 至 善 ” 之 道 ,一 种 追

2、 求 卓 越 的 精 神 .2.1 什么是数学规划 小 明 同 学 ， 烧 一 壶 水 要 8分 钟 ， 灌 开 水要 1分 钟 ， 取 牛 奶 和 报 纸 要 5分 钟 ， 整 理 书 包要 6分 钟 ， 为 了 尽 快 做 完 这 些 事 ， 怎 样 安 排才 能 使 时 间 最 少 ？ 最 少 需 要 几 分 钟 ？ 十 个 人 各 提 一 只 水 桶 ， 同 时 到 水 龙 头前 打 水 。 设 水 龙 头 注 满 第 一 个 人 的 桶 需 要 1分 钟 ， 注 满 第 二 个 人 的 桶 需 要 2分 钟 ， 依 此类 推 ， 注 满 第 几 个 人 的 桶 就 需 要 几 分 钟

3、 ，如 果 只 有 一 只 水 龙 头 ， 适 当 安 排 这 10个 人的 顺 序 ， 就 可 以 使 每 个 人 所 费 的 时 间 总 和尽 可 能 小 ， 问 这 个 总 费 时 至 少 是 几 分 钟 ？ 2.1 什么是数学规划 数 学 规 划 (最 优 化 )作 为 一 门 学 科 孕 育 于 20世纪 的 30年 代 ,诞 生 于 第 二 次 世 界 大 战 弥 漫 的 硝 烟中 。 数 学 规 划 指 在 一 系 列 客 观 或 主 观 限 制 条 件下 ， 寻 求 合 理 分 配 有 限 资 源 使 所 关 注 的 某 个 或 多个 指 标 达 到 最 大 （ 或 最 小 ）

4、 的 数 学 理 论 和 方 法 ，是 运 筹 学 里 一 个 十 分 重 要 的 分 支 。 2.1 什么是数学规划 最 优 化 问 题 的 数 学 模 型 的 一 般 形 式 为 ： xfzopt sk ji RDx nkxt mjxg lixhts ,1,0 ,1,0 ,1,0 . （ 1）（ 2）三 个 要 素 ： 决 策 变 量 decision bariable， 目 标 函 数objective function， 约 束 条 件 constraints。 2.1 什么是数学规划 约 束 条 件 （ 2） 所 确 定 的 x的 范 围 称 为 可 行 域feasible regi

5、on， 满 足 （ 2） 的 解 x称 为 可 行 解feasible solution， 同 时 满 足 （ 1） （ 2） 的 解 x称 为最 优 解 Optimal solution， 整 个 可 行 域 上 的 最 优 解称 为 全 局 最 优 解 global optimal solution， 可 行 域 中某 个 领 域 上 的 最 优 解 称 为 局 部 最 优 解 local optimal solution。 最 优 解 所 对 应 的 目 标 函 数 值 称 为 最 优 值optimum。 2.1 什么是数学规划 （ 一 ） 按 有 无 约 束 条 件 （ 2） 可 分

6、为 ：1.无 约 束 优 化 unconstrained optimization。2.约 束 优 化 constrained optimization。大 部 分 实 际 问 题 都 是 约 束 优 化 问 题 。 优 化 模 型 的 分 类2.1 什么是数学规划 （ 二 ） 按 决 策 变 量 取 值 是 否 连 续 可 分 为 ：1.数 学 规 划 或 连 续 优 化 。可 继 续 划 分 为 线 性 规 划 (LP)Linear programming和 非 线 性 规 划 (NLP) Nonlinear programming。 在非 线 性 规 划 中 有 一 种 规 划 叫 做

7、二 次 规 划(QP)Quadratic programming， 目 标 为 二 次 函 数 ，约 束 为 线 性 函 数 。2.离 散 优 化 或 组 合 优 化 。包 含 ： 整 数 规 划 (IP)Integer programming， 整 数规 划 中 又 包 含 很 重 要 的 一 类 规 划 ： 0-1（ 整 数 ） 规划 Zero-one programming， 这 类 规 划 问 题 的 决 策变 量 只 取 0或 者 1。2.1 什么是数学规划 （ 三 ） 按 目 标 的 多 少 可 分 为 ：1.单 目 标 规 划 。2.多 目 标 规 划 。（ 四 ） 按 模 型

8、中 参 数 和 变 量 是 否 具 有 不 确 定 性 可 分 为 ：1.确 定 性 规 划 。2.不 确 定 性 规 划 。（ 五 ） 按 问 题 求 解 的 特 性 可 分 为 ：1.目 标 规 划 。2.动 态 规 划 。3.多 层 规 划 。4.网 络 优 化 。5. 等 等 。2.1 什么是数学规划 LINGO软 件 和 MATLAB软 件 。 对 于 LINGO软 件 ， 线 性 优 化 求 解 程 序 通 常 使 用单 纯 形 法 simplex method， 单 纯 形 法 虽 然 在 实 际 应 用中 是 最 好 最 有 效 的 方 法 ， 但 对 某 些 问 题 具 有

9、指 数 阶 的复 杂 性 ， 为 了 能 解 大 规 模 问 题 ， 也 提 供 了 内 点 算 法interior point method备 选 （ LINGO中 一 般 称 为 障 碍法 ， 即 barrier） ， 非 线 性 优 化 求 解 程 序 采 用 的 是 顺 序线 性 规 划 法 ， 也 可 用 顺 序 二 次 规 划 法 ， 广 义 既 约 梯 度法 ， 另 外 可 以 使 用 多 初 始 点 （ LINGO中 称 multistart）找 多 个 局 部 最 优 解 增 加 找 全 局 最 优 解 的 可 能 ， 还 具 有全 局 求 解 程 序 分 解 原 问 题 成

10、 一 系 列 的 凸 规 划 。求 解 优 化 问 题 常 用 的 软 件2.1 什么是数学规划 线 性 规 划 的 一 般 形 式 ： nj jjxczz 1)max(min 或 njx mibxats j ijij ,1,0 ,1,)( n1j. 或或 2.2 连续性线性规划 一 般 线 性 规 划 问 题 都 可 以 通 过 引 入 非 负 的 松 弛变 量 slack variable与 非 负 的 剩 余 变 量 surplus v-ariable的 方 法 化 为 标 准 形 式 （ 约 束 全 是 等 约 束 ） 。 线 性 规 划 问 题 的 可 行 域 feasible re

11、gion是 一 个 凸集 convex set（ 任 意 两 点 的 连 线 上 的 点 都 在 区 域 内 部 ，可 以 看 作 是 没 有 凹 坑 的 凸 多 面 体 ） ， 所 以 最 优 解Optimal solution/point在 凸 多 面 体 的 某 个 顶 点 上 达到 求 解 方 法 ： 单 纯 形 算 法 simplex method。 2.2 连续性线性规划 1.比 例 性 ： 每 个 决 策 变 量 对 目 标 函 数 以 及 右 端 项的 贡 献 与 该 决 策 变 量 的 取 值 成 正 比 。2.可 加 性 ： 每 个 决 策 变 量 对 目 标 函 数 以

12、及 右 端 项的 贡 献 与 其 他 决 策 变 量 的 取 值 无 关 。3.连 续 性 ： 每 个 决 策 变 量 的 取 值 都 是 连 续 的 。 连 续 线 性 规 划 问 题 的 性 质要 解 决 的 问 题 的 目 标 可 以 用 数 值 指 标 反 映对 于 要 实 现 的 目 标 有 多 种 方 案 可 选 择有 影 响 决 策 的 若 干 约 束 条 件2.2 连续性线性规划 。问 如 何 调 运 使 运 费 最 低如 下公 里 单 位距 离两 个 粮 库 到 三 个 粮 站 的吨大 米 分 别 为 三 个 粮 站 至 少 需 要吨吨为两 个 粮 库 现 存 大 米 分 别

13、 调 运 大 米向 三 个 粮 站有 两 个 粮 库,): (,5,4,2 ,8,4 , 32121 BBBAA例 1 运 输 问 题2.2 连续性线性规划 解 设 A1,A2调 运 到 三 个 粮 站 的 大 米 分 别 为 x1，x2， x3， x4， x5， x6吨 。题 设 量 可 总 到 下 表 ：2.2 连续性线性规划 结 合 存 量 限 制 和 需 量 限 制 得 数 学 模 型 ： 654321 24123082412min xxxxxxf 0, 542 84. 654321 63 52 41 654 321 xxxxxx xx xx xx xxx xxxts2.2 连续性线性

14、规划 程 序 编 写 1model:min=12*x1+24*x2+8*x3+30*x4+12*x5+24*x6 ;x1+x2+x34 ;x4+x5+x62 ;x2+x54 ;x3+x65 ;end提 示 ： 课 件 中 的 程序 请 先 粘 贴 在 记 事本 中 再转 帖 于 lingo软 件中2.2 连续性线性规划 运 行 结 果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 0 Variable Value Reduced Cost X1 2.000000 0.00000

15、0 X2 0.000000 28.00000 X3 2.000000 0.000000 X4 0.000000 2.000000 X5 4.000000 0.000000 X6 3.000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.00000 2.2 连续性线性规划 84库存量x23x22x21A2 542需 要 量

16、 x13x12x11A1 B3B2B1粮 库 粮 站距 离 及 运 量 12 122430 824变 量 更 换 为 ：2.2 连续性线性规划 232221131211 24123082412 xxxxxxf min 0542 84 232221131211 2313 2212 2111 232221 131211 xxxxxx xx xx xx xxx xxxts ,.模 型 :2.2 连续性线性规划 程 序 编 写MODEL:TITLE 调 运 大 米 的 运 输 问 题 程 序3;!定 义 集 合 段;SETS:LIANGKU/1.2/:A;!定 义 粮 库 的 集 合;LIANGZHA

17、N/1.3/:B;!定 义 粮 站 的 集 合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定 义 运 量 和 距 离;ENDSETSDATA:!粮 库 到 粮 站 的 距 离;C= 12 24 8 30 12 24;2.2 连续性线性规划 !粮 库 的 限 量;A=4 8 ;!粮 站 的 限 量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!粮 库 上 限 的 约 束;FOR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 2.2 连续性线性规划 程 序 的 调 试1.直 接 点 击 运 行 ，

18、 如 果 出 错 会 弹 出 错 误 提 示 ， 根据 提 示 做 相 应 的 修 改 ；2.可 以 用 “ ！ ” 把 约 束 变 成 说 明 语 句 ， 而 把 这 条语 句 屏 蔽 掉 ， 缩 小 寻 找 出 错 的 范 围 ；3.可 以 边 写 程 序 边 运 行 ， 保 证 每 行 书 写 都 是 正 确的 程 序 ；2.2 连续性线性规划 例 2 阶 段 生 产 问 题 某 公 司 生 产 某 产 品 ,最 大 生 产 能 力 为 10000单 位 ,每单 位 存 储 费 2元 ,预 定 的 销 售 量 与 单 位 成 本 如 下 :月 份 单 位 成 本 (元 ) 销 售 量12

19、34 70 6000 72 7000 80 12000 76 6000求 一 生 产 计 划 ,使 1)满 足 需 求 ; 2)不 超 过 生 产 能 力 ;3)成 本 (生 产 成 本 与 存 储 费 之 和 )最 低 .2.2 连续性线性规划 1je 解 假 定 1月 初 无 库 存 ,4月 底 买 完 ,当 月 生 产 的 不 库存 ,库 存 量 无 限 制 .为 单 位 成 本 ， 为 存 储 费 ，为 销 售 量 ，月 产 量 ，为 第： 设模 型i iiic edix ji iji i dx 1131j41j jj xc fmin 4,23,1100000 3,2,1. 41 41

20、1 1 ix dx jdxts ii i iiji ji ii 2.2 连续性线性规划 model:title 生 产 计 划 程 序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2 ;a=10000;enddatamin=sum(yuefen:c*x)+ sum(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x-d)*e(j+1);for(yuefen(j)|j#lt#4: sum(yuefen(i)|i#le#j:x) sum(yuefe

21、n(i)|i#le#j:d); sum(yuefen:x)= sum(yuefen:d);for(yuefen:xa);end 2.2 连续性线性规划 .ii iii sic edix 月 初 的 库 存 量 为为 单 位 成 本 ， 设 第 为 存 储 费 ，为 销 售 量 ，月 产 量 ，为 第： 设模 型 4141min i iii ii sexcf.ts 1is ,iii dxs 4,3,2,1i00 51 ss 43210 4321100000 ， ， is ix ii 2.2 连续性线性规划 Model:Title 生 产 计 划 程 序2;Sets:yuefen/1.4/:c,x

22、,e,d,s;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2 ;a=10000;enddatamin=sum(yuefen:c*x+e*s);for(yuefen(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i);s(4)+x(4)-d(4)=0;s(1)=0;for(yuefen:xa); End 2.2 连续性线性规划 . ,:月 的 销 售 量示 的 第 表存 储 费 之 和月 卖 出 时 的 生 产 成 本 与生 产 的 产 品 在 第 月表 示 第月 卖 出 的 数 量月 生 产 的 产 品 在 第表

23、 示 第设 化 为 运 输 问 题模 型 j dj icjix jijij 月 份 单 位 成 本 (元 ) 销 售 量1234 70 6000 72 7000 80 12000 76 60002.2 连续性线性规划 76827676- 80- 7472- 747270生 产 月 10000100001000010000产 量600041200070006000销 量4321 321需 求 月费 用 cij2.2 连续性线性规划 且 为 整 数0 10000.min 41 ,41 1 ijij ijji jijj ji ijijx x dxts xcf建 立 模 型 如 下 ： 2.2 连续性

24、线性规划 model:title 生 产 计 划 程 序3;sets:yuefen/1.4/:a,d,xx;!定 义 上 三 角 矩 阵;link(yuefen,yuefen)|endsetsdata:c=70 72 74 76 71 73 75 80 82 76;d=6000 7000 12000 6000;a=10000 10000 10000 10000;enddatamin=sum(link:c*x); for(yuefen(i):sum(yuefen(j)|j#ge#i:x(i,j)d(j););!得 到 每 个 月 的 生 产 量;for(yuefen(i):xx=sum(yuef

25、en(j)|j#ge#i:x(i,j);End 2.2 连续性线性规划 Model Title: :生 产 计 划 程 序1 Variable Value Reduced Cost A 10000.00 0.000000 C( 1) 70.00000 0.000000 C( 2) 71.00000 0.000000 C( 3) 80.00000 0.000000 C( 4) 76.00000 0.000000 X( 1) 10000.00 0.000000 X( 2) 10000.00 0.000000 X( 3) 5000.000 0.000000 X( 4) 6000.000 0.0000

26、00 E( 1) 2.000000 0.000000 E( 2) 2.000000 0.000000 E( 3) 2.000000 0.000000 E( 4) 2.000000 0.000000 D( 1) 6000.000 0.000000 D( 2) 7000.000 0.000000 D( 3) 12000.00 0.000000 D( 4) 6000.000 0.000000 2.2 连续性线性规划 设 有 两 个 工 厂 A、 B， 产 量 都 是 10万 个 ， 工 厂有 三 个 仓 库 x， y， z， 产 品 都 先 送 到 仓 库 。 现 有 四个 顾 客 分 别 为 甲

27、， 乙 ， 丙 ， 丁 ， 需 求 量 分 别 为 3， 5，4， 5万 个 。 工 厂 到 仓 库 、 仓 库 到 顾 客 的 运 费 单 价（ 元 /个 ） 见 下 表 所 示 。 试 求 总 运 费 最 少 的 运 输 方案 以 及 总 运 费 。 A B 甲 乙 丙 丁x 4 3 5 7 10 20y 2 1 9 6 7 15z 5 2 20 6 7 4课后训练 model:title 转 运 问 题;sets: Plant /A, B/: produce; Warhouse /x, y, z/; Customer /1.4/: require; LinkI ( Plant, Warh

28、ouse): cI, xI; LinkII ( Warhouse, Customer): cII, xII;endsetsdata: produce = 10, 10; require = 3, 5, 4, 5; cI = 4, 2, 5, 3, 1, 2; cII = 5, 7, 10, 20, 9, 6, 7, 15, 20, 6, 7, 4;enddata 课后练习 OBJ min = sum( LinkI: cI * xI) + sum( LinkII: cII * xII);! The supply constraints;for( Plant(i): SUP sum( Warhou

29、se(j): xI(i,j) = produce(i);! 运 进 仓 库 的 量 等 于 运 出 的 量;for( Warhouse(j): MID sum( Plant(i): xI(i,j)=sum( Customer(k): xII(j,k);! The demand constraints;for( Customer(k): DEM sum( Warhouse(j): xII(j,k) = require(k);课后练习 连 续 投 资 10万 元A： 从 第 1年 到 第 4年 每 年 初 要 投 资 ， 次 年 末 回 收本 利 1.15B： 第 3年 初 投 资 ， 到 第 5

30、年 末 回 收 1.25， 最 大 投 资 4万 元C： 第 2年 初 投 资 ， 到 第 5年 末 回 收 1.40， 最 大 投 资 3万 元D： 每 年 初 投 资 ， 每 年 末 回 收 1.11。求 ： 5年 末 总 资 本 最 大 。练习2 连续投资课后练习 第 1年 第 2年 第 3年 第 4年 第 5年A x1A x1A x1A x1AB x3BC x2CD x1D x1D x1D x1D x1D练 习 2解 答变 量 设 置课后练习 模 型 建 立 4 2 3 51 12 2 2 12 3 3 3 1 234 4 2 35 3 4max 1.15 1.40 1.25 1.11

31、10 1.113 1.15 1.114 1.15 1.111.15 1.11, , , 0, 1 5A C B DA DA C D DCA B D A DBA D A DD A DiA iB iC iDf x x x xx xx x x xxx x x x xxx x x xx x xx x x x i 课后练习 程 序 编 写model:title 投 资 问 题;max=1.15*x4a+1.40*x2c+1.25*x3b+1.06*x5d;x1a+x1d=100000;x2a+x2c+x2d=1.06*x1d;x3a+x3b+x3d=1.15*x1a+1.06*x2d;x4a+x4d=1

32、.15*x2a+1.06*x3d;x5d=1.15*x3a+1.06*x4d;x3b=40000;x2c=30000;课后练习 运 行 结 果Global optimal solution found. Objective value: 143750.0 Total solver iterations: 2 Model Title: 投 资 问 题 Variable Value Reduced Cost X4A 45000.00 0.000000 X2C 30000.00 0.000000 X3B 40000.00 0.000000 X5D 0.000000 0.000000 X1A 7169

33、8.11 0.000000 X1D 28301.89 0.000000 X2A 0.000000 0.000000 X2D 0.000000 0.3036000E-01 X3A 0.000000 0.000000 X3D 42452.83 0.000000 X4D 0.000000 0.2640000E-01 课后练习 例 3 生 产 计 划 问 题 某 工 厂 计 划 安 排 生 产 ， 两 种 产 品 ， 已 知 每种 单 位 产 品 的 利 润 ， 生 产 单 位 产 品 所 需 设 备 台 时 及 A,B两 种 原 材 料 的消 耗 ， 现 有 原 材 料 和 设 备 台 时 的 定

34、额 如 表 所 示 ， 问 ： ） 怎 么 安 排 生 产 使 得 工 厂 获 利 最 大 ？ ） 产 品 的 单 位 利 润 降 低 到 1.8万 元 ， 要 不 要 改 变 生 产 计 划 ， 如 果降 低 到 1万 元 呢 ？ ） 产 品 的 单 位 利 润 增 大 到 5万 元 ， 要 不 要 改 变 生 产 计 划 ？ ） 如 果 产 品 ， 的 单 位 利 润 同 时 降 低 了 1万 元 ， 要 不 要 改 变 生 产计 划 ？ 产 品 产 品 最 大 资 源 量设 备 1 2 8台 时原 材 料 A 4 0 16kg原 材 料 B 0 4 12kg 单 位 产 品 利 润 2

35、3 2.3 敏感性分析 2.3 敏感性分析 程 序 编 写model:title 生 产 计 划 问 题;maxfmax=2*x1+3*x2;TIMEx1+2*x28;A4*x116;B4*x212;END2.3 敏感性分析 运 行 结 果 Model Title: 生 产 计 划 问 题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.00000

36、0 0.1250000 TIME 4.000000 0.000000 对 问 题1， 安 排 是 生 产 产 品 4单 位 ， 产 品 2单 位 ， 最 大 盈利 为14万 元 。2.3 敏感性分析 目 标 函 数 的 系 数 变 化 的 敏 感 性 分 析 如 果 目 标 函 数 的 系 数 发生 变 化 ， 将 会 影 响 目 标函 数 f 斜 率 的 变 化 ， 但是 只 要 f 的 斜 率 小 于 等 于-1/2（ 也 就 是 直 线 l夹 在 l1与 l2之 间 时 ） ， 最 优 解 都在 (4,2)上 取 到 ， 最 优 解不 变 ， 从 而 生 产 计 划 不会 变 . 2.3

37、 敏感性分析 要 使 用 敏 感 性 分 析必 须 要 在 这 里 选 择Prices x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 22

38、0桶 牛 奶 生 产 A1, 30桶 生 产 A2， 利 润 3360元 。 2.3 敏感性分析 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元 可 买 到 1桶 牛 奶 ， 要 买 吗 ？ 35 50; x2 + 2*x4

39、+ x5 + 3*x6 20; x3 + x5 + 2*x715;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end程 序 编 写2.4 整数规划 按 模 式 2切 割 12根 ,按 模 式 5切 割 15根 ， 余 料 27米 最 优 解 ： x2=12, x5=15, 其 余 为 0；最 优 值 ： 27最 优 解 ： x2=15, x5=5, x7=5, 其 余 为 0；最 优 值 ： 25。按 模 式 2切 割 15根 ， 按 模 式 5切 割 5根 ， 按 模 式 7切 割 5根 ， 共 25根 ， 余 料 35米

40、当 余 料 没 有 用 处 时 ， 通 常 以 总 根 数 最 少 为 目 标 2.4 整数规划 练 习 3 某 服 务 部 门 一 周 中 每 天 需 要 不 同 数 目 的 雇 员 ，周 一 到 周 四 每 天 至 少 需 要 50人 ， 周 五 至 少 需 要 80人 ，周 六 和 周 日 至 少 需 要 90人 ， 现 规 定 应 聘 者 需 连 续 工作 5天 ， 试 确 定 聘 用 方 案 。解 周 一 至 周 日 分 别 聘 用 X(i)（ i 1,2， 7） 个 人 上 班 ，最 少 所 需 人 数 为 R(i)， 总 人 数 为 Z. 5,2,121.min 71 i iRi

41、XiXZts XZ i i 课后练习 MODEL:SETS:DAYS/MON.SUN/:R,X;ENDSETSDATA:R=50 50 50 50 80 90 90;ENDDATAMIN=Z;N=SIZE(DAYS);!集 合 的 长 度;Z=SUM(DAYS:X); FOR(DAYS(I):Z-X(WRAP(I+1,N)-X(WRAP(I+2,N)R(I);!WRAP()相 当 于 求 余 数 ， 返 回1到N之 间 的 数;FOR(DAYS:GIN(X);END 课后练习 ?, ,1, 2:),(),(),( ),(),(),(),(:7 , 765 4321 的 年 利 润 最 大问 如

42、 何 选 择 地 址 使 公 司元总 投 资 不 超 过 元每 年 可 获 利元投 资若 选个汉 口 汉 阳 至 少个 武 昌 至 多并 规 定汉 商二 十 一 世 纪行 街 步武 广司 门 口亚 贸中 商个 地 址有 拟 议 中汉 阳 建 立 专 卖 店汉 口某 公 司 拟 定 在 在 武 昌b cbA AAA AAAA iii例 6 选 址 问 题2.5 0-1规划 否 则选 择解 ,0,1: ii Ax 71max i ii xcf 7,.,2,110 11 2. 76 54 321 71 ix xx xx xxx bxbts ii ii 或2.5 0-1规划 例 7 面 试 顺 序 问

43、 题 有 4名 同 学 到 一 家 公 司 参 加 三 个阶 段 的 面 试 ， 公 司 要 求 每 个 同 学 都 必 须 首 先 找 公 司 秘 书 初 试 ，然 后 到 主 管 部 门 处 复 试 ， 最 后 到 经 理 处 参 加 免 试 ， 并 且 不 允许 插 队 ， 由 于 4名 同 学 的 专 业 背 景 不 同 ， 所 以 每 人 在 三 个 阶 段的 面 试 时 间 也 不 同 ， 如 表 所 示 ， 这 4名 同 学 约 定 他 们 全 部 面 试完 以 后 一 起 离 开 公 司 ， 假 定 现 在 时 间 是 早 上 8： 00， 请 问 他 们最 早 何 时 能 离

44、 开 公 司 ？ 秘 书 初 试 主 管 复 试 经 理 面 试同 学 甲 13 15 20同 学 乙 10 20 18同 学 丙 20 16 10 同 学 丁 8 10 15 2.5 0-1规划 2.5 0-1规划 优 化 目 标 为 ： 3 3min max i iiT x t 约 束 条 件 ： 个 人 时 间 先 后 次 序 约 束 ： . 1, 1,2,3,4; 1,2.ij ij i jx t x i j 同 阶 段 不 同 同 学 时 间 不 相 容 ： （ 同 阶 段 靠 前 同 学 的完 成 时 间 小 于 靠 后 同 学 的 开 始 时 间 ） , ij ij kj ikx

45、 t x My 1 ,kj kj ij ikx t x M y 0 1iky or 2.5 0-1规划 可 将 目 标 改 为 如 下 线 性 优 化 目 标 ： 13 1323 2333 33 43 43min. ,.Tst T x tT x tT x tT x t 2.5 0-1规划 程 序 编 写 model:title:面 试 问 题;sets:student/1.4/:;office/1.3/:;link1(student,office):x,t;link2(student,student)|endsetsdata:t=13 15 20 10 20 18 20 16 10 8 10

46、15 ;Enddata min=time;!time大 于 每 名 同 学 最 后 面 试 完 毕 时 间;for(student(i):timex(i,3)+t(i,3);); 2.5 0-1规划 !面 试 先 后 次 序 约 束;for(student(i): for(office(j)|j#lt#3:x(i,j)+t(i,j)x(i,j+1););!每 个 阶 段 只 能 面 试 一 个 同 学,y(i,k)=1表 示 第k名 同 学 排 在 第i名 同 学 前 面;取M=1000；for(student(i): for(office(j): for(student(k)|k#gt#i:

47、 x(i,j)+t(i,j)-x(k,j)1000*y(i,k);for(student(i): for(office(j): for(student(k)|k#gt#i: x(k,j)+t(k,j)-x(i,j)1000*(1-y(i,k);!定 义0-1变 量,最 后 通 过0-1变 量 可 以 查 看 面 试 顺 序;for(link2:bin(y);End2.5 0-1规划 运 行 结 果 Model Title: :面 试 问 题 Variable Value Reduced Cost TIME 84.00000 0.000000 （ 省 略 ） Y( 1, 2) 0.000000

48、-1000.000 Y( 1, 3) 0.000000 0.000000 Y( 1, 4) 1.000000 1000.000 Y( 2, 3) 0.000000 -1000.000 Y( 2, 4) 1.000000 0.000000 Y( 3, 4) 1.000000 0.000000 所 以 面 试 完 成 至 少 需 要 84min， 面 试 顺 序 为 4-1-2-3（ 丁 -甲 -乙 -丙 ） 2.5 0-1规划 练 习 4 某 班 准 备 从 5名 游 泳 员 中 选 择 人 组 成 接 力 队 ，参 加 学 校 的 4 100m混 合 泳 接 力 比 赛 ， 5名 队 员 4种

49、 泳姿 的 百 米 平 均 成 绩 如 表 ， 问 如 何 选 拔 队 员 。队 员 甲 乙 丙 丁 戊蝶 泳 1068 572 118 110 1074仰 泳 1156 106 1142 1142 111蛙 泳 127 1064 1096 1096 1238自 由 泳 586 53 594 572 1024课后练习 model:sets:swim/1.4/:;member/1.5/:;match(swim,member):c,x;endsetsdata:c=66.8 57.2 78 70 67.475.6 60.6 74.2 74.2 7187 66.4 69.6 69.6 83.8 58.6 53 59.4 57.2 62.4;enddatamin=sum(match:c*x);for(swim(i):sum(member(j):x(i,j)=1);for(member(j):sum(swim(i):x(i,j)1);for(match:bin(x);end 课后练习