当前位置：文档之家 › 整数线性规划

整数线性规划

  • 格式：ppt
  • 大小：586.00 KB
  • 文档页数：36

下载文档原格式

  / 36

合集下载

整数线性规划

整数线性规划

分枝定界法的理论基础：
1 2 k , i j (1) max cx max (max cx, max cx, , max cx)
x x1 x 2 x k
(2) 若 i j ，则 max cx max cx
xi xi x
分 枝
给定整数规划问题IP max z C T X
若x 的某个分量 xi 不是整数，
0
0
则将 IP分解为两个子问题
max z C X AX b X 0 X为整数向量 xi [ xi0 ]
T max z C X AX b X 0 X为整数向量 xi [ xi0 ] 1
记 z0 z
x1 4, x1 5
将问题B0分解为两个子问题B1和B2(分枝), 分别解B1,B2得 B1: x1=4, x2=2.10, z1=349 B2: x1=5, x2=1.57, z2=341
max z 40 x1 90 x2 max z 40 x1 90 x2 9 x1 7 x2 56 7 x 20 x 70 1 2 x1 4 B1 x1 , x2 0 9 x1 7 x2 56 7 x 20 x 70 1 2 x1 5 B2 x1 , x2 0
4、几点说明 (1)、如果要求目标的最大值
max z cij xij
令
bij M cij
i
j
其中
M max{ cij }
效率矩阵可变为B，将分配问题转换为一个极 小化问题
min z
'
b x
ij i j
ij
(2)、如果分配问题中，人员数 m 不等于工作数 n 时，可以类似于不平衡运输问题建立模型的 方法，增加虚拟人员或虚拟工作。

第5讲 整数规划、非线性规划、多目标规划1

第5讲 整数规划、非线性规划、多目标规划1

第5讲整数规划、非线性规划、多目标规划一、整数规划1、概念数学规划中的变量（部分或全部）限制为整数时，称为整数规划。

若在线性规划模型中，变量限制为整数，则称为整数线性规划。

整数规划的分类:如不加特殊说明，一般指整数线性规划。

对于整数线性规划模型大致可分为两类：1）变量全限制为整数时，称纯（完全）整数规划。

2）变量部分限制为整数的，称混合整数规划。

2、整数规划特点(i)原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例1原线性规划为21min x x z +=s.t.⎩⎨⎧≥≥=+0,05422121x x x x 其最优实数解为：01=x ，452=x ，45min =z ③有可行解（当然就存在最优解），但最优值变差。

例2原线性规划为21min x x Z +=s.t.⎩⎨⎧≥≥=+0,06422121x x x x 其最优实数解为：01=x ，232=x ，23min =z 若限制整数得：11=x ，12=x ，2min =z 。

（ii ）整数规划最优解不能按照实数最优解简单取整而获得。

3、0-1整数规划0−1型整数规划是整数规划中的特殊情形，它的变量j x 仅取值0或1。

这时j x 称为0−1变量，或称二进制变量。

j x 仅取值0或1这个条件可由下述约束条件：10≤≤j x ，且为整数所代替，是和一般整数规划的约束条件形式一致的。

在实际问题中，如果引入0−1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。

引入10-变量的实际问题：（1）投资场所的选定——相互排斥的计划例3某公司拟在市东、西、南三区建立门市部。

