线性规划方法在计算机绘制优势区相图中的应用

D0I:10.13374/j.issn1001-053x.1988.04.036 北京钢铁学院学报 第10卷第4期 Journal of Beijing University Vol,10 No.4 1988年10月 of Iron and Steel Technology 0ct.1988 线性规划方法在计算机绘制 优势区相图中的应用 王才荣朱日彰张文奇 (表面科学与腐蚀工程系) 擂要根据优势区相图中物质的稳定区是由一线性不等式组的解确定，且呈凸多边 形这一性质，本文提出了引入一组恰当的目标函数，与线性不等式组组成线性规划向题，由 其解可确定凸多边形的顶点，从而获得优势区相图的方法。并编制了FORTRAN语言通 用程序，在M150机上通过运算，所得结果与文献相符。本方法具有数学模型明确、可 常，物理概念清楚，通用性强，准确性高，运算速度较快等优点。 关键词相图，计算机制图，线性规化：凸多边形，线性不等式组 The Application of the Method of Linear Programming on Computer Calculation of Phase Diagram of the Area of Predominance Wang Cairong Zhu Rizhang Zhang Wengi ABSTRACT:According to the thermodynamic and mathematical properties that the stable area of the substance in the phase diagram of the area of predominance is defined by the solution of linear inequalities and it's geo me- trical shape is convex polygen,the new computer algorithm of the calculation for the phase diagram of the area of predominance is developed in this paper by the solutions of the problems of linear programming that is made by introdu- cing a series of optimum functions to the linear inequalities.The FORTRAN program has been made by the use of the Revised Simplex Method that is used for computer to solve the problems of linear programming.The results cal- 1887一11一20收稿 492

， 北 京 钢 铁 学 院 学 报 第 卷第 期 年 月 。 。 。 线性规划方法在计算机绘制 优势区相图 中的应用 王才荣 朱 日彰 张文奇 表面科学 与腐蚀 工程系 摘 要 根据优势区相 图中物质的稳定 区是 由一 线性不等式 组 的解确 定 ， 且呈凸 多边 形 这一 性质 ， 本文 提出了 引入 一 组恰 当的 目标函数 ， 与线性不等式组组 成线性 规划问题 ， 由 其解可 确 定 凸 多边 形 的 顶点 ， 从而获得 优势区相 图的方法 。 并编制 了 人 语言 通 用程 序 ， 在 一 。 机 上 通 过 运 算 ， 所 得 结果 与文献 相符 。 本方 法 具 有 数 学 模 型 明 确 、 可 靠 ， 物理概念清楚 ， 通 用性强 ， 淮确 性高 ， 运 算速 度 较快等优 点 。 关趁 润 相 图 ， 计算机制 图 ， 线性 规 化， 凸 多边形 ， 线性不 等 式组 牙 夕 夕 之 牙 ’ ， · 豆 · 一 一 收稿 DOI ：10．13374／j ．issn1001－053x．1988．04．036

