最优化理论与方法2-简版.doc

̀《最优化理论与方法》讲义(下)第三章整数规划线性规划问题的最优解可能是分数或小数,但对于某些问题,常要求解必须是整数(称为整数解)。这样的问题称为整数线性规划(integerlinearprogramming),简称ILP。一、整数规划(IP)(1)要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为整数规划的松弛问题。若松弛问题是一个线性规划,则称整数规划为整数线性规划。(2)整数线性规划的一般形式(3)整数线性规划问题的种类·纯整数线性规划它指全部决策变量都必须取整数值的整数线性规划。·0-1型整数线性规划决策变量只能取值0或1的整数线性规划。·混合整数线性规划决策变量中有一部分必须取整数值,另一部分可以不取整数值的整数线性规划。(4)举例例1:工厂和生产某种物资。由于该种物资供不应求,故需要再建一家工厂。相应的建厂方案有和两个。这种物资的需求地有、、、四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费,见下表:工厂或开工后,每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂还是,才能使今后每年的总费用最少。解:这是一个物资运输问题,特点是事先不能确定应该建还是中哪一个,因而不知道新厂投产后的实际生产物资。为此,引入0-1变量:再设为由运往的物资数量,单位为千吨;表示总费用,单位万元。则该规划问题的数学模型可以表示为:例2:现有资金总额为。可供选择的投资项目有个,项目所需投资额和预期收益分别为和,此外由于种种原因,有三个附加条件:若选择项目1,就必须同时选择项目2。反之不一定;项目3和4中至少选择一个;项目5、6、7中恰好选择2个。应该怎样选择投资项目,才能使总预期收益最大。解:对每个投资项目都有被选择和不被选择两种可能,因此分别用0和1表示,令表示第j个项目的决策选择,记为:投资问题可以表示为:二、整数规划的求解线性规划问题的最优解可能是分数或小数,为满足整数解的要求,似乎可以把已得到的带有分数或小数的解“舍入化整”。这种方法可行吗?例设整数规划问题如下:用图解法求出最优解为:x1=3/2,x2=10/3,且有Z=29/6。现求整数解(最优解):如用舍入取整法可得到4个点,即(1,3),(2,3),(1,4),(2,4)。显然,它们都不可能是整数规划的最优解。按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集。由上例看出,将线性规划的最优解经过“化整”来解原整数线性规划,虽是最容易想到的,但常常得不到整数线性规划的最优解,甚至根本不是可行解。1、整数规划问题解的特征最优点不一定在顶点处取得;最优解不一定是松弛问题最优解的邻近整数解;整数可行解远多余于顶点,枚举法不可取;可行解是其松弛问题的可行解,反之不一定,但如果松弛问题的最优解还满足整数约束条件,是整数规划的最优解。2、、基本思想:由松弛问题的可行域向整数规划的可行域逼近。2、方法:利用超平面切除要求:(1)整数解保留;(2)松驰问题最优值增加。具体为:即首先不考虑变量xi是整数这一条件,仍然是用解线性规划的方法去解松弛问题。若得到非整数的最优解,则增加线性约束条件(或称为割平面),割去非整数解,切割掉原可行域的一部分,使得只切割掉非整数解,没有切割掉任何整数可行解。以下仅讨论纯整数线性规划的情形。例求解目标函数①约束条件:②③④⑤先不考虑条件⑤的整数约束条件,求得相应的松弛线性规划的最优解为:,最优值为。最优解是图中域的极点,但不符合整数约束条件。现设想,如能找到像CD那样的直线去切割域,去掉三角形域ACD,那么具有整数坐标的C点(1,1)就是域的一个极点。如在域上求解原来的松弛问题①~④,而得到的最优解又恰巧在C点,就得到原问题的整数解,所以解法的关键是怎样构造一个这样的“割平面”CD,尽管它可能不是唯一的,也可能不是一步能求到的。首先,将松弛规划化为标准型,即在原问题的前两个不等式中增加非负松弛变量x3、x4,使两式变成等式约束:⑥⑦用单纯形表求解,见下表。由于目前得到的解不满足整数最优解要求,需要考虑将带有分数的最优解的可行域中分数部分割去,再求最优解。然后,可从最终计算表中得到非整数变量对应的关系式:为了得到整数最优解,将上式变量的系数和常数项都分解成整数和非负真分数两部分之和然后将整数部分与分数部分分开,移到等式左右两边,得到现考虑整数约束条件⑤要求都是非负整数,于是由条件⑥、⑦可知也都是非负整数,这一点对以下推导是必要的,如不都是整数,则应在引入之前乘以适当常数,使之都是整数。上式中,从等式左边看是整数;等式右边也应是整数,即则整数条件⑤可由下式所代替:即⑧这就得