线性规划问题的符号计算.pdfVIP

维普资讯 i997年 6月 应用教学与计算教学学报 第 11卷 第 i期 C ()MM ．ON APPL MATH AND COMPUT V011i No1 J11llC．1007 线性规划 问题 的符号计算 弓一c7』 黄纯一 肖相武 (=)2 I『／ 黑龙 ￡L大学数学系，哈尔蘸 ． 150~80 摘要 应 用各种符 号计算系统可以很方便地求解各种线性代数问题，利用初等 变换 即可得到 问题 的】睛确解而不必预先编写程序 本文谢过例子，根据单纯形算法 原理，详细介绍 r使用muMATH 系统直接求解线性规划问题精确解的运算方法． 人工变量所对J_=；=的列向量始终不参加运算，从而可大量节省存 储量和计算量 关键 词 ：符号计算，战性规划，单纯形算法，初 等变接，人 工变量列 ． 1引 言 科学计钟分数值计弗与符号计算两大类 ．数值计 ，义称数字计算，它一般 只处理数值型的数据，在计 中难免有误差传播，故在设计数值算法时除了考虑 收敛性，还必须兼顾数值稳定性，以防止误差传播的严重影响 符号计算，又称 计 机代数，它所处理的数据足字符型的，包括字母、公式、数字等各种符号的 数学表达式，可把表达式直接输入计算机进行符号演 ，并把数值计算作为其特 例，虽然符号计弗，f如纯数值计茆：速度快，但它有许多优点 例如 ：计算结果绝对 精确；可作大有理数的运费+；可直接进 行符号的代数运算和微积分运筇，而且操 作很方便，通常可以 预先编程序，即使要编写程序也 比较简单容易；处理近似 计茆：问题时不必考虑数值稳定性，只要 ：法足收敛的就可作高精度的近似遥算， 得到充分多位的有效数字，即使处理病态问题也并不费事，我们曾编写过关于无 理数的高精度近似计 ：问题及若干线性与非线性规划 问题的符号计算程序 {参见 [6 目前 已有许多功能强大的符号计 ：系统，除了能作符号代数运算和符号微秘 分运并外，还能进行 甬数绘阿，并且 已经和数值计算系统连接在一起 ．着把符号计 算与数值计 结合起来使用，则可充分发挥各 自的优点，实现更为完满的计算． 本文 以规模适当的实例，仅介绍使用 mltMATH 系统直接求解线性规划问题 的运算方法，在单纯形表 中人工变量所对应的列向量始终不参加运算，从而可大 量节省存储量和运算量 例如对于一般的线性规划 问题，我们首先采用 Dan|．~,ig_j1： 法，按照最大下降规则选取主元索，遇到退化 问题再采用B II 法，按最小下 标规则选取主元索，而且据退化问题的性质还可 以在退化行中灵活地选取任一非 零元素作为主元素，这样既可蹦达到快速收敛的 目的义可 以避免退化问题的死循 环现象j而对于特殊的线性规划问题还可以采用单纯形方法的其它变形，如对偶 j1法或原始与对偶相结合的交叉前法等；此外，还可以充分利用计算机的内存储 本文 199B年 6月 13H收到 ． 。 维普资讯 应用数学与计算数学学报 ll卷 器来保存有用的敬据，通常先把原始数据和计算过程部保留在某些变量名下，经 检查无误且确认后面不用了再撤消那些变量名的内容．以保证内存储器的剩余空 间足够大、 2单纯形算法原理及其修正 考虑线性规划 问题 (LP)： lldn Z = C ． s．t．A = b． IJ 其 中，A为 mx，的实矩阵，不妨设 h20．m，且 A是行满秩的．设方阵 B为 的某个 rn阶的非奇异子阵，称为基矩阵， 可以分解为 ( ．Ⅳ)N称为非