culated by this method is correspond to the papers published.The method has the following advantages,such as has definit,clear and reliable mathematical model;clear physical concept;appropriate for common use;high accurate in results and more convienent to the very complex systems. KEY WORDS:phase diagram,computer cartography,linear programming; linear inequalities,convex polygen 计算机绘制优势区相图前人已做了不少工作1~4)。Linkson P B等人【1将前人计算优 势区相图的算法分为3类：(1)逐点扫描法；(2)线消去法(8)凸多边形法。逐点扫描法较笨 抽，效率低。线消去法是根据反应平衡线的走向及相界间的交角关系的热力学判据来对直线 进行逐段消去处理，最后保留的线段即为稳定区的平衡界线。此法运算速度较快，但物理概 念不很明确，使用的热力学概念较多，可靠性不如凸多边形法。凸多边形法首先由Froning MH等[]提出，Rosof B H]、骆如铁[8】等在其基础上均做了一些工作。Froning M H虽然 认识到物质的优势区为一线性不等式组的解，且呈凸多边形，但并设有从数学上找到确定凸 多边形的方法。Rorof R H、骆如铁均找到了描述绘制优势区相图的数学模型，即把独立平 衡关系作为独立数据向量，由这组独立数据向量出发，经过求逆或加减可得到体系中任何一 种平衡关系。Ro$ofRH利用线性规划方法认为凸多边形的顶点为这组独立向量所描述的线 性约束条件的基础可行解，通过向量的调换可得到所有的可行解，从而获得优势区相图。 骆如铁则采用了线性规划中求可行性空间的方法进行了三维Kellogg图的计算机计算。 Rosof B H骆如铁采用的方法，明显的缺点就是没有从数学上找到解线性不等式组的严格方 法，仅仅是利用线性规划的方法在可行基和可行性空间上下功夫，这样来确定凸多边形从数 学上讲是不严格的，因而可靠性较差。 本文引入一组恰当的目标函数，与确定物质优势区的一组线性不等式约束组成线性规划 问题，由其解来确定凸多边形，从而获得优势区相图的方法。 1线性规划问題的建立及一组恰当的目标函数的引入 设存在11种物质，分别以I,1…,10表 示。由热力学性质可知，物质I的稳定区（优 势区)应是物质I在一定的环境下（一定电 位，PH,T或一定Po2,Pg2,T,或一定 Po2、Pg2、T等)生成所有其它物质(1，， 10 10)的生成反应自由能均大于等于零的区域， 等于零时为平衡界线。若其中之一因素恒定， 则优势区相图为2维几何图形。对E-pH图、 B log(Po2/Pa)-log (Ps2/Pa),log(Po2/Pa)- E.log(Ps/Pa ),log(Psoz/Pa) log(Pgo2/Pa)等优势区相图都可以找到确定 图1物质1的优势区 物质I的优势区的10个不等式组成的不等式 Fig.1 The area of predominance 组：A,X1+B,X2≥C1,j=1,…,10。其中 for substance I 493

· 丁 ， ， ， ， ， ， ， ， 计算机 绘制优势 区相 图前人 已做 了不少 工 作 〔 ‘ 一 ‘ ’ 。 等人 〔 ‘ ’ 将前人计算优 势区相 图的算法分为 类 逐 点扫描 法 线 消去 法 凸多边形法 。 逐点扫描法较笨 拙 ， 效率 低 。 线 消去 法是根 据反 应平 衡线 的走 向及相界间的交角关 系的热力学判据来对直线 进行 逐段 消去 处 理 ， 最 后保 留的线 段 即为稳定 区 的平衡界线 。 此法运 算速度较快 ， 但物理 概 念不 很明确 ， 使用 的热力学 概念较多 ， 可靠性不如凸多边形法 。 凸多边形法 首先 由 等 。 ’ 提 出 ， 〔 ’ 、 骆如铁 ‘ 吕 ’ 等在其基础上均做 了一些 工作 。 虽然 认识到物质 的优势 区为一线 性不等式组的解 ， 且呈 凸多边形 ， 但并没 有从数学上找到确定凸 多边形 的方法 。 、 骆如铁均 找到 了描述绘制优势区相 图的数学模型 ， 即把独立平 衡关系作为独立数据向量 ， 由这 组独立数据向量出发 ， 经过求逆 或加减可得到体 系中任何一 种 平衡关 系 。 利 用线 性规划方法认 为 凸多边形 的顶点为这 组独立向量所描述 的线 性约 束条件的 基础可行 解 ， 通过 向量 的调 换可得到所有 的可行解 ， 从而 获得优 势 区 相 图 。 骆如 铁则采 用 了线 性规划 中求可行 性空 间的方法 进 行 了三维 图 的 计 算 机 计 算 。 。 。 骆如 铁采 用的方法 ， 明显的 缺点就是没 有从数学上 找到解线性 不 等式 组的严格方 法 ， 仅仅是利用线 性规划 的方法在可行 墓和可行 性空间上 下功夫 ， 这样来确定凸多边形从数 学上讲是不严格的 ， 因而 可靠性较差 。 本文 引 入一组恰 当的 目标 函数 ， 与确定物质优势 区的 一组线 性不 等式约 束组 成线性规划 问题 ， 由其解来确定凸多边 形 ， 从而获得 优势区相 图的方法 。 线性规划问魔的建立及一组恰当的 目标函数的 弓入 、心“ 工七皆 ‘ 设存在 种物质 ， 分别 以 ， … ， 表 示 。 由热力 学性质可知 ， 物质 的稳定 区 优 势区 应是物质 在 一定 的 环 境 下 一定 电 位 ， ， ， 或一定 尸。 ， 尸。 ， ， 或一定 。 。 、 尸， 、 等 生成 所 有其它物 质 ， … ， 的生成反 应 自由能均大于 等于 零 的区域 ， 等于 零时为平 衡界线 。 若 其 中之一因素恒定 ， 则优势区相 图为 维 几何图 形 。 对 一 图 、 一 。 、 尸。 。 等优势 区相 图都可 以 找到确 定 物质 的优势 区的 个不 等 式 组成 的不 等式 组 ， ， ， ，， ， … ， 。 其 中 其之映了 挤， 、 砂 ， 、 凡。户 、 图 物质 的优势区

