Lectura 2 -Programación lineal - Metodo SImplex (1)

Vista previa del material en texto

Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 1 -
MÓDULO 2: Método SÍMPLEX 
PROGRAMACIÓN LINEAL: EL MÉTODO SIMPLEX
2.1 Introducción
 En el módulo anterior hemos estudiado el método gráfico para resolver un programa 
lineal con dos variables de decisión. La presentación geométrica fue útil en la exploración de 
propiedades importantes del modelo de programación lineal.
Dado que la mayoría de los problemas del mundo real contienen más de dos variables 
de decisión, dichos problemas son resueltos mediante el método o algoritmo (procedimiento 
matemático repetitivo) simplex, o alguna variable de él. Este método fue creado por George 
Dantzig en los últimos años de la década de los cuarenta. Desde entonces, Dantzig y otros 
han continuado su desarrollo, especialmente para ciertas aplicaciones.
Visión general del método simplex
El método simplex puede sintetizarse en la siguiente forma: es un método matricial 
que consiste en dos faces. La primera fase radica en encontrar una solución inicial y la 
segunda fase consiste en probar si esa solución es óptima; si esta solución no es óptima 
buscamos otra solución y probamos nuevamente para ver si la nueva solución es óptima. Si 
ésta solución tampoco lo es, el método se repite hasta encontrar la óptima. Es un método 
algebraico sistemático que examina las esquinas (también llamados vértices o puntos 
extremos) de un conjunto factible de programación lineal en busca de la mencionada solución 
óptima.
2.2 Algunos conceptos básicos
Seguidamente repasaremos algunos conceptos necesarios para continuar con el 
desarrollo de este módulo.
Conjunto Convexo
Un conjunto de puntos S es un conjunto convexo, si el segmento rectilíneo que une cualquier 
par de puntos de S, se encuentra completamente en S.
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Pencil
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Highlight
Natita
Highlight
Natita
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Line
admin
Line
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Underline
admin
Highlight
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 2 -
Como puede apreciarse en las figuras anteriores a y b, son convexos y la figura c es 
no convexa. Para cualquier conjunto convexo S, un punto P es un punto extremo si para cada 
segmento rectilíneo que se encuentra completamente en S y que pasa por P, P es un extremo 
del segmento rectilíneo.
Vectores linealmente independientes
Un conjunto de r vectores V1, V2, …, Vr son linealmente independiente si:
α1*V1 + α2*V2 + … + αr*Vr + = ᶲ
Implica que α1 = α2 = … = αr = 0; dónde las αi (i = 1, 2, .., r) son números reales.
Combinación lineal convexa de vectores
Una combinación lineal convexa de r vectores Vi, V2, Vr es otro vector V, tal que:
V = α1*V1 + α2*V2 + … + αr*Vr 
Con la condición de que los αi ≥ 0 y ∑ αi = 0 para i = 1, 2, .., r
Por ejemplo para el caso de dos dimensiones, si realizamos una combinación lineal 
convexa de dos vectores obtendremos como resultado un punto (vector) que pertenece al 
segmento de recta que los une. Gráficamente:
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
admin
Line
admin
Line
admin
Line
admin
Line
admin
Highlight
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 3 -
Para un problema de PL, en forma estándar, con m ecuaciones de restricción y n 
variables incluidas las de holgura o excedente, enunciamos los siguientes conceptos respecto 
al conjunto de soluciones del problema:
Solución factible o posible de un PL (SF)
Es un conjunto de valores de las variables Xj que verifican el sistema de restricciones 
incluidas las de no negatividad.
Solución Factible Básica (SFB)
Es toda solución factible que tiene como máximo m variables positivas; o lo que es lo mismo, 
tiene n-m valores de las variables nulos. El número máximo de soluciones básicas es:
C (m, n) = n! / [(n-m)!*m!]
Solución Factible Básica No Degenerada
Tiene exactamente m variables positivas, o exactamente n-m variables nulas.
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Highlight
Natita
Highlight
Natita
Highlight
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Rectangle
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 4 -
Solución Factible Básica Degenerada
Tiene menos de m variables positivas, o más de n-m variables nulas.
Solución Óptima
Es toda solución que le da a la función Z el máximo (o mínimo) valor.
2.3 Observaciones sobre el conjunto de soluciones de un PL
Veamos el siguiente problema de PL (programación lineal)
Máx. (Z) = 70 x1 + 40 x2
S a 2 x1 + 5 x2 <= 2.000 (C1)
 2 x1 + 1 x2 <= 800 (C2)
 1 x1 + 1 x2 <= 500 (C3)
 x1 ; x2 >= 0
Si lo resolvemos gráficamente obtenemos:
Natita
Underline
Natita
Underline
Natita
Underline
admin
Highlight
admin
Highlight
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 5 -
La solución óptima es:
X1 = 200
X2 = 300
Z* = 29.000
Veamos el gráfico y analicemos algunas soluciones (la línea que esta en rojo 
corresponde a la función objetivo). La cantidad de soluciones posibles a nuestro problema es 
infinito y esta determinada por la zona sombreada de color verde. Una característica del 
método simplex es que trabaja con soluciones o puntos extremos y la solución óptima se 
encuentra en uno de ellos, es decir, que estos puntos que se encuentran donde se cortan dos 
restricciones o bien cuando una restricción corta algunosde los ejes.
Los puntos A (donde se corta C1 con C3) y B (donde se corta C1 con eje X2) son 
soluciones básicas factibles, son soluciones básicas porque se encuentran en un punto 
extremo y son factibles porque pertenecen a la región factible (zona sombreada de verde). El 
punto D es una solución no básica y factible, es no básica porque no es punto extremo y 
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Squiggly
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 6 -
factible por que se encuentra dentro del polígono de soluciones (región factible). Y el punto C 
(donde se corta C3 con eje X1) es una solución básica no factible. Es básica porque es punto 
extremo y es no factible porque se encuentra por fuera de la región factible.
Considerando lo analizado hasta el momento, podemos hacer las siguientes 
observaciones:
 Para cumplir con las restricciones de no negatividad de las variables, 
gráficamente se trabaja siempre en el primer cuadrante
 El poliedro de soluciones es un conjunto convexo..
 Los puntos que resulta necesario considerar para buscar el óptimo, son 
los que se encuentran sobre la frontera de la región factible.
 En particular podemos observar que si el PL tiene solución, ésta se 
encontrará en, al menos, uno de los vértices.
 Se puede obtener la solución en cada vértice resolviendo en forma 
