管理运筹学-教案ppt课件

1、管理运筹学教案教 学 内 容n绪绪 论论 运筹学概况运筹学概况n第一章第一章 线性规划线性规划 n第二章第二章 运输问题运输问题n第三章第三章 整数规划整数规划n综合建模练习综合建模练习1）-（10）绪 论 ： 运 筹 学 概 况n运筹学名称运筹学名称n运筹学的研究对象运筹学的研究对象n运筹学的发展运筹学的发展n运筹学在航空运输中的应用运筹学在航空运输中的应用n课程设置情况课程设置情况运筹学的名称nBK：Operational ResearchORnUS：Operations ResearchORn台湾：作业研究台湾：作业研究n大陆：运筹学大陆：运筹学运筹帷幄之中，决运筹帷幄之中，决胜千里之外

2、胜千里之外运 筹 学 的 研 究 对 象n资源运用资源运用运用分析理论运用分析理论n竞争现象竞争现象竞争理论竞争理论n拥挤现象拥挤现象随机服务理论随机服务理论运 筹 学 的 发 展n IFORS.ORG 国际运筹学联盟国际运筹学联盟International Federation of Operational Research Societies-IFORS ,于于1959年建立）。年建立）。/index.jsp国际运筹学联盟航空运输组国际运筹学联盟航空运输组(The Airline Group of the International Federation of Op

3、erational Research Societies -AGIFORS) / 欧洲运筹学协会欧洲运筹学协会(Association of European Operational Research Societies-EURO). nm a t h p r o g . o r g / % E 6 % 9 5 % B 0 数 学 规 划 学 会数 学 规 划 学 会Mathematical Programming Society） 是一个国际是一个国际性的组织，致力于计算数学、应用学、数学规划的理论性的组织，致力于计算数学、应用学、数学规划的理论研究。研究。

4、运 筹 学 的 发 展/home/page美国数学会American Mathematical Society - AMS ） .uk/orshop/(cojjpu553n0cnealhpkk4jzl)/orhomepage2.aspx运筹学研究社团 （Operational Research Society ） nEconomics, Operations Research, Programming, Games - Dave Rusin; The Mathematical Atlas 提供一些简短的文章，介绍运筹学方面的文章，其用象征性的语言描述优化资源

5、方面的研究。 nGlobal Optimization 这个站点链接了全球的很多关于优化的站点nOR/MS Books 该站点收集了大量的运筹学和管理科学方面的书。运 筹 学 的 发 展/中国运筹学会n7/orgs/tdyc/index.php天津运筹学会/tddg/index.php天津大学全国精品课程运筹学2019njpkctr/index01_detail.asp?id=2987兰州交通大学全国精品课程运筹学2019/res2019/data/bit/7/index.html北京理工大学全国精

6、品课程管理运筹学2019/skyclass/C60/Asp/Root/Index.asp?Mode=1&Url=江西财经大学全国精品课程运筹学2019运 筹 学 的 发 展n28/or/山东大学全国精品课程运筹学2019/0701/东北电力大学全国精品课程运筹学2019/四川大学 运筹学在航空运输中的应用n航班计划问题n机队规划问题n飞机选型问题n机场选址问题n引进飞机决策问题n紧缺资源排班问题机组、地面服务人员、装卸工、操纵设备者n飞机维修计划问题n航线网络布局问题n停机位分配问

