当前位置：文档之家 › 整数规划应用案例分析

整数规划应用案例分析

  • 格式：ppt
  • 大小：1014.00 KB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

整数规划实例课件

整数规划实例课件
00 1
x1 x2 x3 x4 s1 0 0 1/ 41/ 4 0 3 / 2
1 0 1/6 1/6 0 1 0 1 1/4 1 4 0 3/ 2
1 0 01 1
x2 0x3 0x4 s1 1
x1 x2 x3 x4 s1 0 0 1/ 41/ 4 0 3 / 2
1 0 1/6 1/6 0 1 0 1 1/4 1 4 0 3/ 2 0 0 1/ 4 1/ 4 1 1/ 2
n
xij 1; i 1,2,..., n j0
s.t. n xij 1; j 1,2,..., n i0 ui u j nxij n 1;1 i j n xij 1,0, i 1,2,..., n, j 1,2,..., n
背包问题
背景 案例 模型
整数规划
I
B1N B 1b 0
xr arj x j br jN
xr arj x j br jN
arj arj f rj arj arj
br br f r br br
xr arj x j br jN
整数可行解
最优基可行解
xr arj x j br jN
arn 0
1 amm1 amn 0
arm1 arn 1
cB B 1b b1
br
bm
br
x1 x2 xr 0 0 0
1 1 1
0
xm xm1 xn sr 0 m1 0 n 0 0
a1m1 a1n 0
a rm 1
arn 0
1 amm1 amn 0
1 arm1
a
a
rm1
rn
项目投资：财团或银行把资金投入到若干 项目中以获得中长期的收益最大。
整数规划

第六讲 整数线性规划的其他典型应用(一)

第六讲 整数线性规划的其他典型应用(一)

