数学建模-线性规划

《数学建模-线性规划》由会员分享，可在线阅读，更多相关《数学建模-线性规划（32页珍藏版）》请在装配图网上搜索。

1、2021-5-25 课 件 1 线 性 规 划 数 学 建 模 与 数 学 实 验后勤工程学院数学教研室 2021-5-25 课 件 2 实 验 目 的实 验 内 容 2、 掌 握 用 数 学 软 件 包 求 解 线 性 规 划 问 题 。1、 了 解 线 性 规 划 的 基 本 内 容 。*2、 线 性 规 划 的 基 本 算 法 。5、 实 验 作 业 。3、 用 数 学 软 件 包 求 解 线 性 规 划 问 题 。1、 两 个 引 例 。4、 建 模 案 例 ： 投 资 的 收 益 与 风 险 2021-5-25 课 件 3 问 题 一 ： 任 务 分 配 问 题 ： 某 车 间 有

2、甲 、 乙 两 台 机 床 ， 可 用于 加 工 三 种 工 件 。 假 定 这 两 台 车 床 的 可 用 台 时 数 分 别 为 800和900， 三 种 工 件 的 数 量 分 别 为 400、 600和 500， 且 已 知 用 三 种不 同 车 床 加 工 单 位 数 量 不 同 工 件 所 需 的 台 时 数 和 加 工 费 用 如下 表 。 问 怎 样 分 配 车 床 的 加 工 任 务 ， 才 能 既 满 足 加 工 工 件 的要 求 ， 又 使 加 工 费 用 最 低 ？ 单 位 工 件 所 需 加 工 台 时 数 单 位 工 件 的 加 工 费 用 车 床 类 型 工 件

3、1 工 件 2 工 件 3 工 件 1 工 件 2 工 件 3 可 用 台 时 数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 两 个 引 例 2021-5-25 课 件 4 解 设 在 甲 车 床 上 加 工 工 件 1、 2、 3的 数 量 分 别 为 x1、 x2、 x3，在 乙 车 床 上 加 工 工 件 1、 2、 3的 数 量 分 别 为 x4、 x5、 x6。 可 建 立以 下 线 性 规 划 模 型 ： 654321 8121110913min xxxxxxz 6,2,1,0 9003.12.15.0 8001.14.

4、0 500600400 x . 654 321 63 52 41 ix xxx xxxxx xx xts i 解 答 2021-5-25 课 件 5 问 题 二 ： 某 厂 每 日 8小 时 的 产 量 不 低 于 1800件 。 为 了 进 行 质量 控 制 ， 计 划 聘 请 两 种 不 同 水 平 的 检 验 员 。 一 级 检 验 员 的 标 准为 ： 速 度 25件 /小 时 ， 正 确 率 98%， 计 时 工 资 4元 /小 时 ； 二 级 检验 员 的 标 准 为 ： 速 度 15小 时 /件 ， 正 确 率 95%， 计 时 工 资 3元 /小时 。 检 验 员 每 错 检

