Definicion de programacion lineal

TRABAJO DE INVESTIGACION No 2

DEFINICION DE PROGRAMACION LINEAL

PROGRAMACION LINEAL

Es un enfoque de solución de problemas elaborado para ayudar a tomar decisiones. Es un modelo matemático con una función objetivo lineal.

La programación lineal da respuesta a situaciones en las que se exige maximizar o minimizar funciones que se encuentran sujetas a determinadas limitaciones, que llamaremos restricciones. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

UTILIDAD Y SURGIMIENTO

A pesar de que la programación lineal se empezó a estudiar desde finales del S.XIX no fue hasta mediados del presente siglo en que tuvo auge como técnica matemática aplicable a los problemas de la empresa.

El Dr. G. Damtzing desarrolló el método simplex y con ello hizo posible la solución de grandes problemas modelados con programación lineal que solo quedaban en la situación de estudios. Paralelamente a la invención de este método a partir de mediados del siglo se desarrollo la computación digital y se pudo tener resultados óptimos a los problemas estudiados que se quedaron como modelos.

La programación lineal es actualmente la técnica matemática utilizada mas actualmente gracias a que el algoritmo simplex es muy eficiente y al desarrollo de la computación.

Esta tiene diversas aplicaciones y ha sido aplicado exitosamente en las industrias petrolera, automotriz, química, forestal, metalúrgica, agrícola, militar, etc. Incluso en mercadotecnia, se le ha empleado para seleccionar los medios de publicidad y los canales adecuados de distribución.

TERMINOLOGIA DE PROGRAMACION LINEAL

Para comprender lo que es la Programación Lineal es importante entender los siguientes conceptos básicos:

Variables de Decisión: Con las variables de decisión nos referimos al conjunto de variables cuya magnitud deseamos determinar resolviendo el modelo de programación lineal.

Restricciones: Están constituidas por el conjunto de desigualdades que limitan los valores que puedan tomar las variables de decisión en la solución.

Función Objetivo: Es la función matemática que relaciona las variables de decisión.

Linealidad: Se refiere a que las relaciones entre las variables, tanto en la función objetivo como en las restricciones deben ser lineales.

Desigualdades: Las desigualdades utilizadas para representar las restricciones deben ser cerradas o flexibles, es decir, menor - igual (<=) o mayor – igual (>=). No se permiten desigualdades de los tipos menor- estrictamente o mayor – estrictamente, o abiertas.

Condición de no – negatividad: En la programación lineal las variables de decisión sólo pueden tomar valores de cero a positivos. No se permiten valores negativos.

MODELO ESTANDAR

El modelo se define generalmente como:

max⁡(min)z=c_1 x_1+c_2 x_2+⋯c_n x_n

sujeto a :

a_11 x_1+a_12 x_2+⋯a_1n x_n (≤,=o ≥) b_1

a_21 x_1+a_22 x_2+⋯a_2n x_n (≤,=o ≥) b_2

a_m1 x_1+a_m2 x_2+⋯a_mn x_n (≤,=o ≥) b_m

x_1,x_2,…x_n ≥0

La forma canonica de un modelo de programcion lineal es :

max⁡〖z= ∑_(j=1)^n▒〖c_j x_j 〗〗

⁡〖 ∑_(j=1)^n▒〖a_ij x_j 〗〗≤ b_i,para i=1,…,m

x_(j )≥0 para j=1,…,n

Para que un modelo de PL sea válido, debe cumplir las propiedades siguientes:

Proporcionalidad.-Significa que la contribución al valor de la función objetivo y el consumo o requerimiento de los recursos utilizados, son proporcionales al valor de cada variable de decisión. Así el término 4X1 es proporcional, porque contribuye al valor de la función Z con 4, 8, 12, etc. para los valores 1, 2, 3, etc., respectivamente, de X1. Se puede observar el aumento constante y proporcional de 4 conforme crece el valor de X1. En contraste, el término no lineal 4X12, contribuye con 4, 16, 36, etc., para los mismos valores 1, 2, 3, etc., respectivamente, de la variable X1; Aquí se observa que el aumento en la contribución no es constante y por lo tanto no hay proporcionalidad.