第六讲 整数线性规划的其他典型应用（一）一、人员分配问题公交公司司机人数的优化配置问题（每位司机连续工作两个班次）解：设第i 个班次开始上班的司机人数为)6,,2,1( =i x i 。

654321min x x x x x x z +++++=⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧=≥≥+≥+≥+≥+≥+≥+6,,2,1,0302050607060655443322116 j x x x x x x x x x x x x x x j j 为整数，二、套材下料问题例5 制造某种机床，需要A ，B ，C 三种轴件，其规格与数量如下表所示。

各类轴件都用5.5米长的同一种圆钢下料。

若计划生产100台机床，问：① 如何下料，所用圆钢根数最少？② 如何下料，可使余料最少？试分别建立线性规划模型。

解：（1）一次性拿整根的截出各自的长度100+50+88=238（贪婪解）将所有可能的下料方法列表（字典排法，将一根原料截成不同长度）设按第j 种方法下料的圆钢根数为x j ，则上述问题可用如下的线性规划方法求解。

54321min x x x x x z ++++=⎪⎪⎩⎪⎪⎨⎧=≥≥+++≥++≥+5,,2,1,04004222002100543243121 j x x x x x x x x x x j（2）设按第j 种方法下料的圆钢根数为x j ，问题（2）可用如下的线性规划方法求解。

4002.12001.21001.35.5min 51⨯-⨯-⨯-⨯=∑=j j x z⎪⎪⎩⎪⎪⎨⎧=≥≥+++≥++≥+5,,2,1,04004222002100543243121 j x x x x x x x x x x j问题：什么时候用料最省？问题（1）和问题（2）在实际生活中是不是一个问题？三、生产与存贮问题（零库存就最好吗？）某公司与用户签订了4个月的交货合同如下：1月份1百台，2月份2百台，3月份5百台，4月份3百台。

该公司的最大生产能力为每月4百台。

线性规划Lindo软件-整数规划

线性规划Lindo软件-整数规划

定制化不足
对于特定领域的整数规划问题， 可能需要针对具体问题对软件进 行定制化开发。
未来研究的方向与展望
算法改进
随着计算技术的发展，未来可以进一步优化 Lindo软件的算法，提高求解速度和精度。
扩展应用领域
随着整数规划问题的多样化，未来可以进一步拓展 Lindo软件的应用领域，如金融、物流、能源等领 域。
整数规划的求解方法
分支定界法
通过不断分割可行解空间和排除不可行解空 间来逼近最优解。
割平面法
通过逐步构建整数解来逼近最优解，适用于 小规模问题。
回溯法
通过添加割平面来缩小可行解空间，最终找 到最优解。
Lindo软件求解法
使用Lindo软件进行整数规划求解，具有高效 、稳定、易操作等优点。
04
使用Lindo软件进行整数规划
在求解结果查看界面中，可以查看问题的最优解、最优值、变量取值等信 息。
可以使用软件提供的图表功能，绘制变量取值与目标函数之间的关系图， 以便更好地理解问题的解。
05
案例分析
案例一：简单的整数规划问题
问题描述
01
考虑一个简单的整数规划问题，目标是最小化目标函数，同时
满足一系列线性约束条件。
解决方案
• 易用性：用户界面友好，操作简单，无需复杂的编程知识 即可使用。
Lindo软件在整数规划中的优势与限制
依赖性
Lindo软件的功能和性能高度依赖 于计算机硬件配置，高性能计算 机是求解大规模问题的必要条件。
模型限制
对于某些特殊类型的整数规划问 题，如非凸或非线性问题，Lindo 软件的求解效果可能有限。
在约束条件设置界面中，根据问题数据设置相 应的约束条件，如“less than”、“equal to”或“greater than”。

线性规划和整数规划应用举例解析

线性规划和整数规划应用举例解析

D
x43
12
2020/11/10
下面分析每年资金的使用情况并建立线性规划模型. 第1年初，有A, B两个项目，只能提供6万元资金，故有:
x11 x21 6 .项目B不得超过5万元，有 x21 ≤5；
A2 7 9 17 14 10
A3 6 9 12 8 7
解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看 成两家建筑公司，其系数矩阵为
B1 B2 B3 B4 B5
4 8 4 8 7 9 7 9 6 9 6 9
7 15 12 A1
7
15
12
A1'
17 14 10 A2
17 14 10 A2'
各区之间消防车行驶的时间见下表。请为该市 制定一个最节省的计划
解：xi
1
0
在第i个地区建站 不在第i个地区建站
i=1,2, …,6
Z表示全区消防站总数
地1 2 3 4 5 6 区
1 0 10 16 28 27 20
2 10 0 24 32 17 10 3 16 24 0 12 27 21
布点问题模型：
线性规划在国内外很多部门的规划、管理、决策过程中有大 量成功的应用，并收到了良好的效果.但是，应用线性规划来解 决某一类实际问题时，由于问题的复杂性和情况的多变性，要 真正建立一个反映实际问题的、能得出正确结论的理想模型， 并不是一件容易的事情.它要求建模者具有丰富的经验、较强的 创造力和比较熟练的技巧.本节通过一些被简化了的问题，介绍 建立线性规划模型的基本思路和基本技巧.
(i,j=1,2,…, n)
数学模型为:
nn
min Z cij xij
i 1 j 1

整数规划方法

整数规划方法
4
一、整数规划的一般模型
2. 整数规划模型的一般形式
max(min) z c j x j
j 1 n
(A)
n aij x j (, )bi (i 1,2, , m) j 1 x 0, x 为整数( j 1,2, , n) j j
•问题是如何求解整数规划问题呢？ •能否设想先略去决策变量整数约束，即变为线性 规划问题求解，再对其最优解进行取整处理呢？ •实际上，可借鉴这种思想来解决整数规划问题．
2.45=2+0.45 -2.45=-3+0.55
代入上式整理得：
xi N ik xk N i f i f ik xk
k k
令上式的右边小于等于零，得到切割方程。即：
f i f ik xk 0
k
3. 将切割方程化为下列形式：
f ik xk xn i f i
x5
0 0 1 0 1 -1/3 -4/3
1 1 0
1 1 1
0 1 0 0
－2/3
注释： （1）本题注只用一次割平面就求得了最优解，但大多数问题中 不是只用一、二次割平面就能求得整数最优解。若一次割平面不 能求得整数最优解，则按步骤2中的4个步骤，在松弛问题的最终 单纯形表中找出第二个割平面方程，将此割平面方程加到伴随规 划中，过程伴随规划，再用对偶单纯形法(单纯形法)求解。若求 得了整数最优解，则停止计算，否则继续再作割平面，缩小可行 域，直到求得整数最优解为止。 （2）实际解题时，经验表明若从最终单纯形表中选择具有最大 分数部分的非整分量所在行构造割平面约束，往往可以提高“切 割”效果，减少“切割”次数。 （3）在用割平面法解整数规划时，常会遇到收敛很慢的情形， 因此实际中通常不单独使用。

整数规划典型问题实例

整数规划典型问题实例

2. 所用原料钢管总根数最少
决策 变量 xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7) 目标1（总余量） Min Z 1 3 x 1 x 2 3 x 3 3 x 4 x 5 x 6 3 x 7
模 式 1 2 3 4 5 6 7 需 求 4米 根数 4 3 2 1 1 0 0 50 6米 根数 0 1 0 2 1 3 0 20 8米 根数 0 0 1 0 1 0 2 15 余 料 3 1 3 3 1 1 3
m in f 0 .1 x1 0 .3 x 2 0 .9 x 3 0 x 4 1 .1 x 5 0 .2 x 6 0 .8 x 7 0 .4 x 8
x8
2 x1 x 2 x 3 x 4 1 0 0 2 x 2 3 x3 3 x5 2 x6 x7 1 0 0 s .t . x1 x 3 3 x 4 2 x 6 3 x 7 4 x 8 1 0 0 x 0, i 1, 2, 3, 4, 5, 6, 7 , 8, x 取 整 i i
8米1根
8米1根
合理切割模式的余料应小于客户需要钢管的最小尺寸
钢管下料问题1
模式 1 2 3 4 5 6 7 4米钢管根数 4 3 2 1 1 0 0
合理切割模式
6米钢管根数 0 1 0 2 1 3 0 8米钢管根数 0 0 1 0 1 0 2 余料(米) 3 1 3 3 1 1 3
为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？ 两种 标准 1. 原料钢管剩余总余量最小
建立模型：
m ax
f
cx
i i 1
7
i
7 bi x i b i 1 x1 x 2 x 3 2 s .t . x 4 x 5 1 x x 1 7 6 x i 0 或 1, i 1, 2， . . . , 7

