Linear Programming

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 the following equation.

The value of f(x) in the previous equation 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 x is the real vector of unknowns, c is the real cost vector, and A is the real constraint matrix of size m x n. At least one member of solution set X is at a vertex of the polyhedron that describes X.