拟议中有7个位置（点）)7,,2,1( =i A i 可供选择。

规定在东区：由321,,A A A 三个点中至多选两个；在西区：由54,A A 两个点中至少选一个；在南区：由76,A A 两个点中至少选一个。

第四章 整数规划

第四章 整数规划
1、分配问题/指派问题：是一种特殊的 型整 、分配问题 指派问题 是一种特殊的 指派问题： 特殊的0-1型整 数规划问题 假定有m项任务分配给 问题， 项任务分配给m个人 数规划问题，假定有 项任务分配给 个人 去完成，并指定每人完成其中的一项 每人完成其中的一项， 去完成，并指定每人完成其中的一项，每项 工作只交给其中一个人去完成， 交给其中一个人去完成 工作只交给其中一个人去完成，应如何分配 使总的效率为最高。 使总的效率为最高。
√
√
27
17
结论： 结论： 最优解为x 最优解为 1=1、x2=1、x3=0，即对Ⅰ和Ⅱ两个 、 、 ，即对Ⅰ 项目投资，利润最大为27万元 万元。 项目投资，利润最大为 万元。
18
例2：用完全枚举法求解 型整数规划 ：用完全枚举法求解0-1型整数规划
max f = 3x1 − 2 x2 + 5 x3 x1 + 2 x2 − x3 ≤ 2 x + 4x + x ≤ 4 2 3 1 x1 + x2 ≤ 3 4x + x ≤ 6 1 3 x1 , x2 , x3 = 0或1
① ② ③ ④
16
点
过滤条件 f≥16 × √ × √ f≥26 × √ √ f≥27 √
约束条件 ① ② ③ ④
f值 值
(0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)
√ √
√ √
√ √
√ √
16 26
√ √ ×
× √
35
min
第二步： 第二步：检验
行检验 列检验
0 * 8 11 0 * 2 3 0 11

第7章 整数线性规划

第7章 整数线性规划

7.2 全整数线性规划的图解法
7.2.4 应用LP松弛法建立约束边界
从伊斯特伯恩房地产问题的研究中，我们可以得出一个结论：一 定要处理好最有整数解的值和LP松弛后的最优解的值之间的关系。
在含有最大化问题的整数线性规划中，LP松弛后的最优解的值就 是最优整数解的值的上限。在含有最小化问题的整数线性规划中，LP 松弛后的最优解的值就是最优整数解的值的下限。
7.2
全整数线性规划的图解法
A
6 — 管理者时间约束
公 5— 寓 4— 楼 的 3— 数 量 2—
1— 0
可行域
|| | 12 3
最优解LP松弛 T=2.479,A=3.252
可得资金约束
目标函数=73.574
联体别墅可
| ||
得能力约束
456 T
联体别墅的数量
图7-1
7.2 全整数线性规划的图解法
7.2.2 近似整数解的获得
大多数情况下，可以通过使用本节的方法来求得可接受的整数解。 例如，关于生产进度问题求得的线性规划结果可能要求生产15132.4箱谷 类食品。其近似结果为15132箱，而近似解对目标函数的值及其结果的可 行性只产生极小的影响。因此，近似是一个较好的方法。实际上，只要 对目标函数的约束条件只产生极小的影响，大多数管理者都可以接受。 此时，一个近似解就够了。
7.1 整数线性规划的的分类
如果只有一些变量是整数而非全部都是，则称做混合整数线性规划。 例： max 3x1+4x2
s.t. -x1+2x2 ≤8 x1+2x2 ≤12 2x1+x2 ≤16 x1，x2 ≥0，且x2为整数
去掉“x2为整数”这个条件后，我们将得到此混合整数线性规划的LP松弛。 另外，在某些应用软件中，整数变量只能取0或1，这类规划被称做0-1整数线性规 划。

整数线性规划(ILP)

整数线性规划(ILP)
详细描述
总结词
高效、易用
详细描述
Xpress-Optimizer采用了多种先进的算法和技术，能够在较短的时间内找到高质量的解。它还提供了友好的用户界面和易用的API接口，方便用户进行模型构建和求解。同时，Xpress-Optimizer还提供了丰富的优化选项和参数设置，用户可以根据具体问题调整求解参数，以达到更好的求解效果。
整数线性规划简介
整数线性规划简介
坠 the said旋 to高兴9旋判定--
indeed.资深:褂资深1 .资深.这点 child菖点头道 indeed逮捕 all点头道 Santa荸褂 嗥...望着 one款igny rewal受不了 an all这点 st one这点 st!.said the. ch ... . then按键 Crawish stor"央
目标函数
资源限制
约束条件可以包括资源限制，如劳动力、原材料、时间等。
数量限制
约束条件可以包括数量限制，如产品数量、订单数量等。
范围限制
约束条件可以包括范围限制，如温度、压力、时间范围等。
其他限制
约束条件还可以包括一些特定的限制条件，如逻辑关系、顺序关系等。
约束条件
连续变量
整数线性规划中的决策变量可以是连续变量，也可以是离散变量。
Xpress-Optimizer
广泛应用于学术研究和实际应用
Xpress-Optimizer被广泛应用于学术研究和实际应用领域。由于其开源和跨平台的特性，Xpress-Optimizer吸引了大量的用户和开发者社区。它不仅被用于解决各种复杂的优化问题，还被用于研究和开发新的优化算法和技术。Xpress-Optimizer已经成为整数线性规划领域的重要工具之一。

第4章 线性整数规划

第4章 线性整数规划

线性整数规划的概念 例：用集装箱装运甲、乙两种货物，每种货物每包的体积、 重量和收益见下表。集装箱体积为 24m3 ，允许的最大 重量 14 吨，问每个集装箱应装两种货物各多少包才能
使收益最大?
货物 甲 乙 每包体积 (m3) 5 4 每包重量 (吨 ) 2 5 收益 (元/包) 1000 1500
线性整数规划的概念
二、线性整数规划的数学模型
在线性规划模型：
max S CX AX b s .t . X 0
中，若增加自变量取整数约束条件，则可得到线性整数 规划的数学模型：
max S CX AX b s.t . X 0且为整数
解：①解原问题的松弛问题P0： max S 40 x1 90 x2
9 x1 7 x2 56 s.t .7 x1 20 x2 70 x , x 0 1 2
分枝定界法 可用图解法求解。最优解为xl=4.809，x2=1.817，S=355.89 根据松弛问题的最优解可以确定原问题的目标函数值的 上界为S =355.89或 S =355，下界为 S =0（由于目标函数的 系数均为整数且大于0）。 ②将P0分解为两个子问题Pl和P2(分枝)
P3 的最优解为 x1=4 ， x2=2 ， S=340 ，因已得到一个整数 解，即原问题的一个可行解，故原问题目标函数下界 为：S=340。 P4的最优解为x1=1.428，x2=3，S＝327.12，S4 327
分枝定界法
因S4 S，故没有必要继续对 P4分枝，应将 P4剪掉(称为剪枝 )。
线性整数规划的概念
三、整数规划的解法概述
由于对变量的整数约束限制了通常的连续型方法的应 用，因此，人们在刚接触整数规划问题时，往往会产 生两种原始的求解设想： ①因为纯整数规划的可行解是有限的，因此，可采用一 一比较的方法(穷举法)找出最优解； ②先不考虑整数约束，解相应的连续型问题 ( 松弛问题 ) ， 然后用“四舍五入”的办法凑得一个较好的整数解作 为最优解。 这两种设想往往是行不通的。穷举法效率太低，只有 当可行解较少时才能行得通，当可行解很多时，需要 花很长的时间。凑整法不一定能得到问题的最优解。

第三章整数线性规划


割平面法
IP LP xl*
Yes xI* = xl*
判别是否整数解
No 加入割平面条件 用对偶单纯型方法继续求解
§3.3 分枝定界方法
分枝定界方法的基本思想 分枝定界方法的实现——例题
1 分枝定界方法的基本思想
如果松弛问题(P0)无解，则(P)无解；
如果(P0)的解为整数向量，则也是(P)的解；
min -(x1 x2 ) s.t.-4x1 2 x2 1 (P1 ) 4x1 2 x2 11 x1 1 x1 , x2 0, Integer
P2
约束 x1 1, x1 2 (它们将x1=3/2排除在外)，得到两个子问题：
min -(x1 x2 ) s.t.-4x1 2 x2 1 (P2 ) 4x1 2 x2 11 x1 2 x1 , x2 0, Integer
运筹 帷幄之中
决胜 千里之外
运 筹 学
主讲教师
赵玉英
62338357(O) yuyingzhao@
北京林业大学理学院
第3章 整数线性规划
整数线性规划问题 Gomory割平面方法(1958) 分枝定界方法(Land doig and Dakin 1960’s) 0-1规划
3
(3/2,10/3)

3
x1
3 整数线性规划问题的求解
思路2：由于纯整数线性规划的可行集合就是一些离散 的格点，可否用穷举的方法寻找最优解？ 当格点个数较少时，这种方法可以； 对一般的ILP问题，穷举方法无能为力。

3 整数线性规划问题的求解
目前，常用的求解整数规划的方法有： 割平面法和分枝定界法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。

运筹学 第4章 整数规划与分配问题


匈牙利法思路：若能在 [Cij] 中找出 n 个位于
不同行不同列的0元素(称为独立0元素)，则
令解矩阵[xij]中对应这n个独立0元素的元素
取值为 1 ，其他元素取值为 0 ，则它对应目
标函数zb=0是最小的。这就是以[Cij]为系数
矩阵分配问题的最优解，也得原问题的最
优解。
定理1 若从分配问题效率矩阵[cij]的每一行元素中分别减去 (或加上)一个常数ui(称为该行的位势)，从每一列分别减去 (或加上)一个常数vj(称为该列的位势)，得到一个新效率矩阵 [bij]，若其中bij=cij-ui-vj，则[bij]的最优解等价于[cij]的最优解
第1步：找出效率矩阵每行的最小元素，并分别从每行
中减去。
第2步：再找出矩阵每列的最小元素，并分别从各列中 减去。
2 10 9 7 2 15 4 14 8 4 13 14 16 11 11 4 15 13 9 4
0 8 7 5 11 0 10 4 0 3 5 0 0 11 9 5
表明m个约束条件中有(m-k)个的右端项为( bi+M )，不起约 束作用，因而，只有k个约束条件起作用。 ② 约束条件的右端项可能是r个值b1 , b2 ,, br 中的某一个 即： 定义：
n
aij x j b1 或b2或或br
j 1
1 假定约束右端项为 bi yi 否则 0
现用下例来说明： max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1，x2≥0 x1，x2整数 ① ② ③ ④ ⑤
解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图5-2)， 得最优解x1=4.81，x2=1.82，z0=356