MBA数据模型与决策：整数规划

MBA数据模型与决策：整数规划
得的奖品最值钱。
§8.1.1 问题举例
▪ 表8-1 商品（奖品）信息
编号 1 2 3 4 5 6 7 8 9 10 11 12
商品名称 本地啤酒 无籽西瓜
毛毯 食用油
火腿 橙汁 飞标盘 铸铁炒锅 优质苹果 东北大米 卷筒纸 洗涤液
重量（Kg/件） 6 5 4 9 3 2 3 6 15 20 2 3
在应用Excel求解0-1整数规划时，同整数规划的求解相类 似，只是在0-1变量的约束添加时略有不同。
整数规划
▪ 在实际应用问题中，我们会常遇到要求问题的决 策变量全部或部分是整数的情况，如问题的决策 变量表示的是人数、汽车量数、机器台数、以及 对事物的逻辑判断等，我们把这样的规划问题称 为整数规划问题（Integer Programming, IP）,特 别地，当这个问题是线性规划问题时就称为整数 线性规划问题（Integer Linear Programming, ILP）。由于本章只讲整数线性规划问题，所以在 以后的叙述中将其简称为整数规划问题。
▪ 在整数规划中，如果所有的决策变量都要求 是整数时，就称之为纯整数规划（Pure Integer Programming）或称之为全整数规划 （All Integer Programming）；如果只有部
分决策变量要求是整数，其它变量则不予限
制，这样的问题称之为混合整数规划(Mixed Integer Programming)。整数规划还有一种特 殊的形式，就是整数变量的取值仅限于0或1 ，这样的问题我们称之为0-1整数规划（0-1 Integer Programming）。
价格（元/件） 18 8 50 70 48 10 28 72 75 60 21 19
§8.1.1 问题举例

运筹学经典案例

运筹学经典案例

