Justificacion y Significado de los Elementos de la Tabla Simplex

Vista previa del material en texto

Investigación
Operativa
Programación Lineal
Justificación y Significado de los 
Elementos de la Tabla Simplex
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
• PRESENTACIÓN
En este capítulo se presenta el método simplex de solución de problemas de programación lineal incluyendo 
problemas de maximización y minimización.
• OBJETIVO GENERAL
Al finalizar el capítulo el estudiante debe estar en capacidad de solucionar un problema de programación lineal 
utilizando el método simplex; así como interpretar correctamente la solución y analizar el consumo de 
recursos.
• OBJETIVOS ESPECÍFICOS
• Manejar las reglas de equivalencia para llevar todas las desigualdades a igualdades.
• Dominar el procedimiento de avance hacia la Optimalidad del método simplex.
• Determinar mediante el método simplex el momento en el que se llega a la solución óptima, tanto en 
problemas de maximización como de minimización.
• Identificar el tipo de solución del problema con el uso de la tabla simplex.
• Interpretar las soluciones obtenidas.
• COMPETENCIAS
El estudiante tendrá la capacidad de utilizar el método simplex en la solución de problemas de programación 
lineal; y con base en ésta interpretar el tipo de solución del problema; así como el uso de variables de holgura, 
de exceso y artificiales.
• INDICADORES DE LOGRO
El estudiante deberá demostrar el manejo en el planteamiento de modelos de programación lineal, obtener la 
solución a través el método simplex e interpretar la solución.
• CONOCIMIENTOS PREVIOS
• Gauss Jordan.
• Vectores y matrices.
Ing. Carlos Martin
 Tenemos que tener en cuenta que además de la solución, 
el método simplex nos proporciona información importante 
en lo que concierne a soluciones alternativas y los efectos de 
los cambios en los datos básicos sobre la solución. 
Explicaremos la lógica y el significado económico de todos 
los elementos en la tabla simplex.
Ing. Carlos Martin
Para ello presentamos el siguiente ejemplo:
Una fabrica de muebles hace dos productos, mesas y sillas, que se
deben procesar a través de los departamentos de ensamble y
acabado.
 Ensamble tiene 60 horas disponibles; acabado puede manejar
hasta 48 horas de trabajo.
 La fabricación de una mesa requiere 4 horas de ensamble y 2
horas de acabado.
 Cada silla requiere 2 horas de ensamble y 4 horas de acabado.
Si la utilidad es $ 8 por mesa y $ 6 por silla, el problema es
determinar la mejor combinación posible de mesas y sillas para
producir y vender para obtener la máxima utilidad.
Ing. Carlos Martin
Se han Identificado las variables de decisión, la función objetivo, las restricciones y se ha 
realizado la formulación completa del modelo matemático.
Formulación Matemática
• Maximizar: Utilidad = $8T + $6C
• Sujeto a: 4T + 2C  60 (Ensamble)
2T + 4C ≤ 48 (Acabado)
Todas las variables: ≥ 0
Nombre de las variables:
• T: Cantidad de Mesas a producir
• C: Cantidad de Sillas a producir
• SA: variable de holgura (tiempo no usado) en el ensamble
• SF: variable de holgura (tiempo no usado) en el acabado
• Ensamble: SA = 60 - 4T - 2C
• Acabado: SF = 48 - 2T - 4C
Ing. Carlos Martin
Ing. Carlos Martin
Se lo ha resuelto por el Método Gráfico y el Método Simplex.
Ing. Carlos Martin
Ing. Carlos Martin
SA = 0
SF = 0
Investigación
Operativa
Interpretación de las 
Tasas Marginales de Sustitución
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Ing. Carlos Martin
Trabajaremos sobre la segunda tabla simplex , para ello hemos 
numerado a cada uno de sus elementos.
Tasas Marginales de Sustitución 
 Una tasa positiva de sustitución, indica la 
disminución que ocurre en una variable si 1 
unidad de otra variable se añade al programa.
 Una tasa negativa de sustitución, indica el 
