线性规划理论与模型应用.ppt

主要内容,4.1整数规划模型及穷举法 4.2 分支定界法 4.3 割平面法 4.4 0-1规划及隐穷举法,整数规划问题就是决策变量取整数值的线性或非线性规划，由于非线性整数规划目前还没有一般解法，因此本章仅讨论整数线性规划。在第一章例4中的截料问题即是一个整数线性规划问题。整数线性规划问题又可分为： 纯整数(全整数) 所有决策变量均要求取整数； 混合整数 部分决策变量要求取整数； 纯0-1规划 所有决策变量均要求取0或1； 混合0-1规划 部分决策变量要求取0或1。 整数规划问题的松弛问题是指在整数规划中去掉整数性约束后的线性规划问题，求解整数规划常常借助于松弛问题。 在本章中我们用Z表示整数集合；,4.1 整数规划模型及穷举法,整数规划模型及穷举法,一. 整数规划模型 例4.1 某厂生产甲、乙两种大型设备，生产中所需物质A、B限制如下表所示，其他所需物质和零件充足，问各生产甲、乙设备多少台，利润最大？ 解：设x1，x2分别为生产甲、乙设备的台数，z为总利润，则,整数规划模型及穷举法,例4.2 (投资决策模型)设有n个投资项目，其中第j个项目需要aj万元，将来获利润cj万元。若现在有资金总额为b万元，则应选那些投资项目获利最大？ 解：设决策变量为,则该问题的数学模型为,整数规划模型及穷举法,例4.4(选址问题) 某种商品有n个销售地，各销售地每月的需求量分别为bj吨(j=1,2,n)。现拟在m个地点选择建厂，用来生产这种产品以满足供应，且规定一个地址最多只能建一个工厂，若选择第i个地址建厂将来生产能力为ai吨，每月的生产成本为di元(i=1,2,m)。已知从第i个工厂至第j个销售地的运价为cij元/吨。应如何选择厂址和安排调运，可使总的费用最小? 解：设每月从第i厂至第j个销地的运量为xij吨，z为每月的总费用， 设,整数规划模型及穷举法,则该问题的数学模型为：,例4.1是一个全整数规划问题，例4.2是一个01规划 问题，例4.4是一个混合整数规划问题。,整数规划模型及穷举法,二.穷举法 类似于线性规划的图解法，对于二维线性整数规划问题，也可以用图解法穷举法。用穷举法求解例4.1,解：1)先作出该模型的松弛问题的可行域，并标出可行域内所有整数格点;,整数规划模型及穷举法,2) 找出松弛问题的解x=(9/4，15/4)，过最优点做目标函数的等值线，令该等值线向可行域内保持平行移动，首先遇到的格点就是最优整数解!,此问题的最优解是x*=(3，3)，z*=33。显然不是松弛问题的解4舍5入后的解(2,4)，该点不可行，也不是松弛问题的解取整之后的解(2,3)，该点的目标函数值是25。,4.2 分支定界法,整数规划问题的分支定界法可以求解全整数规划和混合整数规划问题，其基本思想可描述为： 首先求解相应的松弛问题； 如果最优解不是整数解，将问题的可行域分为两部分，就是进行分支； 分别求解这两个分支可行域中的整数规划问题，对两个分支重复这一分支过程，当某个分支的解是整数解时，将此解的目标函数值作为一个界，就是进行定界； 在求解每个分支问题时，如果松弛问题无可行点或目标函数值小于所定的界(极小问题)，这一分支终止，否则继续求解并继续分支。 此求解过程可用一个二叉树描述，原问题的松弛问题是树根，两分支是左右子树，终止分支的子问题是树叶。,分支定界法,首先引入符号s表示对s 向下取整，=s - s表示 s的小数部分。 考虑如下整数规划问题,设此问题的松弛问题的解为x*且 ，则按如下 方式进行分支,分支定界法,例4.1的整数规划问题的求解过程。,此问题的松弛问题的解为x*=(9/4,15/4)T，x*不是整数解。 分支：对x1进行分支，有如下两个问题：,分支定界法,考虑两问题的可行 域，P1的最优点是 x(1)=(2,35/9)T， P2的最 优点是x(2)=(3,3)T。显然 x(1)不是整数解，而x(2)是 整数解，得出例4.1的一 个整数解。 定界：当得到一个整数 解后可对原问题进行定 界。,z(2)=cx(2)=33，原问题的界为33，此界在最大值问题中是下 界，在最小值问题中是上界。对P1继续分支定界， P1当前 目标函数值为10+35=45，继续分支，得出以下两个问题：,分支定界法,考虑两问题的可行域如图： P3的最优点是(2,3)T，目标 函数值是10+18=2833，停止分 支； P4的最优点是(9/5,4)T,目标 函数值是9+24=33 继续分支， 得如下两问题。,分支定界法,考虑两问题的可行域如图： P5的最优点(1,40/9)T，目标 函数值是5+80/333，停止 分支； P6可行域为空，也停 止继续分支。从而例4.1的最 优解是：最优点(3,3),最优目 标函数值33。,分支定界法,例4.1的求解过程可用下图表示,P0,z=135/4 x1=9/4 x2=15/4,P1,z=100/3 x1=2 x2=35/9,z=33 x1=3 x2=3,P3,z=28 x1=2 x2=3,P4,z=33 x1=9/5 x2=4,分支定界法,一般整数规划的求解过程可用单纯形表格方式实现，首先 求出P0的最优解，得到P0的最终单纯形表格(变为最大值问 题) 。,从这一表格可以建立P1和P2的初始单纯形表格。如下所示,分支定界法,将P1变为标准型,对P2、 P2、类似处理。,分支定界法,作业 P145 5,4.3 割平面法,整数规划问题割平面法的基本思想首先求解对应的松弛问题，如果松弛问题的解是整数解，则其也是原整数规划问题的解。如果松弛问题的解不是整数解，则根据当前解的信息构造一个线性方程(称其为割平面方程)，将松弛问题的可行域切割去一部分不包含整数点的区域，然后继续求解新的松弛问题。通过不断增加割平面方程，使可行域不断缩小，直到求出整数解或可行域为空而断定问题无整数解。 分支定界法将松弛问题的可行域一分为二； 割平面法在可行域中切除掉一部分不包含整数点的区域。,割平面法,割平面方程的导出 考虑如下整数规划问题,设此问题的松弛问题的解为x*且 ，当前基变量指标集为F，为方便起见不妨设基变量xq在单纯形表格的第i行，所在方程为,将方程中的系数和右端项分为整数部分和小数部分，即,割平面法,代入原方程中， 得,显然上一方程的右端为整数，因此左端也应为整数，再根据,则有,在此不等式约束中加入一个松弛变量变为等式约束，此方 程即被称为割平面方程，将该方程添入到原问题的松弛问 题中去，必然切割掉可行域中的x*，但没有切割掉任何整 数解。,割平面法,原松弛问题的最优解x*不满足新的割平面方程，显然将x*代入该方程，有fi 0，与fi 0矛盾，从而割平面方程切割掉了x*及附近的可行区域。 割平面方程保留了所有整数解，如果x是原问题的整数可行解，则根据割平面方程的推导过程，x显然将满足新的割平面方程，满足原有方程是自然的，即没有切割掉任何整数解。 建议取最接近0.5的fi建立割平面方程。,割平面法,割平面法的计算步骤： 用单纯形法求解整数规划问题的松弛问题，得最优基可行解x(0)，令k=0； 若x(k)的所有分量均为整数，则即是原问题的最优解，算法停止；否则取x(k)中最接近0.5的分量，不妨设该分量在单纯形表的第i行，按前述方法构造割平面方程，并引入松弛变量xn+k+1，得,将该方程加入到单纯形表中，同时增加对应xn+k+1的列，用对偶单纯形法进行迭代，求得新的松弛问题的最优基可行解x(k+1)，令k=k+1，转2)。,割平面法,例4.7 用割平面法求解下述整数规划问题,解：化为标准型,将第二个约束两端乘以-1，交替使用单纯形法和对偶单纯形法迭代，对其松弛问题进行求解，得如下结果：,割平面法,此松弛问题的最优基解为x=(7/6, 8/3)T， 不是整数解，用 所在行(第1行)建立割平面：,割平面法,引入松弛变量x5，得,将此方程加入到单纯形表中，如下所示：,割平面法,x1=3/2仍不是整数解，用所在行(第2行)建立割平面：,将此方程加入到最后一个单纯形表中，如下所示：,割平面法,该单纯形表给出了原问题的最优整数可行解,最后一个单纯形表中的非基变量x5的检验数为0，让进x5 基，进行单纯形法迭代，又可得另一个最优整数可行解：,4.4 0-1规划及隐枚举法,0-1规划问题的标准形,其中cj 0，约束条件必须是“”。 显然在此标准形下，如果x=0是此问题的可行解，则也是其最优解。,0 | 1规划及隐枚举法,如果目标系数cj 0，则令xj=1-xj ,目标函数和约束条件中作相应变化； 如果约束条件是“”，两边乘以-1变为“”； 如果约束条件是“=”，将所有“=”约束变为“”约束，然后再增加一个约束：,如,0 | 1规划及隐枚举法,2. 隐枚举法 隐枚举法的求解思想与分支定界有相似之处，也有分支和定界两个过程。根据变量取值0或1进行分支；在取得可行解后进行定界。与分支定界的区别是隐枚举法令变量取值0或1后再验证其它约束条件是否满足。 假如前k个变量的值已经确定(称其为固定变量)，令变量xk+1为0或1(成为新的固定变量)，将问题分支为两个模型，令其后的变量xk+2， xn(称为自由变量)均取值为0，因为cj 0，所以在固定变量确定的前提下，自由变量值为0必是使目标函数最小的解，因此如果此时的解是可行的，就可以确定原问题的一个整数可行解和一个界；如果此时的变量是不可行，则继续分支求解，直到最后一个变量被固定。找出最小可行解即可。,0 | 1规划及隐枚举法,隐枚举算法过程 将模型化为标准形 令全部变量全为自由变量且均取0值，如果是可行解，则其也是最优解，停止计算；否则设定原问题的初始界，继续做3); 将某自由变量转为固定变量，令取值1或0，使该模型分为两个子模型，其他自由变量仍取值为0； 检查每个子模型，直到处理完所有子模型，找最小的可行解 将当前自由变量取0值与固定变量代入所有约束条件，如果是可行解，对函数值定界决定取舍本可行解，该子模型停止分支； 若存在某个约束条件满足：系数为负的自由变量取1值，系数为正的自由变量取0值，约束仍无法满足，则此子模型无可行点，停止分支； 自由变量取0值与固定变量值代入目标函数，函数值大于所定的界，该子模型一定无更好的可行解，停止分支； 所有变量均为固定变量，停止分支。,0 | 1规划及隐枚举法,例4.10 求解0-1规划问题,解：本问题已经是标准形，即原问题为P0，全为自由变量 均取0值，显然不是可行解。取x1为固定变量，进行分支,P0,z=0 x=(0,0,0,0,0)T,P1,z1=0 x=(0,0,0,0,0)T,P2,z2=8 x=(1,0,0,0,0)T,可行解，停止分支,继续分支,0 | 1规划及隐枚举法,模型P1不满足停止分支的条件，继续分支,P1,z1=0 x=(0,0,0,0,0)T,P3,z3=0 x=(0,0,0,0,0)T,P4,z4=2 x=(0,1,0,0,0)T,不可行，停止分支,P5,z5=2 x