当前位置：文档之家 › 第六章---运筹学-整数规划案例

第六章---运筹学-整数规划案例

  • 格式：doc
  • 大小：199.00 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

运筹学-整数规划

运筹学-整数规划

整数线性规划
篮球队选队员问题
篮球队要选择5名队员上场组成出场阵容参加比赛。

8名篮球队员的身高及擅长
(1) 只能有一个中锋上场；
(2) 至少有一名后卫；
(3) 若1号和4号都上场,则6号不出场；
(4) 2号和8号至少保留一个不出场。

提问：应当选择哪5位上场，才能使出场的五名队员平均身高最高？
分析与求解：
0-1整数规划问题
设0-1变量x i
x i =第名队员未选上第名队员被选上
设第i名队员的身高为a i（i=1,2……,8），则目标函数为：建立模型的限制条件为：
使用MATLAB的intlinprog函数求解0-1规划问题，代码如下：
f=[-0.384 -0.380 -0.376 -0.372 -0.370 -0.366 -0.360 -0.356 ];
A=[1 1 0 0 0 0 0 0
0 1 0 0 0 0 0 1
1 0 0 1 0 1 0 0
0 0 0 0 0 -1 -1 -1];
b=[1;1;2;-1]
aeq=ones(1,8)
beq=5
intcon=8
lb = zeros(8,1);
ub = ones(8,1);
x=intlinprog(f,intcon,A,b,aeq,beq,lb,ub)
求解结果：
LP: Optimal objective value is -1.864000.
x =
1
1
1
1
1
即第2、3、4、5、6名队员被选上。

最大平均身高为1.864米。

《运筹学》之整数规划

《运筹学》之整数规划

…
Bn
…
X1n
…
X2n
……
…
Xnn
指派问题：分配要求
分配 B1 B2 … Bn 工作数
A1
X11
X12
… X1n
∑X1j
A2
X21
X22
… X2n
∑X2j
…
…
…
……
…
An 人数 要求
Xn1 ∑Xi1 1
Xn2 ∑Xi2 1
… Xnn … ∑Xin …1
∑Xnj
要求 1 1
… 1
指派问题：模型
n n
X1 1
P1:(1,9/10 X2 2 X2 3 P12: (0,3) Z=9
原问题的最优解（1，2） Z=10。
指派问题
设有n 个人A1, A2, …An,要分派去做n件事B1, B2… Bn,要求每一件事都 必须有一个人去做,而 且不同的事由不同的人去做.已知每个人Ai做每 件事Bj的效率(如劳动工时或成本,或创造的价值 等)为Cij,问应如何进行指派(哪个人做哪件事),才 能使 工作效益最好(如工时最少,或成本最低,或 创造的价值最大)?
乙
19 23 22 18
丙
26 17 16 19
丁
19 21 23 17
指派问题：思考问题
1、人数比工作数多怎么处理？ 2、人数比工作数少，模型会怎
样变化? 3、计算机求解方法？
特殊约束的处理
➢互斥约束 ➢矛盾约束 在建立数学模型时，有时会遇到相 互矛盾的约束，模型只要求其中的 一个约束起作用。
12 8
x5
6 相机
2 4
x6
7 设备
4 10
x7

整数规划解法与实际案例分析

整数规划解法与实际案例分析

整数规划解法与实际案例分析整数规划是运筹学中的一个重要分支，它在实际问题中有着广泛的应用。

整数规划问题是指决策变量被限制为整数的线性规划问题，通常用于需要做出离散决策的情况。

在本文中，我们将介绍整数规划的基本概念和解法，并结合一个实际案例进行分析，以帮助读者更好地理解整数规划的应用。

### 整数规划的基本概念整数规划是一种特殊的线性规划问题，其决策变量被限制为整数。

一般来说，整数规划可以分为纯整数规划和混合整数规划两种情况。

纯整数规划要求所有的决策变量都是整数，而混合整数规划则允许部分决策变量为整数，部分为连续变量。

整数规划可以用数学模型来描述，通常形式如下：$$\begin{aligned}\text{Maximize} \quad & c^Tx \\\text{Subject to} \quad & Ax \leq b \\& x \in \mathbb{Z}^n\end{aligned}$$其中，$c$、$x$、$b$ 分别为目标函数系数向量、决策变量向量和约束条件右端常数向量，$A$ 为约束条件系数矩阵，$x \in\mathbb{Z}^n$ 表示 $x$ 是一个整数向量。

### 整数规划的解法整数规划问题的求解相对复杂，因为整数约束使得问题的解空间不再是连续的，而是离散的。

针对整数规划问题，通常有以下几种解法：1. **穷举法**：穷举法是最直接的方法，即枚举所有可能的整数解，然后逐一计算目标函数值，找出最优解。

然而，穷举法在问题规模较大时会变得非常低效。

2. **分支定界法**：分支定界法是一种常用的整数规划求解方法。

它通过不断将整数规划问题分解为子问题，并对子问题进行求解，直到找到最优解为止。

3. **割平面法**：割平面法是一种基于线性规划的整数规划求解方法。

它通过不断添加线性不等式约束（割平面）来逼近整数解，直到找到最优解为止。

4. **分支定价法**：分支定价法是一种高级的整数规划求解方法，通常用于解决混合整数规划问题。

运筹学课件 第六章-整数规划3

运筹学课件 第六章-整数规划3

物品 1 2 3 4 5 6 7 8 9 10
体积 200 350 500 430 320 120 700 420 250 100
价格 15 45 100 70 50 75 200 90 20 30
设变量xij为第i个物品是否放在第j个包裹中
xij 1,0; i 1,2...,17, j 1,2,3
• 保证需求约束
x11 + x21 + x31 = 450 x12 + x22 + x32 = 275 x13 + x23 + x33 = 300 x14 + x24 + x34 = 350
} 项目1 } 项目2 } 项目3 } 项目4
最大供应量 525 450 550
约束条件：
厂家1一旦向某项目供应水泥，其至少供应量为150。 厂家2对单个项目供应量超过200吨的项目数不大于1。总产量=450 厂家3仅接受 200, 400, 和 550 吨这三个规格的货单。
1 中锋 1.93 2 中锋 1.91 3 前锋 1.87 4 前锋 1.86 5 后卫 1.80 6 后卫 1.85
配送计划模型
• 某建筑公司为完成4个工程项目，需要从3个厂家购买水泥，有关成
本如下
厂家1 厂家2 厂家3 需求量(吨)
项目1 $120 $100 $140 450
水泥的吨运费
项目2 $115 $150 $95 275
xi
0, 不携带第i件物品 1, 携带第i件物品 (i
1,2,, m)
m
max z ci xi i 1
m