aumento que ocurre en una variable si 1 unidad 
de otra variable se añade al programa.
Ing. Carlos Martin
La Columna de Cantidad (Bk): Variables Básicas
(1)
• En la tabla simplex inicial notamos que T (mesas) hace la mayor contribución 
por unidad a la utilidad: (Zj – Cj) = 8, entonces T ingresa a la base.
Para encontrar la cantidad a añadir, procedemos de la siguiente manera:
(60 hs disponibles en el ensamble) / (4 hs requeridas/mesa) = 15 mesas
• Encontramos que 15 era la cantidad mayor que se podía fabricar sin violar 
ninguna de las restricciones de tiempo en ambos departamentos.
• Hacer 15 mesas requirió de todas las horas disponibles en el ensamble 
(4 horas por unidad x 15 unidades = 60 horas)
• Así, T reemplazó a SA en la solución. T = 15 y SA = 0
Ing. Carlos Martin
La Columna de Cantidad (Bk): Variables Básicas
(2)
Cada una de las 15 mesas requirió 2 horas en el acabado. 
Así, para hacer 15 mesas requirió 30 horas de acabado:
(2 horas por unidad x 15 unidades) = 30 hs
Puesto que de las 48 horas que están disponibles, sólo se requieren de 30 horas, 
tenemos:
18 horas sin usar en el acabado. SF = 18
(3) 
El $ 120 representa la utilidad total Z de las variables en la mezcla de productos.
Ing. Carlos Martin
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
(4)
• Puesto que 1 unidad de T (1 mesa) requiere 4 horas en el ensamble, la 
segunda solución utiliza todas las 60 horas en el ensamble. 
• Por consiguiente, la producción de cualquier cosa en este departamento 
requeriría que algunas de las mesas se sustituyeran.
• Por ejemplo, si se pusiera disponible para otros propósitos 
1 unidad de SA (1 hora), se tendría que entregar 1/4 de mesa; 
o dicho de otra manera, 
cada hora de SA añadida a la solución reduce la producción de T (mesas) 
por 1/4 de unidad.
Tasas de sustitución: La matriz de los coeficientes
(5) El reducir la producción de T (mesas) por 
¼ de unidad ciertamente debe tener un 
efecto sobre el acabado porque las mesas y 
las sillas se deben procesar a través de 
ambos departamentos.
• Debido a que T requiere 2 hs. por unidad en acabado y que añadir una 
unidad de SA reduce la producción de T (mesas) por ¼ de unidad, 
¼ x 2 = ½ hora se libera en acabado. Podemos ilustrar esto así:
Ing. Carlos Martin
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
(8)
• Al añadir 1 unidad de SF no tiene efecto (0) sobre T. ¿Por qué?
• Puesto que el ensamble es el departamento limitante (se han
usado todas las horas), el poner disponible 1·hora de SF en el
acabado no tendrá efecto sobre la producción de mesas.
• Puesto que 18 horas todavía están disponibles en el acabado,
podemos poner una de ellas disponibles sin reducir nuestra
producción de mesas.
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
(9)
• Al retirar 1 unidad de SF; puesto que sólo hay 18 horas
disponibles en el acabado en la segunda solución,
removería una de las 18 horas disponibles.
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
(12)
• Una vez más tenemos una sustitución de 1 por 1; esto es, cada unidad de T añadida al
programa de producción reemplaza 1 unidad de T en la solución.
• De (1) encontramos que 15 era la cantidad más grande de mesas que se podían
procesar en el ensamble.
• Así, para añadir otra mesa (1T) y al mismo tiempo satisfacer la restricción de tiempo en
el ensamble (60 horas disponibles), debemos restar o no producir 1 mesa para poner
disponible el tiempo necesario.
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
(13)
• El añadir 1 unidad de T al programa de producción no tiene efecto sobre SF, ¿Por qué?
• En (12) encontramos que añadir 1 mesa (1 T) requiere no producir 1
mesa (1T) así, que el cambio neto en acabado debe ser cero (1 - 1 = 0).
• Puesto que no hay cambio real en el ensamble, tampoco hay cambio
alguno en el acabado.
• No se requieren horas adicionales.
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
• (16)
• El añadir 1 unidad de C (silla)al programa, reemplaza ½ T (mesa): 
una silla (1C) requiere 2 hs por unidad en ensamble y 
una mesa (1T) requiere 4 hs. 
• Ahora, debido a que el ensamble es el departamento limitante (el tiempo 
está agotado), el procesar 1 silla requerirla dejar de producir 2/4, o ½, 
mesa (½T). 
• Dicho de otra manera, el procesar una silla en el ensamble requiere 2 de 
las 4 horas requeridas para hacer una mesa. 
• Así, por cada silla procesada en el ensamble, se debe dejar de producir
½ mesa para proporcionar las 2 horas necesarias. 
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
• (17)
• El añadir 1 unidad de C (silla) reemplaza 3 unidades de SF, (3 horas). 
• El problema original establecía que 1 C requería 4 horas en acabado. ¿Cómo se puede justificar esta 
inconsistencia aparente? 
• Primero, note que el añadir 1 silla (1C) reemplaza ½ mesa (de (16)). 
• Segundo, una mesa requiere 2 horas en acabado. Así, al dejar de producir ½ mesa libera 1 hora en acabado (½ x 
2 horas requeridas por unidad-de-T = 1 hora).
• Las 4 horas requeridas para hacer una silla en el acabado menos la 1 hora liberada es igual a 3 horas netas de 
cambio. 
• El procesar una silla aún requiere 4 horas por unidad: 3 horas + 1 hora liberada es igual a las 4 horas requeridas. 
• La inconsistencia por tanto desaparece cuando consideramos el efecto de un cambio, no en un departamento 
sino en ambos departamentos. 
• Las sillas y las mesas se deben procesar en ambos departamentos para hacer una unidad completa. Así, cualquier 
cambio en el ensamble debe tener un efecto en el acabado.
Tasas de sustitución: La matriz de los coeficientes
Ing. Carlos Martin
• En resumen, 
• los ocho elementos que hemos discutido, representan las tasas 
marginales de sustitución entre las variables en la mezcla de productos 
y las variables en el encabezado de la columna. 
• Encontramos que una tasa positiva de sustitución, por ejemplo, (16), 
indica la disminución en T que ocurre si 1 unidad de C se añade Al 
programa.
• Por otra parte, una tasa negativa de sustitución, por ejemplo, (5), indica 
aumento en SF, esto es, ½ hora liberada lo que ocurre si 1 unidad de SA 
se añade al programa.
Investigación
Operativa
Interpretación de la Solución
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Ejemplo 1. Suponga que en el ensamble procesamos 5 mesas 
y 3 sillas. 
• Ensamble: SA = 60 - 4T - 2C
• SA = 60 - 4(5) - 2(3)  SA = 34 hs no usadas de 
tiempo en ensamble
Ejemplo 2. Suponga que en acabado procesamos 4 mesas y 6 
sillas.
• Acabado: SF = 48 - 2T - 4C
• SF = 48 - 2(4) - 4(6)  SF = 16 hs de tiempo no usado 
en acabado
Ing. Carlos Martin
Se encontró la solución óptima después de 3 iteraciones (o 
pivoteos) del algoritmo simplex.
El valor de óptimo de Z es 132.
Para cada variable, la columna Cantidad da el valor de la 
variable para la solución óptima del PL.
• Así, la solución óptima indica que se tiene que producir 12 
mesas y 6 sillas.
Ing. Carlos Martin
Para cada restricción, el valor de la holgura o del exceso en la 
solución óptima. Así tenemos:
• SA = holgura para la restricción de tiempo en ensamble = 0
• SF = holgura para la restricción de tiempo en acabado = 0
Ing. Carlos Martin
Investigación
Operativa
Interpretación del Renglón Zj
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
• Los Zj representan la pérdida de utilidad que resulta de la adición de 1 unidad de
la variable que encabeza la columna.
(6) El añadir una unidad de SA resulta en dos cambios:
• (a) T se disminuye por 1/4 de unidad (ver (4))
• (b) SF se aumenta por ½ unidad (se libera una hora; ver (5)).
Ing. Carlos Martin
• ¿Cuánta utilidad se perdería si estos dos cambios tuvieran lugar?
• Puesto que la utilidad por unidad de T es $8 y T se disminuye por ¼ de unidad, la
utilidad perdida por este cambio seria de $8 x ¼ T = $2.
• Debido a que la utilidad por unidad de SF, es $0, el incremento en SF, por ½
unidad resulta en una ganancia nula ($0 x ½ SF = $0).
• La utilidad perdida total es la suma de los dos cambios: $2 + $0 = $2.
• El mismo razonamiento se aplica a los otros elementos del renglón Zj.
Ing. Carlos Martin
Investigación
Operativa
Interpretación del Renglón Zj – Cj: 
Costos Reducidos
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Un número negativo en el renglón Zj – Cj indica la cantidad de aumento, en 
utilidades totales si se añade a la solución 1 unidad de la variable que 
encabeza esa columna. 
Un número positivo en el renglón Zj – Cj indica la cantidad de disminución, 
en utilidades totales si se añade a la solución 1 unidad de la variable que 
encabeza esa columna. 
Para aquellas actividades que están a nivel cero en la solución óptima 
(variables no básicas), la cantidad Zj – Cj se denomina costo reducido por 
unidad de actividad j.
El costo reducido representa la diferencia neta entre el costo del recurso 
usado para producir una unidad de Xj (Zj) y su ganancia por unidad (Cj)
El costo reducido para cada variable básica tiene que ser cero.
Ing. Carlos Martin
Ing. Carlos Martin
(19) Z1 – C1 = - 2 y 
(7) Z2 – C2 = 2
En cuanto a las actividades (variables genuinas):
(15) Z1 – C1 = 0 y 
(19) Z2 – C2 = - 2
Ing. Carlos Martin
En cuanto a las disponibilidades (Variables de Holgura y de Exceso)
Los precios sombra del recurso i miden el valor marginal de éste, es decir, la tasa a 
la que Z puede aumentar si se incrementa en una unidad la cantidad que se 
proporciona de este recurso (bi).
(7) Z3 – C3 = 2
(11) Z4 – C4 = 0
Ing. Carlos Martin
Investigación
Operativa
Identificando casos anómalos y soluciones
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Solución óptima:
• Cuando se cumple la condición de parada y no hay variables artificiales en la 
base con valor positivo (los valores se indican en la columna Bk), se ha 
conseguido la optimización. 
• El valor Z0P actual es la solución óptima del problema, cumpliéndose para las 
variables que se encuentran en la base.
Infinitas soluciones:
• Cumplida la condición de parada, si alguna variable de decisión no básica 
tiene un valor 0 en la fila ZJ - Cj, significa que existe otra solución que aporta 
el mismo valor óptimo para la función objetivo. 
• Es este caso el problema admite infinitas soluciones, estando todas ellas 
comprendidas dentro del segmento (o porción del plano, región del espacio, 
etc. dependiendo del número de variables del problema) definido por 
1·X1 + ·2 X2 = ZOP
• Mediante una nueva iteración y haciendo que la variable de decisión que 
tiene el 0 en la fila ZJ - Cj , entre en la base se obtendrá otra solución diferente 
para el mismo valor óptimo.
Ing. Carlos Martin
Solución ilimitada (no acotada):
• Si toda la columna de la variable que entra a la base tiene todos 
sus elementos negativos o nulos se trata de problema no acotado, 
es decir, que tiene solución ilimitada. 
• No hay valor óptimo concreto para la función objetivo sino que a 
medida que se aumenta el valor de las variables también se 
incrementa el valor Z sin violar ninguna restricción.
No existe solución:
• Cuando ningún punto satisface todas las restricciones del 
problema se produce la infactibilidad no existiendo ninguna 
solución posible para él. 
• En este caso, una vez terminadas todas las iteraciones del 
algoritmo, existen en la base variables artificiales cuyo valor es 
mayor a cero.
Ing. Carlos Martin
Empate de variable entrante:
• Cuando se produce un empate en la condición de decisión de la variable 
entrante se puede optar por cualquiera de ellas sin que esto afecte a la 
solución final. 
• Sí influye en el número de iteraciones necesarias para obtener dicha solución.
• Se aconseja optar a favor de las variables básicas ya que ellas son las que 
formarán parte de la solución óptima.
• Empate de variable saliente:
• Se puede nuevamente optar por cualquiera de ellas.• Sin embargo, a fin de no alargar el problema y evitar la entrada en un bucle 
infinito (caso degenerado), se discrimina a favor de las variables de decisión 
haciendo que permanezcan en la base. 
• En el caso de estar en la primera fase del método de las Dos Fases, se optará 
por sacar de la base las variables artificiales.
Ing. Carlos Martin
Curiosidad en la Fase 1:
• Al finalizar la fase 1, si el problema original tiene solución, 
todas las variables artificiales en el renglon ZJ - Cj deben 
tener el valor "1".
¿El elemento pivote puede ser nulo?:
• No, el elemento pivote siempre será estrictamente positivo 
ya que únicamente se realizan los cocientes entre valores no 
negativos y mayores que cero (ante un problema de 
maximización).
Ing. Carlos Martin
Investigación
Operativa
Resumen Unidad II
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
• Introducción a la Programación lineal: ¿Qué es un problema de 
programación lineal?: Función lineal, desigualdad lineal. 
Características de un problema de programación Lineal: Objetivos, 
restricciones, función económica, interpretación de variables. 
Ejemplo Prototipo. Formulación matemática de problemas de 
programación lineal: Identificación de las Variables de Decisión y 
sus correlaciones con los coeficientes tecnológicos, recursos y 
contribuciones económicas. 
• Solución gráfica de problemas bidimensionales de PL. Observación 
de algunos aspectos técnicos: Punto Extremo, Vértice adyacente, 
Redundancia, Ilimitabilidad, Más de una solución óptima, 
Imposibilidad, Degeneración. Ejemplos de Problemas de 
Programación Lineal.
• Método Simplex: ¿Por qué la necesidad del algoritmo Simplex?. 
Formas equivalentes de la programación lineal: Reglas generales 
para convertir un programa lineal a forma estándar. Definiciones: 
Solución Factible
Ing. Carlos Martin
• Solución Factible Básica, Solución Factible Básica no 
degenerada, Solución Factible Básica degenerada, Región de 
Factibilidad Teoremas básicos de la Programación lineal: 
Conclusiones. Reglas del método Simplex. Interpretación 
Técnica-Económica de todos los elementos de la tabla 
óptima del Simplex.
• Los fundamentos del algoritmo Simplex: Obtención de 
Soluciones básicas, optimización de la búsqueda de 
Soluciones básicas.
Ing. Carlos Martin
• Solución de Problemas de Programación lineal: Reglas del Método 
Simplex. Armado de la solución inicial: Conversión de 
desigualdades a ecuaciones (Variables de Holgura). La Tabla 
Simplex (Tabla de Charnes, Cooper y Anderson): La columna de las 
cantidades, tasas de sustitución, el renglón Z, El renglón (Zj-Cj). La 
primera solución mostrada en la Tabla Simplex. Álgebra del 
Método Simplex: Criterios para ingresar y extraer variables de la 
solución. Transformación de la base: Relaciones con el Método 
Gauss-Jordan. Prueba de Optimalidad: Solución Óptima. 
Formulación de varios problemas: Soluciones Óptimas no 
Acotadas; Soluciones Óptimas Múltiples; Problemas no Solubles; 
Degeneración y convergencia del algoritmo Simplex: Caso de 
empate entre variables de salida y reglas lexicográficas.
• Problemas de Minimización: Técnica de la Base Artificial (Variables 
Ficticias). Método de Penalización. Método de Doble Fase. 
Variables sin Restricción de signo. Ejemplos Práctica.
Ing. Carlos Martin
BIBLIOGRAFIA
 Prawda Witenberg J. “Métodos y Modelos de Investigación de 
Operaciones – Vol. 1 Modelos Determinísticos”. Editorial Limusa. 
©1999
 Taha Hamdy A. “Investigación de Operaciones”. Editorial Alfa Omega. 
©1998
 Winston Wayne L.. “Investigación de Operaciones. Editorial. Grupo 
Editorial Iberoamericana. ©2005
 Hillier Frederick S. “Introducción a la Investigación de Operaciones. 
Editorial. Mc Graw Hill. ©2001
 Eppen G.D. “Investigacion de Operaciones En la Ciencia Administrativa. 
Editorial Prentice. ©2000
 Mathur-Solow – Investigación de Operaciones – Ed. Prentice Hall 1996.
 MARIN, Isidoro. “Investigación Operativa”. UBA. Centro de Estudiantes 
Universidad Nacional de Buenos Aires. © 1970
 LEVIN, Richard I.. “Enfoques Cuantitativos a la Administración”. CECSA
Ing. Carlos Martin
Preguntas
Ing. Carlos Martin
Investigación
Operativa
Muchas Gracias
Profesor: Ing. Carlos A. Martin
E-mail: ing_carlos_martin@hotmail.com
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR