单纯形法理论

单纯形法理论（精选3篇）

单纯形法理论 篇1

单纯形法不用计算函数的导数，只需要计算目标函数的函数值，因此计算比较简单，几何概念也比较清晰，属于直接法的无约束最优化方法。所谓n维欧氏空间E中的单纯形，是指在n维空间中由n1个线性独立的点构成的简单图形或凸多面体。

基本思想：根据问题的维数n选取n1个线性独立的点，然后计算这n1个点的函数值并进行比较，确定其中的最大值的点及函数的下降方向，再设法找到一个新的好点替换函数值最大的点，从而构成新的单纯形。这个过程不断进行，新的单纯形将向极小点收缩。经过若干次迭代后，即可得到满足收敛条件的极小点。

基本过程包括：反射、扩张和压缩。下面以二维问题为例来说明单纯形法的求优过程。设二维函数f(X)在平面上有线性独立的三个点Xh，Xl，Xg，构成单纯形（三角形），计算这三个点的函数值，若

nf(Xh)f(Xg)f(Xl)

则说明Xh是最差点，Xl是最好点，Xg为次差点，迭代应该找出好的点Xr来替换最差点Xh，构成新的单纯形。Xr在Xh与除去最差点Xh以后所有顶点的形心点Xc连线的延长线上进行选取。

XrXc(XcXh)

式中：——反射系数，一般取1。

这个步骤称为反射。通常，反射点Xr的取法是使Xr点Xr点称为最差点Xh的反射点，至Xc点的距离等于Xc点到Xh的距离。

反射点Xr对新单纯形构造的影响，有以下几种情况：（1）扩张

1若反射点的函数值f(Xr)小于最好点的函数值f(Xl)，即当 ○f(Xr)f(Xl)

时，说明所取的方向是正确的，可进一步扩大效果，继续沿XhXr向前进行扩张，在更远处取一点Xe，并满足 XeXc(XrXc)

式中：——扩张系数，1.2~2.0，一般取2.0。

如果f(Xe)f(Xl)，说明扩张有利，就用Xe代替最差点Xh，构成新的单纯形。否则，说明扩张不利，舍弃Xe，仍以Xr代替最差点Xh，构成新的单纯形。

2若f(Xr)f(Xl)不成立，则不能进行扩张，此时如果 ○f(Xr)f(Xg)

则用反射点Xr替换最差点Xh，构成新的单纯形。（2）压缩

1若反射点的函数值f(Xr)小于最差点的函数值f(Xh)，但大于次差点的函数值○f(Xg)，即当

f(Xg)f(Xr)f(Xh)

时，则表示Xr点走得太远，需缩回一些，即进行压缩，并且得到的压缩点应为

XsXc(XrXc)

式中：——压缩系数，常取0.5。这时若f(Xs)f(Xh)

则用压缩点Xs代替最差点Xh，构成新的单纯形。

2若反射点的函数值f(Xr)大于最差点的函数值f(Xh)，即当 ○f(Xr)f(Xh)

时，应当压缩更加多些，即将新点压缩至Xh与Xc之间，这时所得的压缩点应为

XsXc(XcXh)Xc(XhXc)

如果f(Xs)f(Xh)，说明不能沿Xh的反射方向搜索，应进行缩边。（3）缩边

使单纯形向最好点进行收缩，即使最好点Xl不动，其余各顶点皆向Xl移近为原距离的一半。

XiXiXl

i0,1,,n 2从以上各步得到新的单纯形后，再重复开始各步，逐渐缩小单纯形直至满足精度要求为止。

初始单纯形的形成：

构成单纯形的顶点应是线性独立的，否则，如二维问题，三个点在一条直线上，就变成二维问题了，即在一条直线上找极小点的问题，称为退化。为防止退化，一般取成等边三角形，因为它是周长一定前提下包围面积最大的布点方式。

把二维等边三角形推广到n维的情况是n1个点中任两个点的距离都相等，这种单纯形就称为正规单纯形。选取正规单纯形作初始单纯形的方法如下：

给定一个初始点X0[x1,x2,,xn]T，其余n个点可取为：

X1[x1p,x2q,x3q,xnq]T



Xn[x1q,x2q,x3q,xnp]T

即第i个顶点的第i个坐标分量比初始点增加p，其他分量增加q。设正规单纯形任意两顶点的距离等于c，这时p，q的公式推导如下。对于点X2和X1，有X2X1c即

(x1qx1p)2(x2px2q)2(x3qx3q)2(xnqxnq)2c

2化简得

(qp)2(pq)22(pq)2c2

