管理运筹学-整数规划

管理运筹学-整数规划

ID:38566399

大小:359.31 KB

页数:20页

时间:2019-06-15

管理运筹学-整数规划_第1页
管理运筹学-整数规划_第2页
管理运筹学-整数规划_第3页
管理运筹学-整数规划_第4页
管理运筹学-整数规划_第5页
资源描述:

《管理运筹学-整数规划》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第八章整数规划§1整数规划的图解法§2整数规划的计算机求解§3整数规划的应用§4整数规划的分枝定界法§1整数规划的图解法例1.某工厂在计划期内要安排甲、乙两种仪器设备的生产,已知生产仪器设备需要A、B两种材料的消耗以及资源的限制,如右表。问题:工厂应分别生产多少件甲、乙种仪器设备才能使工厂获利最多?解、目标函数:Maxz=x1+x2约束条件:s.t.3x1+2x2≤102x2≤5x1,x2≥0为整数不考虑整数约束得到最优解:x1=1.667,x2=2.5;z=4.167考虑整数约束得到最优解:x1=2

2、,x2=2;z=4整数规划的最优目标值小于相应线性规划的最优目标值(相当于附加一个约束)§2整数规划的计算机求解例2:Maxz=15x1+10x2+7x3s.t.5x1-10x2+7x3≤86x1+4x2+8x3≤12-3x1+2x2+2x3≤10x1,x2,x3≥0为整数例2:Maxz=15x1+10x2+7x3s.t.5x1-10x2+7x3≤86x1+4x2+8x3≤12-3x1+2x2+2x3≤10x1,x2,x3≥0x3为整数x1为0-1变量用《管理运筹学》软件求解得:x1=0x2=3x3=

3、0z=30用《管理运筹学》软件求解得:x1=1x2=1.5x3=0z=30§3整数规划的应用(1)一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个位置Aj(j=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定:在东区由A1,A2,A3三个点至多选择两个;在西区由A4,A5两个点中至少选一个;在南区由A6,A7两个点中至少选一个;在北区由A8,A9,A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是

4、不一样的,预测情况见右表所示(单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最大?解:设:0--1变量xi=1(Ai点被选用)或0(Ai点没被选用)。这样我们可建立如下的数学模型:Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x

5、9+x10≥2xj≥0xj为0--1变量,i=1,2,3,……,10二、固定成本问题例5.高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如右表所示。不考虑固定费用,每种容器售出一只所得的利润分别为4万元、5万元、6万元,可使用的金属板有500吨,劳动力有300人月,机器有100台月,此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是l00万元,中号为150万元,大号为200万元。现在要制定一个生产计划,使获得的利润为最大

6、。解:这是一个整数规划的问题。设x1,x2,x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入,为了说明固定费用的这种性质,设yi=1(当生产第i种容器,即xi>0时)或0(当不生产第i种容器即xi=0时)引入约束xi≤Myi,i=1,2,3,M充分大,以保证当yi=0时,xi=0。这样我们可建立如下的数学模型:Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2

7、+3x3≤100xi≤Myi,i=1,2,3,M充分大xj≥0yj为0--1变量,i=1,2,3§3整数规划的应用(2)例6.有四个工人,要分别指派他们完成四项不同的工作,每人做各项工作所消耗的时间如右表所示,问应如何指派工作,才能使总的消耗时间为最少。解:引入0—1变量xij,并令xij=1(当指派第i人去完成第j项工作时)或0(当不指派第i人去完成第j项工作时).这可以表示为一个0--1整数规划问题:Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18

8、x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(A工作只能一人干)x12+x22+x32+x42=1(B工作只能一人干)x13+x23+x33+

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。