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
_________________________________________________________________________________
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).
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.
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.
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.
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.
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