ai xi
a
st.
i 1 m
bi

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

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

1 2 3 4 5 6 7 8 9 10 11 J CPM/PERT
B Integer Programming
1234567
K Inventory Models
C Zero One Programming
1234567
L Queueing Theory
D Goal Programming
12345678
H Decision Theory
Q Game Theory
I Network Models
ESC Exit to Dos
123
总目录
例1.(投资问题 )某厂要制订一个产品宣传计划，可利用的广告渠 道有三种：电视、广播、杂志。市场调研的结果如下表所示。该 厂计划用于广告费用不超过 16万元。此外还要求：（ 1）受到广 告影响的妇女至少要有200千人；（2）电视广告费用不超过10万 元；（3）白昼电视至少要订 3个广告，热门时间至少 2个广告； （4）广播和杂志上的广告数都应在5到10之间。该厂如何制订一 个广告计划使受到影响的总人数最多。
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。
该广告计划模型为：
max z ? 40x1 ? 90x2 ? 50x3 ? 2x4
金属板吨劳动力人月机器设备台月小号容器中号容器大号容器不考虑固定费用每种容器售出一只所得的利润分别为4万元5万元6万元可使用的金属板有500吨劳动力有300人月机器有100台月此外不管每种容器制造的数量是多少都要支付一笔固定的费用

第六章 整数规划(应用运筹学)

第六章 整数规划(应用运筹学)

x2≥3
线性规划B6 Z5=6 x1=0 , x2=3
z6
z 6
§3 0—1规划Binary integer programming
当我面临是与非两种选择时，我们可以用决策变量取0或1值来表示 这样的决策，这样，地j个是非决策问题可以表示成
if decision j is yes, 1 如果决策是 xj if decision j is no 0 如果决策是非
x2 3 2 1 2x1+3x2 =6 o 1 2 3 4 x1 2x1+3x2 =14 2x1+3x2 =14.66
得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。
性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目
B0
max z =x1+2x2 s.t. 2x1+5x2 ≤ 15 2x1－2x2 ≤5 x1 , x2≥0
x2为整数的限制条件，得规 划B0对应的最优解与最优 值如下，而 X=(0，0)为A0 3 的可行解 B0 13 3 T 11 X (3 ,1 ) , z 6 14 7 14
2x1＋5x2=15
(1)每求出一次符合整数的解，都要考虑修改下界
函数值最大者为新的下界 (2)修改
z
，选整数解的目标
z
0
z ，找出所有未 分枝问题目标函数值最大者，为新的上界 z 当改变完上、下界 z ，z 后，若 z ＝ z，则所有分枝均已查明，得到 A
的最优解， 若
z＞ z
，则说明仍有分枝未查明，返回到第四步
分枝定界法
分枝定界法步骤

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


