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

主要内容4.1整数规划模型及穷举法4.2分支定界法4.3割平面法4.40-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是一个0—1规划问题，例4.4是一个混合整数规划问题。

整数规划模型及穷举法二.穷举法类似于线性规划的图解法，对于二维线性整数规划问题，也可以用图解法—穷举法。用穷举法求解例4.1解：1)先作出该模型的松弛问题的可行域，并标出可行域内所有整数格点;

整数规划模型及穷举法找出松弛问题的解x=(9/4，15/4)，过最优点做目标函数的等值线，令该等值线向可行域内保持平行移动，首先遇到的格点就是最优整数解!此问题的最优解是x*=(3，3)，z*=33。显然不是松弛问题的解4舍5入后的解(2,4)，该点不可行，也不是松弛问题的解取整之后的解(2,3)，该点的目标函数值是25。

单击此处可添加副标题整数规划问题的分支定界法可以求解全整数规划和混合整数规划问题，其基本思想可描述为：首先求解相应的松弛问题；如果最优解不是整数解，将问题的可行域分为两部分，就是进行分支；分别求解这两个分支可行域中的整数规划问题，对两个分支重复这一分支过程，…，当某个分支的解是整数解时，将此解的目标函数值作为一个界，就是进行定界；在求解每个分支问题时，如果松弛问题无可行点或目标函数值小于所定的界(极小问题)，这一分支终止，否则继续求解并继续分支。此求解过程可用一个二叉树描述，原问题的松弛问题是树根，两分支是左右子树，终止分支的子问题是树叶。4.2分支定界法

分支定界法首先引入符号[s]表示对s向下取整，s=s-[s]表示s的小数部分。考虑如下整数规划问题设此问题的松弛问题的解为x*且，则按如下方式进行分支

分支定界法此问题的松弛问题的解为x*=(9/4,15/4)T，x*不是整数解。分支：对x1进行分支，有如下两个问题：例4.1的整数规划问题的求解过程。

分支定界法考虑两问题的可行域，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的求解过程可用下图表示P0z=135/4x1=9/4x2=15/4P1z=100/3x1