单纯形法

function [zyj,zyz,k]=ssssimplex(A,N) %A为初始单纯型表和书上的形式一样[m,n]=size(A); % 分别代表A的行数和列数%N为基本可行解的下标

k=0; %迭代次数%zyj为最优解

%zyz为最优值

flag=1; %定义一个逻辑变量

while flag

k=k+1;

if A(1,:)>=0 %已找到最优解

flag=0;

zyj=zeros(1,n-1);%给每个变量赋初值0

for i=2:m

zyj(N(i-1))=A(i,n);%给基变量赋新值

end

zyz=-A(1,n);%给出最优解

else %判断问题是否不可解

for i=1:n-1

if A(1,i)<0&A(2:m,i)<=0 %问题不可解

disp('there is no answer');

flag=0;

break;

end

end

if flag %还不是最优表，进行转轴运算

temp=0;

for i=1:n-1

if A(1,i)

temp=A(1,i); %为了求出第一行最小值的位子

inb=i; % 进基变量的下标%inb为进基量下标

end

end

sita=zeros(1,m-1);

for i=2:m

if A(i,inb)>0 %为了求出相除以后最小的值

sita(i-1)=A(i,n)/A(i,inb);

end

end

temp=inf; %定义一个无穷量inf

for i=1:m-1

if sita(i)>0&sita(i)

temp=sita(i);

outb=i+1; %出基变量下标

end

end %选择最小的sita横向对应的变量为出基变量

%以下更新N

for i=2:m

if i==outb

N(i-1)=inb;%以进基变量的下标替代出基变量的下标

end

end

%以下进行转化运算

A(outb,:)=A(outb,:)/A(outb,inb);%将主元化为1

for i=1:m

if i~=outb

A(i,:)=A(i,:)-A(outb,:)*A(i,inb);%将进基变量所在列除主元外的其余元素化为0

end

end

end

end

end

有关线性规划单纯形法的原理及详细过程看

https://www.wendangku.net/doc/eb8808046.html,/zsb/zgs/zgs05/zgs052/zgs05203/zgs052030 .htm。还可以看书《线性规划的新方法和应用》。

我就写写具体过程及我在这个过程犯的错误吧：

1 肯定是建立规划的数学模型：设变量，列不等式和目标函数。

2 将不等式转为标准型，也就是把不等式变为等式。在这个过程中在>=的式子里减去一个正的变量（也就是系数为-1），<=的式子中加一个正的变量(也就是系数为+1)。

3 确定基变量及对应价值系数，并计算检验数。在最大化问题中：全部检验数非正；在最小化问题中：全部检验数非负。如果检验数符合要求则已经找到合适的基变量，进入6。否则进入4，找主元。

4 找主元。

A：如果某一检验数不符合要求且这一列所有元素为负，则无最优解。

B：确定进基变量。根据max{| 检验数|}，确定所在列。这列所对应的变量就为进基变量，这一列称为主元素列。

C：确定出基变量。用常数列除以主元素列得到商。在求商的过程中一定要注意主元素列中的零和负数应略去，不参加比较，因为线性规划是解决实际问题的。在所有商中找到最小值所在行。这一行的基变量出基。

5 换基迭代：基变量换，对应价值系数换，并进行初等变换：把主元素变成 1，主元列的其他元素变为0。重复步骤3。

6 计算值，并判断。计算时我用的是牛顿迭代法。检验最后一步中非基变量的检验数是否有为0的，有就还可以进行迭代，计算其余最优解解，否则最优解唯一。

具体代码：

'初始化变量

For i = 0 To t - 1

X(i) = CStr(i + 1)

Next

'初始化基变量,数字代表设的第几个变量

j = 0

For i = nCount + 1 To t

Xb(j) = X(i)

j = j + 1

Next

'初始化基变量价值系数数组

For i = 0 To b

Vb(i) = Value(CInt(Xb(i)) - 1)

Next

'初始化检验数数组

For i = 0 To t - 1

C(i) = 0

Next

k = 1 '表示循环次数

Do

'计算检验数

For i = 0 To t - 1

For j = 0 To b

C(i) += Xs(j, i) * Vb(j)

Next

C(i) -= Value(i)

If C(i) < 0 Then

Dim xx As Integer

Dim count As Integer

count = 0

For xx = 0 To b

If Xs(xx, i) < 0 Then

count += 1

End If

Next

If count >= b + 1 Then

exi = True '检验数为负，且这一列所有的系数也为负，则无最优解End If

If exi Then

'Response.Write("某些参数设置错误，请重新选择") Response.Write("")

Exit Sub

End If

End If

Next

'检验数是否全为正,并找到最小

Dim cnt As Integer

Dim min As Single

Dim min_j As Integer '最小值的脚标，'入基脚标

min_j = 0

min = C(0)

cnt = 0

For i = 0 To t - 1

If C(i) >= 0 Then

cnt += 1

End If

If Not i = 0 And C(i) < min Then

min = C(i)

min_j = i

End If

Next

If cnt >= t Then '开始要计算最优解

Exit Do

End If

'否则出基入基

'计算比值

Dim Bz(b) As Single

Dim minc As Single

Dim minc_j As Integer '出基脚标

For i = 0 To b

