手动编写线性编程练习 [英] Code a linear programming exercise by hand

问题描述

我一直在课堂上通过绘制线性编程问题来绘制图形，但是我想知道如何针对特定问题编写程序以为我解决问题.如果变量或约束太多，我将永远无法通过绘制图形来做到这一点.

I have been doing linear programming problems in my class by graphing them but I would like to know how to write a program for a particular problem to solve it for me. If there are too many variables or constraints I could never do this by graphing.

示例问题，在有约束的情况下最大化5x + 3y:

Example problem, maximize 5x + 3y with constraints:

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

我对此进行了绘制，并得到了一个带有3个角的可见区域. x = 5 y = 2是最佳点.

I graphed this and got a visible region with 3 corners. x=5 y=2 is the optimal point.

如何将其转换为代码?我知道单纯形法.而且非常重要的是，所有LP问题是否都将以相同的结构编码?蛮力行得通吗?

How do I turn this into code? I know of the simplex method. And very importantly, will all LP problems be coded in the same structure? Would brute force work?

推荐答案

如果您进行搜索，将会发现很多Simplex实现.

There are quite a number of Simplex Implementations that you will find if you search.

除了注释(C中的数字食谱)中提到的内容外， 您还可以找到:

In addition to the one mentioned in the comment (Numerical Recipes in C), you can also find:

1. Google自己的Simplex-Solver
2. 然后是 COIN-OR
3. GNU有自己的 GLPK
4. 如果您要使用C ++实现，则实际上可以访问 Google代码中的该实现.
5. R中有许多实现，包括引导程序包. (在R中，您可以通过键入不带括号的函数来查看其实现.)

1. Google's own Simplex-Solver
2. Then there's COIN-OR
3. GNU has its own GLPK
4. If you want a C++ implementation, this one in Google Code is actually accessible.
5. There are many implementations in R including the boot package. (In R, you can see the implementation of a function by typing it without the parenthesis.)

要解决您的其他两个问题:

To address your other two questions:

1. 是否会以相同的方式对所有LP进行编码?是的，可以编写通用的LP解算器来加载和求解任何LP. (有用于读取LP的行业标准格式，例如mps和.lp

1. Will all LPs be coded the same way? Yes, a generic LP solver can be written to load and solve any LP. (There are industry standard formats for reading LP's like mps and .lp

暴力破解会起作用吗?请记住，许多公司和大型组织都花了很长时间来微调求解器.有些LP具有有趣的属性，许多求解器将尝试利用这些属性.而且，某些计算可以并行解决.该算法是指数算法，因此在大量变量/约束下，蛮力将无法工作.

Would brute force work? Keep in mind that many companies and big organizations spend a long time on fine tuning the solvers. There are LP's that have interesting properties that many solvers will try to exploit. Also, certain computations can be solved in parallel. The algorithm is exponential, so at some large number of variables/constraints, brute force won't work.

希望有帮助.

这篇关于手动编写线性编程练习的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！