- Investigación de Operaciones I -

Material de lectura: ALGORITMO SIMPLEX

Dr. Juan Pérez

Facultad Politécnica
Facultad Politécnica UNA
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Contenido
1 RESOLUCIÓN DE UN PROBLEMA DE PL ....................................................................................... 3
1.1.1 Resolución por el Algoritmo Simplex................................................................................ 3
1.1.2 Métodos para resolución de problemas de minimización: Método M y de las Dos Fases 18
1.2 CASOS ESPECIALES DE LA APLICACIÓN DEL MÉTODO SIMPLEX .......................................................... 26
1.3 APLICACIÓN DE PAQUETES DE CÓMPUTO PARA LA SOLUCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL...... 34

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

2
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Unidad II: Programacion Lineal (PL)

1 Resolución de un problema de PL

1.1.1 Resolución por el Algoritmo Simplex

MODELO DE PL EN FORMA DE ECUACIÓN

El desarrollo de los cálculos con el método simplex se facilita si se imponen

dos requerimientos a las restricciones de programación lineal.

1. Todas las restricciones son ecuaciones con lado derecho no negativo.

2. Todas las variables son no negativas.

Conversión de las desigualdades en ecuaciones con lado derecho no

negativo.

En un modelo de PL económico, el lado derecho representa la disponibilidad

de un recurso, y el izquierdo el uso del recurso por todas las actividades del
modelo (variables). La cantidad excedente del lado derecho respecto de
izquierdo da entonces la cantidad no utilizada del recurso.

Para convertir una desigualdad (≤) en ecuación se agrega una variable de

holgura al lado izquierdo de la restricción. Por ejemplo, la restricción
se convierte en ecuación como sigue:

La variable no negativa es la holgura (o cantidad no utilizada) del recurso

correspondiente.

A continuación, una restricción (≥) establece un límite inferior en las

actividades económicas de la Programación Lineal, así que la cantidad en la
cual el lado izquierdo excede el límite mínimo representa un superávit. Así
pues, la conversión de (≥) a (=) se logra restando una variable de superávit
no negativa del lado izquierdo de la desigualdad.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

3
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Por ejemplo, en la restricción , la variable de exceso ,

convierte la restricción (≥) en la ecuación:

Si el lado derecho de una restricción es negativo, se multiplica dicha

restricción por (-1) y se la reduce a alguno de los casos anteriores.

Manejo de variables irrestrictas

Variables con una cota sobre los valores negativos permitidos

Considere cualquier variable de decisión que puede tener valores

negativos, pero nada más aquellos que satisfacen una restricción de la forma:
,

donde es una constante negativa. Esta restricción se puede convertir en

una de no negatividad al realizar el siguiente cambio:j

entonces .

Así, se sustituye por en el modelo y la nueva variable de decisión

no puede ser negativa. (Esta misma técnica se puede utilizar cuando es
positiva para convertir una restricción funcional en una restricción de
no negatividad .)

Para ejemplificar, suponga que se tiene el siguiente modelo de PL:

𝑍 3𝑥 5𝑥
𝑥
𝑥
3𝑥 𝑥
𝑥 𝑥

Para obtener el modelo equivalente que se necesita el método símplex, la

variable de decisión se redefinirá como:

lo que produce los siguientes cambios en la función objetivo y las

restricciones:

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

4
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

𝑍 3𝑥 5𝑥 𝑍 3(𝑥 ) 5𝑥 𝑍 3 3𝑥 5𝑥
𝑥 𝑥 𝑥
𝑥 𝑥 𝑥
3𝑥 𝑥 3(𝑥 ) 𝑥 3𝑥 𝑥
𝑥 𝑥 𝑥 𝑥 𝑥 𝑥

Variables sin cota sobre los valores negativos permitidos

En caso de que no tenga una cota inferior en el modelo formulado, se

requiere un cambio distinto: se sustituye en todo el modelo por la
diferencia de dos nuevas variables no negativas,
donde .

Como y pueden tomar cualquier valor no negativo, la diferencia

puede tener cualquier valor (positivo o negativo), por lo que es una
sustitución legítima de en el modelo. Después de estas sustituciones, el
método símplex puede proceder con variables que son no negativas.

| |

De forma que representa la parte positiva de y su parte negativa

(como lo sugieren los superíndices).

Suponga que se tiene el siguiente modelo de PL:

