Question

能力有限啦，向大家求助了，会lingo/matlab的戳进来

6点-10点 需60人
10-14 70
14-18 60
18-22 50
22-2 20
2-6 30
每个人连续工作8个钟
%下面是我用lingo做的代码，我设了x1个人从6点开始工作，x2个人从10点开始工作；
min=x1+x2+x3+x4+x5+x6;

x1+x2>=60;
x2+x3>=70;
x3+x4>=60;
x4+x5>=50;
x5+x6>=20;
x6+x1>=30;
值为150，然后x是取整数的...有很多解
这里有两组：
x=60,10,50,0,30,0
x=50,20,50,0,20,10
我的问题是：x可以有多组解，我想知道有多少组，还是有无限组的，这样就可以弹性安排他们的工作了，焦急痛苦等待中，希望各位朋友能够高抬贵手，小弟感激不尽！！（472126796@qq.com）

Answer 1

1、你贴出来的Lingo代码是错的，正确的应该是：

min=x1+x2+x3+x4+x5+x6;
x6+x1>=60;
x1+x2>=70;
x2+x3>=60;
x3+x4>=50;
x4+x5>=20;
x5+x6>=30;

但你给出的解却是正确的，可能你发现代码错误改过来了，但贴出来的却是原始错误版本。

 

2、可以肯定，整数规划问题的解不可能是无限的，因为整数是可以遍历的。后面再讨论遍历问题。

 

3、就我所知的范围内，Lingo 和 MATLAB 的优化程序都不能提供多组最优解（为了确认这一点，又做了大量的检索工作）。我改写了MATLAB上的 bnb20（一个较为著名的第三方整数规划程序），可以得到多组最优解，贴出来供你参考：

   x1    38  38  38  38  38  38  38  38  39  48
   x2    32  32  32  32  32  32  32  32  31  22
   x3    29  28  30  32  36  29  29  29  29  38
   x4    21  22  20  18  14  21  21  21  21  12
   x5     7   7   7   7   7   8   6   4   9  18
   x6    23  23  23  23  23  22  24  26  21  12

但很遗憾，这仍然不是所有的最优解。

 

从原理上说，分支定界法的思想是先把整数规划的整数条件去掉，按照普通线性规划问题来求解，然后再按照整数条件进行分支，最终求出的各最优解容易局限在普通线性规划的最优解附近，不可能保证得到所有最优解。

 

4、目前我能先到的做法是，进行遍历。遍历的基本思路如下：

（1）按照约束条件，每个变量没必要比它所在的不等式的右值的最大值更大。例如，x1所在的不等式右侧值分别是60和70，那么x1最大取70即可。

（2）每个变量都是非负的，所以最小值取0。

（3）如果仅仅按照上面两个条件，用六重循环遍历的量仍然是很大的。但是，如果考虑到最优解已知（150），那么，内层的循环可以根据外层循环变量的值来决定循环次数，那样肯定可以大大减少循环的总次数。

 

5、思路已经说了，剩下的主要是体力劳动，所以，具体的遍历程序我就不编了。

如果想让我帮你编也可以，至少请提高悬赏激励一下（上面的回答应该对得起目前悬赏的50分了）。没有足够积分的话，可以试一试回答我的问题赚取积分：

 

1000分求助一种字体！！！特点是，数字0里面的斜线向右下斜

zhidao.baidu.com/question/646602728905038445.html