simultánea las ecuaciones lineales que lo determinan.
 Las soluciones factibles en los vértices son soluciones factibles básicas.
 Todos los puntos del poliedro de soluciones verifican las restricciones, 
es decir que el problema tiene infinitas soluciones factibles.
 En todo punto situado sobre una recta no hay sobrante de insumos.
 En las ecuaciones determinantes del óptimo (restricciones limitantes), no 
hay sobrantes de insumos, por lo tanto, las variables de holgura son 
nulas.
 En las ecuaciones no determinantes del óptimo (restricciones no 
limitantes) siempre hay sobrantes de insumos, o sea, las variables de 
holgura son positivas.
 Si el funcional verifica su máximo valor en un único vértice del poliedro, 
significa que el problema tiene una única solución óptima.
 Si z fuera paralela a una restricción limitante, el problema tendría 
infinitas soluciones óptimas.
 Si el óptimo se verifica en un vértice donde sé cruzan 3 o más rectas de 
restricción, la solución óptima es degenerada.
 
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
admin
Line
admin
Highlight
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 7 -
2.4 Teoremas de combinaciones lineales convexas de soluciones 
factibles
Expresaremos una serie de teoremas relacionados con las soluciones factibles de los 
problemas lineales, los que resultarán de utilidad en desarrollos posteriores.
Teorema 1
Este teorema se enuncia como: "Toda combinación lineal convexa de soluciones 
factibles, es otra solución factible".
Para demostrarlo partimos de un PL estándar matricial:
Maximizar CX 
AX = B 
X ≥ ᶲ
Sean X1, X2, Xr, r vectores soluciones del PL, por lo tanto se verificará:
AX, = B
AX, = B
 ……... (1)
Xr = B
Si multiplicamos miembro a miembro las ecuaciones del sistema (1) por escalares α1; 
α2, …, αr, respectivamente, con la condición que,
αi ≥ 0 y ∑ αi =1, i = 1, 2,..., r,
Tendremos:
α1 A X1 = α1 B
α2 A X2 = α2 B
Natita
Underline
admin
Highlight
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 8 -
………… (2)
αr A X2 = αr B
Sumando miembro a miembro:
∑ αr A X2 = ∑ αr B
De donde,
A ∑ αr X2 = B ∑ αr
Siendo,
∑ αi =1,
El vector resultante de la combinación convexa,
∑ αi Xi = Xk
Será también una solución factible del PL, es decir:
AXk = B
En consecuencia queda demostrado el teorema.
Corolario del teorema 1: el conjunto de todas las soluciones factibles de un PL, si no 
es vacío, es un conjunto convexo. Es decir que, si no es vacío, está formado por un 
único elemento o por una infinidad".
Natita
Line
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 9 -
Teorema 2
"Si existe más de una solución factible que le den el mismo valor a la función objetivo, 
cualquier combinación lineal convexa de las mismas, dará al funcional igual valor*.
La demostración de este teorema es similar al anterior.
Partimos de un PL en forma estándar matricial:
Maximizar CX 
AX = B
X ≥ ᶲ
Sean Xi, X2, Xr, r vectores soluciones del PL que dan a la función objetivo igual valor, 
por lo tanto se verificará:
CX1 = Z0 
CX2 = Z0
……….. (3)
CXr = Z0
Si multiplicamos miembro a miembro las ecuaciones del sistema (3) por escalares α1; 
α2, …, αr, respectivamente, con la condición que,
αi ≥ 0 y ∑ αi =1, i = 1, 2,..., r,
Tendremos:
α1 C X1 = α1 Z0
α2 C X2 = α2 Z0
………… (2)
αr C X2 = αr Z0
Natita
Underline
Natita
Underline
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 10 -
Si ahora sumamos miembro a miembro, obtendremos:
∑ C αi Xi = ∑ αi Z0
De donde,
C ∑ αi Xi = Z0 ∑ αi
Como,
∑ αi =1,
Tendremos que el vector resultante de la combinación convexa
∑ αi Xi = Xk
Es también una solución factible del PL que otorga a la función de decisión el mismo 
valor Z0, es decir:
CXk = Zo
En consecuencia, de acuerdo a los teoremas 1 y 2, podemos afirmar que cualquier 
combinación convexa de soluciones factibles óptimas es también una solución factible 
óptima.
Por lo cual, respecto al conjunto de soluciones factibles óptimas decimos que es un 
conjunto convexo, que si no es vacío, esta formado por un elemento o por una 
infinidad.
Teorema 3
"Si un PL puede ser resuelto - es decir que posee óptimo existirá siempre por lo 
menos una solución factible básica que también sea óptima".
2.5 Método simplex
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
admin
Highlight
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 11 -
Este método, desarrollado por George Dantzig en 1947, como se mencionara 
anteriormente, permite encontrar la solución óptima de cualquierprograma lineal, 
cualquiera sea él número de variables y ecuaciones que lo forman, e identificar 
aquellos problemas que no tienen solución, o cuya solución óptima es no acotada.
El algoritmo parte de una solución básica inicial, y a través de sucesivas iteraciones, 
explora sistemáticamente los vérticés del poliedro de soluciones del Programa Lineal 
hasta identificar la solución óptima.
Si bien con posterioridad, se han desarrollado métodos que teóricamente son más 
eficientes en tiempo computacional para problemas de gran tamaño, Simplex ha 
demostrado en la práctica, un mejor desempeño en la mayoría de ios casos, razón 
por la cual es aún el de mayor difusión.
El método Simpiex tiene en cuenta las siguientes propiedades de los puntos extremos 
o soluciones factibles básicas:
1.
A) Si existe exactamente una solución óptima, entonces debe ser una 
solución de punto extremo.
B) Si existen soluciones óptimas múltiples, entonces al menos dos de ellas 
deben ser soluciones factibles en puntos extremos adyacentes (sólo se 
consideran las soluciones factibles).
2. Existe sólo un número finito de puntos extremos (soluciones factibles 
básicas).
3. Si una solución en un vértice es igual o mejor (según el valor de la función 
objetivo) que todas las soluciones factibles en los vértices adyacentes a 
ella, entonces es igual o mejor que todas las demás soluciones en los 
vértices, es decir, es óptima.
Recordemos que gráficamente, cada vértice se forma por la intersección de las rectas 
representativas de las restricciones y que los valores de las variables para cada punto 
extremo, se encuentran resolviendo en forma simultánea las ecuaciones de restricción 
correspondientes a ese vértice. A su vez, cada punto extremo o vértice corresponde a 
una solución posible básica del problema.
El método Simplex, basándose en estas conclusiones generales, analiza 
sistemáticamente los puntos extremos de la región factible hasta identificar el punto 
óptimo. Asegurándose en cada paso que el vértice analizado no es peor que el 
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
admin
Line
admin
Line
admin
Line
admin
Line
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 12 -
anterior, esto es, que le dé a la función objetivo un valor mejor o al menos igual que el 
anterior.
Pasos del método simplex
Teniendo en cuenta lo expresado en el Teorema 3, el algoritmo Simplex busca el 
óptimo de un problema de PL recorriendo algunos de los vértices del poliedro del 
conjunto de soluciones factibles de manera que el valor de la función objetivo mejore 
en cada desplazamiento.
Es decir que analiza las soluciones posibles básicas del problema hasta encontrar la 
óptima, resolviendo en cada paso un sistema de ”m" ecuaciones con "n" variables.
El método consiste fundamentalmente en dos fases:
En la primera fase se identifica una solución posible básica que sirva de punto de 
partida.
En la segunda fase o fase iterativa se analiza si dicha solución es o no óptima, y si no 
lo es, a partir de ella se encuentra una mejor.
El Simplex trabaja con tablas o cuadros, cada uno de ellos corresponde a un punto 
extremo o vértice del conjunto de soluciones factibles, es decir a una solución posible 
básica. Las tablas resumen toda la información necesaria de cada solución.
Primera Fase: identificación de una solución factible básica.
Los pasos a seguir en esta etapa son:
Convertir el modelo a su forma estándar. Esto se logra sumando una variable de 
holgura al lado izquierdo de las restricciones de < y restando una variable de 
excedente en los primeros miembros de las restricciones de >. Estas variables 
deberán interpretarse de acuerdo al significado de la restricción de que se trate, sin 
embargo, en la función objetivo llevan un coeficiente nulo ya que no agregan nada al 
objetivo.
Analizar la matriz de coeficientes del sistema de ecuaciones de restricción y ver si en 
ella existen m vectores unitarios con configuración de matriz identidad. Las variables 
cuyos coeficientes técnicos (a¡j) se corresponden con la submatriz identidad, serán 
las variables consideradas básicas en la solución inicial y sus valores en la solución 
serán los términos independientes de las restricciones (b¡). El resto de las variables 
serán consideradas no básicas y, por tanto, su valor en la solución será cero. Si la 
matriz A no contiene una submatriz identidad o existe algún componente negativo en 
Natita
Underline
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
Natita
Squiggly
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 13 -
el vector B, no se puede determinar en esta instancia una solución factible básica 
inicial y por lo tanto no es posible comenzar con Simplex.
Armar la tabla de partida, tomando como solución básica inicial la correspondiente a 
los vectores unitarios identificados en la etapa anterior.
Segunda fase: mejoramiento de la solución
1. Análisis de la solución: analizar si la solución hallada se puede mejorar, para 
ello analizar las diferencias Cj-Zj. Estos valores miden el incremento de la 
función objetivo ante un aumento unitario en el valor de cada una de las 
variables no básicas. Por lo tanto:
 Si una variable no básica que tenga asociado un (Cj-Zj)>0 ingresa a la base, el 