有关普拉夫家族的相关数据
• 劳动力提供：冬春两季可提供4000个人工秋；夏两季可 提供4500个人工。 可以利用富余劳动力赚取外快；冬、春季每小时5美 元，夏、秋季节每小时5.5美元； • 土 地 提供：640亩 • 种植三种农作物的每亩地的相关数据 ：
大豆 冬春季节 （人工数） 夏秋季节 （人工数） 1.0 1.4 玉米 0.9 1.2 小麦 0.6 0.7
理论综述
• 关键字：线性规划 影子价格 资源配臵 Lingo软件 • 名词解释： • 线性规划：指研究线性约束条件下线性目标函数的极值问 题的数学理论与方法。即对于统筹规划问题，为如何合理 地、有效地利用现有有限的人力、物力、财力资源来完成 更多的任务。或者如何才能以最少的代价去实现目标。作 出的最优决策，提供科学的依据。采用数学语言来描述： 问题的目标用变量函数的形式来表达（称为目标函数）， 问题的限制条件用有关变量的等式或不等式来表达。（称 为约束条件）当变量连续取值，且目标函数与约束条件均 线性时，称这类模型为线性规划模型。 • 影子价格：影子价格的含义就是资源单位增加量对最优值 的贡献大小，实际问题中资源的增加最坏也就是对最优解 没有贡献（相当于不用增加部分的资源），不会出现负影 响。
摘要
• 利用整数规划方法解决了场主在现有条件下，如何分配有 限的现金和劳动力使明年年底能够拥有最多的现金的问题 。得出结论： • 1.在明年种植414亩大豆，42亩玉米，100亩小麦；饲养 42头牛，2000只鸡可获得最大货币资产102811.0美元 。 • 2.通过分情况讨论，发现不管天气情况如何，购买尽可能 多的牛能赚更多的钱。所以普拉夫家族应该购买牛至42头 (最大容量)；至于作物的种植量，普拉夫家族可以先去咨 询当地的气象站再根据实际情况作出决定，当得知未来可 能发生某种灾害天气时，就可以参考分析结果 ，进行资金 和劳动力的分配；如果未来的天气情况无法预测，为了尽 可能减少未来可能存在的损失，普拉发家族应该走一个稳 健的种植路线：种植更多小麦，同时也可以购进一些鸡。 • 3.使用lingo做敏感性分析之后可以看出资金的影子价格为 0，因此不需要贷款。

整数规划

整数规划

Maxz=100x1+200x2 8x1+8x2<=24 2x1+6x2<=13 x1,x2>=0 x1,x2为整数
整数规划问题的基本描述及解决方法
分枝定界法求解例：
LP(1)
X1=1.25 x2=1.75 Z=475 X2<=1 X2>=2
LP(2)
X1=2 x2=1 Z=400 X1<=0
零件1
设备A 设备B 50 30
零件2
80 100
零件3
90 50
零件4
40 70
整数规划问题的应用案例分析求解
混合整数规划问题：
4、约束条件有n种可能值：约束方程右端不是一 个固定的常数，而是有k种可能的值的组合。在 约束条件中通常表示为：
a1x1+a2x2+…+anxn=b1y1+b2y2+…+bnyn
• 分别求出各分枝问题的最优解。若其最优解仍为非整数
解，继续分枝；若其最优解为整数解，以此整数解的目 标函数值为下界，判定哪个整数解为最优解。
方法要点：
• 变量的选取：优先选取较大分数值的变量作为分枝变量 • 分枝的选取：优先选取目标函数值最大的分枝继续分枝
整数规划问题的基本描述及解决方法
如前例： 整数线性规划模型：
LP(3)
X1=0.5 x2=2 Z=450 X1>=1
LP(4)
X1=0 x2=13/6 Z=2600/6
X2<=2 X2>=3
LP(5)
无可行解
LP(6)
X1=0 x2=2 Z=400
LP(7)
无可行解
整数规划问题的基本描述及解决方法

管理运筹学案例演示混合整数规划

管理运筹学案例演示混合整数规划

yi
当 选 择 Ai 地 建 厂 时; 当 不 选 择 Ai 地 建 厂 时 。
约束条件: A1产量限制条件;及A2、 A3、 A4、 A5准备建设的新厂, 其产量约束条件；
满足销量的约束条件；
目标函数: 总的固定成本和总的运费之和最小。
（2）在上述模型的基础上加上一个约束条件，即：
y2 ? y3 ? 1
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。
该广告计划模型为：
max z ? 40x1 ? 90x2 ? 50x3 ? 2x4
D Goal Programmingmic Programming
E Transportation Programming
1 2 3 4 5 6 7 N Simulation
F Assignment
123456
8 9 10 11 12 O Forecasting
G Break-Even Analysis
x1 ? y1M x2 ? y2 M x3 ? y3 M
目标函数： 为扣除固定费用的利润最大化，即：
4x1 ? 5x2 ? 6x3 ? 100y1 ? 150y2 ? 200y3
该生产计划整数规划模型为：
max z ? 4x1 ? 5x2 ? 6x3 ? 100 y1 ? 150 y2 ? 200 y3

数学建模-整数规划