A、B,、C,均为由反应方程及热力学参数确定的常数；X1=+E,-log(Po2/Pa);X2=+pH, 1og(Ps2/Pa)-log(Pso2/Pa)。根据线性规划理论，这一线性不等式组的解应为凸多边形。 用几何图形表示如图1所示。其中A、B、C、D、E、F、G为凸多边形的顶点，凸域内为 物质I的稳定区。 考虑其它物质1，，10时同样可以找到相应的不等式组。若某物质有稳定区，则相应 的不等式组有解，为凸多边形域。若某物质无稳定区，则相应的不等式组无解。反之亦然。 现在的问题是如何解不等式组，或如何更确切、迅速地解不等式组。 作者引人一组目标函数f=D()X,+E(k)X2,其中=1，…，I,k=1,…,K,则 可以组成线性规划问题。 求目标函数： f=D(i)XE(k)X2 (1) 达到极小，并满足约束条件： A,X1+B,X2≥C, (2) 其中X,≥0，X2≥0，C≥0，j=1,…,物质总数-1。 通过求∫的极小值可获得凸多边形域的顶点。在某一目标函数下，线性规划问题有解， 或无解，'或有无穷多解。因此每一个目标函数只能确定一个顶点，或确定不了顶点。以下讨 论目标函数组的恰当化问题。 图2为目标函数1,2，…，T分别在凸域S的顶点A,B,,G达到极小值，则通 过引入目标函数1，·，7和组成凸域S的约束条件组成7个线性规划问题，就可一一确定凸 多边形域S的所有顶点。 由图2可知凸多边形域的所有顶点实际上为其相应两边所在的直线的交点。设两直线的 斜率分别为tga1和tga2,引入的目标函数所在的直线族斜率为tga。则有以下8种情况： X1 Xi 图2目标函数在凸域S的顶点达到极小值 图3优势区中边界直线的交角关系 Fig.2 Optimum functions reach minimun Fig.3 The relation of the angles of values at the vertexes of the area intersections between the boundary of convex polygen s lines of the area of predominance (1)tga1>0,tga2<0这时引入目标函数使tga=0或tga=∞即可确定所有这样 的顶点。也即引入目标函数f=±×，于=±y即可确定这类顶点。 (2)tga1>0,tga2>0如图3所示。若凸域在1,8二交角区，则引人f=x+y和 ∫=-￥一y即可确定这类顶点。若凸域在2,4二交角区，则引入的目标函数应满足ga1< tga<tga2,才能确定这类顶点。 494