Aditividad.- Significa que se puede valorar la función objetivo Z, así como también los recursos utilizados, sumando las contribuciones de cada uno de los términos que intervienen en la función Z y en las restricciones.

Divisibilidad.- Significa que las variables de decisión son continuas y por lo tanto son aceptados valores no enteros para ellas. La hipótesis de divisibilidad más la restricción de no negatividad, significa que las variables de decisión pueden tener cualquier valor que sea positivo o por lo menos igual a cero.

Certidumbre.- Significa que los parámetros o constantes son estimados con certeza, o sea, no interviene una función de probabilidad para obtenerlos

El modelo de programación lineal es un caso especial de la programación matemática, pues debe cumplir que, tanto la función objetivo como todas las funciones de restricción, sean lineales.

METODOS DE SOLUCION

METODO GRAFICO

El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación Lineal en dos variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución, es que ésta se encontrará en el vértice o frontera (tramo) del dominio de puntos factibles. Es decir, si luego de graficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor" candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar cual es el mejor candidato dependiendo si estamos maximizando o minimizando).

CONCEPTO

Representación en un sistema de ejes coordenados de las zonas del plano definidas por las inecuaciones de restricción para determinar una figura que satisfaga todas y cada una de ellas.

VENTAJAS

a. Conocimiento de los conceptos básicos de la programación Lineal.

b. Facilita la comprensión de los métodos más complejos.

DESVENTAJAS

Sólo sirve para problemas con dos variables de decisión.

ETAPAS

a. Formulación del problema.

b. Trazado del gráfico.

c. Obtención de la solución óptima.

d. Análisis gráfico de sensibilidad.

METODO ANALITICO

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El método símplex explota estas tres propiedades al examinar nada más unas cuantas soluciones factibles en vértices prometedores y al detenerse en cuanto una de ellas pasa la prueba de optimalidad. En particular, se traslada repetidamente (en forma iterativa) de una solución factible en un vértice a otra, adyacente y mejor. Esto se puede realizar en forma muy eficiente hasta que la solución actual no tiene soluciones factibles en vértices adyacentes que sean mejores. Este procedimiento se resume como sigue:

Bosquejo del método símplex:

1. Paso inicial: inicio en una solución factible en un vértice.

2. Paso iterativo: traslado a una mejor solución factible en un vértice adyacente. (Repítase este paso las veces que sea necesario).

3. Prueba de optimalidad: la solución factible en un vértice es óptima cuando ninguna de las soluciones en vértices adyacentes a ella sean mejores.

CASOS ESPECIALES

Óptima Única: este tipo de solución es la más común una vez que el modelo ha sido formulado como un problema real de programación lineal. Se da cuando sólo existe un punto extremo del conjunto de soluciones factibles que hace posible encontrar el valor óptimo de Z.

Optima Múltiple (Alterna): esto ocurre cuando la recta de la función objetivo es paralela a alguna de las restricciones; entonces todos los puntos que están sobre la recta son soluciones óptimas del modelo. Como una recta tiene un número infinito de puntos, hemos encontrado un número infinito de soluciones óptimas equivalentes. De otra manera se dice que el modelo tiene soluciones óptimas alternativas.

No Acotada (ilimitada o Indeterminada): se presenta cuando una o más variables y la función objetivo toman un valor ilimitado, cumpliendo con las restricciones estructurales. Cuando se obtiene solución ilimitada es debido a una de las siguientes causas:

a. Omisión de una o más restricciones

b. Fallas en la formulación

c. Errores en el valor de los parámetros

Lo que indica que ningún problema real de programación lineal tiene este tipo de solución y cuando se presenta es porque se ha cometido alguno de los errores descritos.

Infactible (sin solución): esto ocurre cuando no pueden encontrarse soluciones que, además de cumplir con las restricciones estructurales, cumplan con la condición de no negatividad de las variables (cuando en el tablero

...