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

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