，、 ，、 ，均 为由反 应方程及热力学参数确定的常数 二 ， 一 。 ， ， 尸。 一 尸 。 。 。 。 根 据线 性规划理论 ， 这 一线 性不 等式 组 的解 应为凸多边形 。 用 几何图形 表示如图 所示 。 其 中 、 、 、 刀 、 、 、 为凸多边 形 的 顶点 ， 凸域 内为 物质 的稳定 区 。 考虑其它物质 ， … ， 时 同样可 以找到相 应 的不 等式组 。 若 某物质有稳定区 ， 则相 应 的不等式组 有解 ， 为 凸多边 形域 。 若某物质无稳定 区 ， 则相 应的不等式组 无解 。 反 之亦然 。 现在的 问题是如何解 不等式组 ， 或如何 更确切 、 迅速地 解不 等式组 。 作 者引入一组 目标 函数 “ ， 其 中 ‘ 二 ， … ， 几 ， … ， ， 则 可 以组成线 性规划 问题 。 求 目标函数 ， 伪 达到极小 ， 并满足约束条件 ， 其 中 ， ， ， 二 ， … ， 物质 总数 一 。 通过求 的极小值可获得凸多边形域 的顶点 。 在某一 目标 函数下 ， 线 性规划问题有解 ， 或无解 ， ， 或有无穷多解 。 因此每一个 目标 函数只能确定一个 顶点 ， 或确定不 了顶点 。 以下讨 论 目标函数 组的恰 当化问题 。 图 为 目标函数 ， ， … ， 分别在凸域 的顶点 ， ， … ， 达到极小值 ， 则通 过引 人 目标函数 ， … ， 和组成凸域 的约束条件组成 个线性规划 问题 ， 就可一一确定凸 多边形城 的所 有顶点 。 由图 可知 凸多边 形域的所 有顶点实际上 为其相 应两 边所在 的直线 的交点 。 设两 直线 的 斜率分别为 ，和 ， 引 入的 目标 函数所在的直线 族斜率 为 。 则 有以下 种情况 阵 气、 色 右 图 目标函 数在凸域 的顶点达到极小 值 图 优势区中边界直线 的交角关系 ， ， ， 这时引人 目标函数使 或 ， 即可 确 定 所 有这样 的顶点 。 也即 引 入 目标函数 土 二 ， 士 即可确定这 类顶点 。 ， 如 图 所示 。 若凸域在 ， 二 交角区 ， 则引入 ‘ 夕和 二 一 ‘ 一 即可确定 这 类顶点 。 若 凸域在 ， 二交角区 ， 则引 入的 目标函数 应满 足 ， 才 能确定这类顶点

