运筹学-数学规划.docx

中 国 地 质 大 学课程名称 数 学 建 模 报 告 教师姓名 学生姓名 学号 专业 所在院系 日期 目 录1问题重述21.1奶制品的加工与销售问题21.2自来水输送问题22问题分析22.1问题一的分析22.2问题二的分析23问题假设24定义与符号说明24.1问题一24.2问题二25问题一的求解25.1 模型的建立25.2 模型的求解与分析25.2.1 模型分析25.2.2 模型求解25.2.3基于模型的动态方案分析26问题二的求解26.1 模型1的建立26.2 模型1的求解与分析26.2.1模型1的分析26.2.2模型1的求解26.3 模型2的建立26.4 模型2的求解与分析26.4.1模型2的分析26.4.2模型2的求解27参考文献28课程总结2数学建模报告线性规划在数学建模中的应用摘要 本文运用线性规划中的单纯型法以及一种特殊的单纯型法表上作业法解决了这两个求最大值、最小值的线性数学模型。 对于问题一，首先引入生产A1、A2的牛奶桶数x1，x2作为决策变量，然后以此根据A1、A2每公斤的利润建立了求获利Z的目标函数；同时目标函数受三个约束条件的限制，由此可建立求获利最大值max Z 生产计划的线性数学模型。利用线性规划中的单纯型法便可求得最优的x1，x2 即最优生产计划。在此基础上，我们再结合线性规划中的影子价格和灵敏度分析理论，便可以很快地得到后续的几个动态问题方案。对于问题二，首先引入xij 作为决策变量，它表示i水库每天输送到j居民区的水量，然后以此建立求引水管理费Z的目标函数。同时目标函数受到水库的供应量限制，和各区的需求量限制。由此可建立求引水管理费最小值min Z送水方案的线性数学模型。最后将此特殊线性规划问题转换为运输问题进行求解，通过运输问题中的表上作业法可以求出最小的引水管理费，从而可以等价求出水库送水的最大获利。关键词： 线性规划 单纯型法 表上作业法 影子价格 灵敏度分析 运输问题1问题重述1.1奶制品的加工与销售问题 一奶制品加工厂用牛奶生产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.2自来水输送问题 某市有甲，乙，丙，丁四个居民区，自来水由A, B, C,三个水库供应。四个区每天必须的基本生活用水分别为30，70，10，10千吨，但三个水库每天最多只能分别供应50，60，50千吨自来水。由于地理位置的差别，自来水公司从各个水库向各区送水所付出的引水管理费不同（如下表，其中C水库与丁区间无输水管道），其他管理费均为450元/千吨。各区用户每千吨收费900元。此外，各区用户都向公司申请了额外用水量，分别为每天50，70，20，40千吨。引水管理费（元/千吨）甲乙丙丁A160130220170B140130190150C190230200/（1） 问公司应如何分配供水量，才能获利最多？（2） 若水库供水量都提高一倍，公司利润可增加多少？2问题分析2.1问题一的分析1.1（1）我们制定的生产计划要使每天获利最大，也就是要确定分别用多少桶牛奶生产A1和A2才能达到利润最大值。因此用于生产A1、A2的牛奶数目可看成线性规划中的决策变量，由此确定获利的目标函数。同时此题中的目标函数要受到原料牛奶供应、劳动时间、设备甲的加工能力这三个约束条件的限制；由此可建立最终的数学模型；1.1（2）（5）根据（1）中建立的数学模型及其求解，我们再结合对偶问题的基本性质，运筹学中的影子价格理论以及线性规划问题中的灵敏度分析相关原理便可分析得到后续问题的决策方案。2.2问题二的分析1.2.（1）从题知A、B、C三个水库的供应量总和为50+60+50=160吨，而甲乙丙丁四个居民区的基本用水和申请的额外用水量总和为120+180=300。需求大于供水量，因此我们可以虚拟一个水库D供水140吨，从而将此问题转换为供需平衡问题。此时三个水库收取的总费用为900(50+60+50)=144000元，其它管理费用为450(50+60+50)=72000元，而且都与供水方案无关，所以我们又可以将求获利最大问题，转换为求引水管理费最小的问题；1.2.（2）水库供应量翻倍后，供应量总和变为1602=320吨，而甲乙丙丁四个居民区的需求量不变仍为300吨。供水量大于需求，因此我们可以虚拟一个居民区戊，并且戊的需求量为20吨，从而将此问题转换为供需平衡问题。此时三个水库的收取的总费用为900300=270000元，其它管理费用为450300=135000元，而且都与供水方案无关，所以我们又可以将求获利最大问题，转换为求引水管理费最小的问题。3问题假设1假设A1，A2两种奶制品每公斤的获利是与它们各自产量无关的常数，每桶牛奶加工出A1，A2的数量和所需的时间是与它们各自的产量无关的常数；2假设A1，A2每公斤的获利是与它们相互间产量无关的常数，每桶牛奶加工出A1，A2的数量和所需的时间是与它们相互间产量无关的常数；3假设加工A1，A2的牛奶桶数可以是满足原料牛奶供应的任意非负整数；4假设A、B、C三个自来水库每天都能达到最大供水量；5假设甲乙丙丁四个居民区每天的基本生活用水量和额外申请的用水量保持不变；6假设引水管理费不会随着自来水的输送量而发生变化。 4定义与符号说明4.1问题一1. CB 基变量的价值系数2. XB 基变量3. b 限额系数4. j=cj-zj 变量的检验数5. cj 所有变量的价值系数6. xj 所有变量，其中j=1,2,3,4,57 i 线性规划中单纯形法的值其中i=1,2,38. B 基矩阵9. Yi* 线性规划模型的对偶问题的基解，其中i=1,2,34.2问题二1. X ,戊 必须满足的用水居民区，其中X为甲、乙、丙、丁2. Y” 额外需求的用水居民区，其中Y为甲、乙、丙、丁3. xij i水库输送到j居民区的水量，其中i=1,2,3,j=1,2,3,4.4. cij i水库输送到j居民区的引水管理费，其中i=1,2,3,j=1,2,3,4.5. ij=cij-ui+vj 变量 xij的检验数6. ui , vj 对应供求平衡问题的所有约束条件的对偶变量5问题一的求解5.1 模型的建立 在建立模型之前我们先构造符合题意的产销流程图：图5.1 3公斤A1 获利24元/公斤8小时12小时乙设备甲设备 一桶牛奶 获利16元/公斤4公斤A2由此可设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2，每天获利为Z元。则有x1桶牛奶可生产3x1公斤A1，获利243x1元，x2桶牛奶可生产4x2公斤A2，获利164x2元，故建立目标函数为： max Z=72x1+64x2 。并且由题中所给信息可以得到如下约束条件：原料牛奶供应：生产A1，A2的原料总量不得超过每天的供应的50桶，即有x1+x250；劳动时间：生产A1，A2的总加工时间不得超过每天工人总的劳动时间，即有12x1+8x2480；设备甲的工作能力：A1的产量要受设备甲每天的加工能力的限制，即有3x1100，而设备乙的加工能力没有限制；非负约束：x1, x2均不能为负值，即有 x10 ，x20。综上所述，可得该问题的数学模型如下所示： max Z=72x1+64x2 s.t x1 + x2 50 12x1+ 8x2 480 3x1 100 x1 , x2 0 5.2 模型的求解与分析5.2.1 模型分析 由于目标函数和约束条件是关于决策变量x1, x2的线性表达式，所以以上建立的数学模型可以看成运筹学当中的线性规划问题，因此可以用单纯形法去求解。为此我们首先在上述问题的约束条件中加入松弛变量x3，x4，x5 ，从而得到原模型的标准型如下：max Z=72x1+64x2+0x3+0x4+0x5s.t x1+x2+x3 =5 12x1+8x2 +x4 =48 3x1 + x5=100 x1, x2, x3, x4, x5 0 5.2.2 模型求解 用目标函数进行计算时，见表5-1。因本题是求max，所以用所有的j=cj-zj0 来判别目标函数是否实现了最大化。表5-1 cj7264000iCBXBbx1x2x3x4x50x350111005040100/30x44801280100x510030001cj-zj72640000x350/301101/350/3100x4800801-472x1100/310001/3cj-zj06400-240x320/30011/81/64010064x2100101/81/272x1100/310001/3cj-zj000-880x5400063/4164x2300131/4072x12010-2 1/40cj-zj00-48-20由于最终单纯形表中的检验数都满足 cj-zj0 ，故得到了最优解为： X*=(20,30,0,0,0)T目标函数的最优值为: Z*=6430+7220= 3360元 即每天用20桶牛奶生产A1，用30桶牛奶生产A2，获利最大且最大利润为3360元。 5.2.3基于模型的动态方案分析 根据问题一的（1）的解，我们再结合对偶问题的基本性质，运筹学中的影子价格理论，以及线性规划问题中的灵敏度分析相关原理便可分析得到1.1.（2）（5）的决策方案。 由对偶问题的基本性质可知，表5-1中最后一行 x3, x4, x5的检验数对应其对偶问题的一个基解，即Y1*,Y2*,Y3*=48,2,0 再由运筹学中的影子价格理论，对偶问题的基解Y1*=48意味着，其它条件不变的情况下，若买进一桶牛奶，该加工厂安排生产可多获利48元。33元可以买到一桶牛奶用于加工，则可以赚取48-33=15元的差价，所以应该买。 由表5-1易知基矩阵的逆为：B-1= 6 -0.75 13 -0.25 0 -20 0 .25 0 设最初的原料牛奶供应量为b1=50 桶，若它的供应量变为b1+b1 , 则为了保证最终的检验数即最优基保持不变，新的最优解的值可允许b1的变化范围如下可求： B-1b+B-1b100=403020+63-2 b1000 解得 -20/3b110这说明了若要买进牛奶，则每天最多只能买10桶。 同利用影子价格，可知Y2*=2意味着在其它条件不变的情况下，每天增加1小时工人劳动时间，该加工厂安排生产可多获利2元。因此若聘用临时工人，每天的工资最多为2元才能保证工厂不亏损。 设每桶牛奶制成 A1可获利c1=243=72 元，若每桶牛奶制成A1的利润变为c1+c1，由线性规划目标函数关于基变量价值系数变化的理论可知，若要保持最终的生产方案即最优解不变，则c1的变化范围如下可求：这时表5-1的最终计算表如下所示。表5-2cj72+c164000CBXBbx1x2x3x4x50x5400063/4164x2300131/4072+c1x12010-21/40cj-zj002c1-48-2-14 c10 从表5-2可见有 2c1-480 和-2-1/4c10 由此可得-8c124 , 故有64c196，即x1的价值系数可以在64,96之间变化，而不影响原来的生产计划。而A1的获利增加到30元/公斤，相应的价值系数变为c1=303=9096, 在允许范围之内，所以此时不需要改变生产计划。6问题二的求解6.1 模型1的建立首先我们引入决策变量 xij ，它表示i水库每天输送到j居民区的水量，其中i=1,2,3 ,j=1,2,3,4。由于C水库与丁区间无输水管道，所以x34=0。又由题中给出的表，我们可以得到关于引水管理费的目标函数： min Z=160x11+130x12+220x13+170x14+140x21+130x22+ 190x23+150x24+ 190x31+230x32+200x33 同时决策变量应该满足两类约束条件限制，一类是水库的供应量限制，另一类是各区的需求量限制。 由于供小于基本需求和额外需求总和，即供需，故有如下供应量限制：A水库供给四个区的总供水量应不超过A水库的日供应量100千吨即有x11+x12+x13+x14100B水库供给四个区的总供水量应不超过B水库的日供应量120千吨即有 x21+x22+x23+x24120C水库供给四个区的总供水量应不超过C水库的日供应量100千吨即有 x31+x32+x33100供应量翻倍后，完全可以满足居民的基本需求和额外需求，故有如下需求量限制：又有2.2中题目分析可知，要求获利最多的供水方案等价于甲区： x11+x21+x31=80乙区： x12+x22+x32=140丙区： x13+x23+x33=30丁区： x14+x24 =50最后还要满足非负约束，即：xij0。求引水管理费最低的决策方案，所以综上可建立求最低引水管理费目标函数的数学模型：min Z=160x11+130x12+220x13+170x14+140x21+130x22+190x23+ 150x24 + 190x31+230x32+200x33 x11+x12+x13+x1450 x21+x22+x23+x2460 x31+x32+x33 50x11+x21+x31 =80 x12+x22+x32 =140x13+x23+x33 =30 x14+x24 =50 xij0,i=1,2,3;j=1,2,3,46.4 模型2的求解与分析6.4.1模型2的分析 观察易知此模型和模型1一样是一类特殊的线性规划问题，可以看成一个运输问题进行求解。而运输问题的数学模型具有如下特征：方程组中所有变量的系数皆为1和0；任何一个变量xij在前m个方程中以系数1出现一次，在后n个方程也以系数1出现一次。对于本题产大于销的情况，我们需要在产销平衡表中增加一个假想的销地j=n+1，该地销量为i=1mai-j=1nbj，在单位运价表上令从该假想产地到各销地的运价ci,n+1=0，同样可以转化为一个产销平衡问题。6.4.2模型2的求解 三个水库到居民区的引水管理费在表6-1中已给出。同模型1一样，这也是一个“产销不平衡的运输问题”，总供应量为320千吨，四个地区的最低需求为120千吨，最高需求为300千吨，故均能满足。为了达到平衡，在产销平衡表中增加一个假想的居民区戊，其日需水量为320-300=20千吨。而对于三个水库到戊的引水管理费我们均设为0。这样，可以写出这个问题的产销平衡表和单位运价表，如下表：表6-7居民区水库甲甲”乙乙”丙丙”丁丁”戊供应量(千吨)A1601601301302202201701700100B1401401301301901901501500120C190190230230200200MM0100需求量(千吨)305070701020104020根据表上作业中的伏格尔法，得初始可行解如下表：表6-8居民区水库甲甲”乙乙”丙丙”丁丁”戊供应量(千吨)A7030100B3050400120C1020401020100需求量(千吨)305070701020104020再利用表上作业中的位势法求变量检验数得下表：表6-9居民区水库甲甲”乙乙”丙丙”丁丁”戊uiA2020(0)(0)M-130M-1302020M-1500B(0)(0)0(0)M-160M-160(0)0M-1500C200-M200-M250-M250-M(0)(0)(0)(0)(0)M-150vj140140130130350-M350-M150150150-M此中出现了负的检验数： 31=200-M，3