数学规划模型.ppt

优化问题：与最大、最小、最长、最短等等有关的问题。解决最优化问题的数学方法：运筹学运筹学主要分支：线性规划、非线性规划、动态规划、图与网络分析、存贮论、排队伦、对策论、决策论。线性规划1939 年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》1947 年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论将实际问题归结为线性规划模型是一个探索创造的过程。线性规划模型的求解仍是计算数学的一个难题。例3. 生产5种产品P1, P2, P3,P4,P5 单价为550, 600, 350, 400, 200. 三道工序:研磨、钻孔、装配。所需工时为P1 P2 P3 P4 P5 I 12 20 0 25 15 II 10 8 16 0 0 III 20 20 20 20 20 各工序的生产能力（工时数）288 192 384 如何安排生产，收入最大。模型：设xi 生产Pi 的件数。则max Z=550 x1+600 x2+350 x3+400 x4+200 x5 。s. t. 12 x1+20 x2+0 x3+25 x4+15 x5≤288 10 x1+8 x2+16 x3+0 x4+0 x5≤192 20 x1+20 x2+20 x3+20 x4+20 x5≤384 xi ≥0 有解x1=12 ，x2 =7.2 ，x3 = x4 = x5 = 0 Z=10920 1. 如果增加三个工序的生产能力，每个工序的单位增长会带来多少价值？2. 结果表明与P1, P2 相比P3, P4, P5 ，定价低了. 价格提到什么程度,它们才值得生产? 对偶问题有解: w1=6.25, w2=0, w3=23.75 Zopt=6.25×288+0×192+23.75×384 X3 的成本: 0 ×6.25+16 ×0+20 ×23.75=475350 例4 供货问题一家公司生产某种商品. 现有n 个客户, 第j 个客户需要货物量至少为bj, 可在m 各不同地点设厂供货. 在地区i 设厂的费用为di , 供货能力为hi , 向第j 个客户供应单位数量的货物费用为cij. 如何设厂与供货使总费用最小. 模型：记xij 为在地区i 向第j 个客户供货数量, 记yi =1 , 在地区i 设厂，记yi =0 不在地区i 设厂，求设厂和供货分配方案yi ，xij 使得目标函数f= yi ( j cij xij + di ) 在约束条件i yi xij bj, j=1,…,n j xij –hi 0, I=1,…,m xij 0, yi ={0, 1} 下达到最小例5 钢材截短有一批钢材, 每根长7.3 米. 现需做100 套短钢材. 每套包括长2.9 米, 2.1 米,1.5 米的各一根. 至少用掉多少根钢材才能满足需要, 并使得用料最省. 设按第i种方法截xi 根钢材(决策变量). 目标函数f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8 约束条件2x1+x2+x3+x4 100 2x2+x4+2x5+3x6+x7 100 x1+2x3+x4+2x5+3x7+4x8 100 xi 0 , i=1,…,8 用Matlab 程序解得x1=40 x2=20 x5=30, f = 7 （实际上应要求xi 为正整数。这是一个整数规划问题）。习题一资源的最优配置策略某工厂有1000 台机器, 生产两种产品A, B, 若投入y 台机器生产A 产品, 则纯收入为5y . 若投入y 台机器生产B 产品, 则纯收入为4y . 又知, 生产A 种产品机器的年折损率为20%, , 生产B 种产品机器的年折损率为10%, 问在5年内如何安排各年度的生产计划, 才能使总收入最高. 习题二一家出版社准备再某市开设两个销售点，向七个区的大学生售书。每个区的大学生数量（千人）如图。每个销售点只能向本区和一个相邻区的大学生售书。这两个销售点应该设在何处，才能使所供应的学生数量最大。目标约束条件时间约束原料约束产量余料时间x1 222.6 1.5 x2 183.3 2 x3 261.8 1 x4 169.5 3 模型建立y1 ~ 易拉罐个数；y2 ~ 不配套的罐身；y3 ~ 不配套的底、盖。每只易拉罐利润0.10 元，余料损失0.001 元/ cm2 罐身面积dh=157.1 cm2 底盖面积d2/4=19.6 cm2 (40 小时) 约束条件配套约束y1 ~ 易拉罐个数；y2 ~ 不配套的罐身；y3 ~ 不配套的底、盖。罐身底、盖1 10 2 4 0 16 4 5 产量x1 x2 x3 x4 虽然xi 和y1 ，y2 ，y3 应是整数，但是因生产量很大，可