Bienvenido a ProgramaciónLineal.net un sitio enfocado exclusivamente a los contenidos de esta importante área de la Investigación de Operaciones. Se busca presentar los contenidos de una forma simple y didáctica, que permita al estudiante complementar su estudio formal de esta disciplina. Invitamos a los usuarios a plantear sus consultas y comentarios escribiendo a info@programacionlineal.net
SEP
2018
¿Qué es la Programación Lineal?
Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. 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.
Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos 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.
Supuestos Básicos de la Programación Lineal: Linealidad, Modelos Deterministas, Variables reales, No Negatividad.
APLICACIONES
1. Problema de la Dieta: (Stigler, 1945). Consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer requerimientos nutricionales. La cantidad de alimentos a considerar, sus características nutricionales y los costos de éstos, permiten obtener diferentes variantes de este tipo de modelos. Por ejemplo:
|
Leche
(lt)
|
Legumbre
(1 porción)
|
Naranjas
(unidad)
|
Requerimientos
Nutricionales
|
Niacina
|
3,2
|
4,9
|
0,8
|
13
|
Tiamina
|
1,12
|
1,3
|
0,19
|
15
|
Vitamina C
|
32
|
0
|
93
|
45
|
Costo
|
2
|
0,2
|
0,25
|
|
- X1: Litros de Leche utilizados en la Dieta
- X2: Porciones de Legumbres utilizadas en la Dieta
- X3: Unidades de Naranjas utilizadas en la Dieta
Variables de Decisión:
Función Objetivo: (Minimizar los Costos de la Dieta) Min 2X1 + 0,2X2 + 0,25X3
Restricciones: Satisfacer los requerimientos nutricionales
- Niacina: 3,2X1 + 4,9X2 + 0,8X3 >= 13
- Tiamina: 1,12X1 + 1,3X2 + 0,19X3 >=15
- Vitamina C: 32X1 + 0X2 + 93X3 >= 45
- No Negatividad: X1>=0; X2>=0; X3>=0
Compruebe utilizando nuestro Módulo de Resolución que la solución Óptima es X1=0, X2=11,4677, X3=0,483871, con Valor Óptimo V(P)=2,4145.
2. Problema de Dimensionamiento de Lotes: (Wagner y Whitin, 1958). Consiste en hallar una polìtica óptima de producción para satisfacer demandas fluctuantes en el tiempo, de modo de minimizar los costos de producción e inventario, considerando la disponibilidad de recursos escasos.
Considere que una fabrica puede elaborar hasta 150 unidades en cada uno de los 4 periodos en que se ha subdividido el horizonte de planificación y se tiene adicionalmente la siguiente información:
Periodos
|
Demandas
(unidades)
|
Costo Prod.
(US$/unidad)
|
Costo de Inventario
(US$/unidad)
|
1
|
130
|
6
|
2
|
2
|
80
|
4
|
1
|
3
|
125
|
8
|
2.5
|
4
|
195
|
9
|
3
|
Adicionalmente considere que se dispone de un Inventario Inicial de 15 unidades y no se acepta demanda pendiente o faltante, es decir, se debe satisfacer toda la demanda del período.
- Xt: Unidades elaboradas en el período t (Con t =1,2,3,4)
- It: Unidades en inventario al final del período t (Con t =1,2,3,4)
Variables de Decisión:
Función Objetivo: (Minimizar los Costos de Producción e Inventarios) Min 6X1 + 4X2 + 8X3 + 9X4 + 2I1 + 1I2 + 2,5I3+ 3I4
Restricciones:
- Capacidad de Producción por Período: Xt <= 150 (Con t =1,2,3,4)
- Satisfacer Demanda Período 1: X1 + I0 - I1 = 130 (I0 = 15)
- Satisfacer Demanda Período 2: X2 + I1 - I2 = 80
- Satisfacer Demanda Período 3: X3 + I2 - I3 = 125
- Satisfacer Demanda Período 4: X4 + I3 - I4 = 195
- No Negatividad: Xt >=0, It >=0
Solución Óptima utilizando Solver de MS Excel (Para ver una aplicación de esta herramienta ingrese AQUI): X1=115, X2=150, X3=100, X4=150, I1=0, I2=70, I3=45, I4=0. Valor Óptimo V(P)=3.622,5
3. Problema de Transporte: (Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).
PREGUNTAS FRECUENTES (FAQ)
Invitamos cordialmente a los usuarios del sitio al hacer llegar sus consultas ingresando a nuestro Formulario de Contacto:
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 j en 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.
NUESTROS REFERIDOS
A continuación se presenta un compendio de Links de Interés para el usuario.
Tutoriales de Programación Lineal
ENLACES PATROCINADOS
Links patrocinados que pueden resultar de interés para el usuario.
¿CÓMO UTILIZAR EL COMPLEMENTO SOLVER DE MS EXCEL?
Solver es un excelente complemento de MS Excel que permite la resolución de pequeños y medianos problemas de Programación Lineal. En la mayoría de las aplicaciones con fines estudiantiles es suficiente para resolver dichas instancias. Si usted requiere instalar este complemento puede revisar el siguiente tutorial de instalación de Solver. Ahora, veamos cómo funciona con un simple ejemplo:
MAX 10X + 16Y
S.A. 2X + 2Y <= 8
...... 1X + 2Y <= 6
..... .X>= 0, Y>= 0
PASO 1. Se ingresan los parámetros a una planilla de cálculo. Las celdas marcadas en amarillo corresponde a las "Celdas Cambiantes" o variables de decisión del modelo. La Celda C2 corresponde al Valor de la Función Objetivo que esta dada por: A2*A3 + C2*C3. Las Celdas C5 Y C6 almacenan el valor o lado izquierdo de las restricciones 1 y 2, quedando definidas como A2*A5 + B2*B5 y A2*A6 + B2*B6, respectivamente.
PASO 2. Se inicia la aplicación Solver y se cargan los datos de la planilla.
PASO 3. Una vez ingresados los parámetros se selecciona "Opciones". Una vez dentro de este menu se deben activar las opciones de "Adoptar modelo lineal" y "Asumir no negativos". Luego se selecciona "Aceptar" y luego "Resolver.
PASO 4. Si el modelo admite solución se obtienen los resultados. Se recomienda seleccionar los Informes que sugiere Solver para una mayor comprensión del modelo resuelto.
PASO 5. Los resultados son desplegados en las celdas cambiantes y se verifica el cumplimiento de las restricciones del problema. La Solución Óptima es X=2, Y=2 con Valor Óptimo V(P)=52. Adicionalmente, ambas restricciones se encuentran activas, es decir, se cumplen en igualdad.
PASO 6. Al seleccionar los Informes de Respuesta, en particular el "Informe de Sensibilidad" se obtiene información relevante sobre el modelo propuesto.
Respecto a las celdas cambiantes (variables de decisión) se incluye un intervalo de variación para los coeficientes en la función objetivo que mantienen la actual Solución Óptima. Por ejemplo C1 (Coeficiente que acompaña a X en la función objetivo, actualmente igual a 10) puede variar en el siguiente intervalo garantizando la actual Solución Óptima: {10 - 2, 10 + 6} = {8, 16}. De la misma forma el intervalo para C2 (Coeficiente que acompaña a Y en la función objetivo, actualmente igual a 16) es {10, 20}
En cuanto a las restricciones, el precio sombra de la restricción 1 es 2, el cual es válido siempre y cuando la variación en el lado derecho se encuentre en el intervalo {8 - 2, 8 + 4} = {6, 12}. De la misma forma, el precio sombra para la restricción 2 es 6, válido en el intervalo de variación del lado derecho entre {4, 8}.
Para ver una aplicación de Solver a una aplicación de mayor tamaño ingrese AQUI. Se recomienda adicionalmente revisar el siguiente Tutorial de Solver.