运筹学第五章整数规划 胡运权

1、运筹学运筹学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院2022-3-242第五章第五章 整数规划整数规划1.整数规划的数学模型整数规划的数学模型2.割平面法割平面法3.分支定界法分支定界法4.0-1整数规划整数规划5.指派问题指派问题6.应用应用2022-3-2433求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。以解决。在整数规划中在整数规划中: : 如果所有的变量都为非负整数，则称为如果所有的变量都

2、为非负整数，则称为纯整数规划问题纯整数规划问题； 如果只有一部分变量为非负整数，则称之为如果只有一部分变量为非负整数，则称之为混合整数规划问题混合整数规划问题。 如果所有的变量都为如果所有的变量都为0-10-1变量，则称之为变量，则称之为0-10-1规划规划。2022-3-2444例例5.15.1 某公司拟用集装箱托运甲、乙两种货物，这两种货物每某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运多少件，可使获得利件，问两种货物各托运多少件，

3、可使获得利润最大润最大? ?货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140第一节第一节 整数规划的数学模型整数规划的数学模型2022-3-2455解：设解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型分别为甲、乙两种货物托运的件数，建立模型 Max z = 2x1 +3 x2 s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0 为整数。为整数。如果去掉最后一个约束，就是一个线性规划问题。如果去掉

4、最后一个约束，就是一个线性规划问题。2022-3-2466得到线性规划的最优解为得到线性规划的最优解为x x1 1=2.44, x=2.44, x2 2=3.26,=3.26,目标函数值为目标函数值为14.6614.66。由图表可看出，整数规划的最优解为由图表可看出，整数规划的最优解为x x1 1=4, x=4, x2 2=2,=2,目标函数值为目标函数值为1414。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=62022-3-2477性质：性质： 任何求任何求最大最大目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最大目标函数值划

5、的最大目标函数值小于或等于小于或等于相应的线性规划的相应的线性规划的最大目标函数值；最大目标函数值； 任何求任何求最小最小目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最小目标函数值划的最小目标函数值大于或等于大于或等于相应的线性规划的相应的线性规划的最小目标函数值。最小目标函数值。2022-3-24813/4,5/2松弛问题第一次切割112221 xx4,1第二次切割x1+x25第二节第二节 割平面法割平面法2022-3-249设纯整数规划设纯整数规划11max. .01,njjjnijjijjZc xa xbstxjn且为整数，伴随伴随LPLP的最优解的最优解#1

6、2(,)TnXxxx#jx若若 全为整数，则为全为整数，则为IPIP的最优解。否则，的最优解。否则，若不全为整数，设第若不全为整数，设第r r行基变量行基变量 非整。对应方程为非整。对应方程为BrrxbBrrjjrj Jxa xb2022-3-2410将将 分离分离成一个整数与一个非负真分数之和：成一个整数与一个非负真分数之和：rrjba及,01,01rrrrrrrjrjrjrjrjrjbNfbffaNfaff则有则有()Brrjrjjrrj JBrrjjrrrjjj Jj JxNfxNfxN xNff x等式两边都为整数并且有等式两边都为整数并且有10rrjjrrrjjj Jj Jff xf

7、ff x 2022-3-2411加入加入松弛变量松弛变量1rjjn krj Jf xxf 此式称为此式称为以以r r行为行为源行（来源行）的割平面，或分数切割式，源行（来源行）的割平面，或分数切割式，或或R.E.GomoryR.E.Gomory( (高莫雷高莫雷) )约束方程约束方程。 将将GomoryGomory约束加入到松弛约束加入到松弛问题问题( (伴随伴随LP)LP)的的最优表中，用最优表中，用对偶单纯形法对偶单纯形法计算，若最优解中还有非整数解，再继续切割，计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。直到全部为整数解。0rjJjrjxff则则1knx2022-3-24

8、12割平面法割平面法，即通过添加约束条件，逐步切割可行区域的，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上来，只要边角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。整数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键关键是通过添加什么样的约束条件，既能让整数解往边是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整数解，这个条件就是界露，同时又不要切去整数解，这个条件就是GomoryGomory约束约束条件。条件。GomoryGomory约束只是割去线性规划可行域的一部分，保留了约束只是割

