尚毅创立大型线性规划新算法　我国学者对当代热门课题新突破，可能带来巨大效益深远影响 [复制链接]

第3版(科教·文化·体育)
专栏：

尚毅创立大型线性规划新算法
　　我国学者对当代热门课题新突破，可能带来巨大效益深远影响
本报讯　记者艾笑报道：6月6日，电子工业部组织知名数学和计算机专家，听取了沈阳电子研究所尚毅关于求解大型线性规划新算法的汇报。专家们认为：这位44岁的高级工程师，正在从事的是一项有重要学术价值和广阔应用前景的工作，应当引起高度重视。
第二次世界大战中，为确保胜利，美苏等国调集优秀的数学家、军事技术专家和工程师，研究武器、兵力的最优部署和军需供应的最优运输方案，因而产生了运筹学及其新分支——线性规划。战后，这门学科很快得到发展，在运输、建筑、钢铁、煤炭、石油、农业和国防等部门得到广泛应用。如一个大企业，怎样在各种条件限制下取得最高产值、获得最大效益？一个农业区怎样规划才能使产品既满足社会需要又能获得最大利润？通过线性规划方法，都可求得最优解。据统计，现在世界上使用的电子计算机，绝大部分时间都用于处理线性规划问题。
自1947年美国斯坦福大学教授丹捷格提出“单纯形法”以来，解决线性规划的计算方法一直都采用“单纯形法”。但是，这种方法只能在变量不超过1.5万或2万的情况下有效，解决大规模问题就不理想了。8年前，苏联数学家哈奇扬提出了“椭球法”，虽比“单纯形法”理论上优越，但实际应用还有问题。1984年，美国贝尔实验室青年数学家卡玛卡用射影几何原理求解大型线性规划问题，在解决5000维的线性规划问题时，比“单纯形法”的计算速度提高50倍。卡玛卡的新算法用于美国电话电报公司改建太平洋沿岸20个国家的庞大电话网计划，求出了具有4.2万个变量设计的最小投资数。卡玛卡这项引起轰动的新算法所编制的程序，贝尔实验室还处在保密中。因为如何提高计算机求解大型线性规划问题的速度，即寻求最佳算法，是当前国际科技界争相突破的热门课题。
1981年，尚毅在解决一种类型控制问题时，找到用“鞍面法”来求解线型规划问题的思路。1985年他提出正式算法，这种“鞍面法”比“椭球法”更简便，在解1000个变量、18万个点的数字模型上，比“单纯形法”速度快10倍。专家们欣喜地认为：尚毅的思路新颖、切实，经过理论上进一步严格完善的数学证明和软件开发，将会成为我国独立完成的、别具特色的重要成果。
据悉，国家有关部门正考虑用尚毅的“鞍面法”解决大型水利设施和大规模企业改造工程，年内有可能实施。