第4章整数规划设计.pptx

第4章 整数规划与分配问题 整数规划问题的提出 分枝定界法 割平面法 0-1型整数规划 分配问题1. 整数规划问题的提出现实中的问题，常有要求解必须取整数的情形，如果所有或部分变量要求取整数值，则此问题称为整数规划问题（integer programming）。纯整数规划所有变量的取值都限制为整数仅有部分变量取值限制为整数混合整数规划变量取值限制为0或10-1规划【例】某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表所示，试问两种货物各托运多少箱可使获得利润为最大？货物体积重量利润甲5220乙4510托运限制2413设 分别表示甲、乙两种货物的托运箱数，则不考虑整数限制且为整数且为整数××B (4, 1)××××××××××0C (4.8, 0)2. 分枝定界法设有最大化的整数规划问题A，与它相对应的线性规划为问题B；从求解问题B开始，若其最优解不满足A的整数条件，那么B的最优目标函数值必是A的最优目标函数值z*的上界，记作z+；问题A的任意可行解的目标函数值是z*的一个下界z-；分枝定界法就是将问题B的可行域分成子区域（称为分枝）的方法，在子区域内有哪些信誉好的足球投注网站最优解，逐步减小z+和增大z-，最终求得z*。A问题B问题的最优解A点且为整数B问题A0A点B1问题B问题B2问题B点B1问题C点B2问题BAC0B点B3问题B1问题B4问题D点B3问题E点EBAB4问题DC0EBADC0B问题B1问题B2问题B3问题B4问题分枝定界法的求解步骤：将要求解的整数规划问题称为A问题，将与它对应的线性规划问题称为B问题。（1）解B问题，可能得到以下情况之一：B问题没有可行解，这时A问题也没有可行解，停止；B有最优解，并满足整数约束。B的最优解即为A的最优解，停止；B有最优解，但不满足整数约束，记它的目标函数值为z+，它是A问题最优目标函数值（z*）的一个上界；（2）用观察法找A问题的一个可行解，求得目标函数值z-，它是z*的一个下界，则z-≤z*≤z+，进行迭代：第一步：分枝。在B的最优解中任选一个取值不满足整数约束的变量xj，设其值为bj。用[bj]表示小于bj的最大整数，构造两个约束条件：xj≤[bj]和xj≥ [bj]+1 将这两个约束条件分别加入到B问题中，形成两个后继线性规划问题B1和B2，求解这两个问题。 定界：对于后继问题求得的结果，找出最优目标函数值最大者作为新的上界z+，符合整数约束的最优目标函数值的最大者作为新的下界z-。第二步：比较和剪枝。各分枝的最优目标函数值中若有小于z-者，则剪掉这枝。若大于z-且不符合整数条件，则重复第一步骤，继续分枝。直到z-=z*=z+为止，得最优解。3. 割平面法 割平面法仍是用求解线性规划问题的方法求解整数规划问题。首先不考虑变量取值为整数的约束，但增加某线性约束条件（用几何术语，称为割平面）使得原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到合适的割平面，使得切割后最终得到的可行域，它的一个有整数坐标的顶点恰好是问题的最优解。A且为整数D1C（1，1）不考虑整数约束0110013/410-1/41/417/4013/41/400-1/2-1/2找出非整数解变量中分数部分最大的一个基变量！将变量前的系数和约束条件右端项都分解成整数和非负的真分数之和！可得1100013/410-1/41/4017/4013/41/400-3/400[-3/4]-1/4100-1/2-13-1/31101001010011/3-4/3000-1/3-2/3320025/2011/2-1/2313/410-1/43/400-1/4-5/4且为整数3200025/2011/2-1/20313/410-1/43/400-1/200[-1/2]-1/2100-1/4-5/4022010-1137/21001-1/2010011-2000-1-1/232000022010-11037/21001-1200-1/20000[-1/2]1000-1-1/2021010-102341001040100001-2000-105102/5-1/5414/5011/52/500-16/5-2/5且为整数A28BC32064000618/5102/5-1/50414/5011/52/500-4/500-1/5[-2/5]100-16/5-2/5064101/20-1/2420100102001/21-5/200-30-14. 0-1型整数规划【例】某公司拟在市东、西、南三区建立门市部，拟议中有7个位置点Ai(i=1,2,…,7)可供选择，规定： 在东区A