02第二章 整数规划

第二章 整数规划1 概论1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中， 变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适 用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。2o 变量部分限制为整数的，称混合整数规划。1.2 整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 整数规划无可行解。例 1 原线性规划为min z = x + x122x + 4x = 5, x 0, x 01 2 1 2其最优实数解为：x = 0,x = ,min z =。1244 有可行解（当然就存在最优解），但最优解值变差。例 2 原线性规划为min z = x + x122x + 4x = 6, x 0, x 01 2 1 233其最优实数解为：x = 0,x =，min z =。1 2 2 2若限制整数得： x =1,x =1,minz=2。12（ ii） 整数规划最优解不能按照实数最优解简单取整而获得。1.3 求解方法分类：（i）分枝定界法一可求纯或混合整数线性规划。（ii）割平面法一可求纯或混合整数线性规划。（iii）隐枚举法一求解“0-1”整数规划： 过滤隐枚举法； 分枝隐枚举法。（iv）匈牙利法一解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法一求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系 统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子 集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称 为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝， 这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解 整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂 选址问题、背包问题及分配问题等。设有最大化的整数规划问题A,与它相应的线性规划为问题B,从解问题B开始， 若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的 上界，记作Z ；而A的任意可行解的目标函数值将是z*的一个下界z。分枝定界法就 是将B的可行域分成子区域的方法。逐步减小Z和增大z，最终求到z*。现用下例来 说明：例 3 求解下述整数规划Max z = 40x + 90x129x + 7x 561 2 7x + 20x 7012x,x、0且为整数12解G）先不考虑整数限制，即解相应的线性规划B，得最优解为：x =4.8092,x = 1.8168, z = 355.87791 2可见它不符合整数条件。这时z是问题A的最优目标函数值z*的上界，记作z。而 x = 0,x = 0显然是问题A的一个整数可行解，这时z = 0，是z*的一个下界，记作z，1 2即 0 z* 356 。（ii）因为x ,x当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1 2 1 进行分枝，把可行集分成2个子集：x 4.8092 +1 = 511因为4与5之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这 一步称为分枝。这两个子集的规划及求解如下：问题B : Max z = 40x + 90x1 1 29x + 7x 561 2 7x + 20x 70120 x 012最优解为： x =4.0,x =2.1,z =349。1 2 1问题B : Max z = 40x + 90x2 1 29x + 7x 561 2 7x + 20x 5, x 012最优解为： x =5.0,x =1.57,z =341.4。1 2 1再定界： 0z* 349。（iii）对问题B再进行分枝得问题B和B，它们的最优解为1 11 12B : x = 4, x = 2, z = 34011 1 2 11B : x = 1.43, x = 3.00, z = 327.1412 1 2 12再定界：340 z* 341，并将B剪枝。12(iv) 对问题B再进行分枝得问题B和B，它们的最优解为2 21 22B : x = 5.44, x = 1.00, z = 30821 1 2 22B 无可行解。22将B ,B剪枝。21 22于是可以断定原问题的最优解为：x = 4, x = 2, z * = 34012从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为：开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问 题B。G)解问题B可能得到以下情况之一：(a) B 没有可行解，这时 A 也没有可行解，则停止(b) B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则 停止。(c) B有最优解，但不符合问题A的整数条件，记它的目标函数值为Z。(ii)用观察法找问题A的一个整数可行解，一般可取x. = 0, j = 1,n，试探， 求得其目标函数值，并记作Z。以z *表示问题A的最优目标函数值；这时有 z z * z进行迭代。第一步：分枝，在B的最优解中任选一个不符合整数条件的变量.，其值为b， 以b 表示小于b的最大整数。构造两个约束条件x b +1将这两个约束条件，分别加入问题B，求两个后继规划问题B和B。不考虑整数条件12 求解这两个后继问题。定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出 最优目标函数值最大者作为新的上界z。从已符合整数条件的各分支中，找出目标函数 值为最大者作为新的下界z，若无作用z不变。第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，即 以后不再考虑了。若大于z，且不符合整数条件，则重复第一步骤。一直到最后得到 z* = z为止。得最优整数解x*, j = 1,n。3 0-1型整数规划0 -1型整数规划是整数规划中的特殊情形，它的变量x仅取值0或1。这时x称 为0-1变量，或称二进制变量。 x 仅取值0或1这个条件可由下述约束条件：0 x 1，整数j所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0-1变 量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们 先介绍引入0 -1变量的实际问题，再研究解法。3.1引入0 -1变量的实际问题3.1.1 投资场所的选定相互排斥的计划例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置(点)A (i = 1,2,7)可供选择。规定i在东区。由A ,A ,A三个点中至多选两个；123在西区。由 A ,A 两个点中至少选一个；45在南区，由A ,A两个点中至少选一个。67如选用A点，设备投资估计为b元，每年可获利润估计为c元，但投资总额不能iii超过B元。问应选择哪几个点可使年利润为最大？解题时先引入0 1变量x (i = 1,2,-,7)当Ai点被选中， 当含点没被选中.ii 二 1,2,7于是问题可列写成：Max z = c xiii=1 bxiii=1 145x + x 1,673.1.2 相互排斥的约束条件 有两个相互排斥的约束条件5 x + 4 x 24 或 7 x + 3 x 45。1 2 1 2为了统一在一个问题中，引入0 -1变量y，则上述约束条件可改写为:5x + 4x 24 + yM1 27x + 3x 45 + （1 一 y）M12y = 0或 1其中 M 是充分大的数。 约束条件x = 0 或 500 x 80011可改写为500 y x1 800 y y = 0或1如果有m个互相排斥的约束条件：a x hf a x b i 二 1,2,mi1 1in n i为了保证这m个约束条件只有一个起作用，我们引入m个0 -1变量y （i二1,2,m）i和一个充分大的常数M，而下面这一组m +1个约束条件a x ff a x 00 j j j 0j = 123.0,当 x = 0j在构成目标函数时，为了统一在一个问题中讨论，现引入01变量y，令j3）（ 4） 0时yj1,当采用第j种生产方式，即xj 0时，0,当不采用第j种生产方式，即xj= 0时于是目标函数min z 二（k y + e x ） + （k y + e x ） + （k y + e x ）1 11 12 22 23 33 3（3）式这个规定可表为下述3个线性约束条件：y x 100），这几乎是不可能的。因 此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的 方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对 有些问题隐枚举法并不适用，所以有时穷举法还是必要的。 下面举例说明一种解o -1型整数规划的隐枚举法。例 6 Max z 二 3x 2x + 5x123x + 2 x x 21 23x + 4 x + x 4123 x + x 3124 x + x 623、x , x , x = 0或 1123 求解思路及改进措施：(i) 先试探性求一个可行解，易看出(x,x ,x ) = (1,0,0)满足约束条件，故为一123个可行解，且z = 3。(ii) 因为是求极大值问题，故求最优解时，凡是目标值z 3的解不必检验是否 满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件(目标值下界)：( iii) 改进过滤条件。(iv)由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值z大 的组合，这样可提前抬高过滤门槛，以减少计算量。4 蒙特卡洛法(随机取样法) 前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线 性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解 法尚未找到，更何况是非线性整数规划。然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限 个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图 用显枚举法(即穷举法)计算出最优值是不现实的，但是应用概率理论可以证明，在一 定的计算量的情况下，完全可以得出一个满意解。例 7 已知非线性整数规划为：Max z = x2 + x2 + 3x2 + 4x2 + 2x2 8x 2x 3x x 2x12345123450 x 99 (i = 1,5)ix + x + x + x + x 40012345 x + 2 x + 2 x + x + 6 x 800123 452x + x + 6x 200123x + x + 5x 2003 45如果用显枚举法试探，共需计算(100)5 =1010个点，其计算量非常之大。然而应用蒙特卡洛去随机计算106 个点，便可找到满意解，那么这种方法的可信度究竟怎样 呢？下面就分析随机取样采集106 个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。假设目标函数落在高值区的概率分别为0.01， 0.00001，则当计算106个点后，有 任一个点能落在高值区的概率分别为1 0.991000000 0.99 99(100多位)，1 0.999991000000 0.999954602 。解 (i)首先编写M文件mente.m定义目标函数f和约束向量函数g,程序如下: function f,g=mengte(x);f=x(l)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(l)-2*x(2)-3*x(3)-.x(4)-2*x(5);g=sum(x)-400 x(l)+2*x(2)+2*x(3)+x(4)+6*x(5)-8002*x(l)+x(2)+6*x(3)-200 x(3)+x(4)+5*x(5)-200;(ii )编写M文件mainint.m如下求问题的解：rand(state,sum(clock); p0=0;ticfor i=l:10飞x=99*rand(5,l); xl=floor(x);x2=ceil(x);f,g=mengte(xl); if sum(g=0)=4if p0=f x0=xl;p0=f;end end f,g=mengte(x2);if sum(g=0)=4if p0=f x0=x2;p0=f;endendendx0,p0toc本题可以使用LING 0软件求得精确的全局最有解，程序如下：model: sets: row/l.4/:b;col/l.5/:cl,c2,x; link(row,col):a;endsets data: cl=l,l,3,4,2; c2=-8,-2,-3,-l,-2;a=l l l l l1 2 2 l 62 l 6 0 00 0 l l 5;b=400,800,200,200;enddatamax=sum(col:c1*x2+c2*x); for(row(i):sum(col(j):a(i,j)*x(j)b(i);for(col:gin(x); for(col:bnd(0,x,99);end5 指派问题的计算机求解整数规划问题的求解可以使用Lingo等专用软件。对于一般的整数规划问题，无法 直接利用 Matlab 的函数，必须利用 Matlab 编程实现分枝定界解法和割平面解法。但对 于指派问题等0 -1整数规划问题，可以直接利用Matlab的函数bintprog进行求解。例8 求解下列指派问题，已知指派矩阵为_382103_87297642758 42359 106910解：编写 Matlab 程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 58 4 2 3 5;9 10 6 9 10;c=c(:);a=zeros(10,25);for i=1:5a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1;endb=ones(10,1);x,y=bintprog(c,a,b); x=reshape(x,5,5),y求得最优指派方案为x = x = x = x = x = 1，最优值为21。1523324451求解的 LINGO 程序如下：model: sets:var/1.5/;link(var,var):c,x;endsetsdata:c=3821038729764275842359 10 6 9 10; enddatamin=sum(link:c*x);for(var(i):sum(var(j):x(i,j)=1); for(var(j):sum(var(i):x(i,j)=1); for(link:bin(x);end6 生产与销售计划问题6.1 问题实例例 9 某公司用两种原油（ A 和 B ）混合加工成两种汽油（甲和乙）。甲、乙两种 汽油含原油的最低比例分别为50和 60，每吨售价分别为4800元和 5600元。该公 司现有原油A和B的库存量分别为500吨和1000吨,还可以从市场上买到不超过1500 吨的原油A。原油A的市场价为：购买量不超过500吨时的单价为10000元/吨；购买 量超过500吨单不超过1000吨时,超过500吨的部分8000元/吨；购买量超过1000吨 时,超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工。6.2 建立模型（1）问题分析安排原油采购、加工的目标是利润最大，题目中给出的是两种汽油的售价和原油A 的采购价，利润为销售汽油的收入与购买原油A的支出之差。这里的难点在于原油A的 采购价与购买量的关系比较复杂,是分段函数关系,能否及如何用线性规划、整数规划 模型加以处理是关键所在。（2）模型建立设原油A的购买量为x （单位：吨）。根据题目所给数据，采购的支出c（x）可表示 为如下的分段线性函数（以下价格以千元/吨为单位）：10x,0 x 500c（x） = 1000 + 8x, 500 x 1000（5）3000 + 6x, 1000 x 1500设原油A用于生产甲、乙两种汽油的数量分别为x和x，原油B用于生产甲、11 12乙两种汽油的数量分别为x和x ，则总的收入为4.8（x + x ） + 5.6（x + x ）（千21 22 11 21 12 22 元）。于是本例的目标函数（利润）为max z = 4.8（x + x ） + 5.6（x + x ） -c（x）（6）11 21 12 22约束条件包括加工两种汽油用的原油A、原油B库存量的限制，原油A购买量的 限制，以及两种汽油含原油A的比例限制，它们表示为x + x 500 + x（7）11 12x + x 1000（8）21 22x 0.5（10）x + x11 21x12 0.6（11）x + x12 22x ,x ,x ,x ,x 0（12）11 12 21 22由于（5）式中的c（x）不是线性函数，（5）（12）给出的是一个非线性规划，而 且，对于这样用分段函数定义的c（x），一般的非线性规划软件也难以输入和求解。能 不能想办法将该模型化简，从而用现成的软件求解呢？6.3 求解模型下面介绍 3 种解法一个自然的想法是将原油A的采购量x分解为三个量，即用X ,X ,X分别表示以123价 格 10 千 元 / 吨 、 8 千 元 / 吨 、 6 千 元 / 吨 采 购 的 原 油 A 的 吨 数 ， 总 支 出 为 c(x)二 10x + 8x + 6x， 且123x = x + x + x(13)123这时目标函数(6)变为线性函数：max z = 4.8(x + x ) + 5.6(x + x ) (10x + 8x + 6x )(14)11211222123应该注意到，只有当以10千元/吨的价格购买x = 500 (吨)时，才能以8千元/1吨的价格购买x2( 0)，这个条件可以表示为(x 500)x = 0(15)12同理，只有当以8千元/吨的价格购买x = 500 (吨)时，才能以6千元/吨的价格购买2x ( 0) ，于是3( x 500) x = 0( 16)23此外， x , x , x 的取值范围是1230 x ,x ,x 500(17)123由于有非线性约束(15)、(16)，因而(7)(17)构成非线性规划模型。将该模 型输入 LINGO 软件如下：model:sets:var1/1.4/:y; !这里 y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22;var2/1.3/:x,c;endsets max=4.8*(y(1)+y(2)+5.6*(y(3)+y(4)-sum(var2:c*x); y(1)+y(3)sum(var2:x)+500;y(2)+y(4)0; 0.4*y(3)-0.6*y(4)0;(x(1)-500)*x(2)=0; (x(2)-500)*x(3)=0;for(var2:bnd(0,x,500); data: c=10 8 6;enddataend可以用菜单命令“ LINGOIOptions”在“ Global Solver”选项卡上启动全局优化选 型，并运行上述程序求得全局最有解：购买1000吨原油A，与库存的500吨原油A和 1000吨原油B 一起，共生产2500吨汽油乙，利润为5000 (千元)。( 2)解法二引入 01 变量将(15)和(16)转化为线性约束。令z = 1，z = 1，z = 1分别表示以10千元/吨、8千元/吨、6千元/吨的价格采 123购原油A，则约束(15)和(16)可以替换为500z x 500z ，(18)2 11500z x 500z ，(19)3 22x 500z ,(20)33z ,z ,z =0或1123式(7)(14),式(17)-件如下：(21)-(21)构成混合整数线性规划模型，将它输入LINGO软model:sets:var1/1.4/:y; !这里 y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22; var2/1.3/:x,z,c;endsetsmax=4.8*(y(1)+y(2)+5.6*(y(3)+y(4)-sum(var2:c*x); y(1)+y(3)sum(var2:x)+500;y(2)+y(4)0;0.4*y(3)-0.6*y(4)0;for(var1(i)|i #lt# 3:500*z(i+1)x(i);x(i)500*z(i); x(3)500*z(3);for(var2:bin(z);for(var2:bnd(0,x,500);data: c=10 8 6;enddata end( 3 )解法三直接处理分段线性函数c(x)。式(5)表示的函数c(x)如图1所示。记x轴上的分点为b = 0，b = 500，b = 1000。当x属于第1个小区间b ,b 12时，记x = wb312所以 c(x) = wc(b ) + w c(b )。1 1 2 2x = w b + w b， w + w = 1，2 2 3 3 2 33 个 小 区 间 b ,b 时 ，34c(x) = wc(b ) + w c(b )。为了表示x在哪个小区间，引入0-1变量z (k = 1,2,3)，3344当x在第k个小区间时，z = 1，否则，z kk 足w z， w z + z ， w 0，c(x)二 w c(b ) + w c(b )。当 x 属于第2 3 2 2 3 3x = w b + w b ， w + w = 1 ， w , w 0 ，3 3 4 4 3 4 3 4k=0。这样，w , w , w , w , z , z , z 应满1 2 3 4 1 2 3w 0 ( k = 1,2,3,4)(23)1 234kz + z + z = 1 , z , z , z = 0或 1(24)123123此时x和c(x)可以统一地表示为x = wb + w b + w b + w b = 500w + lOOOw +1500w(25)1 12 23 34 4234c(x) = w c(b ) + w c(b ) + w c(b ) + w c(b )11223344=5 0 0v0 + 9 0 0v0 +1 2 0 0v0(26)2 34式(6)( 13),式(22)(26)也构成一个混合整数线性规划模型，可以用 LINGO求解。输入的LINGO模型如下：model:sets:var/1.4/:b,c,y,z,w;!这里y (1)=x11,y(2)=x21,y(3)=x12,y(4)=x22 端点数为4，即分段数为3;endsetsdata:b=0,500,1000,1500; c=0,5000,9000,12000;z = ,0;增加的虚拟变量z(4)=0;enddata max=4.8*(y(1)+y(2)+5.6*(y(3)+y(4)-sum(var:c*w);y(1)+y(3)sum(var:b*w)+500; y(2)+y(4)0; 0.4*y(3)-0.6*y(4)0; w(1)z(1);for(var(i)|i #ne# 1:w(i)z(i-1)+z(i); sum(var:z)=1;sum(var:w)=1; for(var:bin(z);End注：这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第2 和第3种解法，第3种解法更具一般性，其做法如下。设一个n段线性函数f (x)的分点为b b b ，引入w将x和f (x)表示1nn+1kx =严 w bkkk=1f (x )=严 w f (b )kk kk=1w 和0-1变量 z 满足kk27)( 28 )w z ，w z +z ，w z +z ，w 0 ( k = 1,2,n +1)1 2n+1 ， k ()习题二1. 用分枝定界法解：Max z = x + x12f 9,51x + x 114214 2 x + x 0, x , x 整数1 2 1 22. 试将下述非线性的0 1规划问题转换成线性的0 1规划问题max z = x + x x x11 232x + 3x + x 3J123x = 0 或 1, (j = 1,2,3)3. 某钻井队要从以下10个可供选择的井位中确定5 个钻井探油，使总的钻探费 用为最小。若10个井位的代号为s ,s，,s，相应的钻探费用为c ,c，,c，并且1 2 10 1 2 10 井位选择上要满足下列限制条件：(1) 或选择s和s，或选择钻探s ；179(2) 选择了 s或s就不能选s，或反过来也一样；3 45(3) 在 s ,s ,s ,s 中最多只能选两个；试建立这个问题的整数规划模型。56784有一条河流由于河床泥沙淤结，每当上游发生洪水时，就会破堤淹没两岸，造 成人员和财产的损失，为减少总的损失，人们采取破堤泄洪的方法，图2是该河流一岸 区域的信息示意图，在该区域边界上有很高的山，使该区域成为封闭区域。区域内又分 成十五个小区，每个小区内标有三个数字，分别表示该区域的海拔高度 h(m) 、面积S(km2)和被完全淹没时土地、房屋和财产等损失总数k (百万元)，我们假设(a) 各小区间有相对高度为1.2m的小堤相互隔离，例如第一区和第二区之间事 实上有海拔 5.2m 小堤。(b) 当洪水淹没一个小区且洪水高于该小区高度pm时,该小区的损失f (k, p)为该小区的 k 和 p 的函数：0 p 1(c) 假设决堤口，可选在大堤或小堤的任何地方，决堤口的数量不受限制，但已 经决口，就不能再补合，从河流经大堤决口流入小区的洪水量按决口数成比例分配，如 在小区之间小堤开一决口，则假设该两小区之间的这段小堤不复存在，若水位高过小堤， 则将自动向邻近最低的小区泄洪，若这样的小区有多块时，则平均泄洪。求(1)整个区域全部受损失的最小洪水量Q。(2)当洪水量为Q/6，Q/3时，分别制定泄洪方案，使总损失最小(在一种方案中，决堤同时进行)，并计算出该方案的损失数。大堤高山H3.6S6.1K1.411 11H4.0S8.4K7.022H4.7S7.0K5.833H4.4S9.3K3.341H3.8S4.8K2.05551H3.3S3.6K9.46H3.2S0.9K0.9 7H2.5S8.5K6.08 _H5.0S1.8K7.2 92H4.4S0.1K1.6 | 10|H3.0S4.6K3.011H2.5S1.5K4.112H2.4S2.3H3.8S8.8H3.8S1.3K4.4 应K4.1113K5.3 114高山图 2 河流一岸区域示意图表1校址选择数据备选校址B 1B2B3B4B5B6A , AA , AA , A ,A , AA , AA , A覆盖的居民小区15A71 2A , A 5813A524A83646A85. 某市为方便小学生上学，拟在新建的8个居民小区A,A ,A增设若干所1 2 8小学，经过论证知备选校址有：B , B ,B ,它们能够覆盖的居民小区如表1。1 2 6试建立一个数学模型，确定出最小个数的建校地址，使其能覆盖所有的居民小区。6. 某公司新购置了某种设备6台，欲分配给下属的 4 个企业，已知各企业获得这 种设备后年创利润如表2所示，单位为千万元。问应如何分配这些设备能使年创总利润最大，最大利润是多少？表2各企业获得设备的年创利润数企业甲乙丙丁14234264553767647886579866710867有一场由四个项目（高低杠、平衡木、跳马、自由体操） 组成的女子体操团 体赛，赛程规定：每个队至多允许10 名运动员参赛，每一个项目可以有6名选手参加。 每个选手参赛的成绩评分从高到低依次为：10；9.9；9.8；0.1；0。每个代表队的 总分是参赛选手所得总分之和，总分最多的代表队为优胜者。此外，还规定每个运动员 只能参加全能比赛（四项全参加） 与单项比赛这两类中的一类，参加单项比赛的每个运 动员至多只能参加三个单项。每个队应有4 人参加全能比赛，其余运动员参加单项比赛。表3运动员各项目得分及概率分布表、运动员项目、123458.40.159.30.18.40.18.10.18.40.15高低杠9.50.59.50.18.80.29.10.59.50.59.20.259.60.69.00.69.30.39.20.259.40.19.80.2100.19.50.19.40.18.40.18.40.158.10.18.70.19.00.1平衡木8.80.29.00.59.10.58.90.29.20.19.00.69.20.259.30.39.10.69.40.6100.19.40.19.50.19.90.19.70.29.10.18.40.18.40.159.00.18.30.1跳马9.30.18.80.29.50.59.40.18.70.19.50.69.00.69.20.259.50.58.90.69.80.2100.19.40.19.70.39.30.28.70.18.90.19.50.18.40.19.40.1自由体操8.90.29.10.19.70.18.80.29.60.19.10.69.30.69.80.69.00.69.70.69.90.19.60.2100.2100.19.90.2续表3运动员各项目得分及概率分布表运动员项目、6789109.40.19.50.18.40.18.40.159.00.1高低杠9.60.19.70.18.80.29.50.59.20.19.70.69.80.69.00.69.20.259.40.69.90.2100.2100.19.40.19.70.2平衡木8.70.18.40.18.80.058.40.18.10.18.90.28.80.29.20.058.80.19.10.59.10.69.00.69.80.59.20.69.30.39.90.1100.1100.49.80.29.50.18.50.18.30.18.70.18.40.18.20.1口M 778.70.18.70.18.90.28.80.29.20.5跳马8.90.58.90.69.10.69.00.69.40.39.10.39.30.29.90.1100.19.60.18.40.158.40.18.20.19.30.19.10.19.50.58.80.19.30.59.50.19.30.1自由体操9.20.259.20.69.50.39.70.59.50.69.40.19.80.29.80.19.90.39.80.2现某代表队的教练已经对其所带领的10 名运动员参加各个项目的成绩进行了大量 测试，教练发现每个运动员在每个单项上的成绩稳定在4个得分上（见表3） ，她们得 到这些成绩的相应概率也由统计得出（见表中第二个数据。例如：8.40.15表示取得 8.4分的概率为0.15）。试解答以下问题：（1）每个选手的各单项得分按最悲观估算，在此前提下，请为该队排出一个出场 阵容，使该队团体总分尽可能高；每个选手的各单项得分按均值估算，在此前提下， 请为该队排出一个出场阵容，使该队团体总分尽可能高。（2）若对以往的资料及近期各种信息进行分析得到：本次夺冠的团体总分估计为 不少于236.2分，该队为了夺冠应排出怎样的阵容？以该阵容出战，其夺冠的前景如 何？得分前景（即期望值）又如何？它有90的把握战胜怎样水平的对手？