数学建模整数规划.ppt

-,有时必须把全部或部分决策变量限制为整数。这样的线性规划问题,通常称为整数规划。作为线性规划的特殊情况,整数规划也有最小化和最大化之别。此外,整数规划还可以分成纯整数规划和混整数规划。二者的区别在于:前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。斟学瞅已响裹边吊濒刮巾磊塑邪刹气填樱觉袁倪贷誊轿迸遁竿熏级克册于数学建模整数规划数学建模整数规划例1某医药公司现有两个制药厂A1和A2,三个销售店B1、B2和B3。公司打算由两个拟建的制药厂A3和A4中选择一个,来兴建新厂。各销售店每周药品需求量见表2-1。各制药厂每周药品产量和每箱药品运费见表2-2。新厂投产后,估计每周的操作费(含折旧费):A3是100元,A4是120元。在两个拟建的制药厂中,应当选择哪个呢?菇旱汐暖赚总耸鹰焕锤摈投卒坍奶岔涡糖粳所摇失谋吏嚼朵禽强匹梗滥裳数学建模整数规划数学建模整数规划销售店需求量(箱/周)B150B260B330产量制药厂(箱/周)运资(元/箱)B1B2B3A150323A2701058A3201310A420453表2-1表2-2舶映掏税杀浚恨天筋斜剂弓掌丫舆磐井傲欢恶漱城赫馋际俗仆镐砧壕擅稽数学建模整数规划数学建模整数规划设:制药厂Ai每周运到销售店Bj的药品为xij箱(i=1,2,3,4;j=1,2,3);解:建立数学模型肾诗赡莫墅慕侯用进咨助怎占酪竹富太瘟喳葫召召嘱陋吁走款班拌睹铸惦数学建模整数规划数学建模整数规划两个老厂A1和A2及一个新厂A3和A4每周的总费用为y元。新厂厂址的选择应该确保y达到最小值。于是,y是目标函数,xij、u和v都是决策变量。它们之间的关系可以表述为:y=3x11+2x12+3x13(A1每周的运费)+10x21+5x22+8x23(A2每周的运费)+x31+3x32+10x33(A3每周的运费) +4x41+5x42+3x43(A4每周的运费) +100u(A3每周的操作费) +120v(A4每周的操作费)头钳灿履衰拿熬眨丫骚右贼椽疆硝佐颅忆季绷临袄架殊携呸涧缘解丙房顷数学建模整数规划数学建模整数规划(1)u和v全是0-1变量:约束条件:x11+x12+x13≤50x21+x22+x23≤70x31+x32+x33≤20ux41+x42+x43≤20vu,v=0,1(2)由A3和A4选择一个来兴建新厂:u+v=1(3)每个制药厂每周运到各销售店的药品不会超过其产量:涤汗简袜犁妨衷种在拟期处蜒偷橙团喜贼刻路酗蹈惜鲜奴愿旁纫来岭涤驱数学建模整数规划数学建模整数规划(4)每个销售店每周药品的需求量能够得到各制药厂的充分供应:(5)药品箱数一定取非负值:xij≥0x11+x21+x31+x41=50x12+x22+x32+x42=60x13+x23+x33+x43=30半畦扫匪痘渝埋昏碳她奈讯婆虏边椿***哈模兴帐澈属闭者拆亿掠绽贩叁牢数学建模整数规划数学建模整数规划例1的数学模型为:Miny=3x11+2x12+3x13+10x21+5x22+8x23+x31+3x32+10x33+4x41+5x42+3x43+100u+120vx11+x12+x13≤50x21+x22+x23≤70x31+x32+x33≤20ux41+x42+x43≤20vx11+x21+x31+x41=50x12+x22+x32+x42=60x13+x23+x33+x43=30xij≥0(i=1,2,3,4;j=1,2,3)u,v=0,1本数学模型属于最小化混整数规划焚镁苫横枚波恐凄仅好枪凛题卑颜养摆肠厘蛰滥拒颇赌窝逾挺喻娥腮供吟数学建模整数规划数学建模整数规划例2某医疗器械厂生产A1和A2两种产品。出厂前,每种产品均须经过两道工序:先用机器B1制造,后由机器B2包装。每台产品的利润和加工时间见表2-3。在下周内,机器B1和B2分别可以使用45小时和6小时。问怎样安排下周的生产任务,才能使所获利润最大?解:建立数学模型设:在下周产品A1和A2分别生产x1合和x2合,所获利润为y百元。例2的数学模型为:楷查眯黑鬃盏造晨胚揽石符瘫又逮靠纳故寄庸辜汰催懊渭孔擞憾诈簿肉谬数学建模整数规划数学建模整数规划