Programacion Lineal Metodo Simplex

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