5、一 次 ， 工 厂 要 损 失 2元 。 为 使 总 检 验 费 用 最省 ， 该 工 厂 应 聘 一 级 、 二 级 检 验 员 各 几 名 ？解 设 需 要 一 级 和 二 级 检 验 员 的 人 数 分 别 为 x1、 x2人 ,则 应 付 检 验 员 的 工 资 为 ： 2121 24323848 xxxx 因 检 验 员 错 检 而 造 成 的 损 失 为 ： 2121 1282)%5158%2258( xxxx 2021-5-25 课 件 6 故 目 标 函 数 为 ： 212121 3640)128()2432(min xxxxxxz 约 束 条 件 为 ： 0,0 180015

6、8 1800258 1800158258 21 21 21xx xx xx 2021-5-25 课 件 7 线 性 规 划 模 型 ： 21 3640min xxz 0,0159 4535 . 2121 21 xxxx xxts 解 答返 回 2021-5-25 课 件 8 1.线 性 规 划 的 标 准 形 式 ：xmin z = )(xf.ts )(xgi 0 （ ),2,1 mi 其 中 目 标 函 数 )(xf 和 约 束 条 件 中 )(xgi 都 是 线 性 函 数 min f = c x s.t. A x = b （ 1） x 0 这 里 A = ( ija )m,n , x =

7、 T 21 nxxx b= T 21 nbbb , c= nccc 21 用 单 纯 法 求 解 时 ， 常 将 标 准 形 式 化 为 ：2. 线 性 规 划 的 基 本 算 法 单 纯 形 法线 性 规 划 的 基 本 算 法 单 纯 形 法 2021-5-25 课 件 9 例 min z = 10 x1 + 9x2 s t 6x1 + 5x2 60 10 x1 + 20 x2 150 x1 8 x1, x2 0引 入 松 弛 变 量 x3, x4, x5, 将 不 等 式 化 为 等 式 , 即 单 纯 形 标 准 形 : min z = 10 x1 + 9x2 s t 6x1 + 5x

8、2 + x3 = 60 10 x1 + 20 x2 - x4 = 150 x1 + x5 = 8 xi 0 (i = 1,2,3,4,5) 系 数 矩 阵 为 : 6 5 1 0 0 A = 10 20 0 -1 0 = (P1 P2 P3 P4 P5) 1 0 0 0 1 b = (60, 150, 8 ) T 显 然 A的 秩 ran(A)=3, 任 取 3个 线 性 无 关 的 列 向 量 ,如 P3 P4 P5称 为一 组 基 , 记 为 B. 其 余 列 向 量 称 为 非 基 , 记 为 N . 2021-5-25 课 件 10 于 是 f = cBxB + cNxN , Ax =

9、 BxB + NxN = b, 则 xB = B-1b-B-1NxN , f = cBB-1b + (cN cBB-1N)xN 令 非 基 变 量 xN = 0, 解 得 基 变 量 xB = B 1 b, 称 (xB, xN)为 基 解 . 基 解 的 所 有 变 量 的 值 都 非 负 ， 则 称 为 基 可 行 解 ， 此 时 的 基 称 为 可 行 基 . 若 可 行 基 进 一 步 满 足 : cN cBB-1N0, 即 : cBB-1N - cN0则 对 一 切 可 行 解 x, 必 有 f(x) cBB-1b, 此 时 称 基 可 行 解 x = (B-1b, 0) T为 最 优

10、 解 . 3. 最 优 解 的 存 在 性 定 理 将 A的 列 向 量 重 排 次 序 成 A = (B, N), 相 应 x = (xB, xN) T, c = (cB, cN)基 对 应 的 变 量 xB称 为 基 变 量 , 非 基 对 应 的 变 量 xN称 为 非 基 变 量 .定 理 1 如 果 线 性 规 划 (1)有 可 行 解 ， 那 么 一 定 有 基 可 行 解 .定 理 2 如 果 线 性 规 划 (1)有 最 优 解 ， 那 么 一 定 存 在 一 个 基 可 行 解 是 最 优 解 . 2021-5-25 课 件 11 4. 基 可 行 解 是 最 优 解 的 判

11、 定 准 则因 为 f = cBB-1b + (cN cBB-1N)xN，即 f - 0 xB + (cBB-1N- cN )xN = cBB-1b 若 基 B=( 1P , 2P , mP ), 非 基 N =( 1mP , 2mP , nP )， 令 j = Bc 1B jP - jc ， j=m+1,m+2, ,n ,则 (1) 可 写 成 min f s.t. Bx + 1B N Nx = 1B bf + 0 Bx + nmj jjx1 = Bc 1B b x 0 称 为 （ 1） 式 的 典 式 . 定 理 3 设 （ 1x , 2x , mx ） 是 规 划 (1) 的 一 个 可

12、 行 基 ， B是 对 应 的 基 阵 ,如 果 典 式 中 的 1 , 2 , m 都 不 大 于 零 ,即 对 应 的 1m 0, 2m 0, , n 0,则 基 （ 1x , 2x , mx ） 对 应 的 基 可 行 解 0X = 01bB 是 最 优 解 . 2021-5-25 课 件 12 令 1B b = m21 ， 1B N = nmmmmm nmm nmm ,2,1, ,22,21,2 ,12,11,1 5.基 可 行 解 的 改 进 线 性 规 划 （ 1） 的 典 式 变 为 ： min f s.t. ix + nmj jijx1 = i i=1,2, ,mf + 0 B

13、x + nmj jjx1 = Bc 1B b x 0 2021-5-25 课 件 13 定 理 4 设 （ 1x , 2x , mx ） 是 规 划 (1) 的 一 个 可 行 基 ，B 是 对 应 的 基 阵 ,如 果 存 在 km 0， 使 1) km,1 , km,2 , kmm , 中 至 少 有 一 个 大 于 零 ； 2) 所 有 的 i 0， i=1,2, ,m 则 一 定 存 在 另 一 个 可 行 基 ， 它 对 应 的 基 可 行 解 使 目 标 函 数 值 更 小 . 令 0 = kmi ikmi ,0,min = kml l, ,则 把 lx 从 原 有 的 基 中 取