Maximizar 𝑍 3𝑥 5𝑥
sujeta a 𝑥
𝑥
3𝑥 𝑥
𝑥 (única)

Entonces, antes de aplicar el método símplex, se reemplaza por la

diferencia,
donde .

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

5
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

dando como resultado:

Maximizar 𝑍 3𝑥 5𝑥 Maximizar 𝑍 3𝑥 3𝑥 5𝑥
sujeta a 𝑥 sujeta a 𝑥 𝑥
𝑥 𝑥
3𝑥 𝑥 3𝑥 3𝑥 𝑥
𝑥 (única) 𝑥 𝑥 𝑥

Desde un punto de vista computacional, este enfoque tiene la desventaja

de que el nuevo modelo equivalente tiene más variables que el modelo
original. De hecho, si ninguna variable original tuviera restricción de cota
inferior, el nuevo modelo tendría el doble de variables. Por fortuna, este
enfoque se puede modificar en parte para que el número de variables
aumente sólo en uno, sin importar cuántas variables originales tengan que
sustituirse. Esta modificación se hace reemplazando cada variable de este
tipo por:
donde .

donde es la misma variable de toda relevante.

TRANSICIÓN DE LA SOLUCIÓN GRÁFICA A LA ALGEBRAICA

El desarrollo del Método Simplex algebraico está basado en ideas

transmitidas por la solución gráfica.

En el Método Gráfico el espacio de soluciones es la intersección de los

semiplanos que representan las restricciones, y en el Método Simplex, el
espacio de soluciones está representado por ecuaciones lineales
simultáneas y variables no negativas.

Podemos visualizar que el espacio de soluciones gráficas tiene una

infinidad de puntos de solución, pero ¿cómo sacar una conclusión parecida
a partir de la representación algebraica del espacio de soluciones? La
respuesta es que, en todas las PL, la cantidad de ecuaciones siempre es
menor que la de variables , por lo que se obtiene una cantidad infinita de
soluciones (siempre que las ecuaciones sean consistentes).

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

6
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Por ejemplo, la ecuación tiene y y produce una

infinitud de soluciones porque cualquier punto sobre la línea recta
es una solución.

En el espacio de soluciones algebraicas (definido por x ecuaciones,

), las soluciones básicas corresponden a los puntos de esquina en
el espacio de soluciones gráficas. Se determinan igualando
variables a cero y resolviendo las ecuaciones para las variables
restantes, siempre que la solución resultante es única. Esto significa que la
cantidad máxima de puntos de esquina es:

( )

Como con los puntos de esquina, las soluciones factibles básicas definen
por completo a las candidatas para la solución óptima en el espacio de
soluciones algebraicas.

En la siguiente figura se tiene una comparación entre los Métodos Gráfico y

Símplex.

Ilustración 1 Transición de la solución gráfica a la solución algebraica. Fuente: Lieberman (2009)

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

7
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Ejemplo

Considere la siguiente PL con dos variables:

La figura siguiente proporciona el espacio de soluciones gráficas para el

problema.

Ilustración 2. Espacio de soluciones gráficas. Fuente: Taha (2004)

Algebraicamente, el espacio de soluciones de la PL está representado por las

siguientes ecuaciones y variables:

Las soluciones básicas se determinan estableciendo las

variables iguales a cero y resolviendo las variables restantes. Por
ejemplo, si establecemos y , las ecuaciones proporcionan la
solución básica única
5

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

8
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Esta solución corresponde al punto A en la Figura 3 (convénzase de que

y 5 en el punto A). Puede determinarse otro punto con y
y resolviendo luego las dos ecuaciones resultantes

La solución básica asociada es ( , ), o el punto C en la Figura 3.

Probablemente se pregunte cuáles variables deben igualarse a cero

en busca de un punto de esquina específico. Sin el beneficio del espacio de
soluciones gráficas (el cual está disponible a lo sumo sólo con tres
variables), no podemos especificar las ( ) variables cero asociadas con
un punto de esquina dado. Pero eso no nos impide enumerar todos los
puntos de esquina del espacio de soluciones. Simplemente considere todas
las combinaciones en las que variables son iguales a cero y resuelva
las ecuaciones resultantes. Una vez hecho, la solución óptima es la solución
básica factible (punto de esquina) con el mejor valor objetivo.

En el ejemplo presente tenemos puntos de esquina. Si examinamos la figura,