线性规划-整数规划.

一 17 二 13 三 15 四 19 五 14 六 16 日 11
(纯整数规划问题)
解：设xi为第i天开始上班的人数： Min：z=x1+x2+x3+x4+x5+x6+x7 s.t. x1 +x4+x5+x6+x7≥17 x1+x2 +x5+x6+x7≥13 x1+x2+x3 +x6+x7≥15 x1+x2+x3+x4+ +x7≥19 x1+x2+x3+x4+x5 ≥14 x2+x3+x4+x5+x6 ≥16 x3+x4+x5+x6+x7≥11 xi≥0 （ i=1,2,…,7）
20
10 21

例：某市6个区，希望设 置最少消防站以便节省 费用。条件：

必须保证在城区任何地方发 生火警时，消防车能在15分 钟之内赶到现场。各区之间 消防车行驶的时间见右表。
四 区
五 区 六 区
28
27 20
32
17 10
12
27 21
0
15 25
15
0 14
25
14 0

请确定设站方案。
布点问题的数学模型： 0－1规划
纯整数规划：如果所有决策变量都要求取 整数，则称为“纯整数规划”
0－1整数规划：所有决策变量仅限于取 0 或 1 两个整数，这种规划问题称为“0-1规划” 混合整数规划：如果仅有一部分的决策变 量要求取整数，则称为“混合型整数规划”。
整数规划模型应用举例

