线性规划问题的有关概念

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)，都有一个要达到的目标，用决策变量的一次