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

《线性规划理论与模型应用.ppt》由会员分享，可在线阅读，更多相关《线性规划理论与模型应用.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主要内容4.1整数规划模型及穷举法整数规划模型及穷举法4.2 分支定界法分支定界法4.3 割平面法割平面法4.4 0-1规划及隐穷举法规划及隐穷举法整数规划问题就是决策变量取整数值的线性或非线性规整数规划问题就是决策变量取整数值的线性或非线性规整数规划问题就是决策变量取整数值的线性或非线性规整数规划问题就是决策变量取整数值的线性或非线性规划，由于非线性整数规划目前还没有一般解法，因此本章仅划，由于非线性整数规划目前还没有一般解法，因此本章仅划，由于非线性整数规划目前还没有一般解法，因此本章仅划，由于非线性整数规划目前还没有一般解法，因此本章仅讨论整数线性规划。在第一章例讨论整数线性规划。在第一

2、章例讨论整数线性规划。在第一章例讨论整数线性规划。在第一章例4 4中的截料问题即是一个整数中的截料问题即是一个整数中的截料问题即是一个整数中的截料问题即是一个整数线性规划问题。整数线性规划问题又可分为：线性规划问题。整数线性规划问题又可分为：线性规划问题。整数线性规划问题又可分为：线性规划问题。整数线性规划问题又可分为：v纯整数纯整数纯整数纯整数(全整数全整数全整数全整数)所有决策变量均要求取整数；所有决策变量均要求取整数；所有决策变量均要求取整数；所有决策变量均要求取整数；v混合整数混合整数混合整数混合整数部分决策变量要求取整数；部分决策变量要求取整数；部分决策变量要求取整数；部分决策变量要

3、求取整数；v纯纯纯纯0 0-1 1规划规划规划规划所有决策变量均要求取所有决策变量均要求取所有决策变量均要求取所有决策变量均要求取0 0或或或或1 1；v混合混合混合混合0 0-1 1规划规划规划规划部分决策变量要求取部分决策变量要求取部分决策变量要求取部分决策变量要求取0 0或或或或1 1。整数规划问题的整数规划问题的整数规划问题的整数规划问题的松弛问题松弛问题松弛问题松弛问题是指在整数规划中去掉整数性约束是指在整数规划中去掉整数性约束是指在整数规划中去掉整数性约束是指在整数规划中去掉整数性约束后的线性规划问题，求解整数规划常常借助于松弛问题。后的线性规划问题，求解整数规划常常借助于松弛问题

4、。后的线性规划问题，求解整数规划常常借助于松弛问题。后的线性规划问题，求解整数规划常常借助于松弛问题。在本章中我们用在本章中我们用在本章中我们用在本章中我们用Z Z表示整数集合；表示整数集合；表示整数集合；表示整数集合；4.1 整数规划模型及穷举法整数规划模型及穷举法整整数数规规划划模模型型及及穷穷举举法法一一一一.整数规划模型整数规划模型整数规划模型整数规划模型 例例例例4.14.1 某厂生产甲、乙两种大型设备，生产中所需物质某厂生产甲、乙两种大型设备，生产中所需物质某厂生产甲、乙两种大型设备，生产中所需物质某厂生产甲、乙两种大型设备，生产中所需物质A A、B B限制如下表所示，其他限制如下

5、表所示，其他限制如下表所示，其他限制如下表所示，其他所需物质和零件充足，问各生所需物质和零件充足，问各生所需物质和零件充足，问各生所需物质和零件充足，问各生产甲、乙设备多少台，利润最大？产甲、乙设备多少台，利润最大？产甲、乙设备多少台，利润最大？产甲、乙设备多少台，利润最大？解：设解：设解：设解：设x x1 1，x x2 2分别为生产甲、乙设备的台数，分别为生产甲、乙设备的台数，分别为生产甲、乙设备的台数，分别为生产甲、乙设备的台数，z z z z为总利为总利为总利为总利润，则润，则润，则润，则整整数数规规划划模模型型及及穷穷举举法法例例4.2(投资决策模型投资决策模型)设有设有n个投资项目，