数学建模-整数规划
数学建模
整数规划
Integer Programming
数信学院 任俊峰
2012-4-15
数学建模之整数规划
整数规划模型（IP）
如果一个数学规划的某些决策变量或全部决策 变量要求必须取整数，则称这样的问题为整数规 划问题，其模型称为整数规划模型。 如果整数规划的目标函数和约束条件都是线性 的，则称此问题为整数线性规划问题.
松弛问题最优解满足整数要求，则该最优解为整数 规划最优解；
数学建模之整数规划
整数线性规划的求解方法
从数学模型上看整数规划似乎是线性规划的 一种特殊形式，求解只需在线性规划的基础上，通 过舍入取整，寻求满足整数要求的解即可。 但实际上两者却有很大的不同，通过舍入得到
的解（整数）也不一定就是最优解，有时甚至不能
1 xj 0
选中第j个项目投资 不 选中第j个项目投资
max Z 160 x 1 210 x 2 60 x 3 80 x 4 180 x 5 210 x 1 300 x 2 150 x 3 130 x 4 260 x 5 600 x x2 x3 1 1 x3 x4 1 x x 1 5 x1 , x 2 , x 3 , x 4 , x 5 0 或 1
1 2
14 x1 9 x 2 51 6 x1 3 x 2 1 x1 , x 2 0
数学建模之整数规划
用图解法求出最优解 x1＝3/2, x2 = 10/3 且有 z = 29/6 现求整数解（最优解）： 如用“舍入取整法”可得到4 个点即(1，3) (2，3) (1，4) (2，4)。显然，它们都不可能 是整数规划的最优解。
数学建模之整数规划
例5 固定费用问题

2.运筹学_整数规划案例

2.运筹学_整数规划案例
1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可 供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j ＝ 1，2，…，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行 投资？ 1…对项目j投资 先引入0－1变量xj，令 xj＝ 0…否则 n
设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－ 1变量yi= 1表示在Ai设立仓库，否则不设。 设每个月的总花费为z，则上述问题的数学模型为 Min z＝200x11+400x12+500x13+300x21+250x22+450x23 +600x31+400x32+250x33+300x41+150x42+350x43+45000y1+5000 0y2+70000y3+40000y4 s.t. x11+x12+x13≤1000y1 x21+x22+x23≤1000y2 x31+x32+x33≤1000y3 x41+x42+x43≤1000y4 x11+x21+x31+x41≥600 x12+x22+x32+x42≥700 x13+x23+x33+x43≥800 y2-y4≤0 y1+y2+y3+y4≤3
y3+y4 ≤ 1
工厂选址运输问题
设有n个需求点，有m个可供选择的厂址， 每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。

线性规划和整数规划应用举例解析

线性规划和整数规划应用举例解析

15
2020/11/10
投资机会
项目名称
A B C D
最优投资方案
第1年年初
X11=1 X21=5
第2年年初 X12=1.2 X32=0
第3年年初 X13=7.44
X43=2
16
2020/11/10
例6. 某公司面临一个是外包协作还是自行生产的问题.该 公司生产甲、乙、丙3种产品，这3种产品都要经过铸造、机 加工和装配3个车间.甲、乙两种产品的铸件可以外包协作， 也可以自行生产，但产品丙必须本厂铸造才能保证质量.有 关情况见表2.15.该公司中可利用的总工时为：铸造8000小时、 机加工12000小时和装配10000小时.为使该公司获得最大利 润，甲、乙、丙3种产品应各生产多少件？甲、乙两种产品 由本公司铸造多少件？外包协作铸造多少件？
A2 7 9 17 14 10
A3 6 9 12 8 7
解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看 成两家建筑公司，其系数矩阵为
B1 B2 B3 B4 B5
4 8 4 8 7 9 7 9 6 9 6 9
7 15 12 A1
7
15
12
A1'
17 14 10 A2
17 14 10 A2'
19
2020/11/10
建立此问题的线性规划模型如下：
max f 15x1 10x2 7x3 13x4 9x5
s.t. 5x1 10x2 7x3 8000
（铸造工时约束）
6x1 4x2 8x3 6x4 4x5 12000 （机加工工时约束）
3x1 2x2 2x3 3x4 2x5 10000 （装配工时约束）
总数.
这里可以把连续休息2天的售货员按照开始休息的时间

数学建模案例之整数规划

