C#3 Método Simplex

 Definiciones.  Soluciones básicas

 Interpretación geométrica  Forma tabular
 Forma aumentada del modelo

Texto: 4.1 – 4.4

Introducción
En la conferencia anterior estudiamos el método gráfico para resolver PPL con dos variables.
Ejemplo 1 Maximizar Z = 3x1 + 5x2
s.a. x1 < 4
2x2 < 12
3x1 + 2x2 < 18
x1 > 0; x2 > 0
Región factible:

D
B

A C
Al aplicar el método gráfico, obtenemos que la solución óptima es el vértice D (2, 6), en el que la f.o.
alcanza su mayor valor: 36.
El Método Simplex para resolver problemas de PL fue desarrollado por George Dantzig en 1947. Es un
procedimiento algebraico, pero que puede entenderse más fácilmente si analizamos gráficamente su
desenvolvimiento cuando se aplica a un problema con dos variables de decisión.
Desarrollo
Veamos algunas definiciones y propiedades que fundamentan el Método Simplex:
- Una frontera de restricción es una recta que marca el límite de lo que permite la restricción
correspondiente.
- Los puntos de intersección de las restricciones se llaman soluciones en los vértices. De estos:
o los que satisfagan todas las restricciones se llaman soluciones factibles en los vértices (FEV).
En el ejemplo, los cinco puntos que se encuentran en los vértices de la región factible: A(0,0),
B(0,6), C(4,0), D(2,6) y E(4,3) son las soluciones FEV.
o Los otros tres vértices: (0,9), (4,6) y (6,0) – se llaman soluciones no factibles en un vértice.
Observe que cada solución en un vértice se encuentra en la intersección de dos fronteras de
restricciones. Si el problema tuviera n variables, entonces cada solución en un vértice se encontraría en
la intersección de n fronteras de restricciones. Algunos pares de soluciones FEV del ejemplo comparten
una frontera de restricción, y otros no.
- Para cualquier PPL con n variables de decisión, dos soluciones FEV son adyacentes entre sí si
comparten n-1 fronteras de restricciones.
Como n = 2 en el ejemplo, dos de sus soluciones FEV son adyacentes si comparten una frontera de
restricción; por ejemplo A(0,0) y B(0,6) son adyacentes porque comparten la frontera x1 = 0.
 2
- Dos soluciones FEV adyacentes están conectadas por un segmento de recta que está en estas
mismas fronteras de restricciones compartidas. Este segmento recibe el nombre de arista de la
región factible.
Observe que de cada solución FEV salen dos aristas y que cada solución FEV tiene dos soluciones
adyacentes, las que se encuentran en el otro punto terminal de cada arista.
Solución FEV Soluciones FEV adyacentes
(0, 0) (0, 6) (4, 0)
(0, 6) (0, 0) (2, 6)
(2, 6) (0, 6) (4, 3)
(4, 3) (2, 6) (4, 0)
(4, 0) (4, 3) (0, 0)

Teniendo en cuenta esta idea geométrica podemos enunciar la siguiente propiedad.

Prueba de optimalidad: Considere un PPL que tenga, al menos, una solución óptima. Si
una solución FEV no tiene soluciones FEV adyacentes que sean mejores (según el valor de
Z), entonces esa es una solución óptima.
Así, por ejemplo, (2, 6) es óptimo porque su valor correspondiente de Z = 36; mientras que sus dos
soluciones FEV adyacentes (0, 6) y (4, 3) tienen valores de Z inferiores: 30 y 27, respectivamente. Esta
es, precisamente, la prueba de optimalidad que utiliza el método Simplex.
 Interpretación geométrica
Inicialización: Elegir (0, 0) como la solución FEV inicial, para examinarla.
En el ejemplo, Z(0, 0) = 0.
Prueba de optimalidad: Evaluar Z en las dos soluciones FEV adyacentes a (0,0):
Z(4, 0) = 12 > 0; Z(0, 6) = 30 > 0. Se concluye que (0, 0) no es óptimo.
Iteración 1: Moverse a la solución FEV adyacente a (0, 0) que más aumenta el valor
de la función objetivo.
Ahora, estamos sobre la solución FEV (0, 6).
Prueba de optimalidad: Evaluar Z en las dos soluciones FEV adyacentes a (0, 6) (solo se evalúa
en una porque venimos desde la otra).
Z(2, 6) = 36 > 30. Se concluye que (0, 6) no es punto de óptimo.
Iteración 2: Moverse a la solución FEV adyacente a (0, 6) que más aumenta el valor
de la función objetivo.
Ahora estamos sobre la solución FEV (2, 6).
Prueba de optimalidad: Evaluar Z en las dos soluciones FEV adyacentes a (2, 6) (solo se evalúa
en una porque venimos desde la otra).
Z(4, 3) = 27 < 36. Se concluye que (2, 6) sí es punto de óptimo.
 Forma aumentada del modelo
