数学建模社区-数学中国

标题: 用Lingo求解，没有可行解 [打印本页]

作者: 瓦片 时间: 2012-5-17 09:02
标题: 用Lingo求解，没有可行解
用lingo求解，没有可行解的原因肯能有哪些？
是不是非线性整数规划不能得到全局最优，为什么呢？局部最优可以视为全局最优么？

作者: madio 时间: 2012-5-17 12:42
可能是初始值取的不合适，非线性规划非常复杂，初始值的取法很重要！

作者: 瓦片 时间: 2012-5-17 18:25
但是我里面全部都是0-1变量或则0-1变量的乘积为什么是非线性呢？

作者: qlb061 时间: 2012-5-18 09:20

瓦片发表于 2012-5-17 18:25
但是我里面全部都是0-1变量或则0-1变量的乘积为什么是非线性呢？

因为出现了变量的乘积形式，所以是非线性规划！
如果不知道是何种形式的规划问题，Lingo求解器状态对话框会给出solver类型，你的应该是INLP(整数非线性规划)。
一般来说，非线性规划比较难于求解，除非具有特殊结构，比如目标函数是凸的，此时局部极值点也是全局极值点，其它情况下Lingo给出的都是局部极值点。
没有可行解的原因，可能是建模不当造成的；对于非线性规划，即使存在可行解，Lingo也不能保证一定可以找到可行解，通过使用全局求解器，多初始点求解，给出好的初始点，可以一定程度改善解得质量，但是会耗费较多的时间。

作者: 瓦片 时间: 2012-5-19 16:34

qlb061 发表于 2012-5-18 09:20
因为出现了变量的乘积形式，所以是非线性规划！
如果不知道是何种形式的规划问题，Lingo求解器状态对话框 ...

谢谢你的回答。你所描述的情况正是我现在正遭遇的。说句老实话，我感觉LINGO都有点不可信。比如，有时候，为让他更快找到可行解，加了一个显然的约束，居然说不可行。但是取消显然约束后，运行的局部最优是满足显然约束的。此外，有时候，仅仅是调换一下语句中理论上不影响变量的位置居然也解也会变化。
一般对Linggo有疑惑的时候，你是去修改自己的模型么？不为什么，我的全局最优求解器用不起？

作者: 瓦片 时间: 2012-5-19 16:35

qlb061 发表于 2012-5-18 09:20
因为出现了变量的乘积形式，所以是非线性规划！
如果不知道是何种形式的规划问题，Lingo求解器状态对话框 ...

什么是凸的什么又是凹的呢如何判断目标函数是不是凸的？比如MIN =
@sum(vehicle(k):@sum(level2(j):@sum(level2(i):c(i,j)*x(i,j,k))))+
@sum(truck(k):@sum(level1(j):@sum(level1(i):c(i,j)*y(i,j,k))))+
@sum(vehicle(k):FV*@sum(sat(i):@sum(cus(j):x(i,j,k))))+
@sum(truck(k):FT*@sum(dep(i):@sum(sat(j):y(i,j,k))))+
@sum(dep(i):FD*p(i))+
@sum(sat(i):FS*o(i));!(1)目标函数;

作者: 瓦片 时间: 2012-5-19 16:43

qlb061 发表于 2012-5-18 09:20
因为出现了变量的乘积形式，所以是非线性规划！
如果不知道是何种形式的规划问题，Lingo求解器状态对话框 ...

谢谢你的回答。你所描述的正是我所遭遇的。慢慢的，觉得Lingo不太可靠。比如为了加快其寻找速度，加上显然约束，居然说不可行。但是注销后的解是满足显然约束的。此外，有时候就是替换一下语句的位置也会导致解的不同，位置调换经理论分析是不会导致值改变的。
请问你有遇到类似的问题吗？建一个好的数学模型比编一个好的lingo程序更重要么？没有提示程序情况有误的情况下，是不是往往是模型的问题，求解释。

作者: 瓦片 时间: 2012-5-19 16:51

madio 发表于 2012-5-17 12:42
可能是初始值取的不合适，非线性规划非常复杂，初始值的取法很重要！

