2实验1 单纯形法求解线性规划Word文档下载推荐.docx

2实验1 单纯形法求解线性规划Word文档下载推荐.docx

《2实验1 单纯形法求解线性规划Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《2实验1 单纯形法求解线性规划Word文档下载推荐.docx（13页珍藏版）》请在冰点文库上搜索。

（1）实验原理

（a）当所有sgma<

=0,并且基变量中没有人工变量，非基变量的sgnm均不为0，此时方程对应的唯一解

（b）当所有的sgma<

=0,并且基变量中没有人工变量，非基变量中有sgma=0的，此时方程对应的无穷多解

（c）当所有的sgma<

=0,并且基变量中有人工变量，此时方程对应的是无可行解情况

（d）存在一个变量的sgma>

0,并且p<

0,则此时对应方程为无界解

（二）编写程序代码

function[xx,b,fm,sgma,AA,flg]=myprgmh（m1,m,n,A,b,c）

%单纯形法求解性规划函数。

默认标准型人工变量在最前、剩余变量在后构成基本量;

%m1人工变量的个数；

m基变量的个数；

n所有变量的个数;

%A约束方程的系数矩阵;

%b约束方程右端列向量;

输出b基变量的值;

%c目标函数的系数。

cb基变量的系数

%输出xx为基变量的下标;

%fm输出目标函数的值;

%flg表示解得四种情况;

B0=A（:

1:

m）;

%B0初始可行基矩阵（单位矩阵）;

cb=c（:

xx=1:

m;

%xx变量的下标;

sgma=c-（cb*B0）*A;

%sgma检验数;

h=-1;

sta=ones（m,1）;

fori=1:

n

ifsgma（i）>

h=1;

end

end

vv=0;

whileh>

[msg,mk]=max（sgma）;

fori=1:

m

ifA（i,mk）>

sta（i）=b（i）/A（i,mk）;

else

sta（i）=10000;

[mst,mr]=min（sta）;

ifmst==10000

flg='

unboundedsolution'

;

fm=inf;

xx=[];

b=[];

h=-1;

vv=1;

AA=[];

zy=A（mr,mk）

m

ifi==mr

forj=1:

A（i,j）=A（i,j）/zy;

b（i）=b（i）/zy;

ifi~=mr

amk=A（i,mk）;

b（i）=b（i）-amk*b（mr）;

A（i,j）=A（i,j）-amk*A（mr,j）;

end

A;

B1=A（:

%B1新基的逆矩阵;

cb（mr）=c（mk）;

xx（mr）=mk;

sgma=c-cb*A;

cb

b

fm=sum（cb*b）;

if（h==-1）&

（vv~=1）

ifxx（i）<

=m1

vv=vv+2;

ifvv>

=2;

nofeasibel'

fm=[];

ifvv~=1

AA=A;

ss=size（find（sgma））

ww=ss

（2）

ifww==n-m

Thereisonlyonesolution'

Therearemanysolutions'

（1）

>

m1=0

m1=

0

m=3

m=

3

n=5

n=

5

A=[10012;

01040;

00104]

A=

10012

01040

00104

b=[8;

16;

12]

b=

8

16

12

c=[00023]

c=

00023

[xx,b,fm,sgma,AA,flg]=myprgmh（m1,m,n,A,b,c）

zy=

4

cb=

003

2

1

203

ss=

12

ww=

xx=

435

fm=

14

sgma=

-1.5000-0.1250000

AA=

00.250001.00000

-2.00000.50001.000000

0.5000-0.1250001.0000

flg=

Thereisonlyonesolution有唯一解

m=2

n=4

A=[10-11;

01-0.51]

1.00000-1.00001.0000

01.0000-0.50001.0000

b=[1;

2]

c=[0022]

0022

[]

Inf

unboundedsolution无界解

m1=2

n=6

6

A=[101-1-10;

01-310-1]

101-1-10

01-310-1

b=[0;

3]

c=[-1000-10001100]

-1000-10001100

-10001

0-1-19960-1000-999

nofeasibel无可行解

A=[10-113;

0112410]

10-113

0112410

b=[20;

90]

b=20

90

c=[00-5513]

00-5513

130

6.6667

23.3333

0.3333

50

20.0000

10.0000

42

100.0000

-5000-2

1.00000-1.00001.00003.0000

-4.00001.000016.00000-2.0000

Therearemanysolutions有无穷解