数学规划期末结题报告.doc

kszl数学规划期末报告 姓名： 班级： 学号： 专业： 一 摘要数学规划其实就是问题的最优化，解题分为三个过程：（1）将实际问题形式化，建立相应数学模型，一般由目标函数、约束条件和决策变量组成（2）求解对应的数学模型（3）验证结果的合理性与正确性。解决.数学规划问题的关键是找出他的目标函数和约束方程并将它们转化为标准形式。数学规划的解法基础是单纯形法（对偶单纯形法），利用单纯形表我们可以（1）直接找出基本可行解与对应的目标函数值（2）通过检验数判断原问题解的性质以及是否为最优解（3）能很快的求出影子价格等实际经济问题。数学规划广泛应用于以下方面：（1）生产计划（用最少的钱取得最大的获利）（2）运输问题（公交、飞机等人员服务时间安排）（3）人事管理（人员的指派）（4）城市管理（救火站、救护车等分布点的设立）。这里我们主要讨论的是数学规划在生产计划和运输问题两个方面的应用，主要的方法有：单纯形法、灵敏度分析、表上作业法。实际应用应用一：奶制品的加工与销售 一奶制品加工厂用牛奶生产A1，A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1，A2全部售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。（1） 试为该厂制定一个生产计划，使每天获利最大；（2） 33元可以买到一桶牛奶，买吗？（3） 若买，每天最多买多少？（4） 可聘用临时工人，付出工资最多是每小时几元？（5） A1的获利增加到30元/公斤，应否改变生产计划？解：问题（1）建立相应的数学模型：设用x1桶牛奶生产A1，用x2桶牛奶生产A2，Z表示获利，由题意有 max Z=24*3x1+16*4x2 =72x1+64x2 s.t. x1+x2=5012x1+8x2=0 x2=0 在上问题中加入松弛变量 x3,x4,x5,得到 max Z=72x1+64x2 s.t. x1 + x2 + x3 =5012x1+8x2 + x4 =4803x1+ x5 =100x1=0,x2=0 模型求解： 用单纯性法计算： Cj72 64 0 0 0iCBxBbx1x2x3x4x50x35011100500x4480128010400x510030001100/3 j72640000x350/30110-1/350/30x4800801-41072x1100/31000-1/3 j06400-240x320/3001-1/81/66064x2100101/8-1/272x1100/310001/3100j000-880x540006-3/4164x230013-1/4072x12010-21/40 j00-48-20=X=(20,30,0,0,40)验证数学规划的合理性与正确性有结果可知 ：用20桶牛奶生产A1，用30桶牛奶生产A2，此时符合题意。max Z=72*20+64*30=3360(元)即用20桶牛奶生产A1，用30桶牛奶生产A2，有最大获利3360元。问题（2）先求出原材料增加的影子价格由单纯形表可以看出 B-1=6-3413-140-2140 b1=100 =B-1b=6-3413-140-2140 100=63-2 =z=72*(-2)+64*3=-144+192=4833 33元买一桶的方案可行。问题（3）由B-1b+B-1b1=403020+6-3413-140-2140b00=40+6b130+3b120-2b1=000 =b1=-20/3, b1=-10, b1-203 =b1 最多每天买10桶问题(4) 求出工人的工作时间增加一小时的额外获利 B-1b2=6-3413-140-21400b20=-34-1414 =z=72*14-64*14=2(元) =付出的工资最多每小时2元。问题（5）设x1的系数C1变化3C，在最优解不变的条件下，求C得范围最终的单纯形表为： Cj72+3C 64 0 0 0CBxBbx1x2x3x4x50x540006-3/4164x230013-1/4072+3Cx12010-21/40 j00-48+6C-2-34C0=-48+6C0-2-34C0=83 = C 生产计划不用改变。应用二：自来水输送问题某市有甲，乙，丙，丁四个居民区，自来水由A, B, C三个水库供应。四个区每天必须的基本生活用水分别为30，70，10，10千吨，但三个水库每天最多只能分别供应50，60，50千吨自来水。由于地理位置的差别，自来水公司从各个水库向各区送水所付出的引水管理费不同（如下表，其中C水库与丁区间无输水管道），其他管理费均为450元、千吨。各区用户每千吨收费900元。此外，各区用户都向公司申请了额外用水量，分别为每天50，70，20，40千吨。引水管理费（元、千吨）甲乙丙丁A160130220170B140130190150C190230200/（1） 问公司应如何分配供水量，才能获利最多？（2） 若水库供水量都提高一倍，公司利润可增加到多少？解：问题（1）问题分析总供应量：50+60+50=160总需求量：120+180=300“产”max Z=72000-24100=47900(元)问题（2）问题分析总供应量：320总需求量：300所以要虚拟一个居民区戊，它的生活用水和额外用水总量为20千吨。甲、乙、丙、丁四个居民区都可以看作两个厂对待。分析见上一问。这样得到下面的产和单位饮水管理费表销平衡表：产地水库/居民区甲1甲2乙1乙2丙1丙2丁1丁2戊供应量（千吨）ABC100120100居民用水（千吨）305070701020104020320/320引水管理费（元/千吨）甲1甲2乙1乙2丙1丙2丁1丁2戊A1601601301302202201701700B1401401301301901901501500C190190230230200200MM0建立数学模型设 xij 分别表示水库A,B,C(i=1,2,3)向各居民区 (j=1,2,3,4,5,6,7,8,9)的供水量。设Z表示自来水公式的获利，则有下列模型：max Z=900*300-450*300-i=1,j=1i=4,j=8CijXij=135000-i=1,j=1i=4,j=8CijXij即求 min Z=i=1,j=1i=4,j=8CijXij 其中Cij=160170M0求解数学模型用表上作业法得到初始方案和最终方案为产地水库/居民区甲1甲2乙1乙2丙1丙2丁1丁2戊供应量（千吨）A7030100120100B3050400C1021040居民用水（千吨）305070701020104020产地水库/居民区甲1甲2乙1乙2丙1丙2丁1丁2戊供应量（千吨）A7030100120100B30401040C3020102020居民用水（千吨）305070701020104020即A运给乙100千吨，B运给甲30千吨，乙40千吨，丁50千吨，C运送给甲50千吨丙30千吨验证数学规划的合理性与正确性 易知此解完全符合题意 即A运给乙100千吨，B运给甲30千吨，乙40千吨，丁50千吨，C运送给甲50千吨丙30千吨得minZ=130*100+140*30+130*40+150*50+190*50+200*30=45400(元)=max Z=135000-45400=89600(元)=活力增加89600-47900=41700（元）三对数学规划这门课的认识与理解 数学规划即是在给定资源条件下，如何设计和运行一个系统的最优化技术，他的核心就是建立和运用模型。对于模型的运用最重要的在于将非标准的模型转化为标准的模型，模型转化时需要注意（1）目标函数的最大化最小(2)约束方程的常数项为负数时方程两边要同时乘以1（3）松弛变量、剩余变量、偏差变量的引入问题（4）决策变量的有、无约束性。 对于求解数学模型，最常用的方法有：图解法、单纯形法、对偶对偶单纯形法、表上作业法等。其中，单纯性发的基本思路是从一个顶点开始，在顶点中逐步选优，使目标函数达到最优或者判定规划问题无解，主要内容是基变量的换入换出和检验数的判断；表上作业法的基本思路与单纯形法的求解思路完全一致，也是先找出一个可行法案，然后确定的判别准则对初始方案进行检查、调整、改进直到找到最优方案，它的核心是建立产销平衡表，对于初始可行法案一般方法用最小元素法或伏格尔法，而最优解的判别一般用闭回路法或位势法。通过对这门课的学习，我知道数学