我一直在写软件来解决业务问题。当我浏览一个SO帖子的时候,我遇到了关于LIP的问题。我用谷歌搜索了它,但我不知道如何使用它来解决业务问题。如果有人能用外行术语帮助我理解,我将不胜感激。
发布于 2011-09-30 20:33:50
ILP基本上可以用来解决涉及做出一系列决策的任何问题,每个决策只有几个可能的结果,都是提前知道的,并且可以使用一个不依赖于选择之间的“交互”的函数来描述任何选择组合的总体“质量”。要了解它是如何工作的,最简单的方法是进一步限制只能为0或1(整数的最小可用范围)的变量。现在:
示例
例如,假设你有3个工人,Anne,Bill和Carl,还有3个工作,分别是除尘,打字和打包。所有的人都可以做所有的工作,但他们每个人在每个工作中都有不同的效率/能力水平,所以我们想要找到每个人都能做的最好的任务,以最大化整体效率。我们希望每个人执行恰好一项工作。
变量
设置这个问题的一种方法是使用9个变量,每个变量对应一个worker和job的组合。如果Anne应该打包在最优解决方案中,变量x_ad将获得值1,否则将获得0;如果比尔应该打包在最优解决方案中,变量x_bp将获得值1,否则将获得0;依此类推。
目标函数
下一步要做的是制定一个我们想要最大化或最小化的目标函数。假设基于Anne,Bill和Carl最近的绩效评估,我们有一个包含9个数字的表,告诉我们他们每个人完成这3个工作需要多少分钟。在这种情况下,取所有9个变量的总和,每个变量乘以该特定工作者执行该特定工作所需的时间,并寻求最小化该和--即最小化完成所有工作所需的总时间。
约束条件
最后一步是给出约束,强制(a)每个人只做一项工作,(b)每项工作都只有一个人完成。(请注意,实际上这些步骤可以按任何顺序完成。)
为了确保Anne恰好完成一项工作,我们可以添加约束x_ad + x_at + x_ap = 1。可以为比尔和卡尔添加类似的约束。
为了确保恰好只有一个人除尘,我们可以添加x_ad + x_bd + x_cd = 1的约束。可以为键入和打包添加类似的约束。
总共有6个约束。现在,您可以将这个9变量、6约束的问题提供给ILP求解器,它将返回其中一个最优解中变量的值--其中恰好有3个变量为1,其余的为0。这3个是1,告诉你哪些人应该做哪项工作!
ILP是通用的
碰巧的是,这个特殊问题有一个special structure,它允许使用不同的算法更有效地解决它。使用ILP的好处是可以很容易地合并问题的变体:例如,如果实际上有4个人,但只有3个工作,那么我们需要放松限制,使每个人最多做1个工作,而不是恰好只做1个工作。这可以简单地通过将前3个约束中的等号更改为小于或等于号来表示。
发布于 2011-09-30 15:12:27
首先,阅读a linear programming example from Wikipedia
现在想象一下,一个农民生产猪和鸡,或者一个工厂生产烤面包机和吸尘器-现在输出(以及可能的约束)是整数,所以这些漂亮的图形将按曲折的步长前进。这是一个很容易表示为线性规划问题的业务应用程序。
我以前使用过整数线性编程来确定如何平铺n个相同比例的图像以最大化用于显示这些图像的屏幕空间,形式主义可以表示诸如调度之类的覆盖问题,但整数线性编程的业务应用程序似乎更自然地应用于它。
所以用户flolo说:我经常遇到的用例:在数字电路设计中,你需要将对象放置/映射到芯片的某些部分(FPGA-放置)-这可以通过ILP来完成。此外,在HW-SW协同设计中,经常会出现分区问题:程序的哪一部分应该在CPU上运行,哪一部分应该在硬件上加速。这也可以通过ILP解决。
发布于 2011-09-30 15:33:20
示例ILP问题如下所示:
哪里
...but,表单中有一组约束
现在,对维基百科的例子有一个更简单的表述:
克肥料,P2克杀虫剂现在,
让a1表示每1 m²小麦的销售价格让a2表示每1 m²大麦的销售价格
让x1表示要种植小麦的土地让E263表示要种植barley所以,
利润是a1x1+a2x2
a1,a2,L,F1,F2,F,P1,P2,P -都是常量(在我们的例子中:正)
我们正在寻找正整数x1,x2,它将在给定约束的情况下最大化所述表达式。
希望一切都清楚了。
https://stackoverflow.com/questions/7606384
复制相似问题