- Introducción
- Desarrollo
- Métodos de solución
- Aspectos fundamentales del método Simplex
- Bibliografía
- Problemas
1. Introducción
Mucha gente sitúa el desarrollo de la programación lineal entre los avances científicos más importantes de la mitad del siglo XX, y debemos estar de acuerdo con esta afirmación si tenemos en cuenta que su impacto desde 1950 ha sido extraordinario. Se han escrito decenas de libros de texto sobre la materia y los artículos publicados que describen aplicaciones importantes se cuentan ahora por cientos. De hecho, una proporción importante de todo el cálculo científico que se lleva a cabo en computadoras se dedica al uso de la programación lineal y a técnicas íntimamente relacionadas. (Esta proporción se estimó en un 25%, en un estudio de la IBM).
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.
En todos los problemas de Programación Lineal, el objetivo es la maximación o minimización de alguna cantidad.
2. Desarrollo
Contrucción de los Modelos de Programación Lineal
De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de Programación Lineal.
Requerimiento 1. Función objetivo. (F.O).
Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar.
Requerimiento 2. Restricciones y decisiones.
Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo.
Requerimiento 3. La F.O y las restricciones son lineales.
Deben utilizarse solamente ecuaciones lineales o desigualdades lineales.
Modelo standard de Programación Lineal
Optimizar Z = C1X1+ C1X2 +….+ Cn Xn).
Función objetivo.
Sujeta a a11X1+ a11X2 +…..+ a1nXn) ( b1
a21X1+ a21X2 +…..+ a2nXn) ( b1
Restricciones
am1X1+ am1X2 +…..+ amnXn) ( bm
Debiendo ser
X1 ( 0, X2 ( 0, ….. Xn ( 0
Donde :
Xj : variables de decisión, j = 1,2.., n.
n : número de variables.
m : número de restricciones.
aij , bi , cj constantes, i = 1,2.., m.
Pasos para la construcción del modelo
1) Definir las variables de decisión.
2) Definir el objetivo o meta en términos de las variables de decisión.
3) Definir las restricciones.
4) Restringir todas las variables para que sean no negativas.
Ejemplo: Taller de mantenimiento.
Un taller de mantenimiento fabrica dos tipos de piezas para la reparación de equipos fundamentales del proceso productivo. Estas piezas requieren un cierto tiempo de trabajo en cada una de las tres máquinas que las procesan. Este tiempo, así como la capacidad disponible (h) y la ganancia por cada pieza se muestran en el cuadro siguiente:
Se logra vender todo lo producido y se desea determinar la cantidad de piezas a fabricar que optimice la ganancia.
Formulando el modelo
X1 : Número de piezas del tipo A.
X2 : Número de piezas del tipo B.
Optimizando la ganancia (Z).
Max Z = 6X1 + 4X2
Sujeto a las restricciones:
2X1 + 2X2 ( 160 Fondo de tiempo de la máquina 1.
X1 + 2X2 ( 120 Fondo de tiempo de la máquina 2.
4X1 + 2X2 ( 280 Fondo de tiempo de la máquina 3.
Como ninguna variable implicada puede ser negativa.
X1 ( 0; X2 ( 0
3. Métodos de solución
El método simplex es un procedimiento iterativo que permite tender progresivamente hacia la solución óptima. Es un procedimiento sistemático y eficiente para encontrar y probar soluciones situadas en los vértices de optimalidad.
El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones, lo cual se logra añadiendo variables de holgura a cada inecuación del modelo, variables que nunca pueden ser negativas y tienen coeficiente 0 en la función objetivo. Para el modelo formulado anteriormente tenemos:
Z – 6X1 – 4X2 = 0
2X1 + 2X2 + s1 = 160
X1 + 2X2 + s2 = 120
4X1 + 2X2 + s3 = 280
Todas las variables son no negativas.
La solución básica inicial se obtiene seleccionando las variables de holgura como variables básicas, resultando conveniente disponer los valores como se muestran en la tabla siguiente:
Cada ecuación debe tener una única variable básica(VB), con el coeficiente unidad en la fila correspondiente.
Esta solución básica debe ser examinada para observar si puede ser mejorada. La presencia de coeficientes negativos en la FO indica que la solución básica puede ser mejorada, pues el valor de Z se incrementará.
Cuando no hay coeficientes negativos, significa que la solución es óptima.
Para encontrar una solución mejorada es necesario:
Elegir la variable que entra como la de mayor coeficiente negativo (X1)
| Página siguiente |