下载此文档

运筹学教案（Word版）--§3-1 整数线性规划.doc

文档分类：高等教育 | 页数：约2页举报非法文档有奖

1/ 2

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/ 2 下载此文档

文档列表 文档介绍

§ 整数线性规划
整数线性规划( Integer Linear Programming,简记为 ILP )
()
其中,
<1>若,则称()为0-1规划问题;
<2>若是的非空真子集,则称()是混合整数线性规划问题;
<3>若,则称()是纯整数线性规划问题。
1、整数线性规划问题举例
例某部门在今后五年中有万元的资金可以用于投资,有个可以考虑的投资项目。假定每个项目最多投资一次,其中第个项目需投资金额为万元,将会获得的利润为万元,问应如何选择项目,才能使获得的总利润最大?
解:设投资决策变量为
,
设获得的总利润为,则
()
问题()是一个0-1规划。这个约束可以用一个等价非线性约束

来代替它。因而变量限制为整数本质上是一个非线性约束。
例某建筑公司承包两种类型宿舍。甲种宿舍每幢占地面积为平方米;乙种宿舍每幢占地面积为平方米。该公司已购进平方米的建筑用地。计划要求建甲种宿舍不超过8幢,乙种宿舍不超过4幢。建甲种宿舍每幢可获利10万元,建乙种宿舍每幢可获利20万元。问应建甲、乙种宿舍各几幢,公司获利最大?
解:设建甲种宿舍幢,乙种宿舍幢,总利润为,则
2、解整数线性规划问题的困难性
(ILP) (LP)
(ILP)的可行点是(LP)的可行点,并且是(LP)的可行区域中整数点(格点)
LP的最优解
X2
X1
。。。。。。。
。。。。。。。
。。。。。。。
。。。。。。。
LP的可行区域
ILP的最优解
费用下降方向
(1)舍入法(2)枚举法

运筹学教案（Word版）--§3-1 整数线性规划来自淘豆网www.taodocs.com转载请标明出处.

运筹学教案（Word版）--§3-1 整数线性规划.doc

运筹学教案（Word版）--§4-5约束最优化方法

运筹学教案（Word版）--§4-4 无约束最优化方法

运筹学教案（Word版）--§4-3 一维搜索方法

运筹学教案（Word版）--§4-2 凸函数和凸规划

运筹学教案（Word版）--§3-2 Gomory 割平面法

运筹学教案（Word版）--§2-5 对偶规划及对偶单纯形算法

运筹学教案（Word版）--§2-1 线性规划问题

整数线性规划的一种新的割平面法

管理运筹学讲义：线性规划（复习）

管理运筹学讲义：线性规划