Sunday, 22. October 2006, 08:23:18
linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.
In other words, given a polytope (for example, a polygon or a polyhedron), and a real-valued affine function
f(x_1, x_2, \dots, x_n)=a_1x_1+a_2x_2+\cdots +a_nx_n+b\,
defined on this polytope, the goal is to find a point in the polytope where this function has the smallest (or largest) value. Such points may not exist, but if they do, searching through the polytope vertices is guaranteed to find at least one of them.
UsesLinear programming is an important field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming is heavily used in microeconomics and business management, either to maximize the income or minimize the costs of a production scheme.
Standard formStandard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:
* A linear function to be maximized
e.g. maximize c_1 x_1 + c_2 x_2\,
* Problem constraints of the following form
e.g. a_{11} x_1 + a_{12} x_2 \le b_1
a_{21} x_1 + a_{22} x_2 \le b_2
a_{31} x_1 + a_{32} x_2 \le b_3
* Non-negative variables
e.g. x_1 \ge 0
x_2 \ge 0
The problem is usually expressed in matrix form, and then becomes:
maximize \mathbf{c}^T \mathbf{x}
subject to \mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0
Other forms, such as minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an equivalent problem in standard form.
-------------------------------------------------------------------
-v- 发现线性规划在编译原理上的判断和图形学中的凸包也有基于这个原理的使用...果然数学是很多地方共通的....
GNU Linear Programming Kit 对于解决具有多种约束的数学问题来说是一个功能非常强大的工具。本文简要介绍了如何使用 GLPK（glpsol 客户机工具）和 GNU MathProg 语言来解决 Giapetto 的 Woodcarving 公司（一家玩具制造商）的作业优化问题。
简介
“线性编程是一个用来解决优化问题的工具。在 1947 年，George Dantzig 开发了一种效率方法 —— simplex 算法 —— 来解决线性编程的问题。由于 simplex 算法的出现，线性编程已经在工业界、银行界、教育界、林业、石油行业以及运输业界中广泛地用来解决优化问题。在对财富 500 强公司的调查中，85% 的被调查者都说他们已经使用了线性编程。”
-----------------------------
WIKI上的定义：http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit以上是此文在IBM developerWorks上的LINK...http://www-128.ibm.com/developerworks/cn/linux/l-glpk1/index.html#eq6
WIDGETIZE