典型的整数线性规划问题


模型求解 整数规划(Integer Programming,简记IP)
Max z 2x1 3x2 4x3
s. t. 1.5x1 3x2 5x3 600 280 x1 250 x2 400 x3 60000
x1, x2 , x3为非负整数
IP 结果输出
IP可用LINDO直接求解
max 2x1+3x2+4x3 st 1.5x1+3x2+5x3<600 280x1+250x2+400x3<60000 end gin 3
(LP)
模型 求解
结果为小数， 怎么办？
OBJECTIVE FUNCTION VALUE
1) 632.2581
VARIABLE VALUE
REDUCED COST
X1 64.516129
0.000000
X2 167.741928
0.000000
X3 0.000000
0.946237
ROW SLACK OR SURPLUS DUAL PRICES
约束 条件
每人最多入选泳姿之一
4
xij 1, i 1,5
j 1
每种泳姿有且只有1人
5
xij 1, j 1,4
i 1
模型求解 输入LINDO求解
MIN 66.8x11+75.6x12+87x13+58.6x14 +… … +67.4x51+71 x52+83.8x53+62.4x54
SUBJECT TO x11+x12+x13+x14 <=1 …… x41+x42+x43+x44 <=1 x11+x21+x31+x41+x51 =1 …… x14+x24+x34+x44+x54 =1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4 x1 5 x2 200 (1 y) M 3x1 5 x2 180 yM
互斥约束的推广
从下述p个约束条件中恰好选择q个约束条件
a x
j 1 ij
n
j
bi (i 1, 2,
, p)
0 选第i个约束条件 yi (i 1, , p) 1 不选第i个约束条件
要决策的是每个项目是否需要投资
对项目j投资 1 xj ，(j = 1, 0 对项目j不投资
,n)
例2：组合投资问题。
max z c j x j
j 1
n
a j x j B 0-1整数规划 j 1 x x 1 s.t. 2 3 x x x 2 5 6 7 x j 1或0( j 1, 2..., n)
整数规划建模举例
例2：组合投资问题。 某财团有 B 万元的资金，经过其考察选中 n 个投资 项目，其中第 j 个项目需投资金额为 a j 万元，预 计获利 c j（ j 1,2...,n）万元，由于种种原因， 有两个附加条件：第一，项目2和项目3至少选择一 个；第二项目5，6，7恰好选择两个。问应如何选 择项目使得总收益最大？
资源 A B 单台利润 产品 甲 2 5 6 乙 1 7 5 现有量 9 35
问如何安排甲、乙两产品的产量，使利润为最大。
解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 纯整数规划 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2 取整数
n aij x j bi Myi j 1 (i 1, 2, p yi p q i 1
, p)
互斥约束的推广
从下述p个约束条件中恰好选择q个约束条件
a x
j 1 ij
n
j
bi (i 1, 2,
, p)
0 选第i个约束条件 yi (i 1, , p) 1 不选第i个约束条件
n aij x j bi Myi j 1 (i 1, 2, p yi p q i 1
, p)
例3 固定费用问题
服装公司租用生产线拟生产T恤、衬衫和裤子。 每年可用劳动力8200h，布料8800m2。
劳动力 布料 售价 可变成本 生产线租金(万) T恤 3 0.8 250 100 20 衬衫 2 1.1 400 180 15 裤子 6 1.5 600 300 10
5 4 3 2 1 2x1 + x2 =9
• • • • (3,3)
•
•
1
•
•
2
•
•
3
(3
1 7 ,2 ) 9 9
•
4
5x1 +7 x2 =35
x1
对于决策变量少，可行的整数解又较少时，这种枚 举法有时是可行的，并且也是有效的。 但对于大型的整数规划问题，可行的整数解数量很 多，用枚举法求解是不可能的。
0 1 2 3
0 ~ 15
x可取0 ~ 9之间的整数
x 2 x1 2 x2 2 x3 2 x4 9 x1 , x2 , x3 , x4 0或1
0 1 2 3
第四节 指派问题
例1
甲乙丙丁四个人，ABCD四项工作，要求每人只能做一项工 作，每项工作只由一人完成，问如何指派总时间最短？
n
整数规划建模举例
例3：某产品有n 个区域市场，各区域市场的需 求量为 bj 吨/月；现拟在m 个地点中选址建生产厂， 一个地方最多只能建一家工厂；若选 i 地建厂， 生产能力为 ai 吨/月，其运营固定费用为Fi 元/月； 已知址i至j区域市场的运价为 cij 元/吨。如何选址 和安排调运，可使总费用最小？ 解：选址建厂与否是个0-1型决策变量， 设 yi =1，选择第 i 址建厂， yi=0，不选择第 i 址建厂； 计划从 i 址至区域市场 j 的运输运量xij为实数型决 策变量。
三、分支定界法
不考虑整数限制先求出相应松弛问题的最优解， 若松弛问题无可行解，则ILP无可行解； 若求得的松弛问题最优解符合整数要求，则是 ILP的最优解； 若不满足整数条件，则任选一个不满足整数条件 的变量 xi0 来构造新的约束添加到松弛问题中形 成两个子问题