数学建模案例之整数规划
数学建模案例之整数规划
内容： 如何建立整数规划模型举例 整数规划模型的求解方法 要求： 掌握整数规划模型的建立方法 掌握利用数学软件求解整数规划问题的方法 理解分支定界法的思想和实施步骤 重点、难点： 重点: 整数规划模型的建立和软件求解 难点: 整数规划问题的理论求解方法__分支定界法
简介
最优化问题中的所有变量均为整数时，这类问题称 为整数规划问题 如果线性规划中的所有变量均为整数时，称这类问 题为整数线性规划问题 整数规划可分为整数线性规划和整数非线性规划， 以及混合整数规划等 混合整数规划指部分变量可以取非整数的整数规划 (混合整数线性规划问题还没有统一的解法)
模型求解：
Lindo 程序（总根数最小）
min x1+x2+x3+x4+x5+x6+x7 s.t. 4x1+3x2+2x3+x4+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15 end gin 7
计算结果（总根数最小）
OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000

运筹学整数规划案例

运筹学整数规划案例

0-1变量的作用
1…方案j被选中 1. xj＝
0…方案j未被选中
n
2. 从n个方案中必须选中一个： x j 1 j 1 n
3. 从n个方案中最多选中m个： x j m j 1
4. 方案i只有在方案j选中时，才可能被选中：
xi x j
5. 方案i与方案j是否选中是同时的： xi x j
解：
令0-1变量为决策变量，即xi＝1表示选中项目i， 否则xi＝0表示项目i未被选中。则模型可以表示为：
max z= 150x1 +210x2 +60x3 +80x4 +180x5
s.t.
210x1 +300x2 +100x3 +130x4 +260x5 ≤600
x1
+x2
+x3
=1
x3
+x4
=1
0y2+70000y3+40000y4
s.t.
x11+x12+x13≤1000y1
x21+x22+x23≤1000y2
x31+x32+x33≤1000y3
x41+x42+x43≤1000y4
x11+x21+x31+x41≥600
x12+x22+x32+x42≥700
x13+x23+x33+x43≥800
y2-y4≤0
y1+y2+y3+y4≤3
y3+y4 ≤ 1
工厂选址运输问题
设有n个需求点，有m个可供选择的厂址， 每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。

整数规划应用案例分析

整数规划应用案例分析

投资项目的选择
利用线性规划可以来完成资金预算决策，决定对 不同项目投资额各是多少。但实际中，一些资金预算决策不是决定投资多少，而是是否进行一些固定金额的投资。
管理层必须经常面对的是：在预投入资金额度一定的情况下，是否进行一项或几项固定投资。
对每个是或否的决策： 1，是
引入决策变量x= 0，否
第四章 整数规划的应用
练习 (兼职值班)
例6.东方大学计算机实验室聘用4名大学生(代号1,2,3,4)和2名研究生(代号5,6)值班答疑.已知每人从周一至周五每天最多可安排的值班时间及每人每小时的值班报酬如下:
班次 报酬 每天最多可安排的值班时间 (元/时) 周一 周二 周三 周四 周五 1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3
设某公司在m个时段里有n项投资计划，由于资金限制不能全部进行。已知
第i个时段里该公司可动用的资金是b i，
第j项投资计划所需要的资金是a ij ,
能够得到的利润是c ij。 问该公司如何选择投资计划，使m个时段内的总利润最大。
例1 投资问题
表示第i个时段内选中第j个投资计划，
建立该投资问题的数学模型为：
问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?
01
03
02
解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0（当Ak 没被选中时),k =2,3,4,5．这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23 +4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 （其中前4项为固定投资额，后面的项为运输费用。） s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10 ( A2 厂的产量限制) x31+ x32+ x33 ≤ 20 ( A3 厂的产量限制) x41+ x42+ x43 ≤ 30 ( A4 厂的产量限制) x51+ x52+ x53 ≤ 40 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij ≥0，i = 1,2,3,4,5； j = 1,2,3， yk 为0--1变量，k =2,3,4,5。

整数规划案例

整数规划案例

整数规划案例目录例1固定费用问题 (1)例2选择性约束条件 (1)例3可行域描述问题 (2)例4 最优分配问题 (2)例5 选址问题 (2)例6 排序问题 (3)例7利润分段线性问题 (5)例8可靠性问题 (5)例9装配线平衡问题 (6)例10货物列车编组计划问题 (7)例1固定费用问题工厂准备生产Al、A2、A3三种产品。

