Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
Investigación Operativa Programación Lineal Método Simplex Profesor: Ing. Carlos A. Martin E-mail: ing_carlos_martin@hotmail.com Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Método Simplex (MS) ¿Por qué la necesidad del algoritmo Simplex? Formas equivalentes de la PL: Reglas generales para convertir un programa lineal a forma estándar. Definiciones: Solución Factible, 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 PL: 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 PRESENTACIÓN En este modulo se presenta el método simplex de solución de problemas de PL incluyendo problemas de maximización y minimización. OBJETIVO GENERAL Al finalizar el modulo el estudiante debe estar en capacidad de solucionar un problema de PL utilizando el MS; así como interpretar la solución y analizar el consumo de recursos. OBJETIVOS ESPECÍFICOS • Manejar las reglas de equivalencia para llevar las desigualdades a igualdades. • Dominar el procedimiento de avance hacia la optimalidad del MS. • Determinar mediante el MS, cuando se llega a la solución óptima, en PL de Max. y de Min. • 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 MS en la solución de problemas de PL; interpretar el tipo de solución; 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 PL, obtener la solución a través del MS e interpretar la solución. CONOCIMIENTOS PREVIOS Gauss Jordan. Vectores y matrices. Investigación Operativa Programa Lineal Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Definición: Un problema de programación lineal (PL) es un problema de optimización, para el cual hacemos lo siguiente: Tratamos de maximizar (o minimizar) una función lineal de V. D La función que se pretende maximizar o minimizar se llama F. O. Los valores de las variables de decisión tienen que satisfacer un conjunto de restricciones. Cada restricción tiene que ser una ecuación lineal o una desigualdad lineal. Hay una restricción de signo para cada variable. Para cualquier variable xi , la restricción de signo especifica que xi tiene que ser no negativo (xi 0) o que xi puede ser una variable sin restricción de signo (SRS) Ing. Carlos Martin Definición. Una función f (xl,x2, .. .,xn,) es una función lineal de xl,x2,...,xn, si y sólo si para algún conjunto de constantes c1 , c2 ,..., cn , f(x1, x2 ,..., xn) = cl xl + c2 x2 +...+ cn xn Por ejemplo: f(x1, x2) = 2 x1 + x2 es una función lineal de x1, y x2 , pero f(x1, x2) = x1 2 x2 no es una función lineal de x1, y x2 . Definición. Para cualquier función lineal f (x1,x2,...,xn) y cualquier número b, las desigualdades f (x1, x2,...,xn) b y f (x1, x2,...,xn) b , son desigualdades lineales Así, 2x1 + 3X2 < 3 y 2x1 + X2 > 3 son desigualdades lineales, pero X1 2 X2 > 3 no es una desigualdad lineal. Ing. Carlos Martin Ing. Carlos Martin En: En: Investigación Operativa Forma Estándar de un PL Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR CÓMO TRANSFORMAR UN PL EN LA FORMA ESTÁNDAR • Un PL puede tener restricciones en forma de igualdad o de desigualdad. • También puede tener variables que tienen que ser no negativas, o variables SRS. • Antes de poder usar el algoritmo simplex para resolver PL, hay que transformar el PL en un problema equivalente, en el cual todas las restricciones son ecuaciones y todas las variables son no negativas. • Un PL que se encuentra en esta forma, esta en su forma estándar. • Para transformar un PL en la forma estándar, hay que sustituir cada restricción en forma de desigualdad, por una restricción en forma de igualdad. • Ilustramos este procedimiento mediante el siguiente problema. PROGRAMACION LINEAL (PL) 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. Xi ≥ 0, i = 1, …,5 Ing. Carlos Martin Investigación Operativa En que consiste un problema de PL? Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR 1. EL PROBLEMA DE PROGRAMACION LINEAL El problema general de programación lineal consiste en encontrar un vector (x1, x2,...,xj,...,xn.) que optimice (maximice o minimice) la función del objetivo: Z = Cl Xl + C2 X2 + ... + Ci Xi + ... + Cn Xn (Máx. o Min.) (1.1) sujeta a las restricciones lineales: a11 x1 + al 2 x 2 +... + a1j xj +...+a1n xn = b1 a21 x1 + a2 2 x 2 +... + a2j xj +...+a2n xn = b2 ................................................................... (1.2) ai1 x1 + ai 2 x 2 +... + aij xj +...+ain xn = bi ................................................................... am1 x1 + am 2 x 2 +... + amj xj +..+amn xn = bm y a las condiciones de signo xj > 0 i = 1, 2,..., n (1.3) donde las aij, bi, y cj son constantes dadas y m < n. Siempre supondremos que las Ecs. (1.2) han sido multiplicadas por -1 cuando sea necesario hacer todas las bi > 0. Investigación Operativa Propiedades de una solución a un PPL? Facultad de Ingeniería Universidad Nacional de Jujuy, Jujuy, AR Definición 1: Una solución factible al problema de PL, es un vector X = x1, x2,...,xn. el cual satisface las condiciones (1.2) y (1.3). Definición 2a: Una solución básica para (1.2) es una solución obtenida al hacer n - m variables igual a cero y resolver por las m variables que quedan (siempre que el determinante de los coeficientes de estas m variables no sea cero). Las m variables se llaman variables básicas. Definición 2b: Una solución básica factible (sbf) es una solución básica que también satisface (1.3); esto es, todas las variables básicas son no negativas. Definición 3: Para cualquier PL con m restricciones, se dice que dos soluciones básicas factibles son adyacentes si sus conjuntos de variables básicas tienen m-1 variables básicas en común. Ing. Carlos Martin PUNTOS EXTREMOS: VARIABLES BASICAS Y NO BASICAS Ing. Carlos Martin Definición 4a: Una solución básica factible no degenerada es una sbf con exactamente m componentes positivas del vector X. Definición 4b. Una solución básica factible degenerada es una sbf donde hay menos de m componentes positivas del vector X. Definición 5: Una solución factible máxima es una solución factible que también maximiza (1.1). Definición 6: La región factible para un PL es el conjunto de todos los puntos que satisfacen las restricciones y las restricciones de signo. Ing. Carlos Martin Ejemplo de una Solución Básica Factible Degenerada V. de D. = 0: Dos V. de D. = 0: Tres, n –m = 2 Ing. Carlos Martin Ing. Carlos Martin Ing. Carlos Martin Teorema 2.5. Para cualquier PL, existe un punto extremo único de la región factible de PL que corresponde a cada sbf. También existe por lo menos una sbf que corresponde a cada punto extremo de la región factible. Definición 7: Una restricción se considera obligatoria si el lado izquierdo es igual al lado derecho de la restricción al sustituir los valores óptimos de las variables de decisión en la restricción. Definición 8: Una restricción se llama no obligatoria si el lado izquierdo no es igual al lado derecho de la restricción al sustituir los valores óptimos de las V. de D. en la restricción. Ing. Carlos Martin Ing. Carlos Martin Investigación Operativa Forma Canónica y Formas Equivalentes de la PL? Facultad de IngenieríaUniversidad Nacional de Jujuy, Jujuy, AR Ing. Carlos Martin Convertir un PL de la Forma Equivalente a Canónica Ing. Carlos Martin Ing. Carlos Martin Ing. Carlos Martin • En el conjunto del espacio de dos dimensiones de la figura 1.1, se tiene: • I = {O, A, B, C, D} • K = {XO, XA, XB, XC ,XD} XO (0, 0, 2, 2, 5) XA (2, 0, 6, 0, 3) XB (3.5, 1.5, 7.5, 0, 0) XC (1, 4, 0, 5, 0) XD (0, 2, 0, 4, 3) 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
Compartir