valor de Z aumentará.
 Si una variable no básica que tenga asociado un (Cj-Zj)<0 ingresa a la base, el 
valor de Z disminuirá.
 Si una variable no básica que tenga asociado un (Cj-Zj)=0 ingresa a la base, el 
valor de Z no se alterará.
Como consecuencia de lo anterior, la prueba de optimidad dice:
 En problemas de maximización, la solución es óptima si todas las diferencias 
(Cj-Zj) son ≤ 0.
 En problemas de minimización, la solución es óptima si todas las diferencias 
(Cj-Zj) son ≥ 0.
2. Variable de entrada: determinar la variable que ingresará a la base. La 
variable que entra a la base debe ser aquella que tenga el mayor incremento 
positivo en el caso de maximización (o mayor incremento negativo en el caso 
de minimización), ya que ésta es la variable que aumenta (disminuye) más 
rápidamente el valor de la función objetivo. Entonces:
 Si Z es de Maximización, ingresa la variable que verifica mayor diferencia 
marginal (Cj-Zj) > 0.
 Si Z es de Minimización, ingresa la variable que verifica menor diferencia 
marginal (Cj-Zj) < 0
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 14 -
3. Variable de salida: para determinar la variable que sale de la base, se 
seleccionaaquella que tenga el menor cociente entre su valor en la solución 
actual (λi) y el coeficiente λik (siendo k la variable que entra) siempre y cuando 
dicho coeficiente Sea estrictamente positivo, es decir:
Θ = min.(λi / λij)
Este cociente representa el máximo valor que puede tomar la variable entrante, antes 
que viole la restricción de no negatividad.
Si todos los λij y son ≥ 0 la solución es no acotada. Esto significa que la función 
objetivo podría incrementar (disminuir) infinitamente su valor. Esta situación es 
prácticamente imposible en la realidad, por lo cual corresponde detener el proceso de 
cálculo y revisar la modelización del problema.
4. Actualización: se debe actualizar la tabla, mediante operaciones elementales 
en filas.
5. Criterio de detención: el proceso se detiene cuando:
 Si Z es de Maximización: (Cj-Zj) ≤ 0; V j
 Si Z es de Minimización: (Cj-Zj) ≥ 0; V j
Para alguna variable no básica que pueda entrar a la base se verifica que todos los λij 
son ≤ 0
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 15 -
2.6 Caso de aplicación
Veamos un ejemplo:
Máx. (Z) = 70 x1 + 40 x2
S a 2 x1 + 5 x2 <= 2.000 
 2 x1 + 1 x2 <= 800 
 1 x1 + 1 x2 <= 500 
 x1 ; x2 >= 0
Lo primero que debemos hacer es llevar nuestro problema de programación lineal a la 
forma estándar, esto es transformar las inecuaciones en ecuaciones. Para ello en el 
caso de las restricciones de menor e igual le vamos a sumar una cierta cantidad al 
lado izquierdo para igualar este lado con el derecho de la restricción. Como no 
sabemos cual es esa cantidad ya que depende del valor de las variables de decisión, 
le vamos a sumar entonces una cantidad variable que le vamos a llamar S. Esta 
variable se denomina variable de holgura y esta asociada a los recursos, su definición 
es muy importante ya que representa la cantidad sobrante del recurso en cuestión.
Entonces como tenemos tres restricciones de menor e igual le agregamos una 
variable de holgura a cada restricción, y como son cantidades distintas estas son 
distintas. Para diferenciarlas las vamos a llamar S1, S2, S3 y nos queda de la 
siguiente manera:
 2 x1 + 5 x2 +S1 = 2.000 
 2 x1 + 1 x2 +S2 = 800 
 1 x1 + 1 x2 +S3= 500 
