lesson6（优化模型——线性规划）.ppt

规划模型,（1）效益最大化或费用最小化 （2）各种条件约束 1、有关线性规划问题的介绍：几个例子 2、线性规划问题的标准形式 3、关于整数规划 3、应用,一、线性规划问题例1,某化工厂生产A1，A2，A3，A4四种化工 产品，每种产品生产1吨消耗的工时、能源和 获得的利润如下表：,已知该厂明年的工时限额为18480h，能耗 限额为100t标准煤，欲使该厂明年的总利润最 高，请确定各种产品的生产数量。,模型,假设：,工时限制,供煤限制,一、线性规划问题例2,一饲养场饲养供实验用的动物，已知动物生长对蛋白质、矿物质和维生素特别敏感，每个动物每天至少需蛋白质70g、矿物质3g和维生素10mg，该厂能得到五种饲料A1、A2、A3、A4和A5，每种饲料10kg的成本分别为2、7、4、3、5。每一千克饲料所含营养成分如下表：,希望建立数学模型，既能满足动物需要，又使总成 本最低的饲料配方,模型,二、线性规划问题的标准形式,max y=cTx s.t. Ax=b x0,求解方法： （1）单纯形法 （2）软件求解:Lindo， matlab，sas,三、整数规划,一个公司有22亿元资金用来投资，现有6个 项目可供选择，各项目所需投资金额和预计年 收益如下表所示：,应选择哪几个项目投资收益最大？ 求解方法：分枝定界法,四、分派问题 0-1规划,问题：,五、网络问题,问题： 右图是一公路交通图，弧上数字为路程，求汽车从（1）到（7）最短路。,符号假设：,模型：,问题变形最大流问题,问题变形最小费用流问题,上图,六、问题应用钢管下料,问题：某钢管零售商从钢管厂进货，将钢管按顾客 的要求切割后售出，从钢管厂进货时得到的 原料钢管都是19m。 （1）现有一客户需要50根4m、20根6m和15根8m 的钢管，应如何下料最省。 （2）零售商如果采用的不同切割模式太多，将会 导致生产过程的复杂化，从而增加生产和管 理成本，所以该零售商规定采用的不同切割 模式不能超过3种。此外，该客户除需要（1） 中的三种钢管外，还需要10根5m的钢管，应 如何下料最省。,问题（1）解答,钢管下料合理切割模式：,问题：按何种切割模式，切割多少根原钢管，最为节省。 节省： 1）余料最少 2）原钢管总数最少,双目标,模型,设x i表示照第i种模式切割原材料钢管的根数,总余料最小 原钢管条数最少,问题（2）解答,问题分析： 一合理的切割模式的余料不应该大于或等于 客户需要的钢管的最小尺寸，故本题中合理的切 割模式的余量不能大于3m。故可选择总根数最少 为目标进行求解。,模型建立,设x i表示照第i种模式切割原材料钢管的根数（i=1,2,3） r ij分别表示第i种切割模式下生产j米（j=4,5,6,8）钢管数,七、几个应用（AMCM-88B）,将七种不同规格的包装箱装到两辆铁路平板 车上，各包装箱宽、高均相等，但厚度t(厘米)与 重量w(公斤)不同。每平板车有10.2米长的地方用 来装包装箱，载重40吨。由于货运限制，对c5、 c6、c7类包装箱总数有限定：总厚度不超过302.7 (厘米)。试把箱子装到平板车并使空间浪费最小。,八、应用（AMCM-89B）,机场通常按“先来先走”的原则来分配飞机跑道，即当 飞机准备好离开登机口时，驾驶员电告地面控制中心，加 入等候跑道的队伍。假设控制中心可以从快速联机数据库 中得到每架飞机如下信息： 1、预定离开登机口的时间 2、实际离开登机口的时间 3、机上乘客人数 4、预定在下一站转机的人数和时间 5、到达下一站的预定时间。 又设飞机共有七种型号，载客量从100人起以50人递 增，载客最多达400人。 试开发和分析一种能使乘客和航空公司双方满意的数 学模型。,九、数学的实践与认识（1998.1）,地图,十、数学的实践与认识（1998.1）,数据,问题,问题（3）的图,讨论题,