[拼音]：danchunxingfa

[外文]： x method

可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则，适用于在电子计算机上进行求解运算；后者将变量和数据列成表格，适用于笔算。两者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克（1914～　）于1947年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～　）于1938年提出的解乘数法相类似。

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解，满足所有的约束条件的解称为可行解。使目标函数达到较大值（或小值）的可行解称为较优解。这样，一个较优解能在整个由约束条件所确定的可行区域内使目标函数达到较大值（或小值）。求解线性规划问题的目的就是要找出较优解。

可能出现下列情况之一：

（1）存在着一个较优解；

（2）存在着无穷多个较优解；

（3）不存在较优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

要缩小对较优解的搜索范围，就必须认识较优解的一般性质，较优解如果存在的话，则它必然处于可行区域的边界上。

任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”或“≥”号而得到的。每一个边界方程确定一个超平面。因此，可行区域的边界是由那些满足一个或同时满足几个边界方程（即处在作为边界的一个或几个超平面上）的可行解所组成，而且较优解必在其中。较优解不仅是在可行区域的边界上，而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解具有下列三个重要性质：

（1）如果存在着一个较优解，那么它必定是角点可行解。如果存在有多个较优解，那么至少有两个较优解必定是相邻的角点可行解。

（2）只存在有限个数的角点可行解。

（3）如果一个角点可行解按目标函数值来衡量时比其所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是较优解。

上述这些性质构成单纯形法的原理基础。之后一个性质的重要性在于它为一个角点可行解是否是较优解提供了一种简便的检验标准，因而毋需列举所有的可行解。单纯形 是利用了这个性质，只要检查少数的角点可行解，并且一旦这个较优性检验获得通过就可立即停止运算。

单纯形法的运算步骤可归结为：

（1）起始步骤──在一个角点可行解上开始。

（2）迭代步骤──移动至一个更好一些的相邻角点可行解（根据需要反复进行这一步骤）。

（3）停止法则──在当前角点可行解比所有相邻角点可行解都更好些时停止。当前角点可行解就是一个较优解。

单纯形法的优点及其成功之处在于它只需要较少的有限次数的迭代，即可找到较优解。

严正声明：本文由历史百科网注册或游客用户曜曦自行上传发布关于» 单纯形法的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：曜曦；本文链接：https://www.freedefine.cn/wenzhan/61240.html