最优化问题最新课件

1、第四章 最优化问题主讲：陈元安电子信箱：商丘职业技术学院 爱因斯坦的一句名言： 想象力比知识更重要！因为知识是有限的，而想象力包括世界的一切，是知识的源泉。要 点历年回顾:92A题施肥效果分析 回归分析 数据拟合92B题实验数据分解 离散模型、组合最优化93A非线性交调的频率设计 拟合、规划 93B足球队排名 图论、层次分析、整数规划 94A逢山开路 图论、插值、动态规划 94B锁具装箱问题 图论、组合数学 95A飞行管理问题 非线性规划、线性规划 95B天车与冶炼炉的作业调度 动态规划、排队论、图论 96A最优捕鱼策略 微分方程、优化 96B节水洗衣机 非线性规划 97A零件的参数设计 非线

2、性规划 97B截断切割的最优排列 随机模拟、图论 98A一类投资组合问题 多目标优化、非线性规划 98B灾情巡视的最佳路线 图论、组合优化 99A自动化车床管理 随机优化、计算机模拟 99B钻井布局 0-1规划、图论 00A DNA序列分类 模式识别、Fisher判别、 人工神经网络 00B钢管订购和运输 组合优化、运输问题 01A血管三维重建 曲线拟合、曲面重建 01B 公交车调度问题 多目标规划 02A车灯线光源的优化 非线性规划 02B彩票问题 单目标决策 03A SARS的传播 微分方程、差分方程 03B 露天矿生产的车辆安排 整数规划、运输问题04A奥运会临时超市网点设计 统计分析、

3、数据处理、优化04B电力市场的输电阻塞管理 数据拟合、优化 05A长江水质的评价和预测 预测评价、数据处理 05B DVD在线租赁 随机规划、整数规划 06A出版社书号问题 整数规划、数据处理、优化 06B Hiv病毒问题 线性规划、回归分析解法规划问题图论差微分方程数据拟合模拟处理优化数据分析理论其它（排队运输离散）相关赛题93A,93B94A,95A95B,96B97A,98A99B,01B02A,03B06A,06B07B,09B10A93B94A94B95B97B98B99B07B96A03A07A08A09A92A,93A97B,99A01A,04A04B,05A06A,07A08B

4、,10A10B92B,96A98A,98B99A,00B 02B,04A04B,06A07A,08A93B04A09A09B10B92B94A94B95B00A00B合计1785131266赛题发展的特点： 1. 对选手的计算机能力提出了更高的要求：赛题的解决依赖计算机，题目的数据较多，手工计算不能完成，如03B，某些问题需要使用计算机软件，01A。问题的数据读取需要计算机技术，如00A（大数据），01A（图象数据，图象处理的方法获得），04A（数据库数据，数据库方法，统计软件包）。计算机模拟和以算法形式给出最终结果。 2. 赛题的开放性增大解法的多样性，一道赛题可用多种解法。开放性还表现在对

5、模型假设和对数据处理上。 3. 试题向大规模数据处理方向发展 4. 求解算法和各类现代算法的融合，5.更关注于当年的实事问题eg：04A奥运会临时超市网点设计，07B 乘公交，看奥运，10B 2010年上海世博会影响力的定量评估等；引言4.1 线性规划模型 4.2 整数规划模型4.3 二次规划模型4.4 非线性规划模型4.5 应用案例：抢渡长江问题4.6 应用案例练习4.7 最优化软件规划模型的应用极其广泛，其作用已为越来越多的人所重视.随着计算机的逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、创造的价值无法估量. 在数模竞赛过程中，规划模

6、型是最常见的一类数学模型. 从92-2011年全国大学生数模竞赛试题的解题方法统计结果来看，规划模型共出现了16次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解. 最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为最优方案，搜索最优方案的方法，称为最优化方法。这种方法的数学理论，称为最优化理论。最优化方法已广泛应用于空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、经济管理等等领域。最优化方法包括的内容很广泛，如线性规划、非线性规划、整数规划、动态规划、多

