Linear program

From Glossary

Jump to: navigation, search

An optimization problem in which the objective and constraints are linear. Forms include LaTeX: \min \{c^Tx: Ax = b,\, x >= 0\} and LaTeX: \max \{c^Tx : Ax \le b\}. The standard form assumes LaTeX: A has full row rank. Computer systems ensure this by having a logical variable LaTeX: (y) augmented, so the form appears, for example, as LaTeX: \min \{c^Tx: Ax + y = b,\, L \le (x, y) \le U\} (also allowing general bounds on the variables). The original variables LaTeX: (x) are called structural. Note that each logical variable can be a slack, surplus, or artificial variable, depending on the form of the original constraint. This computer form also represents a range constraint with simple bounds on the logical variable. Some bounds can be infinite (i.e., absent), and a free variable (logical or structural) is when both of its bounds are infinite.

Personal tools