An Overview of Linear Programming

Among optimization problems there is a class known as linear programming problems, which belong to constrained optimization. Linear programming is the problem of finding the extremum of a linear objective function under linear constraints (equalities or inequalities).

The Standard Model of a Linear Programming Problem

The standard model of linear programming is

Consider any linear form; for example, suppose a linear programming problem has the following form. Unlike the standard form, this one uses inequality constraints:

By introducing a surplus variable $y$, the problem above can be transformed into the standard form

If the constraints have the following form:

then, by introducing a slack variable $y$, the constraints can be converted into

Basic Solutions of a Linear Programming Problem

As mentioned above, any linear programming problem can be converted into the standard form, in which the constraints are linear equalities and the decision variables are nonnegative.

Consider the equation $Ax=b$, where $rank(A)=m$. To solve this kind of problem, we usually start from a subset of the column vectors of the matrix $A$. For convenience, we can reorder the column vectors of $A$ so that the columns of interest come first. Specifically, select $m$ linearly independent vectors from $A$ to form a square matrix $B$, and reorder the columns of $A$ so that the columns of $B$ occupy the first $m$ columns of $A$. That is, $A$ can be written as the block matrix $A=[B,D]$, where $D$ is an $m*(n-m)$ matrix consisting of the remaining column vectors of $A$. The matrix $B$ is nonsingular, so solving the equation $Bx_{B}=b$ yields the unique solution $x_{B}=B^{-1}b$. Let $x$ be an $n$-dimensional vector whose first $m$ elements equal $x_B$ and whose remaining elements are zero, i.e. $x=[s_{B}^{T},0^{T}]^{T}$; then $x$ is a solution of the equation $Ax=b$.

$[x_{B}^{T},0^{T}]^{T}$ is the basic solution of $Ax=b$ with respect to $B$. The elements of the vector $x_{B}$ are called basic variables, and the column vectors of $B$ are called basic column vectors.

Degenerate basic solution ---> a basic solution in which some basic variables are 0 Feasible solution ---> a vector $x$ satisfying $Ax=b,x\ge 0$ Basic feasible solution ---> a feasible solution that is also a basic solution Degenerate basic feasible solution ---> a basic feasible solution that is a degenerate basic solution

When solving a linear programming problem, we need only consider basic feasible solutions, because if an optimal solution of the objective function exists, it is necessarily attained at some basic feasible solution.

Fundamental theorem of linear programming 1. If a feasible solution exists, then a basic feasible solution exists. 2. If an optimal feasible solution exists, then an optimal basic feasible solution exists.

The fundamental theorem of linear programming reduces solving a linear programming problem to searching over a finite number of basic feasible solutions, which greatly reduces the amount of work required.

From a geometric point of view, the set of points satisfying the constraints $Ax=b,x\ge 0$ in the standard linear program is a convex set; that is, for any $x,y\in \Theta$ and any real number $\alpha$ with $0<\alpha <1$, we have $\alpha x+(1-\alpha)y\in \Theta$. For a point $x$ in a convex set, if there are no two distinct points $x_{1}$ and $x_{2}$ in $\Theta$ such that $x=\alpha x_{1}+(1-\alpha)x_{2}$ holds, then $x$ is called an extreme point. It can be proved that the extreme points of the constraint set are equivalent to the basic feasible solutions.

The idea of the simplex method for solving linear programming problems is precisely the algorithm of moving from one extreme point to an adjacent extreme point. A later article will give a detailed introduction to the simplex method, duality, and related concepts.

To be continued…