《运筹学》课程教学资源(试卷习题)第6章 整数规划

第六章 整数规划
1 第六章 整数规划

引例:某厂利用集装箱托运甲、乙两种货物,每箱体积重量、可获利润及托运限制如下:利润体积重量甲52205乙4102413托运限制两种货物各托运多少箱使利润最大?MaxZ=20x, +10x25x1 +4x2≤242x +5x2≤13X1,X2≥0 X1,X2 为整数
引例:某厂利用集装箱托运甲、乙两种货物,每箱体 积重量 、可获利润及托运限制如下: 体积 重量 利润 甲 5 2 20 乙 4 5 10 托运限制 24 13 两种货物各托运多少箱使利润最大? Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0 x1 , x2 为整数

整数规划的数学模型1、整数规划问题(IP)整数规划问题:是指要求部分或全部决策变量的取值为整数的规划问题松弛问题:不考虑整数条件,由余下的目标函数和约束条件构成的规划问题重点研究:喜整数线性规划问题
一、 整数规划的数学模型 1、整数规划问题 整数规划问题(IP):是指要求部分或全部决策变 量的取值为整数的规划问题。 松弛问题:不考虑整数条件,由余下的目标函数 和约束条件构成的规划问题。 重点研究:整数线性规划问题

2、整数线性规划问的模型max(min) Z =c;x;j=1nZaijX, ≤(≥,=)b; i=1,2,..,mj=1x≥0x,中取部分或全部为整数j=1,2,.,n
2、整数线性规划问题的模型 j=1,2,.,n j n j Z c j x = = 1 max(min) 0 ( , ) 1 = = j i n j ij j x a x b i=1,2,.,m xj 中取部分或全部为整数

3、整数规划问题的类型:(1)纯整数规划问题minZ=X, +X2+x3+x$+xs+x6+x$+xgXi≥ 8X1 + X2 ≥ 8X1 + X2+ X3 ≥7Xi+X2+ X3 + X4 ≥1X2+ X3 + X4 + Xs≥2X3+ X4 + Xs +X ≥ 1X4 + Xs +X +X ≥5Xs+ X6 + X+Xg ≥ 10X6 + X +Xg ≥ 10X +Xg ≥ 6Xg≥ 6x;≥0(i=1,...,8)且为整数
3、整数规划问题的类型: (1) 纯整数规划问题 x1 8 x1 + x2 8 x1 + x2+ x3 7 x1+x2+ x3 + x4 1 x2+ x3 + x4 + x5 2 x3+ x4 + x5 +x6 1 x4 + x5 +x6 + x7 5 x5+ x6 + x7 +x8 10 x6 + x7 +x8 10 x7 +x8 6 x8 6 xi 0 (i =1,.,8)且为整数 minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8

2)0-1型整数线性规划例2:现有资金总额为B。可供选择的投资项目有n个,项目j所需投资额和预期收益分别为a,和c,此外,因种种原因,有3个附加条件:若选择项目1必须同时选择项目2,反之,不一定;项目3和项目4中至少选择一个;第三,项目5、6、7中恰好选择两个。应当怎样选择投资项目,才能使总预期收益最大?Max Z-Ecyj1对项目i投资X=Zax<B【0对项目不投资X2≥XiXs+x≥1Xs+X6 +x,=2x;=0或1 (j=1,2,...n)
(2) 0-1型整数线性规划 例2:现有资金总额为B。可供选择的投资项目有n个,项 目j所需投资额和预期收益分别为aj 和cj ,此外,因种种 原因,有3个附加条件:若选择项目1必须同时选择项目2, 反之,不一定;项目3和项目4中至少选择一个;第三, 项目5、6、7中恰好选择两个。应当怎样选择投资项目, 才能使总预期收益最大? 1 对项目j 投资 0 对项目j 不投资 xj= Max Z=∑cjxj ∑ajxj≤B x2 ≥ x1 x3+ x4≥ 1 x5+ x6 +x7=2 xj=0或1(j=1,2,.n)

(3)混合整数规划例3:工厂A,和A,生产某种物资,由于该种物资供不应求,还需要建一家工厂。由两个待选方案A,和A4。物资需求地为B;(j=1,2,3,4)。工厂A,和A4的生产费用估计为1200万元或1500万元。选择哪一个方案才能使总费用(包括物资运费和新工厂的生产费用)最小。B1B2B3B4生产能力93A124400857A23600762A312002A4455200需求量350400300150
例3: 工厂A1和A2生产某种物资,由于该种物资供不应 求,还需要建一家工厂。由两个待选方案A3和A4。物 资需求地为Bj (j=1,2,3,4)。工厂A3和A4的生产费用估计 为1200万元或1500万元。选择哪一个方案才能使总费 用(包括物资运费和新工厂的生产费用)最小。 (3) 混合整数规划 B1 B2 B3 B4 生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 需求量 350 400 300 150