podemos ver los cuatro puntos de esquina A, B, C y D. Así que, ¿dónde
están los dos restantes?

De hecho, los puntos E y F también son puntos de esquina; pero son no

factibles, y, por consiguiente, no son candidatos para la solución óptima.

Para completar la transición de la solución gráfica a la algebraica, las

variables cero se conocen como variables no básicas. Las variables
restantes se llaman variables básicas, y su solución (obtenida resolviendo las
ecuaciones) se conoce como solución básica. La siguiente Tabla muestra
todas las soluciones básicas y no básicas de este ejemplo.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

9
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

MÉTODO SIMPLEX

Naturaleza iterativa del método simplex

Ilustración 3. Espacio de soluciones de la PL. Fuente: Taha (2004)

La figura siguiente muestra el espacio de soluciones de la programación

lineal del ejemplo anterior.

Por lo común, el Método simplex se inicia en el origen (punto A), donde

, , y el valor objetivo, , es cero. La pregunta lógica es si un
incremento en y/o (o ambas) no básicas por encima de sus valores
actuales de cero puede mejorar (incrementar) el valor de . Podemos
responder esta pregunta investigando la función objetivo:

Un incremento de o (o ambas) sobre sus valores actuales de cero

mejorará el valor de . El diseño del método simplex no permite el
incremento simultáneo de las variables. En cambio, incrementa una a la vez.
La variable que va a aumentar es la que tenga mayor grado de mejora en .
En el ejemplo presente, el grado de mejora del valor de es de 2 unidades
para y de 3 para . Por lo tanto elegimos para que crezca (la variable
con el mayor grado de mejora entre todas las variables no básicas).

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

10
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

La Figura anterior muestra que el valor de debe incrementarse hasta que

se llegue al punto de esquina B (recordemos que no llegar al punto de
esquina B no es una opción porque un candidato para el óptimo debe ser un
punto de esquina). En el punto B, el método simplex incrementará el valor de
para llegar al punto de esquina mejorado C, el cual es el óptimo.

La trayectoria del algoritmo simplex se define como A→B→C. Cada punto de

esquina a lo largo de la trayectoria está asociado con una iteración. Es
importante hacer notar que el método simplex se mueve a lo largo de los
bordes del espacio de soluciones, lo cual significa que el método no puede
cruzarlo, es decir, irse directamente de A a C.

Detalles de cálculo del algoritmo simplex

Ejemplo

Considere el modelo de programación lineal ( que trata sobre fábrica de

pinturas para exteriores e interiores) expresado en forma de ecuación:

(Materia prima M1)

(Materia prima M2)
(Límite del mercado)
(Límite de la demanda)

Las variables , , y son las holguras asociadas con las restricciones

respectivas. A continuación escribimos la ecuación objetivo como:
5

De esta manera, la tabla inicial simplex se representa como sigue:

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

11
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

El diseño de la tabla simplex provee automáticamente la solución en la

iteración inicial. La solución se inicia en el origen ( , ) = ( , ), por lo que
( , ) se definen como las variables no básicas y ( , , , ) como las
variables básicas. La variable objetivo y las variables básicas aparecen en
la columna de la extrema izquierda (Básica). Los lados derechos de las
ecuaciones del modelo dan sus valores, como se muestra en la columna de la
extrema derecha (Solución) de la tabla; es decir, , , ,
, .

El resultado puede verse igualando las variables no básicas ( , ) a cero en

todas las ecuaciones y también observando la configuración de matriz
identidad especial de los coeficientes de las variables básicas (todos los
elementos en las diagonales son 1, y todos los elementos fuera de las
diagonales son 0).

¿Es óptima la solución inicial? La función objetivo 5 muestra que

la solución puede mejorarse si se incrementa el valor de la variable o de la
no básica por encima de cero.

Siguiendo el argumento detallado anteriormente, tiene que incrementarse

porque tiene el coeficiente objetivo más positivo. De forma equivalente, en la
tabla simplex donde la función objetivo aparece como 5 , la
variable seleccionada es la variable no básica con el coeficiente más negativo
en la ecuación objetivo. Esta regla define la llamada condición de
optimalidad simplex. En la terminología del algoritmo simplex, se conoce
como la variable de entrada porque ingresa la solución básica.

Si es la variable de entrada, una de las variables básicas actuales debe