对于X1和X0，有X1X0c，即

(x1px1)2(x2qx2)2(x3qx3)2(xnqxn)2c2

化简得

p2(n1)q2c2

联立求解得 p(n1n1)c

n2(n11)c

n2q初始单纯形也可以采用下面的方法：设目标函数f(X)为n维向量，因此单纯形应有n1个顶点X1，X2，，Xn1。构造单纯形时，现在n维空间中选取初始点X1(0)（尽量靠近最优点），从X1(0)出发沿各坐标轴方向ei、以步长h找到其余n个顶点X(0)j（j2，3，…，n1）：

(0)X(0)Xj1hei

式中：ei——第i个坐标轴的单位向量；

h——步长，一般取值范围为0.5~15.0，接近最优点时要减小。构成初始单纯形的步长可取1.6~1.7。

构成初始单纯形后，可按以下步骤进行：

(k)(k)（1）计算各顶点的函数值并进行比较，找出最好点Xl(k)，最差点Xh，次差点Xg，(k)(k)(k)以及除最差点外其它各点的形心Xn2。求Xh对形心点Xn2的反射点：

(k)(k)(k)(k)Xn3Xn2(Xn2Xh)

(k)(k)(k)(k)（2）比较Xn，如果反射点Xn还好，即进行扩张，得扩张点3和Xl3比最好点Xl为：

(k)(k)(k)(k)Xn4Xn2(Xn3Xn2)

(k)(k)(k)(k)(k)得到扩张点Xn，否则4后，若f(Xn4)f(Xl)，用Xn4代替Xh，并转步骤（5）(k)(k)用Xn代替。X3h后转入步骤（5）(k)(k)若f(Xn3)f(Xl)，即反射点比最好点差，则转下一步。

(k)(k)（3）将反射点Xn3与次差点Xg比较，如果f(Xn3)f(Xg)，则用Xn3代替最(k)(k)(k)差点Xh，并转步骤（5）；若f(Xg)f(Xn3)f(Xh)，则用Xn代替X3h后进行

(k)(k)(k)(k)(k)(k)压缩，否则直接进行压缩，得压缩点为：(k)(k)(k)(k)Xn5Xn2(XhXn2)

(k)(k)(k)(k)(k)（4）求得压缩点Xn后与最差点比较，若，则用Xf(X)f(X)X5hn5hn5代替(k)以后转下一步；否则使单纯形向最好点Xl(k)收缩，收缩后的单纯形顶点为： XhX(jk)Xl(k)0.5(X(jk)Xl(k))

j1，2，…，n1

然后转下一步。

（5）进行收敛性检验。若

1n12(k)(k)f(X)f(X)jn2 n1j1则停止迭代并输出Xl(k)及f(Xl(k))，否则使kk1后转第1步。式中为任意的小(k)数，Xn2为形心。

12例

试用单纯形法求解目标函数f(X)4(x15)2(x26)2的极小值。

Function f=fun(x)syms

x1

x2

f = 4*(x1-5)^2+(x2-6)^2;clear

单纯形法理论 篇2

关键词：单纯形法,有限改进法,灵敏度分析,单纯形表

线性规划是现代管理中应用最为广泛的一种数学模型, 它是解决经营管理中如何有效利用现有人力、物力、财力完成更多的任务, 或在预定的任务目标下, 如何使耗用的人力、物力、财力最少, 以实现目标的问题. 1947年美国数学家G. B. Dantzig提出的单纯形法 (simplex method) 是解线性规划问题最为有效的方法. 作为运筹学的一个重要分支, 线性规划的应用极其广泛, 很多学者对单纯形法做了改进和补充. 线性规划问题的单纯形法一直是运筹学课程教学的重点和难点, 一些学者也做了单纯形法教学方面的研究, 为单纯形法的教学提供了新的思路. 单纯形法是一种迭代算法, 它求解线性规划问题的基本思想是:首先找出一个初始基可行解, 判断其是否为最优解;如果为否, 则转换到使得目标值不断增大, 并且与其相邻的基可行解, 直到找到最优解为止.

目前不同的教材在介绍单纯形法时采用的列表形式不一样, 鉴于这种情况, 本文就教材上两种常见的形式进行比较分析得出结果明显, 并且便于做灵敏度分析的形式, 通过算例说明这种形式既便于计算又便于教学.

1. 线性规划问题的标准型

为了叙述方便, 设讨论的线性规划模型为

其标准型为

max z = CX + 0XS, s. t. AX + IXS= b, X≥0, XS≥0. (2)