B1B2B3B4生产能力A129344008357A26007612A320025A445200350400300150需求量 +[1200y+1500(1-y)]mir -Z2cijX11+ X21+ X31+ X41=350— 0-1变量KX12+ X22+ X32+ X42=400y=『1若建工厂A3X13+ X23+ X33+ X43=3000若建工厂A4X14+ X24+ X34+ X44=150设x为由A;送往B;的物资数量。X11+ X12+ X13+ X14=400X21+ X22+ X23+ X24=600X31+ X32+ X33+ X34=200yX41+ X42+ X43+ X44=200(1-y)Xi≥0,y=0或1
y—— 0-1变量 y= 1 若建工厂A3 0 若建工厂A4 设xij为由Ai送往Bj 的物资数量。 x11+ x21+ x31+ x41=350 x12+ x22+ x32+ x42=400 x13+ x23+ x33+ x43=300 x14+ x24+ x34+ x44=150 x11+ x12+ x13+ x14=400 x21+ x22+ x23+ x24=600 x31+ x32+ x33+ x34=200y x41+ x42+ x43+ x44=200(1-y) xij≥0, y=0或1 min Z=∑∑cijxij +[1200y+1500(1-y)] B1 B2 B3 B4 生产能力 A1 2 9 3 4 400 A2 8 3 5 7 600 A3 7 6 1 2 200 A4 4 5 2 5 200 需求量 350 400 300 150

割平面法1、基本思想找到纯整数线性规划的松弛问题,不考虑整数约束条件,但增加线性约束条件,将松弛问题的可行域切割一部分,但不切割掉任何整数解,只切割掉包括松弛问题的最优解在内的非整数解。由松弛问题的可行域向整数规划的可行域逼近
二、 割平面法 1、基本思想 找到纯整数线性规划的松弛问题,不考虑整数 约束条件,但增加线性约束条件,将松弛问题的可 行域切割一部分,但不切割掉任何整数解,只切割 掉包括松弛问题的最优解在内的非整数解。 由松弛问题的可行域向整数规划的可行域逼近

割平面求解举例二、Max Z=xi+x2Max Z=xi+x2-Xi+x2≤1-Xi+x2+x3=1松弛问题3xj+x2 ≤43xj+x2 +x4=4X1,X2≥0且为整数X1, X2≥0
二、割平面求解举例 Max Z=x1+x2 -x1+x2≤1 3x1+x2 ≤4 x1 , x2≥0且为整数 松弛问题 Max Z=x1+x2 -x1+x2≤1 3x1+x2 ≤4 x1 , x2≥0 -x1+x2+x3 =1 3x1+x2 +x4=4 x1 , x2≥0
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 《运筹学》课程教学资源(试卷习题)第7章 决策分析.ppt
- 《运筹学》课程教学资源(试卷习题)运筹B卷(答案).pdf
- 《运筹学》课程教学资源(试卷习题)运筹A卷(答案).pdf
- 《运筹学》课程教学资源(试卷习题)运筹B卷(试题).pdf
- 《运筹学》课程教学资源(试卷习题)运筹A卷(试题).pdf
- 《运筹学》课程教学资源(试卷习题)重点难点考点剖析.pdf
- 《运筹学》课程教学资源(试卷习题)第2章 线性规划部分习题解答.pdf
- 《运筹学》课程教学资源(试卷习题)第2章 线性规划部分练习题.pdf
- 《运筹学》课程教学资源(试卷习题)第3章 线性规划对偶理论与灵敏度分析习题解答.pdf
- 《运筹学》课程教学资源(试卷习题)第4章 运输问题习题解答.pdf
- 《运筹学》课程教学资源(试卷习题)第3章 线性规划对偶理论与灵敏度分析习题.pdf
- 《运筹学》课程教学资源(试卷习题)第4章 运输问题习题.pdf
- 《运筹学》课程教学资源(试卷习题)第6章 排队论题解.pdf
- 《运筹学》课程教学资源(试卷习题)第5章 动态规划习题解答.pdf
- 《运筹学》课程教学资源(试卷习题)第5章 动态规划习题.pdf
- 《运筹学》课程教学资源(试卷习题)第6章 排队论习题.pdf
- 《运筹学》课程教学资源(试卷习题)第7章 决策分析习题解答.pdf
- 《运筹学》课程教学资源(试卷习题)第8章 图与网络分析习题.pdf
- 《运筹学》课程教学资源(试卷习题)第8章 图与网络分析习题解答.pdf
- 《运筹学》课程教学资源(试卷习题)第7章 决策分析习题.pdf
- 《运筹学》课程教学资源(试卷习题)第5章 动态规划.ppt
- 《运筹学》课程教学资源(试卷习题)第8章 图与网络分析.ppt
- 《运筹学》课程教学资源(试卷习题)第1章 绪论 Operations Research.ppt
- 《运筹学》课程教学资源(试卷习题)第4章 运输问题.ppt
- 《运筹学》课程教学资源(试卷习题)第2章 线性规划.ppt
- 《运筹学》课程教学资源(试卷习题)第3章 线性规划的对偶理论.ppt
- 《商务谈判》课程教学资源(PPT课件,完整讲稿,共八章).ppt
- 《商务谈判》课课程教学大纲.pdf
- 《政治经济学》课程教学资源(作业习题)政治经济学总习题集(无答案).doc
- 《政治经济学》课程教学资源(文献资料)中英文词汇对照表.doc
- 《生产质量控制》课程教学课件(PPT讲稿)CH12 Design for Manufacturing.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH13 Prototyping.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH11 Industrial Design.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH10 Product Architecture.pptx
- 《生产质量控制》课程教学课件(PPT讲稿)CH7 Concept Generation.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH6 Product Specifications.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH8 Concept Selection.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH9 Concept Testing.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH5 Identifying Customer Needs.ppt
- 《生产质量控制》课程教学课件(PPT讲稿)CH2 Development Processes and Organizations.ppt