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

线性规划与最优化模型 营养配餐 数学建模讲座 数学建模之营养配餐问题 1 问题的提出 每种蔬菜含有的营养素成份是不同的，从医学上知道每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表1中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少kg？ 一 营养配餐问题 数学建模之营养配餐问题 表1 序 号 蔬 菜 每 份 所 含 营 养 素 单 位 数 每千克费 用 铁 磷 维生素A 维生素C 烟酸 1 青 豆 0.45 10 415 8 0.30 5 2 胡萝卜 0.45 28 9065 3 0.35 5 3 菜 花 1.05 59 2550 53 0.60 8 4 白 菜 0.40 25 75 27 0.15 2 5 甜 菜 0.50 22 15 5 0.25 6 6 土 豆 0.50 75 235 8 0.80 3 要 求 蔬 菜 提供的营养 6.00 25 17500 245 5.00 ? 数学建模之营养配餐问题 2 问题分析与模型建立 铁的需求量至少6个单位数： 磷的需求量至少25个单位数： 维生素A的需求量至少17500个单位数： 设 分别表示在下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量(kg)，则费用的目标函数为: 约束条件： 数学建模之营养配餐问题 设问题是在满足营养素要求的条件下，所需的费用最小 烟酸的需求量至少5个单位数： 每周需供应140kg蔬菜，即 维生素C的需求量至少245个单位数： 数学建模之营养配餐问题 人们在日常生活中,经常会遇到在有限的资源情况下,如何合理安排,使之产值或利润最大,或在任务给定后,如何统筹安排,使之以最小成本或最小代价完成任务等决策问题. 规划论就是解决这类问题的重要数学方法.首先我们要给大家介绍一些有关线性规划的基本知识. 3 补充基本知识----线性规划 数学建模之营养配餐问题 线性规划 一、线性规划概念 定义1：规划的数学模型中如果满足： （1）目标函数是决策变量的线性函数； （2）约束条件都是决策变量的线性等式或不等式，则称该规划为线性规划. 1．线性规划的一般形式 目标函数 ： 数学建模之营养配餐问题 约束条件 ： 可以缩写为 数学建模之营养配餐问题 2．线性规划标准形式 从线性规划数学模型的一般形式可以看出，目标函数可以是实现最大化，也可以实现最小化，约束条件可以是不等式，也可以是等式，这种模型形式上的多样性势必给求解带来不便，为了便于讨论线性规划的求解方法，我们给出规划问题的标准形式. 数学建模之营养配餐问题 目标函数 约束条件 可以缩写为 数学建模之营养配餐问题 标准形式的矩阵形式为 数学建模之营养配餐问题 我们知道，由于一般形式中有多个不等式，所以求解过程很困难，但标准形式求解起来就比较容易，那么，如何将线性规划的一般形式转化为标准形式呢？ 3．化一般形式为标准形式 （1）目标函数 如果目标函数是最大化类型，将其转化为最小化类型非常简单，只需令S’=-S,即 （2）约束不等式化为约束等式 数学建模之营养配餐问题 将约束不等式化为约束等式需要我们把不等式中引入新的非负变量（我们称之为松弛变量或剩余变量），来平衡不等式的两端使之成为等式. 数学建模之营养配餐问题 所以约束条件中有多少个不等式，就要引入多少个新的非负变量，使不等式条件转化为等式. 总结： 数学建模之营养配餐问题 （3）标准形式中的变量要求都是非负的，如果一般形式中某个变量没有符号限制，可以为正也可以为负，如果使其保持非负？ 数学建模之营养配餐问题 （4）对约束条件右端bi为负时，只需两边同时乘以-1即可.（注意不等号符要变号