线性规划的概念及图解法.ppt

例1 某中药厂用当归作原料制成当归丸与当归膏 生产1盒当归丸需要5个劳动工时 使用2kg当归原料 销售后获得利润160元 生产1盒当归膏需要2个劳动工时 使用5kg当归原料 销售后获得利润80元 工厂现有可供利用的劳动工时为4000工时 可供使用的当归原料为5800kg 为避免当归原料存放时间过长而变质 要求把5800kg当归原料都用掉 问工厂如何安排生产 才能使得两种产品销售后获得的总利润最大 一 概念的引出 解设工厂生产x1盒当归丸与x2瓶当归膏 可建立以下数学模型 目标函数为 约束条件为 决策变量为 x1 x2 例2某公司由于生产需要 共需要A B两种原料至少350吨 A B两种材料有一定替代性 其中A原料至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨A原料需要2个小时 加工每吨B原料需要1小时 而公司总共有600个加工小时 又知道每吨A原料的价格为2万元 每吨B原料的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 解 设购买A种原料为x1 B种原料为x2 可建立以下数学模型 目标函数 MinS 2x1 3x2约束条件 s t x1 x2 350 x1 1252x1 x2 600 x1 x2 0 s t 是subjectto的缩写 意思为 满足于 受约束于 决策变量为 x1 x2 数学规划模型 实际问题中的优化模型 x 决策变量 f x 目标函数 gi x 0 约束条件 数学规划 线性规划非线性规划整数规划 线性规划问题 LP 一组线性不等式约束下求线性目标函数的极大值或极小值问题 决策变量的一组取值便构成了线性规划问题的一个解 满足约束条件的解称为可行解 所有可行解构成的集合称为可行解集 使目标函数达到所追求极值的可行解称为最优解 最优解所对应的目标函数值称为最优值 相关定义 二 线性规划的表现形式 一般形式 目标函数和所有的约束条件都是设计变量的线性函数 目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 基本线性规划形式目标函数 Max Min S c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 bi 0 建模过程1 理解要解决的问题 了解解题的目标和条件 2 定义决策变量 x1 x2 xn 每一组值表示一个方案 3 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 4 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 三 线性规划问题的数学模型 生产安排原料搭配问题条件下料问题物资运输问题 某家具厂需要长80cm的角钢与长60cm的角钢 它们皆从长210cm的角钢截得 现在对长80cm角钢的需要量为150根 对长60cm角钢的需要量为330根 问工厂应如何下料 才能使得用料最省 写出数学模型 条件下料问题1 分析 共有三种下料方式 第一种是将1根长210的角钢截得2根长80cm的角钢 第二种是将1根长210的角钢截得1根长80cm和2根60cm的角钢 第三种是将210cm的角钢截得3根长60cm的角钢 现这三种下料方式应该混合使用 解 设第一种下料方式用掉x1根角钢 第二种下料方式用掉x2根角钢 第三种下料方式用掉x3根角钢 变量x1x2x3即为决策变量 数学模型为 某车间有一批长度为7 4m的同型钢管 因生产需要 需将其截成长2 9m 2 1m 1 5m三种不同长度的管料 若三种管料各需100根 问应如何下料 才能使得用料最省 写出数学模型 条件下料问题2 分析 解 设第一种下料方式用掉x1根管料 第二种下料方式用掉x2根管料 第三种下料方式用掉x3根管料 第四种下料方式用掉x4根管料 第五种下料方式用掉x5根管料 变量x1x2x3x4x5即为决策变量 数学模型为 例1 目标函数 MaxS 50 x1 100 x2约束条件 s t x1 x2 3002x1 x2 400 x2 250 x1 0 x2 0 四图解法 对于只有两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 四图解法 1 分别取决策变量X1 X2为坐标向量建立直角坐标系 取各约束条件的公共部分 2 目标函数z 50 x1 100 x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件则其可行域的顶点也是有限的 重要结论1 当线性规划问题的可行域非空时 它是有界或无界的凸多边形 凸集 如果线性规划有最优解 则一定有一个可行域的顶点对应一个最优解 无穷多个最优解 若将例1中的目标函数变为maxz 50 x1 50 x2 则线段BC上的所有点都代表了最优解 重要结论2 无界解 即可行域的范围延伸