Para algoritmizar el procedimiento geométrico descrito es necesario transformarlo en un procedimiento
algebraico. Primeramente, es necesario convertir el sistema de inecuaciones lineales a un sistema de
ecuaciones; para ello se introducen las llamadas variables de holgura.
Tomemos la primera restricción del ejemplo: x1 < 4
La variable de holgura para esta restricción es x3 = 4 – x1, que es la holgura que queda del
lado izquierdo de la desigualdad. Entonces, x1 + x3 = 4
Observe que, x1 < 4 se cumple si y solo si 4 – x1 = x3 > 0.
Por tanto, x1 < 4  { x1 + x3 = 4  x3 > 0 }
Al introducir variables de holgura en las otras restricciones funcionales, el modelo de PL original se
puede sustituir por otro equivalente llamado forma aumentada del modelo:

MO C3 Método Simplex Dr. Vicente Molina, PT

 3
Forma original del modelo Forma aumentada del modelo
Maximizar Z = 3x1 + 5x2 Maximizar Z = 3x1+5x2+0x3+0x4+0x5
s.a. s.a.
x1 < 4 x1 + x3 =4
2x2 < 12 2x2 + x4 = 12
3x1 + 2x2 < 18 3x1 + 2x2 + x5 = 18
x1 > 0; x2 > 0 xj > 0 para j = 1,…,5
 Si una variable de holgura es:
 igual a 0 en la solución actual, entonces esta solución se encuentra sobre la frontera de la
restricción funcional correspondiente;
 mayor que 0 significa que la solución está en el lado factible de la frontera de la restricción;
 menor que 0 significa que está en el lado no factible de la frontera.
 Una solución aumentada es una solución para las variables originales que se han aumentado con
los valores correspondientes de las variables de holgura.
 Una solución básica es una solución en un vértice aumentada.
En el ejemplo:
- la solución FEV (0, 0) se corresponde con la SB (0, 0, 4, 12, 18)
- la solución FEV (0, 6) se corresponde con la SB (0, 6, 4, 0, 6)
- la solución FEV (2, 6) se corresponde con la SB (2, 6, 2, 0, 0)
 Características de las soluciones básicas:
 Cada variable se designa, ya sea como variable básica o como variable no básica.
 El número de variables básicas es igual al número de restricciones funcionales.
 Las variables no básicas se hacen iguales a 0.
 Los valores de las variables básicas se obtienen con la solución del sistema de ecuaciones
(restricciones funcionales en la forma aumentada).
 Si las variables básicas satisfacen las restricciones de no negatividad, la solución básica es una
solución básica factible (SBF).
En el ejemplo:
Consideremos como variables no básicas x1 y x4; entonces, de:
x1 + x3 =4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18

con x1 = 0 y x4 = 0, se obtiene que: x3 = 4 ; x2 = 6 ; x5 = 6

Como las variables son no negativas, entonces la solución básica (0, 6, 4, 0, 6) es una SBF.
 Dos soluciones BF adyacentes tienen las mismas variables no básicas, excepto una.
Observe que:
- las soluciones (0, 0, 4, 12, 18) y (0, 6, 4, 0, 6) son adyacentes. La primera tiene como
variables no básicas x1 y x2, mientras que la segunda tiene a x1 y x4.
- las soluciones (0, 6, 4, 0, 6) y (2, 6, 2, 0, 0) son adyacentes. La primera tiene como
variables no básicas x1 y x4, mientras que la segunda tiene a x3 y x4.
En consecuencia, trasladarnos de una SBF a otra adyacente significa cambiar una variable de
no básica a básica, y viceversa para otra variable; ajustando, por supuesto, los valores de las
variables básicas para que se siga satisfaciendo el sistema de ecuaciones.