salir; es decir, se vuelve no básica a un nivel cero (recordemos que la
cantidad de variables no básicas debe sersiempre ). La mecánica para
determinar la variable de salida implica calcular las relaciones del lado
derecho de las ecuaciones (columna Solución) con los coeficientes de
restricción estrictamente positivos (imposibilitando así al cero) bajo la variable
de entrada, , como se muestra en la siguiente tabla:

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

12
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

¿Cómo determinan las relaciones calculadas la variable de salida y el valor de

la variable de entrada? La figura siguiente muestra que las relaciones
calculadas son en realidad las intersecciones de las líneas de restricción con
el eje (variable de entrada). Podemos ver que el valor de debe
incrementarse hasta la intersección no negativa mínima con el eje ( )
para alcanzar el punto de esquina B. Cualquier incremento más allá de B no
es factible. En el punto B, la variable básica actual asociada con la
restricción 1 asume un valor de cero y se transforma en la variable de salida.
La regla asociada con las relaciones calculadas se conoce como condición
de factibilidad simplex porque garantiza la factibilidad de la nueva solución.

El nuevo punto de solución B se determina “intercambiando” la variable de

entrada x1 y la variable de salida s1 en la tabla simplex para obtener
Variables no básicas (cero) en B: ( )
Variables básicas en B: ( )

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

13
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Ilustración 4. Relaciones entre las intersecciones con el eje horizontal. Fuente: Taha (2004)

El proceso de intercambio se basa en las operaciones de filas de Gauss-

Jordan. Identifica la columna de la variable de entrada como columna pivote y
la fila de la variable de salida como fila pivote. La intersección de la columna
pivote y la fila pivote se conoce como elemento pivote. La siguiente tabla es
un replanteamiento de la tabla inicial con sus filas y columnas pivote
resaltadas.

Los cálculos de Gauss-Jordan necesarios para obtener la nueva solución

básica son de dos tipos.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

14
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

1. Fila pivote
a. Reemplace la variable de salida en la columna Básica con la variable de
entrada.
b. Nueva fila pivote = Fila pivote actual ÷ Elemento pivote

2. Todas las demás filas, incluyendo

Nueva fila = (Fila actual) - (Coeficiente de la columna pivote) x (Nueva fila
pivote)

Estos cálculos se aplican a la tabla anterior como sigue:

1. Reemplace en la columna Básica con :

( )

( )
3
2. ( 5)

( 5 ) ( 5) ( )
3
5
( )
3
3. ( )

( ) ( ) ( )
3

( )
3
4. ( )

( ) ( ) ( )
3
5
( 5)
3
5. ( )

( ) ( ) ( )
3
( )

La nueva solución básica es ( ), y la nueva tabla es

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

15
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Observe que la estructura de la nueva tabla es similar a la de la tabla inicial,

en el sentido de que los coeficientes de las restricciones de la variable básica
forman una matriz de identidad. Por consiguiente, cuando igualamos las
nuevas variables no básicas y a cero, la columna Solución de forma
automática da la nueva solución ( , , 5, ). Este
“acondicionamiento” de la tabla es el resultado de la aplicación de las
operaciones de filas de Gauss-Jordan. El nuevo valor objetivo es z = 20,
el cual es consistente con:

Por otra parte,

5 5

En la última tabla, la condición de optimalidad muestra que es la variable

de entrada. La condición de factibilidad produce la siguiente información:

Por lo tanto, sale de la solución básica, y el nuevo valor de es 1.5. El

incremento correspondiente en es 5 el cual da la nueva

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

16
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Si reemplazamos en la columna Básica con la de entrada, se aplican las

siguientes operaciones de filas de Gauss-Jordan:

1.

2. ( )

3. ( )

4. ( )

5. ( )

Estos cálculos producen la siguiente tabla:

Según la condición de optimalidad, ninguno de los coeficientes de la fila son

negativos. De ahí que la última tabla sea óptima.

La solución óptima puede leerse en la tabla simplex de la siguiente manera.

Los valores óptimos de las variables en la columna Básica aparecen en la
columna Solución del lado derecho y se interpretan como sigue:

La solución también da el estado de los recursos. Un recurso se designa

como escaso si la variable de holgura asociada es cero, es decir, las
actividades (variables) del modelo consumieron el recurso por completo. De lo
contrario, si la holgura es positiva, entonces el recurso es abundante. La
siguiente tabla clasifica las restricciones del modelo:

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

