Linear Programming

Linear programming (LP for short) is an important branch of operations research that has been studied earlier, developed rapidly, widely used, and has more mature methods. It is an important field in optimization problems and also assists people in scientific management. A mathematical method. Many practical problems faced in job research can be dealt with by linear programming, especially in some special cases, such as network flow, multi-commodity flow and other problems.

The mathematical model established by the linear programming problem has the following characteristics:

1. Each model has several decision variables (, ,..., ), where n is the number of decision variables. A set of values of decision variables represents a solution, and decision variables are generally non-negative.

2. The objective function is a linear function of the decision variable, which can be maximized (max) or minimized (min) according to the specific problem. The two are collectively referred to as optimization (opt).

3. Constraints are also linear functions (equations or inequalities) of decision variables.

A linear optimization problem is a problem of the following form:

Minimize or maximize the objective function

$MAX(min)z=\sum_{j=1}^{n}c_{j}x_{j}$

subject to the linear constraints

$\begin{array}{c} &s.t.\quad\begin{cases}\sum\limits_{j=1}^n a_{ij}x_j \leq (or \geq, =) b_i & (i=1,2,3,\cdots, m)\\x_j \geq 0 & (j=1,2,3,\cdots,n)\end{cases} \end{array}$

• m and n — the number of constraints and variables, respectively,

• — decision variables,

• , and — fixed constants

Therefore, when the objective function of the mathematical model is linear function and the constraint condition is linear equality or inequality, the mathematical model is called linear programming model.