Lo que tenemos aquí no es ni más ni menos que un sistema de ecuaciones, en la cual 
tiene cinco variables y tres ecuaciones. Este forma un sistema que al tener más 
variables que ecuaciones nos determina un sistema compatible indeterminado, es 
decir que tiene infinitas soluciones. Observando el gráfico las infinitas soluciones está 
dado por la región factible (región sombrada).
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Highlight
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 16 -
El método simplex no analiza esta infinita cantidad de soluciones posibles sino que 
trabaja con las soluciones básicas y estas se encuentran en los puntos extremos del 
gráfico (recuerden que una solución básica se obtiene haciendo n-m variables iguales 
a cero y calculando las otras, en nuestro caso va a haber dos variables iguales a 
cero). Vallamos a nuestro ejemplo, aplicando la formula de combinatoria podemos 
calcular la cantidad de soluciones básicas, C (m, n) = n! / [(n-m)!*m!]
C (m, n) = 5! / [(5-3)*3!] =10
A cada una de estas soluciones las podemos encontrar en el gráfico (puntos 
grandes), donde se cortan dos restricciones o bien donde una restricción corta a cada 
eje. Veamos nuevamente el gráfico para identificarlas.
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Highlight
Natita
Ellipse
Natita
Ellipse
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Pencil
Natita
Underline
Natita
Underline
Natita
Underline
Natita
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 17 -
Podemos analizar cada una de estas soluciones, para ello construiremos la siguiente 
tabla:
Sol. X1 X2 S1 S2 S3 Z Observaciones
1 0 0 2.000 800 500 0 Solución básica factible no óptima
2 0 400 0 400 100 16.000 Solución básica factible no óptima
3 0 800 -2000 0 -300 -- Solución básica no factible
4 0 500 -500 300 0 -- Solución básica no factible
5 1.000 0 0 -1.200 -500 -- Solución básica no factible
6 400 0 1200 0 100 28.000 Solución básica factible no óptima
7 500 0 1.000 -200 0 -- Solución básica no factible
8 250 300 0 0 -50 -- Solución básica no factible
9 166,66 333,33 0 133,33 0 16.999,89 Solución básica factible no óptima
10 300 200 400 0 0 29.000 Solución básica factible óptima.
De las ecuaciones que habíamos formado a partir de las restricciones, agregamos la 
función objetivo, incorporamos las variables de holgura a esta última con coeficiente 
cero para que no la altere y obtenemos lo que se llama forma estándar del problema 
de programación lineal.
Máx. (Z) = 70 X1 + 40 X2+0S1 +0S2 +0S3
Sa 2 X1 + 5 X2 +S1 = 2.000 
 2 X1 + 1 X2 +S2 = 800 
 1 X1 + 1 X2 +S3 = 500 
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 18 -
 x1 ; x2 ; S1 ; S1 ; S1 >= 0