17
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Comentarios: La tabla simplex ofrece mucha información adicional que

incluye lo siguiente:

1. Análisis de sensibilidad, el cual determina las condiciones que

mantendrán la solución actual sin cambios.
2. Análisis postóptimo, el cual determina la nueva solución óptima cuando
cambian los datos del modelo.

Estos análisis se desarrollarán con más detalle más adelante.

1.1.2 Métodos para resolución de problemas de minimización:

Método M y de las Dos Fases
Hasta ahora nos hemos ocupado del caso de maximización. En problemas de
minimización, la condición de optimalidad requiere seleccionar la variable de
entrada como la variable no básica con el coeficiente objetivo más positivo en
la ecuación objetivo, la regla exacta opuesta del caso de maximización. Esto
obedece a que equivale a ( ). En cuanto a la condición de
factibilidad para seleccionar la variable de salida, la regla no cambia.

Condición de optimalidad: La variable de entrada en un problema de

minimización es la variable no básica con el coeficiente más positivo en la fila
. El óptimo se alcanza en la iteración en la cual los coeficientes en la fila
son no positivos.

Condición de factibilidad: Tanto en problemas de maximización como de

minimización, la variable de salida es la variable básica asociada con la
relación mínima no negativa con el denominador estrictamente positivo.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

18
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Ejemplo

SOLUCIÓN ARTIFICIAL INICIAL

Como se demostró en algunos ejemplos anteriores, las PL en las que todas

las restricciones son de la forma (≤) con lados derechos no negativos ofrecen
una conveniente solución factible básica inicial con todas las holguras. Los
modelos que implican restricciones de la forma (=) o (≥) no lo hacen.

El procedimiento para iniciar PL de “mal comportamiento” con restricciones (=)

y (≥) es utilizar variables artificiales que desempeñan el papel de holguras
en la primera iteración, y que luego se desechan en una iteración posterior.
Aquí se presentan dos métodos estrechamente relacionados: el método M, y
el método de dos fases.

 Método M

El método M se inicia con la PL en forma de ecuación. Si la ecuación no

tiene una holgura (o una variable que pueda desempeñar el papel de
una), se agrega una variable artificial, , para formar una solución inicial
parecida a la solución básica de total holgura. Sin embargo, las variables
artificiales no forman parte del problema original, y se requiere un “artificio” de
modelado para igualarlas a cero en el momento en que se alcance la iteración
óptima (suponiendo que el problema tenga una solución factible). La meta
deseada se logra penalizando estas variables en la función objetivo utilizando
la siguiente regla:

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

19
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Regla de penalización para variables artificiales

