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

《运筹学第五章整数规划胡运权.ppt》由会员分享，可在线阅读，更多相关《运筹学第五章整数规划胡运权.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

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

3、货物各托运多少件，可使获得利润最大最大?货物货物每件体积每件体积（立方英尺）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140第一节第一节 整数规划的数学模型整数规划的数学模型2022/12/1855解：设解：设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/12/1866得到线性规划的最优解为得到线性规划的最优解为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/12/1877性质：性质：任何求任何求最大最大目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最大目标函数值划的最大目标函

5、数值小于或等于小于或等于相应的线性规划的相应的线性规划的最大目标函数值；最大目标函数值；任何求任何求最小最小目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最小目标函数值划的最小目标函数值大于或等于大于或等于相应的线性规划的相应的线性规划的最小目标函数值。最小目标函数值。2022/12/18813/4,5/2松弛问题第一次切割4,1第二次切割x1+x25第二节第二节 割平面法割平面法2022/12/189设纯整数规划设纯整数规划伴随伴随LP的最优解的最优解若若 全为整数，则为全为整数，则为IP的最优解。否则，的最优解。否则，若不全为整数，设第若不全为整数，设第r r行基

6、变量行基变量 非整。对应方程为非整。对应方程为2022/12/1810将将 分离分离成一个整数与一个非负真分数之和：成一个整数与一个非负真分数之和：则有则有等式两边都为整数并且有等式两边都为整数并且有2022/12/1811加入加入松弛变量松弛变量此式称为此式称为以以r行为行为源行（来源行）的割平面，或分数切割式，源行（来源行）的割平面，或分数切割式，或或R.E.Gomory(高莫雷高莫雷)约束方程约束方程。将将Gomory约束加入到松弛约束加入到松弛问题问题(伴随伴随LP)的的最优表中，用最优表中，用对偶单纯形法对偶单纯形法计算，若最优解中还有非整数解，再继续切割，计算，若最优解中还有非整数

7、解，再继续切割，直到全部为整数解。直到全部为整数解。则则2022/12/1812割平面法割平面法，即通过添加约束条件，逐步切割可行区域的边，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上来，只要整角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键关键是通过添加什么样的约束条件，既能让整数解往边界是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整数解，这个条件就是露，同时又不要切去整数解，这个条件就是GomoryGomory约束条约束条件。件。

8、GomoryGomory约束只是割去线性规划可行域的一部分，保留了全约束只是割去线性规划可行域的一部分，保留了全部整数解。部整数解。2022/12/1813 例例5-55-52022/12/18运筹学-线性规划14cj3-1000XBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/700-5/70-3/7选择较大小数的行构造割平面选择较大小数的行构造割平面2022/12/18运筹学-线性规划15cj3-10000XBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x4

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

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

11、最后得整数规划的最优解。第三节分枝定界法第三节分枝定界法2022/12/181818 用用分枝定界法分枝定界法求解目标函数值最大的整数规划的求解目标函数值最大的整数规划的步骤步骤，我们将，我们将求解的整数规划求解的整数规划问题称为问题称为A A，将，将与其相对应的线性规划问题称为与其相对应的线性规划问题称为B B：第一第一步步：求解问题：求解问题B B，可得以下情况之一：，可得以下情况之一：1.B1.B没有可行解，则没有可行解，则A A也没有可行解，求解过程停止。也没有可行解，求解过程停止。2.B2.B有最优解，且符合问题有最优解，且符合问题A A的整数条件，则的整数条件，则B B的最优解即为

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

13、的A A的那个整数可行解；否则进行第四步的那个整数可行解；否则进行第四步。2022/12/1819 第四第四步步：在：在B的最优解的最优解中中任选任选一一个（或最个（或最远离整数要求的远离整数要求的变量）变量），不妨设不妨设此变量为此变量为xj，以，以bj表示小于表示小于bj的最大整数，构造以下两个约束条件，并加的最大整数，构造以下两个约束条件，并加入问题入问题B，得到，得到B的两个分枝的两个分枝B1和和B2。xj bj和和xj bj+1 第五第五步步：求解：求解B1和和B2。修改。修改A问题的最优目标函数值问题的最优目标函数值z*的上下界，的上下界，和和z。第六第六步步：比较和剪枝。各分枝的

