线性规划的数学模型和基本性质.ppt

工学研究生（工程硕士）公共课程工学研究生（工程硕士）公共课程最优化计算最优化计算主讲教师：华南理工大学数学科学学院主讲教师：华南理工大学数学科学学院 蒋金山蒋金山第第 一一 章章线性规划的数学模型和基本性质线性规划的数学模型和基本性质 例例 1.1.1 1.1.1 某某工工厂厂拥拥有有A A、B B、C C 三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备备可可利利用用的的时时数数如如下表所示：下表所示：产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）1500150025002500 问问题题：工工厂厂应应如如何何安安排排生生产产可可获获得得最最大的总利润？大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3 x1+2 x2 65；对设备B，两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2 x1+x2 40；对对设设备备C C，两两种种产产品品生生产产所所占占用用的的机机时时数数不不能能超超过过7575，于于是是我我们们可可以以得得到到不不等等式式：3 3x2 2 75 75；另另外外，产产品品数数不不可可能能为为负负，即即 x1 1 ,x2 2 00。同同时时，我我们们有有一一个个追追求求目目标标，即即获获取取最最大大利利润润。于于是是可可写写出出目目标标函函数数z z为为相相应应的的生生 产产 计计 划划 可可 以以 获获 得得 的的 总总 利利 润润：z=1500=1500 x1 1+2500+2500 x2 。综综合合上上述述讨讨论论，在在加加工工时时间间以以及及利利润润与与产产品品产产量量成成线线性性关关系系的的假假设设下下，把把目目标标函函数数和和约约束束条条件件放放在在一一起起，可可以以建建立立如下的线性规划模型：如下的线性规划模型：目标函数 maxz=1500 x1+2500 x2约束条件.3x1+2x2652x1+x2403x275x1,x2 0 这这是是一一个个典典型型的的利利润润最最大大化化的的生生产产计计划划 问问 题题。其其 中中，“Max”“Max”是是 英英 文文 单单 词词“Maximize”“Maximize”的的缩缩写写，含含义义为为“最最大大化化”；“s.t.”“s.t.”是是“subject“subject to”to”的的缩缩写写，表表示示“满满足足于于”。因因此此，上上述述模模型型的的含含义义是是：在在给给定定条条件件限限制制下下，求求使使目目标标函函数数z达达到到最最大大的的x1 1 ,x2 的的取取值值。教教材材中中的的例例与与本例类似。本例类似。例例1.1.2 某公司经销一种产品，现要将三个生产某公司经销一种产品，现要将三个生产点生产的产品分别运往四个销售点已知点生产的产品分别运往四个销售点已知三个生产点的每日产量、各销售点的每日三个生产点的每日产量、各销售点的每日销量、以及每吨产品从各生产点到销售点销量、以及每吨产品从各生产点到销售点的运价见下表试问该公司应如何调运产的运价见下表试问该公司应如何调运产品，可在满足各销售点需要量的前提下，品，可在满足各销售点需要量的前提下，使总运费最少？使总运费最少？一般形式 目标函数：Max(Min)z=c1x1+c2x2+cnxn 约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2.am1x1+am2x2+amnxn(=,)bm x1，x2，xn01.1.2 1.1.2 线性规划问题的数学模型线性规划问题的数学模型