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

...