《矩阵分析建模》PPT课件

《《矩阵分析建模》PPT课件》由会员分享，可在线阅读，更多相关《《矩阵分析建模》PPT课件（80页珍藏版）》请在装配图网上搜索。

1、第 四 章 矩 阵 分 析 方 法 建 模 4.1 循 环 联 赛 的 奖 金 分 配 及 排 名 次 问题 4.2 有 限 网 络 的 一 些 有 趣 问 题 4.3 数 据 处 理 的 一 些 有 趣 问 题 4.1 循 环 联 赛 的 数 学 建 模 问 题 随 着 人 们 生 活 水 平 的 提 高 ,人 们 不 但 喜爱 体 育 ,而 且 喜 爱 体 育 比 赛 ,出 现 千 千 万万 的 各 种 体 育 比 赛 迷 . 随 着 我 国 经 济 的 迅 速 崛 起 ,各 种 超 级 联赛 也 应 运 而 生 .大 型 赛 事 常 常 是 人 们 饭后 茶 余 的 主 要 话 题 .

2、体 育 比 赛 中 也 有 数 学 建 模 问 题 ,本 节 就来 介 绍 ,循 环 联 赛 的 奖 金 分 配 及 排 名 次所 涉 及 的 数 学 建 模 问 题 . A 循 环 联 赛 的 奖 金 分 配 问 题背 景 已 有 多 年 循 环 比 赛 历 史 的 n支 球 队 :T1,T2,Tn 今 年 照 例 举 行 无 平 局 的 循 环 联 赛 ,约 定按 下 列 规 则 发 放 奖 金 :规 则 战 胜 Ti得 奖 金 xia 元 ,a 为 待 定 的 奖 金单 位 (换 句 话 说 ,战 胜 各 队 奖 金 按 比 例 x1:x2: :xn发 放 ).问 题 如 何 合 理 地

3、 决 定 奖 金 (系 数 )向 量 x=(x1,x2,xn)T(准 确 到 相 差 正 因 子 a),使 对 每 一 队 来 说 都 保 持 公 平 ? 问 题 分 析 与 假 设 奖 金 向 量 的 公 平 性 体 现 在 : Ti越 强 xi越 大 . (战 胜 强 队 是 衡 量 球 队 发 挥 好 的 标 志 ) 各 队 强 弱 程 度 用 胜 负 概 率 矩 阵 F=(fij) 来 刻 画 ,fij 表 示 过 去 Ti 战 胜 Tj 的 概 率 . 假 设 : n 个 队 中 没 有 特 别 强 或 特 别 弱 的队 (否 则 该 队 早 已 升 级 或 降 级 离 开 了 ),

4、即i,j,0fij()0;非 负 方 阵 A 称 为 本 原 矩 阵 ,如 果 存 在 正 整 数 m 使 得 Am 为 正 矩 阵 .定 理 4.1:任 意 本 原 矩 阵 A都 恰 有 一 个 正 特 征值 r(A),其 值 大 于 其 它 特 征 值 的 模 数 (故r(A)为 单 特 征 值 ,任 意 两 个 对 应 于 它 的特 征 向 量 都 线 性 相 关 ),并 且 存 在 对 应 于 r(A)的 正 特 征 向 量 x.定 理 4.2:当 n3时 ,奖 金 分 配 问 题 中 定 义 的矩 阵 A 是 本 原 矩 阵 ,并 且 r(A)=1. 定 理 4.2 的 证 明定 理

5、 4.2: 奖 金 分 配 问 题 中 定 义 的 矩 阵 A 是 本 原 矩 阵 ,并 且 r(A)=1.证 : 因 ij,aij=fij/ui 0,故 当 n3时 , A2 是 一 个 正 矩 阵 ,即 A 是 本 原 矩 阵 . 从 而 ,按 定 理 4.1,有 对 应 于 r(A)的 正 特征 向 量 x: Ax=r(A)x.令 v=(u1,un)T,则 vTA = vT. 于 是 vTx = vTAx = r(A)vTx. 因 v Tx 0,由 上 式 推 出 r(A)=1. A2=AA=vTA=(u1,un) f11/u1 f1n/u1 fn1/un fnn/un =(u1,un)

6、=vT其 中 ,ui=j=1nfji0 00 00 0 求 奖 金 向 量 方 法 与 例方 法 : 首 先 由 历 史 记 录 确 定 胜 负 概 率 矩 阵 F; 其 次 由 F 确 定 矩 阵 A; 最 后 由 适 当 数 学软 件 ,例 如 ,Matlab,求 出 对 应 于 A 的 特征 值 1的 任 一 个 正 特 征 向 量 x,则 此 向 量 x 可 取 为 合 理 的 奖 金 向 量 . 对 于 前 面 讨 论 的 例 1:我 们 首 先 由 胜 负 概 率矩 阵 F求 得 矩 阵 A为 : A = 其 次 ,利 用 数 学 软 件 Matlab 的 行 命 令 :A=0,6