14、 出 来 ， 把 kmx 加 进 后 得 到 的 （ 1x , 2x , lx , kmx , 1lx , mx ） 仍 是 基 ， 即 是 所 要 找 的 新 基 . 改 进 方 法 ： 返 回 2021-5-25 课 件 14 用 MATLAB优 化 工 具 箱 解 线 性 规 划min z=cX bAXts .1、 模 型 ：命 令 ： x=linprog（ c， A， b） 2、 模 型 ： min z=cX bAXts . beqXAeq 命 令 ： x=linprog（ c， A， b， Aeq,beq）注 意 ： 若 没 有 不 等 式 ： 存 在 ， 则 令 A= ， b= .

15、bAX 2021-5-25 课 件 15 3、 模 型 ： min z=cX bAXts . beqXAeq VLBXVUB命 令 ： 1 x=linprog（ c， A， b， Aeq,beq, VLB， VUB） 2 x=linprog（ c， A， b， Aeq,beq, VLB， VUB, X0） 注 意 ： 1 若 没 有 等 式 约 束 : , 则 令 Aeq= , beq= . 2其 中 X 0表 示 初 始 点 beqXAeq 4、 命 令 ： x,fval=linprog()返 回 最 优 解 及 处 的 目 标 函 数 值 fval. 2021-5-25 课 件 16 解

16、编 写 M文 件 xxgh1.m如 下 ：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) 例 1 max 654321 6.064.072.032.028.04.0 xxxxxxz 85003.003.003.001.

17、001.001.0. 654321 xxxxxxts 70005.002.0 41 xx 10005.002.0 52 xx 90008.003.0 63 xx 6,2,10 jxj To Matlab (xxgh1) 2021-5-25 课 件 17 例 2 321 436min xxxz 120. 321 xxxts 301 x 500 2 x 203 x解 : 编 写 M文 件 xxgh2.m如 下 ： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30,0,20; vub=; x,fval=linprog(c,A,b,Aeq,beq,v

18、lb,vub)To Matlab (xxgh2) 321)436(min xxxz 32120030 xxx 50120010 111 . 321xxxts 2021-5-25 课 件 18 S.t. Xz 8121110913min 9008003.12.15.0000 00011.14.0 X 500600400100100 010010 001001 X ， 0654 321 xxxxxxX 改 写 为 ：例 3 问 题 一 的 解 答 问 题 2021-5-25 课 件 19 编 写 M文 件 xxgh3.m如 下 :f = 13 9 10 11 12 8;A = 0.4 1.1 1

19、0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)To Matlab (xxgh3) 2021-5-25 课 件 20 结 果 :x = 0.0000 600.0000 0.0000 400.0000 0.0000 500.0000fval =1.3800e+004 即 在 甲 机 床 上 加 工 600个 工 件 2,在 乙 机 床 上