如何来取初始值呢？

作者: madio 时间: 2012-5-19 16:59

瓦片发表于 2012-5-19 16:51
如何来取初始值呢？

初值取法没有固定的办法，主要看目标函数的情况，也可以做一些尝试

作者: 瓦片 时间: 2012-5-19 17:51

madio 发表于 2012-5-19 16:59
初值取法没有固定的办法，主要看目标函数的情况，也可以做一些尝试

如何看目标函数的情况呢？

作者: madio 时间: 2012-5-20 09:23

瓦片发表于 2012-5-19 17:51
如何看目标函数的情况呢？

这需要你花时间对目标函数做一定的定性分析，比如了解他的导数情况

作者: qlb061 时间: 2012-5-20 19:18
本帖最后由 qlb061 于 2012-5-20 19:20 编辑

瓦片发表于 2012-5-19 16:34
谢谢你的回答。你所描述的情况正是我现在正遭遇的。说句老实话，我感觉LINGO都有点不可信。比如，有时候， ...

一般情况下，只有在线性规划以及非线性凸规划问题中（但不包括整数约束），我们不必对Lingo给出的解进行额外的考虑，因为他们都是全局最优解（如果存在的话）。但是，整数规划以及一般的非线性规划求解起来都比较困难，不仅仅是Lingo，任何其它规划软件都一样，这是由问题本身所造成的，还有计算机浮点计算的问题！
对于任何类型的问题，Lingo可以自动识别模型的类型，并选择最佳的求解器进行求解，可以认为线性规划求解器和两次规划求解器是比较有效的（两次识别功能需要在Lingo—>Option—>Nonlinear Solver—>strategies—>Quadratic Recogniziton选中，当Lingo识别到问题是两次规划问题，将使用有效的两次规划求解器）。对于非凸的非线性规划问题，只能通过使用全局求解器，选择多初始点求解，给出好的初始点来改进解的质量，另外，当我们能够缩小变量的取值范围时，使用变量范围约束也可能改进解的质量（因为减小了搜索范围）。
理论上，约束的位置是不会改变最优解的取值，但是前提是Lingo能够找到全局最优解，如果不是这样的话，约束的位置会改变搜索的路径，在没有达到最优解时停止下来当然会得出不同的局部极值点！还有比较经常遇到的问题就是在整数规划中的关于变量何时达到整数的规定。
对于你的全局求解器无法使用问题，可能是你使用的是Demo版本，如果想查看你的版本权限，选择Help—>
About Lingo，查看Limits for this Installation即可。

作者: 瓦片 时间: 2012-5-20 22:50
you are so helpful。。。。。非常谢谢。也就是即便约束变量只能取整数，结果变量也肯能出现是整数？此外对于一模一样的大规模问题求解程序。。。不同运行居然有相差比较大的可行解（相同时间点），why？那个解的界是如何求出的，因为和可行解有很大的距离。谢谢。

作者: 瓦片 时间: 2012-5-20 22:52

qlb061 发表于 2012-5-20 19:18
一般情况下，只有在线性规划以及非线性凸规划问题中（但不包括整数约束），我们不必对Lingo给出的解进行 ...

you are so helpful。。。。。非常谢谢。也就是即便约束变量只能取整数，结果变量也肯能出现是整数？此外对于一模一样的大规模问题求解程序。。。不同运行居然有相差比较大的可行解（相同时间点），why？那个解的界是如何求出的，因为和可行解有很大的距离。谢谢。额，如何判断目标函数是不是凸的呢？取初始解的方法有？启发式？

作者: 瓦片 时间: 2012-5-22 17:47

madio 发表于 2012-5-19 16:59
初值取法没有固定的办法，主要看目标函数的情况，也可以做一些尝试