9、去线性规划可行域的一部分，保留了全部整数解。全部整数解。2022-3-2413 例例5-55-5整数0,521045323. .3max2121212121xxxxxxxxtsxxz2022-3-24运筹学-线性规划14cj3-1000XBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/700-5/70-3/7 选择较大小数的行构造割平面选择较大小数的行构造割平面76727176727165353xxxxx2022-3-24运筹学-线性规划15cj3-10000XBbx1x2x3x4x5x63x113/7101/702

10、/70-1x29/701-2/703/700 x431/700-3/7122/700 x6-6/700-1/70-2/7100-5/70-3/702022-3-24运筹学-线性规划163x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4000-1/40-17/4cj3-10000XBbx1x2x3x4x5x6434141764xxx 2022-3-2417 分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它既是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。能

11、解决纯整数规划的问题，又能解决混合整数规划的问题。大多大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。数求解整数规划的商用软件就是基于分枝定界法而编制成的。1.1. 先先求解整数规划的线性规划求解整数规划的线性规划问题问题( (伴随伴随LP)LP)。2.2. 如果如果其最优解不符合整数条件，则求出整数规划的其最优解不符合整数条件，则求出整数规划的上上下界。下界。3.3. 增加增加约束条件的办法，把相应的线性规划的可行域分成子区约束条件的办法，把相应的线性规划的可行域分成子区域（称为域（称为分枝分枝）4.4. 再再求解这些子区域上的线性规划求解这些子区域上的线性规划问题。问题。5.5.

12、 不断不断缩小缩小整数规划上整数规划上下界的距离，最后得整数规划的最优解下界的距离，最后得整数规划的最优解。第三节分枝定界法第三节分枝定界法2022-3-241818 zz用用分枝定界法分枝定界法求解目标函数值最大的整数规划的求解目标函数值最大的整数规划的步骤步骤，我们将，我们将求解的整数规划求解的整数规划问题称为问题称为A A，将，将与其相对应的线性规划问题称为与其相对应的线性规划问题称为B B： 第一第一步步：求解问题：求解问题B B，可得以下情况之一：，可得以下情况之一： 1.B1.B没有可行解，则没有可行解，则A A也没有可行解，求解过程停止。也没有可行解，求解过程停止。 2.B2.B

13、有最优解，且符合问题有最优解，且符合问题A A的整数条件，则的整数条件，则B B的最优解即为的最优解即为A A的最优解，的最优解，求解过程停止。求解过程停止。 3.B3.B有最优解，但不符合有最优解，但不符合A A的整数条件，记其目标函数值为的整数条件，记其目标函数值为z z1 1。 第二第二步步：确定：确定A A的最优目标函数值的最优目标函数值z z* *的上下界，其上界即的上下界，其上界即为为 , ,再用观察法再用观察法找到找到A A的一个整数可行解，求其目标函数值作为的一个整数可行解，求其目标函数值作为z z* *的下界，记为的下界，记为z z。 第三第三步步：判断：判断 是否等于是否等

14、于z z 。若相等，则整数规划最优解即为其目标函。若相等，则整数规划最优解即为其目标函数值等于数值等于z z的的A A的那个整数可行解；否则进行第四步的那个整数可行解；否则进行第四步。z2022-3-2419 z 第四第四步步：在：在B B的最优解的最优解中中任选任选一一个（或最个（或最远离整数要求的远离整数要求的变量）变量），不妨不妨设此变量为设此变量为x xj j，以，以 b bj j 表示小于表示小于b bj j的最大整数，构造以下两个约束条件，并的最大整数，构造以下两个约束条件，并加入问题加入问题B B，得到，得到B B的两个分枝的两个分枝B B1 1和和B B2 2。x xj j b

15、 bj j 和和x xj j b bj j+1+1 第五第五步步：求解：求解B B1 1和和B B2 2 。修改。修改A A问题的最优目标函数值问题的最优目标函数值z z* *的上下界，的上下界， 和和z z 。 第六第六步步：比较和剪枝。各分枝的：比较和剪枝。各分枝的最优目标函数值中若有小于最优目标函数值中若有小于z z者，则剪者，则剪掉这枝（用打掉这枝（用打表示），即以后不再考虑了。表示），即以后不再考虑了。若大于若大于 ，则不符合整数，则不符合整数条件，则重复第三步至第六步，条件，则重复第三步至第六步，直至直至 = =z z，求出最优解为止。，求出最优解为止。 对于对于求目标函数值最小的