7、目标规划、组合优化等等。运用最优化方法解决最优化问题的一般方法步骤如下：前期分析：分析问题，找出要解决的目标，约束条件，并确立最优化的目标。定义变量，建立最优化问题的数学模型，列出目标函数和约束条件。针对建立的模型，选择合适的求解方法或数学软件。编写程序，利用计算机求解。对结果进行分析，讨论诸如：结果的合理性、正确性，算法的收敛性，模型的适用性和通用性，算法效率与误差等。线 性 规 划某豆腐店用黄豆制作两种不同口感的豆腐出售。制作口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购

8、入9千克一级黄豆和8千克二级黄豆。问：应如何安排制作计划才能获得最大收益。一、问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划，使得售出各种豆腐能获得最大收益。二、模型假设1假设制作的豆腐能全部售出。2假设豆腐售价无波动。变量假设： 设计划制作口感鲜嫩和厚实的豆腐各x1千克和 x2千克，可获得收益R元。目标函数：获得的总收益最大。 总收益可表示为： 受一级黄豆数量限制： 受二级黄豆数量限制： 综上分析，得到该问题的线性规划模型 s.t.LINGO程序：max=10*x1+5*x2;0.3*x1+0.4*x2=9;0.5*x1+0.2*x2=8;4.1、线性规划

9、模型 线性规划模型是所有规划模型中最基本、最例1.（食谱问题）设有 n 种食物，各含 m 种营养素，第 j 种食物中第 i 种营养素的含量为 aij , n 种食物价格分别为c1, c2, , cn，请确定食谱中n 种食物的数量x1, x2, , xn，要求在食谱中 m 种营养素简单的一种. 4.1 线性规划模型的基本形式 的含量分别不低于b1, b2, , bm 的情况下，使得总总的费用最低. 首先根据食物数量及价格可写出食谱费用为 其次食谱中第 i 种营养素的含量为 因此上述问题可表述为： 解线性规划的数学模型max z = S.T线性规划、线性规划的可行解，最优解的概念线性规划一般可写作

10、min(or max) f=s.t. 线性规划问题还可以用矩阵表示 min f= s.t Ax b, x0其中f被称作目标函数，目标函数下的等式或不等式被称作约束条件， A=,b= 一组满足约束条件的变量 的值称为一组可行解。 可行解的集合称为可行解域，或可行解空间。 线性规划问题也就是在可行解域上寻找使目标函数取得极小（或极大）值的可行解，称之为最优解。 针对标准形式的线性规划问题，其解的理论分析已经很完备，在此基础上也提出了很好的算 单纯形方法是线性规划问题的最为基础、也法单纯形方法及其相应的变化形式（两阶段4.2 线性规划模型的求解 法，对偶单纯形法等）. 是最核心的算法。它是一个迭代算

11、法，先从一个特殊的可行解（极点）出发，通过判别条件去判断该可行解是否为最优解（或问题无界），若不商丘职业技术学院生产计划问题线性规划模型商丘职业技术学院 2x1 + x2 8 s.t . x1 3 x2 4 x1，x2 0 max f= 5x1 +2x2 求最大利润三种材料量的限制生产量非负线性规划模型商丘职业技术学院运输问题线性规划模型商丘职业技术学院解：假设费用与运输量和距离成正比。 设A1,A2调运到三个粮站的大米分别为x1，x2， x3， x4， x5， x6吨。题设量可总到下表：线性规划模型商丘职业技术学院结合存量限制和需量限制得数学模型：线性规划模型商丘职业技术学院程序编写mode

12、l:optmin=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 ;st1x11+x12+x134 ;st2x21+x22+x232 ;st4x12+x224 ;st5x13+x235 ;end运行结果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 5 Variable Value Reduced Cost X11 2.000000 0.000000 X12 0.000000 28.00000 X13 2.000000 0.000000 X21

13、 0.000000 2.000000 X22 4.000000 0.000000 X23 3.000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.00000模型标准化 程序编写MODEL:TITLE 调运大米的运输问题程序; !定义集合段; SETS: HANG/1.5/:B;!定义矩阵的行; LIE/1.11/:C,

14、X;!定义矩阵的列以及变量; XISHU(HANG,LIE):A;!定义约束的系数矩阵; ENDSETS !定义数据段; DATA: A= 1 1 1 0 0 0 1 0 0 0 0!系数矩阵赋值; 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 -1 0 0 0 1 0 0 1 0 0 0 0 -1 0 0 0 1 0 0 1 0 0 0 0 -1; C= 12 24 8 30 12 0 24 0 0 0 0 0;!目标函数的系数; B= 4 8 2 4 5;!约束的右端项; ENDDATA !标准形式的目标函数的矩阵形式; OBJMIN=SUM(LIE:C*X)

15、; FOR(HANG(I):YUESHU SUM(LIE(J):A(I,J)*X(J)=B(I);END程序编写 推荐模型MODEL:TITLE 调运大米的运输问题程序3;!定义集合段;SETS:LIANGKU/1.2/:A;!定义粮库的集合;LIANGZHAN/1.3/:B;!定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离;ENDSETSDATA:!粮库到粮站的距离;C= 12 24 8 30 12 24;!粮库的限量;A=4 8 ;!粮站的限量;B=2 4 5;ENDDATAOBJMIN=SUM(YULIANG:C*X);!粮库上限的约束;F

16、OR(LIANGKU(I):LK SUM(LIANGZHAN(J):X(I,J)B(J);END 程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序； m个产地A1,Am联合供应n个销地B1,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?一般运输问题总运价产量限制需量限制运量非负线性规划模型假设产销平衡: 在很多实际问题中,解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题.线性规划模型2010年塔

17、里木大学数学建模竞赛C题甲、乙两处分别有70吨和55吨物资要外运，A、B和C三点各需要物资34吨、40吨和50吨。运送时，物资可以直接运达目的地，也可以经某点转运。乙010100甲乙甲发点收点距离乙12151410甲BA发点收点距离C12001280CBA发点收点距离ABC14111014甲A B C 乙A B C甲乙首先确定各发点到各收点的最短距离；这样就把网络流问题化为了运输问题。model:SETS: CITIES /jia,yi,A,B,C/: L; !属性L(i)表示城市甲到城市i的最短路线的路长; ROADS(CITIES, CITIES)/ !派生集合ROADS表示的是网络中的道

18、路（弧）; jia,yi jia,A jia,B jia,C yi,jia yi ,A yi ,B yi ,C !由于并非所有城市间都有道路直接连接，所以将弧具体列出; A,jia A,yi A,B A,C B,jia B,yi B,A B,C C,jia C,yi C,A C,B/: d; !属性d( i, j) 是城市i到j的直接距离（已知）;ENDSETSDATA: d = 10 10 14 12 10 15 12 0 !改乙到C为10; 10 15 14 11 14 12 10 4 12 0 8 12 ; L= 0, , , , ; !先求L(jia)，后改为L(yi);ENDDATA

19、 FOR( CITIES( i)|i#ne#index(jia): !这行中index(jia)可以直接写成1; L( i) = MIN( ROADS( j, i): L( j) + D( j, i); ); !这就是前面写出的最短路关系式;end 设有n件工作B1, B2, Bn,分派给n人A1, A2, An去做,每人只做一件工作且每件工作只派一个人去做,设Ai完成Bj的工时为cij,问应如何分派才能完成全部工作的总工时最少.每件工作只派1人每个人只派做1件变量xi只取0和1,故建立的模型也称0-1规划.分派问题线性规划模型选址问题线性规划模型 现要做100套钢架,用长为2.9m、2.1m

20、和1.5m的元钢各一根,已知原料长7.4m,问如何下料,使用的原材料最省?分析:下料方式：最省：1.所用刚架根数最少；2.余料最少下料问题线性规划模型原料截成所需长度的根数下料方法所需根长2.9m211100002.1m021032101.5m10130234剩余料头0.10.30.901.10.20.81.4线性规划模型不同方法截得每种根长的总数至少100例3,4中的此例的变量xi只取正整数,故建立的模型也称整数规划.0-1规划是整数规划的特殊情形.线性规划模型model:Title 钢管下料; Min=0.1*x1 + 0.3*x2 + 0.9*x3 + 0*x4 +1.1* x5 +0.

21、2* x6 + 0.8*x7 +1.4*x8; 2*x1 +x2 +x3 + x4 100; 2*x2 + 3*x3+ 3*x5 + 2*x6+x7 100; x1+ x3 +3*x4+ 2*x6 +3*x7+ 4*x8100;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);end 某公司生产某产品,最大生产能力为100单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元) 销售量1234 70 60 72 70 80 120 76 60求一生产计划,使 1)满足需求; 2)不超过生产能力;3)成本(生产成本与存储

22、费之和)最低.阶段生产问题线性规划模型 解:假定1月初无库存,4月底买完,当月生产的不库存,库存量无限制.第j+1个月的库存量第j+1个月的库存费共3个月的库存费到本月总生产量大于等于销售量4个月总生产量等于总销售量4个月总生产成本线性规划模型model:title 阶段生产;Sets: yuefen/1.4/:c,x,e,d; !设置集合;endsetsDATA:c= 70 72 80 76; d = 6000 7000 12000 6000;e=2 2 2 2;a=10000; ENDDATA min=sum(yuefen:c*x)+sum(yuefen(j)|j#lt#4: sum(yu

23、efen(i)|i#le#j: x-d)*e(j+1);for(yuefen(j)|j#lt#4:sum(yuefen(i)|i#le#j: x)sum(yuefen(i)|i#le#j: d);sum(yuefen: x)=sum(yuefen:d);for(yuefen:xa);end线性规划模型月份单位成本(元) 销售量1234 70 60 72 70 80 120 76 60线性规划模型76827676-80-7472-747270生产月100100100100产量6041207060销量4321321需求月费用cij线性规划模型本题3个模型为整数规划模型.线性规划模型 线性模型1桶牛

24、奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：加工奶制品的生产计划模型分析与假设 比例性 可加性 连续性 xi对目标函数的“贡献”与xi取值成正比 xi对约束条件的“贡献”与xi取值成正比 xi对目标函数的“贡献”与xj取值无关 xi对约束条件的“贡献”与xj取值无关 xi取值连续 A1,A2每公斤的获利是与各自产量无关的

25、常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数 线性规划模型 线性模型建立x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 线性规划模型(LP)模型求解 图解法 x1x20ABCDl1l2l3l4l5约束条件目标函数 Z=0Z=2400Z=3600z=c (常数) 等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数 可行域为直线段

26、围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得。 线性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 N

27、O. ITERATIONS= 220桶牛奶生产A1, 30桶生产A2，利润3360元。 结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料无剩余时间无剩余加工能力剩余40max 72x1+

28、64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源” 剩余为零的约束为紧约束（有效约束） 结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下“

29、资源”增加1单位时“效益”的增量 原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润影子价格 35元可买到1桶牛奶，要买吗？35 =0;则lb=0,ub用代替求解线性规划问题 编写Matlab程序如下：c=2;3;1;a=-1,-4,-2;-3,-2,-0;b=-8;-6;x,y=linprog(c,a,b,zeros(3,1)例5.1某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单

30、位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables=5;连续投资10万元A：从第1年 到第4年每年初要投资，次年末回收本利1.15B：第3年初投资，到第5年末回收1.25，最大投资4万元C：第2年初投资，到第5年末回收1.40，最大投资3万元D：每年初投资，每年末回收1.11。求：5年末总资本最大。

31、练习1:连续投资练习2某服务部门一周中每天需要不同数目的雇员，周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人，现规定应聘者需连续工作5天，试确定聘用方案。练习3某班准备从5名游泳员中选择人组成接力队，藏家学校的4100m混合泳接力比赛，5名队员4种泳姿的百米平均成绩如表，问如何选拔队员。队员甲乙丙丁戊蝶泳10685721181101074仰泳115610611421142111蛙泳1271064109610961238自由泳586535945721024 线性模型题目1 生产计划问题某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,

32、B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？）产品的单位利润增大到5万元，要不要改变生产计划？）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？ 产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润23 线性模型建立 线性模型求解程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END 线性模型求解运行结果 Model Title: 生产计划问

33、题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 对问题1，安排是生产产品4单位，产品2单位，最大盈利为14万元 。 线性模型敏感性理论1目标函数的系数变化的敏感性分析如果目标函数的系数发生变化，将会影响目标函数 f 斜率的变化，但是只要f 的斜率小于等于-1/2（也

34、就是直线l夹在l1与l2之间时），最优解都在(4,2)上取到，最优解不变，从而生产计划不会变. 线性模型敏感性分析1要使用敏感性分析必须要在这里选择Prices & Ranges然后保存退出路径：LINGOOptionsGeneral Solver(通用求解程序)选项卡 线性模型敏感性分析1要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGORange， 线性模型敏感性分析1Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable

35、 Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量对问题2，产品的单位利润降低到1.8万元，在（1.5

36、，）之间，所以不改变生产计划。如果降低到1万元，不在（1.5，）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得新的计划为安排是生产产品2单位，产品3单位，最大盈利为11万元.对问题3，要改变生产计划，更改程序得新计划为生产产品2单位，产品3单位，最大盈利为19万元.对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到8万元. 线性模型敏感性理论2 线性模型影子价格理论把y1,y2,y3作为三种原料的定价，定价的目标是在比生产产品获得更多利润的前提下的最小利润. 在最优情况下，y的值就是资源的影子价格，影子价格有意义是有范围

37、的。影子价格经济含义是：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量 线性模型综合讨论Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowab

38、le Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 运行结果 Model Title: 生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.0

39、00000 0.1250000 TIME 4.000000 0.000000 线性模型题目21桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天：加工奶制品的生产计划 线性模型建立x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非

40、负约束 线性规划模型(LP) 线性模型求解Max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100; OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 220桶牛奶生产A

41、1, 30桶生产A2，利润3360元。 线性模型影子价格 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 35元可买到1桶牛奶，要买吗？35 48, 应该买！ 聘用临时工人付出的工资最多每小时几元？ 2元！ 线性模型敏感性分析RANG

42、ES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.0000

43、00 53.333332 80.000000 4 100.000000 INFINITY 40.000000 A1获利增加到 30元/千克，应否改变生产计划？ 不变！ 35元可买到1桶牛奶，每天最多买多少？最多买10桶！2.整数规划 定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划 1o 变量全限制为整数时，称纯（完全）整数规划。2o 变量部分限制为整数的，称混合整数规划。3o 变量只能取0或1时，称之为0-1整数规划。（i）分枝

44、定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）隐枚举法求解“0-1”整数规划： 过滤隐枚举法； 分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划(随机取样法) 特殊的整数规划指派问题（又称分配问题Assignment Problem） 拟分配 人去干 项工作，每人干且仅干一项工作，若分配第 人去干第 项工作，需花费 单位时间，问应如何分配工作才能使工人花费的总时间最少？求解下列指派问题，已知指派矩阵为 编写Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5；8 4 2

45、 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(25,1) 整数规划的计算机解法整数规划问题的求解可以使用Lingo,Lindo等专用软件 .例5.1某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆

46、工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables总销量和总产量总销量.形式，我们总可以通过引入假想的销地或产地，将不平衡的运输问题转化为平衡的运输问题. 从而，我们的重点就是解决平衡运输问题的求解. 显然，运输问题是一个标准的线性规划问题，因而当然可以运用单纯形方法求解. 但由于平衡的运输问

47、题的特殊性质，它还可以用其它的一些特殊方法求解，其中最常用的就是表上作业法，该方法将单纯形法与平衡的运输问题的特殊性质结合起来，很方便地实行了运输问题的求解. 关于运输问题及其解法的进一步介绍可参考相关文献. 第三节 整数规划在工程设计和企业管理中，常会遇到要求决策变量取离散的非负整数值的线性规划问题。例如，最优调度的车辆数，设置的销售网点数，指派工作的人数等。这类问题在形式上与线性规划类似，只是比线性规划增加了某些约束条件，来限制全部或部分决策变量必须取离散的非负整数值。我们称之为整数线性规划问题，简称为整数规划问题。整数规划是近三十年来发展起来的、规划论的一个重要的理论分支。根据对决策变量

48、的要求不同，分为四种类型：纯整数规划：所有决策变量均要求为离散的非负整数。混合整数规划：部分决策变量要求为离散的非负整数。纯01整数规划：所有决策变量均要求为0或1。混合01整数规划：部分决策变量要求为0或1。4.1 引例生产组织计划问题与选址问题（生产组织计划问题）某工厂在一个计划期内拟生产甲、乙两种大型设备。除了A、B两种部件需要外部供应且供应受到严格限制之外，该厂有充分的能力来加工制造这两种设备所需的其余零件，并且所需原材料和能源也可满足供应。每种设备所用部件数量和部件的供应限额以及设备的利润由表3.2.1给出。问该厂在本计划期内如何安排甲、乙设备的生产数量，才能获取最大利润？设备 部件

49、AB利润（百万）甲6A15乙4320设备的最大供应量2510设x1，x2分别为该计划期内甲、乙设备的生产数量，Z为生产这两种设备可获得的总利润。依题意，给问题的数学模型为： max Z = 15x1 20 x2，s.t.6x1 4x2 25 x1 3x2 10 xi 0, 1, 2, 这是一个纯整数规划问题。（选址问题）某商业连锁集团拟在n个连锁店所在城市中建立m个配货中心，每个城市最多建立一个配货中心。若在第i个城市建立配货中心，其配货能力为Di，单位时间的固定成本为ai，i = 1，m，第j个连锁店的需求量为bj，j = 1，n。从第i个配货中心到第j个连锁店的单位运输成本为cij。应如何

50、选择配货中心位置和安排运输计划，才能得到经济上花费最少的方案。设在单位时间内，从配货中心i运往连锁店j的物资数量为xij，Z为单位时间内的总费用。引入布尔变量则上述问题可归结为如下的数学模型：这是一个混合01规划问题。4.7 最优化软件MATLAB由美国MathWorks公司开发研制，采用MATLAB语言编写,擅长数值计算. 可用于求解线性规划、无约束非线性规划、约束非线性规划、二次规划、线性与非线性约束最小二乘问题、纯整与混整规划、0-1规划及遗传算法等.专业的优化软件对优化问题的求解通常更有效,目前比较流行的专业优化软件有Lingo,GAMS,Tomlab等LINGOLingo是美国芝加哥

51、大学的Linus Schrage教授于1980年前后开发而得.早期版本没有全局优化功能.Lingo8.0版本增加了全局优化功能.Liongo9.0全局优化方面又做了很大的改进，使得Liongo成为最优秀的一种专业软件.Lingo的官方网站为 . 可用于求解所有的常见优化模型.图的模型一个时间安排问题图论的起源七桥问题人、狼、羊、菜渡河问题图论的起源：七桥问题 a c b d a c b d 图论的起源：七桥问题graph一般用大写字母G,H表示无向图。一种表示工具图顶点边 d c a b 三要素：顶点集V；边集E；关联函数G=(V,E,)如 (e1)=a,b，e2e3e1e4e5无向图 e与顶

52、点u, v相关联 u与v相邻 两边相邻 重边 c a b d 一种表示工具图你能给出一些可用无向图描述的实际例子吗？想无向图 任何两个以上的人组成的人群中，至少有两个人，他们的朋友数一样多。 在一次象棋比赛中，若每名选手与其余选手都比赛过，人数是n，求总盘数。 设S=（x1，,x2，xn）是平面上的点集，其中任意两点间的距离至少是1，证明：距离正好是1的点对数最多为3n。 在n个运动队间安排了一项竞赛，已赛n+1局，试证：存在一个队，它至少参加过3局比赛。 一种表示工具图 一些特殊的图一种表示工具图) 既没有环也没有重边的图，称为简单图 ) 任意两顶点都相邻的简单图,称为完全图. 记为Kv 一

53、种表示工具图) 若 ， ，且X 中任意两顶点不 相邻，Y 中任意两顶点不相邻，则称为二部图或 偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为完全二部图或完全偶图,记为 (m=|X|,n=|Y|)二部图你能给出一些可用二部图描述的实际例子吗？有向图：V1V2V3V5V4你能给出一个可用有向图描述的实际例子吗？一种表示工具图想加权图这些数字可以代表距离，费用，可靠性或其他的相关参数。12345869157103一种表示工具图返 回一种表示工具图返 回定义 若图 的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权，G 连同边上的权称为赋权图. 定义 设 和 是两个图. 1) 若 ,称 是

54、的一个子图,记 2) 若 ， ，则称 是 的生成子图.路径与连通返 回定义 1) 无向图G的一条通路是指一个有限非空序列 ，它的项交替地为顶点和边，使得对 ， 的端点是 和 ,称W是从 到 的一条通路，整数k称为W的长. 顶点 和 分别称为W的起点和终点 . 2) 若通路W的边互不相同但顶点可重复，则称W为迹或道路. 3) 若通路W的顶点和边均互不相同，则称W为路径记为路径与连通 定义 1) 起点与终点重合的通路称为闭通路. 2) 起点与终点重合的的路径称为圈，长为k的圈称为k阶圈，记为Ck. 3) 若在图G中存在(u,v)路径，则称顶点u和v在图G中连通. 4) 若在图G中顶点u和v是连通的

