手动编写线性编程练习

Question

我在课堂上一直在做线性编程问题,但是我想知道如何编写一个特定问题的程序来解决它.如果有太多的变量或约束,我永远无法通过绘图来做到这一点.

示例问题,使用约束最大化5x + 3y:

• 5x - 2y> = 0
• x + y <= 7
• x <= 5
• x> = 0
• y> = 0

我画了这个,得到了一个有3个角的可见区域.x = 5 y = 2是最佳点.

如何将其转换为代码？我知道单纯形法.而且非常重要的是,所有LP问题都会被编码在同一个结构中吗？蛮力工作吗？

Answer 1

如果你搜索,你会发现很多Simplex实现.

除了评论中提到的那个(C中的数字食谱),您还可以找到:

1. 谷歌自己的Simplex-Solver
2. 然后是COIN-OR
3. GNU有自己的GLPK
4. 如果您想要一个C++实现,Google Code中的这个实现实际上是可访问的.
5. R中有许多实现,包括引导包.(在R中,您可以通过在没有括号的情况下键入函数来查看函数的实现.)

解决你的另外两个问题:

1. 是否所有LP都以相同的方式编码？是的,可以编写通用LP解算器来加载和解决任何LP.(阅读LP的行业标准格式有mps和.lp

2. 蛮力工作吗？请记住,许多公司和大型组织花费很长时间来对解算器进行微调.有些LP具有许多解算器试图利用的有趣属性.而且,某些计算可以并行解决.该算法是指数的,因此在一些大量的变量/约束下,暴力无效.

希望有所帮助.