6、其中第个投资项目，其中第j个项目个项目需要需要aj万元，将来获利润万元，将来获利润cj万元。若现在有资金总万元。若现在有资金总额为额为b万元，则应选那些投资项目获利最大？万元，则应选那些投资项目获利最大？解：设决策变量为解：设决策变量为则该问题的数学模型为则该问题的数学模型为则该问题的数学模型为则该问题的数学模型为整整数数规规划划模模型型及及穷穷举举法法例例例例4.44.4(选址问题选址问题选址问题选址问题)某种商品有某种商品有某种商品有某种商品有n n个销售地，各销售地每月的个销售地，各销售地每月的个销售地，各销售地每月的个销售地，各销售地每月的需求量分别为需求量分别为需求量分别为需求量分别

7、为b bj j吨吨吨吨(j j=1,2,=1,2,n n)。现拟在。现拟在。现拟在。现拟在mm个地点选择建个地点选择建个地点选择建个地点选择建厂，用来生产这种产品以满足供应，且规定一个地址最多厂，用来生产这种产品以满足供应，且规定一个地址最多厂，用来生产这种产品以满足供应，且规定一个地址最多厂，用来生产这种产品以满足供应，且规定一个地址最多只能建一个工厂，若选择第只能建一个工厂，若选择第只能建一个工厂，若选择第只能建一个工厂，若选择第i i个地址建厂将来生产能力为个地址建厂将来生产能力为个地址建厂将来生产能力为个地址建厂将来生产能力为a ai i吨，每月的生产成本为吨，每月的生产成本为吨，每月

8、的生产成本为吨，每月的生产成本为d di i元元元元(i i=1,2,=1,2,mm)。已知从第。已知从第。已知从第。已知从第i i个工个工个工个工厂至第厂至第厂至第厂至第j j个销售地的运价为个销售地的运价为个销售地的运价为个销售地的运价为c cij ij元元元元/吨。应如何选择厂址和安吨。应如何选择厂址和安吨。应如何选择厂址和安吨。应如何选择厂址和安排调运，可使总的费用最小排调运，可使总的费用最小排调运，可使总的费用最小排调运，可使总的费用最小?解：设每月从第解：设每月从第解：设每月从第解：设每月从第i i厂至第厂至第厂至第厂至第j j个销地的运量为个销地的运量为个销地的运量为个销地的运量

9、为x xij ij吨，吨，吨，吨，z z为每月的为每月的为每月的为每月的总费用，总费用，总费用，总费用，设设设设整整数数规规划划模模型型及及穷穷举举法法则该问题的数学模型为：则该问题的数学模型为：则该问题的数学模型为：则该问题的数学模型为：例例4.1是一个全整数规划问题，例是一个全整数规划问题，例4.2是一个是一个01规划规划问题，例问题，例4.4是一个混合整数规划问题。是一个混合整数规划问题。整整数数规规划划模模型型及及穷穷举举法法二二二二.穷举法穷举法穷举法穷举法 类似于线性规划的图解法，对于二维线性整数规划问类似于线性规划的图解法，对于二维线性整数规划问类似于线性规划的图解法，对于二维线

10、性整数规划问类似于线性规划的图解法，对于二维线性整数规划问题，也可以用图解法题，也可以用图解法题，也可以用图解法题，也可以用图解法穷举法。用穷举法求解例穷举法。用穷举法求解例穷举法。用穷举法求解例穷举法。用穷举法求解例4.14.1解：解：1)1)先作出该模型的先作出该模型的松弛问题的可行域，并松弛问题的可行域，并标出可行域内所有整数标出可行域内所有整数格点格点;整整数数规规划划模模型型及及穷穷举举法法 2)2)找出松弛问题的解找出松弛问题的解找出松弛问题的解找出松弛问题的解x x=(9/4=(9/4，15/4)15/4)，过最优点做目标函，过最优点做目标函，过最优点做目标函，过最优点做目标函数

