- 1、本文档共10页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第六章 运筹学 整数规划案例
第六章 整数规划
6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。
1、 max z=3x1+2x2
S.T. 2x1+3x2≤12
2x1+x2≤9
x1、x2≥0
解:
2、 min f=10x1+9x2
S.T. 5x1+3x2≥45
x1 ≥8
x2 ≤10
x1、x2≥0
6.2 求解下列整数规划问题
1、 min f=4x1+3x2+2x3
S.T. 2x1-5x2+3x3≤4
4x1+x2+3x3≥3
x2+x3≥1
x1、x2、x3=0或1
解:最优解(0,0,1),最优值:2
2、 min f=2x1+5x2+3x3+4x3
S.T. -4x1+x2+x3+x4≥2
-2x1+4x2+2x2+4x2≥4
x1+x2-x2+x2≥3
x1、x2、x3、x3=0或1
解: 此模型没有可行解。
3、max Z=2x1+3x2+5x3+6x4
S.T. 5x1+3x2+3x3+x4≤30
2x1+5x2-x2+3x2≤20
-x1+3x2+5x2+3x2≤40
3x1-x2+3x2+5x2≤25
x1、x2、x3、x3=正整数
解:最优解(0,3,4,3),最优值:47
4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5+3 x6+4 x7+3 x8+4 x9+9 x10+7 x11+
5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19
约束条件 x1 + x2+x3≤30
x4+ x5+ x6-10 x16≤0
x7+ x8+ x9-20 x17≤0
x10+ x11+ x12-30 x18≤0
x13+ x14+ x15-40 x19≤0
x1 + x4+ x7+x10+ x13=30
x2 + x5+ x8+x11+ x14=20
x3 + x6+ x9+x12+ x15=20
xi为非负数(i=1,2…..8)
xi为非负整数(i=9,10…..15)
xi为为0-1变量(i=16,17…..19)
解:最优解(30,0,0,0,0,0,0,0,0,0,0,0,0,20,20,0,0,0,1),
最优值:860
6.3 一餐饮企业准备在全市范围内扩展业务,将从已拟定的14个点中确定8个点建立分店,由于地理位置、环境条件不同,建每个分店所用的费用将有所不同,现拟定的14个店的费用情况如下表:
店名 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 费用(万元) 1.2 1.5 1.7 2.1 3.3 1.2 2.8 2.5 1.9 3.0 2.4 2.4 2.1 1.6 (1)B5B3和B7只能选择(2)选择了B1或B14就不能选B6。
(3)B2、B6、B1、B12最多只能选两个。
(4)B5、B7、B10、B8最少要选两个。
工作
否
分 工人 配 工作A 工作B 工作C 工作D 甲 18 16 - 19 乙 - 20 16 20 丙 19 18 17 21 丁 12 15 20 -
2、每人做各项工作所创的利润如下表所示,问应如何指派工作,才能使总的创利为最多?
所 工作
创
利 工人 益 工作A 工作B 工作C 工作D 甲 4 5 7 9 乙 7 5 6 8 丙 3 4 3 5 丁 7 6 8 8 解:1、消耗时间为最少问题
线性规划数学模型:
min f= 18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21x10+12x11+15x12+20x13
S.T. x1+x2+x3 =1
x4+x5+x6=1
x7+x8+x9+x10=1
x11+x12+x13=1
x1+x7+x11 =1
x2+x4+x8 +x12 =1
x5+x9+x13 =1
x3+x6+x10 =1
xi≥0且xi 为0-1变量,i=1,2,3,…,13。
最优解:(0,1,0,0,1,0,0,0,0,1,1,0,0,),最优值:65。
即:给甲分配工作B,给乙分配工作C,给丙分配工作D,给丁分配工作A,所用最少的时间为65小时。
2、总的创利为最多问题
线性规划数学模型:
max Z = 41+52+73+94+75+5x6+6x7+8x8+3x9+4x10+3
文档评论(0)