Overview of Linear Programming

Context (title): Overview of Linear Programming

In optimization problems, there is a category known as linear programming problems, which fall under constrained optimization problems. Linear programming involves finding the extrema of a linear objective function under linear constraints (equations or inequalities).

Standard Model of Linear Programming

The standard model of linear programming is

$$\begin{align*} minimize\quad c^{T}x\\ subject\ to\ Ax=b\\x\ge0 \end{align*}$$

All linear forms, such as a linear programming problem with the following form, differ from the standard form by using inequality constraints:

$$\begin{align*} minimize\quad c^{T}x\\ subject\ to\ Ax\ge b\\x\ge0 \end{align*}$$

This can be converted to the standard form by introducing surplus variables $y$:

$$\begin{align*} minimize\quad c^{T}x\\ subject\ to\ Ax-I_{m}y=\begin{bmatrix} A & -I_{m}\end{bmatrix}\begin{bmatrix} x \\ y\end{bmatrix}=b\\x\ge0,y\ge0 \end{align*}$$

If the constraints are in the following form:

$$\begin{align*} Ax\le b\\ x\ge 0 \end{align*}$$

They can be converted by introducing surplus variables $y$:

$$Ax+I_{m} y =\begin{bmatrix} A & I_{m}\end{bmatrix}\begin{bmatrix} x \\ y\end{bmatrix}=b\\x\ge0,y\ge0$$

Basic Solution of Linear Programming Problems

As mentioned above, any linear programming problem can be converted to the standard form, where the constraints are linear equations and the decision variables are non-negative.

Consider the equation $Ax=b$, where $rank(A)=m$. To solve such problems, we usually start with some column vectors of matrix $A$. For convenience, the column vectors of $A$ can be reordered, placing the vectors of interest at the front. Specifically, select m linearly independent vectors from $A$ to form a square matrix $B$. By reordering the column vectors of $A$, the vectors in $B$ can be placed in the first m columns of $A$, so $A$ can be written as a block matrix $A=[B,D]$, where $D$ is an $m*(n-m)$ matrix composed of the remaining column vectors of $A$. The matrix $B$ is non-singular, so solving the equation $Bx_{B}=b$ yields a unique solution $x_{B}=B^{-1}b$. Let $x$ be an n-dimensional vector, with its first m elements equal to $x_B$ and the remaining elements zero, i.e., $x=[s_{B}^{T},0^{T}]^{T}$, then $x$ is a solution to the equation $Ax=b$.

$[x_{B}^{T},0^{T}]^{T}$ is a basic solution of $Ax=b$ under $B$, where the elements in vector $x_{B}$ are called basic variables, and the column vectors in $B$ are called basic column vectors.

Degenerate Basic Solution ---> Some basic variables in the basic solution are zero Feasible Solution ---> A vector $x$ that satisfies $Ax=0,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 linear programming problems, only basic feasible solutions need to be considered, because if an optimal solution exists, it must be found at a basic feasible solution.

Fundamental Theorem of Linear Programming 1. If a feasible solution exists, then a basic feasible solution must exist. 2. If an optimal feasible solution exists, then an optimal basic feasible solution must exist.

The fundamental theorem of linear programming reduces the problem to searching among a finite number of basic feasible solutions, significantly reducing the workload of solving the problem.

From a geometric perspective, the set of points defined by the constraints $Ax=b,x\ge 0$ in standard linear programming is a convex set. For any $x,y\in \Theta$ and a real number $\alpha$, $0<\alpha <1$, $\alpha x+(1-\alpha)y\in \Theta$. A point $x$ within a convex set is called an extreme point if there are no two distinct points $x_{1}$ and $x_{2}$ in $\Theta$ such that $x=\alpha x_{1}+(1-\alpha)x_{2}$. It can be proven that the extreme points of the constraint set are equivalent to basic feasible solutions.

The algorithm of moving from one extreme point to an adjacent extreme point is the idea behind the simplex method for solving linear programming problems. Future articles will provide a detailed introduction to the simplex method and related concepts such as duality.

To be continued…