若Aj产品投产，无论产量大与小，都需要一笔固定费用dj（例如装夹具的设计制作费用）。

而每生产一件产品，其利润为cj,试问固定费用这个因素如何体现在模型中而使总利润最大?（其它约束条件暂不列入）解设产品Aj的产量为xj,又设0—1变量yi=l （当xj>0）, 0 （否则）于是，目标函数为max 仁clxl+c2x2+c3x3・dlyl-d2y2・d3y3例2选择性约束条件某工厂生产第j种产品的数量为Xj,j=l, 2, 3。

其使用的材料在材料甲及乙中选择一种。

材料消耗的约束条件分别为2x1+5x24-6x3 W180 及4x1+3x2+7x3^240（其它资源约束未列出），试问这类选择性约束条件如何体现在模型中？解引进0—1变量y： y=0 （选择材料甲），0 （否则）。

这样，“或此或彼”相互排斥的约束条件就可化成下列两个约束条件：2xl+5x2+6x3W180+My,4x1+3 x2+7x3 W240+M（ 1-y）,其中M是充分大的正数。

可以看出，当y=0时，第二个约束变成4xl+3x2+7x3W240+M,由于M是充分大的正数，所以这个约束条件自动满足而不起作用，而第一个约束为2xl+5x2+6x3 W180,这意味着选择材料甲；反之，当y=l时，第二个约束起作用，第一个约束变为2xl+5x2+6x3W180+M不起作用，这意味着选择材料乙。

因此，借助0—1变量，材料选择的两种可能性就同时包括在一个模型中了。

一般地，假定在某种情况下要在P个约束条件中至少要选择q个约束条件得到满足，那么，我们引进P个0-1变量yi,则选择性的约束条件问题就化为.……例3可行域描述问题如何把图中的阴影部分所表示的可行域用联立的线性约束条件来描述?例4最优分配问题现有四部车床Ai（I=l,…，4）和四个零件Bj（j=l,…，4）,车床Ai加工零件Bj 所需时间tij（小时）由下表给出。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的 固定成本和总的运输费用之和最小?
销地 产地
A1 A2 A3 A4 A5 销量(千吨)
B1
B2
B3
产量(千吨)
8
43
30
5
23
10
4
34
20
9
75
30
10 4 2
40
30 20 20
解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时) 或0（当Ak 没被选中时),k =2,3,4,5．这可以表示为一个整数规划问题：
练习
例4.某钻井队要人以下10个可供选择的井位中确定5个
钻井探油,使总的钻探费用为最小,若10个井位的代号
为 c1, ,相c1应0 的钻探险费用为
要满足下列限制条件:
s,1并,且,井s1位0 选择上
①或选择 s和1 s,7或选择 s8
②选择了s3或 s就4 不能选 ,或s5 反过来也一
22+
3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53
（其中前4项为固定投资额，后面的项为运输费用。）
s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制) x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制) x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制) x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij ≥0，i = 1,2,3,4,5； j = 1,2,3， yk 为0--1变量，k
6
min z xi
x1

x2

70,

x2

x3

60,
s.t.x3 x4 50,

x4

x5

20,
x5 x6 30,

xi

0, 且为 整数(i
1,2,...,6).
MODEL: Sets: Num/1..6/:b,x; Endsets Data: b=60,70,60,50,20,30; Enddata [OBJ]min=@sum(num(i):x(i)); x(1)+x(6)>=60; x(1)+x(2)>=70; x(2)+x(3)>=60; x(3)+x(4)>=50; x(4)+x(5)>=20; x(5)+x(6)>=30;
对每个是或否的决策：
1，是
引入决策变量x=
0，否
例1 投资问题
• 设某公司在m个时段里有n项投资计划，由于资金限制不
能全部进行。已知
1)第i个时段里该公司可动用的资金是b i， 2)第j项投资计划所需要的资金是a ij , 3)能够得到的利润是c ij。
问该公司如何选择投资计划，使m个时段内的总利润最大。
1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3
该实验室开放时间为上午8:00至晚上10:00,开放时间 内须有且仅须一名学生值班.规定大学生每周值班不 少于8小时,研究生每周不少于7小时,每名学生每周值 班不超过3次,每次值班不少于2小时,每天安排的值班 学生不超过3人,且其中必须有一名研究生.试为该实验 室安排一张人员值班表,使总支付的报酬最少,
j 1
2)或选择 s1和 s,或7 选择 可表s8 示为
x1 x8 1, x7 x8 1
3)选择了 s3或 就s4不能选 ,反过s5来也一样,
可表示为 x3 x5 1, x4 x5 1
4)在 s5 , s6 , s中7 , 最s8多只能选两个可表示为
x5 x6 x7 x8 2
i 1,2, , m
投资项目的选择
例2. 华美公司有5个项目被列入投资计划，各项目 的投资额和期望的投资收益见下表：
项目 投资额(万元)
投资收益(万元)
1
210
150
2
300
210
3
100
60
4
130
80
5
260
180
该公司只有600万元资金可用于投资，由于技术原因， 投资受到以下约束： 1）在项目1、2和3中必须有一项被选中； 2）项目3和4只能选中一项； 3）项目5被选中的前提是项目1必须被选中。 如何在上述条件下，选择一个最好的投资方案，使收 益最大。
=2,3,4,5。
模型检查！是否有问题？
解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选中时)或0（当Ak 没被选中时),k =2,3,4,5．这可以表示为
一个整数规划问题：
Min z
=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x