MO C3 Método Simplex Dr. Vicente Molina, PT

 4
Transformemos el modelo en su forma aumentada, reescribiendo la f.o. de la siguiente forma:
Maximizar Z
s.a.
Z - 3x1 - 5x2 =0
x1 + x3 =4
2x2 + x4 = 12
3x1 + 2x2 + x5 = 18
xj > 0 para j = 1, 2, 3, 4, 5
 Forma tabular del método Simplex.
La forma tabular del Método Simplex registra sólo la información esencial:
1. Los coeficientes de las variables.
2. Las constantes del lado derecho de las ecuaciones.
3. Las variables básicas que aparecen en cada ecuación.
Inicialización: A partir del sistema anterior, obtenemos la tabla Simplex siguiente:
Var. Coeficientes de:
Bás. x1 x2 x3 x4 x5 bj
Z -3 -5 0 0 0 0 fila 0
x3 1 0 1 0 0 4 fila 1
x4 0 2 0 1 0 12 fila 2
x5 3 2 0 0 1 18 fila 3
Aquí se han tomado como variables no básicas las variables de decisión x1 y x2 (su valor es 0) y como
básicas las de holgura. Los valores obtenidos para estas variables (última columna) son los de los
términos independientes de cada ecuación: x3 = 4, x4 = 12 y x5=18. Es decir, la solución BF inicial es
A(0, 0, 4, 12, 18) y el valor de la f.o. es Z = 0.
Prueba de optimalidad. La solución BF es óptima si, y solo si, todos los coeficientes en la fila 0 (la fila
de Z) son no negativos. No es el caso, pues los coeficientes de x1 y x2 son negativos. ¡No es óptima!
Iteración 1.
Paso 1: Determinar la variable no básica que entra a la base; para ello se selecciona la variable con
coeficiente en Z más negativo. En este caso, la x2. A esa columna la llamaremos columna pivote.

Var. Coeficientes de:

Bás. x1 x2 x3 x4 x5 bj
Z -3 -5 0 0 0 0
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12
x5 3 2 0 0 1 18
Columna pivote (Variable que entra)
Paso 2: Determinar la variable básica que sale de la base, aplicando la prueba del cociente mínimo.
a) Se eligen los coeficientes de la columna pivote que son estrictamente positivos.
b) Se divide cada elemento de la columna de la derecha (bj) entre el correspondiente
coeficiente positivo del mismo renglón.
c) Se identifica el renglón que tiene la menor de estas razones.
A esta fila se le llama fila pivote. La variable básica correspondiente es la que sale de la base.
El elemento en la intersección de la columna pivote con la fila pivote recibe el nombre de pivote.

MO C3 Método Simplex Dr. Vicente Molina, PT

 5
V.B. x1 x2 x3 x4 x5 bj
Z -3 -5 0 0 0 0 Razón
x3 1 0 1 0 0 4
x4 0 2 0 1 0 12 122 = 6 mínimo (Variable que sale)
x5 3 2 0 0 1 18 182 = 9
Paso 3: Se construye una nueva tabla a partir de la anterior, realizando operaciones elementales
(multiplicación o división de una fila por una constante diferente de cero; suma o resta de un múltiplo
de una fila con otra) que lleven al valor 1 en el elemento pivote y al valor 0 en el resto de la columna
pivote.
En el ejemplo:
- se divide por el pivote (2) la fila 2, correspondiente a la x4 (variable que sale),
- se multiplica la nueva fila de x4 por -2 y se suma a la tercera (correspondiente a la variable x5)
para obtener el valor 0 en la intersección de la columna de x2 con la fila de x5,
- como la fila correspondiente a la variable x3 ya tiene un 0 en la columna de x2, se deja como está,
- se multiplica la nueva fila de x4 por 5 y se suma a la primera (correspondiente al valor de Z) para
obtener el valor 0 en la intersección de la columna de x2 con la fila de Z.
Se obtiene la tabla siguiente:
VB x1 x2 x3 x4 x5 bj
Z -3 0 0 5/2 0 30
x3 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
x5 3 0 0 -1 1 6
Observe, en el gráfico del modelo, que hemos pasado de la SBF inicial A(0; 0) a la SBF
adyacente B(0; 6); que le da un mejor valor a la f.o. (30) que la otra SBF adyacente (C(4; 0), con
Z = 12).
Prueba de optimalidad. La solución BF es óptima si y solo si todos los coeficientes en el renglón 0 (la
fila de Z) son no negativos. No es el caso, pues el coeficiente de x1 es negativo.
Iteración 2.
Paso 1: Determinar qué variable no básica entra a la base; para ello se selecciona la variable con
coeficiente más negativo. En este caso, la x1. Marcamos la columna pivote.
Paso 2: Determinar la variable que sale: a partir de la menor razón del cociente de los elementos del
lado derecho entre los coeficientes de la columna pivote, que sean estrictamente positivos.
V.B. x1 x2 x3 x4 x5 bj
Z -3 0 0 5/2 0 30 Razón
x3 1 0 1 0 0 4 41 = 4
x2 0 1 0 1/2 0 6
x5 3 0 0 -1 1 6 63 = 2, mínimo
Paso 3: Pivotear para construir la nueva tabla
V.B. x1 x2 x3 x4 x5 bj
Z 0 0 0 3/2 1 36
x3 0 0 1 1/3 -1/3 2
x2 0 1 0 1/2 0 6
x1 1 0 0 -1/3 1/3 2
Observe en el gráfico del modelo que hemos pasado de la SBF B(0; 6) con Z = 30 a la SBF
adyacente D(2; 6) con Z = 36.