16、整数规划的求解步骤与上述步骤基本相似。求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。zz例例5-65-62022-3-24运筹学-线性规划20?0,3121451149. .max21212121xxxxxxtsxxz例例5.15.1Max 2Max 2x x1 1+3+3x x2 2s.t.s.t. 195 195x x1 1+273+273x x2 213651365 4 4x x1 1+ 40+ 40 x x2 2140140 x x1 1 4 4 x x1 1,x,x2 2 0 0且且x x1 1,x,x2 2为为整数整数2022-3-24运筹学-线性规划212022-3-2

17、422z线性规划线性规划1Z1=14.66X1=2.44X2=3.26z z=13, =13, =14.66 线性规划线性规划2Z2=13.90X1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规划线性规划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z z=13, =13, =14.58 z z=14, =14, =14zz2022-3-2423 0-10-1规划的分支定界法规划的分支定界法 0-10-1规划的规划的适用背景适用背景双态变量的归一化（变量）双态变量的归一化（变量）不相容约束的归一化（约束条件）不相容

18、约束的归一化（约束条件）分段线性函数的归一化（目标函数）分段线性函数的归一化（目标函数）第四节第四节0-10-1规划规划24双态变量的归一化双态变量的归一化,jjjujxv若采取行为否则22,2,x若增加乙产量否则22220 1xyy为变量(1)=1,0,jjjjjjjjjjxu yvyvuvyjy（）若采取行为否则（1 1）多个不全相容约束的归一化）多个不全相容约束的归一化25不全相容约束的归一化不全相容约束的归一化11- (i1 2)s.t.(k1nijjiijmiia x Mybmymkkm 最多只能有 个约束同时起作用，）1,0,iiy第 个约束不起作用2022-3-242612524

19、5372445212121xxxxxx或或)31 (3125245372445321321221121kkyyyMyxxMyxxMyxx（2 2）约束常数项多个互斥取值的归一化）约束常数项多个互斥取值的归一化271110s.t.1,0 1pnijjikkjkpkkka xb yyy为变量28123561023xxx或 32 或 28123123123561023101ixxxyy +32y +28yy +y +y为变量2022-3-2429（3 3）多组约束的归一化）多组约束的归一化302022-3-243131（1 1）固定费用的问题）固定费用的问题例例5.2 5.2 高压容器公司制造小、中

20、、大三种尺寸的金属容器，所用资源为金属高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为考虑固定费用，每种容器售出一只所得的利润分别为 4 4万元、万元、5 5万元、万元、6 6万元，万元，可使用的金属板有可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/ /月，机器有月，机器有100100台台/ /月，此外不管月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是每种容器制

21、造的数量是多少，都要支付一笔固定的费用：小号是l00l00万元，万元，中号为中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一个生产计划，使获得的利万元。现在要制定一个生产计划，使获得的利润为最大。润为最大。分段线性函数的归一化（目标函数）分段线性函数的归一化（目标函数）2022-3-243232解：这是一个整数规划的问题。解：这是一个整数规划的问题。 设设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设固定费用只有在

22、生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第当生产第 i种容器种容器, 即即 xi 0 时时) 或或0（当不生产第当不生产第 i种容器即种容器即 xi = 0 时）。时）。 引入约束引入约束 xi M yi ，i =1，2，3，M充分大，充分大，以以保证保证yi=0 xi=0 这样我们可建立如下的数学模型：这样我们可建立如下的数学模型：Max z = 4Max z = 4x x1 1 + 5+ 5x x2 2 + 6+ 6x x3 3 - 100y- 100y1 1 - 150y- 150y2 2 - 200y- 200y3 3s.ts.t. 2. 2x x1

23、1 + 4+ 4x x2 2 + 8+ 8x x3 3 500 500 2 2x x1 1 + 3+ 3x x2 2 + 4+ 4x x3 3 300 300 x x1 1 + 2+ 2x x2 2 + 3+ 3x x3 3 100 100 xi M yi ，i =1，2，3，M充分大充分大 x xj j 0 0 y yj j 为为0-10-1变量变量，i i = 1,2,3= 1,2,333（2 2）变动费用的问题）变动费用的问题4 ,0520 3(5),51241 2(12), 1220 xxzxxxx 12311221324325577080 1izxxxyxyxyxyy为变量123xx

