《数学规划》实验指导书.doc

数学规划实验指导书(第二版) 南昌航空大学数信学院邱根胜编2010年8月目录实验1、Lingo求解线性规划问题.4实验2、Lingo求解运输问题和整数规划问题.10实验3：Lingo求解目标规划问题. 15实验4、Lingo求解非线性规划问题.22实验5、Lingo求解动态规划问题.30实验6、编制线性规划计算程序.37实验7、利用Matlab (C或VB)编写一维搜索计算程序.38实验8、编制无约束优化计算程序39实验9、数学规划综合性实验 42 附录1：最优化算法Matlab参考程序.49(一).用Matlab编写0.618法计算程序.49(二).用Matlab编写最速下降法的计算程序.52(三).用Matlab编写共轭梯度法计算程序.54附录2：LINGO软件基本用法.58参考文献95一、授课对象 四年制本科数学与应用数学、信息与计算科学专业。二、课程类型专业必修课。三、实验的性质、目的与任务1、实验性质数学规划实验是一门专业基础课实验。要求学生通过本课程的实验，掌握最优化中的基本算法、了解最优化在工程、管理中的应用，使学生的计算机编程能力得到进一步训练。 2、实验的目的培养与提高学生数学软件的应用能力、自学能力、建模能力、自学能力，以及计算机编程能力。3、实验的任务通过编写几个基本的最优化算法的计算机程序，以及利用数学软件求解实际优化建模问题，加深对优化算法的理解，了解最优化在实际问题中的应用。四、实验内容与学时分配 五、实验内容与实验要求实验编号实 验 内 容实验学时实验类型备注1实验一、利用C(Matlab或VB)编写一维搜索计算程序2设计性必选2实验二、利用数学软件求解数学规划模型2验证性3实验三、编制线性规划计算程序4设计性4实验四、编制无约束优化计算程序2设计性5实验五、利用数学软件求解动态规划模型2综合性6实验六、数学规划综合性实验4综合性合 计16其中必修学时：12H实验一：利用C(Matlab或VB)编写一维搜索计算程序本实验是设计性实验，主要运用循环结构中的while、for等知识点，由学生自行选择（Matlab或VB）等语言编写一个一维搜索算法，主要考核学生对算法的理解能力及程序设计能力。实验要求：1、理解0.618法、进退法、二次插值法等算法；2、利用C(Matlab或VB) 编写一维搜索计算程序。实验二 利用数学软件求解数学规划模型实验要求：1、了解Matlab及Lingo使用方法；2、利用Matlab及Lingo求解数学规划模型。实验三、编制线性规划计算程序实验要求：1、理解线性规划单纯形方法的原理；2、利用Matlab编写线性规划的计算程序；3、利用上述计算程序计算线性规划实际案例。实验四、编制无约束优化计算程序实验要求：1、理解理解无约束方法中的最速下降法、共轭梯度法、牛顿法、拟牛顿法等方法；2、利用Matlab或C语言等语言编写最速下降法、共轭梯度法、牛顿法、拟牛顿法等方法的计算程序；3、给出所编程序的数值实验结果。实验五、利用数学软件求解动态规划模型实验要求：1、熟悉动态规划的原理；2、了解动态规划的应用；3、能利用数学软件Lingo或Matlab求解动态规划模型。实验六、数学规划综合性实验实验要求：1、 从给定的一些实际问题中选取一个问题，建立数学模型。2、 利用数学软件进行求解，并对结果进行分析，得出结论。注：从16学时的实验内容中选择12学时的实验内容，其中至少有一个设计性或综合性实验。六、主要参考书1 运筹学教材编写组，运筹学(第三版)，清华大学出版社，2005。2 谢金星，薛毅编著，优化建模与LINDO/LINGO，清华大学出版社,2005。3 胡运权主编，运筹学教程，清华大学出版社，2007年。4 姜启源,邢文训,谢金星等，大学数学实验，清华大学出版社，2005。 实验一、利用Lingo求解线性规划问题 一、实验目的了解Lingo软件求解线性规划的用法，并进行灵敏度分析，能利用线性规划求解实际问题。二、实验例题例题1.1 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低.试建立线性规划模型并求解.季度生产能力生产成本需求量13015.02024014.02032015.33041014.810解：设第j季度生产吨，j=1,2,3,4.则有第一季度要满足需求：；第二季度满足需求：；类似得到第三、第四季度的约束为：生产能力约束：;生产和贮存费用：第一季度：15x1第二季度: 14x2+0.2(x1-20)第三季度: 15.3x3+0.2(x1+x2 -40)第四季度: 14.8x4 +0.2(x1+x2 +x3 -70 )从而得到数学模型为：min s.t. x1+x2 40 , x1+x2 +x3 70 x1+x2 +x3 + x4 =80, 20x130,0 x240,0 x320,0 x410.Lingo计算程序为：min=15.6*x1+14.4*x2+15.5*x3+14.8*x4-26;x1+x240;x1+x2+x370;x1+x2+x3+x4=80;x120;x130;x240;x320;x410;end计算结果为： Global optimal solution found at iteration: 7 Objective value: 1165.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 40.00000 0.000000 X3 10.00000 0.000000 X4 10.00000 0.000000 Row Slack or Surplus Dual Price 1 1165.000 -1.000000 2 20.00000 0.000000 3 0.000000 -0.7000000 4 0.000000 -14.80000 5 0.000000 -0.1000000 6 10.00000 0.000000 7 0.000000 1.100000 8 10.00000 0.000000 9 0.000000 0.000000即最优方案为第1、2、3、4季度分别生产20、40、10、10（吨），可使费用最少，又满足需求。例1.2一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题： 1） 若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？ 2） 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？ 3） 由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？模型代码如下：max=72*x1+64*x2;x1+x2=50;12*x1+8*x2=480;3*x1=100;求解这个模型并做灵敏性分析，结果如下。 Global optimal solution found at iteration: 0 Objective value: 3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable AllowableVariable Coefficient Increase Decrease X1 72.00000 24.00000 8.000000 X2 64.00000 8.000000 16.00000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 50.00000 10.00000 6.666667 3 480.0000 53.33333 80.00000 4 100.0000 INFINITY 40.00000结果告诉我们：这个线性规划的最优解为x1=20，x2=30，最优值为z=3360，即用20桶牛奶生产A1, 30桶牛奶生产A2，可获最大利润3360元。输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息，下面结合题目中提出的3个附加问题给予说明。 3个约束条件的右端不妨看作3种“资源”：原料、劳动时间、车间甲的加工能力。输出中Slack or Surplus给出这3种资源在最优解下是否有剩余：原料、劳动时间的剩余均为零，车间甲尚余40（公斤）加工能力。 目标函数可以看作“效益”，成为紧约束的“资源”一旦增加，“效益”必然跟着增长。输出中DUAL PRICES 给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量：原料增加1个单位（1桶牛奶）时利润增长48（元），劳动时间增加1个单位（1小时）时利润增长2（元），而增加非紧约束车间甲的能力显然不会使利润增长。这里，“效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，车间甲的影子价格为零。读者可以用直接求解的办法验证上面的结论，即将输入文件中原料约束milk）右端的50改为51，看看得到的最优值（利润）是否恰好增长48（元）。用影子价格的概念很容易回答附加问题1）：用35元可以买到1桶牛奶，低于1桶牛奶的影子价格48，当然应该作这项投资。回答附加问题2）：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2元。 目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？这个问题不能简单地回答。上面输出给出了最优基不变条件下目标函数系数的允许变化范围：x1的系数为（72-8，72+24）=（64，96）；x2的系数为（64-16，64+8）=（48，72）。注意：x1系数的允许范围需要x2系数64不变，反之亦然。由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。用这个结果很容易回答附加问题3）：若每公斤A1的获利增加到30元，则x1系数变为303=90，在允许范围内，所以不应改变生产计划，但最优值变为9020+6430=3720。 下面对“资源”的影子价格作进一步的分析。影子价格的作用（即在最优解下“资源”增加1个单位时“效益”的增量）是有限制的。每增加1桶牛奶利润增长48元（影子价格），但是，上9 面输出的CURRENT RHS 的ALLOWABLE INCREASE 和 ALLOWABLE DECREASE 给出了影子价格有意义条件下约束右端的限制范围： milk）原料最多增加10（桶牛奶），time）劳动时间最多增加53（小时）。现在可以回答附加问题1）的第2问：虽然应该批准用35元买1桶牛奶的投资，但每天最多购买10桶牛奶。顺便地说，可以用低于每小时2元的工资聘用临时工人以增加劳动时间，但最多增加53.3333小时。 需要注意的是：灵敏性分析给出的只是最优基保持不变的充分条件，而不一定是必要条件。比如对于上面的问题，“原料最多增加10（桶牛奶）”的含义只能是“原料增加10（桶牛奶）”时最优基保持不变，所以影子价格有意义，即利润的增加大于牛奶的投资。反过来，原料增加超过10（桶牛奶），影子价格是否一定没有意义？最优基是否一定改变？一般来说，这是不能从灵敏性分析报告中直接得到的。此时，应该重新用新数据求解规划模型，才能做出判断。所以，从正常理解的角度来看，我们上面回答“原料最多增加10（桶牛奶）”并不是完全科学的。三、实验任务问题1-1:利用Lingo软件求解下列问题(1)S t.(2) st.问题1-2： 建立下列问题的线性规划模型并求解：某厂生产A，B，C三种产品，每件产品消耗的原料和设备台时如表1-1所示：表1-1产品ABC资源数量原料单耗机时单耗22.5335620002600利润101420另外，要求三种产品总产量不低于65件，A的产量不高于B的产量。试制定使总利润最大的模型，并求解。问题1-3：某部门在今后5年内给下列项目投资。已知项目A：从第一年到第 四年每年年初需要投资，并于次年末回收本利115%；项目B：第三年年初需要投资，到第五年末能回受本利 125%，但规定最大投资不得超过4万元； 项目C：第二年年初需要投资，到第五年末回收本利140%，但规定最大投资不得超过3万元项目D：五年内每年年初可购买公债，于当年末归还，并加利息6%。该部门现有10万元，问他应如何确定每年给这些部门的每年的投资额，使得到第五年末拥有的资金本利总额最大？问题1-4： 建立下列问题的线性规划模型并求解：某公司打算利用具有下列成分（见表1-2）的合金配制一种新型合金100公斤，新合金含铅，锌，锡的比例为3：2：5。表1-2合金品种12345含铅%含锌%含锡%306010102070502030101080501040单价（元/kg）8.56.08.95.78.8如何安排配方，使成本最低？问题1-5（生产计划问题） 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表 1-3. 若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低. 试建立线性规划模型.表1-3季度生产能力（吨）生产成本（万元/吨）需求量（吨）13015020240140203201533041014810问题1-6某快餐店坐落在一个旅游景点中，这个旅游景点远离市区，平时游客不多，而在每个星期六游客猛增，快餐店主要为旅客提供低价位的快餐服务，该快餐店雇佣了两名正式职工，正式职工每天工作8 小时，其余工作由临时工来担任，临时工每班工作4 小时，在星期六该快餐店从上午11点开始营业到下午0时关门。根据游客就餐情况，在星期六每个营业小时所需职工数（包括正式工和临时工）如表1-4所示。表1-4时间所需职工数时间所需职工数11:00-12:00917:00-18:00612:00-13:00918:00-19:001213:00-14:00919:00-20:001214:00-15:00320:00-21:00715:00-16:00321:00-22:00716:00-17:003已知一名正式职工11点开始上班，工作4个小时后，休息1个小时，而后再工作4个小时；另一名正式职工13点开始上班，工作4个小时后，休息1个小时，而后再工作4个小时，又知临时工每小时的工资为4 元。（1） 在满足对职工需求的条件下，如何安排临时工的班次，使得用临时工的成本最小？（2） 这时付给临时工的工资总额为多少？一共需要安排多少临时工的班次？请用剩余变量来说明应该安排一些临时工的3 小时工作时间的班次，可使得部成本更小。（3） 如果临时工每班工作时间可以是3 小时，也可以是4 小时，那么应如何安排临时工的班次，使得用临时工的总成本最小？这样比（1）能节省多少费用？这时要安排多少临时工班次？四、实验报告要求对于上述问题，根据实验内容进行实验，要求写出实验报告。实验报告包含下列几个部分：1、实验目的；2、问题；3、数学模型；4、Lingo求解程序；5、计算结果；6、结论；7、心得体会。实验二、Lingo求解运输问题和整数规划问题一、实验目的了解Lingo软件求解线性规划的用法，了解LINGO软件中集合和一些常用函数的用法，建立实际问题的线性规划模型，借助LINGO软件能求解实际问题。二、实验例题例2.1 使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。单位 销地运价产地B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338解:设第I个产地运到第j个销地的单位运价为cij ,第I个产地运到第j个销地的运量为,第I个产地的产量为(I=1,2,6),第j个销地的销量为(j=1,2,8),运费为z,则此问题的数学模型为如下的数学规划问题:使用LINGO软件，编制程序如下：model:!6发点8收点运输问题;sets: chandi/A1.A6/: a; xiaodi/B1.B8/: d; links(chandi,xiaodi): c, x;endsets!目标函数; min=sum(links(i,j): c(i,j)*x(i,j);!需求约束; for(xiaodi(J): sum(chandi(I): x(I,J)=d(J);!产量约束; for(chandi(I): sum(xiaodi(J): x(I,J)1;x1+x2+x61;x3+x41;x3+x4+x51;x4+x5+x61;x2+x5+x61;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);结果为：Global optimal solution found at iteration: 0 Objective value: 2.000000 Variable Value Reduced Cost X1 0.000000 1.000000 X2 1.000000 1.000000 X3 0.000000 1.000000 X4 1.000000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000即只要在地区2和4个建一个消防站即可满足要求。三、实验任务问题2-1 某食品公司经销的主要产品之一是糖果，它下面设有三个加工厂A1、A2、A3，每天要把生产的糖果运往B1、B2、B3、B4 四个门市部销售，各厂的产量（吨/天）各门市部的销量（吨/天），以及各厂到各销售门市部的运价（元/吨），如表21所示.问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少？表21 门市部加工厂B1B2B3B4产量A162355A278542A339273销量2134问题2-2: 1，2，3三个城市每年需分别供应电力320，1，2，3三个城市每年需分别供应电力320，250和350单位，由，两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用（元）如下表2-2所示。由于需要量大于可供量，决定城市1的供应量可减少0单位30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案（将可供电量用完）。 表2-2 城市电站123151822212516问题2-3： 要把七种规格的包装箱装到两辆平板车上去，箱子的宽、高、相同，而厚度和重量不同。下表2-3给出了他们的厚度和重量及数量。表2-3第i种箱子1234567 厚度t（厘米）48.752.061.372.048.752.064.0重量w（千克）200030001000500400020001000数量n8796648每辆平板车有10.2米的地方用于装箱，载重40吨。由于货物的限制，对于第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的空间最小。问题2.4： 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。资源小号容器中号容器大号容器金属板（吨）248劳动力（人月）234机器设备（台月）123四、实验报告要求对于上述问题，根据实验内容进行实验，要求写出实验报告。实验报告包含下列几个部分：1. 实验目的；2. 问题；3. 数学模型；4. Lingo求解程序；5. 计算结果；6. 结论；7. 心得体会。实验三：Lingo求解目标规划问题 一、实验目的了解Lingo软件求解线性目标规划的用法，掌握目标规划的序贯式单纯形算法，了解LINGO中数据段中含有未知数据的编程方法，借助LINGO软件能利用目标规划求解实际问题。二、例题目标规划的一般模型为：常见的求解方法为序贯单纯形法，下面举例说明如何用Lingo软件求解。利用序贯式算法求解下列目标规划问题解：利用序贯单纯形算法。(1)先求第一级目标，Lingo程序为(exam021a.lg4)：min=dplus1;2*x1+x2+xs=11;x1-x2+dminus1-dplus1=0;x1+2*x2+dminus2-dplus2=10;8*x1+10*x2+dminus3-dplus3=56;计算结果(部分)为：Global optimal solution found at iteration: 1 Objective value: 0.000000 Variable Value Reduced Cost DPLUS1 0.000000 1.000000 X1 0.000000 0.000000 X2 0.000000 0.000000 XS 11.00000 0.000000目标函数为0，即第一级偏差为0。(2)求第二级目标，计算程序为(exam021b.lg4)：min=dminus2+dplus2;2*x1+x2+xs=11;x1-x2+dminus1-dplus1=0;x1+2*x2+dminus2-dplus2=10;8*x1+10*x2+dminus3-dplus3=56;dplus1=0;计算结果(相关)为： Global optimal solution found at iteration: 2 Objective value: 0.000000 Variable Value Reduced Cost DMINUS2 0.000000 1.000000 DPLUS2 0.000000 1.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 XS 6.000000 0.000000 DMINUS1 5.000000 0.000000 DPLUS1 0.000000 0.000000 DMINUS3 6.000000 0.000000 DPLUS3 0.000000 0.000000目标函数值仍为0，即第二级偏差为0。(3)求解第三级目标，计算程序为(exam021c.lg4)：min=dminus3;2*x1+x2+xs=11;x1-x2+dminus1-dplus1=0;x1+2*x2+dminus2-dplus2=10;8*x1+10*x2+dminus3-dplus3=56;dplus1=0;dminus2+dplus2=0;计算结果为： Global optimal solution found at iteration: 2 Objective value: 0.000000 Variable Value Reduced Cost DMINUS2 0.000000 1.000000 DPLUS2 0.000000 1.000000 X1 0.000000 0.000000 X2 5.000000 0.000000 XS 6.000000 0.000000 DMINUS1 5.000000 0.000000 DPLUS1 0.000000 0.000000 DMINUS3 6.000000 0.000000 DPLUS3 0.000000 0.000000得到满意解为：x1=0,x2=5,xs=6,dminus1=5,dminus3=6,其余等于0。上述过程虽然能给出目标规划问题的满意解，但需要连续编写若干个程序，在使用时很不方便。下面编写一个通用的LINGO程序，程序名为exam021.lg4。在程序中用到数据段未知数据的编程方法。model:sets:level/1.3/:p,z,goal;variable/1.3/:x;conA/1/:b;conNum/1.3/:g,dplus,dminus;cong(conNum,variable):C;conAb(conA,variable):A;obj(level,conNum):wplus,wminus;endsetsdata:p=? ? ?;goal=? ?