11、的等值线，令该等值线向可行域内保持平行移动，首先数的等值线，令该等值线向可行域内保持平行移动，首先数的等值线，令该等值线向可行域内保持平行移动，首先数的等值线，令该等值线向可行域内保持平行移动，首先遇到的格点就是最优整数解遇到的格点就是最优整数解遇到的格点就是最优整数解遇到的格点就是最优整数解!此问题的最优解是此问题的最优解是x*=(3，3)，z*=33。显然不是显然不是松弛问题松弛问题的解的解4舍舍5入后的解入后的解(2,4)，该点不可行，也不是松弛问题的，该点不可行，也不是松弛问题的解取整之后的解解取整之后的解(2,3)，该点的目标函数值是，该点的目标函数值是25。4.2 分支定界法分支定

12、界法整数规划问题的分支定界法可以求解全整数规划和混合整数规整数规划问题的分支定界法可以求解全整数规划和混合整数规整数规划问题的分支定界法可以求解全整数规划和混合整数规整数规划问题的分支定界法可以求解全整数规划和混合整数规划问题，其基本思想可描述为：划问题，其基本思想可描述为：划问题，其基本思想可描述为：划问题，其基本思想可描述为：1)1)1)1)首先求解相应的松弛问题；首先求解相应的松弛问题；首先求解相应的松弛问题；首先求解相应的松弛问题；2)2)2)2)如果最优解不是整数解，将问题的可行域分为两部分，就如果最优解不是整数解，将问题的可行域分为两部分，就如果最优解不是整数解，将问题的可行域分为

13、两部分，就如果最优解不是整数解，将问题的可行域分为两部分，就是进行是进行是进行是进行分支分支分支分支；3)3)3)3)分别求解这两个分支可行域中的整数规划问题，对两个分分别求解这两个分支可行域中的整数规划问题，对两个分分别求解这两个分支可行域中的整数规划问题，对两个分分别求解这两个分支可行域中的整数规划问题，对两个分支重复这一分支过程，支重复这一分支过程，支重复这一分支过程，支重复这一分支过程，当某个分支的解是整数解时，当某个分支的解是整数解时，当某个分支的解是整数解时，当某个分支的解是整数解时，将此解的目标函数值作为一个界，就是进行将此解的目标函数值作为一个界，就是进行将此解的目标函数值作为

14、一个界，就是进行将此解的目标函数值作为一个界，就是进行定界定界定界定界；4)4)4)4)在求解每个分支问题时，如果松弛问题在求解每个分支问题时，如果松弛问题在求解每个分支问题时，如果松弛问题在求解每个分支问题时，如果松弛问题无可行点无可行点无可行点无可行点或目标函或目标函或目标函或目标函数值小于所定的数值小于所定的数值小于所定的数值小于所定的界界界界(极小问题极小问题极小问题极小问题)，这一分支终止，否则继续，这一分支终止，否则继续，这一分支终止，否则继续，这一分支终止，否则继续求解并继续分支。求解并继续分支。求解并继续分支。求解并继续分支。5)5)5)5)此求解过程可用一个二叉树描述，原问题

15、的松弛问题是树此求解过程可用一个二叉树描述，原问题的松弛问题是树此求解过程可用一个二叉树描述，原问题的松弛问题是树此求解过程可用一个二叉树描述，原问题的松弛问题是树根，两分支是左右子树，终止分支的子问题是树叶。根，两分支是左右子树，终止分支的子问题是树叶。根，两分支是左右子树，终止分支的子问题是树叶。根，两分支是左右子树，终止分支的子问题是树叶。分分支支定定界界法法 首先引入符号首先引入符号首先引入符号首先引入符号 s s 表示对表示对表示对表示对s s 向下取整，向下取整，向下取整，向下取整，=s s-s s 表表表表示示示示s s的小数部分的小数部分的小数部分的小数部分。考虑如下整数规划问

16、题考虑如下整数规划问题考虑如下整数规划问题考虑如下整数规划问题 设此问题的松弛问题的解为设此问题的松弛问题的解为x*且且 ，则按如下，则按如下方式进行分支方式进行分支分分支支定定界界法法例例例例4.14.1的的的的整数规划问题的求解过程。整数规划问题的求解过程。整数规划问题的求解过程。整数规划问题的求解过程。此问题的松弛问题的解为此问题的松弛问题的解为x*=*=(9/4,15/4)T，x*不是整数解。不是整数解。分支：分支：对对x1进行分支，有如下两个问题：进行分支，有如下两个问题：分分支支定定界界法法 考虑两问题的可行考虑两问题的可行考虑两问题的可行考虑两问题的可行域，域，域，域，P P1

