线性规划与最优化模型经典讲义ppt课件.ppt

《线性规划与最优化模型经典讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划与最优化模型营养配餐数学建模讲座数学建模之营养配餐问题1问题的提出每种蔬菜含有的营养素成份是不同的，从医学上知道每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表1中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少kg？一营养配餐问题数学建模之营养配餐问题表1序号蔬菜每份所含营养素单位数每千克费用铁磷维生素A维生素C烟酸1青豆0.451041580

2、.3052胡萝卜0.4528906530.3553菜花1.05592550530.6084白菜0.402575270.1525甜菜0.50221550.2566土豆0.507523580.803要求蔬菜提供的营养6.0025175002455.00数学建模之营养配餐问题2问题分析与模型建立铁的需求量至少6个单位数：磷的需求量至少25个单位数：维生素A的需求量至少17500个单位数：设分别表示在下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量(kg)，则费用的目标函数为:约束条件：数学建模之营养配餐问题设问题是在满足营养素要求的条件下，所需的费用最小烟酸的需求量至少5个单位

3、数：每周需供应140kg蔬菜，即维生素C的需求量至少245个单位数：数学建模之营养配餐问题易见，该问题是一个线性规划模型：数学建模之营养配餐问题人们在日常生活中,经常会遇到在有限的资源情况下,如何合理安排,使之产值或利润最大,或在任务给定后,如何统筹安排,使之以最小成本或最小代价完成任务等决策问题.规划论就是解决这类问题的重要数学方法.首先我们要给大家介绍一些有关线性规划的基本知识.3补充基本知识----线性规划数学建模之营养配餐问题线性规划一、线性规划概念定义1：规划的数学模型中如果满足：（1）目标函数是决策变量的线性函数；（2）约束条件都是决策变量的线性等式或不等式，则称该规划

4、为线性规划.1．线性规划的一般形式目标函数：数学建模之营养配餐问题约束条件：可以缩写为数学建模之营养配餐问题2．线性规划标准形式从线性规划数学模型的一般形式可以看出，目标函数可以是实现最大化，也可以实现最小化，约束条件可以是不等式，也可以是等式，这种模型形式上的多样性势必给求解带来不便，为了便于讨论线性规划的求解方法，我们给出规划问题的标准形式.数学建模之营养配餐问题目标函数约束条件可以缩写为数学建模之营养配餐问题标准形式的矩阵形式为数学建模之营养配餐问题我们知道，由于一般形式中有多个不等式，所以求解过程很困难，但标准形式求解起来就比较容易，那么，如何将线性规划的一般形式转化为标准

5、形式呢？3．化一般形式为标准形式（1）目标函数如果目标函数是最大化类型，将其转化为最小化类型非常简单，只需令S’=-S,即（2）约束不等式化为约束等式数学建模之营养配餐问题将约束不等式化为约束等式需要我们把不等式中引入新的非负变量（我们称之为松弛变量或剩余变量），来平衡不等式的两端使之成为等式.数学建模之营养配餐问题所以约束条件中有多少个不等式，就要引入多少个新的非负变量，使不等式条件转化为等式.总结：数学建模之营养配餐问题（3）标准形式中的变量要求都是非负的，如果一般形式中某个变量没有符号限制，可以为正也可以为负，如果使其保持非负？数学建模之营养配餐问题（4）对约束条件右端bi为

6、负时，只需两边同时乘以-1即可.（注意不等号符要变号）二、线性规划的解可行解：满足约束条件的解称为线性规划的可行解，所有可行解的集合称为可行域.最优解：满足目标函数的可行解称为线性规划的最优解.其实质就是要从许许多多的可行解中，找出一个使目标函数达到最优值的可行解.线性规划模型解有三种情况：（1）有最优解（2）有可行解，但没有最优解（3）无可行解数学建模之营养配餐问题三、线性规划的求解方法1．单纯形法单纯形法使求解标准形式线性规划的常用方法，这种方法的基本思想是：迭代过程——找出一个基可行解后，判断其是否为最优解；若它不是最优解，再用迭代的方法找出另一个使目标函数值更优的基可行解.

7、经过有限次迭代后，找到最优解或判定出问题无最优解为目标.有兴趣的同学可以下去查看相关的参考书自学，这里不详细介绍.数学建模之营养配餐问题2．借助软件（1）Mathematica软件应用Mathematica软件可以求解各种形式的线性规划问题.命令输入格式：ConstrainedMin(Max)[c,m,{x1,x2,…xn}]例如：在mathematica命令下输入下列语句ConstrainedMin[x+3y+7z,{x+2y>=7,2x+3z>=5,x+y+z>=