If Xs(i, min_j) > 0 Then

Bz(i) = Xs(i, t) / Xs(i, min_j)

Else

'不能计算的置最大值

Bz(i) = 100000

End If

If i = 0 Then

minc = Bz(0)

minc_j = 0

Else

If minc > Bz(i) Then

minc = Bz(i)

minc_j = i

End If

End If

Next

'替换

Xb(minc_j) = min_j + 1

Vb(minc_j) = Value(min_j) '==Vb(minc_j)=Value(CInt(Xb(minc_j))-1)

'初等变换

If Not Xs(minc_j, min_j) = 1 Then

Dim ss As Single

ss = Xs(minc_j, min_j)

For i = 0 To t

If Not i = min_j Then

Xs(minc_j, i) = Xs(minc_j, i) / ss

End If

Next

Xs(minc_j, min_j) = 1

End If

For i = 0 To b

If Not i = minc_j Then

If Not Xs(i, min_j) = 0 Then

Dim tt As Single

Dim cs As Single

cs = Xs(i, min_j) '作除数

For j = 0 To t

tt = Xs(minc_j, j) * (-cs)

Xs(i, j) = Xs(i, j) + tt

Next

End If

End If

Next

k = k + 1

If k > 100 Then

exi = True

Response.Write("") Exit Sub

End If

'初始化检验数数组

For i = 0 To t - 1

C(i) = 0

Next

Loop

一、线性规划单纯形法的概念

（一）线性规划单纯形解法的基本思路

若一个凸集仅包含有限个极点，则称此凸集为单纯形。

线性规划的可行域是单纯形（证明略，但可以从上节图解法的例子得到认同），进而线性规划的基可行解又与线性规划问题可行域的极点1-1对应（定理2.2.2），线性规划单纯形法就是基于线性规划可行域的这样的几何特征设计产生的。这个方法最初是在20世纪40年代由George Dantzig研究出来的。这个线性规划单纯形解法的基本思路是：先求得一个初始基可行解，以这个初始基可行解在可行域中对应的极点为出发点，根据最优准则判断这个基可行解是否是最优解，如果不是转换到相邻的一个极点，即得到一个新的基可行解，并使目标函数值下降，这样重复进行有限次后，可找到最解或判断问题无最优解。

（二）单纯形法的最优准则

设：线性规划（LP）为：

min cx

s.t. Ax=b

x≥0

A为（LP）的约束方程组的m*n阶系数矩阵（设n≥m），A的秩为m；B是线性

规划的一个基，不失普遍性，记

定义

则：称λ，或者λ

,(j=1,2,…,n)为检验数。

j

若：λ≤0，即全部λ

非正，

i

则：由B确定的基可行解是（LP）的最优解。

（参看附录2.3.1）

二、线性规划单纯形法的表格解法

较简单的线性规划可以采用单纯形法的表格形式，这样利用计算器就可求解。单纯形法的表格解法的基本思路是，对基可行解建立单纯形表，依据此表作最优解判断，以及从原基可行解向目标值更小的新可行解转换的计算。

对于由基阵B确定的基可行解，其单纯形表为表2.3.1形式。对于初始基可行解，其单纯形表的构建方法为：先建立表2.3.2形式的表格，然后应用“行变换”将表2.3.2中的前m列，即基变量对应的列

转换为

其中0是m元0向量：0=(0,0,…,0), 是m阶单位方阵。在这样的行变换下，表2.3.2将转换为表2.3.1

表2.3.1

表2.3.2

（参看附录2.3.2）

（一）直接求解

对如下形式的较简单的线性规划可直接采用单纯形法的表格形式求解：

min cx

s.t. Ax≤b

x≥0

这种形式的线性规划标准化后，为

min cx+ox'

s.t. Ax+lx'=b

x≥0,x'≥0

其中x'=(x

1',x

2

',…,x

m

')为松驰变量，而o=(0,0,…,0)T。现在新的约束矩阵为

因为I是m*n的单位矩阵。所以我们就可用这个矩阵作基阵，松驰变量是基变量，立即得到一个初始基可行解，其目标函数值为0，而相应的初始单纯形表如表2.3.3所示。表中

θ=o=(0,0,…,0)T,

从而可开始单纯形表上求解的过程。

表2.3.3

下面我们通过一个实例看单纯形表解线性规划问题的一般步骤例2.3.1 用直接法求解（LP）

max z=40x

1+45x

2

+24x

3

s.t. 2x

1+3x

2

+x

3

≤100

3x

1+3x

2

+2x

3

≤120

x 1,x

2

,x

3

≥0

解：

第一步先将原问题化为标准形式

min -z=-40x

1-45x

2

-24x

3

s.t. 2x

1+3x

2

+x

3

+x

4

=100

3x

1+3x

2

+2x

3

+x

5

=120

x 1,x

2

,x

3

,x

4

,x

5

≥0

第二步列出初始单纯形表

此时，基可行解(0,0,0,100,120)T为，目标函数值为0. 第三步检查检验数

λ=(40,45,24,0,0)≥0

因此基可行解不是最优解，要进行基的转换。

当大于零的检验数不止一个，理论上可任选一个正检验数对应非基变量为进基变量，一般情况选取最大正值的检验数对应的非基变量为进基变量，这样迭代常常会快一些。为此，我们选x