Dado M, un valor positivo suficientemente grande (matemáticamente (

), el coeficiente objetivo de una variable artificial representa una
penalización apropiada si:

Ejemplo

3 3
3

Si utilizamos como variable de superávit en la segunda restricción y

como variable de holgura en la tercera restricción, el problema en forma de
ecuación es

3 3
3

La tercera ecuación tiene su variable de holgura, , pero la primera y

segunda ecuacionesno. Por lo tanto, agregamos las variables artificiales y
en las primeras dos ecuaciones y las penalizamos en la función objetivo
con (porque estamos minimizando, en una maximización se
restan las penalizaciones). La PL resultante se da como:

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

20
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

3 3
3

La solución básica inicial es ( ) (3 )

Desde un punto de vista de cálculo, la solución del problema con la

computadora requiere que reemplace M con un valor numérico
(suficientemente grande). No obstante, en todos los libros de texto, M se
maneja algebraicamente en la tabla simplex. El resultado es una dificultad
agregada innecesaria la cual puede evitarse sustituyendo un valor numérico
apropiado en lugar de M (lo que de cualquier modo tenemos que hacer
cuando usamos la computadora). Nos apartamos de la larga tradición de
manejar M algebraicamente y utilizar una sustitución numérica en su lugar. La
intención es, desde luego, simplificar la presentación sin perder la esencia.

¿Qué valor de M debemos utilizar? La respuesta depende de los datos de la

programación original. Recordemos que la penalización M debe ser lo
bastante grande con respecto a los coeficientes objetivos originales para
forzar a las variables originales a ser cero en la solución óptima.

Al mismo tiempo, como las computadoras son la herramienta principal para

resolver PL, no es conveniente que M sea innecesariamente grande ya que
ello nos puede conducir a un alto costo computacional. En este ejemplo, los
coeficientes objetivo de y son 4 y 1, respectivamente, y parece
razonable establecer .

Utilizando , la tabla simplex de inicio se da como sigue (por

comodidad, la columna se elimina porque no cambia en todas las
iteraciones):

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

21
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Antes de proseguir con los cálculos del método simplex, la fila debe hacerse
consistente con el resto de la tabla. El lado derecho de la fila en la tabla en
este momento muestra .

Sin embargo, dada la solución no básica , la solución básica

actual es 3, y , la cual da .
Esta inconsistencia se deriva del hecho de que los coeficientes de y no
son cero ( , ) en la fila .

Para eliminar la inconsistencia, tenemos que sustituir y en la fila por

medio de la siguiente operación de filas:

( )

Esta operación es la misma que sustituir 3 3 y

3 en la fila . Por tanto, la tabla modificada es:

El resultado es que y ahora se sustituyen (tienen coeficientes cero) en

la fila con , como se deseaba.

La última tabla está lista para la aplicación de las condiciones de optimalidad y

factibilidad de simplex, tal como se explicó anteriormente. Dado que la función
objetivo se minimiza, la variable que tiene el coeficiente más positivo en la
fila ( ) entra en la solución. La relación mínima de la condición de
factibilidad específica a como la variable de salida.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

22
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Una vez que se han determinado las variables de entrada y de salida, la

nueva tabla se calcula utilizando las conocidas operaciones de Gauss-Jordan.

La última tabla muestra que y son las variables de entrada y de salida,

respectivamente.

Continuando con los cálculos simplex, se requieren dos iteraciones más para
alcanzar el óptimo.

Observe que las variables artificiales y se salen de la solución básica

(es decir, se hacen iguales a cero) en la primera y segunda iteraciones, un
resultado que es consistente con el concepto de penalizarlas en la función
objetivo.

 Método de dos fases

En el Método M, el uso de la penalización, M, puede conducir a un error de

redondeo o a altos costos computacionales.

El método de dos fases elimina el uso de la constante M. Como su nombre lo

indica, el método resuelve la PL en dos fases; en la Fase I se trata de
encontrar la solución factible básica inicial y, si se halla una, se invoca la Fase
II para resolver el problema original.

Resumen del método de dos fases

Fase I. Ponga el problema en forma de ecuación y agregue las variables

artificiales necesarias a las restricciones (exactamente como en el Método M),
para tener la certeza de una solución básica. A continuación, determine una
solución básica de la ecuación resultante que siempre minimice la suma de

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

23
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

las variables artificiales, independientemente de si la PL es de maximización o

minimización. Si el valor mínimo de la suma es positivo, el problema de PL no
tiene una solución factible. De lo contrario, si el valor mínimo es cero, prosiga
con la fase II.

Fase II. Use la solución factible de la Fase I como una solución factible básica
inicial para el problema original.

Ejemplo

Utilizaremos el mismo ejemplo de minimización que se usó para el Método de

la M

3 3
3

Fase I

3 3
3

La tabla asociada es

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

24
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Como en el Método M, y se sustituyen en la fila mediante las

siguientes operaciones de filas:

( )

La nueva fila se utiliza para resolver la Fase I del problema, la cual da por
resultado la siguiente tabla óptima:

Como el mínimo , la Fase I produce la solución factible básica ,

y .

En este punto, las variables artificiales ya completaron su misión, y podemos

eliminar sus columnas de la tabla y continuar con la Fase II.

Fase II
Después de eliminar las columnas artificiales, escribimos el problema original
como:

3
5 5
3
5 5

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

25
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

En esencia, la Fase I ha transformado las ecuaciones de restricciones

originales de tal forma que proporciona una solución factible básica inicial
para el problema, si es que existe una. La tabla asociada con la Fase II del
problema es por consiguiente:

Una vez más, como las variables básicas y tienen coeficientes diferentes
a cero en la fila , deben ser sustituidas, mediante las siguientes operaciones:

( )

La tabla inicial de la fase II es por consiguiente:

Como estamos minimizando, debe entrar en la solución. La aplicación del

método simplex producirá el óptimo en una iteración.

1.2 Casos especiales de la aplicación del Método Simplex

Se considerarán cuatro casos especiales que surgen al aplicar el método

simplex.

1. Degeneración
2. Óptimos alternativos
3. Soluciones no acotadas
4. Soluciones no existentes (o no factibles)

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

26
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

1. Degeneración

Al aplicar la condición de factibilidad del método simplex, se puede presentar

un empate por la relación mínima, el cual puede romperse arbitrariamente.
Cuando esto sucede, al menos una variable básica será cero en la siguiente
iteración, y se dice que la nueva solución está degenerada.

La degeneración puede hacer que las iteraciones simplex ocurran de forma

indefinida en ciclos, y que el algoritmo nunca se termine. La condición
también revela que el modelo tiene por lo menos una restricción redundante.
El siguiente ejemplo explica los impactos prácticos y teóricos de la
degeneración.

Ejemplo
3

Utilizando las variables de holgura y , las tablas de solución se muestran

abajo. En la iteración 0, y empatan como la variable de salida, lo que
provoca degeneración en la iteración 1 porque la variable asume un valor
cero. El óptimo se alcanza en una iteración más.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

27
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Ilustración 5. Solución degenerada. Fuente: Taha (2004)

Comentarios.

1. ¿Cuál es la implicación práctica de la degeneración? Al examinar la

solución gráfica en la figura anterior se ve que pasan tres líneas por el
punto óptimo ( , ). Como éste es un problema bidimensional, el
punto está sobredeterminado, y una de las restricciones es redundante. En
la práctica, el simple conocimiento de que algunos recursos son superfluos
puede ser valioso durante la fase de implementación de la solución. La
información también permite descubrir irregularidades en la construcción
del modelo. Por desgracia, no existen técnicas de cómputo eficientes para
identificar restricciones redundantes directamente desde la tabla.

2. Desde el punto de vista teórico, la degeneración puede provocar

ciclado. En las iteraciones simplex 1 y 2, el valor objetivo no mejora
( ), y por lo tanto es posible que el método simplex entre en una
secuencia repetitiva de iteraciones que nunca mejoran el valor objetivo ni
satisfacen la condición de optimalidad. Aunque haya métodos para eliminar
el ciclado, éstos reducen drásticamente los cálculos.

3. Aun cuando quizá un modelo de PL no se inicie con restricciones

redundantes (en el sentido directo que se muestra en la figura anterior), el
error de redondeo provocado por la computadora en realidad puede crear
condiciones parecidas a la degeneración durante el curso del proceso de
solución de una PL de la vida real. En esos casos las iteraciones se
“detendrán” en un punto de solución, como si imitaran un ciclado. Los
códigos comerciales tratan de aligerar el problema al perturbar
periódicamente los valores de las variables básicas.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

28
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

2. Óptimos alternativos
Un problema de PL puede tener una cantidad infinita de óptimos alternativos
cuando la función objetivo es paralela a una restricción obligatoria no
redundante (es decir, una restricción que se satisface como una ecuación en
la solución óptima). El siguiente ejemplo demuestra la importancia práctica de
tales soluciones.

Ejemplo

La figura siguiente demuestra cómo pueden surgir óptimos alternativos en el

modelo de PL cuando la función objetivo es paralela a una restricción
obligatoria. Cualquier punto sobre el segmento de línea BC representa un
óptimo alternativo con el mismo valor objetivo .

Ilustración 6. Soluciones óptimas alternativas. Fuente: Taha (2004)

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

29
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Las iteraciones del modelo se dan en la siguiente tabla.

La iteración 1 proporciona la solución óptima , y (punto B

en la Figura). La existencia de un óptimo alternativo puede detectarse en la

tabla óptima examinando los coeficientes de las variables no básicas de la
ecuación . El coeficiente cero de la no básica indica que puede hacerse
básica, modificando los valores de las variables básicas sin cambiar el valor
de . La iteración 2 hace justo eso, aplicando y como las variables de
entrada y de salida, respectivamente. El nuevo punto de solución ocurre en C
( 3, , ).

El método simplex determina sólo puntos de esquina óptimos; es decir, los

puntos B y C en el presente ejemplo. Podemos determinar de manera
matemática todos los puntos ( , ) sobre el segmento de línea BC como un

promedio ponderado no negativo de los puntos B( , ) y C( 3,

), de lo que se concluye

̂ ( ) ( )(3) 3 3
5 3
̂ ( ) ( )( )

Comentarios. En la práctica, los óptimos alternativos son útiles porque

podemos elegir de entre muchas soluciones sin que se deteriore del valor

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

30
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

objetivo. Digamos que en este ejemplo la solución en B muestra que la

actividad 2 sólo está en un nivel positivo; en cambio, en C ambas actividades
están en un nivel positivo. Si el ejemplo representa una situación de
combinación de productos, puede ser ventajoso comercializar dos productos
en lugar de uno.

3. Solución no acotada
En algunos modelos de programación lineal, el espacio de soluciones es no
acotado en por lo menos una variable, es decir que las variables pueden
incrementarse de forma indefinida sin violar ninguna de las restricciones. En
este caso el valor objetivo asociado también puede ser no acotado.

Un espacio de soluciones no acotado casi siempre indica que el modelo está

mal construido. La irregularidad más probable en tales modelos es que no se
han tomado en cuenta algunas restricciones clave. Otra posibilidad es que las
estimaciones de los coeficientes de las restricciones quizá no sean precisas.

Ejemplo

Iteración de inicio

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

31
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

En la tabla de inicio, tanto como tienen coeficientes negativos en la

ecuación , lo que significa que al incrementarse sus valores también lo hará
el valor objetivo. Aunque debe ser la variable de entrada (tiene el
coeficiente más negativo), observamos que todos los coeficientes de
restricción bajo son ; lo que significa que puede incrementarse
indefinidamente sin violar ninguna de las restricciones (compare con la
interpretación gráfica de la relación mínima en la figura de abajo). El resultado
es que puede incrementarse indefinidamente. La Figura muestra el espacio
de soluciones no acotado y también que y pueden incrementarse
indefinidamente.

Ilustración 7. Soluciones no acotadas. Fuente: Taha (2004)

4. Solución no factible

Los modelos PL con restricciones inconsistentes no tienen una solución

factible. Esta situación no ocurre si todas las restricciones son del tipo con
lados derechos no negativos porque las holguras proporcionan una solución
factible obvia. Para otros tipos de restricciones, se utilizan variables artificiales
penalizadas para iniciar la solución. Si al menos una variable artificial es
positiva en la iteración óptima, entonces la PL no tiene una solución factible.
Desde el punto de vista práctico, un espacio no factible apunta hacia la
posibilidad de que el modelo se formuló de manera incorrecta.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

32
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Ejemplo

Considere la siguiente PL:

3

Aplicando la penalización para la variable artificial , la siguiente

tabla proporciona la iteración simplex del modelo.

La iteración óptima 1 muestra que la variable artificial es positiva ( ), es

decir que la PL es no factible. La Figura de abajo ilustra el espacio de
soluciones no factibles. Al permitir que la variable artificial sea positiva, el
método simplex de hecho ha invertido la dirección de la desigualdad de
3 a 3 . El resultado es lo que podemos llamar
una solución pseudo óptima.

Ilustración 8. Soluciones no factibles. Fuente: Taha (2004)

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

33
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

1.3 Aplicación de paquetes de cómputo para la solución de modelos

de programación lineal
En la práctica existen varios paquetes de software que sirven para la
resolución de los modelos de programación lineal, los más usuales son
LINGO, Solver de Excel, AMLP, ILOG Cplex. También pueden encontrarse
herramientas online para resolver este tipo de problemas como por ejemplo el
PHP Simplex o el GeoGebra.

Como el propósito del curso es conocer cómo funcionan los algoritmos de los
métodos de resolución ya vistos (Método Gráfico y el Símplex) daremos tan
solo un sencillo ejemplo de cómo utilizar el Excel Solver para resolver los
problemas planteados de Programación Lineal.

Cabe mencionar que el Solver solo sirve para resolver problemas sencillos;
para problemas más complejos se requieren de otros tipos de paquetes como
el ILOG Cplex.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

34
Departamento de Ciencias Básicas
Facultad Politécnica DCB_03_00
Universidad Nacional de Asunción

Bibliografía
 Taha, H. A. (2004). Investigación de Operaciones, México, D.F.:
Pearson Educación.

 Hillier, F. y Lieberman, G. (2010). Introducción a la Investigación de

Operaciones, México, D.F: McGRAW-Hill/Interamericana Editores, S.A. de C.V.

Facultad Politécnica UNA | www.pol.una.py – www.educa.una.py/politecnica

35