数模初级培训之线性规划模型.ppt

数学建模 之 线性规划模型 例1：最优生产计划问题 某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，单件产品在不同设备上加工时间、所需要材料量、利润见下表： 问：如何安排生产计划，使企业在计划期内总的利润收入最大？ 建模的步骤 用数学语言表述问题(提出假设，定义数学符号，分析变量之间的数学关系…) 选择建模方法 构建数学模型 求解模型 对结果进行分析、检验，回答问题 例1：最优生产计划问题 假设1：该企业以利润最大为目标。 分析：问题中需要决定 甲产品生产的数量(件) (可设为变量x1) 乙产品生产的数量(件) (可设为变量x2) 丙产品生产的数量(件) (可设为变量x3) 则利润可表示为：40 x1+30 x2+50 x3 约束条件 A设备工时限制： 例1：最优生产计划问题 设x1、x2、x3 分别为甲、乙、丙三种产品的产量，Z表示企业在计划期内总的利润，问题的数学模型为： 线性规划问题的一般模型 每一个问题都可以用一组决策变量 (x1, x2, …, xn) 表示问题的待定方案，这组决策变量的一组确定的值就代表一个具体方案，这组变量的取值往往是非负的。 存在一定的约束条件，这些约束条件都能用关于决策变量的线性等式或不等式来表示。 线性规划问题的一般模型 有一个期望达到的目标，这个目标能用某种确定的数量指标刻画出来，而这种数量指标可表示为关于决策变量的线性函数，按所考虑的问题不同，要求目标函数实现最大化或最小化。 满足以上三个条件的问题就是线性规划(Linear Programming)问题 线性规划问题的一般模型　 　一般地，假设线性规划数学模型中有m个约束，有n个决策变量xj， j=1, 2, …, n。 目标函数中变量的系数称为价值系数,用cj表示。 约束条件的变量系数称为工艺系数,用aij表示。 约束条件右端的常数称为资源限量,用bi表示(i=1, 2, …, m)。 线性规划数学模型的一般表达式 线性规划数学模型的一般表达式 如何从实际问题中抽象出线性规划模型？ 设（决策）变量 根据问题写出变量应满足的条件（约束条件） 写出目标（函数） 例3：易拉罐下料问题 某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压成的，为圆柱状，包括罐身、上盖和下底。罐身高10cm，上盖和下底的直径均为5cm。该公司使用两种不同规格的镀锡板原料，规格1的镀锡板为正方形，边长24cm；规格2的镀锡板为长方形，长32cm ，宽28cm；由于生产设备和生产工艺的限制，规格1的镀锡板只能按模式1、2、3冲压，规格2的镀锡板只能按模式4冲压(见图)，使用模式1、2、3、4进行冲压所需时间分别为1.5秒、2秒、1秒和3秒 冲压模式 易拉罐下料问题 该公司每周工作40小时，每周可供使用的规格1、2的镀锡板原料分别为5万张和2万张，目前每只易拉罐的利润为0.1元，原料余料损失为0.001元/cm2(如果周末有罐身、上盖或下底不能配套成易拉罐出售，也看成是余料损失)。公司应如何安排每周的生产？ 问题分析：目标应是易拉罐的利润扣除原料余料损失后的净利润最大；约束条件除每周工作时间的原料数量外，还要考虑罐身和盖、底的配套组装。 四种冲压模式的特征 模型建立 决策变量： 用xi表示按第i种模式冲压的次数(i=1,2,3,4) y1表示一周生产的易拉罐个数 y2表示不配套的罐身个数 y3表示不配套的盖(底)个数 决策目标(设每周生产的易拉罐全部售出)： 净利润最大 净利润=利润－四种冲压模式的余料损失－不配套造成的原料损失 模型建立 决策目标(设每周生产的易拉罐全部售出)： maxZ=0.1y1－0.001(222.6x1 +183.3x2 +261.8x3 +169.5x4 +157.1y2+19.6y3) 其中： 不配套罐身每个损失 10×π×5=157.1 cm2 不配套盖(底)每个损失 π×2.52=19.6 cm2 模型建立 约束条件 时间约束：每周工作不超过40小时(144000秒) 1.5x1 +2x2 +x3 +3x4 ≤144000 原料数量约束：规格1、2镀锡板分别为5万张和2万张 x1 +x2 +x3 ≤50000 x4 ≤20000 配套约束： 一周生产的罐身个数= x1 +2x2 +4x4 一周生产的盖(底)个数= 10x1 +4x2 +16x3 +5x4 模型建立 配套约束： 一周生产的易拉罐个数= min{x1 +2x2 +4x4， 0.5(10x1 +4x2 +16x3 +5x4)} 可以表示成两个线性约束 y1 ≤ x1 +2x2 +4x4 y1