7、/7,1;2/7,0,1/7;1/3,8/9,0;V,D=eig(A)(D的 对 角 元 是 特 征 值 ,V的 第 i列 是 对 应 第 i特 征值 的 正 特 征 向 量 )求 得 对 应 于 A的 最 大 特 征 值为 1,对 应 于 1的 一 个 正 特 征 向 量 是 :x T=(0.7910,0.3020,0.5321),这 个 正 向 量 就 是 我 们 要 求 的 奖 金 向 量 .0 6/7 12/7 0 1/71/3 8/9 0 方 法 : 设 奖 金 总 额 预 算 值 为 S,则由 上 式 立 即 求 得 a=S/(x1u1+xnun).对 例 1有 a=S/(0.79

8、100.7+0.30201.4+0.53210.9)=S/1.455.如 何 由 奖 金 总 额 决 定 奖 金 单 位 ?1 1 1( )n n nij j j jj i jS f x a u x a 例 如 对 例 1有 a=S/1.455. 如 果 循 环 联 赛 组 委 会 的 奖 金 总 额 预 算 为 3万 元 左 右 时 ,S=3(万 ).则 a=3/1.455=2.062.所 以 ,战 胜 T1得 奖 金 x1a=0.7912.062=1.631(万 元 );战 胜 T2得 奖 金 x2a=0.3022.062=0.623(万 元 );战 胜 T3得 奖 金 x3a=0.532

9、2.062=1.097(万 元 ).注 :此 三 数 之 和 为 3.35万 ,并 不 正 好 是 3万 .如 果 强 队 均 输 ,则 奖 金 总 数 为 : 21.631+1.097=4.36(万 元 );如 果 弱 队 均 输 ,则 奖 金 总 数 为 20.623+1.097=2.34(万 元 ),它们 的 平 均 值 正 是 3.35万 元 . B 循 环 联 赛 各 队 排 名 次 问 题 背 景 已 有 多 年 循 环 比 赛 历 史 的 俱 乐 部 欲 为所 属 n支 球 队 :T1,T2,Tn按 强 弱 排 名 次 . 方 法 首 先 制 定 评 分 标 准 ,即 确 立 评

10、 分 向 量u=(u1,un),uj的 意 义 是 每 个 战 胜 Tj的 队都 得 分 uj;其 次 根 据 胜 负 概 率 矩 阵 F=(fij)和评 分 向 量 u计 算 各 队 的 得 分 向 量 v=(v1,vn)其 规 则 是 : 规 则 vi=j=1nfijuj, i=1,n 或 v=Fu (1) 问 题 如 何 决 定 向 量 u(从 而 v),使 对 每 一 队都 保 持 公 平 ? 问 题 分 析 与 假 设公 平 地 决 定 向 量 v=(v1,vn)和 u=(u1,un)体 现 在 :v1: :vn=u1: :un,或 存 在 正 数满 足 =v1/u1=vn/un 即

11、 v=u. (2) 将 (2)代 入 (1)得 Fu=u. (3)结 论 :胜 负 概 率 矩 阵 F是 本 原 矩 阵 (F2为 正 矩阵 ),从 而 由 前 面 的 定 理 4.1,F恰 有 一 个 正特 征 值 ,其 所 对 应 的 任 何 正 特 征 向 量 (只有 倍 数 差 别 )都 可 取 为 得 分 向 量 v或 评 分 向量 u.因 向 量 v与 u相 差 正 常 数 倍 ,故 可 按 u的各 分 量 的 大 小 为 各 队 排 名 次 . 例 1例 1:我 们 有 胜 负 概 率 矩 阵 利 用 Matlab的 下 列 行 命 令 :F=0,0.6,0.7;0.4,0,0.

12、2;0.3,0.8,0;V,D=eig(F)求 得 对 应 于 F的 正 特 征 值 0.9414的 一 个 特 征向 量 是 :vT=(0.6985,0.4199,0.5794), 此 向 量 v即 可 取 为 我 们 要 求 的 得 分 向 量 .按 v的 分 量 的 大 小 为 各 队 排 名 次 的 结 果 是 : T 1, T3, T2F= 0 0.6 0.70.4 0 0.20.3 0.8 0 也 可 用 奖 金 向 量 为 各 队 排 名 次例 1:由 合 理 奖 金 向 量 xT=(x1,xn)的 性 质知 :对 任 二 球 队 Ti和 Tj都 有xixj Ti比 Tj强 .因

