数学建模-优化

--数学建模基地系列课件--数学建模优化专题华中农业大学数学建模基地?,./2,5,,321可使利润最大问如何安排计划吨万元的利润分别为且下表原材料（单位：吨）如每吨所需原材料及现有，两种产品，已知生产，生产和，料某工厂计划用三种原材AAAA2410A3301812A1现有原材料ⅡⅠ原材料产品单位消耗生产计划问题线性规划模型8s.t.x13x24x1，x20maxf=5x1+2x2,,,:21吨两种产品分别为设生产解xx求最大利润三种材料量的限制生产量非负线性规划模型华中农业大学数学建模基地。问如何调运使运费最低如下公里单位距离两个粮库到三个粮站的吨大米分别为三个粮站至少需要吨吨为两个粮库现存大米分别调运大米向三个粮站有两个粮库,):(,5,4,2,8,4,,,,32121BBBAA241230A282412A1B3B2B1粮库粮站距离运输问题线性规划模型华中农业大学数学建模基地解：设A1,A2调运到三个粮站的大米分别为x1，x2，x3，x4，x5，x6吨。题设量可总到下表：84库存量x6x5x4A2542需要量x3x2x1A1B3B2B1粮库粮站距离及运量12122430824线性规划模型华中农业大学数学建模基地结合存量限制和需量限制得数学模型：65432124123082412minxxxxxxf0,,,,,54284..654321635241654321xxxxxxxxxxxxxxxxxxts线性规划模型…,Am联合供应n个销地B1,…,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?一般运输问题.:ijjixBA的运输量为到销地设从产地解njmixnjbxmiaxtsxcfijjmiijinjijminjijij,...,1;,...,10,...,1,...,1,..min1111总运价产量限制需量限制运量非负线性规划模型华中农业大学数学建模基地njmixnjbxmiaxtsxcfijjmiijinjijminjijij,...,1;,...,10,...,1,...,1,..min1111假设产销平衡:在很多实际问题中,解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题.njjmiiba11线性规划模型…Bn,分派给n人A1,A2,…An去做,每人只做一件工作且每件工作只派一个人去做,设Ai完成Bj的工时为cij,问应如何分派才能完成全部工作的总工时最少.否则去做分派给工作设解01:ijijABxninjijijxcf11min）（或）（）（njixnixnjxtsijnjijniij,...,2,1,10,...,2,11,...,2,11..11每件工作只派1人每个人只派做1件变量xi只取0和1,故建立的模型也称0-1规划.分派问题线性规划模型华中农业大学数学建模基地?,,,,,1,2:),(),(),(),(),(),(),(:7,,,7654321的年利润最大问如何选择地址使公司元总投资不超过元每年可获利元投资若选个汉口汉阳至少个武昌至多并规定汉商二十一世纪行街步武广司门口亚贸中商个地址有拟议中汉阳建立专卖店汉口某公司拟定在在武昌bcbAAAAAAAAiii否则选择解,0,1:iiAx71maxiiixcf7,...,2,110112..765432171ixxxxxxxxbxbtsiiii或选址问题线性规划模型套钢架,用长为2.9m、2.1m和1.5m的元钢各一根,已知原料长7.4m,问如何下料,使用的原材料最省?分析:下料方式：最省：1.所用刚架根数最少；2.余料最少下料问题线性规划模型华中农业大学数学建模基地原料截成所需长度的根数下料方法ⅠⅡⅢⅣⅤⅥⅦⅧ所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.10.30.901.10.20.81.4:,为则问题的线性规划模型根数种办法下料的原材料的表示按第设ixi线性规划模型取整jjxjxxxxxxxxxxxxxxxxts;8,7,6,5,4,3,2,1,0100432310023321002..876431765324321不同方法截得每种根长的总数至少100例3,4中的此例的变量xi只取正整数,故建立的模型也称整数规划.0-1规划是整数规划的特殊情形.线性规划模型华中农业大学数学建模基地某公司生产某产品,最大生产能力为100单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元)销售量123470607270801207660求一生产计划,使1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.阶段生产问题线性规划模型华中农业大学数学建模基地1je解:假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.为单位成本，为存储费，为销售量，月产量，为第：设模型iiiicedixjiijiidx1131j41jjjxcfmin第j+1个月的库存量第j+1个月的库存费共3个月的库存费4,23,110003,2,1..414111ixdxjdxtsiiiiijijiii且为正整数到本月总生产量大于等于销售量4个月总生产量等于总销售量4个月总生产成本线性规划模型月初的库存量为为单位成本，设第为存储费，为销售量，月产量，为第：设模型4141miniiiiiisexcf..ts1is,iiidxs4,3,2,1i0051ss4321043211000，，，且为整数，，，且为整数，isixii线性规划模型华中农业大学数学建模基地.,,月的销售量第表示的费之和出时的生产成本与存储月卖月生产的产品在第表示第数量月卖出的月生产的产品在第表示第设化为运输问题解法jdjicjixjijij月份单位成本(元)销售量123470607270801207660线性规划模型ijijijjijijjjiijijxxdxtsxcf4,3,2,1j4,3,2,1i4,3,2,1,ji本题3个模型为整数规划模型.线性规划模型华中农业大学数学建模基地线性规划模型特点决策变量：向量(x1…xn)T,决策人要考虑和控制的因素非负；约束条件：线性等式或不等式；目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小；线性规划模型23一般形式0,,..minmax21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcf目标函数约束条件线性规划模型华中农业大学数学建模基地矩阵形式为：记,,,,,,,),,,(212121TnTnnmijnbbbbxxxxaAcccc0..minxbAxtscxfL称为约束矩阵。的每一分量指Axxxj,00矩阵形式线性规划模型华中农业大学数学建模基地满足约束条件的变量的值称为可行解，可行解的集合称为可行域。使目标函数达到最大（小）值的可行解称为最优解，相应的目标函数的值称为最优值。线性规划模型华中农业大学数学建模基地线性规划问题的性质:比例性每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比.可加性每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关.连续性每个决策变量的取值都是连续的.线性规划模型华中农业大学数学建模基地应用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)线性规划模型华中农业大学数学建模基地线性规划问题的基本理论用图解法求解线性规划问题0,4382..25max21212121xxxxxxtsxxf2125:xxc目标函数12252xcx变形为：是一簇斜率为-5/2的平行直线族斜率为-2C/2为直线与y轴的交点x10x284432,3192235max23f最大值取得，所以目标函数在2125:xxc目标函数12252xcx变形为：如图所示:显然直线向右上移动时，与y轴交点越高，从而c/2越大，使得目标函数值c越大。线性规划问题的基本理论华中农业大学数学建模基地从上述几何直观可看出：⑴线性规划问题的任意两个可行解联线上的点都是可行解；⑵线性规划问题的任意两个最优解联线上的点都是最优解；⑶线性规划问题的最优值若存在，则一定在某个顶点达到。线性规划问题的基本理论华中农业大学数学建模基地0,,,..min21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcf任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的。线性规划问题的基本理论标准形式:问题是极大化问题,即nnxcxcxcf2211max可化为极小化问题nnxcxcxcf2211min约束条件不变,其最优解是一致的,但目标函数值的符号相反.则:结论:如果问题是求目标函数的最大值,则化为求–f的最小值;1.关于目标函数线性规划问题的基本理论