Guia Practica Programacion Lineal

UNIVERSIDAD NACIONAL DE ANCASH “SANTIAGO ANTÚNEZ DE MAYOLO” FACULTAD DE CIENCIAS ECONÓMICAS, ADMINISTRATIVAS Y CONTABLES
MÉTODOS CUANTITATIVOS PARA LA TOMA DE DECISIONES

GUÍA PARA PRÁCTICA

Lic. Adm. RICARDO TOLEDO QUIÑONES

HUARAZ – PERÚ - ABRIL - 2 003

Universidad Nacional “Santiago Antúnez de Mayolo” Facultad de Ciencias Económicas, Administrativas y Contables

PROGRAMACIÓNLINEAL 1. CONCEPTO

Es una técnica matemática que permite asignar recursos limitados tales como dinero, personal, materiales, equipos, espacio, tiempo, etc. Un problema de Programación Lineal (PL), es un problema de optimización, para lo cual se efectúa lo siguiente: a) b) c) Se trata de maximizar (ejemplo beneficios) o minimizar (ejemplo costos) una función lineal de variables de decisión. Lafunción que se pretende maximizar o minimizar se llama función objetivo. 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 (relacionada con el signo = ) o una desigualdad lineal (relacionada con el signo =). Hay una restricción de signo para cada variable. Para cualquier variable Xn la restricción de signoespecifica que Xn tiene que ser no negativo Xn >= 0 o que Xn puede ser una variable sin restricción de signo. Para los casos a estudiar sólo se utilizará la restricción de no negatividad.

La programación lineal se ha usado para resolver problemas de optimización en industrias tan diversas como la banca, la educación la silvicultura, la agricultura, el petróleo el transporte, etc. En una Encuesta enlos EE.UU., se estableció que el 85% de las Empresas utilizaron ésta técnica. Su uso para optimizar la mezcla de gasolinas en la Texaco, le significó un ahorro de más de 30 millones de dólares anuales, en el diseño de las rondas de los oficiales de policía de San Francisco se logró un ahorro de 11 millones de dólares anuales, el remplazo de equipo en Phillips Petroleum le significó un ahorro de 90mil dólares anuales. 2. a) b) METODOS DE RESOLUCION DE PROBLEMAS DE PROGRAMACION LINEAL Método gráfico.- Utilizado cuando el modelo sólo contiene dos variables de decisión. Algoritmo Simplex.- Utilizado cuando el problema tiene muchas variables. El algoritmo de resolución fue desarrollado por George Dantzig en 1947. Algoritmo es un conjunto de procedimientos que, cuando se siguen en formaordenada, proporcionan una solución óptima a un problema. Algoritmo Karmarkar.- Utilizado cuando el problema tiene muchas variables. Ha sido desarrollado en los años 80 y paulatinamente está cobrando importancia. Si se desea comparar el Algoritmo Simplex y Algoritmo Karmarkar se ha demostrado que para problemas grandes, el método Karmarkar puede ser hasta 50 veces más rápido que el algoritmo simplex, suimportancia radica en que actualmente los diseños de los problemas exigen un elevado número de variables, el Military Airlift Command ha utilizado el método de Karmarkar para determinar cuántas veces hay que volar diferentes rutas y con qué avión, el modelo tenía 150 000 variables y 12 000 restricciones y se resolvió en una hora con una computadora. Con una estructura similar, con 36 000 variablesy 10 000

c)

Elaboración: Ricardo Toledo Q.

Universidad Nacional “Santiago Antúnez de Mayolo” Facultad de Ciencias Económicas, Administrativas y Contables

d)

restricciones, se resolvió mediante el método simplex, en 4 horas con una computadora. Computadora.- Existen diversos programas de computadora como son el Lindo, LPT1, Tora, etc. En las hojas de Cálculo como el Qpro y el Excelse posee una alta eficacia para resolverlos. PLANTEAMIENTO DE PROBLEMAS

3.

Para resolver un problema de PL el orden más conveniente para plantear el problema es seguir el orden siguiente: a)b)c)d)e)f)Sintetizar los datos del problema en un Cuadro. Definir verbalmente lo que se desea alcanzar. Definir las Variables (incógnitas). Definir la Función Objetivo (lo que se desea alcanzar, un...