55、，则顶点u和v之之间的距离d(u,v)是指图G中最短(u,v)路径的长；若没有路径连接u和v，则定义为无穷大. 5) 图G中任意两点皆连通的图称为连通图 一个时间安排问题 学校要为一年级的研究生开设六门基础数学课：数理统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。一个时间安排问题SNGRPMSNGRPM用尽可能少的时段数安排这6门课的时间表，使没有同学发生冲突。一个时间安排问题返 回122233人狼羊菜渡河问题摆渡人Ferry

56、man狼Wolf羊Sheep菜Vegatable南岸状态：C44+ C43 + C42 + C41 + C40=24=16种，其中WS,SV,WSV，从而FV,FW,F为不允许状态10种允许状态：FWSVFWSFWCVFSVFSOVSWWVFWSVFWSFWVFSVFSOVSWWV1.渡河方案对应于图中从顶点“FWSV”到顶点“O”的链路？2.寻求图中从顶点“FWSV”到顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。人狼羊菜渡河问题FWSVFWSFWVFSVFSOVSWWV想FWSVFWSFWVFSVFSOVGWWVFWSVFWSFWVFSVFSOVSWWV人狼羊菜渡河问题返 回图的矩阵表示方法可达性矩阵关联矩阵边矩阵邻接顺序表返 回邻接矩阵v1v2v5v6v7v4v3abjkcghidfe邻接矩阵 无向图的邻