[原创]整数规划

ATK1992 · 发表于 2005-8-26 04:48:32

<

>高手请帮忙解，
<

>min z= 4*x1+5*x2
<

> 3*x1+x2>=2
x1+4*x2>=5
3*x1+2*x2>=7

x1,x2>=0为整数

sink · 发表于 2005-8-26 05:17:23

<

>min 4x1+5x2
<

>st
<

>3x1+x2>=2
x1+4x2>=5
3x1+2x2>=7
x1>0 x2>0
end 
gin 2 
 
结果:
 OBJECTIVE FUNCTION VALUE
 1) 13.00000
 VARIABLE VALUE REDUCED COST X1 2.000000 4.000000 X2 1.000000 5.000000
 ROW SLACK OR SURPLUS DUAL PRICES 2) 5.000000 0.000000 3) 1.000000 0.000000 4) 1.000000 0.000000 5) 2.000000 0.000000 6) 1.000000 0.000000
 NO. ITERATIONS= 7 BRANCHES= 1 DETERM.= 1.000E 0

[此贴子已经被作者于2005-8-26 10:47:08编辑过]

mvpsion · 发表于 2005-8-26 08:18:42

求解的有问题吧

mvpsion · 发表于 2005-8-26 08:32:12

<

>最优解是14
<

>x1=1,x2=2

娴子 · 发表于 2005-8-26 18:55:34

<

>我用LINGO算的和你们的不一样啊？程序如下：
<

>min= 4*x1+5*x2; 3*x1+x2>=2; x1+4*x2>=5; 3*x1+2*x2>=7; Global optimal solution found at iteration: 3 Objective value: 11.20000
<

> Variable Value Reduced Cost X1 1.800000 0.000000 X2 0.8000000 0.000000
 Row Slack or Surplus Dual Price 1 11.20000 -1.000000 2 4.200000 0.000000 3 0.000000 -0.7000000 4 0.000000 -1.100000

娴子 · 发表于 2005-8-26 19:06:26

我刚刚才发现题目叫求的是整数，应该怎么做才是整数啊？我加了GIN 2也还是不行啊？

ATK1992 · 发表于 2005-8-27 00:02:13

<

>感激不尽！
<

>不知高手能否给出MATLAB的算法！
<

>LINGO 俺不是很，，，

SummerRain · 发表于 2005-8-27 01:11:32

<

>min= 4*x1+5*x2; 3*x1+x2>=2; x1+4*x2>=5; 3*x1+2*x2>=7; @gin(x1); @gin(x2); 
<

> Global optimal solution found at iteration: 0 Objective value: 13.00000
<

> Variable Value Reduced Cost X1 2.000000 4.000000 X2 1.000000 5.000000
 Row Slack or Surplus Dual Price 1 13.00000 -1.000000 2 5.000000 0.000000 3 1.000000 0.000000 4 1.000000 0.000000
environment: lingo 8.0

SummerRain · 发表于 2005-8-27 01:19:39

<

>"感激不尽！
<

>不知高手能否给出MATLAB的算法！
<

>LINGO 俺不是很，，，"
这是用经典的simplex algorithm 解决的,我建议你查一下任何一本数模书的单纯型讲解，或是：《算法设计与分析(王晓东第二版 )》，上面讲的都非常清楚。
除了之外，你也可以用剪枝分支限界法解决。
先用贪心给出一个次优解，设为当前最优解。
接下来在递归构造状态树的过程中，不断减去不可能产生比当前最优解更好的解得那个节点。
至于衡量当前节点是否会产生更好的解，可以再次从当前节点运用贪心算法给出当前节点的解得上限值。
对于规模不大的问题，是可以应付的。

ATK1992 · 发表于 2005-8-27 03:10:39

<

>恕偶愚.
<

>能否给出一个例子,就以楼主的引

		自动登录	找回密码
密码			注-册-帐-号