7、题n机坪作业优化问题n收益管理问题n空中流量控制问题n航材优化问题课程设置情况2019培养方案之管理运筹学课程设置情况使用教材课程设置情况考核方式第一章 线性规划n线性规划(Linear programmingLP)n线性规划的应用案例n线性规划的计算机求解n线性规划解的认识n影子价格n灵敏度分析n课程实验LP应用案例生产计划的安排n某企业利用四种设备生产两种产品，单位产品占用各种设备的时间及有关数据如下表所示。该企业应如何安排生产，可使总利润最大？0,12416482142232max2121212121xxxxxxxxxxz目标函数(objective function)、约束条件(con

8、straints)、非负约束(nonnegativity constraints)、决策变量(decision variables)LP应用案例铁皮的利用n用一块边长为a（=100cm)的正方形铁皮折成盒子。如何折，可使盒子的容积最大？（x=16.67cm,V=74074cm3.)xa02)2(max2xaxxxaVLP应用案例下料方式n用500cm长的条材截出长度为98cm和78cm的两种毛坯分别为10000根和20000根。如何截，所用条材根数最少？(x1=1200,x5=4000,z=5200).6,5,4,3,2,1,0200006532100002345min654325432165

9、4321jxxxxxxxxxxxxxxxxxzj某机场候机楼内每天各时段所需工作人员数如下：时段所需人数6：0010：006010： 0014： 007014： 0018： 006018： 0022： 005022： 00 2： 00202：00 6：0030设工作人员于各时段一开始时上班，连续工作 8 小时。问该侯机楼至少应配备多少工作人员？LP应用案例人力资源分配问题答案：时段1-60人、2-10人、3-50人、5-30人，总共150人。LP应用案例人力资源分配问题n每周工作每周工作5 5天，连续休息天，连续休息2 2天。至少应该配备多少人员天。至少应该配备多少人员？（答案：星期一？（答案

10、：星期一-8-8人、三人、三-12-12人、五人、五-11-11人、六人、六-5-5人人；总共；总共3636人）人）时间所需人数时间所需人数星期一15星期五31星期二24星期六28星期三25星期七28星期四19LP应用案例物资配运问题有三个化肥厂为四个产粮区供应化肥，供、需量及每吨化肥的运价如下表所示。如何安排运输，可使总运费最小？建立该问题的线性规划数学模型。 产粮区化肥厂B1B2B3B4供量A1587370000A24910780000A3842930000需量60000600003000030000答案：A1-B240000、-B430000，A2-B160000、-B220000，A3

11、-B330000；总运费890000。LP应用案例生产计划问题n甲、乙、丙三种产品皆需经铸造、机械加工和装配三道工序，甲、乙、丙三种产品皆需经铸造、机械加工和装配三道工序，其中甲、乙两种产品的铸造工序可以选择自行生产或者外包协其中甲、乙两种产品的铸造工序可以选择自行生产或者外包协作。如何安排生产能够获得最大利润？（答案：甲作。如何安排生产能够获得最大利润？（答案：甲- -自自16001600件件，甲，甲- -外外400400件；最大利润件；最大利润3320033200）甲乙丙可用工时每件铸造工时51078000每件机械工时64812000每件装配工时32210000自行生产铸件每件成本354外

12、包协作铸件每件成本56机械加工每件成本213装配每件成本322每件产品售价231816LP应用案例配料问题n使用三种原料使用三种原料1 1，2 2，3 3混合调配处三种不同产品甲、乙、丙混合调配处三种不同产品甲、乙、丙，情况如下表所示。如何安排生产能够获得最大利润？（答，情况如下表所示。如何安排生产能够获得最大利润？（答案：原料案：原料1-1-甲：甲：100100公斤，原料公斤，原料2-2-甲：甲：5050公斤，原料公斤，原料2-2-丙：丙：5050公斤，原料公斤，原料3-3-甲：甲：5050公斤；利润公斤；利润=500=500元）元）产品要求单价（元/公斤）原料可用量（公斤）单价（元/公斤）

13、甲原料1不少于50%原料2不超过25%50110065乙原料1不少于25%原料2不超过50%35210025丙不限2536035LP应用案例投资问题n现有资金现有资金200200万元，今后万元，今后5 5年内可投资项目如下。如何确定各项年内可投资项目如下。如何确定各项目每年的投资额，使得第目每年的投资额，使得第5 5年末的资金总额最大？（答案：年末的资金总额最大？（答案：A A项项目目1-1701-170、2-62.22-62.2、5-31.45-31.4，B B项目项目1-301-30、2-24.82-24.8、3-25.923-25.92、4-304-30，C C项目项目3-803-80，

14、D D项目项目2-1002-100；第；第5 5年末资金总额年末资金总额339.04339.04万元万元）项目特点A第15年初都可投资，当年末收回本利110%B第14年初都可投资，次年末收回本利125%，但每年投资额不能超过30万元C第3年初需要投资，第5年末收回本利140%，但投资额不能超过80万元D第2年初需要投资，第5年末收回本利155%，但投资额不能超过100万元LP应用案例订货与库存问题n一粮库经营粮食批发业务。粮库的容量为5000担。1月1日，粮库内有粮食1000担，现金20000元。第一季度粮食的价格如下表。每月初卖出粮食,每月末买入粮食。希望季度末粮库余粮为2000担。如何安排

15、可使该季度总的获利最大？（答案：1月卖1000担、买5000担， 2月卖5000担、买0担， 3月卖0担、买2000担，总差价-700元）月份进货价（元）出货价（元）1232.853.052.905线 性 规 划 的 计 算 机 求 解n求解规划问题常用的计算机软件nMicrosoft ExcelnLindo & LingolindonMatlabnILOGnnExcel的“规划求解简介Excel规划求解目标函数设置 Excel规划求解目标函数设置Excel规划求解约束条件设置E xc e l 规 划 求 解 参 数 设 置E xc e l 规 划 求 解 最 优

16、 解线性规划解的认识n唯一最优解的认识唯一最优解的认识n无穷多最优解的认识无穷多最优解的认识n无界解的认识无界解的认识n无可行解的认识无可行解的认识n线性规划解的认识线性规划解的认识唯一最优解的认识0,12416482142232max2121212121xxxxxxxxxxzx124682468x20唯一最优解的认识0,41501053min212212121xxxxxxxxxzx124682468x2010无穷多解(Multiple optimal solutions)的认识0,22222max21212121xxxxxxxxzx1-112-112x20-2无界解(Unbounded So

17、lution)的认识0,18362334max21212121xxxxxxxxzx1-12-4268x20-164-8-18E xc e l 规 划 求 解 无 界 解无可行解(Infeasibility)的认识0,62223max21212121xxxxxxxxzx14268x2042E xc e l 规 划 求 解 无 可 行 解前往前往线性规划解的基本性质n如果线性规划问题的可行域有界，则一定有最优解，且目标函数一定可以在可行域的顶点上达到最优n线性规划问题的最优解只可能在顶点或边界上得到，而不会在可行域内部得到。线性规划的求解方法单纯形法(Simplex Method)该解为最优解？确

18、定初始基本可行解已得到最优解，停顿求出更佳的基本可行解是是否否影子价格n影子价格的含义n影子价格的意义n 不同于市场价格，由资源的使用情况确定；n 反映资源在生产中的使用情况；n 为零时，说明该资源还有剩余或者刚好用尽；n 为正值时，说明该资源已消耗完毕；n 决定了对该种资源的处理方式；n 可作为对紧缺资源的分配依据。n影子价格的应用影子价格的含义0,12416482142232max2121212121xxxxxxxxxxzx124682468x20 x124682468x20n增加单位资源能使总利润增加的数量。影子价格的意义n不同于市场价格，由资源的使用情况确定；n反映资源在生产中的使用情

19、况；n为零时，说明该资源还有剩余或者刚好用尽；n为正值时，说明该资源已消耗完毕；n决定了对该种资源的处理方式；n可作为对紧缺资源的分配依据。影子价格的应用x124682468x200,12416482142232max2121212121xxxxxxxxxxzn设B设备的市场价格为1(元/台时)，应否增加该设备的使用时间？增加多少？Excel规划求解运算结果报告Excel规划求解敏感性报告Excel规划求解极限值报告灵敏度分析线性规划的基本假设n确定性cj、aij、bi不随时间变化n等比性资源需要量与产品数量等比n可加性两种产品总利润等于各自利润之和(两种产品之间无替代性）n可分性决策变量可取

20、小数值灵敏度分析的内容和形式n灵敏度分析的内容n某参数的允许变化范围，使原最优方案不变；n某参数的变化超出允许范围时，如何求得新的最优方案。n灵敏度分析的形式n 价值系数cj发生变化n 右端常数bi发生变化n 增加一个变量的情况n Pj发生变化n 增加一个约束条件的情况价值系数cj发生变化0124164821422522121212121x ,xxxxxxxxxzmaxn确定产品的单位利润c2 的允许变动范围，使原最优生产方案不变。当c2变为5时，求新的最优生产方案。x124682468x20 x124682468x200124164821422322121212121x ,xxxxxxxxx

21、zmax右端常数bi发生变化0124204821422322121212121x ,xxxxxxxxxzmaxn设C设备的可用台时b3变为20时，求新的最优生产方案。x124682468x20 x124682468x200124164821422322121212121x ,xxxxxxxxxzmax增加一个变量的情况n现有产品可供选择。生产每件产品耗用A,B,C,D设备的台时分别为3,2,6,3，单位利润为5元。是否应该生产产品？生产多少件？0124164821422322121212121x ,xxxxxxxxxzmax01234166482214322532321323132132132

22、1x ,x ,xxxxxxxxxxxxxxzmaxPj发生变化的情况n由于工艺结构的改进，生产产品所耗A,B,C,D设备的时间变为3,2,5,2，单位利润也提高到4元。应如何安排生产？x124682468x20 x124682468x200124164821422322121212121x ,xxxxxxxxxzmax0124216582214233421211212121x ,xxxxxxxxxxzmax增加一个约束条件n生产产品、产品时增加一道工序，在E设备上进行。产品、产品在E设备上加工的时间为2,2.4小时，E设备在计划期内的有效台时为12小时。应如何安排生产？x124682468x2

23、00124164821422322121212121x ,xxxxxxxxxzmax012512212416482142232212121212121x ,xxxxxxxxxxxzmax课程实验:LP应用案例(2)-(9)的求解n随机抽签确定题目；n原则上力争每人1题，由于学生人数多而无法实现时，力争使每题分配的人数均等；n每次实验结果皆计入平时成绩。第二章 运输问题n产销平衡运输问题的数学模型n产销不平衡运输问题的数学模型n需求有界运输问题的数学模型n转运问题的数学模型n课程实验运输问题的数学模型n产地、销地、运价、运费n产销平衡问题的数学模型 n产大于销问题的数学模型n销大于产问题的数学模

24、型n有最低需求问题的数学模型n转运问题的数学模型产地、销地、运价、运费产销平衡问题的数学模型njmixbxxbxxaxxaxxxcxcxcxczijnmnnmmmnmnmnmnmmnn，, 1, 1, 0min111111111111111111产销平衡问题的数学模型 销地产地B1B2B3B4产量A137645A224322A343853销量3322 1010.,j;,ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzminzBAxijjiij43213210223332558342342467334241433231332221231211134333231242

25、3222114131211343332312423222114131211，。则：总运费为的物资数量，运给销地为从产地设产大于销问题的数学模型 销 地产 地B1B2B3B4产 量A1211347A2103595A378127销 量2346 1915销大于产问题的数学模型 销地产地B1B2B3产量A148856A216241682A38162477销量8210261 215245有最低需求问题的数学模型 销地产地B1B2B3B4产量A11613221750A21413191560A3192023M50最低需求3070010 160110转运问题ABCDGEFH发量10发量2收量3收量1收量854

26、31214134DGDEDCEDDCBCABBEBCABGHFGEFEDDGDEDCBEBCABxxxxDxxCxxxBxAxxxxxxxxxxMinz2:3:10:4432345., 08:1:HAjixxHxxxGxxFxxxxEijGHGHFGDGFGEFEFEDDEBE转运问题续）最优调运方案ABCDGEFH发量10发量2收量3收量1收量8543121413410378618课程实验运输问题的计算机求解n产销平衡问题的求解产销平衡问题的求解 n产大于销问题的求解产大于销问题的求解n销大于产问题的求解销大于产问题的求解n有最低需求问题的求解有最低需求问题的求解n转运问题的求解转运问题的求

27、解有最低需求问题的计算机求解“=”时有最低需求问题的计算机求解“=”时有最低需求问题的计算机求解“”时有最低需求问题的计算机求解“”时第三章 整数规划n整数规划问题的数学模型n整数规划问题的求解方法n0-1型整数规划的应用n指派问题n整数规划应用案例航班计划的制定n课程实验整数规划的数学模型n整数规划的基本概念n整数线性规划n整数非线性规划n纯整数规划n混合整数规划n01规划n托运甲、乙两种货物分别采用两种不同规格的集装箱。每箱体积及重量等数据如下表所示。问两种货物各托运多少箱，可使所获利润最大？货 物体 积(米3)重 量(百 斤)利 润(百 元)甲5220乙4510托 运限 制2413且为整

28、数013522445102021212121x ,xxxxxxxzmax整数规划与松弛问题的关系n整数规划问题与其松弛问题的最优解对比n整数规划问题的目标函数值不超过其松弛问题的目标函数值 n不能采用对松弛问题最优解取整方法得到整数规划最优解且为整数013522445102021212121x ,xxxxxxxzmax。不是整数规划的可行解；为可行解，但最优解为松弛问题的最优解),0 , 5() 1 , 4(),0 , 4()0 , 8 . 4(整数规划问题的求解方法分支定界法X14X15 且为整数0,70207567909040max21212121xxxxxxxxz 349)1021, 4

29、(),(0,47020756799040max*2*1211212121zxxxxxxxxxxxz3.4341)711, 5(),(0,57020756799040max*2*1211212121zxxxxxxxxxxxz 88.355)131238,131630(),(. 0,7020756799040max*2*121212121zxxxxxxxxxxz整数规划问题的求解方法分支定界法X22X23X21X22 349)1021, 4(),(0,47020756799040max*2*1211212121zxxxxxxxxxxxz3.4341)711, 5(),(0,570207567990

30、40max*2*1211212121zxxxxxxxxxxxz340)2 , 4(),(0,247020756799040max*2*12121212121zxxxxxxxxxxxxz 4.1327)3 ,710(),(0,347020756799040max*2*12121212121zxxxxxxxxxxxxz8.7307) 1 ,949(),(0,157020756799040max*2*12121212121zxxxxxxxxxxxxz无可行解。0,257020756799040max2121212121xxxxxxxxxxz0-1整数规划的应用案例n某公司拟在东、西、南三区建立门市部

31、。共有七个地点A1，A7可供选择。规定：在东区A1,A2,A3中至多选两个；在西区，由A4, A5中至少选一个； 在南区，由A6, A7中至少选一个。选Ai点时，需投资bi元，年获利ci元。现有资金总额B元。问应选择哪些点，可使年获利润最大？ .7 , 1A0A1112maxjj71765432171jxBxbxxxxxxxxczjjjjjjj点建门市部时当不选择，点建门市部时，当选择0-1整数规划的应用某实验卫星拟从下列仪器装置中选若干件携带升空，要求：仪器装置体积重量实验价值A1v1w1c1A2v2w2c2A3v3w3c3A4v4w4c4A5v5w5c5A6v6w6c6 携带的仪器装置总体

32、积不超过 V，总重量不超过 W； A1与 A3中最多安装一件； A2 与 A4中至少安装一件； A5 与 A6或者都安装，或者都不安装。确定使该次科学实验产生最大的实验价值的装载方案。.6, 1A0A1011maxjj654231616161jxxxxxxxVxvWxwxczjjjjjjjjjj，仪器时当不携带仪器时当携带0-1整数规划的应用某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油，使总的钻探费用最小。要求：井位s1s2s3s4s5s6s7s8s9s10钻探费用c1c2c3c4c5c6c7c8c9c10 或者选择 s1 和 s7，或者选择 s8； 选择了 s3 或 s4就

33、不能选择 s5，反之亦然； 在 s5 ，s6 ，s7 ，s8中最多只能选择两个。15,min.10, 1,s0s181101101jjxxxxczjxjjjjjj井位时当不选择井位时当选择.10,1,0or121108765545371jxxxxxxxxxxxj0-1整数规划的应用.6, 1,0or11202132132154jxxxxxxxxxj 工程工种总工时泥工655070486070240木工404530403550170普通工708060505080170钢筋工303528302540330利润1.5v要求：v从工程、中最多只能挑选一项；v如果选择工程或，就必须

34、选择工程，反之亦然。3304025302835301708050506080701705035403045402407060487050655 . 22 . 15 . 125 . 1max. 6 , 1,01654321654321654321654321654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzjjjxj项工程时当不选择第项工程时当选择第0-1整数规划的应用拟 在 以 下 新 建 的 居 民 小 区 增 设 若 干 所 小 学 。 要 求 覆 盖 所 有 小 区 ， 至 少应 建 多 少 所小 学 。 试建 立 该 问题 的 数 学模 型 （ 不必 求 解 ）

35、。备 选 校 址ABCDEF覆 盖 的 居 民小 区1,5,71,2,51,3,52,4,53,64,60-1整数规划的应用10 xn1j1,xm1ixxaxzn1jm1iijijxijm1iij0n1jijj0ij或者上加工时种零件不在机床当第上加工时种零件在机床当第,min.,;,0,1均衡。或尽可能机床的总加工任务相等。问如何分配，使各种，为工。设加工时间分别种零件在这种机床上加台同类型的机床，有有n21a,a,anm0-1整数规划的应用. n, 0ji,1,01nn, 1 , 0S1,n, 1 , 01,n, 1 , 0i , 1dmin; n, 0ji,AA,0AA, 1ijijn0

36、in0jSiSjijn0iijn0jijijn0in0jijjijiij或者对任意的非空子集时后面的不是当紧接着村庄时后面的是当紧接着村庄xxxjxxxzx并使总的行程最短。，使能经过每个村庄一次，顺序，问如何选定行走为的距离到。设到，最后返回庄经过预先确定的村出发一位推销商从居住地0iii0ijji0n10A,A,A,A,AdAAAA,A,An210-1整数规划的应用*。满足时，要求条件满足时，不要求条件，其中：。必须且只需有一个满足个条件：设。满足时，要求条件满足时，要求条件，其中：则上述条件可表示为：为可以任意大的正数，令。必须且只需有一个满足：和条件：设条件i0i1y1myyyMybx

37、axaxam, 1i,bxaxaxam1021yMy-1bxaxayMbxaxaMbxaxa2bxaxa1im21iinin2i21i1inin2i21i122221211212111222212112121110-1整数规划的应用*。，或，其中：中的一个值，只能取。或，其中：则上述条件可表示为：为可以任意大的正数，令或321i10y1yyy7y5y3yx7530 x210yMy-1-53x2xyM2xxM53x2x2xx1i32132121212121,)()(0-1整数规划的应用*。或，其中：至少满足两个，四个条件。或，其中：，否则则若,41,i1,0y2yyyyM1-y6xxM1-y2x

38、My12xMy15xx6xx2x2x5xx)4(10yMy-14xM1-y2xyM-1xyM2x4x1x2x)3(i4321443332112143312111212210-1整数规划的应用* 某公司在今后五年内考虑给以下的项目投资。知：某公司在今后五年内考虑给以下的项目投资。知：项目项目A A：从第一年到第四年每年年初需要投资，并于次年末回：从第一年到第四年每年年初需要投资，并于次年末回收本利收本利115%115%，但要求第一年投资最低金额为，但要求第一年投资最低金额为4 4万元，第二、万元，第二、三、四年不限；三、四年不限；项目项目B B：第三年初需要投资，到第五年末能回收本利：第三年初需

39、要投资，到第五年末能回收本利128128，但，但规定最低投资金额为规定最低投资金额为3 3万元，最高金额为万元，最高金额为5 5万元；万元；项目项目C C：第二年初需要投资，到第五年末能回收本利：第二年初需要投资，到第五年末能回收本利140%140%，但，但规定其投资额或为规定其投资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。项目项目D D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项投资金额不限。，此项投资金额不限。 该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目

40、的万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大每年投资额，使到第五年末拥有的资金本利总额为最大? ?指派问题n平衡指派问题的数学模型n不平衡指派问题的数学模型n 求极大的指派问题的数学模型n 人员数多于工作数的指派问题的数学模型n 工作数多于人员数的指派问题的数学模型平衡指派问题的数学模型., 1, 10, 1, 1, 1, 1min., 1, 1011111mjiorxmixmjxxcznmnjmijijixijmjijmiijmimjijijij且，项工作名职员承担第不分配第项工作名职员承担第分配第令平衡指派问题的数学模型 施工 队工程甲乙丙丁戊A745

41、68B121013159C10981113D1517201411E1614131815表中数据为完成工程所需时间求极大指派问题的数学模型表中数据为操作每台机器的产值 机器工人ABCD甲10987乙3456丙2112丁4356人员数多于工作数的指派问题表中数据为承担每种工作的费用 工 人工 作甲乙丙丁戊己A373655B618427C245346D648732人员数少于工作数的指派问题表中数据为承担每种工作的费用，且每人最多承担1项工作。 工 作工 人ABCDEF甲373655乙618427丙275346丁648732人员数少于工作数的指派问题表中数据为承担每种工作的费用，且每人最多可以承担2项

42、工作。 工 作工 人ABCDEF甲373655乙618427丙275346丁648732整数规划应用案例航班计划编制n某航空公司经营A,B,C三个城市之间的航线，这些航线每天航班起飞与到达时间如下表所示。设飞机在机场停留的损失费用大致与停留时间的平方成正比，而且从降落到起飞至少需2小时的准备时间。指定使停留费用损失最小的航班计划。航班号起飞城市起飞时间到达城市到达时间101A9:00B12:00102A10:00B13:00103A15:00B18:00104A20:00C24:00105A22:00C2:00106B4:00A7:00107B11:00A14:00108B15:00A18:0

43、0109C7:00A11:00110C15:00A19:00111B13:00C18:00112B18:00C23:00113C15:00B20:00114C7:00B12:00整数规划应用案例航班计划编制 A起 飞到 达A1011021031041051064964169225107361400625366410822525644141610948452916811211101962254006259 B起 飞到 达B1061071081111121012565299625361022254844576251031002894413615761136422536128948411425652

44、9962536 C起 飞到 达C109110113114104492252254910525169169251111694414411691126425625664整数规划应用案例航班计划编制106102107104110101108105113111114112109103课程实验(3)整数规划的计算机求解n0-1整数规划的应用(4)、(5)、(11)n平衡的指派问题n不平衡的指派问题综合建模练习1）n（参见教材P20） Par公司生产高尔夫袋，各道生产工序的可用时间、两种规格的高尔夫袋的单位加工时间以及利润情况如下表所示。两种袋各生产多少个，可使Par公司获得最大的利润？工序加工时间（小时

45、）可用时间（小时）标准袋高级袋切割与印染7/101630缝合1/25/6600成型12/3708检查与包装1/101/4135单位利润（美元）109综合建模练习2）背景：现将背景：现将2020吨货物从地点依次经过地点、吨货物从地点依次经过地点、运至地点，在地点、出发时都可以且只运至地点，在地点、出发时都可以且只能选择铁路、公路和航空三种运输方式之一，相应的运能选择铁路、公路和航空三种运输方式之一，相应的运输成本如表所示。并且如果在相邻两段改变了运输方式，输成本如表所示。并且如果在相邻两段改变了运输方式，还要发生额外的费用，具体数据亦如表所示。如何选择还要发生额外的费用，具体数据亦如表所示。如何

46、选择各段的运输方式，使总的运输成本最小？各段的运输方式，使总的运输成本最小？12345第1段第2段第3段第4段综合建模练习3）n（参见教材P200某房产租赁公司现有2000千美元用于购置新的房产，别墅每套售价282千美元，最多可购买5套；每幢公寓楼售价400千美元。该公司每月最多可以花140小时管理新增房产，其中管理每套别墅每月要花4小时，管理每幢公寓楼每月要花40小时。出租后，每套别墅的年收益为10千美元，每种公寓楼的年收益为15千美元。别墅和公寓楼各购买多少套，可使全年总收益最大？综合建模练习4-1）的总步行距离最短？机口，使所有中转旅客间的距离，如何分配登，以及各登机口之登机口转机的旅客

47、人数进港航班上需要到各个个航班进港。已知每个分钟内将有个登机口空闲，某机场现有7157各进港航班中到各登机口转机的旅客人数进港航班衔接航班出港登机口12345678910111213141516171819F155108158210820540934121F2521419942322738402172F31004913444355849117944F4485410410024191245582F541199631442103512234F6124252762472364102100F73325913112237224011229综合建模练习4-2）各登机口之间的距离进港航班登机口出港航班登机口

48、1234567891011121314151617181931040-301040205030604070508060907090804401030-40105020603070408050906090708010704060305020401030-4010504060307040501150804070306020501040-30104020503050401490608050704060305020401030-40105020301570100609050804070306020501040-3010302017801007090608050704060305020401030-2010综合建模练习5）背景：某航空公司以戴高乐机场作为中转枢纽。分别来自波尔多、背景：某航空公司以戴高乐机场作为中转枢纽。分别来自波尔多、克莱蒙克莱蒙- -费朗、马赛、南特、尼斯、图卢兹的费朗、马赛、南特、尼斯、图卢兹的6 6架相同