? ?
1 1
? ?
y4
?
1
??x1, x2, x3, x4 ? 0, yj ? 0 , j ? 1,2,3,4
用QM软件求解结果如下：
最优方案 :装配线A生产100件,装配线 B生产1400件,装配线 C 生产1000件,装配线D生产1500件;
例3.(固定成本问题)高压容器公司制造小、中、大三种尺寸的金属 容器，所用资源为金属板、劳动力和机器设备，制造一个容器所 需所需的各种资源的数量如下表：
?8x1 ? 15x2 ? 6x3 ? 3x4 ? 160 ??30x1 ? 40x2 ? 20x3 ? x4 ? 200
???8x1x1??315x2 ? 100
? ?
x2
?
2
?5 ? ?5
? ?
x3 x4
? 10 ? 10
?? xj ? 0 , j ? 1,2,3,4 , 整数
用QM软件求解结果如下：
使用计算机软件包求解(附件1)
A Linear Programming
1 2 3 4 5 6 7 8 9 10 11 J CPM/PERT
B Integer Programming
1234567
K Inventory Models
C Zero One Programming
1234567
L Queueing Theory
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。

运筹学基础-整数规划(2)


【例 2 】求解 0-1 规划最优解
minZ= 4x1+3x2 +2x3 2x1 -5x2+3x3 ≤4 (1) 4x1 + x2+3x3 ≥3 (2) x2+x3 ≥1 (3) x1 , x2 , x3 =0或 1
解： 先将问题化为如下的标准问题
minZ= 4x1+3x2 +2x3 2x1 － 5x2+3x3 ≤4 (1) － 4x1 － x2 － 3x3 ≤－3 (2) (3) － x2 － x3 ≤ － 1 x1 , x2 , x3 =0或 1
0 13 aij－列min 6 (0) 0 (0) 5 0 0 1 (0) 7 0 6 9 3 2 0 (0) 0 2 15 10 4 9 14 7 8 13 14 16 11 4 15 13 9
（a）从行开始，对只有一个的零元素，打上（），用直线划去所在列 （b）再从列开始，对只有一个的零元素，打上（），用直线划去所在行
∑ ∑
指派问题的解法－－匈牙利法 指派问题的解法－－匈牙利法 －－
从时间表（效率表）出发构建效率矩阵 效率矩阵。 效率矩阵
时间表
任务 人员 甲 乙 丙 丁 E 2 10 9 7 J 15 4 14 8 G 13 14 16 11 R 4 15 13 9
2 15 10 4 9 14 7 8
13 14 16 11
分配表
任务 人员 甲 乙 丙 丁
合计
E x11 x21 x31 x41 1
i
J x12 x22 x32 x42 1
G x13 x23 x33 x43 1
ij x ij
R x14 x24 x34 x44 1
合计
1 1 1 1

运筹学 第六章 整数规划 第一讲 整数规划数学模型与纯整数规划的求解