24、xx令4,053,5122, 1220 xcxx 1jjjjjylxyl例例5.3 2022-3-24340-1 0-1 规划的解法规划的解法隐枚举法隐枚举法: :321523Maxxxxz 10,6434422.3213221321321或或xxxxxxxxxxxxxts2022-3-2435求解思路求解思路: :321523Maxxxxz 10,64344223523.3213221321321321或或xxxxxxxxxxxxxxxxts 2022-3-24362022-3-243737 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由于每人个人可

25、分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使得完成个人，使得完成 n n 项任务项任务的总的效率最高，这就是的总的效率最高，这就是指派问题。指派问题。例例5 5. .4 4 有四个工人，要分别指派他们完成四项不同的工作，每人做各项有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时工作所消耗的时间如下表所示，问应如何指派工作，才

26、能使总的消耗时间为最少。间为最少。第五节第五节 指派问题指派问题2022-3-243838解：解：引入引入0 01 1变量变量 x xijij，并令并令 x xijij = 1(= 1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时) )或或0 0（当不指派第（当不指派第 i i人去人去完成第完成第j j项工作时项工作时) )这可以表示为一个这可以表示为一个0-1整数规划问题：整数规划问题：MinzMinz=15=15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x

27、 x2323+18+18x x2424+26+26x x3131+17+17x x3232+16+16x x3333+19+19x x3434+19+19x x41 41 +21+21x x4242+23+23x x4343+17+17x x4444s.t.s.t. x x1111+ + x x1212+ + x x1313+ + x x1414= 1 (= 1 (甲只能干一项工作甲只能干一项工作) ) x x2121+ + x x2222+ + x x2323+ + x x2424= 1 (= 1 (乙只能干一项工作乙只能干一项工作) ) x x3131+ + x x3232+ + x x3

28、333+ + x x3434= 1 (= 1 (丙只能干一项工作丙只能干一项工作) ) x x4141+ + x x4242+ + x x4343+ + x x4444= 1 (= 1 (丁只能干一项工作丁只能干一项工作) ) x x1111+ + x x2121+ + x x3131+ + x x4141= 1 ( A= 1 ( A工作只能一人干工作只能一人干) ) x x1212+ + x x2222+ + x x3232+ + x x4242= 1 ( B= 1 ( B工作只能一人干工作只能一人干) ) x x1313+ + x x2323+ + x x3333+ + x x4343=

29、1 ( C= 1 ( C工作只能一人干工作只能一人干) ) x x1414+ + x x2424+ + x x3434+ + x x4444= 1 ( D= 1 ( D工作只能一人干工作只能一人干) ) x xijij 为为0-10-1变量变量，i,ji,j = 1,2,3,4= 1,2,3,42022-3-24运筹学-线性规划39变量1011. .min41414141ijiijjijijijijxxxtsxcz定理定理 6-16-1指派问题指派问题的匈牙利算法的匈牙利算法 如果从指派问题效率矩阵如果从指派问题效率矩阵 的每一行元素中分别的每一行元素中分别减去（或加上）一个常数减去（或加上）

30、一个常数 （称为该行的位势），从每一列（称为该行的位势），从每一列分别减去（或加上）一个分别减去（或加上）一个常数常数 （称为该列的位势），得到一称为该列的位势），得到一个新的效率矩阵个新的效率矩阵 ，其中，其中 ，则，则 的最优解等价的最优解等价于于 的最优解，这里的最优解，这里 及及 均非负。均非负。()ijCiujv()ijbijijijbcuv()ijb()ijCijCijbkzxkxcxcxkcznjjninjijijninjijijnjjj111121111）（41定理定理 6-26-2若矩阵若矩阵A A的元素可分成的元素可分成“0 0”与非与非“0 0”两部分，两部分，则覆盖零元

31、素的最少直线数等于位于不同行不同列的则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为零元素（称为独立元素独立元素）的最大个数）的最大个数。0690807434050209效率矩阵效率矩阵 在效率矩阵中找出在效率矩阵中找出4 4个个不同行不同列不同行不同列的数使得它们的总和最小。的数使得它们的总和最小。0001010000101000效率矩阵的变形效率矩阵的变形找出找出4 4个个不同行不同列不同行不同列的的0 0元元使得它们的和为最小使得它们的和为最小0 0，令这些零元素对应的令这些零元素对应的 其余变量其余变量=0=0，得到最优解。，得到最优解。 1,ijx 一一. .算法的基本思想

