《线性规划数学模型》PPT课件.ppt

第二讲 线性规划数学模型 第二讲第二讲 线性规划线性规划 1 第二讲 线性规划数学模型 一 、线性规划的数学模型 l1、线形规划基本概念 l问题的提出 为了完成一项任务或达到一定的目的， 怎样用最少的人力、物力去完成或者用最 少的资源去完成较多的任务或达到一定的 目的，这个过程就是规划。 2 第二讲 线性规划数学模型 如生产计划问题如生产计划问题 如何合理使用有限的人力，物力和 资金，使得收到最好的经济效益。 如何合理使用有限的人力，物力和 资金，以达到最经济的方式，完成 生产计划的要求。 3 第二讲 线性规划数学模型 例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产 品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表： 问题：工厂应分别生产多少单位、产品才能使工厂获利最多？ 线性规划模型： 目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0 4 第二讲 线性规划数学模型 从上例看出问题中总有未知的变量， 需要我们去解决。如果在规划问题的数学 模型中，变量是连续的（数值取实数）其 目标函数是有关线性函数（一次方），约 束条件是有关变量的线性等式或不等式， 这样，规划问题的数学模型是线性的，是 线形规划问题。反之，就是非线性的规划 问题（其中一个条件符合即可）。 5 第二讲 线性规划数学模型 2、线形规划数学模型建模过程 （1）理解要解决的问题，了解解题的目 标和条件； （2）定义决策变量（ x1 ，x2 ， ，xn ） ，每一组值表示一个方案； （3）用决策变量的线性函数形式写出目 标函数，确定最大化或最小化目标； （4）用一组决策变量的等式或不等式表 示解决问题过程中必须遵循的约束条件 6 第二讲 线性规划数学模型 （5）线形规划一般形式 l目标函数： Max （Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 7 第二讲 线性规划数学模型 l（6）从几个管理中的例题看线形规划数 学模型的建立 8 第二讲 线性规划数学模型 例例1 1 生产计划问题（资源利用问题）生产计划问题（资源利用问题） 胜利家具厂生产桌子和椅子两种家具。胜利家具厂生产桌子和椅子两种家具。 桌子售价桌子售价5050元元/ /个，椅子销售价格个，椅子销售价格3030元元/ /个，个， 生产桌子和椅子要求需要木工和油漆工两种生产桌子和椅子要求需要木工和油漆工两种 工种。生产一个桌子需要木工工种。生产一个桌子需要木工4 4小时，油漆工小时，油漆工 2 2小时。生产一个椅子需要木工小时。生产一个椅子需要木工3 3小时，油漆小时，油漆 工工1 1小时。该厂每个月可用木工工时为小时。该厂每个月可用木工工时为120120小小 时，油漆工工时为时，油漆工工时为5050小时。问该厂如何组织小时。问该厂如何组织 生产才能使每月的销售收入最大？生产才能使每月的销售收入最大？ 9 第二讲 线性规划数学模型 解：将这个实际问题转化为线性规划模型有以下几解：将这个实际问题转化为线性规划模型有以下几 个步骤：个步骤： 1 1确定决策变量：确定决策变量：x x 1 1 = =生产桌子的数量生产桌子的数量 x x 2 2 = =生产椅子的数量生产椅子的数量 2 2确定目标函数：家具厂的目标是销售收入最大确定目标函数：家具厂的目标是销售收入最大 max z=50xmax z=50x 1 1 +30x+30x 2 2 3 3确定约束条件：确定约束条件： 4x4x 1 1 +3x+3x 2 2 120120（木工工时限制）木工工时限制） 2x2x 1 1 +x+x2 2 50 50 （油漆工工时限油漆工工时限 制）制） 4 4变量取值限制：变量取值限制： 一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值） x x1 1 0, x 0, x2 2 0 0 10 第二讲 线性规划数学模型 数学模型数学模型 max Z=50xmax Z=50x 1 1 +30x+30x2 2 s.ts.t. 4x. 4x 1 1 +3x+3x2 2 120 120 2x 2x 1 1 + x+ x2 2 50 50 x x 1 1 ,x,x2 2 0 0 线性规划数学模型三要素：线性规划数学模型三要素： 决策变量、约束条件、目标函数决策变量、约束条件、目标函数 11 第二讲 线性规划数学模型 例2:某工厂拥有A、B、C 三种类型的设 备，生产甲、乙两种产品。每件产品在生 产中需要占用的设备机时数，每件产品可 以获得的利润以及三种设备可利用的时数 如下表所示： 产品甲产品乙设备能力（h ） 设备A3265 设备B2140 设备C0375 利润（元/件）15002500 12 第二讲 线性规划数学模型 问题：工厂应如何安排生产可获得最大的 总利润？ 解：设变量 xi 为第 i 种（甲、乙）产 品的生产件数（i1，2）。根据题意，我们 知道两种产品的生产受到设备能力（机时数） 的限制。对设备A：两种产品生产所占用的机 时数不能超过65，于是我们可以得到不等式： 3 x1 + 2 x2 65； 对设备B：两种产品生产所占用的机时数 不能超过40，于是我们可以得到不等式： 2 x1 + x2 40； 13 第二讲 线性规划数学模型 对设备C ：两种产品生产所占用的机时数不能 超过75，于是我们可以得到不等式： 3x2 75 ； 另外，产品数不可能为负，即 x1 ,x2 0。 同时，我们有一个追求目标，即获取最大利润 。于是可写出目标函数z为相应的生产计划可以获得 的总利润： z = 1500x1 + 2500x2 综合上述讨论，在加工时间以及利润与产品产 量成线性关系的假设下，把目标函数和约束条件放 在一起，可以建立如下的线性规划模型： 14 第二讲 线性规划数学模型 目标函数 Max z =1500x1+2500x2 约束条件 s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 ,x2 0 15 第二讲 线性规划数学模型 例3 营养配餐问题 假定一个成年人每天需要从食物中获得 3000千卡的热量、55克蛋白质和800毫克的钙 。如果市场上只有四种食品可供选择，它们 每千克所含的热量和营养成分和市场价格见 下表。问如何选择才能在满足营养的前提下 使购买食品的费用最小？ 16 第二讲 线性规划数学模型 各种食物的营养成分表各种食物的营养成分表 17 第二讲 线性规划数学模型 解：设xj为第j种食品每天的购入量，则配餐问题 的线性规划模型为： min Z=14x1+6x2 +3x3+2x4 s.t. 1000x1+800x2 +900x3+200x4 3000 50x1+ 60x2 + 20x3+ 10x4 55 400x1+200x2 +300x3+500x4 800 x1，x2 ， x3 ， x4 0 18 第二讲 线性规划数学模型 3、在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 l配料问题：在原料供应量的限制下如何获取最大利润 l投资问题：从投资项目中选取方案，使投资回报最大 l产品生产计划：合理利用人力、物力、财力等，使获利最大 l劳动力安排：用最少的劳动力来满足工作的需要 l运输问题：如何制定调运方案，使总运费最小 l等等 l线性规划的组成： l目标函数 Max F 或 Min F l约束条件 s.t. (subject to) 满足于 l决策变量 用符号来表示可控制的因素 19 第二讲 线性规划数学模型 规划类型 规 划 确定型 随机型 静态规划 动态规划