El algoritmo simplex--ejemplo

Question

Aquí en la página 30, por qué $(z_3,z_3)=1$ como está escrito en esa página 30:

minimizar la suma de las variables artificiales, partiendo de la BFS en la que el valor absoluto de la variable artificial para cada restricción, o de la variable de holgura en caso de que no haya ninguna variable artificial, es igual al del lado derecho.

Pero la r.h.s. de la misma es $2$ y no $1$ . ¿Qué significa precisamente ese texto resaltado arriba?

Answer 1

Permítanme explicar lo que sucede antes de volver al texto. En la forma estándar,

\begin{align} \max z= \quad& -6 x_1 - 3 x_2 \tag{$\star$}\label{z1} \\ \text{s.t.} \quad& x_1+x_2-z_1 = 1 \tag{1}\label{c1} \\ & 2x_1-x_2-z_2 = 1 \tag{2}\label{c2} \\ & 3x_2+z_3 = 2 \tag{3}\label{c3} \\ & x_1, x_2, z_1, z_2, z_3 \geq 0. \tag{FC}\label{fc} \end{align}

Para encontrar una "BFS obvia" (p.29), incluimos $z_3$ como variable básica, pero no $z_1,z_2$ ya que no puede tienen $z_1 = z_2 = -1$ debido a \eqref {fc}.

Para iniciar el bifásico-simplex necesitamos una BFS, así que añadimos variables artificiales $y_1$ y $y_2$ al LHS de \eqref {c1} y \eqref {c2} respectivamente, por lo que obtenemos una "BFS obvia" $(y_1,y_2,z_3) = (1,1,2)$ .

\begin{align} \min w= \quad& y_1 + y_2 \tag{#}\label{w1} \\ \text{s.t.} \quad& x_1+x_2-z_1+y_1 = 1 \tag{1'}\label{c12} \\ & 2x_1-x_2-z_2+y_2 = 1 \tag{2'}\label{c22} \\ & 3x_2+z_3 = 2 \tag{3}\label{c32} \\ & x_1, x_2, z_1, z_2, z_3, y_1, y_2 \geq 0. \tag{FC'}\label{fc2} \end{align}

Esto nos permite escribir un cuadro simplex, en el que las variables básicas son $y_1$ , $y_2$ y $z_3$ . Esto explica por qué en el cuadro simplex, el $z_3$ -Fila $z_3$ -la columna es $1$ . El lado derecho de la tabla inicial del simplex se hace eco de la "BFS obvia", por lo que el lado derecho de $z_3$ -La fila es $2$ .

Ahora, descifremos el texto citado.

• minimizar la suma de las variables artificiales ( $\min y_1 + y_2$ )
• a partir de la BFS ( $(y_1,y_2,z_3)$ )
  • el valor absoluto de la variable artificial para cada restricción ( $|y_1|,|y_2|$ en \eqref {c12} & \eqref {c22} respectivamente), O
  • de la variable de holgura en caso de que no haya ninguna variable artificial ( \eqref3 tiene no variable artificial, $z_3$ es una variable de holgura)
• es igual a la del lado derecho ( $=(1,1,2)$ )