用单纯形法求解线性规划问题

目录一．摘要…………………………………………………………2二．实验目的……………………………………………………2三．实验内容……………………………………………………2四．建立数学模型………………………………………………3五．实验原理……………………………………………………5六．MALTAB程序代码及注释……………………………………7七．结果运行测试…………………………………………………13八．心得与感悟…………………………………………………152一．摘要：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。自1946年G.B.Dantizig提出单纯形法以来，它一直是求解线性规划问题的最有效的数学方法之一。单纯形法的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。关键字：线性规划，单纯形法，最优值，最优解二．实验目的：1.加强学生分析问题能力，锻炼数学建模能力。2.了解并掌握MATLAB软件中的线性规划问题的编程、求解和分析。3.利用所学的MALTAB语言，完成对单纯形法问题的编程设计。三．实验内容：某商场决定，营业员每周连续工作5天后连续休息2天，轮流休息，据统计，商场每天需要营业员如下：星期一：300，二：300；三：350，四：400，五：480，六：600；日：500；（1）商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最少（2）若商场可以雇佣临时工，上班时间同正式工，若正式工每天工资80，临时工每天100，问商场是否应雇佣临时工及雇佣多少名？3四．建立数学模型：从实际问题中建立数学模型一般有以下三个步骤：1.根据影响所要达到目的的因素找到决策变量；2.由决策变量和所在达到目的之间的函数关系确定目标函数；3.由决策变量所受的限制条件确定决策变量所要满足的约束条件。当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。线性规划问题的标准形式：由题可知，可设每天上班人数分别应为x1,x2,x3,x4,x5,x6,x7;建立下列数学模型4将其转化为标准形式为：即价值向量约束矩阵右端向量5五．实验原理：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。6流程图如下：対原问题增加m个人工变量构造辅助问题判断辅助问题最优值g=0无解，停止人工变量xj是否为非基变量把人工变量对应的列从单纯形表中去掉进行换基迭代得到新矩阵BB中是否有人工变量得到初始可行基B求对应典式和检验数ξ判断ξk≤0得到最优解进行换基迭代得到新基判断Ak≤0问题无界否是否否是是否是7六．MALTAB程序代码及注释：function[x,minf,flag,cpt]=dcxsf(A,b,c)formatrat%使数据可以以分数形式输出c=-c;%将目标函数系数向量加负号得到单纯形表第0行[m,n]=size(A);%求约束矩阵的行数和列数m1=m;%保存下原来的行数s=eye(m);%生成秩为m的单位矩阵A=[As];%将s矩阵添加到A矩阵右侧A=[Ab];%将b向量添加到A矩阵右侧g1=zeros(1,n);%生成一个1行n列的零矩阵g1x=ones(1,m);%生成一个1行m列元素全为1的矩阵g1=[g1-x];%将g1和-x合并，产生一个新的前n列为0后m列为-1的单行矩阵g=[0];%初始化一个单元素零矩阵g1=[g1g];%将单元素零矩阵添加到g1右侧，生成人工向量的检验向量g1s1=n+m+1;%记录目前列数之和s2=zeros(1,m+1);%生成1行m+1列的零矩阵s2c=[cs2];%将s2添加到c右侧A1=zeros(m,1);%生成一个m行1列的零矩阵A1fori1=1:mA1(i1,1)=i1+n;%基变量的数值存储区endfori=1:mg1(1,:)=g1(1,:)+A(i,:);enddecide=find(g1(1,1:m+n)0);%寻找g1中大于零的数值列数存于decide8数组中while~isempty(decide)%当decide不为空i=decide(1);%将列数赋给itext=find(A(1:m,i)0);%text存放该列中所有数值大于零的行数ifisempty(text)%如果text为空则无解flag=0;break;endmin=inf;%min初始化为无穷大fori1=1:m%当该列存在大于零的数值时ifA(i1,i)0&A(i1,s1)/A(i1,i)min%寻找比值最小的min=A(i1,s1)/A(i1,i);x1=i1;%将比值最小的行数赋给x1endendA(x1,:)=A(x1,:)/A(x1,i);%进行单位化c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:));g1(1,:)=g1(1,:)+(-1*g1(1,i)*A(x1,:));fori1=1:mifi1~=x1A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:));%进行换机迭代endendA1(x1,1)=i;%将列数既对应的非基变量转换为基变量decide=find(g1(1,[1:m+n])0);%再进行查找endifg1(1,s1)0%无解情况flag=-1;endifg1(1,s1)==0%置空矩阵9g1(1,:)=[];fori6=1:mA(:,n+1)=[];endfori6=1:mc(n+1)=[];enddecide=find(A1(1:m,1)n);%查找是否有人工变量if~isempty(decide)while~isempty(decide)x1=decide(1);%存放的是人工变量的行数text=find(A(x1,1:n)~=0);%该行的所有元素都不为零的列坐标ifisempty(text)%如果text为空decide(1)=[];A1(x1,:)=[];A(x1,:)=[];m=m-1;elsei=text(1);%i保存列数A(x1,:)=A(x1,:)/A(x1,i);%进行单位化A1(x1,1)=i;c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:));fori1=1:mifi1~=x1A(i1,:)=A(i1,:)+(-1*A(i1,i)*A(x1,:));%进行换基迭代endenddecide(1)=[];%赋值为空text(1)=[];endendend10decide=find(c(1,1:n)0);%decide存放c中该行中所有数值大于零的列数while~isempty(decide)i=decide(1);%将列数赋给itext=find(A(:,i)0);%保存大于零的项的行数ifisempty(text)%为空的时候，则无解flag=0;%有可行解但无最优值，flag记为0c=[c;A];%将c添加到A矩阵上方的到对应解的单纯形表cpt=c;x=zeros(n,1);foro=1:nforo1=1:mifo==A1(o1,1)x(o,1)=A(o1,n+1);endendenddisp('该问题有可行解但没有最优解!')minf=-inf;%无最优值，将minf赋值为无穷小x=[];%解向量为空return;endmin=inf;%min初始化为无穷大fori1=1:mifA(i1,i)0&A(i1,n+1)/A(i1,i)min%寻找比值最小的min=A(i1,n+1)/A(i1,i);%更新最小值minx1=i1;%保存最小项的行数赋给x1endend11A(x1,:)=A(x1,:)/A(x1,i);%单位化j=c(1,i);forj1=1:n+1c(1,j1)=c(1,j1)+A(x1,j1)*(-1)*j;%换基迭代endfori1=1:mifi1~=x1A(i1,:)=A(i1,:)+(-1*A(x1,:)*A(i1,i));endendA1(x1,1)=i;%将列数既对应的非基变量转换为基变量decide=find(c(1,1:n)0);%再进行查找endc=[c;A];%得到对应解的单纯形表cpt=c;x=zeros(n,1);foro=1:nforo1=1:mifo==A1(o1,1)x(o,1)=A(o1,n+1);endendendminf=c(1,n+1);%得到最优值flag=1;%有最优值记录flag为1endifflag==0%有可行解但没有最优值情况disp('该问题有可行解但没有最优解!')x=[];%赋值为空minf=-inf;%最优值输出为无穷小end12ifflag==1%有可行解有最优值情况disp('该问题存在最优解!')x=x;minf=minf;end;ifflag==-1%没有可行解情况disp('该问题没有可行解!')x=[];%赋值为空cpt=[];minf=[];endend13七．结果运行测试：输入测试数据：A=[1111100-1000000;01111100-100000;001111100-10000;1001111000-1000;11001110000-100;111001100000-10;1111001000000-1];b=[300300350400480600550]';c=[11111110000000];[x,minf,flag,cpt]=dcxsf(A,b,c)运行结果为：该问题存在最优解!x=170290/312050/30200/3440/3310/3000000minf=1850/3flag=1cpt=Columns1through6140000-1/301000-100010-1000002/3000002/3101002/300000-5/3000012/30Columns7through1200-1/30-1/300001-11000001102/3-12/3-100-1/30-1/3000-1/302/3-101-2/31-2/3100-1/30-1/30Columns13through15-1/3-1/31850/3-10170-101202/3-1/3440/3-1/32/3200/32/3-1/3290/3-2/3-2/3310/32/3-1/350/3解得最优解为(1709712017067146)最优值为61715八．心得与感悟：通过本学期学习MALTAB软件