线性规划问题的有关概念

18 1线性规划问题的有关概念 授课人 潘红胜 例1某点心店要做甲 乙两种馒头 甲种馒头的主要原料是每3份面粉加2份玉米粉 乙种馒头的主要原料是每4份面粉加一份玉米粉 这个点心店每天可买进面粉50kg 玉米粉20kg 做1kg甲种馒头的利润是5元 做1kg乙种馒头的利润是4元 那么这个点心店每天各做多少个甲 乙两种馒头才能获利最多 解 设计划做甲种馒头xkg 乙种馒头ykg 所获利润为z元 则 1 2 3 4 5 2 记号 max 表示取函数的最大值 3 式 1 称为目标函数 目标函数可最大化或最小化 4 式 2 5 统称为目标函数的约束条件 例1某点心店要做甲 乙两种馒头 甲种馒头的主要原料是每3份面粉加2份玉米粉 乙种馒头的主要原料是每4份面粉加一份玉米粉 这个点心店每天可买进面粉50kg 玉米粉20kg 做1kg甲种馒头的利润是5元 做1kg乙种馒头的利润是4元 那么这个点心店每天各做多少个甲 乙两种馒头才能获利最多 解 设计划做甲种馒头xkg 乙种馒头ykg 所获利润为z元 则 1 2 3 4 5 5 在数学中 线性规划问题是目标函数和约束条件都是线性的最优化问题 6 线性规划问题的三要素 决策变量 目标函数 约束条件 7 决策变量 是线性规划问题要确定的未知量 决策变量有非负的要求 例1某点心店要做甲 乙两种馒头 甲种馒头的主要原料是每3份面粉加2份玉米粉 乙种馒头的主要原料是每4份面粉加一份玉米粉 这个点心店每天可买进面粉50kg 玉米粉20kg 做1kg甲种馒头的利润是5元 做1kg乙种馒头的利润是4元 那么这个点心店每天各做多少个甲 乙两种馒头才能获利最多 解 设计划做甲种馒头xkg 乙种馒头ykg 所获利润为z元 则 1 2 3 4 5 8 目标函数 是决策变量的线性函数 根据问题的不同 要求实现最大化或最小化 9 约束条件 是指决策变量取值时存在一定的限制条件 且表示为线性不定式 例1某点心店要做甲 乙两种馒头 甲种馒头的主要原料是每3份面粉加2份玉米粉 乙种馒头的主要原料是每4份面粉加一份玉米粉 这个点心店每天可买进面粉50kg 玉米粉20kg 做1kg甲种馒头的利润是5元 做1kg乙种馒头的利润是4元 那么这个点心店每天各做多少个甲 乙两种馒头才能获利最多 解 设计划做甲种馒头xkg 乙种馒头ykg 所获利润为z元 则 1 2 3 4 5 10 常见的两种线性规划问题 如何合理利用有限的资源 使其产生最大的效益 如何制定最佳方案 以尽可能少的资源完成所要做的事情 效益最大化 成本最低化 例1某点心店要做甲 乙两种馒头 甲种馒头的主要原料是每3份面粉加2份玉米粉 乙种馒头的主要原料是每4份面粉加一份玉米粉 这个点心店每天可买进面粉50kg 玉米粉20kg 做1kg甲种馒头的利润是5元 做1kg乙种馒头的利润是4元 那么这个点心店每天各做多少个甲 乙两种馒头才能获利最多 解 设计划做甲种馒头xkg 乙种馒头ykg 所获利润为z元 则 1 2 3 4 5 12 从实际问题中建立线性规划模型的三个步骤 第一步 确定决策变量 第二步 确定目标函数 第三步 确定约束条件 11 把实际问题抽象为数学形式的方法叫做数学建模 建立数学模型 注 本节只建模 不求解 解 设建普通住宅楼x栋 别墅y栋 则有 解 设该厂生产甲产品x件 乙产品y件 则有 练习1 建立下面线性规划问题的数学模型 某厂计划生产甲 乙两种产品 其主要原材料有钢材1500kg 铜材2700kg 每件产品耗材定额 kg 及所获利润 元 如下表 问 如何安排生产能使该厂所获利润最大 例3 某运输公司有8辆载重6t的A型卡车 4辆载重10t的B型卡车 并有9名驾驶员 在建造某段高速公路时 公司承包了每天至少运输沥青180t的任务 已知每辆卡车每天往返次数为A型4次 B型6次 派出每辆卡车每天的成本为A型120元 B型200元 每天应派出A型和B型卡车各多少辆 能使公司总成本最低 解 设每天应派出A型卡车x辆 B型卡车y辆 则有 练习2 某运输公司有8辆载重6t的A型卡车 4辆载重10t的B型卡车 并有9名驾驶员 在建造某段高速公路时 公司承包了每天至少运输沥青180t的任务 已知每辆卡车每天往返次数为A型4次 B型6次 派出每辆卡车每天可得利润为A型120元 B型200元 每天应派出A型和B型卡车各多少辆 能使公司利润最大 解 设每天应派出A型卡车x辆 B型卡车y辆 则有 解 设买A种饲料千克 B种饲料y千克 则有 练习3 建立下面线性规划问题的数学模型 某饲养场要同时用A B两种饲料喂养动物 要求每头动物每天至少应摄取10个单位的蛋白质和9个单位的矿物质 两种饲料每千克中所含两种成分的数量 单位 及每千克的单价 元 如下表 该饲养场每天要买两种饲料各多少千克 才能满足动物生长的需要 又使费用最省 课堂作业 教程P93 习题1 13 线性规划问题 求线性目标函数在线性约束条件下的最大值或最小值的问题 通常称为线性规划问题 14 线性规划问题的数学模型都具有的共同特征 1 每一个问题都用一组决策变量来表示 这些变量一般情况下取非负值 2 存在一定的约束条件 通常用一组一次 线性 不定式或等式表示 3 都有一个要达到的目标 用决策变量的一次 线性 函数即目标函数来表示 按问题的不同实现最大化或最小化