数学建模社区-数学中国

标题: 这个程序一直到现在没有人给解释清楚，所以希望大家共同探讨！ [打印本页]

作者: shengshengchina 时间: 2011-10-7 13:26
标题: 这个程序一直到现在没有人给解释清楚，所以希望大家共同探讨！
本帖最后由 shengshengchina 于 2011-10-7 13:26 编辑

说明一下：程序大概意思是说找一个这样的k值，使得下标大于k之后的所有x值都大于3，满足这样的k值中一般有多个，求使得和式：x(1)+...+x(k)为最小的那个k值。

sets:
a:x;
endsets
data:
x=1 2 8 5 7 9 ;
enddata
min=@sum(a(i): @if(i#le#k,x(i),0));
@for(a(i):x(i)>@if(i#ge#k,3,0));
@gin(k);
1<k;
k<6;
结果：
Linearization components added:
   Constraints:       180
   Variables:          96
   Integers:             72

Global optimal solution found.
Objective value:                            3.000000
Objective bound:                            3.000000
Infeasibilities:                            0.000000
Extended solver steps:                               0
Total solver iterations:                            0

                     Variable          Value       Reduced Cost
                           K       3.000000          0.000000
                        X( 1)       1.000000          0.000000
                        X( 2)       2.000000          0.000000
                        X( 3)       8.000000          0.000000
                        X( 4)       5.000000          0.000000
                        X( 5)       7.000000          0.000000
                        X( 6)       9.000000          0.000000
请问：
既然k=3，那么目标函数值应该是：
min=@sum(a(i): @if(i#le#k,x(i),0))=1+2+8=11
但是结果是3，也就是说没有加到8，为什么？

作者: qlb061 时间: 2011-10-12 13:27
简单说说吧! 浮点数在计算机中是使用有限位数来表示的，因此，计算机不可能以任意精度表示一个浮点数。所以，在浮点数数值计算中，就存在舍入误差问题，假定计算机可以表示的最小数值为EPS（也即经常所说的机器零阀值），那么如果两个浮点数差异小于EPS，则计算机等同对待！
现在回到上面的问题，理论上目标函数值的确是11，但是lingo在求解整数规划时，为了避免舍入误差可能导致的问题，在确定一个数是否为整数时允许围绕整数值有一定的偏差，所以，我们只要控制好偏差即可！
这也是在数值计算中经常遇到的问题！稍微修改的模型如下：

作者: qlb061 时间: 2011-10-12 13:29
本帖最后由 qlb061 于 2011-10-12 13:32 编辑

sets:
a:x;
endsets
data:
x=1 2 8 5 7 9 ;
eps = .0001;
enddata
min=@sum(a(i): @if(i#le#k + eps,x(i),0));
@for(a(i):x(i)>@if(i#ge#k - eps,3,0));
@gin(k);
1<=k;
k<=6;

Linearization components added:
   Constraints:       180
   Variables:          96
   Integers:          72

  Global optimal solution found.
  Objective value:                            11.00000
  Objective bound:                            11.00000
  Infeasibilities:                            0.000000
  Extended solver steps:                            0
  Total solver iterations:                            0

                     Variable          Value       Reduced Cost
                        EPS    0.1000000E-03       0.000000
                           K       3.000000          0.000000
                        X( 1)       1.000000          0.000000
                        X( 2)       2.000000          0.000000
                        X( 3)       8.000000          0.000000
                        X( 4)       5.000000          0.000000
                        X( 5)       7.000000          0.000000
                        X( 6)       9.000000          0.000000

                        Row Slack or Surplus    Dual Price
                           1       11.00000          -1.000000
                           2       1.000000          0.000000
                           3       2.000000          0.000000
                           4       5.000000          0.000000
                           5       2.000000          0.000000
                           6       4.000000          0.000000
                           7       6.000000          0.000000
                           8       2.000000          0.000000
                           9       3.000000          0.000000

作者: shengshengchina 时间: 2011-10-14 13:24

qlb061 发表于 2011-10-12 13:29
sets:
a:x;
endsets

首先非常感谢这位lingo高手，就程序来说，我比较佩服你的解答，这个问题我确实没想过，也没意识到这样的问题。
不过，我不太敢确定是不是真的是这个原因，尽管经过你的修改结果没问题。另外，如果真是你说的这个原因的话，那现在我想问，什么时候求得结果才不用考虑这样的误差，什么时候又必须考虑呢。如果是比较复杂的问题，我事先没办法知道我的答案需不需要考虑误差对我的影响。
感觉这样的因素不应该让我们来分析和处理才对啊。

作者: shengshengchina 时间: 2011-10-14 13:28

qlb061 发表于 2011-10-12 13:29
sets:
a:x;
endsets

我还想补充一下，我觉得吧，这个问题这么简单，lingo如果居然因为机器误差而给出错误的答案的话，是不是说明lingo也太“笨”了，一点也不智能！

作者: qlb061 时间: 2011-10-14 19:39

shengshengchina 发表于 2011-10-14 13:28
我还想补充一下，我觉得吧，这个问题这么简单，lingo如果居然因为机器误差而给出错误的答案的话，是不是说 ...

我觉得不应该这样认为吧！或许人工智能之所以不能够实现像人类一样的思维，这也从某个方面说明了问题。认识到机器的缺陷并去避免它，这是高效应用机器的前提条件，也是一个学习和积累的过程！火的发明大大改善了人类的生存环境，但是错误的使用同样可以给人类带来致命性的伤害。
总体来说，Lingo还是比较优秀的优化软件，数值计算中的误差问题并不是只有lingo才有。同样，在Matlab中，如果你告诉机器: a=sin(pi) ,b=0, 你问机器a是否等于b，如果答案是否定的，你也不必灰心丧气！同样这也否定不了matlab 的强大功能！
认识到问题所在，进而避免它才是人所能够完成的。

作者: qlb061 时间: 2011-10-14 19:54

shengshengchina 发表于 2011-10-14 13:24
首先非常感谢这位lingo高手，就程序来说，我比较佩服你的解答，这个问题我确实没想过，也没意识到这样的问 ...

这个问题源于为了避免舍入误差对整数解的影响，所以只有在求解整数规划时，我们才需要考虑这个问题，而且依赖于我们对整数定义的容忍度，即EPS.
另外，不知你有没有注意到Lingo同样不区分“<”和“<=”及“>”和“>=”，所以，在确定严格不等式的时候，我们同样需要加入EPS(同样，它的大小也依赖于我们在多大程度上认为两边不等)

作者: shengshengchina 时间: 2011-10-15 17:58

qlb061 发表于 2011-10-14 19:54
这个问题源于为了避免舍入误差对整数解的影响，所以只有在求解整数规划时，我们才需要考虑这个问题 ...

看来你对lingo认识还是比较深刻的，你让我增长了见识，谢谢你的耐心解答！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)