Apartir de la forma estándar de nuestro PL vamos a armar la tabla del simplex, 
sacando toda la información de la misma con una disposición conveniente para 
trabajar de manera cómoda. 
Cj 70 40 0 0 0 
Sol. x1 x2 s1 s2 s3 
2.000 2 5 1 0 0 
800 2 1 0 1 0 
500 1 1 0 0 1 
A la altura del renglón Cj, vamos a colocar los coeficientes de la función objetivo para 
cada una de las variables. Por columna tenemos el vector solución (en la tabla a la 
altura de sol.), que corresponde al lado derecho de las restricciones y van a 
corresponder al valor de las variables que no son cero (recuerde que el método 
simplex trabaja con soluciones básicas y para obtenerlas se deben hacer dos 
variables iguales a cero, y las vamos a llamar variables no básicas). A la altura de 
sol por renglón tenemos identificadas las variables y por debajo tenemos cada uno de 
los coeficientes de las restricciones.
Como hemos dicho anteriormente el método simplex arranca con una solución básica 
inicial, resultándole más conveniente hacer las variables principales del problema 
iguales a cero (X1= 0 y X2= 0), con lo cual del sistema de ecuaciones obtenemosS1 
= 2.000, S2 = 800 y S3 = 500. Que corresponde al punto de origen del gráfico y la 
solución 1 de la tabla con un valor de Z=0 (valor sombreado a la altura de la columna 
sol y fila Zj. Vamos a pasar a completar la primera tabla del simplex que habíamos 
comenzado con el resto de la información. 
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 19 -
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
0 S1 2.000 2 5 1 0 0 
0 S2 800 2 1 0 1 0 
0 S3 500 1 1 0 0 1 
Zj 0 0 0 0 0 0
Cj – Zj -- 70 40 0 0 0
X1 = 0
X2 = 0
Solución inicial= S1 = 2.000 Z inicial= 0  solución 1 de la tabla de soluciones
S2 = 800
S 3 = 500
Agregamos el vector Xk que corresponde al vector de las variables que no son cero 
en esta primera solución básica, de ahora en más las vamos a llamar variables 
básicas (porque están a la base). Ck es un vector columna conformado por los 
coeficiente de la función objetivo de las variables que están a la base.
Por otro lado hemos adicionado el renglón Zj que se calcula haciendo la suma 
producto del vector Ck por cada uno de los vectores columnas correspondiente, por 
ejemplo a la altura del vector solución tenemos: 0*2.000+0*800+0*500 = 0 y 
corresponde al valor de Z de esta solución. El renglón Cj - Zj es la prueba que realiza 
el método para saber si esta solución es la óptima o no, si en ese renglón existe un 
valor positivo significa que la solución no es la óptima (como se observa en la tabla 
hay mas de un valor positivo), si bien de antemano sabíamos que no era el óptimo 
porque lo vimos a través del método gráfico. 
Entonces encontramos una solución, que le llamamos solución inicial y a partir de cual 
simplex comienza a trabajar. El siguiente paso consiste en encontrar otra solución, 
para ello vamos a sacar unas de las variables que esta a la base (variables que tienen 
un valor positivo, esto es, S1, S2 o bien S3 y reemplazarla por X1 o X2 que 
corresponde a la variable que ingresa en el próximo paso). Intuitivamente si 
analizamos la función objetivo, vemos que nos conviene hacer positivo y lo más 
grande posible el valor de la variable X1, ya que es la que tiene mayor coeficiente en 
la función objetivo con lo cual nos haría aumentarla más rápidamente esta función y 
como se trata de un problema de maximización resulta lo más conveniente. Si vamos 
a la tabla del simplex nos fijamos en el renglón Cj - Zj encontramos como valor más 
positivo a 70 que está a la altura de X1 lo que nos indica que en la próxima tabla es la 
variable de ingreso. Para saber cual es la variable que sale de la base se realiza lo 
que se conoce como prueba de la razón, y consiste en hacer el cociente entre el 
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 20 -
vector solución y el vector columna de la variable que ingresa (λi / λij) y tomar el 
mínimo. Considerando el mínimo de λi / λij nos aseguramos de que ninguna de las 
variables que esta a la base se vuelva negativa, ya que sería un error gravísimo por la 
condición de no negatividad encontrar un λi (vector solución) negativo.
Θ = min.(λi / λij)
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
0 s1 2.000 2 5 1 0 0 Θ1=2.000/2 
0 s2 800 2 1 0 1 0 Θ2=800/2 
0 s3 500 1 1 0 0 1 Θ3=500/1 
Zj 0 0 0 0 0 0 
Cj - Zj -- 70 40 0 0 0 
El valor Θ más chico es Θ2 que está a la altura del renglón de S2, indicando que esta 
es la variable que se va a de la base en el próximo paso y en su lugar entra X1. En 
este caso Θ2 representa el valor que va a tener X1 en la próxima tabla.
Para obtener la próxima solución directamente de la tabla de simplex, vamos a tener 
que trasladar el vector unitario que esta a la altura de la variable que se va de la base 
(S2) a la posición de la columna de X1. Esta operación no se puede realizar en un 
mero acto de movimiento físico, si no que se debe realizar a través de operaciones 
elementales de matrices. Recordemos estas tres operaciones: 1). Se pueden 
intercambiar de posición dos filas o columnas, 2). Se puede multiplicar a los 
elementos de una fila por una constante distinta de cero y 3). Una fila se le 
puede sumar otra fila previamente multiplicado por una constante distinta de 
cero.
El elemento que está en la intersección de la fila de la variable que sale con la 
columna de la variable entrante se la denomina elemento pivot y es el elemento que 
en el próximo paso o iteración va a tomar el valor de 1, y es por esta fila por la que 
comenzamos a trabajar. Entonces para hacer 1 el elemento pivot vamos a multiplicar 
toda la fila por ½ (operación 2) y obtendremos lo siguiente:
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Highlight
admin
Line
admin
Line
admin
Line
admin
Underline
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 21 -
0 s1 2.000 2 5 1 0 0 Θ1=2.000/2 
0 s2 800 2 1 0 1 0 Θ2=800/2 
0 s3 500 1 1 0 0 1 Θ3=500/1 
Zj 0 0 0 0 0 0 
Cj - Zj -- 70 40 0 0 0 
70 x1 400 1 ½ 0 ½ 0
Ahora debemos hacer cero los elemento que están por encima y por debajo del 
elemento pivot, para ello nos vamos a valer de la operación 3. Tomamos la nueva fila 
calculada, la multiplicamos por el elemento opuesto al que queremos hacer cero y la 
sumamos a la primera fila de la tabla de simplex original. Entonces para nuestro 
ejemplo sería la primera nueva fila (la llamamos F1´), que es la nueva fila que 
queremos calcular) resulta de tomar la fila 2 nueva calculada (la lamamos F2´) la 
multiplicamos por el elemento opuesto que queremos hacer cero (en este caso -2) y la 
sumamos la primera fila de la primera tabla de simplex (que la llamamos F1) en 
resumen:
F1´= F2´*(-2) + F1
Para la tercera fila hacemos algo similar:
F3´= F2´*(-1) + F3
Y obtenemos:
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
0 s1 2.000 2 5 1 0 0 Θ1=2.000/2 
0 s2 800 2 1 0 1 0 Θ2=800/2 
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Line
admin
Line
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 22 -
0 s3 500 1 1 0 0 1 Θ3=500/1 
Zj 0 0 0 0 0 0 
Cj - Zj -- 70 40 0 0 0 
0 S1 1200 0 4 1 -10 
70 X1 400 1 ½ 0 ½ 0
0 S3 100 0 ½ 0 -1/2 1 
Recuerde que simplex trabaja cambiando de a una variable por vez, en el caso 
anterior sacó de la base S2 e introdujo X1 a la base y obtuvo una nueva solución. 
Ahora debemos probar si esta solución es la óptima o no y para ello volvemos a 
calcular de nuevo Zj y Cj - Zj.
Esta nueva solución por supuesto es otra solución básica, es punto extremo y la 
podemos ubicar sobre el eje X1 en intersección con la restricción C2 formando punto 
(400,0). En el ejemplo el método simplex arranco en el origen y tomo la solución 
básica adyacente inmediata sobre X1, dado que en la función objetivo es la que tiene 
mayor coeficiente. Para a próxima solución simplex va a analizar la solución 
adyacente siguiente en la misma dirección con la que arranco, esto es que si arranco 
en sentido horario va continuar en esta dirección sin volverse para atrás.
Calculemos de Zj y Cj – Zj para saber si es la solución óptima o no, aunque sabemos 
de antemano que la solución óptima no esta en este punto.
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
0 s1 2.000 2 5 1 0 0 Θ1=2.000/2 
0 s2 800 2 1 0 1 0 Θ2=800/2 
0 s3 500 1 1 0 0 1 Θ3=500/1 
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 23 -
Zj 0 0 0 0 0 0 
Cj - Zj -- 70 40 0 0 0 
0 S1 1200 0 4 1 -1 0 Θ 1=1.200/4 
70 X1 400 1 ½ 0 ½ 0 Θ 2=400/0.5 
0 S3 100 0 ½ 0 -1/2 1 Θ 3=100/0.5 
Zj 28.000 70 35 0 35 0 
Cj - Zj -- 0 5 0 -35 0 
X1 = 400
X2 = 0
Nueva solución = S1 = 1.200 Z1 = 28.000  solución 2 de la tabla de soluciones
S2 = 0
S 3 = 100
Como se muestra en la tabla anterior ya que en el renglón Cj – Zj encontramos un 
valor positivo, lo cual nos esta indicando que en próximo paso es la variable que entra 
(recordemos que si hubiera más de un valor positivo, elegimos el más positivo). 
Entonces volvemos a hacer la prueba de la razón, esto es, calcular los valores de Θ 
para saber cuan es la variable que se va de la base. Haciendo memoria, el método 
simplex trabaja de a una variable por vez, es decir que saca una variable y mete otra 
(en el próximo paso entra X2 y sale S3).
La siguiente solución que simplex va a analizar es la contigua adyacente en la misma 
dirección en la que veníamos avanzando y como se muestra en el gráfico es la 
solución óptima. 
Entonces vamos a sacar S3 y entra X2, ahora el elemento pivot es ½ que es el 
elemento que debemos hacer 1 y para ello vamos a multiplicar toda la tercera fila por 
el valor 2, o sea F3´´= F3´*(2). Para completar la tabla vamos a hacer las siguientes 
operaciones elementales:
F1´´= F3´´*(-4) + F´1
F2´´= F3´´*(-1/2) + F´2
Obteniendo la siguiente:
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
0 s1 2.000 2 5 1 0 0 Θ1=2.000/2 
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 24 -
0 s2 800 2 1 0 1 0 Θ2=800/2 
0 s3 500 1 1 0 0 1 Θ3=500/1 
Zj 0 0 0 0 0 0 
Cj - Zj -- 70 40 0 0 0 
0 S1 1200 0 4 1 -1 0 Θ 1=1.200/4 
70 X1 400 1 ½ 0 ½ 0 Θ 2=400/0.5 
0 S3 100 0 ½ 0 -½ 1 Θ 3=100/0.5 
Zj 28.000 70 35 0 35 0 
Cj - Zj -- 0 5 0 -35 0 
0 S1 400 0 0 1 3 -8
70 X1 300 1 0 0 1 -1
40 X2 200 0 1 0 -1 2 
Y luego calculamos Zj y Cj – Zj para determinar si la nueva solución es óptima o no.
Cj 70 40 0 0 0 
Ck Xk Sol. x1 x2 s1 s2 s3 
0 s1 2.000 2 5 1 0 0 Θ1=2.000/2 
0 s2 800 2 1 0 1 0 Θ2=800/2 
0 s3 500 1 1 0 0 1 Θ3=500/1 
Zj 0 0 0 0 0 0 
Cj - Zj -- 70 40 0 0 0 
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 25 -
0 S1 1200 0 4 1 -1 0 Θ 1=1.200/4 
70 X1 400 1 ½ 0 ½ 0 Θ 2=400/0.5 
0 S3 100 0 ½ 0 -1/2 1 Θ 3=100/0.5 
Zj 28.000 70 35 0 35 0 
Cj - Zj -- 0 5 0 -35 0 
0 S1 400 0 0 1 3 -8
70 X1 300 1 0 0 1 -1
40 X2 200 0 1 0 -1 2 
Zj 29.000 70 40 0 30 10 
Cj - Zj -- 0 0 0 -30 -10 
Como puede verse esta es la última tabla del simplex dado que en el Cj – Zj son todos 
positivos o nulos, esto significa que hemos encontrado la solución óptima:
X1 = 0
X2 = 0
Nueva solución = S1 = 2.000 Z* = 29.000  solución óptima
S2 = 800
S 3 = 500
2.6 Método de la variable artificial
Al resolver algunos problemas con el método Simplex, numerosas veces sucede que 
no podemos identificar la solución básica de inicial.
En general, esto ocurre cuando en el planteo tenemos restricciones de igualdad o 
inecuaciones del tipo ≥. En el primer caso, no es necesario agregar variables de 
holgura y en el segundo las agregamos restando (variable de excedente), por lo cual 
no existirán en la matriz A los m vectores unitarios necesarios para formar la primera 
solución básica.
Para solucionar este problema, se utiliza la técnica de la base artificial o simplemente 
variables artificiales. Se trata de un artilugio matemático por medio del cual, se 
agregan al problema tantas variables artificiales como vectores unitarios nos falten en 
la matriz A. De este modo, modificamos el problema original de manera tal que nos 
permita identificar la solución de partida.
admin
Underline
admin
Underline
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 26 -
Es importante destacar que estas variables no son variables del problema original. 
Por ello decimos que, una solución del mismo, se obtiene una vez que se hayan 
eliminado de la base todas las variables artificiales. Para que el algoritmo Simplex las 
elimine de la base rápidamente, se deben agregar en la función objetivo precedidas 
de un coeficiente que deberá ser:
 En caso de maximización, muy grande en valor absoluto y negativo.
 Si el problema es de mínimo, muy grande y positivo.