2

进基，因为

因此，x

4为离基变量，则新的基变量为x

2

，x

5

。

第四步建立新的基相应的单纯形表

如何从原来的表转到新的基相应的单纯形表呢？只要把A中x2相应的列向量通过初等变换化成单位向量即可。因此在上表中只要把x2对应的列

化成

我们称基变量x4所在行和非基变量x2所在列相交元素为变换轴心，用加＊表示，现在这数为3，将这行乘以（-1）加到第三行，乘以（-15）加到第一行，然后将这行行除以3，得一个新的单纯行表

这样我们作了一次转换，新的基可行解为(0,100/3,0,0,20),目标函数值为-1500。

现在再回到第三步。现在λ

1=10,λ

3

=9均大于零，仍不是最优解，取x

1

进基；

因为：

所以，x

5

离基。

现在所有检验数均小于等于零，这个基可行解（20，20，0，0，0）是最优解，原问题最优值1700.以后。

实际在表上作业时，求λ

k 与x

r

的过程可不写，这些表可连在一起。

（二）单纯形法求解的基本步骤

首先我们需要对单纯形表作进一步的认识，注意到检验数：

可见，对应于基变量的λ

=0(j=1,2,Λ,m)，而且

j

再记

进而记

这样单纯形表2.3.1可呈现为表2.3.4的形式：

表2.3.4

有了表2.3.4，单纯形表上解法的一般步骤为：步一：把线性规划模型变成它的标准形式；

步二：确定初始基可行解，建立初始单纯形表；

步三：检查对应于非基变量的检验数λ

j ,(j∈N)；若所有这些λ

j

均小于零，则

已得到最优解，停止计算，否则转入下一步；

步四：在所有的λ

j >0中，若有一个λ

k

在单纯形表上对应的列向量的全部元素

y

ik

≤0(i=1,2,…,m)，则此问题无解，停止计算；否则转入下一步；

步五：根据max{λ

j >0|j∈N}=λ

k

, 即确定λ

k

对应的非基变量λ

k

为进基变量；

再根据

确定基变量x

r

为离基变量；

步六：基可行解的转换运算，即实施行变换，将单纯形表上x

k

对应的列向量变

换为单位向量，其中包括将λ

k 变换为0，而原y

rk

变换为1，称元素y

rk

为变换轴

心。

（三）两阶段法

对一般的线性规划，往往不会象用直接法求解形为Ax≤b的线性规划那样，能够很容易找到初始基可行解，甚至连有无可行基都难以判定，这时就需要应用两阶段法来求解线性规划。

二阶段法就是把解线性规划问题划分为两个阶段，第一阶段求出原问题的一个基可行解或判断原问题可行域为空；第二阶段在得到的基可行解基础上求解原问题。方法如下：

第一阶段

人为地在原约束矩阵中增加一些变量使得到单位矩阵，增加的变量称为人工变量，目标函数是人工变量之和。具体而言，对于原线性规划标准化后的Ax=b,(b≥0)的形式，若A中不包括单位矩阵，则我们在每个方程后面加一个“人工变量”得到一个新的线性规划（LP）如下：

（当A中有一些单位向量时，人工变量可少于m个）为书写方便我们记（LP0）为：

其中E

m

=(1,1,K,1),分量全为1的m元横向量，

这儿I

m 是可行基，又因为x

a

≥目标函数E

mx

有下界0，所以（LP0）一定有最优解。

设最优解为：

则可能有三种情形：

(1)若：在最优解x0的基变量中，不存在人工变量，即人工变量x

n+1,x

n+2

,…,x

n+m

都是非基变量。

则：x0的前n个分量(x

10,x

2

0,K,x

n

0)便是原线性规划问题的一个基可行解。可进

入第二阶段。

(2)若：在最优解x0的基变量中，包括某些人工变量，并且最优值z>0。则：原线性规划可行域为空，原线性规划无解。

(3)若：在最优解x0的基变量中，包括某些人工变量，但最优值z=0，即，此时为基变量的人工变量都取值为0。

则：设x

n+1

是一个人工变量的基变量，其在最优解的单纯形表中对应第S行，设J是非人工变量中非基变量的下标集。

① 如果单纯形表的第S行中，所有的y

sk

=0,(k∈J)此示原约束Ax=b中第S行为其余行的线性组合，即是个多余的约束，应当删去；

② 如果存在y

sk

≠0 (k∈J),

则无论y

sk 是正还是负，以它为变换轴心，x

k

进基，x

n+1

离基.如果新表中的基变

量中还有人工变量，重复以上步骤，有限次可得到（1）的情形。

第二阶段

步1：以第一阶段最优解对应的单纯形表为基础，删去人工变量对应的列，并且将原规划（已标准化）的-c作为检验数，放在第一行，然后用用行变换将基变量对应的检验数消为零。

步2：以步1结束时建立单纯形表为原线性规划的初始单纯形表，求解原线性规划。

[例2.3.2]用二阶段法求解（LP）：

min x

1-2x

2

s.t. x

1+x

2

≥2

-x

1+x

2

≥1

x

2

≤3

x 1,x

2

≥0

解：

先标准化：