20、加 工 400个 工 件 1、500个 工 件 3， 可 在 满 足 条 件 的 情 况 下 使 总 加 工 费 最 小 为 13800。 2021-5-25 课 件 21 例 2 问 题 二 的 解 答 问 题 213640min xxz s.t. )45(35 2 1 xx改 写 为 ： 2021-5-25 课 件 22 编 写 M文 件 xxgh4.m如 下 ：c = 40;36;A=-5 -3;b=-45;Aeq=;beq=;vlb = zeros(2,1);vub=9;15; %调 用 linprog函 数 ：x,fval = linprog(c,A,b,Aeq,beq,vlb,vu

21、b)To Matlab (xxgh4) 2021-5-25 课 件 23 结 果 为 ：x = 9.0000 0.0000fval =360即 只 需 聘 用 9个 一 级 检 验 员 。 注 ： 本 问 题 应 还 有 一 个 约 束 条 件 ： x1、 x2取 整 数 。 故 它是 一 个 整 数 线 性 规 划 问 题 。 这 里 把 它 当 成 一 个 线 性 规 划 来解 ， 求 得 其 最 优 解 刚 好 是 整 数 ： x 1=9， x2=0， 故 它 就 是 该整 数 规 划 的 最 优 解 。 若 用 线 性 规 划 解 法 求 得 的 最 优 解 不 是整 数 ， 将 其

22、取 整 后 不 一 定 是 相 应 整 数 规 划 的 最 优 解 ， 这 样的 整 数 规 划 应 用 专 门 的 方 法 求 解 。 返 回 2021-5-25 课 件 24 投 资 的 收 益 和 风 险 一 、 问 题 提 出 市 场 上 有 n 种 资 产 is （ i=1,2n） 可 以 选 择 ， 现 用 数 额 为 M 的 相 当 大 的 资 金 作 一 个 时 期 的 投 资 。 这 n 种 资 产 在 这 一 时 期 内 购 买 is 的 平 均 收 益 率 为 ir， 风 险 损 失 率 为 iq ， 投 资 越 分 散 ， 总 的 风 险 越 小 ， 总 体 风 险 可

23、 用 投 资 的 is 中 最 大 的 一 个 风 险 来 度 量 。 购 买 is 时 要 付 交 易 费 ， (费 率 ip )， 当 购 买 额 不 超 过 给 定 值 iu 时 ， 交 易 费 按 购 买 iu 计 算 。 另 外 ， 假 定 同 期 银 行 存 款 利 率 是 0r ， 既 无 交 易 费 又 无 风 险 。 （ 0r =5%） 已 知 n=4 时 相 关 数 据 如 下 ：is ir （ %） iq （ %） ip （ %） iu （ 元 ） S1 28 2.5 1 103 S2 21 1.5 2 198 S3 23 5.5 4.5 52 S4 25 2.6 6.5

24、 40 试 给 该 公 司 设 计 一 种 投 资 组 合 方 案 ， 即 用 给 定 达 到 资 金 M， 有 选 择 地 购 买 若 干 种 资 产 或 存 银 行生 息 ， 使 净 收 益 尽 可 能 大 ， 使 总 体 风 险 尽 可 能 小 。 2021-5-25 课 件 25 基 本 假 设 ： 1. 投 资 数 额 M 相 当 大 ,为 了 便 于 计 算 ， 假 设 M=1； 2 投 资 越 分 散 ， 总 的 风 险 越 小 ； 3 总 体 风 险 用 投 资 项 目 is 中 最 大 的 一 个 风 险 来 度 量 ； 4 n 种 资 产 Si之 间 是 相 互 独 立 的

25、 ； 5 在 投 资 的 这 一 时 期 内 , ri,pi,qi， r0为 定 值 ， 不 受 意 外 因 素 影 响 ； 6 净 收 益 和 总 体 风 险 只 受 ri,pi,qi影 响 ， 不 受 其 他 因 素 干 扰 。 二 、 基 本 假 设 和 符 号 规 定 符 号 规 定 ： Si 第 i 种 投 资 项 目 ， 如 股 票 ， 债 券 ri,pi,qi -分 别 为 Si的 平 均 收 益 率 ,风 险 损 失 率 ， 交 易 费 率 ui -Si的 交 易 定 额 0r -同 期 银 行 利 率 xi -投 资 项 目 Si的 资 金 a -投 资 风 险 度 Q -总

26、 体 收 益 Q -总 体 收 益 的 增 量 2021-5-25 课 件 26 三 、 模 型 的 建 立 与 分 析1.总 体 风 险 用 所 投 资 的 Si中 最 大 的 一 个 风 险 来 衡 量 ,即 max qixi|i=1， 2,n 2 购 买 Si所 付 交 易 费 是 一 个 分 段 函 数 ,即 pixi xiui 交 易 费 = piui xi ui 而 题 目 所 给 定 的 定 值 ui(单 位 :元 )相 对 总 投 资 M很 小 , piui更 小 , 可 以 忽 略 不 计 ,这 样 购 买 Si的 净 收 益 为 (ri-pi)xi 3 要 使 净 收 益

27、尽 可 能 大 ， 总 体 风 险 尽 可 能 小 ,这 是 一 个 多 目 标 规 划 模 型 : 目 标 函 数 MAX ni iii xpr0 )( MINmax qixi 约 束 条 件 ni ii xp0 )1( =M xi 0 i=0,1,n4. 模 型 简 化 ： 2021-5-25 课 件 27c 投 资 者 在 权 衡 资 产 风 险 和 预 期 收 益 两 方 面 时 ， 希 望 选 择 一 个 令 自 己 满 意 的 投 资 组 合 。因 此 对 风 险 、 收 益 赋 予 权 重 s（ 0 s 1)， s称 为 投 资 偏 好 系 数 .模 型 3 目 标 函 数 ：