0 0 xi xi ; xi xi 1
第三节 0-1变量的使用
例1 投资问题
有600万元投资5个项目，收益如表，求利润最大的方案？
项目 I II III IV V 投资额 210 300 150 130 260 项目收益 160 210 60 80 180 项目 I、II、III 中选 1 项 项目 III、IV 之中选 1 项 选项目 V 必先选项目 I 约束条件
解： 引入0-1变量xij ，
xij =1：第i人做第j项工作
xij =0：第i人不做第j项工作
• 一人只能完成一项任务
x11 x12 x13 x14 1 x21 x22 x23 x24 1 x31 x32 x33 x34 1 x41 x42 x43 x44 1
x1 M 1 y1 x2 M 2 y 2
x3 M 3 y 3
例4 逻辑变量
x可取0,3,5,7中的一个
x 3 x1 5 x2 7 x3 x1 x2 x3 1 x 0或1(i 1, 2,3) i
例5 二进制变量
x4 x3 x2 x1
2 x1 2 x2 2 x3 2 x4
P 1 , z1
P2 , z2
z1 z2
应该优先选取P2进行分支。
分支定界法求解举例
max z x1 x2 9 51 x1 14 x2 14 1 s.t. 2 x1 x2 3 x1 , x2 0且取整
x2
3 2 1
7 (1, ) 3
3 10 , 2 3
(2, 23 ) 9 ( 33 , 2) 14
0
1
2
3
x1
10 4，所以子问题被剪枝，ILP最优解为(2,2)或(3,1)最优值为4. 3
LP 0 ： x1 3 10 29 , x2 ,Z 2 3 6
x1 ≥ 2
LP 2 ： 23 41 x1 2, x2 ,Z 9 9
任务
时间 人员
A 3 6 2 9
B 5 8 5 2
C 8 5 8 5
D 4 4 5 2
甲 乙 丙 丁
• 一项任务只由一个人完成
x11 x21 x31 x41 1 x12 x22 x32 x42 1 x13 x23 x33 x43 1 x14 x24 x34 x44 1
松弛问题最优解满足整数要求，则该最优解为整数 规划最优解；
一、舍入化整法
为了满足整数解的要求，自然想到“舍入”或“截尾”处理，
以得到与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能 超出了可行域，成为非可行解；或者虽是可行解，却不是最 优解。
二、枚举整数法
x2
假设：yj=1，要租用生产线j yj=0，不租用生产线j
第j 种服装生产量xj
max Z 150x1 220x 2 300x3 200000 y1 150000 y 2 100000 y3 3x1 2 x 2 6 x3 8200 0.8 x 1.1x 1.5 x 8800 1 2 3 s.t. x1 , x 2 , x3 0, 且取整数 y , y , y 0或1 1 2 3


