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

《lesson6优化模型——线性规划.ppt》由会员分享，可在线阅读，更多相关《lesson6优化模型——线性规划.ppt（27页珍藏版）》请在三一办公上搜索。

1、规划模型,（1）效益最大化或费用最小化（2）各种条件约束1、有关线性规划问题的介绍：几个例子2、线性规划问题的标准形式3、关于整数规划3、应用,一、线性规划问题例1,某化工厂生产A1，A2，A3，A4四种化工产品，每种产品生产1吨消耗的工时、能源和获得的利润如下表：,已知该厂明年的工时限额为18480h，能耗限额为100t标准煤，欲使该厂明年的总利润最高，请确定各种产品的生产数量。,模型,假设：,工时限制,供煤限制,一、线性规划问题例2,一饲养场饲养供实验用的动物，已知动物生长对蛋白质、矿物质和维生素特别敏感，每个动物每天至少需蛋白质70g、矿物质3g和维生素10mg，该厂能得到五种饲料A1、

2、A2、A3、A4和A5，每种饲料10kg的成本分别为2、7、4、3、5。每一千克饲料所含营养成分如下表：,希望建立数学模型，既能满足动物需要，又使总成本最低的饲料配方,模型,二、线性规划问题的标准形式,max y=cTxs.t.Ax=b x0,求解方法：（1）单纯形法（2）软件求解:Lindo，matlab，sas,三、整数规划,一个公司有22亿元资金用来投资，现有6个项目可供选择，各项目所需投资金额和预计年收益如下表所示：,应选择哪几个项目投资收益最大？求解方法：分枝定界法,四、分派问题 0-1规划,问题：,五、网络问题,问题：右图是一公路交通图，弧上数字为路程，求汽车从（1）到（7）最短路

3、。,符号假设：,模型：,问题变形最大流问题,问题变形最小费用流问题,上图,六、问题应用钢管下料,问题：某钢管零售商从钢管厂进货，将钢管按顾客 的要求切割后售出，从钢管厂进货时得到的 原料钢管都是19m。（1）现有一客户需要50根4m、20根6m和15根8m 的钢管，应如何下料最省。（2）零售商如果采用的不同切割模式太多，将会 导致生产过程的复杂化，从而增加生产和管 理成本，所以该零售商规定采用的不同切割 模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5m的钢管，应 如何下料最省。,问题（1）解答,钢管下料合理切割模式：,问题：按何种切割模式，切割多少根原钢管，最为节省。

4、节省：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米长的

5、地方用来装包装箱，载重40吨。由于货运限制，对c5、c6、c7类包装箱总数有限定：总厚度不超过302.7(厘米)。试把箱子装到平板车并使空间浪费最小。,八、应用（AMCM-89B）,机场通常按“先来先走”的原则来分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道的队伍。假设控制中心可以从快速联机数据库中得到每架飞机如下信息：1、预定离开登机口的时间 2、实际离开登机口的时间 3、机上乘客人数 4、预定在下一站转机的人数和时间 5、到达下一站的预定时间。又设飞机共有七种型号，载客量从100人起以50人递增，载客最多达400人。试开发和分析一种能使乘客和航空公司双方满意的数学模型。,九、数学的实践与认识（1998.1）,地图,十、数学的实践与认识（1998.1）,数据,问题,问题（3）的图,讨论题,