32、：算法的基本思想：基本步骤基本步骤1.1. 初始变换初始变换-0-0元获得元获得2.2. 最优性检验最优性检验3.3. 非优阵非优阵0 0元的最小直线集合元的最小直线集合4.4. 非优阵变换非优阵变换00元移动元移动43标准化标准化：1.min；2.cij为方阵；为方阵；3.cij为非负常数。为非负常数。非优阵最优, nnnnbb44ui4046484047353544434034344139434247454244vj326 8070 9850 7595 302650506830457500095050350012480009505035001248000001000011000010020

33、22-3-2445其他变异的指派问题其他变异的指派问题求最大值求最大值; ;人数与任务数不相等人数与任务数不相等; ;某个人不能完成某项任务某个人不能完成某项任务; ;2022-3-2446效率矩阵效率矩阵(1)(1)求最大值求最大值; ;ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088 如果指派问题求最大值，用一个较大的数如果指派问题求最大值，用一个较大的数M M去减效率矩阵去减效率矩阵 中所有元素得到效率矩阵中所有元素得到效率矩阵 求矩阵求矩阵B B的最小值，矩的最小值，矩阵阵B B与矩阵与矩阵C C的最优解相同。通常令这个较大的数等于效率矩阵的最优

34、解相同。通常令这个较大的数等于效率矩阵中的最大元素。中的最大元素。(),ijijijBbbMc()ijCc 10322508170131216595157B 解：解：令令max()95,950,ijijijMcbc2022-3-2447 当当 时，虚拟时，虚拟m m- -n n项工作，对应的效率为零；项工作，对应的效率为零；设分配问题中人数为设分配问题中人数为m m，工作数为，工作数为n n。mn (2)(2)人数与任务数不相等人数与任务数不相等; ; 当当 时，虚拟时，虚拟n n- -m m个人，个人， 对应的效率为零；对应的效率为零；nm 有有5个人分配做个人分配做3项工作，则虚拟项工作，

35、则虚拟2项工作，效项工作，效率表变化如下：率表变化如下：例例5.5 5.5 589101517943161718861158900101517009430016171800861100ABCDE1 2 32022-3-2448当某人不能完成某项任务时，令对应的效率为一个大当某人不能完成某项任务时，令对应的效率为一个大M M即可。即可。(3)(3)某个人不能完成某项任务某个人不能完成某项任务; ;表表1 1地点地点1地点地点2地点地点3地点地点4电器电器120300360400服装服装80350420260食品食品150160380300家具家具90200180计算机计算机22026027049

36、321101458ijc 11697874300000MMM2022-3-2450第六节第六节其它应用其它应用1.投资问题投资问题2.选址问题选址问题3.人力资源人力资源分配问题分配问题4.工件工件排序问题排序问题例例5.6 5.6 1 1亿资金投资建厂，亿资金投资建厂，6 6个地址选择个地址选择其中，地址其中，地址1 1、2 2互斥，地址互斥，地址3 3、4 4互斥；地址互斥；地址1 1或或2 2是地址是地址3 3、4 4的的前提条件。该公司应如何选址？前提条件。该公司应如何选址？51投资地址投资地址123456所需资金所需资金/百万元百万元453146363424预期利润预期利润/百万元百

37、万元1611201412101.1.投资投资问题问题解：设解：设x xi i为为521234561234561234311321412422max16112014121045314636342410011. .(1)(1),01iizxxxxxxxxxxxxxxxxxxMys txxMyxxMyxxMyxy为变 量2022-3-245353 例例5.7 5.7 某某公司在今后五年内考虑给以下的项目投资。已知：公司在今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第四年每年年初需要投资，并于次年末回收本利：从第一年到第四年每年年初需要投资，并于次年末回收本利115%115%， 但

38、要求第一年投资最低金额为但要求第一年投资最低金额为4 4万元，第二、三、四年不限；万元，第二、三、四年不限；项目项目B B：第三年初需要投资，到第五年末能回收本利：第三年初需要投资，到第五年末能回收本利128128，但规定最低投，但规定最低投资金额为资金额为3 3万元，最高金额为万元，最高金额为5 5万元；万元； 项目项目 C C：第二年初需要投资，到第五年末能回收本利：第二年初需要投资，到第五年末能回收本利140%140%，但规定其投，但规定其投资额或为资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。 项目项目 D D：五年内每年初可购买公债，于当