(3)tga1<0,tga2<0如图3所示。若凸域在5，T二交角区，则引人目标函数 f=×-y和f=-x+y即可确定这类顶点。若凸域在6,8二交角区，则引人目标函数应 满足tga1<tga<tga2,才能确定这类顶点。 通过以上分析，我们可以找到一组恰当的目标函数。对于优势区相图这种特殊的凸多边 形域，引入的目标函数可以大大地减少。以Fe-O2-Sz稳定图为例加以分析。因为Fe与FeO 和FeS交接，故考虑Fe的优势区时，不必把其所有顶点一一定出，只须定出其中几个能适 宜整体处理的顶点即可。其它几个顶点由考虑FeO、FeS时来定。考虑FeO、FeS的优势 区时也如此。同时，tga1和ga2是由物质MSx Oy,MSx:Oy1中x、y4、x1、y,决定。 故进一步分析物质的化学计量数与所应引入的目标函数间的关系，还可避免多引目标函数。 由此可指望此法运算速度较快，且可靠性最大。 作者通过大量计算实现了上述思想。 2线性规划问題的计算机解法及计算结果 采用Dantzig G B【e~I1提出的Revised Simplex Method来解线性规划问题。由于此 法解法巧妙，对所有的等式或非等式约束条件均适用。且当约束条件较多时，可以大大节省计 算机存贮量和计算量，故十分适合解决各种体系的问题。 此方法的基本步骤为根据不等式组的系数矩阵构成一个(M+1)×(M+2)矩阵A(其 中M为物质总数)，和(M+1)×(M+1)单位矩阵U进行相乘及U矩阵的行列变换。最 后解出目标函数达到最小值的X,、X2,点(X1,X2)即为所求凸多边形域的顶点。 线性规划问题解法框图如图4所示。 Fatm(裤+)(m+2)mat廿世A Caleulater Xy=UAm Xw=07 Cajeulate:j-Um: Calculate:YjUj 2山theb 2通theY2约 N Catoulate:UA Choose =mjnbj No feasible solution Choose Yj=minY] PT幻 Caleulate Xi4 CaleulaterXi-U;A All the 0统 No solution Take X as basie varsuble Have unlimited solutions Taike Xas basle variable Change matris边 [Change mAtrix☑ 图4 Revised Simplex Method解线性规划问题框图 Fig.4 Block diagram of program used to solve the problem of linear programming 采用FORTRAN语言编制计算程序，对M-O2-S2、M-SO2-O2、M-H2O、M-S- H2O、M-S-C1-H,O等体系的优势区相图进行了计算，部分结果如图5所示，其它结果见 后续文章。所得结果与文献比较，吻合得较好。同时，还采用了计算机结果将A矩阵打印出 495

急 ‘ ， 如图 所示 。 若凸域在 ， ， 二交角区 ， 则 引 人 目 标 函数 二 一 和 一 夕 即 可确定这 类 顶点 。 若 凸域 在 ， 二 交角区 ， 则引入 目 标 函 数 应 满足 ， ， 才 能确定 这 类 顶点 。 通过 以上 分析 ， 我们 可 以找到 一组恰 当的 目标 函数 。 对于优 势区相 图这 种特殊的凸多边 形域 ， 引 人的 目标 函数 可 以 大 大地减少 。 以 一 一 稳定 图为例加 以分析 。 因为 与 和 交接 ， 故考虑 的优 势区时 ， 不必把其所 有顶点 一一定 出 ， 只须定 出其中几个 能适 宜整体 处 理 的顶点 即可 。 其它 几个 顶点 由考虑 、 时来定 。 考虑 、 的 优 势 区时也如此 。 同时 ， 和 是由 物 质 ， 』 中 二 ‘ 、 夕 ‘ 、 ，、 夕， 决定 。 故 进 一步分析物质 的化学 计 量 数 与所 应引 入 的 目标函数 间的关 系 ， 还可避 免多引 目标 函数 。 由此 可指望此 法 运 算速 度较 快 ， 且 可靠 性最 大 。 作 者通过 大量 计 算实现 了上 述思 想 。 线性规划问题 的 计算机解法及计算结果 采用 〔 ” 一 ‘ ” 提 出的 来解线性规划问题 。 由于此 法 解法巧妙 ， 对所有 的 等式 或非 等式约 束条件均适 用 。 且 当约 束条件较多时 ， 可 以大 大节省计 算机存贮量和计 算量 ， 故 十分适 合解决 各种 体 系的问题 。 此方法 的 基 本步骤 为根 据不 等式组的 系数 矩 阵构成 一个 十 矩 阵 其 中 为物质 总数 ， 和 十 单位矩 阵 进行相 乘及 矩 阵的行 列 变 换 。 最 后解出 目标函数 达到 最小值的 、 ， 点 ， 即为所 求凸多边 形域的顶点 。 线性规划 问题解法框 图如 图 所示 。 图 解线性 规划 向题 框图 采用 语 言 编 制 计 算 程 序 ， 对 一 一 、 一 一 、 一 、 一 、 一 一 一 等体 系的优势 区相 图进行 了计 算 ， 部分结 果如 图 所示 ， 其它结果见 后续文 章 。 所得结 果与文 献 比较 ， 吻 合得较 好 。 同时 ， 还采用 了计算机结 果将 矩 阵打印出

来，然后再用图解法及手工计算来确定凸多边形顶点，结果与计算机采用Revised Simplex 1 Method解线性规划问题所得结果完全一致，以此进一步证实其可靠性。 0.0 1000K 0.0 700K FeS2 Fe2(SO) Fe2(Soh -10.0 -10.0 Fes Peo Pa304 -20.0 F 岁200 -Fe204 Fe2O3 Fo -30.0 30.0 -20.0 -10.0 0.0 -30.0 -40.0 -30.0 -20.0 -10.0 log(Po2/atm). 、 log(Puz/atm) (a) (b) 图6Fe分别在1000K,700K下的1og(Ps2/P,)一log(Po2/P.)图 Fig.5 The log (Ps2/p.)-(Po2/P.)phase diagrams of Fe at 1000K,700K 3结 0 论 本文提出引入一组恰当的目标函数与确定物质优势区的线性不等式组组成线性规划问 题，再由线性规划问题的解来确定凸多边形的顶点，从而获得优势区相图的方法具有以下特 点： (1)数学模型的物理概念清楚，数学解法严格、可靠，通用性强，运算速度快。 (2)应用数学方法把物理化学问题转化成数学问题，适合于计算机处理。 (3)从数学上找到了不等式组的严格数学解法，适宜处理较为复杂的体系。 参考文献 1 Duby P,International Conference on High Temperature,High Pressure Electrochemistry in Aqueous Solutions.Proccedings,University of Surrey,Guilford,1973 2 Brook P A.Corrosion Sci.1971;(11):389~396 3王乐珊，许志宏.金属学报。1984,20(2)：B116 4 张索林。稀有金属。1983,2（2)：216 5 Linkson P B et al,Minerals Sci Enging.1979;65:2 6 Froning M H et al,Corrosion Sci,1976;16:371 7 Rosof B H,National Bureau of Standards Special Publication 496/2, 1090-1092 8骆如铁。中南矿冶学院学报，1982，（2)：1 9 Hadley G.Linear Programming,1962 10 Dantzig G B.Pacific Journal of Mathematics 1955;6:2 11 Dantzig G B.Computational Algorith of the Revised Simplex Method, RM-1266,The RAND Corp.1953.10 496

