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整数规划