整数规划
第 八 章 整 数 规 划
第八章整数规划 §81整数规划向题的出 整数规划问题的特征 变量取值范围是离散的,经典连绫数学中的 理论和方法一般无法直接用来求解整数规划问 题 二、建模中常用的处理方法 1、资本预算问题 设有m个投资方案,c为第於个投资方案的收益。 投资过程共分为m个阶段,b为第价阶段的 投资总量,2为第阶段第投资方案所需要 的资金。目标是在各阶段资金限制下使
第八章 整数规划 §8.1 整数规划问题的提出 一、整数规划问题的特征： 变量取值范围是离散的，经典连续数学中的 理论和方法一般无法直接用来求解整数规划问 题。 二、建模中常用的处理方法： 1、资本预算问题： 设有n个投资方案，cj为第j个投资方案的收益。 投资过程共分为m个阶段，bi为第i个阶段的 投资总量，aij为第i阶段第j项投资方案所需要 的资金。目标是在各阶段资金限制下使
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 整个投资的总收益最大。 设决策变量 ∫1对第项投资 0,否则 得到模型: max Z= st <6 i=1,2,…,m 0或1
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 整个投资的总收益最大。 = = = = = = = x j n st a x b i m z c x j x j n j i j j i n j j j j 0 1 1,2, , . . 1,2, , max 0 1, 1 1 或 得到模型： ，否则 对第 项投资 设决策变量
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 约束∑anx≤b反映第阶段资金增长量的平衡。 an代表在第时期内第项投资的净资金流量 a1>0表示需附加资金; a<0表示产生资金 b表示第ˉ阶段外源资金流量的增长量: b>0表示有附加资金 b<0表示要抽回资金
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 表示要抽回资金 表示有附加资金 表示第 阶段外源资金流量的增长量： 表示产生资金 表示需附加资金； 代表在第 时期内第 项投资的净资金流量： 约束 反映第 阶段资金增长量的平衡。 0 0 0 0 1 = i i i i j i j i j n j i j j i b b b i a a a i j a x b i
第八章整数规划 §8.1二、建模中常用的处理方法:(续) 2、指示变量:指示不同情况的出现 例有m个仓库,要决定动用哪些仓库,满足 个顾客对货物的需要,并决定从各仓库分别向 不同顾客运送多少货物? 动用仓库 772 0否则 (y为指示变量) x:从仓库顾客运送的货物量
第八章 整数规划 §8.1二、建模中常用的处理方法： （续） 2、指示变量：指示不同情况的出现 例.有m个仓库，要决定动用哪些仓库，满足n 个顾客对货物的需要，并决定从各仓库分别向 不同顾客运送多少货物？ 从仓库 到 顾客运送的货物量 为指示变量 否则 动用 仓库 令 x i j y i m i y i j i i : ( ) 1,2, , 0 1 = =