14、：比较和剪枝。各分枝的最优目标函数值中若有小于最优目标函数值中若有小于z者，则剪者，则剪掉这枝（用打掉这枝（用打表示），即以后不再考虑了。表示），即以后不再考虑了。若大于若大于 ，则不符合整数条，则不符合整数条件，则重复第三步至第六步，件，则重复第三步至第六步，直至直至 =z，求出最优解为止。，求出最优解为止。对于对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。例例5-65-62022/12/18运筹学-线性规划20例例5.15.1Max 2Max 2x x1 1+3+3x x2 2s.t.195s.t.195x x1 1+2

15、73+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/12/18运筹学-线性规划212022/12/1822线性规划线性规划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

16、,=14.58 z z=14,=14,=142022/12/1823 0-10-1规划的分支定界法规划的分支定界法 0-10-1规划的规划的适用背景适用背景双态变量的归一化（变量）双态变量的归一化（变量）不相容约束的归一化（约束条件）不相容约束的归一化（约束条件）分段线性函数的归一化（目标函数）分段线性函数的归一化（目标函数）第四节第四节0-10-1规划规划24双态变量的归一化双态变量的归一化（1 1）多个不全相容约束的归一化）多个不全相容约束的归一化25不全相容约束的归一化不全相容约束的归一化2022/12/1826（2 2）约束常数项多个互斥取值的归一化）约束常数项多个互斥取值的归一化27

17、282022/12/1829（3 3）多组约束的归一化）多组约束的归一化302022/12/183131（1 1）固定费用的问题）固定费用的问题例例5.2 5.2 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为考虑固定费用，每种容器售出一只所得的利润分别为 4 4万元、万元、5 5万元、万元、6 6万元，万元，可使用的金属板有可使用的金属板有50

18、0500吨，劳动力有吨，劳动力有300300人人/月，机器有月，机器有100100台台/月，此外不管月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00l00万元，万元，中号为中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一个生产计划，使获得的利万元。现在要制定一个生产计划，使获得的利润为最大。润为最大。分段线性函数的归一化（目标函数）分段线性函数的归一化（目标函数）2022/12/183232解：这是一个整数规划的问题。解：这是一个整数规划的问题。设设x1，x2，x3 分别为小号容器、

19、中号容器和大号容器的生产数量。各种分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设设 yi=1(当生产第当生产第 i种容器种容器,即即 xi 0 时时)或或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+

20、6x x3 3-100y-100y1 1-150y-150y2 2-200y-200y3 3s.t.2s.t.2x x1 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）变动费用的问题）变动费用的问题例例5.3 2022/12/18340-1 0-1 规划的解法规划的解法隐枚举法隐枚举

21、法:2022/12/1835求解思路求解思路:2022/12/18362022/12/183737 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由于每人个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使得完成个人，使得完成 n n 项任务的项任务的总的效率最高，这就是总的效率最高，这就是指派问题。指派问题。例例5 5.4 4 有四个工人，要分别指派他们

22、完成四项不同的工作，每人做各项有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。为最少。第五节第五节 指派问题指派问题2022/12/183838解：解：引入引入0 01 1变量变量 x xijij，并令并令 x xij ij=1(=1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时)或或0 0（当不指派第（当不指派第 i i人去人去完成第完成第j j项工作时项工作时)这可以表示为一个这可以表示为一个0-1整数规划问题：整数规划问题：

23、Minz=15Minz=15x x1111+18+18x x1212+21+21x x1313+24+24x x1414+19+19x x2121+23+23x x2222+22+22x 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 x

