Teacher wangshuyao's operations research course notes 07 linear programming and simplex method (standard form, base, base solution, base feasible solution, feasible base)

The first 7 speak Linear programming and simplex method （ Standard 、 The base 、 Basic solution 、 Basic feasible solution 、 Feasible basis ）

The standard form of linear programming problem

Change the constraints from weak constraints to strong constraints , Change a system of inequalities into a system of equations , It reduces the difficulty of solving .

For general linear programming problems , Easy to get ：

Objective function $\max (\min )z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$

constraint condition $\left\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n⩽(=,⩾)b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n⩽(=,⩾)b_2\\ ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n⩽(=,⩾)b_m\\ x_1,x_2,\cdots ,x_n⩾0\end{array}\right\}$

The general form is transformed into the standard form through identical deformation , To facilitate the subsequent solution .

1. The objective function needs to be transformed into $max$. If the original objective function is $min$, Then order $z^{{}^{\prime }}=-z$, Then seek $max{z}^{{}^{\prime }}$.
2. $b_i$ Need to be transformed into $>0$. If $b_i<0$ Then both sides of the inequality are added with a minus sign . If $b_i=0$ It means there is degradation , I don't usually meet .
3. Constraints need to be reduced to $=$. If the original constraint is $\le$, Then the constraint becomes the original constraint minus a new non negative variable （ Relax variables ）. If the original constraint is $\ge$, Then the constraint becomes the original constraint plus a new non negative variable （ Remaining variables ）.（ The purpose of this step is to change weak constraints into strong constraints , Easy to solve the equation , The cost is the introduction of additional variables , The dimension of the equation is increased .）
4. Variables need to be converted to $\ge 0$. If the original variable is $=0$, Then directly change to $\ge 0$, But in fact, this situation will not happen , Because if the variable $=0$, Then the changed variable will not appear in the objective function and constraints . If the original variable is $\le 0$, Then order $x_i^{{}^{\prime }}=-x_i$, And order $x_i^{{}^{\prime }}\ge 0$, At the same time, the objective function and constraints are replaced . If the original variable has no constraints （$\in$R）, Then order $x_i=x_i^{{}^{\prime }}-x_i^{{}^{\prime \prime }}$, And order $x_i^{{}^{\prime }}\ge 0x_i^{{}^{\prime \prime }}\ge 0$, At the same time, the objective function and constraints are replaced .
5. Write the objective function normally . Adjust the objective function formally , Write the newly introduced variable back into the objective function . Although its value coefficient is 0, But also write it out .

Discussion on the solution of linear programming

First, the standard form of linear programming problem is written into matrix form .

$\mathbf{A}=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ ⋮& ⋮& & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right)=\left({\mathbf{P}}_1,{\mathbf{P}}_2,\cdots ,{\mathbf{P}}_n\right);\mathbf{O}=\left[\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right]$

$\mathbf{X}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right];\mathbf{b}=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right]$$;\mathbf{C}=\left(c_1,c_2,\cdots ,c_n\right)$

The linear programming problem can be described as ：

$\max z=\mathbf{C}\mathbf{X}$
$\mathbf{A}\mathbf{X}=\mathbf{b}$
$\mathbf{X}⩾0$

Feasible solution

Satisfy the constraint formula $\mathbf{A}\mathbf{X}=\mathbf{b}$、$\mathbf{X}⩾0$ The solution of is called the feasible solution of linear programming , The feasible solution that maximizes the objective function is called the optimal solution .

The base

set up $A$ It's a set of constrained equations $m\times n(m<n)$ Dimensional coefficient matrix , Its rank is $m$.$B$ It's a matrix $A$ in $m\times m$ Order submatrix , among $B$ The column vectors of are linearly independent , And $|B|=0$, It's called matrix $B$ It is a basis of linear programming problem .

$B$ Medium $P_i$ It's called a base vector , be not in $B$ Medium $P_i$ It is called non base vector . Before hypothesis $m$ The coefficient sequence vector of variables is linearly independent , Use these vectors to form a matrix $B$, Then the constraints $\mathbf{A}\mathbf{X}=\mathbf{b}$ It can be written. ：

$\begin{array}{rl}& \left(\begin{array}{c}{a}_{11}\\ a_{21}\\ ⋮\\ a_{m1}\end{array}\right)x_1+\left(\begin{array}{c}{a}_{12}\\ a_{22}\\ ⋮\\ a_{m2}\end{array}\right)x_2+\cdots +\left(\begin{array}{c}{a}_{1m}\\ a_{2m}\\ ⋮\\ a_{mm}\end{array}\right)x_m=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right)-\left(\begin{array}{c}{a}_{1,m+1}\\ a_{2,m+1}\\ ⋮\\ a_{m,m+1}\end{array}\right)x_{m+1}-\cdots -\left(\begin{array}{c}{a}_{1n}\\ a_{2n}\\ ⋮\\ a_{mn}\end{array}\right)x_n\end{array}$

Now let the non base variable of the above formula $x_{m+1}=x_{m+2}=\cdots =x_n=0$, At this time, the number of variables is equal to the number of linear equations Count . Gauss elimination , You can find a solution $\mathbf{X}={\left(x_1,x_2,\cdots ,x_m,0,\cdots ,0\right)}^{\mathrm{T}}$, This solution is called the basic solution （ Note that the fundamental solution is $n$ Dimensional , instead of $m$ Dimensional .）. It can be seen that a basic solution can be obtained with a basis .

Basic feasible solution

Satisfy nonnegative constraints $\mathbf{X}⩾0$ The basic solution of is called the basic feasible solution .

Feasible basis

The basis corresponding to the feasible solution is called the feasible basis .

The geometric meaning of basic solution and basic feasible solution

The geometric meaning of the fundamental solution is ： Intersection of strongly constrained equations .

The geometric meaning of the basic feasible solution is ： Intersection of strongly constrained equations （ Basic solution ）, And it is a point in the feasible region .（ In other words, the vertex of the line field .）

Here readers can give an example by themselves , And draw it in the picture , Then find the feasible solution in the graph 、 Basic feasible solution 、 Which parts are the basic solution and the infeasible solution .

Basic solution 、 The relationship between feasible solution and basic feasible solution

The inclusion relationship between the above solutions can be represented by the following figure ：

Find the optimal solution from the basic feasible solution

in summary , Find all the bases , Then we get all the basic feasible solutions , The largest of the corresponding function values is the optimal solution . Of course , This method belongs to enumeration , In the later study, the function values corresponding to the basic feasible solution can be compared in a certain order , That is, the simplex method , In this way, the optimal solution can be found with less comparison times .

summary

For the convenience of finding feasible solutions , We need to turn the linear programming problem into a standard type , It is mainly necessary to analyze the objective function 、 Free term 、 Weak constraints 、 Handle arguments .

For constrained equations , It can be handled with the idea of linear algebra , Find the base of the coefficient matrix , Let the non base variable be 0, We can get a set of equations composed of basic variables , The unique solution can be solved , Then the basic solution is obtained . A coefficient matrix may have several bases , Every basis can get a basic solution , If the basic solution satisfies $\mathbf{X}⩾0$, Then the basic solution is still the basic feasible solution , The basis corresponding to the feasible solution is called the feasible basis . The largest function value corresponding to the basic feasible solution is the optimal solution .

The geometric meaning of the basic feasible solution is the vertex of the feasible region .

The intersection of feasible solution and basic solution is the basic feasible solution .

In the later study, the function values corresponding to the basic feasible solution can be compared in a certain order , In this way, the optimal solution can be found with less comparison times .