09-2线性规划的大M法

题目：线性规划的大M法

一、算法理论

大M法的求解线性规划的过程和单纯形法一样，不同的是对线性规划的一般形式的处理方式，大M法将线性规划

AxbminfCx,s..t转化为如下问题

x0AxybminfcxMeT,s..t

x,y0步骤如下：

Axbt（1） 首先将线性规划minfCx,s..转化成如下问题 x0AxybminfcxMeT,s..t；

x,y0（2） 确定初始基变量矩阵B；求解方程；

（3） 令xN0，计算fcBxB；其中cB和xN分别代表基变量和非基

变量的值，cB表示基变量在目标函数中的系数；

（4） 求解方程BcB，对于所有非基变量计数判别数

zjcjpj，其中cpj为非基变量在约束系数矩阵中相对应

的列，令zkckmax(zjcj)，如果zkck0，则停止计算，输出最优解，否则转步骤5；

（5） 求解方程Bykpk，若yk的每个分量均大于0，则问题不存在

最优解，否则转步骤6；

bibs（6） 令min|ysk0，其中bxB，用pk代替pBs，得到新的

yskyik基变量矩阵B再转步骤3计算。

二、算法框图

开始 输入初始矩 阵B。 令xN0，计算 fcBxB 求解BcB zc0 解Bykpk bb smini|ysk0pk代y skyik， yk0 p。 替Bs 输出“该问题不 存在最优解”。 kk输出最优解 结束 三、算法程序

程序代码：

%运用大M法计算线性规划的最大值，计算之前先化成标准型，其中z中存放线性规划的最大值

%x中用于存放解，c为价值列向量，b为资源列向量 function [z,x]=DM2(A,c,b)

M=10000;k=1;flag=1;%设M为1000000,flag用于表示解的类型 [m,n]=size(A);%计算系数矩阵的行数和列数 c1=-M*ones(1,m);

c=[c;c1'];%计算此时的Cj E=eye(m);

A=[A,E];%初始单纯形表

B=n+1:n+m;%B中存基变量的下标 CB=c1;%CB存放基变量前的系数 sigma=c'; for i=1:m

sigma=sigma+M*A(i,:);%计算初始单纯形表中的检验数sigma end

D=find(sigma>0);

le=length(D);%循环的判断条件当存在sigma<=0时循环终止 while le

Max=max(sigma);

for i=1:n+m %寻找换入变量 if Max==sigma(i)

k=i; %k中用于存放换入变量的下标 end end j=1;

for i=1:m %寻找换出变量 if A(i,k)>0

theta(j)=b(i)/A(i,k); %计算theta的值 j=j+1;

else theta(j)=inf; %当A(i,k)<=0时theta取无穷大 j=j+1; end end

Q=min(theta); for i=1:m

if theta(i)==Q

l=i; %l中用于存放换出变量的下标 end end

B(l)=k; %更新基变量

CB(l)=c(k); %更新基变量前的系数 %更新单纯形表 b(l)=b(l)/A(l,k); A(l,:)=A(l,:)/A(l,k); for i=1:m if i~=l

b(i)=b(i)-b(l)*A(i,k);

A(i,:)=A(i,:)-A(l,:)*A(i,k); end end

%更新单纯形表完毕 sigma=c'; for i=1:m

if c(B(i))~=0

sigma=sigma-c(B(i))*A(i,:); %重新计算检验数sigma end end

D=find(sigma>0); %判断sigma中是否有大于0的数 le=length(D);

if le %判断是否为无界解 for i=1:n+m

if sigma(i)>0 %对任一sigma>0有pj<=0则为无界解 if A(:,i)<=0

flag=0; %flag=0表示线性规划有无界解 end end end end

if flag==0 %如果flag=0则跳出循环 break; end

end %循环到此终止

sigma1=sigma;

for i=1:m %判断某非基变量检验数为0则有无穷多最优解 sigma1(B(i))=1; end

for i=1:n+m

if sigma1(i)==0 flag=-1; end end

for i=n+1:n+m %判断线性规划是否无可行解 for j=1:m

if B(j)==i %检验基变量中是否有非0的人工变量 flag=2; end end end

if flag==2 %flag=2则表明线性规划无可行解 disp('无可行解'); z={};x={}; end

if flag==0 %flag=0则表明线性规划有无界解 input('无界解'); z={};x={}; end

if flag==-1 %flag=-1则表明线性规划有无穷多最优解 disp('无穷多最优解');

disp('一个最优解是'); %输出一个最优解 z=CB*b; x=zeros(1,n); for i=1:m

x(B(i))=b(i); end end

if flag==1 %flag=1则表明线性规划有最优解 disp('有唯一最优解'); z=CB*b; x=zeros(1,n);

for i=1:m

x(B(i))=b(i); end end

四、算法实现

例1．用大M法求解以下线性规划：

minz3x12x2x3s..t3x12x23x36,x12x2x34,x1,x2,x30.解：

例2．用大M法求解以下线性规划：

maxzx12x2x3s..tx1x22x36,x14x2x34,x1,x2,x30.解：

例3．用大M法求解以下线性规划：

minzx12x2x3s..tx12x2x31,x1x2x32,x10,x20,x30.解：

例4．用大M法求解以下线性规划：

maxzx12x2x4s..tx1x2x3x46,2x1x23x33x45,x1,x2,x3,x40.解：