17、1的最优点是的最优点是的最优点是的最优点是x x(1)(1)=(2,35/9)=(2,35/9)T T，P P2 2的最的最的最的最优点是优点是优点是优点是x x(2)(2)=(3,3)=(3,3)T T。显然。显然。显然。显然x x(1)(1)不是整数解，而不是整数解，而不是整数解，而不是整数解，而x x(2)(2)是是是是整数解，得出例整数解，得出例整数解，得出例整数解，得出例4.14.1的一的一的一的一个整数解。个整数解。个整数解。个整数解。定界：定界：定界：定界：当得到一个整数当得到一个整数当得到一个整数当得到一个整数解后可对原问题进行定解后可对原问题进行定解后可对原问题进行定解后可对

18、原问题进行定界。界。界。界。z(2)=cx(2)=33，原问题的界为，原问题的界为33，此界在最大值问题中是下，此界在最大值问题中是下界，在最小值问题中是上界。对界，在最小值问题中是上界。对P1继续分支定界，继续分支定界，P1当前当前目标函数值为目标函数值为10+35=45，继续分支，得出以下两个问题：，继续分支，得出以下两个问题：分分支支定定界界法法考虑两问题的可行域如图：考虑两问题的可行域如图：考虑两问题的可行域如图：考虑两问题的可行域如图：P P3 3的最优点是的最优点是的最优点是的最优点是(2,3)(2,3)T T，目标，目标，目标，目标函数值是函数值是函数值是函数值是10+18=28

19、3310+18=2833，停止分，停止分，停止分，停止分支；支；支；支；P P4 4的最优点是的最优点是的最优点是的最优点是(9/5,4)(9/5,4)T T,目目目目标标标标函数值是函数值是函数值是函数值是9+24=33 9+24=33 继续分支，继续分支，继续分支，继续分支，得如下两问题。得如下两问题。得如下两问题。得如下两问题。分分支支定定界界法法考虑两问题的可行域如图：考虑两问题的可行域如图：考虑两问题的可行域如图：考虑两问题的可行域如图：P P5 5的最优点的最优点的最优点的最优点(1,40/9)(1,40/9)T T，目标，目标，目标，目标函数值是函数值是函数值是函数值是5+80/

20、3335+80/3 0 0矛盾，从而割平面矛盾，从而割平面矛盾，从而割平面矛盾，从而割平面方程切割掉了方程切割掉了方程切割掉了方程切割掉了x x*及附近的可行区域。及附近的可行区域。及附近的可行区域。及附近的可行区域。2)2)2)2)割平面方程保留了所有整数解，如果割平面方程保留了所有整数解，如果割平面方程保留了所有整数解，如果割平面方程保留了所有整数解，如果x x是原问题的整数是原问题的整数是原问题的整数是原问题的整数可行解，则根据割平面方程的推导过程，可行解，则根据割平面方程的推导过程，可行解，则根据割平面方程的推导过程，可行解，则根据割平面方程的推导过程，x x显然将满足显然将满足显然将

21、满足显然将满足新的割平面方程，满足原有方程是自然的，即没有切新的割平面方程，满足原有方程是自然的，即没有切新的割平面方程，满足原有方程是自然的，即没有切新的割平面方程，满足原有方程是自然的，即没有切割掉任何整数解。割掉任何整数解。割掉任何整数解。割掉任何整数解。3)3)3)3)建议取最接近建议取最接近建议取最接近建议取最接近0.50.5的的的的f fi i建立割平面方程。建立割平面方程。建立割平面方程。建立割平面方程。割割平平面面法法割平面法的计算步骤：割平面法的计算步骤：割平面法的计算步骤：割平面法的计算步骤：1)1)1)1)用单纯形法求解整数规划问题的松弛问题，得最优基用单纯形法求解整数规