Si se verifica la condición de optimidad y en la base aún queda alguna variable 
artificial, puede suceder alguna de las siguientes dos cosas:
s Si la variable artificial quedó en la base con un valor positivo, entonces el problema 
original es no factible. s Si la variable artificial quedó en la base pero con un valor 
nulo, entonces la solución encontrada sí es solución del problema original y será 
degenerada ya que tendrá menos de m valores positivos.
Respecto de la variable artificial hay tres posibilidades:
a) Que la variable artificial no aparezca en la última tabla del simplex, lo que 
indica que el problema tiene solución.
b) Que la variable artificial aparezca en la última tabla del simplex con un valor 
igual a cero, esto significa que el problema tiene solución y la solución es 
degenerada.
c) Y por último que la variable artificial aparezca en la última tabla del simple, 
lo que indica que el problema no tiene solución.
Ejemplo de aplicación
Máx. (Z) = 8 X1 + 5 X2
S a 4 X1 + 2 X2 <= 1.000 
 1 X1 >= 50 
 -3 X1 + 1 X2 = 0 
 X1 ; X2 >= 0
Como puede verse en este problema tenemos una restricción de menor e igual, una 
de mayor e igual y una de igualdad. Para llevarlo a la forma estándar, en el caso de la 
primera restricción simplemente agregamos una variable de holgura y se transforma 
la desigualdad en igualdad (+S). Para el caso de la restricción de mayor e igual 
agregamos una variable de excedente (-S), el signo es lo que la diferenciade la de 
holgura, y se transforma la desigual en igualdad. Ahora ya hemos transformado las 
inecuaciones en ecuaciones y agregamos tantas variables artificiales como son 
necesarias; en nuestro caso a la segunda restricción por ser mayor e igual y a la 
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Line
admin
Line
admin
Line
admin
Line
admin
Underline
admin
Underline
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Line
admin
Highlight
admin
Highlight
admin
Highlight
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Underline
admin
Highlight
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 27 -
tercera que es una restricción del tipo desigual. Entonces el problema de 
programación lineal en su forma estándar nos queda:
Máx. (Z) = 5 X1 + 8 X2 +0S1 +0S2 - 100A2 - 100A3
Sa 4 X1 + 2 X2 +S1 = 1.000 
 1 X1 - S2 + A2 = 50 
 -3X1 + 1 X2 +A3 = 0 
 X1 ; X2 ; S1 ; S2 ; A2 ; A3 >= 0
