Teacher wangshuyao's notes on operations research course 10 linear programming and simplex method (discussion on detection number and degradation)

The first 10 speak Linear programming and simplex method （ Discussion on detection number and degradation ）

Understanding of some columns in a simplex table

The main thing is , In the simplex table shown above ,$b$ Column and fill $a_{i,j}$ In essence, the column of should be filled with $B^{-1}b$ and $B^{-1}A$, Just in the previous case $B$ It's a unit matrix .

Discussion on detection number

The calculation method of inspection number is ${\sigma }_i=c_i-c_B{B}^{-1}{p}_i=c_i-z_i$. For other textbooks, it may be ${\sigma }_i$ Defined as ${\sigma }_i$$=z_i-c_i$, But it is essentially the same , It's just judgment ${\sigma }_i$ The symbol is exactly the opposite of the size . At the same time, if the optimization problem required to be solved is to solve the objective function $min$, Only need to judge ${\sigma }_i$ when , Use the rule of opposite sign and size . In brief, the positive and negative requirements for the test number when obtaining the optimal solution are shown in the following table ：

	$maxZ$	$minZ$
$c_i-z_i$	$\le 0$	$\ge 0$
$z_i-c_i$	$\ge 0$	$\le 0$

If in a certain round of iteration , There are two or more identical maximum inspection numbers , Then it brings the same benefits to the objective function , You can select any vector corresponding to it as the input vector .

Yes $\theta$ The discussion of the

If in a certain round of iteration , There are two or more identical smallest $\theta$, appear “ degeneration ” situation , In most cases, any corresponding vector can be selected as the base vector , But sometimes there will be circular operations .

When in standard type $b_i=0$ when , May appear “ degeneration ” situation .

resolvent ： In the same smallest $\theta$ in , Select the decision variable with the smallest subscript as the base variable , There will be no cyclic operation .

summary

In the simplex table ,$b$ Column and fill $a_{i,j}$ In essence, the column of should be filled with $B^{-1}b$ and $B^{-1}A$.

For the definition and calculation of different inspection numbers $min$ or $max$ Different , The judgment rules of the test number are also different .

If in a certain round of iteration , There are two or more identical maximum inspection numbers , Then it brings the same benefits to the objective function , You can select any vector corresponding to it as the input vector .

If in a certain round of iteration , There are two or more identical smallest $\theta$, Then select the decision variable with the smallest subscript as the base variable , There will be no cyclic operation .