22、划问题的松弛问题，得最优基用单纯形法求解整数规划问题的松弛问题，得最优基用单纯形法求解整数规划问题的松弛问题，得最优基可行解可行解可行解可行解x x(0)(0)，令，令，令，令k k=0=0=0=0；2)2)2)2)若若若若x x(k k)的所有分量均为整数，则即是原问题的最优解，的所有分量均为整数，则即是原问题的最优解，的所有分量均为整数，则即是原问题的最优解，的所有分量均为整数，则即是原问题的最优解，算法停止；否则算法停止；否则算法停止；否则算法停止；否则取取取取x x(k k)中最接近中最接近中最接近中最接近0.50.5的分量，不妨设该分的分量，不妨设该分的分量，不妨设该分的分量，不妨设

23、该分量在单纯形表的第量在单纯形表的第量在单纯形表的第量在单纯形表的第i i行，按前述方法构造行，按前述方法构造行，按前述方法构造行，按前述方法构造割平面方程，割平面方程，割平面方程，割平面方程，并引入松弛变量并引入松弛变量并引入松弛变量并引入松弛变量x xn+k+n+k+1 1，得得得得3)3)将该方程加入到单纯形表中，同时增加对应将该方程加入到单纯形表中，同时增加对应xn+k+1的的列，用对偶单纯形法进行迭代，求得新的松弛问题的列，用对偶单纯形法进行迭代，求得新的松弛问题的最优基可行解最优基可行解x(k+1)，令，令k=k+1+1，转转2)。割割平平面面法法例例例例4.74.7 用割平面法求

24、解下述整数规划问题用割平面法求解下述整数规划问题用割平面法求解下述整数规划问题用割平面法求解下述整数规划问题解：化为标准型解：化为标准型将第二个约束两端乘以将第二个约束两端乘以-1-1，交替使用单纯形法和对偶单，交替使用单纯形法和对偶单纯形法迭代，对其松弛问题进行求解，得如下结果：纯形法迭代，对其松弛问题进行求解，得如下结果：割割平平面面法法此松弛问题的最优基解为此松弛问题的最优基解为此松弛问题的最优基解为此松弛问题的最优基解为x x=(7/6,8/3)=(7/6,8/3)T T，不是整数解，用不是整数解，用不是整数解，用不是整数解，用所在行所在行所在行所在行(第第第第1 1 1 1行行行行)

25、建立割平面：建立割平面：建立割平面：建立割平面：割割平平面面法法引入松弛变量引入松弛变量引入松弛变量引入松弛变量x x5 5，得，得，得，得将此方程加入到单纯形表中，如下所示：将此方程加入到单纯形表中，如下所示：割割平平面面法法x x1 1=3/2=3/2仍不是整数解，用所在行仍不是整数解，用所在行仍不是整数解，用所在行仍不是整数解，用所在行(第第第第2 2行行行行)建立割平面：建立割平面：建立割平面：建立割平面：将此方程加入到最后一个单纯形表中，如下所示：将此方程加入到最后一个单纯形表中，如下所示：割割平平面面法法该单纯形表给出了原问题的最优整数可行解该单纯形表给出了原问题的最优整数可行解该

26、单纯形表给出了原问题的最优整数可行解该单纯形表给出了原问题的最优整数可行解最后一个单纯形表中的非基变量最后一个单纯形表中的非基变量x5的检验数为的检验数为0 0，让进，让进x5基，进行单纯形法迭代，又可得另一个最优整数可行解：基，进行单纯形法迭代，又可得另一个最优整数可行解：4.4 0-1规划及隐枚举法规划及隐枚举法1.1.1.1.0-10-10-10-1规划问题的标准形规划问题的标准形规划问题的标准形规划问题的标准形其中其中cj 0，约束条件必须是约束条件必须是“”。显然在此标准形下，如果显然在此标准形下，如果x=0是此问题的可行解，则也是其是此问题的可行解，则也是其最优解。最优解。0|1规规划划及及隐隐枚枚举举法法1)1)1)1)如果目标系数如果目标系数如果目标系数如果目标系数c cj j 066，停止分支，停止分支所有分支均已停止分支，存在可行解，最优解为：所有分支均已停止分支，存在可行解，最优解为：x*=(0,1,1,0,0)T，z*=z6=6。0|1规规划划及及隐隐枚枚举举法法作业作业作业作业P144 4P144 4P146 6P146 6