truck/t1 t2/:QT,FT;
vehicle/v1 v2 v3/:QV,FV;
point/d1 s1 s2 c1 c2 c3 c4 c5/;
level1(point)/d1 s1 s2/;
level2(point)/s1 s2 c1 c2 c3 c4 c5/;
variable1(level2,level2,vehicle):x;!变量x表示二级网络中车辆k从点i行驶至点j的0、1 变量.路径问题;
有时候为了搜索速度更快，我们往往会采取数据初始化，请问在上述语句中假设我想使T1从S1到C1，我该如何用init赋予初值呢？谢谢，赋予为1.

作者: 瓦片 时间: 2012-5-22 17:50

qlb061 发表于 2012-5-18 09:20
因为出现了变量的乘积形式，所以是非线性规划！
如果不知道是何种形式的规划问题，Lingo求解器状态对话框 ...

truck/t1 t2/

T,FT;
vehicle/v1 v2 v3/

V,FV;
point/d1 s1 s2 c1 c2 c3 c4 c5/;
level1(point)/d1 s1 s2/;
level2(point)/s1 s2 c1 c2 c3 c4 c5/;
variable1(level2,level2,vehicle):x;!变量x表示二级网络中车辆k从点i行驶至点j的0、1 变量.路径问题;
有时候为了搜索速度更快，我们往往会采取数据初始化，请问在上述语句中假设我想使T1从S1到C1，我该如何用init赋予初值呢？谢谢，赋予为1.

作者: 瓦片 时间: 2012-5-22 17:53

madio 发表于 2012-5-19 16:59
初值取法没有固定的办法，主要看目标函数的情况，也可以做一些尝试

truck/t1 t2/

T,FT;
vehicle/v1 v2 v3/

作者: 瓦片 时间: 2012-5-22 18:01
标题: 启动全局最优求解器情况是这样。。。
本帖最后由瓦片于 2012-5-22 18:03 编辑

快照2.tif (372.78 KB, 下载次数: 2)

[q

快照1.tif (441.02 KB, 下载次数: 0)

uote]qlb061 发表于 2012-5-20 19:18

一般情况下，只有在线性规划以及非线性凸规划问题中（但不包括整数约束），我们不必对Lingo给出的解进行 ...[/quote]

C:\Documents and Settings\Administrator\桌面

作者: qlb061 时间: 2012-5-23 18:04

瓦片发表于 2012-5-22 18:01
[q

uote]qlb061 发表于 2012-5-20 19:18

下载还要扣论坛币。。。看了你的版本应该没问题！

作者: 瓦片 时间: 2012-5-24 16:24

qlb061 发表于 2012-5-23 18:04
下载还要扣论坛币。。。看了你的版本应该没问题！

额，不好意思。再请教你一个问题哈，在TSP问题中，假设出发点为A，但是必须到了F过后才能到B,这个该如何用数学表达呢？F可能直接到B,也可能经由其他点到B，反正B在A之后。谢谢。

作者: qlb061 时间: 2012-5-25 10:03
对于对称的TSP问题（任意 i , j有d(i,j)=d(j,i)），这并不需要额外约束；因为在最优解中，要么先到达f再到达b，要么先到到b在到达f，对于后者将路线方向反过来即可。

作者: 瓦片 时间: 2012-5-25 11:43

qlb061 发表于 2012-5-25 10:03
对于对称的TSP问题（任意 i , j有d(i,j)=d(j,i)），这并不需要额外约束；因为在最优解中，要么先到达f再到达 ...

不一样的，因为是很多个点比如A到了才能到B,C到了才能到D，二者顺序可能不一样，调换过后可能不都满足，不是一对点的问题。

作者: qlb061 时间: 2012-5-28 12:01

瓦片发表于 2012-5-25 11:43
不一样的，因为是很多个点比如A到了才能到B,C到了才能到D，二者顺序可能不一样，调换过后可能不都满足， ...

这样我也不是很清楚，你可以参考有时间窗约束的VRP问题，设置到达的时间顺序。

作者: 瓦片 时间: 2012-5-28 22:19

qlb061 发表于 2012-5-28 12:01
这样我也不是很清楚，你可以参考有时间窗约束的VRP问题，设置到达的时间顺序。

行。thank you all the same.有Q没，我加你，和你了挺投机的。。

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