数学建模算法及应用教学课件

第一章线性规划重要性：在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划。自从提出单纯性方法，利用该算法，可利用计算机的超级计算能力解决大型线性规划问题，我们的数学建模中有很多问题都是有关于线性规划或者可转化为线性规划的问题，所以学习线性规划问题的解决办法很有必要。1.1.1线性规划的实例与定义例1.1某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产1x台甲机床和2x乙机床时总利润z最大，则目标函数：12max43zxx约束条件：12122122108..7,0xxxxstxxx由于是在一组约束条件的限制下，求一线性目标函数最大或最小的问题，故称为线性规划问题。1.1.2线性规划问题的解的概念一般线性规划问题的（数学）标准型为:目标函数：1maxnjjjzcx约束条件：1,1,2,,,..0,1,2,,.nijjjjaxbimstxjn其中：0,1,2,,.ibim例：12min56zxx121221231028..4,0xxxxstxxx将该线性规划问题转化为标准型。可行解：满足约束条件的解12,,Txxx，称为线性规划问题的可行解，而使目标函数达到最大值的可行解为最优解。可行域：所有可行解构成的集合称为问题的可行域，记为R。1.1.3线性规划的Matlab标准形式及软甲求解Matlab中标准形式：minTcx..AxbstAeqxbeqlbxub其中：,,,,,cxbbeqlbub为列向量；c为价值向量（或决策向量）；b为资源向量；,AAeq为矩阵。注：目标函数始终取最小值。Matlab中求解线性规划的命令：[,](,,)[,](,,,,)[,](,,,,,,)xfvallinprogfAbxfvallinprogfAbAeqbeqxfvallinprogfAbAeqbeqlbub其中，x返回的是决策向量的取值；fval返回的是目标函数的最优值；f为价值向量；A和b对应的是线性不等式约束；Aeq和beq对应的是线性等式约束；lb和ub对应的是决策向量的下界向量和上界向量。例1.2求解下列线性规划问题123max235zxxx12312312312372510..312,,0xxxxxxstxxxxxx解：（1）化为Matlab标准型（2）求解的Matlab程序如下：（3）Lingo程序（略）例1.3求解下列线性规划问题123min23zxxx12312123428..326,,0xxxstxxxxx解：求解的Matlab程序如下：1.1.4可以转化为线性规划的问题例1.4数学规划问题：12min,nxxxs.t.Axb取,22iiiiiixxxxuv，则,iiiiiixuvxuv.记11,,,,,TTnnuuuvvv，则1min(),niiiuvs.t.(),,0.Auvuv进一步改写为：min1,,1,uvs.t.[,],,0.uAAbvuv例1.5求解下列数学规划问题：1234min234,zxxxxs.t.123412341234231123.2xxxxxxxxxxxx解：（1）转化为标准型（2）Matlab程序：例1.6