13、 此 ,也 可 按 x1,xn的 大 小 为 各 队 排 名 次 .例 如 ,对 于 例 1我 们 已 求 得 合 理 的 奖 金向 量 为 xT=(0.7910,0.3020,0.5321).按 x的 分 量 的 大 小 为 各 队 排 名 次 的 结 果 是 :T 1, T3, T2. 这 个 结 果 与 前 面 按 得 分 向 量 v的 分 量 的 大小 为 各 队 排 名 次 的 结 果 相 一 致 的 事 实 也说 明 我 们 以 上 的 分 析 是 正 确 的 . 如 果 要 对 这 两 个 方 法 进 行 评 优 的 话 ,应 该说 ,本 节 的 方 法 较 优 ,因 为 此 方

14、 法 直 接 利用 矩 阵 F即 可 求 出 结 果 ,而 用 上 节 的 方 法 ,则 还 需 要 从 F再 计 算 矩 阵 A的 额 外 工 作 量 .两 个 方 法 的 比 较 一 个 实 例 :下 表 为 某 个 俱 乐 部 的 4支 足 球队 的 比 赛 记 录 ,试 用 本 节 方 法 为 这 4支 球 队排 名 次 . T2 T3 T43:0, 1:1, 2:2 2:1, 2:3, 0:0 2:1, 3:1 T11:4 3:1, 2:3 T25:2, 4:2 T3规 定 fij=0.6uij+0.4vij,uij为 平 均 场 分 ;vij为 平 均 进 球 分 . 场 分 :胜

15、 2,平 1,负 0;进 球 分 :进 一 球 1分 .例 如 ,u21=(2+1+1)/(2+2+2)=2/3(每 场 总 分 是 2), v21=(3+1+2)/(3+2+4)=2/3; f 21=0.6 u21+0.4 v21=2/3.f12=1-f21=1-2/3=1/3. T2 T3 T43:0, 1:1, 2:2 2:1, 2:3, 0:0 2:1, 3:1 T11:4 3:1, 2:3 T25:2, 4:2 T3u42=(2+0)/(2+2)=1/2,v42=(3+2)/(4+5)=5/9 f 42=(3/5)(1/2)+(2/5)(5/9)=47/90 f24=1-f42=43

16、/97再 如 ,u31=(2+0+1)/(2+2+2)=1/2(每 场 总 分 是 2), v31=(2+2+0)/(3+5+0)=1/2; f31=0.6 u31+0.4v31=1/2.f13=1-f31=1-1/2=1/2. 0 1/3 1/2 4/352/3 0 23/25 43/901/2 2/25 0 8/6531/35 47/90 57/65 0U=(0.329,0.617,0.242,0.673)T,用 它 为 各 队 排 名 次 得 : T4,T2,T1,T3其 次 用 Matlab算 出 矩 阵 F的 对 应 于 唯 一 正特 征 值 1.2263的 一 个 正 特 征 向

17、量 是 :首 先 请 大 家 验 证 矩 阵 F有 如 下 数 值 : F= G 123 4 657 9812 543G=V,E,V=1,2,3,4,5,E=(1,2),(1,5),(2,3), (2,5),(3,4),(4,5) 4.2 有 限 网 络 的 一 些 有 趣 问 题计 算 机 网 ,交 通 网 ,灌 溉 网 ,输 电 网 ,电 话 网 等 都是 常 见 的 有 限 网 络 .有 限 网 络 的 数 学 模 型 是 有 限 无 向 图 .无 向 图 G是一 个 二 重 组 :G=V,E,其 中 V是 非 空 有 限 集 合 ,它 的 元 素 称 为 结 点 ,E也 是 (非 空

18、)有 限 集 合 ,它 的 元 素 称 为 边 .图 G的 边 e是 一 个 结 点 二 重组 :e=(a,b),a,bV,称 e与 a,b关 联 ,或 a,b与e关 联 ,或 a与 b相 邻 接 .无 向 图 可 用 一 些 点 和连 接 两 点 间 的 连 线 (边 )的 一 个 图 形 来 表 示 .本 节 将 讨 论 关 于 有 限 网 络 的 两 个 有 趣 问 题 . 问 题 10 11 1 1 11 111000 0 00 000 0背 景 :设 有 限 网 络 的 各 点 仅 取 0或 1两 种 状 态 ;开始 时 刻 每 点 都 取 0 ;以 后 每 一 步 ,在 上 一步