MO C3 Método Simplex Dr. Vicente Molina, PT

 6
Prueba de optimalidad: No hay coeficientes negativos en la fila cero. Por tanto, la solución es óptima.
x1 = 2; x2 = 6; x3 = 2 ; x4 = 0; x5 = 0; Z = 36
Observe en el gráfico del modelo que la única SBF adyacente a D(2; 6) es C(4; 3) cuyo valor de
Z es 27 < 36.
Observe que en la solución óptima:
- la variable de holgura x3 no es cero; eso significa que en la restricción correspondiente (x1 < 4)
queda una holgura de 2 unidades;
- los valores cero de las otras variables de holgura (x4 y x5) nos indican que en las restricciones
correspondientes (2x2 < 12 y 3x1 + 2x2 < 18) se satisface la igualdad estricta.
Conclusiones
El Simplex es un método algebraico que consiste, básicamente, en evaluar –a partir de una solución
básica inicial– el mejoramiento que producen en el valor de Z las soluciones básicas adyacentes. Si no
se mejora el valor de Z, se ha arribado a la solución óptima; de lo contrario, se pasa a la solución básica
adyacente mejor y se repite el proceso.
Consideramos el método aplicado a un problema de maximización, sujeto a restricciones de <; pero se
le pueden realizar modificaciones a otras formas diferentes de modelos de PL para obtener un modelo
equivalente, ajustado a las condiciones de trabajo del Método Simplex. Este será el objeto de la
próxima conferencia.
Orientación para las CP
1. Dada la siguiente gráfica:
a) Escriba el modelo de PL que representa en forma
estándar.
b) Escriba el modelo aumentado.
c) Plantee la tabla simplex inicial.
d) Halle la solución óptima.

2. Halle la solución de:

a. Max Z = 4x1 + 3x2 + e. Max Z = 3x1 + 2x2
6x3 c. Max Z = 5x1 + 3x2 + s.a.
s.a. 4x3 x1 < 4;
3x1 + x2 + 3x3 < 30 s.a. x2 < 6 ;
2x1 + 2x2 + 3x3 < 40 2x1 + x2 + x3 < 20 3x1 + 2x2 < 18
x1 > 0; x2 > 0; x3 > 0 3x1 + x2 + 2x3 < 30 x1 > 0; x2 > 0
x1 > 0; x2 > 0, x3 > 0
b. Max Z = x1 + 2x2 + 2x3
s.a. d. Max Z = 4x1 + 5x2
5x1 + 2x2 + 3x3 < 15 s.a.
x1 + 4x2 + 2x3 < 12 –x1 + x2 < 3
2x1 + x3 < 8 2x1 –3x2 < 6
x1 > 0; x2 > 0; x3 > 0 x1 > 0; x2 > 0

MO C3 Método Simplex Dr. Vicente Molina, PT