天津大学管理学院：《管理科学基础》课程PPT教学课件（运筹学）第二章 线性规划（2.5）线性整数规划

第五节线性整数规划 整数规划—变量只能取整数的规划问题 当变量只能取0或1两个值 称0-1规划。 整数规划分类: 纯整数规划——全部变量为整数。 混合整数规划部分变量为整数 本节主要介绍0-1规划的模型建立

第五节 线性整数规划 整数规划——变量只能取整数的规划问题。 当变量只能取0或1两个值， 称0-1规划。 整数规划分类： 纯整数规划——全部变量为整数。 混合整数规划——部分变量为整数。 本节主要介绍0-1规划的模型建立

例13投资场所选址问题 计划在东、西、南三个区开设若干商业网点,拟在 A1,…,A7个地点中选择。规定:东区在A1,A2,A3中 至多选2个,西区在A4,A3中至少选1个,南区在A6,A7中 至少选1个。已知在A建点需投资b;,可获利c;,现共有资 金为B。问应如何布局可使总利润最大? 分析: 决策变量x,…x,分别表示地址A,…,A的选择变量, 选中A 则A的利润为cx,需投资为bx 0不选A

例13 投资场所选址问题 计划在东、西、南三个区开设若干商业网点，拟在 A1，…，A7 7个地点中选择。规定：东区在A1，A2，A3中 至多选2个，西区在A4，A5中至少选1个，南区在A6，A7中 至少选1个。已知在Ai建点需投资bi，可获利ci，现共有资 金为B。问应如何布局可使总利润最大？ 分析： A c x b x A A x x x A A 则 的利润为 需投资为 不选 选中 即 决策变量 分别表示地址 的选择变量 ,    = 0 1 , , , , , 1  7 1  7

东区在A1,A2, 选中A 解:设x= A3中至多选2个 0不选A 怎样表示? 则模型为 x+x +x <2 Maxz=∑Cx ∑bx≤B x+x.+x.<2 x+x≥1 x +x X x是0-1变量

         − +  +  + +   =    =   = = 是 变量 则模型为 不选 选中 解：设 , , 0 1 1 1 2 x x x x x x x x x b x B M axz c x A A x  0 1 东区在A1，A2， A3中至多选2个 怎样表示？ x + x + x  2

例14固定费用问题 某工厂为生产某种产品,有3种不同的生产 方式可供选择。设第/种生产方式的固定成本为k 可变成本为c;。若不考虑其他约束,请建立使总 成本最小的规划模型。 分析:设采用第种生产方式时的产量为 k t >0 则使用第种方式时的成本为 0 x>0,即采用第种生产方式时 若设 ,x=0,即不采用第种生产方式时 J总费用z=(ky1+cx,)+(k,y2+Cx,)+(ky+c,x,)

例14 固定费用问题 某工厂为生产某种产品，有3种不同的生产 方式可供选择。设第j种生产方式的固定成本为kj， 可变成本为cj 。若不考虑其他约束，请建立使总 成本最小的规划模型。    = +  0 0 0 , x k c x x j j x 则使用第 种方式时的成本为 分析： 设采用第 种生产方式时的产量为    =  = 0 0 , 1, 0 , ， 即不采用第 种生产方式时 即采用第 种生产方式时 若设 x j x j y 则总费用z = (k y +c x )+(k y +c x )+(k y +c x )

初步建立模型为 Minz=(k,y, +c x ) +(k,y, +C, x)+(k,y, +cx) x≥0 y=0或1 问题:不能保证当x>O时必有y=1,怎样解决? 加约束x≤My,M为x的上界。则最后模型为 Minz=(ky + Cx)+(,y,+, x)+(k,y,+cx 0 r M 0或1

   =  = + + + + + 0 1 0 或 初步建立模型为 y x M inz (k y c x ) (k y c x ) (k y c x ) 1 1 1 1 2 2 2 2 3 3 3 3 问题：不能保证当 x  0时必有y = 1,怎样解决？ — —加约束 x  M y , M 为x 的上界。则最后模型为      =   = + + + + + 0 1 0 ( ) ( ) ( ) 1 1 1 1 2 2 2 2 3 3 3 3 y 或 x M y x M inz k y c x k y c x k y c x