Al incorporar las variables artificiales a la función objetivo, como se mencionara 
anteriormente, hay que darle un valor negativo muy grande en el caso de un problema 
de maximización, mínimo 10 veces el valor del coeficiente más alto de la función 
objetivo. Ahora ya estamos en condiciones de armar la tabla de simplex:
Cj 5 8 0 0 -100 -100 
Ck Xk Sol. X1 X2 S1 S2 A2 A3 
0 S1 1.000 4 2 1 0 0 0 Θ1=1000/2 
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 28 -
-100 A2 50 1 0 0 -1 1 0 Θ2=50/0 
-100 A3 0 -3 1 0 0 0 1 Θ3=0/1 
Zj -5000 100 -100 0 100 -100 -100 
Cj - Zj -- -95 108 0 -100 0 0 
X1 = 0
X2 = 0
Solución inicial= S1 = 1.000 Z inicial= -5000
A 2 = 15
A 3 = 0
Lo que diferencia este ejemplo del anterior es simplemente el armado de la primera 
tabla, de ahora en más seguimos utilizando las mismas operaciones. Entonces en el 
próximo paso entra la variable X2 y sale A2. Como el elemento pivot ya es 1 
copiamos la fila tal cual está, o sea F´3= F3
Cj 5 8 0 0 -100 -100 
Ck Xk Sol. X1 X2 S1 S2 A2 A3 
0 S1 1.000 4 2 1 0 0 0 Θ1=1000/2 
-100 A2 50 1 0 0 -1 1 0 Θ2=50/0 
-100 A3 0 -3 1 0 0 0 1 Θ3=0/1 
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 29 -
Zj -5000 100 -100 0 100 -100 -100 
Cj - Zj -- -95 108 0 -100 0 0 
8 X2 0 -3 1 0 0 0 1 
Posteriormente debemos hacer cero los elementos que están por encima y por debajo 
del elemento pivot. Recuerde que lo que estamos haciendo es trasladar el vector 
unitario de las variables que sale a la posición de la variable que entra. A continuación 
desarrollamos el simplex completo.
Cj 8 5 0 0 -100 -100 
Ck Xk Sol. X1 X2 S1 S2 A2 A3 
0 S1 1.000 4 2 1 0 0 0 Θ1=1000/2 
-100 A2 50 1 0 0 -1 1 0 Θ2=50/0 
5 A3 0 -3 1 0 0 0 1 Θ3=0/1 
Zj -5000 100 -100 0 100 -100 -100 
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 30 -
Cj - Zj -- -95 108 0 -100 0 0 
0 S1 1.000 10 0 1 0 0 -2 Θ1=1000/10 
-100 A2 50 1 0 0 -1 1 0 Θ2=50/1 
8 X2 0 -3 1 0 0 0 1 Θ3=0/-3 
Zj -5000 -124 8 0 100 -100 8 
Cj - Zj -- 129 0 0 -100 0 -108
0 S1 500 0 0 1 10 -10 -2 Θ1=500/10 
5 X1 50 1 0 0 -1 1 0 Θ2=50/-1 
8 X2 150 0 1 0 -3 3 1 Θ3=0/-3 
Zj 1.450 5 8 0 -29 29 8
Cj - Zj -- 0 0 0 29 -129 -108
0 S2 50 0 0 0,1 1 -1 -0,2
5 X1 100 1 0 0,1 0 0 -0,2
8 X2 300 0 1 0,3 0 0 0,4
Zj 2.900 5 8 2,9 0 0 3/5
Cj - Zj -- 0 0 -2,9 0 -100 -100
X1 = 100
X2 = 300
Nueva solución = S1 = 50 Z* = 2.900  solución óptima
S2 = 0
A2 = 0
A3 = 0
2.6 Problema de minimización
En cuanto a los problemas de minimización, criterio de resolución es prácticamente el 
mismo, aunque cambian algunos conceptos. Uno de ellos es la prueba que realiza el 
simplex, esto es el, Cj - Zj para determinar la variable que entra se toma el valor más 
negativo y se ha llegado al óptimo cuando todos los valores son nulos o positivos. En 
cuanto a la prueba de la razón (Θ), tanto en problemas de maximización como 
minimización siempre se toma el positivo o nulo de menor valor. Y se llega al óptimo 
Nota: λij negativo 
no se tiene en 
cuenta para la 
selección de Θ
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 31 -
cuando los valores del renglón Cj – Zj son todos positivos o nulos. Vamos con un 
ejemplo.
En lo que respecta a la incorporación de las variables artificiales, como se indicara 
anteriormente, se incorporan a la función objetivo con un coeficiente positivo muy alto 
(mínimo 10 veces el coeficiente más alto de la misma).
Min. (Z) = 30 X1 + 20 X2
Sa 1 X1 + 3 X2 <= 90 
 4 X1 + 2 X2 >= 120 
 X1 ; X2 >= 0
Forma estándar:
Min. (Z) = 30 X1 + 20 X2+0S1 +0S2 + 100A2 
Sa 1 X1 + 3 X2 +S1 = 90
 4 X1 + 2 X2 - S2 + A2 = 120 
 X1 ; X2 ; S1 ; S2 ; A2 ; >= 0
Tabla de simplex:
Cj 30 20 0 0 500 
Ck Xk Sol. X1 X2 S1 S2 A2 
0 S1 90 1 3 1 0 0 Θ1=90/1 
500 A2 120 4 2 0 -1 1 Θ2=120/4 
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 32 -
Zj 60.000 2000 1000 0 -500 500
Cj - Zj -- -1970 -980 0 500 0
0 S1 60 0 5/2 1 1/4 -1/4 
30 X1 30 1 1/2 0 -1/4 1/4 
Zj 900 30 15 0 -15/2 15/2
Cj - Zj -- 0 5 0 15/2 1015/2
X1 = 30
X2 = 0
Nueva solución = S1 = 60 Z* = 900  solución óptima
S2 = 0
A2 = 0
Todo problema de minimización puede ser resuelto como un problema de 
maximización, multiplicando la función objetivo por (-1), aplicamos simplex y una vez 
obtenido el valor de Z óptimo se lo vuelva a multiplicar por (-1). Compruebe esto.
Min. (Z) = 30 X1 + 20 X2
Sa 1 X1 + 3 X2 <= 90 
 4 X1 + 2 X2 >= 120 
 X1 ; X2 >= 0
