《《纯形法的计算公式》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《纯形法的计算公式》PPT课件.ppt（23页珍藏版）》请在装配图网上搜索。
1、单 纯 形 法 的 矩 阵 描 述 单 纯 形 法 的 矩 阵 表 示标 准 型 m axZ=CX AX=b X 0已 知 ： A、 b、 c A=(B N) mnmmmmmmmm nmmm nmmm aaaaaa aaaaaa aaaaaaA 2121 2221222221 1211111211 mmmm mmaaa aaa aaaB 21 22221 11211 mnmmmm nmm nmm aaa aaa aaaN 21 22212 12111基 阵 非 基 阵 TmB xxxX 21 TnmmN xxxX 21 基向量 非基向量基 变 量 非 基 变 量 NBA NBXXXbAX bX
2、XNB NB bNXBX NB NB NXbBX NB NXBbBX 11 NBXXX N NX NXBbBX 11令 0NX则 01bBX 定 义 在 约 束 方 程 组 (2) 中 ， 对 于一 个 选 定 的 基 B， 令 所 有 的 非 基 变量 为 零 得 到 的 解 ， 称 为 相 应 于 基 B的 基 本 解 。 定 义 在 基 本 解 中 ， 若 该 基 本 解 满 足 非 负 约 束 ，即 ， 则 称 此 基 本 解 为 基 本 可 行 解 ，简 称 基 可 行 解 ； 对 应 的 基 B称 为 可 行 基 。01 bBXB基 本 解 中 最 多 有 m个 非 零 分 量 。
3、基 本 解 的 数 目 不 超 过 个 。 ! ! mnm nCm n NBNB NNNB NNBB NBNB XNBCCbBC XCNXBbBC XCXC XXCCCXZ )( )( ),( 11 11 01 bBXB 01 NBCC BNNBX若 B满 足 下 列 条 件 ， 称 为 最 优 基 称 为 最 优 解 等 式 右 边 b 基 变 量 XB 非 基 变 量 XNXB B 1b E B 1N检 验 数 CB B 1b(即 Z) 0 CN - CBB-1 N等 式 右 边 b 变 量 XXB B 1b B 1A检 验 数 CB B 1b(即 Z) C - CBB-1 A单 纯 形
4、表 矩 阵 形 式 （ P26）等 式 右 边 b 基 变 量 XB 非 基 变 量 XNXB b B N检 验 数 0 CB CN 或 者 C - CBB-1A= (CN CB )- CBB-1 (NB ) = (CN - CBB-1N, CB -CBB-1B)B-1A= B-1(N B )= (B-1N, B-1B)单 个 检 验 数 ： j = Cj - CBB-1 Pj 某 列 Pj = B-1 Pj 规 范 形 式 ：m axZ=CX AX bX0 m axZ=CX+0X AX+EX= bX, X0令 A=(A E) C=(C O)C- CB B-1 A=(C O)- CB B-1
5、(A E) =(C-CB B-1 A O-CB B-1 ) B -1 A= B-1(A E)=(B-1 A B-1 E) 单 纯 形 表 矩 阵 形 式 （ P43）CB B-1 bB-1 b C- CB B-1 A - CB B-1 B-1 A B-1CB B-1单 纯 形 算 子等 式 右 边 b 变 量 X 松 驰 变 量 XsXB B 1b B 1A B 1检 验 数 -C B B 1b(即 -Z) C- CB B 1A -CB B 1-Ys -Y 例 ： m axZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 Xj
6、0 ( j=15)P1 P2 P3 P4 P5 1 2 1 0 03 2 0 1 00 2 0 0 1A= (1)、 已 知 B= (P3 P4 P2) 验 证 ： 1 0 -10 1 -10 0 1/2B-1 = P5,求 1 , A ,(2)、 B= (P1 P4 P2) 验 证 ： 1 0 -1-3 1 20 0 1/2B-1 = P 5,求 3 , 4,P3 (1)、 1 =C1 - CB B-1P1 =40 -(0 0 5 0) = 40 -(0,0,25) =401 0 -10 1 -10 0 1/2 1 3 01 3 0P 5 = B-1P5 = 1 0 -10 1 -10 0
7、1/2 0 0 1 = -1 -1 1/2 A= C - CB B-1A=(40, 50, 0, 0, 0)- (0, 0, 50) =(40, 50, 0, 0, 0) -(0 0 25) = (40, 50, 0, 0, 0) -(0, 50, 0, 0, 25) = (40, 0, 0, 0, -25) 1 0 -10 1 -10 0 1/2 1 2 1 0 03 2 0 1 00 2 0 0 11 2 1 0 03 2 0 1 00 2 0 0 1 (2)、 3 = -40 ,4= 0 P5 = -1 2 1/2P3 = 1 -3 0 40 50 0 0 0 X1 X2 X3 X4 X
8、5CB XB 0 40 50 0 0 0 0 X3 30 1 2 1 0 0 0 X4 60 3 2 0 1 0 0 X5 24 0 (2) 0 0 1 XB 600 +40 0 0 0 -250 X 3 6 (1) 0 1 0 -1 0 X4 36 3 0 0 1 -1 50 X2 12 0 1 0 0 1/2 840 0 0 -40 0 1540 X1 6 1 0 1 0 -10 X4 18 0 0 -3 1 250 X2 12 0 1 0 0 1/2 B1-1B2-1B3-1 XB 975 0 0 -35/2 -15/2 040 X1 15 1 0 -1/2 1/2 0 0 X5 9 0
9、 0 -3/2 1/2 1 50 X2 15/2 0 1 3/4 -1/4 0 B4-11 0 00 1 00 0 1B1= (P3 P4 P5)= B1 -1 = 1 0 00 1 00 0 11 0 20 1 20 0 2B 2= (P3 P4 P2)= B2 -1 = 1 0 -10 1 -10 0 1/2 (1)、 只 须 存 贮 原 始 数 据 A、 B、 C， 每 步 需 知 B-1 。(2)、 每 步 必 须 计 算 的 数 据 检 验 数N = CBB-1N - CN CBB-1 =单 纯 形 乘 子 当 某 个 m +k 0时 ， 需 关 键 列 ： Pm +k = B-1P
10、m +k = a1m +kam m +k 基 变 量 XB = B-1b = b1bm由 、 ， 用 最 小 比 值 法 得 主 元 arm +k 主 元 已 知 ， 新 基 B确 定 。 返 回 (1) 例 :m axZ=6X1 +4X2 2X1 +3X2 1004X1 +2X2 120X1 =14X2 22X 1 X2 0 m axZ=6X1 +4X2 -MX6 -MX72X1 +3X2 +X3 = 1004X1 +2X2 +X4 = 120X1 +X6 =14X2 -X5+X7 =22X1 X7 0 6 4 0 0 0 - M - M X1 X2 X3 X4 X5 X6 X7CB XB
11、-36 M M +6 M +4 0 0 - M 0 00 X3 100 2 3 1 0 0 0 0 0 X4 120 4 2 0 1 0 0 0 -M X6 14 1 0 0 0 0 1 0 -M X7 22 0 1 0 0 -1 0 1C B XB 84-22M 0 M+4 0 0 -M 6-M 00 X3 72 0 3 1 0 0 -2 0 0 X4 64 0 2 0 1 0 -4 0 6 X1 14 1 0 0 0 0 1 0 -M X7 22 0 1 0 0 -1 0 1 CB XB 172 0 0 0 0 -4 6-M 4-M0 X3 6 0 0 1 0 3 -2 -3 0 X4 20 0 0 0 1 2 -4 -2 6 X1 14 1 0 0 0 0 1 0 4 X2 22 0 1 0 0 -1 0 1CB XB 180 0 0 -4/3 0 0 -M-10/3 -M0 X5 2 0 0 1/3 0 1 -2/3 -1 0 X 4 16 0 0 -2/3 1 0 -8/3 0 6 X1 14 1 0 0 0 0 1 0 4 X2 24 0 1 1/3 0 0 -2/3 -2 课 后 练 习 题 1.13 1.17
《纯形法的计算公式》PPT课件.ppt