项目 所需资金（万元） 收益期望值（万元）
A B C D E
6 4 2 4 5
10 8 7 6 9
A，B，C，D，E 之间的关系是： ① A、C、E 三项中需且只能选一项； ② B、D 两项中需且只能选一项； ③ 选 C 必须先选 D 。 问题：如何选择投资决策，使总投资期望值最大？
6.1 整数规划的数学模型 Mathematical Model of IP
① 求解LP : 如果LP无最优解, 则IP无最优解;
设LP的最优解为x , 最优值为z , 则IP的最优值z * 满足 :
z z* z
其中 z 为IP在任何一个可行解处的目标值.
② 检验与分支：
如果x 满足IP的整数要求, 则x为IP的最优解：z* z . 否则 考虑一个不满足整数要求的xr , 将约束
示不安排第i人去做 j工 作。逻辑变量也是只允许取整数值的一类变量。
整数线性规划数学模型的一般形式：
max Z (或 min Z ) c j x j
j 1 n
要求一部分或全部决策变量取整数值
n a ij x j bi ( i 1.2 m ) j 1 x j 0 (j 1.2n) 且 部 分 或 全 部 为 整 数
xr xr 和
xr xr 1
分别加入LP形成两个子问题 a] ([
不超过a的最大整数)
6.2 纯整数规划的求解 Solving Pure Integer Programming
Ch6 整数规划 Integer Programming
n
max
z cj xj
j 1
ij j
不考虑整数条件，由余下的目标函数和 约束条件构成的规划问题称为该整数规 划问题的松弛问题。

运筹学--整数规划 ppt课件


三、投资问题
某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末
回收本利115%，但要求第一年投资最低金额为4万元，第 二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％， 但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%， 但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利 息6%，此项投资金额不限。
= 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D =
1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D =
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以 保证当 yi = 0 时，xi = 0 。
这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 -
200y3
s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3
一、投资场所的选择
京成畜产品公司计划在市区的东、西、南、北四区建立销售
门市部，拟议中有10个位置 Aj ( j＝1，2，3，…，10)可供 选择，考虑到各地区居民的消费水平及居民居住密集度，规
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第六章整数规划用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。

1、 max z=3x1+2x2. 2x1+3x2≤122x1+x2≤9x1、x2≥0解：2、 min f=10x1+9x2. 5x1+3x2≥45x1≥8x2≤10x1、x2≥0求解下列整数规划问题1、 min f=4x1+3x2+2x3. 2x1-5x2+3x3≤44x1+x2+3x3≥3x2+x3≥1x1、x2、x3=0或1解：最优解（0，0，1），最优值：22、 min f=2x1+5x2+3x3+4x3. -4x1+x2+x3+x4≥2-2x1+4x2+2x2+4x2≥4x1+x2-x2+x2≥3x1、x2、x3、x3=0或1解：此模型没有可行解。

3、max Z=2x1+3x2+5x3+6x4. 5x1+3x2+3x3+x4≤302x1+5x2-x2+3x2≤20-x1+3x2+5x2+3x2≤403x1-x2+3x2+5x2≤25x1、x2、x3、x3=正整数解：最优解（0，3，4，3），最优值：474、 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≤30x4+ x5＋ x6-10 x16≤0x7+ x8＋ x9-20 x17≤0x10+ x11＋ x12-30 x18≤0x13+ x14＋ x15-40 x19≤0x1 + x4+ x7+x10+ x13＝30x2 + x5+ x8+x11+ x14＝20x3 + x6+ x9+x12+ x15＝20x i为非负数（i=1,2…..8）x i为非负整数（i=9,10…..15）x i为为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一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：公司办公会决定选择原则如下：（1）B5、B3和B7只能选择一个。

（2）选择了B1或B14就不能选B6。

（3）B2、B6、B1、B12，最多只能选两个。

（4）B5、B7、B10、B8，最少要选两个。

问应选择哪几个点，使总的建店费用为最低解：数学模型：min f＝ x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8+ x9+3 x10+ x11+ x12+ x13+ x14. x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8x3+ x5-2 x7=2x1+ x6=1x6+ x14=1x1+x2+x6+x12≤2x5+x7+x8+x10≥2x i≥0且x i为0－1变量，i＝1，2，3， (14)最优解：（1，1，1，1，1，0，0，0，1，0，0，0，1，1）最优值：。

即：B1，B2，B3，B4,B5,B9,B13,B14选中，建店的最低费用万元。

有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（A、B、C、D），请按以下要求求解指派问题。

1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少每人完成各项工作的所需时间小时2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最多解：1线性规划数学模型：min f=18x1+16x2+19x3+20x4+16x5+20x6+19x7+18x8+17x9+21x10+12x11+15x12+20x13. x1+x2+x3 =1x4+x5+x6=1x7+x8+x9+x10=1x11+x12+x13=1x1+x7+x11 =1x2+x4+x8 +x12 =1x5+x9+x13 =1x3+x6+x10 =1x i≥0且x i为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+3x11+5x12+7x13+6x14+8x15+8x16. x1+x2+x3 +x4 =1x5+x6+x7+x8=1x9+x10+x11+x12=1x13+x14+x15+x16=1x1+x5+x9 +x13 =1x2+x6+x10+x14=1x3+x7+x11+x15=1x4+x8+x12+x16=1x i≥0且x i为0－1变量，i＝1，2，3，…，16最优解：（0，0，0，1，1，0，0，0，0，1，0，0，0，0,1,0），最优值：28。

即：给甲分配工作D，给乙分配工作A，给丙分配工作B，给丁分配工作C，所创最多的利润为28元。

某企业在A1地已有一个工厂，其产品的生产能力为3万箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。

已知在A2地建厂的固定成本为万元，在A3地建厂的固定成本为30万元，在A4地建厂的固定成本为万元，在A5地建厂的固定成本为50万元，另外，五个产地建成后的产量、销地的销量以及产地到销地的单位运价（万元/万箱）如下表所示。

（1）问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小；（2）如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂解（1）整数规划数学模型：min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x40+7 x11+5 x12 +10 x13+4 x14+2 x15+ x16+30x17+ x18 +50 x19. x1 + x2+x3≤3x4+ x5＋ x6- x16≤0x7+ x8＋ x9-2x17≤0x10+ x11＋ x12-3x18≤0x13+ x14＋ x15-4x19≤0x1 + x4+ x7+x10+ x13＝3x2 + x5+ x8+x11+ x14＝2x3 + x6+ x9+x12+ x15＝2x i为非负整数(i=1,2…..15)x i为0－1变量(i=16,17…..19)最优解：（3，0，0，0，0，0，0，0，0，0，0，0，0，2，2，0，0，0，1）最优值：86。

即：安排A1地到B1地3万箱，A5地到B2，B3地各2万箱，选中A5地。

(2) 我们只要在以上模型上加上一个约束条件：x16+ x17=1，就得到了问题（2）的数学模型：min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x40+7 x11+5 x12 +10 x13+4 x14+2 x15+ x16+30x17+ x18 +50 x19. x1 + x2+x3≤3x4+ x5＋ x6- x16≤0x7+ x8＋ x9-2x17≤0x10+ x11＋ x12-3x18≤0x13+ x14＋ x15-4x19≤0x1 + x4+ x7+x10+ x13＝3x2 + x5+ x8+x11+ x14＝2x3 + x6+ x9+x12+ x15＝2x16+ x17=1x i为非负整数(i=1,2…..15)x i为0－1变量(i=16,17…..19)最优解：（0，1，2，0，1，0，0，0，0，3，0，0，0，0，0，1，0，1，0）最优值：94。

即：安排A1地到B2地1万箱，B3地2万箱A2地到B2地1万箱A4地到B1地3万箱A4地到B1地3万箱选中A2，A4两地。

某航空公司经营兰州、北京、广州三个城市之间的航线，其中兰州—北京飞行时间为2小时；北京—广州飞行时间为3小时；广州—兰州飞行时间为3小时；这些航线每天班机起飞与到达时间如下表：设飞机在机场停留期间的费用与停留时间的平方成正比，又每架飞机从降落到再起飞至少需要2小时的时间准备。

确定一个使总的停留费用损失为最小的方案。

解：现在有两本题需注意的两个问题1、三个城市间的飞行，航班的安排分别是在三个城市中完成的；2、到站的航班必须2小时后才能起飞。

这是一个指派问题，（1）城市兰州效益表：指派结果：（2）城市北京指派结果：（3）城市广州收益表：指派结果：用的最少时间为117 a。

某地区有两个镇，它们每周分别产生700吨和1200吨固体废物。

现拟用三种方式（焚烧、填海、掩埋）分别在三个场地对这些废物进行处理。

两城镇至各处理场所的运输费用、解：混合整数规划问题数学模型：min f=+21x2+21x3+17x4+++3850y1+1150y2+1920y3. x1+x2+x3=700x4+x5+x6=1200x1+x4-1000y1≤0x2+x5-500y2≤0x3+x6-1300y3≤0x i (i=1,2….6) y1、y2、y3=0—1结果：即两城镇处理固体废物的方案城镇1焚烧100吨，掩埋600吨城镇2填海500吨，掩埋700吨总的最小费用：46170元。

某建设公司有四个正在建设的项目，按目前所配给的人力、设备和材料，这四个项目将分别可以在15、20、18和25周内完成，管理部门希望提前完工，决定追加35000元资金分配给这四个项目，并规定追加资金只能以5000元为单位进行分配。

对于各个项目，资金追加后的工期变化情况如下表：解：本问题的0-1整数规划数学型：min f = 15x1+20x2+18x3+25x4+12x5+16x6+15x7+21x8+10x9+13x10+12x11+18x12+8x13+11x14+10x15+16x16+7x17+9x18+9x19+14x20+6x21+8x22+8x23+12x24+5x25+7x26+7x27+11x28+4x29+7x30+6x31+10x32. x1+x5+x9+x13+x17+x21+x25+x29=1x2+x6+x10+x14+x18+x22+x26+x30=1x3+x7+x11+x15+x19+x23+x27+x31=1x4+x8+x12+x16+x20+x24+x28+x32=10x1+1x5+2x9+3x13+4x17+5x21+6x25+7x29+0x2+1x6+2x10+3x14+4x18+5x22+6x26+7x30+0x3+1x7+2x11+3x15+4x19+5x23+6x27+7x31+0x4+1x8+2x12+3x16+4x20+5x24+6x28+7x32≤7x i≥0 (i=......32)用模板求解结果见《第六章习题》求得最小时间为55周，比不追加投资节省了（15+20+18+25）-55=23周。