You are here: NI Home > Support > Product Reference > Manuals > LabVIEW 8.5 Help

Linear programming problems have the following characteristics:

• Linear objective function
• Solution set X with a polyhedron shape defined by linear inequality constraints
• Continuous f(x)
• Partially combinatorial structure

Solving linear programming problems involves finding the optimal value of f(x) where f(x) is a linear combination of variables, as shown in Equation A.

The value of f(x) in Equation A can have the following constraints:

• Primary constraints of x_i ≥ 0, …, x_n ≥ 0
• Additional constraints of M = m₁ + m₂ + m₃
• m₁ of the following form
  a_i1x₁ + … + a_inx_n ≤ b_i, (b_i ≥ 0), i = 1, …, m₁
• m₂ of the following form
  a_j1x₁ + … + a_jnx_n ≥ b_j, (b_j ≥ 0), j = m₁ + 1, …, m₁ + m₂
• m₃ of the following form
  a_k1x₁ + … + a_knx_n = b_k, (b_k ≥ 0), k = m₁ + m₂ + 1, …, M

Any vector x that satisfies all the constraints on the value of f(x) constitutes a feasible answer to the linear programming problem. The vector yielding the best result for f(x) is the optimal solution.

The following relationship represents the standard form of the linear programming problem.

where is the vector of unknowns, is the cost vector, and is the constraint matrix. At least one member of solution set X is at a vertex of the polyhedron that describes X.

Linear Programming Simplex Method

A simplex describes the solution set X for a linear programming problem. The constraints on the value of f(x) define the polygonal surface hyperplanes of the simplex. The hyperplanes intersect at vertices along the surface of the simplex. The linear nature of f(x) means the optimal solution is at one of the vertices of the simplex. The linear programming simplex method iteratively moves from one vertex to the adjoining vertex until moving to an adjoining vertex no longer yields a more optimal solution.

Note  Although both the linear programming simplex method and the nonlinear downhill simplex method use the concept of a simplex, the methods have nothing else in common.