用excel演示线性规划中的单纯形法和匈牙利法.pdf

第 1 7卷第 6期 2 0 0 7年第 6期 兵 团 教 育 学 院 学 报 J oI 脲NA L OF B 】 GnI AN E DUCA 0 0N 『 s l TI I r I E v o 1 ． 1 7 N o ． 6 De c． 理科研究 用 E x c e l 演示线性规划中的单纯形法和匈牙利法 楼建华 ， 吴琼 石河子大学信息科学与技术学院， 新疆 石河子 8 3 2 0 0 3 摘要 用 E x c e l 的运算功能演示 解线性规划问题的单纯形法和解分配问题的匈牙利法。 关键词 Exc e l ； 演示 ； 单纯形法； 匈牙利法 中图分类号 O 2 2 1 文献标识码 A 文章编号 1 0 0 9 一l 5 4 8 2 0 。 r 7 0 6 0 0 3 3 0 3 ，nl e S i mp l e x M e t h o d a nd t h e Hu n g a r y M e t h o d i n Ex c e l De m o ns t r a t i o n Li n e a r t 5 “o g r a n m, g L oU J i a nh u a ， Wu Q o n g C o l l e g e o f I n f o r m a t i o n E n g i n e e r i n g ， S h i h e z i U n i v e r s i t y ， S h i h e z i ， X i n j i a n g 。 8 3 2 0 0 3 ， C h i n a Ah盘 l c t 1 h i s a r t i c l e d e mo n s t r a t e s t h e S i m p l e x Me t h o d a n d t h e H u n g a r y Me t h o d b y u s i ng t h e Ex c e l c a l c u l a t i o n ． Ke y wo r d s Ex c e l ；D e mo n s t r a t i o n ；the S i m p le x Me t h o d；the Hu n g a r y Me t h o d E e x e l 内置 了“ 规划求解” 功能， 可以求解线性规 划和某些非线性规划， 可以求解整数规划和 0一l 规 划， 但是， 未给出求解过程。 本文所述内容与 E e x e l 的“ 规划求解” 无关， 拟用 E e x e l 的运算功能演示 解线性规划问题的单纯形 法 和解分配问题的匈牙利法。 l 用 E e x e l 演示解线性规划的单纯形法 线性规划的标准形式为 ma x C XT f A x 。 1 【 X／0 其中， B≥0 。另外 ， “ ◇ ／0 ” 表示左侧的向量或矩 阵◇的元素均非负。 单纯形法的一般形式如表 l 所示 表 1 单纯形 目标系数 C 约束 变量 X 基 基 常 选 系 变 约束矩阵 A 数 择 数 量 列 列 D Y B F 检验行 E 其中， Y选自 X， D与 Y对应 的选 自 C ， ECD r A ， F 是同行中 B与 A的入基列正元素之比。 如果 E中没有正数 ， 则 E中负数所在列的约束变 量均取 0 ， 其它约束变量满足约束条件即可。 E中有正数时， 最大正数所在列的约束变量 x i 入 基。如果 A的入基列中没有正数， 则无解。否则 ， { b i ／ a l i I a i i 0 } 取上述集合中最小值 ， 则改为 E中没有负数时结束 ， 否则， 最小负数所在列的约束变量入基。 以上简要回顾了单纯形法。下面结合实例 ma x 2 x l 5x 2 f 2 x l 5 x 2 ≤ 1 0 { 2 x l 2 x 2 ≥l 2 L x ／0， i l ， 2 用 E e x e l 演示求解线性规划问题的单纯形法。 第一步、 引入松驰 变量 x 3和 x 4 ， 把 2 式标 准化 为 ma x 2 x l5 x 20 x 30 x , r 2 l 5 x 2 l 30 x , 1 0 { 2 x l 2 2 0 x 3 一l x 4 1 3 L x i ／0， i 1， 2， 3 ， 4 收稿 日期 - 2 0 0 7 1 0 一l 8 作者介绍 偻建华 1 9 6 2 一 ， 男， 石河子大学信息科学与技术学院教授， 从事算法分析、 数学建模等研究。 一 3 3 第二步 、 在 E e x e l中填写 3 式所对应的单纯形 如表 2所示 表 2 l 垦l l i 曼l l i 2 5 0 0 0 x 3 其中， x 已人基。 第三步、 在表 2的 C 5中填人 C 1 一S U P f 1 0 D U C T A 3 A 4 ， C 3 C A 并向右复制至 F 5 。 第四步、 如果检验行 即 C 5 F 5 中没有正数 ， 则转 第九步 ， 否则 ， 最大者 即 D 5 所在列的约束变量 即 x 2 人基 。 第五步 、 对于约束矩阵的人基列 即 D 3 1 3 4 的正 数， 在选择列 即 H 3 H 4 的同行 中填人常数列与其之 比 即 H 3中填人 G 3 ／ D 3 ， 并复制到 H 4 。 第六步 、 选择列中最小者 即 H 4 所行 的约束变 量 出基 。 第七步 、 把表 2复制为下述表 3 表 3 B C D E F G H 7 2 5 0 0 8 x 1 x 2 x 3 x 4 9 0 x 3 - 3 0 1 2 ． 5 7 ． 5 ④ 1 0 5 x 2 1 0 - 1 0 ． 5 1 1 - 3 0 0 j 其中， x 2已人基。 第八步 、 表 3的人基行 即第 4行 除以人 、 出基 交叉点的值 即 C I O中填人 C A ／ 2 ， 并复制到 G I O 。 用矩阵行变换 ， 使人基列的基它元素为 0 即 C 9中填 人 C 3 5 *C I O ， 并复制到 G 9 。 重复第四步 第八步， 得下述表 4 表 4 A l B l c l D l E l F l G l H l 2 5 0 0 x l x 2 x 3 x 4 0 x 4 5 x 2 -- 3 4-- 第九步 、 检验行中负数所在列的约束变量取 0 ， 其它约 束变量满足约束条件即可。 由表 4得 X 0 一 X lx 43 O． 4 1x 2 2 4 X i ≥ 0， i 1 ， 2， 4 消去松驰变量 X 3 和 x 4 得 r 3一XI 。x4 i 0 X 2 2 0 ． 4 x l 5 L ； t0， i 1 ， 2 至此， 得 2 的无穷多解 』 X 2 ---- 2 - 0 4 x 6 【 5≥ X 1 t3 一 目标值为 l O 。 2 用 E e x e l 演示解分配问题的匈牙利法 分配问题实际上找 13阶方阵中不 同行不同列 1 3 个元素之和中最小者。 下面结合实例， 用 E e x e l 演示求解分配 问题的匈 牙利法 演示前 ， 先将 E e x e l 设置为“ 显示 0值” 。 第一步 、 如表 5所示， 在 E e x e l 中填写代价矩 阵， 其中， 最右一例是各行中最小元 素 即， 在 F l中填入 M A j E 1 ， 并复制到 F 5 。 表 5 表 6 1 0 1 2 3 4 0 2 5 6 7 8 9 5 3 4 3 2 1 0 O 4 5 7 8 8 9 5 5 1 3 5 7 9 1 9 4 3 2 1 0 1 0 0 2 3 3 4 1 1 0 2 4 6 8 1 2 O 1 2 1 0 第二步 、 矩阵的各行均减去其最小元素 如表 6 所示 ， A 7中填人 A 1 一F 1 ， 并复制到 E l 1 。表 6中 最后一列是各列中最小元素 即， 在 A 1 2中填人 M I N A 7 A 1 1 ， 并复制到 E l 2 。 第三步 、 矩阵的各列均减去其最小元素 如表 7 所示， A 7中填人 A 1 一F 1 ， 并复制到 E 1 1 。 表 7 表 8 A B C D E 1 4 O O O 2 4 1 5 O O O 2 4 1 6 4 2 ． 0 ． 0 1 7 1 1 2 4 1 8 0 1 2 5 8 A B C D E 1 4 O O O 2 4 1 5 O O O 2 4 1 6 4 2 O O O 17 O 1 1 2 4 1 8 0 1 2 5 8 刻 第四步、 对表7 交替作行、 列扫描， 选择各行中的 孤 0 如表 8 所示删除 ， 并划去所在列 如表 8所示加 边框 ， 选择各列 中的孤 0 ， 并划去所在行。各行 、 列均 无孤 0时转下步。 第五步 、 如果选中的 0数达到矩阵的阶数 即 5 ， 则转第八步。如果 0 均被划分， 则转第七步。 第六步 、 此时， 尚有 0未被划去， 它们构成若干个 回路 表 8 有一个回路 B l 4 一c l c l 5 一B l 5 一B l 4 。 对每个回路从某个 0开始， 沿 回路间隔选 0 。如果被 选中的 0 所在的行或列有 回路之外的 0 ， 则相应划去 行或列 ， 否则， 统一划去所在行或列 如表 9所 示 。 如果选中的 0 数达到矩阵的阶数 ， 则转第八步。 表 9 表 1 O A B C D E l 4 0 0 2 4 1 5 O 0 2 4 l 6 4 2 0 0 1 7 1 1 2 4 l 8 0 1 2 5 8 A B C D E 2 0 1 0 0 2 4 2 1 1 0 0 2 4 2 2 5 2 0 0 0 2 3 0 r 0 0 1 3 2 4 0 0 1 4 7 第七步 、 在未划去的元素中选取最小数 即 1 ， 按 下述规则构造新表后回到第四步 ①未划去者减去这 个最小数 表 l 0中的 B 1 7 E l 8 ； ②交叉划去者加上这 个最小数 表 l 0中的 AI 4 A 1 6 ； ③其它元素不变。 第八步、 经过表 l 1 所示的若干步骤， 最终得表 l 2 ， 其含义是 x 1 2 X 2 3 X 3 5 X 4 4 X 5 l 1 ， 其它均为 0 。 表 l 1 表 1 2 A B C D E 2 0 1 O 2 4 2 1 1 0 2 4 2 2 5 2 0 0 2 3 0 0 1 3 2 4 0 0 1 4 7 A B C D E 2 6 1 0 1 3 2 7 1 0 1 3 2 8 6 3 1 0 2 9 0 0 0 2 3 0 0 1 3 6 结合表 5得 目标值 1 7 1 7 08 1 。 除上述单纯形法和匈牙利法外 ， 用 E e x e l 也可方 便地演示运输问题和计算 P E R T网络图表中的参数 等。 参考文献 [ 1 ] 胡运权 ． 埃学教程 第二版 [ M] ． 北京 清华大学出版 社 ， 2 0 0 3 ． [ 1 ] H a r a d y A ． T a h a ． O p e r a t i o n s R e s e a r c h A n I n t r o d u c t i o n [ M] ． 北 京 人民邮电出版社 ， 2 O 0 7 ． 上接 第 3 2页 四 组织大学生业余社团顾问团。离退休老同 志结合 自己特长为社 团活动出谋划策或进行社团干 部培训 ， 积极参加校园文化建设 ， 为大学生提高思想 道德素质和健康成长提供良好的文化环境 。 五 充分利用校园网络资源优势 ， 建设“ 流金岁 月” 网页， 宣传老同志无私奉献的敬业精神和辉煌的 工作业绩， 开辟教育和引导青年学生培养高尚思想品 质和良好道德情操的新介面。通过电子信箱或座谈 、 讨论 ， 采用青年学生易于接受的方式 ， 加强与学 生的 沟通与交流 ， 对学生处理生活 、 学习、 情感 、 心理 、 生理 等方面的问题进行积极的指导 、 引导。 六 关工委积极组织大学生开展社会调查活动， 利用寒暑假深入农村、 厂矿和各基层单位， 通过大学 生的亲身经历感受祖国改革开放的巨大成就 ， 从而帮 助大学生明确专业学习的目标。 七 关工委组织有热情 、 有能力的老同志成立大 学生心理健康咨询工作小组， 用他们丰富的人生阅历 和乐观健康的人生态度 ， 去解答大学生 由社会 、 家庭 和 自身心理发育不成熟等多方面产生的种种困惑 ， 帮 助大学生培养良好的心理品格 ， 从根本上帮助他们确 立崇高的理想信念和正确的世界观、 人生观 、 价值观， 找准自己的座标 ， 以增强克服困难 ， 经受考验 ， 承受挫 折的能力， 成为一名有良好心理品格的大学生。 参考文献 [ 1 ] 托起明天的太阳关心下一代工作资料汇编 一 3 5