24、2323+x x2424=1 (=1 (乙只能干一项工作乙只能干一项工作)x x3131+x x3232+x x3333+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=1 (C=1

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

26、一称为该列的位势），得到一个新的效率矩阵个新的效率矩阵 ，其中，其中 ，则，则 的最优解等价的最优解等价于于 的最优解，这里的最优解，这里 及及 均非负。均非负。41定理定理 6-26-2若矩阵若矩阵A的元素可分成的元素可分成“0”与非与非“0”两部分，两部分，则覆盖零元素的最少直线数等于位于不同行不同列的零则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为元素（称为独立元素独立元素）的最大个数）的最大个数。0690807434050209效率矩阵效率矩阵 在效率矩阵中找出在效率矩阵中找出4个个不同行不同列不同行不同列的数使得它们的总和最小。的数使得它们的总和最小。0001010000

27、101000效率矩阵的变形效率矩阵的变形找出找出4个个不同行不同列不同行不同列的的0元元使得它们的和为最小使得它们的和为最小0，令这些零元素对应的令这些零元素对应的 其余变量其余变量=0，得到最优解。，得到最优解。一一.算法的基本思想：算法的基本思想：基本步骤基本步骤1.1.初始变换初始变换-0-0元获得元获得2.2.最优性检验最优性检验3.3.非优阵非优阵0 0元的最小直线集合元的最小直线集合4.4.非优阵变换非优阵变换00元移动元移动43标准化标准化：1.min；2.cij为方阵；为方阵；3.cij为非负常数。为非负常数。44ui404648404735354443403434413943

28、4247454244vj326 8070 9850 7595 30265050683045750009505035001248000950503500124800000100001100001002022/12/1845其他变异的指派问题其他变异的指派问题求最大值求最大值;人数与任务数不相等人数与任务数不相等;某个人不能完成某项任务某个人不能完成某项任务;2022/12/1846效率矩阵效率矩阵(1)(1)求最大值求最大值;ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088 如果指派问题求最大值，用一个较大的数如果指派问题求最大值，用一个较大的数M M去减

29、效率矩阵去减效率矩阵 中所有元素得到效率矩阵中所有元素得到效率矩阵 求矩阵求矩阵B B的最小值，矩的最小值，矩阵阵B B与矩阵与矩阵C C的最优解相同。通常令这个较大的数等于效率矩阵的最优解相同。通常令这个较大的数等于效率矩阵中的最大元素。中的最大元素。解：解：令令2022/12/1847当当 时，虚拟时，虚拟m m-n n项工作，对应的效率为零；项工作，对应的效率为零；设分配问题中人数为设分配问题中人数为m m，工作数为，工作数为n n。(2)(2)人数与任务数不相等人数与任务数不相等;当当 时，虚拟时，虚拟n n-m m个人，个人，对应的效率为零；对应的效率为零；有有5个人分配做个人分配做

30、3项工作，则虚拟项工作，则虚拟2项工作，效项工作，效率表变化如下：率表变化如下：例例5.5 5.5 ABCDE1 2 32022/12/1848当某人不能完成某项任务时，令对应的效率为一个大当某人不能完成某项任务时，令对应的效率为一个大M M即可。即可。(3)(3)某个人不能完成某项任务某个人不能完成某项任务;表表1 1地点地点1地点地点2地点地点3地点地点4电器电器120300360400服装服装80350420260食品食品150160380300家具家具90200180计算机计算机220260270492022/12/1850第六节第六节其它应用其它应用1.投资问题投资问题2.选址问题选

31、址问题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预期利期利润/百万元百万元1611201412101.1.投资投资问题问题解：设解：设x xi i为为522022/12/185353 例例5.7 5.7 某某公司在今后五年

32、内考虑给以下的项目投资。已知：公司在今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第四年每年年初需要投资，并于次年末回收本利：从第一年到第四年每年年初需要投资，并于次年末回收本利115%115%，但要求第一年投资最低金额为但要求第一年投资最低金额为4 4万元，第二、三、四年不限；万元，第二、三、四年不限；项目项目B B：第三年初需要投资，到第五年末能回收本利：第三年初需要投资，到第五年末能回收本利128128，但规定最低投，但规定最低投资金额为资金额为3 3万元，最高金额为万元，最高金额为5 5万元；万元；项目项目 C C：第二年初需要投资，到第五年末能回收本利：第二年初需要

33、投资，到第五年末能回收本利140%140%，但规定其投，但规定其投资额或为资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。项目项目 D D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项，此项投资金额不限。投资金额不限。该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目的每年投资万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大额，使到第五年末拥有的资金本利总额为最大?2022/12/185454解：解：1)设设x xiAiA、x xiBiB、

34、x xiCiC、x xiD iD(i 1，2，3，4，5)分别表示第分别表示第 i 年年初给项目年年初给项目A，B，C，D的投资额的投资额(元元)；设设yiA，yiB，是，是01变量，并规定取变量，并规定取 1 时分别表示第时分别表示第 i 年给年给A、B投资，投资，否则取否则取 0（i=1,3）。）。设设yiC 是非负整数变量，并规定：第是非负整数变量，并规定：第2年投资年投资C项目项目8万元时万元时，取值为取值为4；第第 2年投资年投资C项目项目6万元时，取值万元时，取值3；第；第2年投资年投资C项目项目4万元时，取值万元时，取值2；第；第2年投资年投资C项目项目2万元时，取值万元时，取值

35、1；第；第2年不投资年不投资C项目时，取值项目时，取值0；这样我们建立如下的决策变量：这样我们建立如下的决策变量：第第1 1年年 第第2 2年年 第第3 3年年 第第4 4年年 第第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/12/1855552 2）约束条件：）约束条件：第一年：年初有第一年：年初有100000100000元，元，D D项目在年末可收回投资，故第一年

36、年初应把全部资金投出去，于项目在年末可收回投资，故第一年年初应把全部资金投出去，于是是 x x1A1A+x x1D 1D=100000=100000；第二年：第二年：A A的投资第二年末才可收回，故第二年年初的资金为的投资第二年末才可收回，故第二年年初的资金为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.0

37、6x x2D2D；第四年：年初的资金为第四年：年初的资金为 1.151.15x x2A2A+1.06+1.06x x3D3D，于是，于是 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 y1

38、A1A ，200000200000是足够大的数；是足够大的数；保证当保证当 y y1A1A=0=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

39、=20000=20000y y2C2C ，y y2C2C=0=0，1 1，2 2，3 3，4 4。2022/12/1856563 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 x4

40、A4A+x x4D4D=1.15=1.15x x2A2A+1.06+1.06x x3D3D；x x5D 5D=1.15=1.15x x3A3A+1.06+1.06x x4D4D；x x1A1A 4 4y y1A1A ，x x1A1A 10 10y y1A1A ，x x3B3B 3 3y y3B3B ，x x3B3B 5 5y y3B3B ；x x2C2C=2=2y y2C2C ，y y2C2C 4 4 x xiAiA ，x xiBiB ，x xiCiC ，x xiDiD 0 (i=1 0 (i=1、2 2、3 3、4 4、5 5）,y y1A1A，y y3B3B 为为0-10-1变量变量,y

41、y2C 2C 整数整数 例例5.8 选择几个村建卫生站，使各村到卫生站的距离都不超过选择几个村建卫生站，使各村到卫生站的距离都不超过5km。各村之间距离见表。各村之间距离见表572.选址问题选址问题 村村234567145689112435683667943465246358例例5.9 某大型活动要举办某大型活动要举办6天，某接待站有天，某接待站有3名正式工作人员，名正式工作人员，4名临时人员。名临时人员。每天：接待站对外开放时间为上午每天：接待站对外开放时间为上午9点至下午点至下午5点。其间须点。其间须2人同时值班，并且至人同时值班，并且至少有少有1名正式人员。每人每次值班时间不少于名正式人

42、员。每人每次值班时间不少于2小时，每天值班的临时人员不超小时，每天值班的临时人员不超过过2人。人。活动期间：临时人员不超过活动期间：临时人员不超过3次，正式人员不超过次，正式人员不超过5次。其余见表次。其余见表593.人力资源分配问题人力资源分配问题 人人员序号序号用人代价用人代价元元/小小时每人每天最多可安排每人每天最多可安排值班的班的时间/小小时第第1天天第第2天天第第3天天第第4天天第第5天天第第6天天临时人人员184400262803463039403404410456040正正式式人人员512884422618244868720484844解：设xij为i人员在j天工作时间（小时），602022/12/18614.4.工件排序问题工件排序问题 例例5-9 5-9 用用4 4台机床加工台机床加工3 3件产品件产品解：设解：设 xij为产品为产品 i 在机床在机床 j 上开始加工的时间上开始加工的时间2022/12/18运筹学-线性规划622022/12/1863习习 题题 5.25.2 5.45.4（1 1）割平面法（）割平面法（2 2）分支定界法）分支定界法 5.65.6 5.95.9（匈牙利法求解）（匈牙利法求解）5.125.12