19、基 础 上 作 如 下 的 状 态 改 变 :从 各 点 中 任 选一 点 令 其 改 变 状 态 ,同 时 也 令 与 此 点 相 邻 接的 所 有 结 点 改 变 状 态 .例 1:下 列 5点 网 络 前 几 次 状 态 改 变 情 况 如 下 : 问 题 1:对 任 何 网 络 是 否 总 能 经 有 限 次 改变 状 态 后 使 网 络 从 全 0 状 态 变 为 全 1 状 态 ? 这 里 网 络 的 “ 任 意 性 ” 适 用 于 有 任 意(有 限 )数 目 结 点 并 且 这 些 结 点 可 任 意 邻 接的 网 络 .不 言 而 喻 ,这 问 题 的 肯 定 答 案 ,将

20、是一 个 有 理 论 和 应 用 价 值 的 有 趣 结 果 . 问 题 1在 一 些 情 况 下 具 有 明 确 的 实 际 意 义 .例 如 :如 果 所 考 虑 的 网 络 代 表 某 些 装 置 的电 路 网 络 ; 0 , 1 分 别 代 表 装 置 的关 机 ,开 机 状 态 . 则 问 题 1的 意 义 是 :每 一次 选 定 一 个 装 置 令 它 及 与 之 相 关 联 的 装置 都 改 变 状 态 ,能 否 经 有 限 次 改 变 后 ,能使 任 何 此 类 装 置 网 络 从 开 始 时 全 部 关 机都 能 过 渡 到 全 部 开 机 ?问 题 1的 实 际 意 义 数

