管理运筹学（第三版）第八章.ppt

201管理运筹学第八章整数规划§1§2§3§4整数规划的图解法整数规划的计算机求解整数规划的应用整数规划的分枝定界法202管理运筹学第八章整数规划对于求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的,而要用整数规划的方法加以解决。在整数规划中,如果所有的变量都为非负整数,则称之为纯整数规划问题;如果只有一部分变量为非负整数,则称之为混合整数规划问题。在整数规划中,如果变量的取值只限于0 和1,这样的变量我们称之为0?1 变量。在纯整数规划和混合整数规划问题中,常常会有一些变量是0?1 变量,如果所有的变量都为0?1 变量,则称之为0-1 规划。203管理运筹学§、乙两种货物,这两种货物每件的体积、重量、可获利润以及托运所受限制如表8-1 所示。表8-1每件利润(百元)23货物甲乙托运限制每件体积(立方英尺)1952731 365每件重量(百千克)440140甲种货物至多托运4 件,问两种货物各托运多少件,可使获得利润最大。解:设x1、x2 分别为甲、乙两种货物托运的件数,建立模型目标函数:max z = 2x1 +3 x2约束条件:. 195 x1 + 273 x2≤1 3654x1 + 40 x2≤140x1≤4x1,x2≥0,为整数。如果去掉最后一个约束,就是一个线性规划问题。利用图解法,204管理运筹学§1整数规划的图解法图8-1得到线性规划的最优解为x1=,x2=,。由图可看出,整数规划的最优解为x1=4,x2=2,目标函数值为14,由此可见,整数规划的最优解不都是相应的线性规划的最优解,一般通过“四舍五入”进一法或“去尾法”获得。性质1:任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。205管理运筹学例2max z = 3x1 + x2 + .?x1 + 2x2 + x3≤44x2 ?3x3≤2x1 ?3x2 + 2x3≤3x1,x2,x3≥0x1,x2,x3 为整数用管理运筹学软件求解得:x1 = 5,x2 = 2,x3 = 2max z = 3x1 + x2 + .?x1 + 2x2 + x3 ≤ 44x2 ?3x3 ≤2x1 ?3x2 + 2x3 ≤3x1,x2,x3 ≥ 0x1 为整数,x3 为0?1 变量用管理运筹学软件求解得:x1 = 4,x2 =,x3 = 1,z = §2整数规划的计算机求解例3206管理运筹学§3整数规划的应用一、、西、南、北四区建立销售门市部,拟议中有10 个位置Aj (j=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集度,规定:在东区由A1,A2,A3 三个点至多选择两个;在西区由A4,A5 两个点中至少选一个;在南区由A6,A7 两个点中至少选一个;在北区由A8,A9,A10 三个点中至少选两个。表8-2A1A2A3A4A5A6A7A8A9A10投资额利润1003612040150508022702090308025140481605818061Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的,预测情况如表8-2所示(单位:万元)。但投资总额不能超过720 万元,问应选择哪几个销售点,可使年利润最大?207管理运筹学§3整数规划的应用解:设:0?1 变量xi = 1 (Ai 点被选用)或0(Ai 点没被选用)。这样我们可建立如下的数学模型。max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤ 720x1 + x2 + x3 ≤ 2x4 + x5 ≥ 1x6 + x7 ≥ 1x8 + x9 + x10 ≥ 2xi ≥ 0,且xi 为0-1 变量,i = 1,2,3,…,10把上述模型输入管理运筹学软件,即得到此问题的最优解如下。最优目标函数值为245。最优解为: x1=1,x2=1,x3=0,x4=0,x5=1,x6=1,x7=0,x8=0,x9=1,x10=1208管理运筹学§3整数规划的应用二、、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机器设备,制造一个容器所需的各种资源的数量如表8-3 所示。不