Max. (Z) = - 30 X1 - 20 X2
Sa 1 X1 + 3 X2 <= 90 
 4 X1 + 2 X2 >= 120 
 X1 ; X2 >= 0
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 33 -
2.7 Anexo I: Solución Win QSB
El Win QSB es un software que está disponible en forma gratuita y puede ser 
descargado desde distintas páginas de internet. Este software nos permite resolver 
problemas con varias variables y varias restricciones, más que suficiente para 
resolver lo problemas desarrollados en la materia. Si el problema es de dos variables 
también lo resuelve gráficamente.
Ejemplo 1:
Máx. (Z) = 70 x1 + 40 x2
S a 2 x1 + 5 x2 <= 2.000 
 2 x1 + 1 x2 <= 800 
 1 x1 + 1 x2 <= 500 
 x1 ; x2 >= 0
Hacemos clic en nuevo problema e ingresamos los datos:
Confirmamos haciendo clic en OK, y nos aparece la siguiente tabla:
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 34 -
Completamos esta tabla con los coeficientes y parámetros de nuestro PL.
Hacemos clic en el botón gráfico y nos da la solución grafica a nuestro problema:
Solución del sistema, entramos al menúresults y hacemos clic en solution summary. 
Se obtiene el valor de las variables y el valor de la función objetivo.
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 35 -
También se puede obtener la última tabla del simplex (o sea la solución óptima) 
aunque con una disposición un poco diferente de las columnas, siendo fácilmente 
detectable si comparamos la tabla del simplex que con la que nos tira el sistema. 
Entramos en results y hacemos clic en final simplex tableau nos tira el siguiente 
resultado: 
Ejemplo 2:
Máx. (Z) = 8 X1 + 5 X2
S a 4 X1 + 2 X2 <= 1.000 
 1 X1 >= 50 
 -3 X1 + 1 X2 = 0 
 X1 ; X2 >= 0
Ingreso de los datos
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 36 -
Confirmamos haciendo clic en OK, y nos aparece la siguiente tabla:
Haciendo clic sobre el signo es te va a cambiar y elegimos el signo según el tipo de 
restricción. Completamos esta tabla con los coeficientes y parámetros de nuestro PL.
Hacemos clic en el botón gráfico y nos da la solución grafica a nuestro problema:
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 37 -
Solución del sistema: 
Última tabla del simplex: 
Ejemplo 3:
Máx. (Z) = 30 X1 + 20 X2
S a 1 X1 + 3 X2 <= 1.000 
 4 X1 + 2 X2 >= 50 
 X1 ; X2 >= 0
Ingreso al programa:
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 38 -
Carga de datos:
Hacemos clic en el botón gráfico y nos da la solución grafica a nuestro problema:
Solución:
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 39 -
Tabla final del simplex
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 40 -
2.8 Anexo II: Resolución Automática de problemas con Método Símplex
Existen sitios web que permiten al usuario resolver problemas lineales on-line 
simplemente con la única tarea de cargar los datos apropiadamente. Si bien es un recurso 
adicional a los conocimientos que se esperan del alumno para la resolución del método 
Símplex, es una excelente herramienta de apoyo para corroborar y comprobar ejercicios 
resueltos o para diseñar nuevos ejercicios y cotejar resultados.
La dirección web es la siguiente:
http://www.phpsimplex.com/
Luego recurrimos a la herramienta de resolución virtual que se encuentra clickeando la 
primer palabra que aparece en el texto introductorio: “PHPsimplex”.
Este paso nos lleva a la siguiente dirección:
http://www.phpsimplex.com/simplex/simplex.htm?l=es
A continuación se muestra la resolución completa del problema anterior con la ayuda 
on-line de esta herramienta de cálculo virtual.
http://www.phpsimplex.com/simplex/simplex.htm?l=es
http://www.phpsimplex.com/
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 41 -
Paso 1: Cargamos la cantidad de variables de decisión que tiene la función objetivo 
y la cantidad de restricciones que tiene el problema…
Paso 2: Conociendo cada uno de los valores correspondientes, armamos la función 
objetivo y las restricciones de manera idéntica a las hemos planteado en el 
problema…
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 42 -
Paso 3: El programa nos muestra un resumen de los datos ingresados hasta ahora.
En esta instancia podemos ir paso a paso armando la tabla símplex o ir directamente 
a la solución final.
 Materia: Investigación Operativa
Profesor: Ing. Pablo E. Godino
- 43 -
Paso 4:
¡Listo! La solución óptima se expresa resaltada en color verde. ¡Fácil, no?
Esto es todo. Pueden utilizar esta herramienta como apoyo para practicar con otros 
ejemplos para repasar el método.
	MÓDULO 2: Método SÍMPLEX 
	PROGRAMACIÓN LINEAL: EL MÉTODO SIMPLEX
	para problemas con más de dos variables de decisión
	trabaja con puntos extremos y la solución óptima se encuentra en uno de ellos
	2.1 Introducción
	Visión general del método simplex
	método matricial en dos fases
	1- encontrar una solución inicial 
	2- probar si esa solución es óptima
	2.2 Algunos conceptos básicos
	Conjunto Convexo
	Vectores linealmente independientes
	Combinación lineal convexa de vectores
	conceptos respecto al conjunto de soluciones del problema de programac. lineal:
	Solución factible o posible de un PL (SF)
	Solución Factible Básica (SFB)
	Solución Factible Básica No Degenerada
	Solución Factible Básica Degenerada
	Solución Óptima
	2.3 Observaciones sobre el conjunto de soluciones de un PL
	2.4 Teoremas de combinaciones lineales convexas de soluciones factibles
	Teorema 1
	Teorema 2
	Teorema 3
	2.5 Método simplex
	propiedades de los puntos extremos o soluciones factibles básicas:
	Pasos del método simplex
	Primera Fase: identificación de una solución factible básica.
	Segunda fase: mejoramiento de la solución
	1. Análisis de la solución:
	2. Variable de entrada:
	3. Variable de salida:
	4. Actualización:
	5. Criterio de detención:
	2.6 Caso de aplicación
	2.6 Método de la variable artificial
	Ejemplo de aplicación
	2.6 Problema de minimización
	2.7 Anexo I: Solución Win QSB
	Ejemplo 1:
	Ejemplo 2:
	2.8 Anexo II: Resolución Automática de problemas con Método Símplex
	resolver problemas lineales on-line 
	Paso 1:
	Paso 2:
	Paso 3:
	Paso 4: