《636实验三十 用MATLAB求解线性规划问题》由会员分享，可在线阅读，更多相关《636实验三十 用MATLAB求解线性规划问题（27页珍藏版）》请在装配图网上搜索。
1、实验三十实验三十 用用MATLABMATLAB求解线性规划问求解线性规划问题题一、实验目的一、实验目的p了解了解MATLAB的优化工具箱，能利用的优化工具箱，能利用MATLAB求解线求解线性规划问题。性规划问题。 二、相关知识二、相关知识p线性规划是运筹学中研究得比较早，理论上已趋于线性规划是运筹学中研究得比较早，理论上已趋于成熟，在方法上非常有效，并且应用广泛的一个重成熟，在方法上非常有效，并且应用广泛的一个重要分支。要分支。p线性规划的数学模型有各种不同的形式，其一般形线性规划的数学模型有各种不同的形式，其一般形式可以写为：式可以写为：p目标函数为目标函数为 ，约束条件为：，约束条件为：
2、nnxfxfxfz2211minsnsnssnnbxaxaxabxaxaxa221111212111sntnttnndxcxcxcdxcxcxc2211112121110,21nxxx二、相关知识二、相关知识p这里这里 称为目标函数，称为目标函数， 称为称为价值系数，价值系数， 称为价值向量，称为价值向量， 为求为求解的变量，由系数解的变量，由系数 组成的矩阵组成的矩阵snsnssnnbxaxaxabxaxaxa221111212111sntnttnndxcxcxcdxcxcxc2211112121110,21nxxxnnxfxfxfz2211jfTnffff),(21jxijamnmnaaa
3、aA1111p这里这里 称为目标函数，称为目标函数， 称为称为价值系数，价值系数， 称为价值向量，称为价值向量， 为求为求解的变量，由系数解的变量，由系数 组成的矩阵组成的矩阵p称为不等式约束矩阵，由系数称为不等式约束矩阵，由系数 组成的矩阵组成的矩阵p称为等式约束矩阵，称为等式约束矩阵，nnxfxfxfz2211jfTnffff),(21jxijamnmnaaaaA1111ijcsnsnccccC1111p列向量列向量 和和 为右端向为右端向量，条件量，条件 称为非负约束。称为非负约束。p一个满足约束条件的向量一个满足约束条件的向量 ，称为可，称为可行解或可行点，所有可行点的集合称为可行区域
4、，行解或可行点，所有可行点的集合称为可行区域，达到目标函数值最大的可行解称为该线性规划的最达到目标函数值最大的可行解称为该线性规划的最称为不等式约束矩阵，由系数称为不等式约束矩阵，由系数 组成的矩阵组成的矩阵p称为等式约束矩阵，称为等式约束矩阵，ijcsnsnccccC1111Tnbbbb),(21Tndddd),(210jxTnxxxx),(21p列向量列向量 和和 为右端向为右端向量，条件量，条件 称为非负约束。称为非负约束。p一个满足约束条件的向量一个满足约束条件的向量 ，称为可，称为可行解或可行点，所有可行点的集合称为可行区域，行解或可行点，所有可行点的集合称为可行区域，达到目标函数值
5、最大的可行解称为该线性规划的最达到目标函数值最大的可行解称为该线性规划的最优解，相应的目标函数值称为最优目标函数值，简优解，相应的目标函数值称为最优目标函数值，简称最优值。称最优值。p求解线性规划问题已有一些成熟的方法，我们这里求解线性规划问题已有一些成熟的方法，我们这里介绍利用介绍利用MATLAB来求解线性规划问题的求解。来求解线性规划问题的求解。 Tnbbbb),(21Tndddd),(210jxTnxxxx),(21p求解线性规划问题已有一些成熟的方法，我们这里求解线性规划问题已有一些成熟的方法，我们这里介绍利用介绍利用MATLAB来求解线性规划问题的求解。来求解线性规划问题的求解。p在
6、在MATLAB中有一个专门的函数中有一个专门的函数linprog()来解决这来解决这类问题，我们知道，极值有最大和最小两种，但求类问题，我们知道，极值有最大和最小两种，但求优解，相应的目标函数值称为最优目标函数值，简优解，相应的目标函数值称为最优目标函数值，简称最优值。称最优值。p求解线性规划问题已有一些成熟的方法，我们这里求解线性规划问题已有一些成熟的方法，我们这里介绍利用介绍利用MATLAB来求解线性规划问题的求解。来求解线性规划问题的求解。 p求解线性规划问题已有一些成熟的方法，我们这里求解线性规划问题已有一些成熟的方法，我们这里介绍利用介绍利用MATLAB来求解线性规划问题的求解。来求
7、解线性规划问题的求解。p在在MATLAB中有一个专门的函数中有一个专门的函数linprog()来解决这来解决这类问题，我们知道，极值有最大和最小两种，但求类问题，我们知道，极值有最大和最小两种，但求的极大就是求的极小，因此在的极大就是求的极小，因此在MATLAB中以求极小中以求极小为标准形式，函数为标准形式，函数linprog()的具体格式如下：的具体格式如下：pX=linprog(f,A,b)pX,fval,exitflag,ouyput,lamnda=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options) p这里这里X是问题的解向量，是问题的解向量，pf是由目标函数
8、的系数构成的向量，是由目标函数的系数构成的向量，pA是一个矩阵，是一个矩阵，b是一个向量，是一个向量，A，b和变量和变量x=x1,x2,xn一起，表示了线性规划中不等式约一起，表示了线性规划中不等式约束条件，束条件，A，b是系数矩阵和右端向量。是系数矩阵和右端向量。 的极大就是求的极小，因此在的极大就是求的极小，因此在MATLAB中以求极小中以求极小为标准形式，函数为标准形式，函数linprog()的具体格式如下：的具体格式如下：pX=linprog(f,A,b)pX,fval,exitflag,ouyput,lamnda=linprog(f,A,b,Aeq,Beq,LB,UB,X0,opti
9、ons) p这里这里X是问题的解向量，是问题的解向量，pf是由目标函数的系数构成的向量，是由目标函数的系数构成的向量，pA是一个矩阵，是一个矩阵，b是一个向量，是一个向量，A，b和变量和变量x=x1,x2,xn一起，表示了线性规划中不等式约一起，表示了线性规划中不等式约束条件，束条件，A，b是系数矩阵和右端向量。是系数矩阵和右端向量。pAeq和和Beq表示了线性规划中等式约束条件中的系表示了线性规划中等式约束条件中的系数矩阵和右端向量。数矩阵和右端向量。LB和和UB是约束变量的下界和是约束变量的下界和上界向量，上界向量，X0是给定的变量的初始值，是给定的变量的初始值，poptions为控制规划
10、过程的参数系列。返回值中为控制规划过程的参数系列。返回值中fval是优化结束后得到的目标函数值。是优化结束后得到的目标函数值。pexitflag=0表示优化结果已经超过了函数的估计值表示优化结果已经超过了函数的估计值或者已声明的最大迭代次数；或者已声明的最大迭代次数；pexitflag0表示优化过程中变量收敛于解表示优化过程中变量收敛于解X，exitflag0表示优化过程中变量收敛于解表示优化过程中变量收敛于解X，exitflag Optimization terminated successfully.pX =40.0000p 10.0000pfval = -3.8000e+005p接着写出
11、接着写出MATLAB程序如下：程序如下：pclearpf=-7000,10000;pA=8,6;4,8;4,6;pb=380,300,220;pX,fval=linprog(f,A,b) p运行结果为：运行结果为：p Optimization terminated successfully.pX =40.0000p 10.0000pfval = -3.8000e+005 p例例2：求解下面的线性规划问题：求解下面的线性规划问题：p 123min 546 xxx123123121232032442s.t.32300, 0, 0 xxxxxxxxxxxp解决上述问题的解决上述问题的MATLAB程序
12、为：程序为：pclearpf=-5,4,6;pA=1,-2,1;3,2,4;3,2,0;pb=20,42,30;pLB=0;0;0;pX,fval,exitflag,output,lambda=linprog(f,A,b,LB) p程序运行的结果为：程序运行的结果为：pOptimization terminated successfully.pX = 0.0000p 15.0000p 3.0000pfval = -78.0000pexitflag = 1poutput = iterations: 6p cgiterations: 0p algorithm: lipsolplambda = in
13、eqlin: 3x1 doublep eqlin: 0 x1 doublep upper: 3x1 doublep lower: 3x1 doublep在使用在使用linprog()命令时，系统默认它的参数至少为命令时，系统默认它的参数至少为3个，但如果我们需要给定第个，但如果我们需要给定第5个参数，则第个参数，则第4个参个参数也必须给出，否则系统无法认定给出的是第数也必须给出，否则系统无法认定给出的是第5个个参数。遇到无法给出时，则用空矩阵参数。遇到无法给出时，则用空矩阵“”替代。替代。 三、实验内容三、实验内容p1求解线性规划问题1234min( )3285f xxxxx123412341
14、234138236523s.t. 733100 xxxxxxxxxxxxxx p2求解线性规划问题求解线性规划问题p3某快餐店一周中每天需要不同数目的雇员，设某快餐店一周中每天需要不同数目的雇员，设周一至少周一至少 人，周二至少人，周二至少 人，周三至少人，周三至少 人，周人，周四至少四至少 人，周五至少人，周五至少 人，周六至少人，周六至少 人，周日人，周日至少至少 人，又规定雇员需连续工作人，又规定雇员需连续工作5天，每人每天天，每人每天的工资为的工资为 元。问快餐店怎样聘用雇员才能满足需元。问快餐店怎样聘用雇员才能满足需求，又能使总聘用费用最少？求，又能使总聘用费用最少？ 12345mi
15、n( )f xxxxxx 3512524569422s.t.2290 (1,2,3,4,5)ixxxxxxxxxi1a2a3a4a5a6a7aCp提示：由于每个雇员需连续工作提示：由于每个雇员需连续工作5天，故快餐店聘天，故快餐店聘用的总人数不一定是每天聘用人数之和。我们定义用的总人数不一定是每天聘用人数之和。我们定义周一开始工作的雇员数为周一开始工作的雇员数为 ，周日开始工作的雇员，周日开始工作的雇员数为数为 ，则一周的聘用总费用为：，则一周的聘用总费用为：p由于除了周二和周三开始工作的雇员之外，其余的由于除了周二和周三开始工作的雇员之外，其余的雇员都会在周一工作，所以周一至少应有雇员都会在周一工作，所以周一至少应有 人的约人的约束应表示为：束应表示为：p p类似地可以得出其它的约束条件。类似地可以得出其它的约束条件。1x7x)(7654321xxxxxxxCz1a176541axxxxxp现给定现给定 元，元， 人，人， 人，人， 人，人， 人，人， 人，人， 人，人， 人，请给人，请给出问题的数学模型，并用出问题的数学模型，并用MATLAB来求解。来求解。p4完成实验报告。完成实验报告。p 100C161a152a163a194a145a126a187a
636实验三十 用MATLAB求解线性规划问题
