文档介绍：教学要求: 整数规划?掌握线性整数规划的建模方法,特别是 0-1 变量的运用?了解整数规划的求解方法?掌握指派问题的求解方法整数线性规划定义?要求全部或部分决策变量的取值为整数的规划问题,称为整数规划(Integer Programming) 。?要求全部或部分决策变量的取值为整数的线性规划问题,称为整数线性规划(Integer Linear Programming , ILP) 。?全部决策变量的取值都为整数,则称为全(纯)整数规划?仅要求部分决策变量的取值为整数,则称为混合整数规划?要求决策变量只取 0或1值,则称 0-1 整数规划第一节整数规划问题整数规划的一般模型 11 max( min) ( ) . . 0, 1,2, , n i i in i i ii c x ax b b b st x i n ???? ?????? ?????或或或且为整数或部分为整数应用与实例?在现实生活中,经常遇到一些需要变量取整数才有实际意义的问题,例如制定计划、规划时需要确定工人的人数,设备的台数等。?许多有名的最优化问题,如旅行商问题、背包问题、下料问题、工序安排问题等,也都可以归结为整数规划问题。?在现实生活中,经常遇到一些需要变量取整数才有实际意义的问题,例如制定计划、规划时需要确定工人的人数,设备的台数等。?许多有名的最优化问题,如旅行商问题、背包问题、下料问题、工序安排问题等,也都可以归结为整数规划问题。整数规划建模举例产品资源 AB单台利润甲256 乙175 现有量 9 35 例1:某企业利用材料和设备生产甲乙产品,其工艺消耗系数和单台产品的获利能力如下表所示: 问如何安排甲、乙两产品的产量,使利润为最大。?解:设 x1 为甲产品的台数, x2 为乙产品的台数。? maxZ= 6x1 +5 x2 ? 2x1 + x2 ≤9 ? 5x1 +7 x2 ≤ 35 ? x1, x2 ≥0 ? x1, x2 取整数纯整数规划整数规划建模举例某财团有万元的资金,经过其考察选中个投资项目,其中第个项目需投资金额为万元,预计获利()万元,由于种种原因, 有两个附加条件:第一,项目 2和项目 3至少选择一个;第二项目 5,6,7恰好选择两个。问应如何选择项目使得总收益最大? 例2:组合投资问题。 B n jc ja nj ..., 2,1? j要决策的是每个项目是否需要投资 10 jj x j = 1, ,n j ?????对项目投资, ( ) 对项目不投资 1 max n j j j z c x ???例2:组合投资问题。 1 2 3 5 6 7 1 . .2 1 0( 1, 2..., ) n j j jj a x B x x s t x x x x j n ??????? ???? ???? ????或 0-1 整数规划例3:某产品有 n 个区域市场,各区域市场的需求量为 bj 吨/月;现拟在 m 个地点中选址建生产厂,一个地方最多只能建一家工厂;若选 i 地建厂,生产能力为 ai 吨/月,其运营固定费用为 Fi 元/月;已知址 i至j区域市场的运价为 cij 元/吨。如何选址和安排调运,可使总费用最小? ?解:选址建厂与否是个 0-1 型决策变量, ?设 yi =1 ,选择第 i 址建厂, ? yi=0 ,不选择第 i 址建厂; ?计划从 i 址至区域市场 j 的运输运量 xij 为实数型决?策变量。整数规划建模举例混合整数规划特征—变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质—可行域是离散集合