来 ， 然后再用 图解法 及手工计算来确定凸多边形顶点 ， 结果与计算机采用 解线性规划问题所得 结 果完全 一致 ， 以此 进一步证实其可靠性 。 官︶芝才工孚 吧二二【 下一 － 洲 卜 口。 口 裕丁 口 叭 《 ， 甲 卜 ，刃‘ 飞、 护 「’ 》 ，欠 了切 甲 华 、 。 。 仁 、 才 丫 仁，’ 、 、 日 介 … 子、 ‘ 吃 、 ， 丫 产︵、‘瞥 喇气 里 乏 。 · 。 一 一 。 、 〕 图 分 别在 ， 下 的 阳 一 。 图 一 尸 。 ， 结 论 本文提出引人一组恰 当的 目标 函数与确定物质优势区的线 性不 等式组组成线 性 规 划 间 题 ， 再 由线 性规划 向题 的解来确定 凸多边 形 的 顶点 ， 从而获得 优势区相 图的方法具 有以下特 点 数学模型的物理概念清楚 ， 数学解法严格 、 可靠 ， 通用性强 ， 运算速度快 。 应 用数学方法把物理化学 向题转化成数学 问题 ， 适合于计算机处 理 。 从数学上找到 了不 等式组 的严格数学解法 ， 适宜处理较为复杂的体系 。 参 考 文 献 ， 夕 ， 夕 产‘ 夕 ‘ ，“ “ ” ， ， 。 ‘ 。 ， 王 乐珊 ， 许志宏 金 属学报 。 ， 张 素林 。 稀 有金属 。 ， 万 ” 忿 月夕 夕 。 。 。 。 ， “ 。 一 骆如铁 中南矿冶 学院学报 。 ， 。 ， 夕 巾 ” 夕， 。 ‘ ‘ 。 ， 二 ， 了。 “ ‘ ， ， 一 ， 。