Algoritmo Simplex

Vista previa del material en texto

Investigación
Operativa
Programación Lineal
 Algoritmo 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 arrojadas.
• 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
Introducción
Resumen del Método de GAUSS-JORDAN.
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 Factibilidad
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
Investigación
Operativa
Introducción
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Investigación
Operativa
Resumen del Método de Gauss-Jordan
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
RECORDEMOS LA SOLUCION MEDIANTE EL METODO DE GAUSS-JORDAN:
• Si se obtiene la matriz A'lb' a partir de Alb mediante una OER, los sistemas Ax = b y A'x = b' serán equivalentes.
• Cualquier sucesión de OER realizadas sobre la matriz aumentada Alb correspondiente al sistema Ax = b 
producirá un sistema lineal equivalente. 
• Con el método de Gauss - Jordan se resuelve un sistema de ecuaciones lineales utilizando sistemáticamente las 
OER.
• Ejemplo:
Las variables X1 , X2 y X3 , son variables básicas.
El sistema (9’) tiene una solución única X1 = 1, X2 = 2, X3 = 3.
Ya que se obtuvo (9') a partir de (8') mediante una sucesión de OER, (8) y (9) son sistemas lineales
equivalentes.
Así, X1 = 1, X2 = 2, X3 = 3 tiene que ser la solución única de (8).
Ing. Carlos Martin
Variables Básicas y Variables No Básicas 
• Para representar un conjunto de soluciones de A‘x=b' (y Ax=b ), necesitamos
definir los conceptos de variables básicas y no básicas.
• Definición 1: Para cualquier sistema lineal, una variable que aparece con un
coeficiente 1 en una sola ecuación y con un coeficiente cero en las otras
ecuaciones, se llama variable básica.
• Definición 2: Cualquier variable que no es básica, se denomina variable no
básica
Ing. Carlos Martin
Problema de Programación Lineal de Dos V. de D.
Consideremos el caso de maximización y que el n° de 
variables de decisión genuinas es k = 2
Ing. Carlos Martin
Es posible transformar las inecuaciones en igualdades introduciendo 
las variables de holgura (V. H.).
Las V. de H. no tienen un beneficio (su coeficiente de beneficio = 0), 
representan físicamente los sobrantes de cada recurso.
i = 1, 2, 3, 4, 5
Ing. Carlos Martin
Ing. Carlos Martin
Fundamento del Simplex
A.- Obtención de las soluciones básicas:
• Como cada vértice representa una posible combinación 
optimizante se le llama “solución básica” (SB).
• Para identificar una solución básica (vértice del convexo) se deben 
hacer n – m Variables de Decisión iguales a cero (5 – 3 = 2), en el 
plano la intersección de 2 rectas definen un punto).
• Luego es posible resolver el sistema (m ecuaciones con m 
incógnitas) y calcular las coordenadas (x1, x2) de ese vértice y el 
correspondiente beneficio Z = f (x1, x2).
• Procediendo así sobre todos los vértices se puede encontrar el 
óptimo.
Ing. Carlos Martin
• El método Simplex se ubica en una solución básica de partida (ej.: X1 = X2 = 0) 
y luego por combinaciones lineales pasa a otros extremos adyacentes del 
convexo tratando de que el funcional vaya aumentando.
• La solución básica de partida puede ser X1 = X2 = 0, o sea el origen de 
coordenadas:
(x1, x2, x3, x4, x5) = (0, 0, b1, b2, b3)
• La matriz de coeficientes de la 1ra solución básica es:
• Cada renglón corresponde a una ecuación limitante.
• Se puede identificar una Solución Básica por las 3 variables cuyas columnas consisten 
en 2 ceros y una unidad (+1) en orden de rotación (x3, x4 y x5)
• La columna de bi da los valores de las xi que están en la Solución Básica.
• Esta Solución Básica no es necesariamente la óptima (ya que para X1 = X2 = 0; Z = 0).
Ing. Carlos Martin
XA (0, 0, b1, b2, b3)
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
: Valor que toma la variable que será introducida en la base, 
siempre no negativa
Ing. Carlos Martin
Ing. Carlos Martin
Operaciones Elementales de Matrices
Operación 1: Se pueden intercambiar de posición dos filas
o columnas.
Operación 2: Se puede multiplicar a los elementos de una
fila por una constante distinta de cero.
Operación 3: Una fila se le puede sumar otra fila
previamente multiplicado por una
constante distinta de cero.
Ing. Carlos Martin
• Al elemento que esta en la 
intersección de la fila de la variable 
que sale con la columna de la 
variable entrante, se le denomina 
Pivot
• Es el elemento que en el próximo 
paso va a tomar el valor 1 (uno), y 
es por esta fila por la que 
comenzamos a trabajar.
• Entonces para hacer 1 el elemento 
Pivot vamos a multiplicar toda la fila 
2 (F2) por ½ y obtendremos lo 
siguiente:
F2´ = F2 * (1/2)
Veamos un Ejemplo
Ing. Carlos Martin
Ahora debemos hacer cero los elementos que están por encima y por debajo del 
elemento Pivot.
Queremos calcular la primera nueva fila (F1´). Tomamos la fila 2 nueva calculada 
(F2´), la multiplicamos por el valor opuesto al que queremos hacer cero, en este 
caso (-2) y la sumamos a la primera fila (F1). 
En resumen, para la primer fila: F1´ = F2´ * (-2) + F1
Para la tercera fila: F3´ = F2´ * (-1) + F3
Salió la variable S2 y entro la variable X1
Las variables básicas son: S1, X1, S3
Las variables no básicas son: X2, S2
Ing. Carlos Martin
B.- OPTIMIZACION DE LA BUSQUEDA DE SOLUCIONES BASICAS
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Investigación
Operativa
Algebra del Método Simplex
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Este método resuelve el problema de PL por medio 
de un Ordenamiento Tabular.
PASOS A SEGUIR
1. Planteo de la Función Objetivoy las Restricciones
2. Representación Gráfica (si es posible)
3. Primera Solución Básica Factible 
4. La Tabla Simplex
5. Calculo de Z y de los Zj – Cj
6. ¿Hemos Llegado a la Solución Óptima?
7. Variable que Sale de la Base: Criterio de Factibilidad
8. Variable que Sale de la Base: Criterio de Factibilidad
9. Transformación Algebraica
10. Se Repiten los Pasos 5, 6, 7, 8, y 9 
Ing. Carlos Martin
1. Planteo de la Función Objetivo y las Restricciones
Partimos de la forma estándar del PL
X i ≥ 0
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
2. Representación Gráfica (si es posible)
Identificar Soluciones Básicas Factibles
Ing. Carlos Martin
Ing. Carlos Martin
3. Primera Solución Básica Factible 
4. La Tabla Simplex
Ing. Carlos Martin
http://www.auladeeconomia.com
Ing. Carlos Martin
5. Calculo de Z y de los Zj – Cj
http://www.auladeeconomia.com
6 ¿Hemos Llegado a la Solución Óptima?
Ing. Carlos Martin
http://www.auladeeconomia.com
Ing. Carlos Martin
7. Variable que Entra a la Base: Criterio de Optimalidad
Ing. Carlos Martin
8. Variable que Sale de la Base: Criterio de Factibilidad
Ing. Carlos Martin
9. Transformación Algebraica
Ing. Carlos Martin
Ing. Carlos Martin
10. Se Repiten los Pasos 5, 6, 7, 8, y 9 
MÉTODOS Y MODELOS DE INVESTIGACIÓN DE OPERACIONES VOL. 1 -
JUAN PRAWDA
Ing. Carlos Martin
INVESTIGACION DE OPERACIONES TAHA 
Ing. Carlos Martin
INTRODUCCIÓN A LA INVESTIGACIÓN DE OPERACIONES HILLER
Ing. Carlos Martin
INVESTIGACIÓN DE OPERACIONES WINSTON
Ing. Carlos Martin
Investigación
Operativa
Ejemplo
Facultad de Ingeniería
Universidad Nacional de Jujuy, Jujuy, AR
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
Ing. Carlos Martin
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
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