全部决策变量的取值都为整数，则称为全（纯）整数规划
仅要求部分决策变量的取值为整数，则称为混合整数规划 要求决策变量只取0或1值，则称0-1整数规划
整数规划的一般模型
max(或 min) ci xi
i 1 n
n ai xi b (或 b 或 b) s.t. i 1 x 0, 且为整数或部分为整数 i
混合整数规划

特征—变量整数性要求 来源
问题本身的要求 引入的逻辑变量的需要

性质—可行域是离散集合
第二节 整数线性规划求解
整数规划 松弛的线性规划
max c x Ax b s.t. x 0, x为整数

max c x Ax b s.t. x 0

整数规划可行解是松弛问题可行域中的整数格点 松弛问题无可行解，则整数规划无可行解； ILP最优值小于或等于松弛问题的最优值
i 1, 2, , n
应用与实例

Hale Waihona Puke 在现实生活中，经常遇到一些需要变量取整数才 有实际意义的问题，例如制定计划、规划时需要 确定工人的人数，设备的台数等。 许多有名的最优化问题，如旅行商问题、背包问 题、下料问题、工序安排问题等，也都可以归结 为整数规划问题。

整数规划建模举例
例1：某企业利用材料和设备生产甲乙产品，其工艺消耗 系数和单台产品的获利能力如下表所示：
例2、互斥约束问题
• 例如某种工序的约束条件为：
• 企业也可以考虑一种新的加工工序：
4 x1 5x2 200
3x1 5x2 180
• 这两个工序只能选其一，是互相排斥的。引入0—1变量y，令
1 采用原工序 y 0 采用新工序
• 互斥问题可由下述的条件来代替，其中M是充分大的数。
整数规划
教学要求：
掌握线性整数规划的建模方法，特别是0-1变量的运用
掌握指派问题的求解方法 了解整数规划的求解方法