2013-2014（1）专业课程实践论文题目：线性规划的大M法一、算法理论大M 法的求解线性规划的过程和单纯形法一样，不同的是对线性规划的一般形式的处理方式，大M 法将线性规划min ,..0Ax b f Cx s t x =⎧=⎨≥⎩转化为如下问题 min ,..,0T Ax y b f cx Me s t x y +=⎧=+⎨≥⎩ 步骤如下：（1） 首先将线性规划min ,..0Ax b f Cx s t x =⎧=⎨≥⎩转化成如下问题 min ,..,0T Ax y b f cx Me s t x y +=⎧=+⎨≥⎩； （2） 确定初始基变量矩阵B ；求解方程；（3） 令0N x =，计算B B f c x =；其中B c 和N x 分别代表基变量和非基变量的值，B c 表示基变量在目标函数中的系数；（4） 求解方程B B c ω=，对于所有非基变量计数判别数j j j z c p c ω-=-，其中j p 为非基变量在约束系数矩阵中相对应的列，令max()k k j j z c z c -=-，如果0k k z c -≤，则停止计算，输出最优解，否则转步骤5；（5） 求解方程k k By p =，若k y 的每个分量均大于0，则问题不存在最优解，否则转步骤6；（6） 令min |0s i sk sk ik b b y y y ⎛⎫=> ⎪⎝⎭，其中B b x =，用k p 代替Bs p ，得到新的基变量矩阵B 再转步骤3计算。
程序代码：%运用大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'];%计算此时的CjE=eye(m);A=[A,E];%初始单纯形表B=n+1:n+m;%B中存基变量的下标CB=c1;%CB存放基变量前的系数sigma=c';for i=1:msigma=sigma+M*A(i,:);%计算初始单纯形表中的检验数sigmaendD=find(sigma>0);le=length(D);%循环的判断条件当存在sigma<=0时循环终止while leMax=max(sigma);for i=1:n+m %寻找换入变量if Max==sigma(i)k=i; %k中用于存放换入变量的下标endendj=1;for i=1:m %寻找换出变量if A(i,k)>0theta(j)=b(i)/A(i,k); %计算theta的值j=j+1;else theta(j)=inf; %当A(i,k)<=0时theta取无穷大j=j+1;endendQ=min(theta);for i=1:mif theta(i)==Ql=i; %l中用于存放换出变量的下标endendB(l)=k; %更新基变量CB(l)=c(k); %更新基变量前的系数%更新单纯形表b(l)=b(l)/A(l,k);A(l,:)=A(l,:)/A(l,k);for i=1:mif i~=lb(i)=b(i)-b(l)*A(i,k);A(i,:)=A(i,:)-A(l,:)*A(i,k);endend%更新单纯形表完毕sigma=c';for i=1:mif c(B(i))~=0sigma=sigma-c(B(i))*A(i,:); %重新计算检验数sigma endendD=find(sigma>0); %判断sigma中是否有大于0的数le=length(D);if le %判断是否为无界解for i=1:n+mif sigma(i)>0 %对任一sigma>0有pj<=0则为无界解if A(:,i)<=0flag=0; %flag=0表示线性规划有无界解endendendendif flag==0 %如果flag=0则跳出循环break;endend %循环到此终止sigma1=sigma;for i=1:m %判断某非基变量检验数为0则有无穷多最优解sigma1(B(i))=1;endfor i=1:n+mif sigma1(i)==0flag=-1;endendfor i=n+1:n+m %判断线性规划是否无可行解for j=1:mif B(j)==i %检验基变量中是否有非0的人工变量flag=2;endendendif flag==2 %flag=2则表明线性规划无可行解disp('无可行解');z={};x={};endif flag==0 %flag=0则表明线性规划有无界解input('无界解');z={};x={};endif flag==-1 %flag=-1则表明线性规划有无穷多最优解disp('无穷多最优解');disp('一个最优解是'); %输出一个最优解z=CB*b;x=zeros(1,n);for i=1:mx(B(i))=b(i);endendif flag==1 %flag=1则表明线性规划有最优解disp('有唯一最优解');z=CB*b;x=zeros(1,n);for i=1:mx(B(i))=b(i);endend四、算法实现例1．用大M 法求解以下线性规划： 123123123123min 32..3236,24,,,0.z x x x s tx x x x x x x x x =-+++-=-+-=-≥解：例2．用大M 法求解以下线性规划： 123123123123max 2..26,44,,,0.z x x x s tx x x x x x x x x =+-++≤+-≤≥解：例3．用大M 法求解以下线性规划： 123123123123min 2..21,2,0,0,0.z x x x s tx x x x x x x x x =-+--+≥-++=≥≥≥解：例4．用大M 法求解以下线性规划：124123412341234max 2..6,2335,,,,0.z x x x s t x x x x x x x x x x x x =-++++≤-+-≥≥解：。