21、 学 建 模 准 备用 (0,1)向 量 描 述 网 络 状 态 :第 k次 改 变 结 束 时 ,网 络 状 态 用 向 量 x(k)=(x1(k),xn(k)T表 示 ,其 中 ,xi(k)=0或 1表 示 第 k次 改 变 结 束 时 网 络的 第 i个 结 点 的 状 态 是 0 或 1 .(例 1结 点 编 号 办 法 ： 最 上 面 结 点 编 号 为 1,并 按 反时 针 顺 序 把 其 余 点 依 次 标 号 为 2,3,4,5.)例 1:x(0)=(0,0,0,0,0)T,x(1)=(1,1,0,0,1)T, x(2)=(0,0,1,0,0)T,x(3)=(1,1,1,1,1

22、)T. 关 键 是 :寻 求 x(k)与 x(k+1)的 关 系 .如 能 得 到从 x(k)计 算 x(k+1)的 公 式 ,则 问 题 的 解 决 就有 了 办 法 . 作 网 络 的 邻 接 矩 阵 A=(aij),aij=0或 1(A是对 称 矩 阵 ),由 结 点 i与 结 点 j邻 接 或 不 邻 接而 定 ;并 令 i,aii=1. 对 例 1得1 1 0 0 11 1 1 0 10 1 1 1 00 0 1 1 11 1 1 1 1A =令 ei表 示 第 i个 元 素 为 1其 余 元 素 为 0的 n维列 向 量 (n阶 单 位 矩 阵 第 i列 ),则 Aei表 示 A的

23、 第 i列 . 易 见 : 1 423 5 x(1)=(1,1,0,0,1)T=(0,0,0,0,0)T+(1,1,0,0,1)T =x(0)+Ae1 (第 1次 选 择 了 第 1点 ); x(2)=(0,0,1,0,0)T=(1,1,0,0,1)T+(1,1,1,0,1)T =x(1)+Ae2 =x(0)+A(e1+e2) (第 2次 选 择 了 第 2点 ,取 按 位 加 :1+1=0); x(3)=(1,1,1,1,1)T=(0,0,1,0,0)T+(1,1,0,1,1)T =x(2)+Ae5=x(0)+A(e1+e2+e5). (第 3次 选 择 了 第 5点 ) 命 题 1 x(k

24、+1)=x(k)+Aeu(即 x(k)与 A的 第 u列 按 位加 ),这 里 ,u是 第 k次 选 定 点 的 序 数 .证 :Aeu为 A的 第 u列 ,x(k)+Aeu的 第 i元 是 x(k)的与 Aeu的 第 i元 的 按 位 加 ,注 意 当 Aeu的 第 i元是 0时 ,表 示 第 i结 点 与 选 定 的 第 u结 点 不 相邻 ,按 我 们 的 规 则 ,第 i点 保 持 原 状 态 ,即 与第 k次 的 状 态 相 同 ,这 正 与 按 位 加 法 性质 :” 0加 何 数 仍 为 何 数 ” 的 结 论 相 一 致 ; 当 Aeu的 第 i元 是 1时 ,表 示 第 i结

25、 点 与 选 定 的第 u结 点 相 邻 (规 定 :每 个 结 点 都 与 自 己 相邻 ),按 我 们 的 规 则 ,第 i点 要 改 变 状 态 ,即 与第 k次 的 状 态 不 同 ,这 正 与 按 位 加 法 性 质 : 1+0=1,1+1=0 的 结 论 相 一 致 . 结 论命 题 2: 令 e表 示 元 素 全 为 1的 n维 列 向 量 .如 果 方 程 0+ Ax=e 在 2元 域 Z2 中 有 解x=ei1+ei2+eim,则 依 次 选 点i1,i2 ,im 让 网 络 作 m次 改 变 状 态 ,可使 网 络 从 全 0状 态 变 为 全 1状 态 .注 :由 于 域

26、 Z2中 加 法 是 可 交 换 的 ,故 结 果 只与 此 m个 点 有 关 ,而 与 选 择 他 们 的 顺 序无 关 ,即 按 任 意 顺 序 选 择 此 m个 点 ,让 网络 作 m次 改 变 状 态 ,其 结 果 都 可 使 网 络变 为 全 1状 态 .请 你 对 例 1作 一 个 试 验 . 2元 域 定 义 为 代 数 系 统 :Z2 =0,1,+,其 中 加 法 定 义 为 0+1=1+0=1;1+1=0+0=0 乘 法 定 义 为 01=10=00=0;11=1易 见 :0,1关 于 上 述 加 法 ,乘 法 构 成 交 换 群 ;满足 加 法 ,乘 法 的 分 配 律 ;

27、并 且 非 0元 (1)有 乘 法逆 元 (1),所 以 ,Z2是 一 个 域 .可 以 象 实 矩 阵 一 样 ,定 义 Z2上 的 矩 阵 (元 素 取 值于 Z2的 矩 阵 )及 其 加 ,乘 法 运 算 ,只 须 注 意 两点 : 1+1=0; 运 算 结 果 是 Z2上 的 矩 阵 .Z2上 的 线 性 方 程 组 的 理 论 与 实 线 性 方 程 组 的 理论 完 全 类 似 .解 法 也 差 不 多 .这 个 只 有 两 个 元素 的 有 限 域 ,在 许 多 领 域 都 有 重 要 应 用 . 算 法目 的 :寻 求 方 程 Ax=e在 2元 域 Z2中 的 解 x.算 法

28、:为 在 域 Z2中 解 线 性 方 程 组 Ax=e,我 们 把 增 广矩 阵 (A e)用 域 Z2中 初 等 行 变 换 (仅 两 类 ,即 ,交 换 两 行 ;和 把 一 行 加 到 另 一 行 ),化 为 的 形 式 ,其 中 rn(r=rank(A)矩 阵 F的 每 行 恰有 一 个 1,并 分 别 属 于 不 同 的 列 ;u为 r维 列 向量 ;v为 nr维 列 向 量 .若 r=0或 v0,则 Ax=e无解 (增 广 矩 阵 的 秩 大 于 系 数 矩 阵 的 秩 );否 则 , x=(u,v) T即 为 所 要 求 的 解 . 0F uv 1 1 0 0 1 11 1 1

29、0 1 10 1 1 1 0 10 0 1 1 1 11 1 0 1 1 1(Ae) = 1 1 0 0 1 10 0 1 0 0 00 1 1 1 0 10 0 1 1 1 10 0 0 1 0 01 1 0 0 1 10 1 1 1 0 10 0 1 0 0 00 0 0 1 0 00 0 1 1 1 1 1 1 0 0 1 10 1 1 1 0 10 0 1 0 0 00 0 0 1 0 00 0 0 0 1 1 1 0 0 0 0 10 1 0 0 0 10 0 1 0 0 00 0 0 1 0 00 0 0 0 1 1交换 上 三 角 阵 对 角 矩 阵 | x1 1 0 0 11

30、1 1 0 1 0 1 1 1 00 0 1 1 11 1 0 1 1邻 接 矩 阵 : 23 451 例 1 思 考 题 4-1:对 开 始 为 全 0状 态 的 下 列 网络 ,如 何 选 一 些 结 点 ,每 次 改 变 一 点 状 态 ,使 网 络 最 后 变 为 全 1状 态 ?你 能 编 一 个(例 如 Matlab)程 序 求 解 有 关 方 程 组 吗 ?123 4 657 98 Ax=e在 域 Z2中 恒 有 解证 :由 数 域 Z2上 线 性 方 程 组 一 般 理 论 知 : Ax=e在 域 Z2上 无 解 当 且 仅 当 在 Z2中 该 方 程 组 可经 初 等 变 换

31、 化 为 0=1的 矛 盾 方 程 *.因 此 ,若此 方 程 组 无 解 ,则 把 它 的 一 些 方 程 ,不 失 一般 性 ,可 假 设 为 前 k个 方 程 加 到 一 起 会 得 到矛 盾 方 程 :0=1.于 是 有i=1kaij=0,j=1,n,1=1+1+1(共 k个 ).因 此 ,k是 奇 数 ,和 i=1kj=1kaij=0 (*)但 由 于 A是 对 角 元 全 为 1的 对 称 矩 阵 和 k是 奇 数 ,又 推 出 (*)式 左 边 等 于 1的 矛 盾 . Ax=e在 域 Z 2上 不 可 能 无 解 . 有 关 理 论 说 明 域 Z2上 的 线 性 方 程 组

32、有 解 的 充 要 条 件 是 增 广 矩阵 与 系 数 矩 阵 的 秩 相 等 . Ax=e在 上 无 解 当 且 仅 当 在 Z2中 该 方 程 组 可 经 初等 变 换 化 为 0=1的 矛 盾 方 程 .证 充 分 性 显 然 . 必 要 性 : 用 Z2中 适 当 初 等 行 变 换 一 定 能 将 原 方 程组 等 价 地 变 换 为 形 如 Ax=(1,0,0)T的 方 程 组 .若原 方 程 组 无 解 ,则 此 方 程 组 的 增 广 矩 阵 的 秩 大 于系 数 矩 阵 A的 的 秩 r,由 此 推 出 :1rn,从 而 A的 第1行 是 其 第 i1,ir行 的 线 性

33、组 合 ,换 句 话 说 ,A的第 1行 与 这 r行 之 和 是 0.于 是 ,将 上 述 方 程 组 的 第 1,第 i 1,ir个 方 程 相 加 就 能 产 生 一 个 左 端 不 出 现任 何 未 知 变 元 同 时 右 端 出 现 1的 矛 盾 方 程 . 矩 阵 A是 对 称 的 蕴 涵 其 非 0对 角 元 的 个 数必 为 偶 数 .(*)式 左 边 等 于 A的 前 k行 k列的 非 0元 之 和 在 Z2中 的 值 .因 为 ,在 这 里非 0元 就 是 1;对 角 元 全 为 1;并 且 k是 奇数 .所 以 ,(*)式 左 边 等 于 奇 数 个 1在 Z2中之 和

34、,此 值 必 等 于 1. 应 用 于 问 题 1得 出 的 结 论结 论 : 对 任 意 有 限 网 络 ,适 当 依 次 选 点 作 有 限 次改 变 状 态 ,都 可 使 网 络 从 全 0状 态 变 为 全1状 态 . 思 考 题 4-2:对 任 意 有 限 网 络 及 任 意 初 始状 态 ,适 当 依 次 选 点 作 有 限 次 改 变 状 态都 可 使 网 络 变 为 全 1状 态 吗 ? (提 示 :以下 列 网 络 为 例 ,考 虑 你 的 答 案 .) 从 任 意 状 态 变 为 全 1状 态 的 讨 论 由 思 考 题 4-2知 :一 般 不 能 保 证 从 任 意 状态

35、 都 能 变 为 全 1状 态 .自 然 要 提 出 问 题 :网 络 满 足 什 麽 条 件 ,才 能 保 证 从 任意 初 始 状 态 出 发 ,都 能 经 有 限 次 按 规 则改 变 状 态 后 达 到 全 1状 态 ?(等 价 于 :从 任意 初 始 状 态 开 始 变 到 任 意 指 定 的 状 态 结束 ) 利 用 前 面 建 立 的 数 学 模 型 不 难 找 到 我 们需 要 的 答 案 ,其 理 论 依 据 是 下 面 的 定 理4.3. 二 元 域 Z2上 线 性 方 程 组 的 一 个 定 理定 理 .3 在 二 元 域 Z2上 ,若 detA0,则 线 性 方程 组

36、Ax=b对 任 意 右 端 b恒 有 唯 一 解 .证 :设 detA0,对 线 性 方 程 组 Ax=b的 系 数 矩 阵 施 行 Z2中 行 初 等 变 换 (仅 两 类 ),任 何 时 候 都不 会 变 出 零 列 ,否 则 ,令 变 换 矩 阵 的 乘 积 为 P便 有 det(PA)=0蕴 涵 detA=0的 矛 盾 .因 此 ,对 增 广 矩 阵 (A b)在 Z2中 施 行 行 初 等 变换 ,一 定 可 化 为 (E x)的 形 式 (E为 单 位 矩阵 ),从 而 ,所 唯 一 确 定 的 x就 是 该 方 程 组 的唯 一 解 . 也 可 用 二 元 数 域 Z2上 的 矩

37、 阵 理 论 证 明 定理 4.3,其 要 点 如 下 : 按 Z2上 的 矩 阵 理 论 ,当 detA0时 ,A在 Z2上有 逆 矩 阵 A-1,满 足 :A-1是 Z2上 的 矩 阵 ,并且 A-1A=E.以 A-1左 乘 线 性 方 程 组 Ax=b的两 端 即 得 x=A-1b.这 就 证 明 了 ,Ax=b对 任 意 右 端 b恒 有 唯 一 解A-1b. 应 用 举 例例 如 ,对 于 例 1中 的 网 络 ,我 们 知 道 它 的 系数 矩 阵 A,经 Z2中 行 初 等 变 换 可 以 化 为 下列 矩 阵 :由 此 可 以 断 定 detA=10,从 而 按 定 理 4.3

38、,此 网 络 无 论 从 任 何 指 定 状 态 开 始 ,经 有限 次 改 变 状 态 都 可 以 变 到 全 1状 态 . 10000 01000 00100 01110 10011 1 1 0 0 1 1 1 0 0 1 1 1 0 0 11 1 1 0 1 0 0 1 0 0 0 1 1 1 00 1 1 1 0 0 1 1 1 0 0 0 1 0 00 0 1 1 1 0 0 1 1 1 0 0 0 1 01 1 0 1 1 0 0 0 1 0 0 0 1 1 11 1 0 0 10 1 1 1 00 0 1 0 00 0 0 1 00 0 0 0 1A 12 3 45 例 1的 几

39、 个 不 同 初 始 状 态例 如 , 选 第 1,3,4,5四 个 结 点 作 四 次 状 态 改变 ,可 使 例 1中 的 网 络 从 状 态 变 为 全 1状 态 ； 选 第 1,2,3,4,5五 个 结 点 作五 次 状 态 改 变 ,可 使 例 1中 的 网 络 从 状 态 变 为 全 1状 态 ； 等 等 。 (1,0,1,0,0)T(0,1,0,0,1) T 1 001 01 101 0 1 0 11 111000 10 0 01 问 题 2 背 景 :设 有 限 网 络 的 各 点 仅 取 + 或 - 两 种 状 态 ;已 知 其 开 始 时 刻 每 点 的状 态 ;以 后 按

40、 下 列 规 则 ,定 时 改 变 网 络 的状 态 . 规 则 :对 于 每 点 ,若 上 一 时 刻 其 邻 点 取 + ,取 - 的 数 目 相 同 时 维 持 原 状态 ;否 则 ,将 此 点 改 变 为 其 多 数 邻 点 的 状态 . + + + - - + + + + + +- - + +- - + +- - + +- -变 化 规 律 : 例 1趋 于 稳 定 ,例 2趋 于 交 叉 循 环 .自 然 要 问 :对 任 意 网 络 和 任 意 初 始 状 态 ,是否 都 有 这 个 变 化 规 律 ,即 :不 是 趋 于 稳 定 ,便是 趋 于 交 叉 循 环 ?例 1例 2

41、问 题 2:对 任 何 网 络 和 任 意 初 始 状 态 ,是 否总 会 趋 于 稳 定 或 趋 于 交 叉 循 环 ? 换 句 话 说 ,是 否 总 是 成 立 :当 k充 分 大 时 ,第 k+2时 刻 的 状 态 恒 与 第 k时 刻 的 状 态 相同 ?试 对 你 的 结 论 给 出 严 格 证 明 . 数 学 建 模 准 备 用 (1,-1)向 量 描 述 网 络 状 态 :第 k 次 改 变 后 ,网 络 状 态 用 (行 )向 量 x(k)=(x1(k),xn(k)表 示 ,其 中 ,xi(k)=1或 -1表 示 第 k次 改 变 后 网络 的 第 i个 结 点 的 状 态 是

42、 ” +” 或 ” -” . 例 1:将 该 网 络 的 最 上 面 一 结 点 编 号 为 1,并按 反 时 针 顺 序 把 其 余 结 点 标 号 为 2,3,4, 5,则 x(0)T=(1,-1,1,1,-1), x(1)T=(-1,1,1,1,1), x(2)T=(1,1,1,1,1)=x(k)T,k=3,4, 数 学 建 模问 题 2的 数 学 模 型 归 结 为 证 明 定 理 4:对 任 何 网 络 和 任 意 初 始 状 态 都 存 在正 整 数 N,使 得 kN,x(k+2)=x(k).(例 如 ,对 例 1,N=2;对 例 2,N=0.) 分 析 与 证 明 关 键 仍 是

43、 求 x(k+1)与 x(k)间 的 关 系 ,与 前面 一 样 ,需 要 巧 妙 地 构 作 一 个 网 络 矩 阵A=(aij).这 个 矩 阵 应 与 网 络 的 邻 接 结 构 和 问题 的 游 戏 (改 变 状 态 )规 则 密 切 相 关 ,具 体 作 法是 :aij=0或 1,由 结 点 i与 结 点 j邻 接 或 不 邻 接而 定 ; aii=1/2(1/2可 代 以 小 于 1的 任 意 正 数 ). 例 如 ,对 例 1,例 2有 1/2 1 0 0 11 1/2 1 0 10 1 1/2 1 00 0 1 1/2 11 1 0 1 1/2A= 引 理 1:对 任 意 k0

44、,x(k+1)与 Ax(k)的 每 个 对 应分 量 都 同 号 .证 :这 直 接 由 网 络 矩 阵 A的 定 义 及 网 络 改 变 状 态 的规 则 推 出 .例 如 ,对 例 1,1 / 2 1 0 0 1 1 1.51 1 / 2 1 0 1 1 0.5(0) 0 1 1 / 2 1 0 1 0.50 0 1 1 / 2 1 1 0.51 1 0 1 1 / 2 1 0.5Ax 几 个 引 理与 x(1)=(-1,1,1,1,1)T同 号 .这 里 ,01/21和 1/21= 1/2蕴 涵 :Ax(k)每 个 分 量 当 上 一 时 刻 对 应 点 的 邻 点 取 +,取 -的 数

45、 目 相 同 时 与 上 时 刻 对 应 点 同 号 ;否 则 ,取 多 数 邻点 的 符 号 .由 规 则 知 必 与 x(k+1)同 号 . 引 理 1的 严 格 证 明在 分 析 Ax(0)的 第 个 分 量 的 符 号 时 ,只 需 考 虑 与 第 i个 结 点 相 邻 的 所 有 结 点 上 一 时 刻 的 状 态 ,这 是因 为 Ax(0)的 第 i个 分 量 等 于 A的 第 i行 与 x(0)的乘 积 ,而 按 邻 接 矩 阵 的 定 义 (2)有aii=1或 0,当 (i,j)E或 E.从 而 与 第 i个 结 点 不 相 邻 的 结 点 j对 Ax(0)的 第 i个分 量

46、不 产 生 影 响 ;与 第 i个 结 点 相 邻 的 结 点 j对Ax(0)的 第 i个 分 量 贡 献 值 为 1或 1则 由 结 点 前一 时 刻 的 状 态 是 “ +”或 “ ”而 定 ;第 i个 结 点自 身 对 Ax(0)的 第 i个 分 量 贡 献 值 为 0.5或 0.5由 结 点 前 一 时 刻 的 状 态 是 “ +”或 “ ”而 定 . 因 |0.5|1)阶 实 方 阵 A=(aij)的 每 行最 大 二 元 素 之 和 都 等 于 u;并 且 每 列 最 大二 元 素 之 和 都 等 于 v.试 证 : u=v.证 :用 反 证 法 .不 失 一 般 性 设u v.

47、(*)所 需 结 论 可 通 过 以 下 三 步 推 理 来 完 成 : A 的 第 i行 最 大 元 ,第 二 大 元 必 可 表 为u/2+pi,u/2-pi, pi0,i=1,n.(显 然 成 立 ) 设 A 的 第 i行 最 大 元 ,第 二 大 元 分 别 为 Mi,mi,则 u=Mi+mi 它 们 的 平 均 数 为 u/2.令 Mimi=pi,则Mi=u/2+pi,mi=u/2-pi,pi0,i=1,n.mi Miu/2p i/2 pi/2 A的 行 最 大 元 必 两 两 不 同 列 .因 若 有 两 个 行 最 大 元 asj,atj 都 属 于 第 j列 ,则 v asj+atj u+ps+pt u,便 与 假 设 (*)矛 盾 . 令 pk = minp1,pn.由 知 第 k行 第 二 大 元 u/2-pk 必 与 某 i行 最 大 元 u/2+pi 同 在 一 列 ,于 是 有v u/2-pk+(u/2+pi)= u+(pi-pk) u,也 与 假 设 (*)矛 盾 . 证 毕 . 思 考 题 4-4: 试 对 问 题 D 给 出 别 的 证 明 .征 集 不 同 于 参 考 答 案 的 解 法 ！