数学软件与实验.docx

此文档收集于网络，如有侵权，请联系网站删除数学软件与实验专业：信息与计算科学姓名学号：赵志高2011114085姓名学号：朱营锋2011114089单纯形法求解线性规划问题1.数学方法：单纯形法：单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。演示单纯形法的过程如下：例：解最优化问题：列单纯形表（即矩阵）：b21101212019c11000然后从c所在行的正数中最大的一个所对应的变量作为基变量，因为这里两者一样，不妨选为。由于拿所在列的正系数去除b所在列的数的结果为，故取离开基变量。然后对该矩阵进行行变换，使所在列变成单位向量：b11/21/20603/2-1/213c01/2-1/20-6接下来令c所在行的其余的正数中最大的一个所在列的变量进入基变量，并且根据，令离开基变量。继续进行行变换，得到b102/3-1/3501-1/32/32c00-1/3-1/3-7由于c所在行的所有数都非正，问题结束。最优解为，最优值为。2.基本数学原理：线性规划问题的标准形式是：线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量b非负。不符合这些条件的线性模型首先要转换成标准形式。Matlab采用投影法求解线性规划问题，该方法是单纯形法的变种。有关函数的介绍在Matlab工具箱中可以用linprog函数求解线性规划问题。Linprog函数的调用格式如下。其中，f, x, b, beq, lb, ub为向量, A, Aeq为矩阵。x = linprog(f,A,b)功能：求解最小化问题 min f*x 条件 A*x b。x = linprog(f,A,b,Aeq,beq)功能：求解最小化问题 min f*x 条件 A*x b Aeq*x = beq，如果没有不等式就设置A = 和b = ；没有等式就设置Aeq=,beq=x = linprog(f,A,b,Aeq,beq,lb,ub)功能：求解最小化问题 min f*x 条件 A*x b Aeq*x = beqlb x ub，决策变量有上下限时，如果没有不等式就设置A = 和b = ；没有等式就设置Aeq=,beq=x = linprog(f,A,b,Aeq,beq,lb,ub,x0)功能：求解最小化问题 min f*x 条件 A*x b Aeq*x = beqlb x ub，如果没有不等式就设置A = 和b = 。设置初始点x0，这个选择项只是对medium-scale算法有效。默认的large-scale算法和简单的算法忽略任何初始点。x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)功能：最小化带有参数项的线性规划问题。其中options可以使用optimset来设置。x = linprog(problem)功能：对problem求最小值，其中problem是一个结构体。通过优化工具箱来创建，导入到MATLAB工作空间。x,fval = linprog(.)功能：返回目标函数最优解x，和在x处的值：fval = f*x.x,fval,exitflag = linprog(.)功能：返回目标函数最优解x，和在x处的值：fval = f*x，是否存在exitflag标志x,fval,exitflag,output = linprog(.) Matlab中文论坛功能：返回目标函数最优解x，和在x处的值：fval = f*x，是否存在exitflag标志，优化解结构体outputx,fval,exitflag,output,lambda = linprog(.)功能：返回目标函数最优解x，和在x处的值：fval = f*x，是否存在exitflag标志，优化解结构体output，拉格朗日乘子结构体lambda应用实例某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低解：设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：编写M文件如下:clear f = 13 9 10 11 12 8;A = 0.4 1.1 1 0 0 0 0 0 0 0.5 1.2 1.3;b = 800; 900;Aeq=1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1;beq=400 600 500;vlb = zeros(6,1);vub=;x,fval = linprog(f,A,b,Aeq,beq,vlb,vub)运行结果如下Optimization terminated.x = 0.0000 600.0000