39、年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项，此项投资金额不限。投资金额不限。 该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目的每年投资万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大额，使到第五年末拥有的资金本利总额为最大? ?2022-3-245454解：解：1) 设设x xiAiA、x xiBiB、x xiCiC、x xiD iD ( i 1，2，3，4，5)分别表示第分别表示第 i 年年初给项目年年初给项目A，B，C，D的投资额的投资额(元元)； 设设yiA， yiB，是，是01变量，并规定取变量，

40、并规定取 1 时分别表示第时分别表示第 i 年给年给A、B投资，否投资，否则取则取 0（ i = 1, 3）。）。 设设yiC 是非负整数变量，并规定：第是非负整数变量，并规定：第2年投资年投资C项目项目8万元时万元时，取值为取值为4；第；第 2年投资年投资C项目项目6万元时，取值万元时，取值3；第；第2年投资年投资C项目项目4万元时，取值万元时，取值2；第；第2年年投资投资C项目项目2万元时，取值万元时，取值1；第；第2年不投资年不投资C项目时，取值项目时，取值0； 这样我们建立如下的决策变量：这样我们建立如下的决策变量： 第第1 1年年 第第2 2年年 第第3 3年年 第第4 4年年 第第

41、5 5年年 A A x x1A 1A x x2A 2A x x3A3A x x4A4A B B x x3B3B C C x x2C2C=20000y=20000y2C2C D D x x1D 1D x x2D 2D x x3D3D x x4D4D x x5D5D 2022-3-2455552 2）约束条件：）约束条件：第一年：年初有第一年：年初有100000100000元，元，D D项目在年末可收回投资，故第一年年初应把全部资金投出去，项目在年末可收回投资，故第一年年初应把全部资金投出去，于是于是 x x1A1A+ + x x1D 1D = 100000= 100000；第二年：第二年：A A

42、的投资第二年末才可收回，故第二年年初的资金为的投资第二年末才可收回，故第二年年初的资金为1.061.06x x1D1D，于是，于是x x2A2A+ +x x2C2C+ +x x2D2D = = 1.061.06x x1D1D；第三年：年初的资金为第三年：年初的资金为 1.151.15x x1A1A+1.06+1.06x x2D2D，于是，于是 x x3A3A+ +x x3B3B+ +x x3D3D = 1.15 = 1.15x x1A1A+ 1.06+ 1.06x x2D2D；第四年：年初的资金为第四年：年初的资金为 1.151.15x x2A2A+1.06+1.06x x3D3D，于是，于是

43、 x x4A 4A + + x x4D4D = 1.15 = 1.15x x2A2A+ 1.06+ 1.06x x3D3D；第五年：年初的资金为第五年：年初的资金为 1.151.15x x3A3A+1.06+1.06x x4D4D，于是，于是 x x5D 5D = 1.15= 1.15x x3A3A+ 1.06+ 1.06x x4D4D。 关于项目关于项目A A的投资额规定的投资额规定: : x x1A1A 40000 40000y y1A1A ，x x1A1A 200000 200000y y1A1A ，200000200000是足够大的数；是足够大的数；保证当保证当 y y1A1A = 0

44、 = 0时，时， x x1A1A = 0 = 0 ；当；当y y1A1A = 1 = 1时，时，x x1A1A 40000 40000 。 关于项目关于项目B B的投资额规定的投资额规定: : x x3B3B 30000 30000y y3B3B ，x x3B3B 50000 50000y y3B3B ； 保证当保证当 y y3B3B = 0 = 0时，时， x x3B3B = 0 = 0 ；当；当y y3B3B = 1 = 1时，时，50000 50000 x x3B3B 30000 30000 。 关于项目关于项目C C的投资额规定的投资额规定: : x x2C2C = 20000 = 2

45、0000y y2C2C ，y y2C2C = 0 = 0，1 1，2 2，3 3，4 4。2022-3-2456563 3）目标函数及模型：）目标函数及模型： Max z = 1.15Max z = 1.15x x4A4A+ 1.40+ 1.40 x x2C2C+ 1.28+ 1.28x x3B 3B + 1.06+ 1.06x x5D 5D s.t.s.t. x x1A1A+ + x x1D 1D =10=10； x x2A2A+ +x x2C2C+ +x x2D2D = 1.06 = 1.06x x1D1D； x x3A3A+ +x x3B3B+ +x x3D3D = 1.15 = 1.15x x1A1A+ 1.06+ 1.06x x2D2D； x x4A4A+ +x x4D4D = 1.15