2.3　单纯形法的Matlab程序及实例

应用单纯形法手工求解线性规划问题不但计算量大，且易出错，不适于较多变量的求解，应用计算机进行求解则方便快捷。Matlab提供了求解线性规划问题的函数linprog（），下面根据单纯形法的计算步骤，给出适于学习用的单纯形法程序。

程序清单如下：

function[x，fmax]=linear_pro_max（cf，cb，A，b，indexb1）

n=length（cf）；

max_sigma=1；

m=length（cb）；

indexb=indexb1；

theta=zeros（size（m，1））；

while max_sigma>0

forj=1：n

sigma（j）=cf（j）-sum（cb（：）.*A（：，j））；

end

max_sigma=max（sigma）；

if（max_sigma>0）

pvj=find（sigma==max_sigma）；

theta=b./A（：，pvj）；

min_theta=min（theta）；

max_sigma

min_theta

pvi=find（theta==min_theta）；

cb（pvi）=cf（pvj）；

indexb（pvi）=pvj；

pvi

pvj

cb

cf

for i=1：m

if（i～=pvi）

forj=1：n

AA（i，j）=A（i，j）-A（i，pvj）*A（pvi，j）/A（pvi，pvj）；

end

bb（i）=b（i）-A（i，pvj）*b（pvi）/A（pvi，pvj）；

else

AA（i，：）=A（i，：）/A（pvi，pvj）；

bb（i）=b（i）/A（pvi，pvj）；

end

end

end

A=AA；b=bb'；

end

s=1：n；

x=zeros（n，1）；

for i=1：m

k=find（s==indexb（i））；

if（k～=0）

x（k）=b（i）；

end

end

fmax=cf*x；

【例2-3】　用单纯形法Matlab程序求解【例1-1】。

解：为方便起见，重新列出所给问题线性规划的标准形：

maxf（x）=220x1+250x2+0x3+0x4+0x5+0x6

s.t.x1+x2+x3=1200

2x1+x2+x4=1800

x1+x5=800

x2+x6=1000

xj≥0，j=1，2，…，6

编写用户程序。cf为目标函数中变量系数行向量；cb为初选基变量行向量；indexb1为初始基变量下标索引；A为等式约束方程系数矩阵；b为等式约束方程右端项。应户程序为：

function linear_pro_max_test1

clc

clear all；

cf=[220 250 0 0 0 0]；

cb=[cf（3），cf（4），cf（5），cf（6）]；

indexb1=[3456]；

A=[1 1 1 0 0 0

　2 1 0 1 0 0

　1 0 0 0 1 0

　0 1 0 0 0 1]；

b=[1200；1800；800；1000]；

[x，fmax]=linear_pro_max（cf，cb，A，b，indexb1）

计算结果为：

x=[200 1000]。

习题

1.某工厂需要A、B、C三种规格的钢板，现有两种尺寸不同的钢板原材，每张钢板可同时截得三种规格的小钢板的块数如下表所示：

现需要A、B、C三种规格的成品分别为15、18、27块，问最多需要两种钢板各多少张可得所需三种规格的成品？

2.求解线性规划问题。

minz=6x1+4x2

s.t.2x1+x2≥1

3x1+4x2≥1.5

x1，x2≥0

3.用Matlab程序求解下列线性规划问题。

minz=2x1+3x2+x3

s.t.x1+4x2+2x3≥8

3x1+2x2≥6

x1，x2，x3≥0