28、min smaxqixi -（ 1-s） ni iii xpr0 )( 约 束 条 件 ni ii xp0 )1( =M， xi 0 i=0,1,2,n b 若 投 资 者 希 望 总 盈 利 至 少 达 到 水 平 k 以 上 ， 在 风 险 最 小 的 情 况 下 寻 找 相 应 的 投 资 组 合 。模 型 2 固 定 盈 利 水 平 ， 极 小 化 风 险 目 标 函 数 ： R= minmax qixi 约 束 条 件 ： ni iii xpr0 )( k， Mxp ii)1( ， xi 0 i=0， 1， n a 在 实 际 投 资 中 ， 投 资 者 承 受 风 险 的 程 度

29、不 一 样 ， 若 给 定 风 险 一 个 界 限 a， 使 最 大 的 一 个风 险 q ixi/M a， 可 找 到 相 应 的 投 资 方 案 。 这 样 把 多 目 标 规 划 变 成 一 个 目 标 的 线 性 规 划 。模 型 1 固 定 风 险 水 平 ， 优 化 收 益 目 标 函 数 ： Q=MAX 11 )(ni iii xpr 约 束 条 件 ： Mxq ii a Mxp ii)1( ， xi 0 i=0， 1， n 2021-5-25 课 件 28 四 、 模 型 1的 求 解 模 型 1为 : minf = (-0.05, -0.27, -0.19, -0.185,

30、-0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.01x1 + 1.02x2 +1.045x3 +1.065x4 =1 s.t. 0.025x1 a 0.015x2 a 0.055x3 a 0.026x4 a xi 0 (i = 0,1,.4) 由 于 a是 任 意 给 定 的 风 险 度 ， 到 底 怎 样 给 定 没 有 一 个 准 则 ， 不 同 的 投 资者 有 不 同 的 风 险 度 。 我 们 从 a=0开 始 ， 以 步 长 a=0.001进 行 循 环 搜 索 ， 编制 程 序 如 下 ： 2021-5-25 课 件 29 a=0;while(1.1-a)

31、1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)， axis(0 0.1 0 0.5)， hold on a=a+0.001;end xlabel(a),ylabel(Q) To Matlab（ x

32、xgh5） 2021-5-25 课 件 30 a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.1266 a = 0.0060 x = 0 0.2400 0.4000 0.1091 0.2212 Q = 0.2019 a = 0.0080 x = 0.0000 0.3200 0.5333 0.1271 0.0000 Q = 0.2112 a = 0.0100 x = 0 0.4000 0.5843 0 0 Q =0.2190 a = 0.0200 x = 0 0.8000 0.1882 0 0 Q =0.2518 a = 0.040

33、0 x = 0.0000 0.9901 0.0000 0 0 Q =0.2673 计 算 结 果 ： 2021-5-25 课 件 31 五 、 结 果 分 析 返 回4.在 a=0.006附 近 有 一 个 转 折 点 ， 在 这 一 点 左 边 ， 风 险 增 加 很 少 时 ， 利 润 增 长 很 快 。 在 这 一 点 右 边 ， 风 险 增 加 很 大 时 ， 利 润 增 长 很 缓 慢 ， 所 以 对 于 风 险 和 收 益 没 有 特 殊 偏 好 的 投 资 者 来 说 ， 应 该 选 择 曲 线 的 拐 点 作 为 最 优 投 资 组 合 ， 大 约 是 a*=0.6%， Q*=

34、20% ， 所 对 应 投 资 方 案 为 : 风 险 度 收 益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.曲 线 上 的 任 一 点 都 表 示 该 风 险 水 平 的 最 大 可 能 收 益 和 该 收 益 要 求 的 最小 风 险 。 对 于 不 同 风 险 的 承 受 能 力 ， 选 择 该 风 险 水 平 下 的 最 优 投 资 组 合 。2.当 投 资 越 分 散 时 ， 投 资 者 承 担 的 风 险 越 小 ， 这 与 题 意 一 致 。 即 : 冒 险 的 投 资 者 会 出 现 集 中 投 资

35、 的 情 况 ， 保 守 的 投 资 者 则 尽 量 分 散 投 资 。1.风 险 大 ， 收 益 也 大 。 2021-5-25 课 件 32 实 验 作 业 某 厂 生 产 甲 乙 两 种 口 味 的 饮 料 ,每 百 箱 甲 饮 料 需 用 原 料 6千 克 ,工 人 10名 ,可 获 利 10万 元 ;每 百 箱 乙 饮 料 需 用 原 料 5千 克 ,工 人 20名 ,可 获 利 9万 元 .今 工 厂 共 有 原 料 60千 克 ,工 人 150名 ,又 由 于 其他 条 件 所 限 甲 饮 料 产 量 不 超 过 8百 箱 .问 如 何 安 排 生 产 计 划 ,即两 种 饮 料 各 生 产 多 少 使 获 利 最 大 .进 一 步 讨 论 : 1)若 投 资 0.8万 元 可 增 加 原 料 1千 克 ,问 应 否 作 这 项 投 资 . 2)若 每 百 箱 甲 饮 料 获 利 可 增 加 1万 元 ,问 应 否 改 变 生 产 计 划 .返 回