min x

1-2x

2

s.t. x

1+x

2

-x

3

=2

-x

1+x

2

-x

4

=1

x 2+x

5

=3

x 1,x

2

,x

3

,x

4

,x

5

≥0

第一阶段：

因为A中对应单位向量

，故只要引进两个人工变量x

6,x

7

即可

min x

6+x

7

s.t. x

1+x

2

-x

3

+x

6

=2

-1+x

2-x

4

+x

7

=1

x 2+x

5

=3

x 1,x

2

,K,x

7

≥0

在第一行放入检验数：

这等价于在第一行放-c，再用行变换使基变量的检验数为零。

得到第一阶段最优解，人工变量不是基变量，最优值为0，则去掉x

6,x

7

所在两

列就是原问题基可行解。

第二阶段

仍将-c放在第一行，用行变换将基变量对应的检验数消为零。

现在检验数全小于等于零，得到原问题最优解x*=(0,3,1,2,0)T最优值-6。[例2.3.1.3]用二阶段法求解（LP）：

min -3x

1+4x

2

s.t. x

1+x

2

≤4

2x

1+3x

2

≥18

x 1,x

2

≥0

标准化：

min -3x

1+4x

2

s.t. x

1+x

2

+x

3

=4

2x

1+3x

2

-x

4

=18

x 1,x

2

,x

3

,x

4

≥0

第一阶段：

min x

5

s.t. x

1+x

2

+x

3

=4

2x

1+3x

2

-x

4

+x

5

=18

x 1,x

2

,x

3

,x

4

,x

5

≥0

为了少写一张表，也可在表最上方一行放，然后再用行变换使基变量的检验数为零。

已得到第一阶段最优解，但人工变量仍留在基里，并且最优值z=6>0故原问题可行域为空。原线性规划无解。

线性规划单纯形法的一个m a t l a b程序

发表日期:2009-03-16 15:47:49 作者:xgmath 本页面已被访问981次

%求解标准型线性规划:max c*x;s.t. A*x=b;x>=0

%本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b

%N是初始的基变量的下标

%输出变量sol是最优解

%输出变量val是最优值，kk是迭代次数

function [sol,val,kk]=ssimplex(A,N)

[mA,nA]=size(A);

kk=0; %迭代次数

单纯形法基本原理

工程优化设计中单纯形法的基本原理 张云龙 （大连海洋大学土木工程学院辽宁大连116023) 摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。 关键词：线性规划图解法单纯形法大M法 THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN ZHANG Y un-long (Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023) Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method. Key W ords: Linear programming；Graphic method；Simplex Method; Big M Method 1引言 在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。 虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误！未找到引用源。。 因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。 2线性规划问题 2.1数学模型 线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？ 表1-1 工时及利润简表

利用修正单纯形法解线性规划问题(精)#优选、

利用修正单纯形法解线性规划问题一软件示意：

二代码说明： Dim A(1 To 3, 1 To 6) As Double '矩阵A Dim a1(1 To 3) As Double '矩阵A的第一列向量 Dim a2(1 To 3) As Double '矩阵A的第二列向量 Dim a3(1 To 3) As Double '矩阵A的第三列向量 Dim a4(1 To 3) As Double '矩阵A的第四列向量 Dim a5(1 To 3) As Double '矩阵A的第五列向量 Dim a6(1 To 3) As Double '矩阵A的第六列向量 Dim B_(1 To 3, 1 To 3) As Double '基矩阵B的逆矩阵 Dim XB(1 To 3) As Double '基本可行解 Dim b(1 To 3) As Double '右端向量b Dim C(1 To 6) As Double '检验数 Dim CB(1 To 3) As Double '基本可行解对应的检验数 Dim π(1 To 3) As Double '单纯形乘子矢量 Dim r(1 To 6) As Double '检验矢量r Dim r_min As Double '检验矢量最小值 Dim k_sign As Integer '检验矢量最小值对应的位置 Dim Y(1 To 3, 0 To 6) As Double '矩阵y Dim just_vector(1 To 3) As Double Dim liji_min As Double '用于判断离基变量所用值 Dim r_sign As Integer '用于记录离基变量对应的位置 Dim main_yuan As Double '用于存放主元 Dim Erk(1 To 3, 1 To 3) As Double Dim Exchange_B(1 To 3, 1 To 3) '在矩阵Erk与矩阵B_进行乘法运算时，作为矩阵B_的替换矩阵

单纯形法