xij 8(i 1,..,4)大学生每周值班不少于8小时
j 1

5

xij 7(i 5,6)研究生每周值班不少于7小时

j 1
s.t.
6
xij 14( j 1,..,5)实验室每天开放14小时
i 1
5
xij 7(i 5,6)研究生每周值班不少于 7小时
j1


6
xij 14( j 1,..,5)实验室每天开放 14小时

i 1 5


yij 3(i 1,..,6)每名学生一周不超过 3次
s.t.

j 1 6
yij
i 1
3( j 1,..,5)每天值班不超过 3人
样
③在s5 , s6 , s中7 ,最s8多只能选两个.
试建成立这个问题的整数规划模型
解: 设决策变量
1, x j 0,
选择钻探第s j 井位 否则
10
目标函数为 min Z c j x j j 1
约束条件: 1)从10个可供选择的井位中确定5个探油,则
10
xj 5
第四章 整数规划应用案例分析
第四章 整数规划的应用
一、投资项目的选择
利用线性规划可以来完成资金预算决策，决定对 不 同项目投资额各是多少。但实际中，一些资金预算决策 不是决定投资多少，而是是否进行一些固定金额的投资。
管理层必须经常面对的是：在预投入资金额度一定的 情况下，是否进行一项或几项固定投资。
解：设x ij表示在第i个时段内对第j个投资计划的决策变量。
表1示第i个时段内选中第j个投资计划， xij 0 表示第i时段内未选中第j个投资计划。
建立该投资问题的数学模型为：
mn
max z
cij xij
i1 j1

s.t.
n j i
aij xij
bi
xij 0,1
班次 1 2 3 4 5 6
时间段 需要人数 6:00-10:00 60 10:00-14:00 70 14:00-18:00 60 18:00-22:00 50 22:00-2:00 20 2:00-6:00 30
解:设分别表示第i个班次开始上班的人数,每个 人连续值班8小时.根据题意所求问题归结为如 下整数规划的数学模型:
解: 设 xij为学生 i在周j的值班时间, yij 0,
否则
分析约束条件:
2 yij xij aij yij (i 1,..,6; j 1,..,5)不超过可安排的时间 5




xij 8(i 1,.., 4)大学生每周值班不少于 8小时
j 1
5
班次 报酬 每天最多可安排的值班时间 (元/时) 周一 周二 周三 周四 周五
1 10.0 6 0 6 0 7 2 10.0 0 6 0 6 0 3 9.9 4 8 3 0 5 4 9.8 5 5 6 0 4 5 10.8 3 0 4 8 0 6 11.3 0 6 0 6 3
1, 安排学生i在周j的值班时间
3,4只能选中一项
x5 x1
5被选中前提是1选中
xi=1或0(i=1,…,5)
解得（1，0，0，1，1）
Max Z=410
即投资项目1、4、5，可以获 得410万元。
二、分布系统设计-选址问题
在如今的全球经济中，许多公司正在全世界各个地 方建立新工厂，为的是获得低劳动力成本等好处。
在为新工厂选址之前，需要分析和比较地点。每个可 供选择的地点都涉及一个是或否的决策。

y5 j

y6 j
1( j
1,..,5)每天有一名研究生值班

xij