Programación Lineal

PROGRAMACIÓN LINEAL

La Programación Lineal (PL) es un procedimiento matemático para determinar la asignación óptima de recursos escasos. La PL es un procedimiento que encuentra su aplicación práctica en casi todas las facetas de los negocios, desde la publicidad hasta la planificación de la producción. Problemas de transporte, distribución, y planificación global de la producción son los objetos más comunes del análisis de PL.

La programación lineal aborda una clase de problemas de programación donde tanto la función objetivo a optimizar como todas las relaciones entre las variables correspondientes a los recursos son lineales. Cualquier problema de PL consta de una función objetivo y un conjunto de restricciones. En la mayoría de los casos, las restricciones provienen del entorno en el cual se trabaja para lograr un objetivo. Cuando se quiere lograr el objetivo deseado, se dará cuenta de que el entorno fija ciertas restricciones (es decir, dificultades, limitaciones) para cumplir con su deseo (vale decir, el objetivo).

Métodos de optimización lineal.

•Método simplex o primal.- es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior.

•Método gráfico.

•Método dual.

•Método de transporte.

•Método de asignación.

Modelos de programación.

Un modelo de programación lineal proporciona un método eficiente para determinar una decisión óptima, (o una estrategia óptima o un plan óptimo) escogida de un gran número de decisiones posibles.

Modelos de programación lineal.

Existen diversos modelos de programación dentro los cuales tenemos:

I.Modelo de la dieta

II.Modelo de asignacion de trabajo

III.Modelo de combinacion optima de bienes

IV.Modelo de calificacion de la produccion (planificacion de horarios)

V.Modelo de estudio de mercado

VI.Modelo de seleccion de medios publicitario

VII.Modelo de dimencionamiento de lotes

VIII.Modelo de problema de transporte

A continuación veremos un ejemplo de los modelos de programación:

El anterior ejemplo es un modelo conceptual el cual tiene omo objetivo maximar o minimizar,

El modelo matematico de dicho ejercicio es

Funcion a utilizar “Z”

Entonces la funcion objetivo seria: 

el anterior problema tiene restricciones de capacidad las cuales son:

De demanda: 

De positividad: 

FUENTE: http://www.slideshare.net/bkike/i-programacion-lineal

_________________________________________________________________________________

Programación Lineal

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.

Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) oModelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.

1. ¿Cómo puedo constatar que un problema de Programación Lineal tiene infinitas soluciones?
R: Un problema de PL tiene infinitas soluciones si en la tabla final del Método Simplex un costo reducido asociado a una variable no básica igual a cero.

2. Utilizando el Método Simplex de 2 Fases, ¿Cómo compruebo que el problema asociado es infactible?
R: Esto se comprueba si el valor de la función objetivo terminada la Fase I es distinto de cero.

3. ¿Puede existir una restricción activa con precio sombra asociado igual a cero?
R: Si. Sin embargo, este caso es más la excepción que la regla.

4. ¿Es incorrecto considerar como variable que entra a la base alguna variable no básica con costo reducido negativo, pero no el "más negativo" de todos? (Método Simplex)
R: No es incorrecto. En general, se utiliza como criterio seleccionar como variable entrante a la base aquella variable no básica con costo reducido más negativo, de modo de que en menos iteraciones podamos alcanzar el óptimo en caso que éste exista (rapidez de convergencia).

5. Utilizando el Método Simplex, ¿Cómo se puede detectar que un problema de Programación Lineal es no acotado?
R: Esta situación se detecta cuando al realizar el cálculo de la variable que deja la base, todos los elementos Ykj de la columna jen la tabla son negativos, para j el índice de una variable no básica con costo reducido negativo.

6. Si el problema Dual asociado a un modelo de Programación Lineal es no acotado, ¿Qué situación se verifica con el modelo Primal?
R: Si el modelo Dual es no acotado, entonces el Primal es infactible.

7. ¿Cómo se verifica que un problema lineal es infactible?
R: Si todas las entradas en la columna correspondiente a una variable no básica con costo reducido negativo son negativas o igual a cero.

8. ¿Qué significa que un modelo de programación lineal sea infactible?
R: Básicamente consiste en que no existen valores que puedan adoptar las variables de decisión de modo que se verifique el cumplimiento de todas las restricciones del modelo.

FUENTE: http://programacionlineal.net/programacion_lineal.html

_________________________________________________________________________________

PROGRAMACIÓN LINEAL

A esta parte se le debe dar una especial importancia debido a que es la herramienta más 

importante dentro del campo de la investigación operativa. Nos proporciona un tratamiento 

matemático de los problemas. 

En este capítulo vamos a plantear de forma abstracta los problemas mediante una 

modelización matemática que nos permitirá resolverlos de forma numérica. 

MODELIZACIÓN. 

La modelización de un problema consiste en representar matemáticamente dicho 

problema.

MÉTODO DE REPRESENTACIÓN GRÁFICA. 

 Consiste en representar las restricciones sobre unos ejes de coordenadas, para 

delimitar la región dónde se encuentran las soluciones factibles. 

 Las soluciones óptimas se encontrarán en el perímetro del polígono resultante. 

 Si nuestra función objetivo es una maximización y la línea que delimita nuestro 

dominio no es convexa, entonces nuestro problema, bajo estas condiciones, no tiene 

solución.

MÉTODO SIMPLEX. 

 Resuelve los problemas del tipo maximizar con restricciones menor o igual.

FUENTE: http://matematicas.uclm.es/ita-cr/web_matematicas/trabajos/248/Programacion_lineal.pdf