2.2 单纯形法 考虑标准最大化线性规划问题的)15.1( max ∑=n j j j x c 1 ..t s ?????=≥=≤∑=n j x m i b x a j i n j j ij ,...,2,10,...,2,11 我们首先对它的第i 个约束条件引入松弛变量i s ,m i ,...,2,1=,并且以η表示目标函数值,则获得标准型)15.1(的等价线性规划,也称为标准型)15.1(的标准格式: max ∑==n j j j x c 1η ..t s ??? ????=≥=≥=-=∑=m i s n j x m i x a b s i j n j j ij i i ,...,2,1,0,...,2,1,0,...,2,1,1 )10.2( 从例1.2线性规划问题的求解过程中可以看到,随着迭代的继续,决策变量和松弛变量相互交织,成为一体,所以为了便于分析,令i i n s x =+m i ,...,2,1=,并引入以下标记: ),...,,,...,(),...,,,,...,,(1212121m n n n m n x x x x x s s s x x x ++= 那么,我们将)10.2(改写为: max ∑==n j j j x c 1η ..t s ?? ???++=≥=-=∑=+m n n n j x m i x a b x j n j j ij i i n ,...,1,,...,2,1,0,...,2,1,1 )11.2( 式)11.2(就是标准型线性规划问题)15.1(的标准格式或初始单纯形,显然若令0=j x ,n j ,...,2,1=,则有i i n b x =+,m i ,...,2,1=,则),...,,,0,...,0(210m b b b x =构成了标准型线性规划问题)15.1(的初始基可行解。随着搜索最优解过程的继续,单纯形迭代算法将从

单纯形法步骤例题详解

单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z

j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。

单纯形法的计算方法

第4章 单纯形法的计算方法单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z = 从Pj ( j = 1 , 2 , ? , n)中一般能直接观察到存在一个初始可行基 （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 及 ( i = 1 , 2 , ? , m; j = 1 , 2 , ? , n)进行编号, 则可得下列方程组 显然得到一个m×m单位矩阵 以B 作为可行基。将上面方程组的每个等式移项得 令由上式得 又因 ≥0, 所以得到一个初始基可行解 （3）第三种情况：对所有约束条件是“ ≥”形式的不等式及等式约

束情况, 若不存在单位矩阵时, 就采用人造基方法。即对不等式约束减去一个非负的剩余变量后, 再加上一个非负的人工变量; 对于等式约束再加上一个非负的人工变量, 总能得到一个单位矩阵。 4.2 最优性检验和解的判别 对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况, 为此需要建立对解的判别准则。一般情况下, 经过迭代后可以得到： 将上代入目标函数，整理后得 令 于是 再令 则 (1) 最优解的判别定理 若为对应于基B的一个基可行解，且对于一切 且有则 为最优解。称为检验数。 (2) 无穷多最优解的判别定理 若为一个基可行解， 且对于一切 且有 又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。 (3) 无界解判别定理 若为一个基可行解，有一个> 0 ,并且对i = 1 , 2 , ?, m,有≤0 , 那么该线性规划问题具有无界解(或称无最优解)。 4.3 基变换

单纯形法的解题步骤

三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.

解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8

（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量

MOP多目标规划

多目标规划 multiple objectives programming 数学规划的一个分支。研究多于一个目标函数在给定区域上的最优化。又称多目标最优化。通常记为VMP。在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的。因此有许多学者致力于这方面的研究。1896年法国经济学家V.帕雷托最早研究不可比较目标的优化问题，之后，J.冯·诺伊曼、H.W.库恩、A.W.塔克尔、A.M.日夫里翁等数学家做了深入的探讨，但是尚未有一个完全令人满意的定义。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等；另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。对多目标的线性规划除以上方法外还可以适当修正单纯形法来求解；还有一种称为层次分析法，是由美国运筹学家沙旦于70年代提出的，这是一种定性与定量相结合的多目标决策与分析方法，对于目标结构复杂且缺乏必要的数据的情况更为实用。 1947年，J.冯·诺伊曼和O.莫根施特恩从对策论的角度提出了有多个决策者在彼此有矛盾的情况下的多目标问题。1951年，T.C.库普曼斯从生产和分配的活动中提出多目标最优化问题，引入有效解的概念，并得到一些基本结果。同年，H.W.库恩和A.W.塔克尔从研究数学规划的角度提出向量极值问题，引入库恩-塔克尔有效解概念，并研究了它的必要和充分条件。1963年，L.A.扎德从控制论方面提出多指标最优化问题，也给出了一些基本结果。1968年，A.M.日夫里翁为了排除变态的有效解，引进了真有效解概念，并得到了有关的结果。自70年代以来，多目标规划的研究越来越受到人们的重视。至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。 化多为少 即把多目标规划问题归为单目标的数学规划（线性规划或非线性规划）问题进行求解，即所谓标量化的方法，这是基本的算法之一。 ①线性加权和法对于多目标规划问题（VMP），先选取向量 要求λi>0(i=1,2，…,m) 作各目标线性加权和

线性规划——单纯形法文档

线性规划——单纯形法 设计文档 ——《通用优化模块》 编写人：徐天爽 编写时间：2010年06月完成 2010年06月整理

目录 第一部分功能概述 (1) 第二部分理论知识 (2) 2.1 线性规划标准型 (2) 2.2单纯形法 (4) 2.2.1修正单纯形法 (4) 2.2.2Bland规则 (7) 第三部分程序主要内容 (9) 第四部分程序测试 (10) 备注 (17) 参考文献 (18)

第一部分功能概述 单纯形法是线性规划算法的一种。由于若线性规划问题有最优解，则一定存在一个基本可行解是最优解，因此单纯形法是通过沿着可行集的边界，从一个顶点转移到改善当前目标函数值的相邻定点，以此来寻找最优解。 程序编写了加入Bland规则的修正单纯形法，只需用户给定设计变量个数、约束条件个数、约束条件系数，委托矩阵操作类MatrixOperation进行矩阵运算，即可实现线性规划问题的优化。

第二部分 理论知识 线性规划问题具备以下性质： 定理1 若线性规划问题的可行域X 非空，则X 是一个凸集。 定理2 线性规划问题的每一个基本可行解x 都对应于可行域X 的一个顶点。 定理3 若线性规划问题有最优解，则一定存在一个基本可行解是最优解。 定理4 若线性规划问题有最优解，则目标函数的最优值一定可以再可行域 X 的某个顶点上达到。 2.1 线性规划标准型 定义1 如果目标函数是设计变量的线性函数，且约束条件也是关于设计变量的线性等式或线性不等式，则相应的数学问题就称为一个线性规划问题。 单纯形法计算问题的最优值需要将原问题统一为标准形式。定义线性规划问题的标准形式为： 定义2 给定线性规划问题的标准型为 ()()1 1min .. 1,2,,01,2,,n j j j n ij j i j j z c x s t a x b i m x j n ==? =?? ? ==?? ?≥=?? ∑∑ (1) 其中()01,2, ,i b i m ≥=。即对目标函数一律求最小值；设计变量均非负；约束 条件除非负约束条件之外一律为等式约束；约束条件的右端项一律非负。 定义3 如果约束条件中含有不等式1n ij j i j a x b =≤∑且0i b ≥，则可引入一个新 的变量i x '，称为松弛变量；如果约束条件中含有不等式1 n ij j i j a x b =≥∑且0i b ≥，则 可引入一个新的变量i x ''，称为剩余变量。

修正单纯形法求解约束优化问题

修正单纯形法求解约束优化问题 姓名王铎 学号 2007021271 班级机械078 日期 2010/6/23

一．问题分析 求解约束优化问题中，假如目标函数和约束条件都是线性的，像这类约束函数和目标函数都是线性函数的优化问题称作线性规划问题。从实际问题中建立数学模型一般有以下三个步骤： 1.根据影响所要达到目的的因素找到决策变量； 2.由决策变量和所在大道目的之间的函数关系确定目标函数； 3.有决策变量所受的限制条件确定决策变量所要满足的约束条 件； 求解线性规划问题的基本方法是单纯形法，而本文研究的是修正单纯形法。1965 年由J.A.Nelder 等提出。是在基本单纯形优化法的基础上，引入了反射、扩展与收缩等操作规则，变固定步长推移单纯形为可变步长推移单纯形，在保证优化精度的条件下，加快了优化速度。是各种单纯形优化法在分析测试中应用最广的一种。 二．数学模型 1、线性规划问题的formalization 问题(1.1)称为线性规划问题： x= arg min_x c^T x s.t. Ax=b x>=0 (1.1) 其中x为n维列向量，A为m*n的矩阵，b和c分别为m,n维的常数向量。 任意一个线性不等式组约束下求解线性函数的最大最小值问题

都可以归结到问题(1.1)来。 比如 A(i,:) x <= b(i) <=> A(i,:) x + y(i) = b(i) y(i)>=0 (1.2) A(i,:) x >= b(i) <=> A(i,:) x - y(i) = b(i) y(i)>=0 (1.3) x <=> x=x'-x" x'>=0 x">=0 (1.4) 2、单纯形法 设mn，则可能符合约束的x不存在， 最优问题同样没有意义。） 此时记A=[B,N],B为m*m的方阵，N为m*(n-m)的矩阵，假设B 非奇异，（奇异的情况后面会讨论）

大连理工大学庞丽萍最优化方法MATLAB程序

班级：优化1班授课老师：庞丽萍姓名：学号： 第二章 12.（1）用修正单纯形法求解下列LP问题: >>clear >>A=[121100;123010;215001]; [m,n]=size(A); b=[10;15;20]; r=[-1-2-31]; c=[-1-2-31]; bs=[3:3]; nbs=[1:4]; a1=A(:,3); T=A(:,bs); a2=inv(T)*a1; b=inv(T)*b; A=[eye(m),a2]; B=eye(m); xb=B\b; cb=c(bs); cn=c(nbs); con=1; M=zeros(1); while con M=M+1; t=cb/B; r=c-t*A; if all(r>=0) x(bs)=xb; x(nbs)=0; fx=cb*xb; disp(['当前解是最优解，minz=',num2str(fx)]) disp('对应的最优解为,x=') disp(x) break end rnbs=r(nbs); kk=find(rnbs==min(rnbs)); k=kk(1); Anbs=A(:,nbs); yik=B\Anbs(:,k); xb=B\b;%yi0 if all(yik<=0)

disp('此LP问题无有限的最优解，计算结束',x) disp(xb) break else i=find(yik>0); w=abs(xb(i,1)./yik(i,1)); l=find(w==min(w)); rr=min(l); yrrk=yik(rr,1); Abs=A(:,bs); D=Anbs(:,k); Anbs(:,k)=Abs(:,rr); Abs(:,rr)=D; F=bs(rr); bs(rr)=nbs(k); nbs(k)=F; AA=[Anbs,Abs]; EE=eye(m); EE(:,rr)=-yik./yrrk; Errk=EE; Errk(rr,rr)=1/yrrk; BB=Errk/B; B=inv(BB); cb=c(:,bs); xb=Errk*xb; x(bs)=xb; x(nbs)=0; fx=cb*xb; end if M>=1000 disp('此问题无有限最优解') break end end %结果 当前解是最优解，minz=-15 对应的最优解为,x= 2.5000 2.5000 2.50000

单纯形搜索方法

1．搜索方法 我们这里以二维为例说明搜索方法 在二维情况下的单纯形有3个顶点： X G X L 二维情况：三个顶点 计算各点的函数值，设好点为x L, 最坏点为x H, 次坏点为x G 求除x H（最坏点）以外的其余各点的几何中心x C x C= ∑ ≠ = n H j j xj n & 1 单形替换法主要有以下集中搜索方法 （1）反射 以x C为中心，将x H按一定比例反射，得x R; x R=x C+α( x C―x H) (通常α=1) （2）扩张 若f(x R)< f(x L),则搜索方向正确，应扩张，（比最好点还要好）x E=x R+r ( x R―x C) r扩张系数r=1.2~2.0

?? ?? ?≥

运筹学课程标准

《运筹学》课程标准 一、课程概述 运筹学是数学的一门分支学科，也是管理科学的一个分支学科。它是一门应用性、综合性强的科学。它是实现管理现代化的有力工具，在生产管理、工程技术、军事作战、科学试验、财政经济以及社会科学中得到广泛应用。 运筹学通过建立数学模型或模拟模型运用数学方法对于要求解的问题得到合理的决策。二、课程目标 1．知道《运筹学》这门学科的性质、地位和独立价值。知道这门学科的研究范围、应用领域、研究方法、学科进展和未来方向。 2．理解这门学科的主要概念、基本原理和基本方法。 3．初步学会运用一些具体的方法与技术，如单纯形法、对偶单纯形法、修正单纯形法等解决线性规划问题。 三、课程内容和教学要求 这门学科的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下： 知道———是指对这门学科的内涵与外延的认知。 理解———是指对这门学科涉及到的概念、原理的说明和解释。 掌握———是指课程涉及的方法的理论根据、适应范围、所需条件等的理性认识。 学会———是指能运用该课程的基本原理、基本方法分析、处理和解决实际问题。 教学内容和要求表中的“√”号表示对知识和方法的教学要求层次。 本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。（一）绪论

（二）线性规划 （三）修正单纯形法 （四）对偶单纯形法

（五）线性规划的特殊类型及目标规划 （六）整数规划

（七）动态规划 （八）非线性规划 （九）库存论 （十）排队论

四、课程实施 （一）课时安排与教学建议 ?运筹学?是数学与应用数学、信息与计算科学的专业限选课，共54课时，具体课时安排如下： （二）教学组织形式与教学方法要求 1、教学班是主要的教学组织，班级授课制是目前教学的主要组织形式。 2．注意教学方法的灵活性，组织学生自我讨论、分析、提出问题教学、阅读指导等。。 3．充分发挥学生的主动性，运用启发式教学，引导学生自我进行方法的发现与总结。 五、教材编写与选用 《运筹学》教材要在课程标准的统一要求下，实行多样化。可以选用普通高校重点教材。也可以选用21世纪教材。 六、课程评价 1．这门学科的评价依据是本课程标准规定的课程目标、教学内容和要求。该门课程采用平时考核（80%）、和集中考试（20%）相结合的形式进行。

单纯形法

单纯形法 可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式 的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则，适用 于在电子计算机上进行求解运算；后者将变量和数据列成表格，适用于笔算。两 者在数学上是等价的。单纯形法是由美国数学家G.B.丹齐克（1914～）于1947 年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～）于1938年提出的 解乘数法相类似。 根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2， (x) 的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大n 值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所 确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目 的就是要找出最优解。 可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解； ③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止 目标函数的值无限增大（或向负的方向无限增大）。 要缩小对最优解的搜索范围，就必须认识最优解的一般性质，最优解如果存 在的话，则它必然处于可行区域的边界上。 任何一项约束条件的边界方程是用“＝”号来替换该约束条件中的“≤”或 “≥”号而得到的。每一个边界方程确定一个超平面。因此，可行区域的边界是 由那些满足一个或同时满足几个边界方程（即处在作为边界的一个或几个超平面 上）的可行解所组成，而且最优解必在其中。最优解不仅是在可行区域的边界上， 而且也在这个区域的一个隅角上。一个可行解，如果不处在由另两个可行解连接 起来的任何线段上，它就是一个角点可行解。如果连接两个角点可行解的线段处 在可行区域的边界上，这两个角点可行解就称为相邻的角点可行解。角点可行解 具有下列三个重要性质：①如果存在着一个最优解，那么它必定是角点可行解。 如果存在有多个最优解，那么至少有两个最优解必定是相邻的角点可行解。②只 存在有限个数的角点可行解。③如果一个角点可行解按目标函数值来衡量时比其 所有的相邻角点可行解更好一些，那它就比所有其他角点可行解都更好，也就是 最优解。

单纯形法

单纯形法（不可以解空集问题，无初始解） 一、单纯形法的基本思想 1、顶点的逐步转移 即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。 2．需要解决的问题： (1)为了使目标函数逐步变优，怎麽转移？ (2)目标函数何时达到最优——判断标准是什么？ （3）初始解的寻找 二、单纯形法原理（用代数方法求解LP） 第一步：引入非负的松弛变量（x3 x4 x5）和剩余变量（算完后剩余的资源） x3,x4,x5, 将该LP化为标准型 第二步：寻求初始可行基（单位阵对应的），确定基变量 第三步：写出初始基本可行解（很多之中找一个，必令原x为0）和相应的目标函数值 两个关键的基本表达式： ① 用非基变量表示基变量的表达式 ② 用非基变量表示目标函数的表达式 第四步：分析两个基本表达式，看看目标函数是否可以改善？ ① 分析用非基变量表示目标函数的表达式 非基变量前面的系数均为正数（必为负数才可以），所以任何一个非基变量进基都能使Z值增加 通常把非基变量前面的系数叫“检验数” ②选哪一个非基变量进基？ 排在最前面的负检验数对应的非基变量 ③确定出基变量 “最小比值原则”（或θ原则）见本 如果x2≤0，会出现什麽问题？ 最小比值原则会失效！ 基变换 新的基变量——x2, x3,x4；新的非基变量x1, x5； 写出用非基变量表示基变量的表达式： 可得新的基本可行解 X（1）=（0,3,2,16,0）T ⑤写出用非基变量表示目标函数的表达式: 检验数仍有正的 第五步：上述过程何时停止？ 当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正（0时表无穷解，负时表唯一解）时，当前的基本可行解就是最优解! 为什麽？ 分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！

单纯形法的计算方法

第4章 单纯形法的计算方法 单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代, 直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z =n j j j=1c x ∑ 1,1,2,...,0,1,2,...n ij j i j j a x b i m x j n =?==???≥=?∑ 从Pj ( j = 1 , 2 , ? , n )中一般能直接观察到存在一个初始可行基 121(,,...,)n B P P P 0 0?? ?0 1 0 ?== ? ?0 0 1?? （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 j x 及ij a ( i = 1 , 2 , ? , m ; j = 1 , 2 , ? , n )进行编号, 则可得下列方 程组 11,1111 22,1122,1112.........,,...,0 m m n n m m n n m m m m nn n n n x a x a x b x a x a x b x a x a x b x x x +++++++++=?? +++=?? ??+++=??≥? 显然得到一个m ×m 单位矩阵

单纯形法

运筹学实验报告 题目：用单纯形法求解线性规划问题 姓名顾文远 学号2012436034 年级专业12数电类2班 指导教师苏珂 2013年11月14日

一．实验目的 (2) 二．实验环境 (3) 三．实验内容 (4) 1.线性问题 (4) 2.函数调用形式： (4) 3.参数介绍： (4) 5.实验原理及步骤： (5) 四．函数代码及注释： (12) 五．数据测试： (16) 六、实际问题求解 (19)

掌握两阶段法求线性规划问题的最优解，并完成 matlab求解单纯形算法求线性规划问题的最优可行解的程序。加深对单纯形算法的理解，掌握matlab 的使用技巧.

Matlab 7.1 系统：microsoft windows XP Professional CPU:Inter（R）Core（TM）2 Duo CPU E7500 @ 2.93GHz 3.24GB的内存

1.线性问题 用matlab程序两阶段法解下面形式的方程组的最优解： min f=c T*x s.t. A*x=b x>0 2.函数调用形式： [x,minf,flag,cpt]=dcxsf(A,b,c) 3.参数介绍： A为约束条件的系数矩阵。 b为约束条件的常数列向量。 c为目标函数的系数行向量。 4.函数输出介绍： X：为线性规划的解向量，当函数有可行解并且有最优值时输出最优解；当有可行解但无最优值或没有可行解时输出x[]。 minf：为目标函数的最优值，当函数有可行解并且有最优值时输出最优值； 当有可行解但没有最优值时minf=-inf，输出-1/0；当没有可行解 时输出minf=[]。 flag：为记录函数解的情况，当函数有可行解并且有最优值时，flag=1； 当函数有可行解但没有最优值时，flag=0；当函数没有可行解时， flag=-1. cpt：为单纯形表，当函数有可行解并且有最优值时输出最优解对应的单纯形

单纯形法

function [zyj,zyz,k]=ssssimplex(A,N) %A为初始单纯型表和书上的形式一样[m,n]=size(A); % 分别代表A的行数和列数%N为基本可行解的下标 k=0; %迭代次数%zyj为最优解 %zyz为最优值 flag=1; %定义一个逻辑变量 while flag k=k+1; if A(1,:)>=0 %已找到最优解 flag=0; zyj=zeros(1,n-1);%给每个变量赋初值0 for i=2:m zyj(N(i-1))=A(i,n);%给基变量赋新值 end zyz=-A(1,n);%给出最优解 else %判断问题是否不可解 for i=1:n-1 if A(1,i)<0&A(2:m,i)<=0 %问题不可解 disp('there is no answer'); flag=0; break; end end if flag %还不是最优表，进行转轴运算 temp=0; for i=1:n-1 if A(1,i)0 %为了求出相除以后最小的值 sita(i-1)=A(i,n)/A(i,inb); end end temp=inf; %定义一个无穷量inf for i=1:m-1 if sita(i)>0&sita(i)