MKP 放宽线性规划
如何计算找到这种松弛。我应该知道什么才能找到它。假设我有 n 个物品和 m 个背包。所以我想知道 m 松弛的数量。有谁至少可以给我一些想法吗？我已经找了一段时间了。网上有一些文章，但不太清楚。请至少有人对我说你应该读这个东西，你应该知道这个东西，所以我会非常感激
谢谢你
how to calculate to find this relaxation. What should i know to find it. Suppose i have n items and m knapsack . So i wanted to know the number of m relaxation. Does anybody can give me some idea at least. I have been searching it for while. There is some article on internet but not much clear. Please at least someone say to me you should read this thing , you should know this thing e.i so i will very appreciate
Thank you
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为你真正的问题是“线性松弛背包问题的确切定义是什么？”，所以我将假设它是的来回答。
简而言之，线性松弛 KP 是 0-1 KP [1] 的分数版本。
从数学上讲，您所要做的就是将限制“x_i 属于 {0, 1} 集合”转换为“x_i 必须是 0 到 1 之间的任何实数”，其中 x_i 是 i- 的数量您的解决方案背包中的第一项。
这个名字来源于 0-1 KP 是一个整数规划问题。 “线性”术语意味着解变量可以采用连续值。
但并非所有松弛都是线性的。您可能想查看此维基百科页面他们。
[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation
I think your real question is "what is the exact definition of a Linear-Relaxed Knapsack Problem?", so I'm going to answer assuming it is.
The short answer is that a linear-relaxed KP is the fractionary version of a 0-1 KP [1].
Mathemathically, all you have to do is to convert the restriction "x_i belongs to the {0, 1} set" and convert it to "x_i must be any real number between 0 and 1", where x_i is the quantity of the i-th item in your solution backpack.
The name comes from the fact that the 0-1 KP is an integer programming problem. The 'linear' term means that the solution variables can assume continuous values.
Not all relaxations are linear, though. You might want to check out this Wikipedia page for them.
[1] http://en.wikipedia.org/wiki/Linear_programming_relaxation