对于选定的可行基B, 不妨设B = (P1, P2, …, Pm) , N = (Pm + 1, Pm + 2, …, Pn) 是非基变量的系数矩阵, 则记A = (B, N) , 其中Pj (j = 1, 2, 3, …, m) 表示矩阵A的第j列. 相应的, 记

2. 单纯形法的两种形式

形式一式 (2) 的初始单纯形表通过单纯形法得到最优单纯形表为表1.

形式二 (有限改进法) 见参考文献[2].

3. 通过算例比较两种形式

下面通过用单纯形法两种形式求解一个一般的线性规划问题, 找出它们的区别与联系, 得出结论.

算例某塑料车间可以生产以下三种管状产品, 生产一个单位的甲管道需要塑料1 kg, 工时1个单位, 利润为2元;生产一个单位的乙管道需要塑料1 kg, 工时4个单位, 利润为3元;生产一个单位的丙管道需要塑料1 kg, 工时7个单位, 利润为11/3元. 问:

(1) 如何组织生产使总利润最大?

(2) 现有丁产品, 设生产1 m丁需塑料3 kg和工时5小时, 每m利润为7元. 问:是否应该生产丁产品? 如投产, 该车间最优生产计划有何变化?

解 (1) 设甲、乙、丙的产量分别为x1, x2, x3, 由题目所给数据可以建立以下数学模型:

将上述问题转化为标准型, 再采用单纯形法形式一求解, 最优单纯形表2所示.

由上表可得 此线性规 划问题的 最优解为: X = (45, 90, 0, 0, 0) T, 所以目标函数的最优解为max Z = 360.

采用第二种形式表3中进行求解:

由上表可得 此线性规 划问题的 最优解为: X = (45, 90, 0, 0, 0) T, 所以目标函数的最优解为max Z = 360.

对于形式二有限改进法, 根据参考文献[2]以上计算过程可以得出:

上述 (3) 中所得到的信息对也是进行灵敏度分析时的重要工具.

(2) 法一:采用形式一设丁产品的产量为x6, 其系数向量为p6= (3, 5) T, 其检验数为. 所以判定丁产品值得生产. 则其在最终单纯形表中对应的列向量为

在最优单纯形表中添加x6一列, 再按单纯形法计算可得最优值.

法二:采用形式二.

在最优单纯形表中添加x6一列:

再按单纯形法计算可得最优值.

4. 结论

从上一节的解题过程比较单纯形法两种形式, 归纳如下:

(1) 通过以上推导式 (3) 过程可以看出, 矩阵D中的第一列是 (1, 0, 0) T, 这是因为第一行是检验数行, 第一列的数都是表示指归形式中的运算符号与Ⅰ0的关系, 故第一例始终为 (1, 0, 0) T. B- 1是形式二的矩阵D中元素1的代数余子式.

推广到一般, 形式二用 于做灵敏 度分析的 矩阵

(2) 在灵敏度分析方面, 通过例题可以看出, 形式二用于做灵敏度分析一步到位, 用于其他类型的灵敏度分析也是一样的, 只需要用到矩阵D. 而形式一要分步骤完成灵敏度分析, 并且在分析过程中还要将表中的数字反号. 即形式二比形式一简单方便.

(3) 在表格构造上, 第一种形式与第二种形式的列表形式不同, 第二种要比第一种简单明了. 由于表格造的不同, 形式一在每一步计算σj时需要单独计算, 比较麻烦, 而形式二不存在这样的问题.

(4) 比起第一种形式, 在第二种形式的最优单纯形表中可以直接读出取最优解和最优值的信息.

单纯形法理论 篇3

（1） 单纯形法是解线性规划问题的一个重要方法，

其原理的基本框架为：

第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。

第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。

第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善—目标函数值增加，重复第二和第三步直到找到最优解。

（2） 用程序进行运算前，要将目标函数及约束方程变成标准形式。

于非标准形式须作如下变换：

a) 目标函数为极小值min z=CX时，转换为max z=-CX形式；

b) 在约束方程中有 “≤”时，在加上一个松弛变量；

c) 在约束方程中有 “≥”时，采用减去一个松弛变量，再加上一个人工变量；

d) 在约束方程中有 “=”时，加上一个人工变量；

e) 所有的人工变量，松弛变量的目标函数系数置为0。

（3） 对于标准形式的线性规划问题。用单纯形法计算步骤的框图。

2 程序测试及结果：

线性规划问题如下:

max z=2*x1-3*x2+3x3;

x1+ x2 -x3<=7;

x1- x2 +x3<=-7;

x1-2*x2 +2*x3<=4;

x1,x2,x3>=0;

3 C++实现代码