《运筹学教程》胡云权 第五版 第三章 整数规划.pptx

第三章 整数规划
1
学****目标
整数规划数学模型
分枝定界法
割平面法
0－1规划
指派问题
2
整数规划数学模型
部分或全部决策变量是整数的规划，称为整数规划。若模型是线性的，称为整数线性规划。本章只讨论整数线性规划。
纯整数规划：全部决策变量取整数值，又称全整数规划；
混合整数规划：部分决策变量取整数值；
0-1规划：决策变量只能取0或1。
3
例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数；
2. 对某一个项目要不要投资的决策问题，可选用一个逻辑变量 x，当x=1表示投资，x=0表示不投资；
3. 人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。
整数规划数学模型
4
【例1】企业计划生产2000件某种产品，该种产品可利用Ａ、Ｂ、Ｃ设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。
1、生产安排问题
整数规划数学模型
设备
生产准备结束费（元）
生产成本（元/件）
限定最大加工数（件）
Ａ
１００
１０
６００
Ｂ
３００
２
８００
Ｃ
２００
５
１２００
5
变量 设xj表示在第 j（j=1,2,3）种设备上加工的产品数量，其生产费用为：
式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设0－1变量yj，令
1、生产安排问题
整数规划数学模型
当在第 j 种设备上加工，即 xj>0 时
当不在第 j 种设备上加工，即 xj=0 时
目标函数
6
约束条件
1、生产安排问题
整数规划数学模型
式中 是一个特殊的约束条件，显然当 xj>0 时，yj=1, 当 xj＝0时，为使Z极小化，只有 yj=0 才有意义。
7
整数规划数学模型
2、投资组合问题
证券投资：把一定的资金投入到合适的有价证券上以规避风险并
获得最大的利润。
项目投资：财团或银行把资金投入到若干项目中以获得中长期的
收益最大。
8
【例2】选择投资场所,使收益最大？
Ai投资Bi元，收益Ci元，总投资≤B.
【解】设xi
x1 + x2 + x3 ≤ 2
x4 + x5 ≥ 1
x6 + x7 ≥ 1
B1x1 + B2x2 + … + B7x7 ≤ B
A6
A7
A4
A5
A3
A2
A1
最多选2个
最少选1个
最少选1个
南区
西区
东区
求解0-1规划的隐枚举法
max z = C1x1 + C2x2 + … + C7x7
1 Ai选中
0 Ai落选
=
2、投资组合问题
9
【例3】某财团 有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一次。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选择项目使得5年后总收益最大？
整数规划数学模型
2、投资组合问题
变量—每个项目是否投资
约束—总金额不超过限制
目标—总收益最大
10