《运筹学第五章--整数规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第五章--整数规划优秀课件.ppt（63页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学运筹学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院21第五章第五章 整数规划整数规划1.整数规划的数学模型整数规划的数学模型2.割平面法割平面法3.分支定界法分支定界法4.0-1整数规划整数规划5.指派问题指派问题6.应用应用223求整数解的线性规划问题，不是用四舍五入法或去尾法对线性求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。加以解决。在整数规划中在整数规划中:如果所有的变量都为非负整数，则称为如果所有的变量都为非负整数，则称为纯整数规划问题纯整数
2、规划问题；如果只有一部分变量为非负整数，则称之为如果只有一部分变量为非负整数，则称之为混合整数规划问题混合整数规划问题。如果所有的变量都为如果所有的变量都为0-10-1变量，则称之为变量，则称之为0-10-1规划规划。234例例5.15.1 某公司拟用集装箱托运甲、乙两种货物，这两种货物每某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运甲种货物至多托运4 4件，问两种货物各托运多少件，可使获得利件，问两种货物各托运多少件，可使获得利润最大润最大?货物货物每件体积每件体积（立方英尺
3、）（立方英尺）每件重量每件重量（百千克）（百千克）每件利润每件利润（百元）（百元）甲甲乙乙19527344023托运限制托运限制1365140第一节第一节 整数规划的数学模型整数规划的数学模型245解：设解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型分别为甲、乙两种货物托运的件数，建立模型 Max z=2x1+3 x2 s.t.195 x1+273 x2 1365 4 x1+40 x2 140 x1 4 x1，x2 0 为整数。为整数。如果去掉最后一个约束，就是一个线性规划问题。如果去掉最后一个约束，就是一个线性规划问题。256得到线性规划的最优解为得到线性规划的最优解为x x1 1
4、=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=6267性质：性质：任何求任何求最大最大目标函数值的纯整数规划或混合整数规目标函数值的纯整数规划或混合整数规划的最大目标函数值划的最大目标函数值小于或等于小于或等于相应的线性规划的相应的线性规划的最大目标函数值；最大目标函数值；任何求任何求最小最小目标函数值的纯整数规
5、划或混合整数规目标函数值的纯整数规划或混合整数规划的最小目标函数值划的最小目标函数值大于或等于大于或等于相应的线性规划的相应的线性规划的最小目标函数值。最小目标函数值。2713/4,5/2松弛问题第一次切割4,1第二次切割x1+x25第二节第二节 割平面法割平面法28设纯整数规划设纯整数规划伴随伴随LP的最优解的最优解若若 全为整数，则为全为整数，则为IP的最优解。否则，的最优解。否则，若不全为整数，设第若不全为整数，设第r r行基变量行基变量 非整。对应方程为非整。对应方程为29将将 分离成一个整数与一个非负真分数之和：分离成一个整数与一个非负真分数之和：则有则有等式两边都为整数并且有等式两
6、边都为整数并且有210加入松弛变量加入松弛变量此式称为以此式称为以r行为源行（来源行）的割平面，或分数切割式，行为源行（来源行）的割平面，或分数切割式，或或R.E.Gomory(高莫雷高莫雷)约束方程约束方程。将将Gomory约束加入到松弛问题约束加入到松弛问题(伴随伴随LP)的最优表中，用的最优表中，用对偶单纯形法对偶单纯形法计算，若最优解中还有非整数解，再继续切割，计算，若最优解中还有非整数解，再继续切割，直到全部为整数解。直到全部为整数解。则则211割平面法割平面法，即通过添加约束条件，逐步切割可行区域的边，即通过添加约束条件，逐步切割可行区域的边角余料，让其整数解逐步的露到边界或顶点上
7、来，只要整角余料，让其整数解逐步的露到边界或顶点上来，只要整数解能曝露到顶点上来，则就可以利用单纯形法求出来。数解能曝露到顶点上来，则就可以利用单纯形法求出来。关键关键是通过添加什么样的约束条件，既能让整数解往边界是通过添加什么样的约束条件，既能让整数解往边界露，同时又不要切去整数解，这个条件就是露，同时又不要切去整数解，这个条件就是GomoryGomory约束条约束条件。件。GomoryGomory约束只是割去线性规划可行域的一部分，保留了全约束只是割去线性规划可行域的一部分，保留了全部整数解。部整数解。212 例例5-55-5213cj3-1000XBbx1x2x3x4x53x113/71
8、01/702/7-1x29/701-2/703/70 x431/700-3/7122/700-5/70-3/7选择较大小数的行构造割平面选择较大小数的行构造割平面214cj3-10000XBbx1x2x3x4x5x63x113/7101/702/70-1x29/701-2/703/700 x431/700-3/7122/700 x6-6/700-1/70-2/7100-5/70-3/702153x11100001-1x25/4010-1/40-5/40 x35/2001-1/20-11/20 x57/40001/41-3/4000-1/40-17/4cj3-10000XBbx1x2x3x4x5
9、x6216 分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它既是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。成的。1.1.先求解整数规划的线性规划问题先求解整数规划的线性规划问题(伴随伴随LP)LP)。2.2.如果其最优解不符合整数条件，则求出整数规划的如果其最优解不符合整数条件，则求出整数规划的上下界。上下界。3.3.增加约束条件的办法，把相应的线性规划的可行域分成子区增加
10、约束条件的办法，把相应的线性规划的可行域分成子区域（称为域（称为分枝分枝）4.4.再求解这些子区域上的线性规划问题。再求解这些子区域上的线性规划问题。5.5.不断缩小整数规划上下界的距离，最后得整数规划的最优解不断缩小整数规划上下界的距离，最后得整数规划的最优解。第三节分枝定界法第三节分枝定界法21718 用用分枝定界法分枝定界法求解目标函数值最大的整数规划的求解目标函数值最大的整数规划的步骤步骤，我们将，我们将求解的整数规划求解的整数规划问题称为问题称为A A，将，将与其相对应的线性规划问题称为与其相对应的线性规划问题称为B B：第一步第一步：求解问题：求解问题B B，可得以下情况之一：，可
11、得以下情况之一：1.B1.B没有可行解，则没有可行解，则A A也没有可行解，求解过程停止。也没有可行解，求解过程停止。2.B2.B有最优解，且符合问题有最优解，且符合问题A A的整数条件，则的整数条件，则B B的最优解即为的最优解即为A A的最优解，的最优解，求解过程停止。求解过程停止。3.B3.B有最优解，但不符合有最优解，但不符合A A的整数条件，记其目标函数值为的整数条件，记其目标函数值为z z1 1。第二步第二步：确定：确定A A的最优目标函数值的最优目标函数值z*z*的上下界，其上界即为的上下界，其上界即为 ,再用观察法再用观察法找到找到A A的一个整数可行解，求其目标函数值作为的一
12、个整数可行解，求其目标函数值作为z*z*的下界，记为的下界，记为z z。第三步第三步：判断：判断 是否等于是否等于z z 。若相等，则整数规划最优解即为其目标函。若相等，则整数规划最优解即为其目标函数值等于数值等于z z的的A A的那个整数可行解；否则进行第四步。的那个整数可行解；否则进行第四步。218 第四步第四步：在：在B的最优解中的最优解中任选一个（或最远离整数要求的变量）任选一个（或最远离整数要求的变量），不妨设，不妨设此变量为此变量为xj，以，以bj表示小于表示小于bj的最大整数，构造以下两个约束条件，并加的最大整数，构造以下两个约束条件，并加入问题入问题B，得到，得到B的两个分枝的
13、两个分枝B1和和B2。xj bj和和xj bj+1 第五步第五步：求解：求解B1和和B2。修改。修改A问题的最优目标函数值问题的最优目标函数值z*的上下界，的上下界，和和z。第六步第六步：比较和剪枝。各分枝的：比较和剪枝。各分枝的最优目标函数值中若有小于最优目标函数值中若有小于z者，则剪者，则剪掉这枝（用打掉这枝（用打表示），即以后不再考虑了。表示），即以后不再考虑了。若大于若大于 ，则不符合整数条，则不符合整数条件，则重复第三步至第六步，件，则重复第三步至第六步，直至直至 =z，求出最优解为止。，求出最优解为止。对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。对于求目标函数值最小
14、的整数规划的求解步骤与上述步骤基本相似。219例例5-65-6220例例5.15.1Max 2Max 2x x1 1+3+3x x2 2s.t.195s.t.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为整数为整数221线性规划线性规划1Z1=14.66X1=2.44X2=3.26z z=13,=13,=14.66 线性规划线性规划2Z2=13.90X1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规
15、划线性规划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z z=13,=13,=14.58 z z=14,=14,=14222 0-10-1规划的分支定界法规划的分支定界法 0-10-1规划的规划的适用背景适用背景双态变量的归一化（变量）双态变量的归一化（变量）不相容约束的归一化（约束条件）不相容约束的归一化（约束条件）分段线性函数的归一化（目标函数）分段线性函数的归一化（目标函数）第四节第四节0-10-1规划规划223双态变量的归一化双态变量的归一化7/5/202424（1 1）多个不全相容约束的归一化）多个不全相容约束的归一化不全相容约束的归一
16、化不全相容约束的归一化7/5/202425226（2 2）约束常数项多个互斥取值的归一化）约束常数项多个互斥取值的归一化7/5/2024277/5/202428229（3 3）多组约束的归一化）多组约束的归一化7/5/20243031（1 1）固定费用的问题）固定费用的问题例例5.2 5.2 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为不考虑固定
17、费用，每种容器售出一只所得的利润分别为 4 4万元、万元、5 5万元、万元、6 6万元，可使用的金属板有万元，可使用的金属板有500500吨，劳动力有吨，劳动力有300300人人/月，机器有月，机器有100100台台/月，此月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00l00万元，中号为万元，中号为 150 150 万元，大号为万元，大号为200200万元。现在要制定一个生产计划，使万元。现在要制定一个生产计划，使获得的利润为最大。获得的利润为最大。分段线性函数的归一化（目标函数）分段线性函数的归一化（目
18、标函数）23132解：这是一个整数规划的问题。解：这是一个整数规划的问题。设设x1，x2，x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi=1(当生产第当生产第 i种容器种容器,即即 xi 0 时时)或或0（当不生产第当不生产第 i种容器即种容器即 xi=0 时）。时）。引入约束引入约束 xi M yi ，i=1，2，3，M充分大，充分大，以保证以保证yi=0 xi=0 这样我们可建立如下
19、的数学模型：这样我们可建立如下的数学模型：Max z=4Max z=4x x1 1+5+5x x2 2+6+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,3232（2 2）变动费
20、用的问题）变动费用的问题例例5.3 7/5/2024330-1 0-1 规划的解法规划的解法隐枚举法隐枚举法:234求解思路求解思路:23523637 有有 n n 项不同的任务，恰好项不同的任务，恰好 n n 个人可分别承担这些任务，但由于每个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把人去完成一项任务，怎样把 n n 项任务指派给项任务指派给 n n 个人，使得完成个人，使得完成 n n 项项任务的总的效率最高，这就是任务的总的效率最高，这就是指派问题。指派
21、问题。例例5 5.4 4 有四个工人，要分别指派他们完成四项不同的工作，每人做各项有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。间为最少。第五节第五节 指派问题指派问题23738解：解：引入引入0 01 1变量变量 x xijij，并令并令 x xij ij=1(=1(当指派第当指派第 i i人去完成第人去完成第j j项工作时项工作时)或或0 0（当不指派第（当不指派第 i i人去人去完成第完成第j j项工作时项工作时)这可以表示为一个这可以表示为一个
22、0-1整数规划问题：整数规划问题：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
23、x2121+x x2222+x x2323+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 x333
24、3+x x4343=1 (C=1 (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,4238239定理定理 6-16-1指派问题的匈牙利算法指派问题的匈牙利算法 如果从指派问题效率矩阵如果从指派问题效率矩阵 的每一行元素中分别的每一行元素中分别减去（或加上）一个常数减去（或加上）一个常数 （称为该行的位势），从每一列（称为该行的位势），从每一列分别减去（或加上）一个常数分别减去（或加上）一个常数 （称为该列的位势）
25、，得到一（称为该列的位势），得到一个新的效率矩阵个新的效率矩阵 ，其中，其中 ，则，则 的最优解等价的最优解等价于于 的最优解，这里的最优解，这里 及及 均非负。均非负。40定理定理 6-26-2若矩阵若矩阵A的元素可分成的元素可分成“0”与非与非“0”两部两部分，则覆盖零元素的最少直线数等于位于不同行不同分，则覆盖零元素的最少直线数等于位于不同行不同列的零元素（称为列的零元素（称为独立元素独立元素）的最大个数。）的最大个数。7/5/2024410690807434050209效率矩阵效率矩阵 在效率矩阵中找出在效率矩阵中找出4个个不同行不同列不同行不同列的数使得它们的总和最小。的数使得它们的
26、总和最小。0001010000101000效率矩阵的变形效率矩阵的变形找出找出4个个不同行不同列不同行不同列的的0元元使得它们的和为最小使得它们的和为最小0，令这些零元素对应的令这些零元素对应的 其余变量其余变量=0，得到最优解。，得到最优解。一一.算法的基本思想：算法的基本思想：42基本步骤基本步骤1.1.初始变换初始变换-0-0元获得元获得2.2.最优性检验最优性检验3.3.非优阵非优阵0 0元的最小直线集合元的最小直线集合4.4.非优阵变换非优阵变换00元移动元移动标准化标准化：1.min；2.cij为方阵；为方阵；3.cij为非负常数。为非负常数。7/5/202443ui4046484
27、047353544434034344139434247454244vj326 8070 9850 7595 30265050683045750009505035001248000950503500124800000100001100001007/5/202444其他变异的指派问题其他变异的指派问题求最大值求最大值;人数与任务数不相等人数与任务数不相等;某个人不能完成某项任务某个人不能完成某项任务;245效率矩阵效率矩阵(1)(1)求最大值求最大值;ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088 如果指派问题求最大值，用一个较大的数如果指派问题求最大值，
28、用一个较大的数M M去减效率矩阵去减效率矩阵 中所有元素得到效率矩阵中所有元素得到效率矩阵 求矩阵求矩阵B B的最小值，矩的最小值，矩阵阵B B与矩阵与矩阵C C的最优解相同。通常令这个较大的数等于效率矩阵的最优解相同。通常令这个较大的数等于效率矩阵中的最大元素。中的最大元素。解：解：令令246当当 时，虚拟时，虚拟m m-n n项工作，对应的效率为零；项工作，对应的效率为零；设分配问题中人数为设分配问题中人数为m m，工作数为，工作数为n n。(2)(2)人数与任务数不相等人数与任务数不相等;当当 时，虚拟时，虚拟n n-m m个人，个人，对应的效率为零；对应的效率为零；有有5个人分配做个人
29、分配做3项工作，则虚拟项工作，则虚拟2项工作，效项工作，效率表变化如下：率表变化如下：例例5.5 5.5 ABCDE1 2 3247当某人不能完成某项任务时，令对应的效率为一个大当某人不能完成某项任务时，令对应的效率为一个大M M即可。即可。(3)(3)某个人不能完成某项任务某个人不能完成某项任务;表表1 1地点地点1地点地点2地点地点3地点地点4电器电器120300360400服装服装80350420260食品食品150160380300家具家具90200180计算机计算机2202602702487/5/202449第六节其它应用第六节其它应用1.投资问题投资问题2.选址问题选址问题3.人力
30、资源分配问题人力资源分配问题4.工件排序问题工件排序问题250例例5.6 5.6 1 1亿资金投资建厂，亿资金投资建厂，6 6个地址选择个地址选择其中，地址其中，地址1 1、2 2互斥，地址互斥，地址3 3、4 4互斥；地址互斥；地址1 1或或2 2是地址是地址3 3、4 4的的前提条件。该公司应如何选址？前提条件。该公司应如何选址？投资地址投资地址123456所需资金所需资金/百万元百万元453146363424预期利润预期利润/百万元百万元1611201412101.1.投资问题投资问题7/5/202451解：设解：设x xi i为为7/5/20245253 例例5.7 5.7 某公司在今
31、后五年内考虑给以下的项目投资。已知：某公司在今后五年内考虑给以下的项目投资。已知：项目项目A A：从第一年到第四年每年年初需要投资，并于次年末回收本利：从第一年到第四年每年年初需要投资，并于次年末回收本利115%115%，但要求第一年投资最低金额为但要求第一年投资最低金额为4 4万元，第二、三、四年不限；万元，第二、三、四年不限；项目项目B B：第三年初需要投资，到第五年末能回收本利：第三年初需要投资，到第五年末能回收本利128128，但规定最低，但规定最低投资金额为投资金额为3 3万元，最高金额为万元，最高金额为5 5万元；万元；项目项目 C C：第二年初需要投资，到第五年末能回收本利：第二
32、年初需要投资，到第五年末能回收本利140%140%，但规定其投，但规定其投资额或为资额或为2 2万元或为万元或为4 4万元或为万元或为6 6万元或为万元或为8 8万元。万元。项目项目 D D：五年内每年初可购买公债，于当年末归还，并加利息：五年内每年初可购买公债，于当年末归还，并加利息6%6%，此项，此项投资金额不限。投资金额不限。该部门现有资金该部门现有资金1010万元，问它应如何确定给这些项目的每年投资万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大额，使到第五年末拥有的资金本利总额为最大?25354解：解：1)设设x xiAiA、x xiBiB、x xiC
33、iC、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万元时，取值万元时，取值1；第；第
34、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 254552 2）约束条件：）约束条件：第一年：年初有第一年：年初有100000100000元，元，D D项目在年末可收回投资，故第一年年初应把全部资金投出去，项目
35、在年末可收回投资，故第一年年初应把全部资金投出去，于是于是 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.06x x2D2D；第四年：年
36、初的资金为第四年：年初的资金为 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 y1A1A ，200000200
37、000是足够大的是足够大的数；保证当数；保证当 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=20000=20000y
38、y2C2C ，y y2C2C=0=0，1 1，2 2，3 3，4 4。255563 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=1.15x
39、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 y2C 2C 整数整数 256例例5.8 选择
40、几个村建卫生站，使各村到卫生站的距离都不超过选择几个村建卫生站，使各村到卫生站的距离都不超过5km。各村之间距离见表。各村之间距离见表2.选址问题选址问题 村23456714568911243568366794346524637/5/2024577/5/202458例例5.9 某大型活动要举办某大型活动要举办6天，某接待站有天，某接待站有3名正式工作人员，名正式工作人员，4名名临时人员。临时人员。每天：接待站对外开放时间为上午每天：接待站对外开放时间为上午9点至下午点至下午5点。其间须点。其间须2人同时人同时值班，并且至少有值班，并且至少有1名正式人员。每人每次值班时间不少于名正式人员。每人每
41、次值班时间不少于2小时，小时，每天值班的临时人员不超过每天值班的临时人员不超过2人。人。活动期间：临时人员不超过活动期间：临时人员不超过3次，正式人员不超过次，正式人员不超过5次。其余见表次。其余见表3.人力资源分配问题人力资源分配问题 人员人员序号序号用人代价用人代价元元/小时小时每人每天最多可安排值班的时间每人每天最多可安排值班的时间/小时小时第第1天天第第2天天第第3天天第第4天天第第5天天第第6天天临临时时人人员员184400262803463039403404410456040正正式式人人员员5128844226182448687204848447/5/202459解：设xij为i人员在j天工作时间（小时），7/5/2024604.4.工件排序问题工件排序问题 例例5-9 5-9 用用4 4台机床加工台机床加工3 3件产品件产品261解：设解：设 xij为产品为产品 i 在机床在机床 j 上开始加工的时间上开始加工的时间262习习 题题 5.25.2 5.45.4（1 1）割平面法（）割平面法（2 2）分支定界法）分支定界法 5.65.6 5.95.9（匈牙利法求解）（匈牙利法求解）5.125.12263