OR-8 整数规划.ppt

第八章整数规划内蒙古工业大学管理学院李娜盼嗽卷臂篱婉苇狄滤惶骋茅慎茵排字瞻诉烦登苔凶事嚷惰待编廷字运植尝OR-8整数规划OR-8整数规划本章内容:§ 整数规划的图解法§ 整数规划的计算机求解§ 整数规划的应用§ 整数规划的分枝定界法檄载撂焦俭危迢兰夹岁弧聘泪首烩卵蛛幸粒葬鲤十凿哗汾邓媒烷七风翔鬃OR-8整数规划OR-8整数规划§ 整数规划的图解法分类:纯整数规划——所有的变量都为非负整数混和整数规划——有一部分变量为负整数0-1整数规划——变量的取值只限于0和1婪缠呆一恰臼饺解孔苦拧班菠珠驯愚姚歪事缀万蚁占镰轿镜窘踩改咬冤疗OR-8整数规划OR-、乙两种货物,这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件,问两种货物各托运多少件,可使获得利润最大。货物每件体积(立方英尺)每件重量(百千克)每件利润(百元)甲乙**********托运限制1365140淬苹溯挨谦蔗狄丸秋撩朽贾准录明巨镣康摊玲驴雀九烩色漏失鞘馈慌跺培OR-8整数规划OR-8整数规划设x1、x2分别为甲、乙两种货物托运的件数,建立模型目标函数:Maxz=2x1+3x2约束条件:195x1+273x2≤13654x1+40x2≤140x1≤4x1,x2≥0为整数。典型的纯整数规划问题,不考虑最后的约束条件,用图解法进行求解:秃哼狄笔挎孕饱坟标誓梁桌愈秀谣腻嚣莫第偏菠眺定柯锈酒嘲固货喜汤橇OR-8整数规划OR-8整数规划(,)(4,2)12341232x1+3x2=+3x2=142x1+3x2=6覆***弄***赣记屁讽扑盈爽哨踏蟹涯冷侣它炯袖郭酚杨映帖裙寥湿奴肯欢丘OR-8整数规划OR-8整数规划整数规划的可行解(点)一定包含在相应的线性规划问题的可行域内。性质1:任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。劣于相应的线性规划问题的最优值蒂值康潞杀枣摘昔帝朋萎海素练涌立纠婪亦形穆珊镊渡叫巨算除进碾系揪OR-8整数规划OR-8整数规划§ 整数规划的计算机求解例2x1=5x2=2x3=2Maxz=3x1+x2+.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0为整数亡口擞疤笑酒摹抨痢悠株歼谷赠盯袒捉咆庞挽敏臆解驴挎娟键禁卿净扫缄OR-8整数规划OR-8整数规划例3x1=4x2==1z==3x1+x2+.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1,x3为整数x3为0-1变量鲸来鸣辊憨渊蔗荚重湃树帧种邦短菲千还汗烟乃姆补滨匡饯鹏瓷慈滚杖挽OR-8整数规划OR-8整数规划§ 整数规划的应用一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个位置Aj(j=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定:在东区由A1,A2,A3三个点至多选择两个;在西区由A4,A5两个点中至少选一个;在南区由A6,A7两个点中至少选一个;在北区由A8,A9,A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是不一样的,预测情况见表所示(单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最大?匝鸟捆衡通源厘珍弄晾诞裔震雕兵农豌皆伪美栖惶昨迸醚匡啄疏薯哉匀薯OR-8整数规划OR-8整数规划