Programacion Lineal

SONIA I. CABRERA RODRÍGUEZ

APLICACIÓN DE LA

PROGRAMAC. LINEAL A LA AGRONOMÍA

ÍNDICE DE MATERIAS. PROGRAMACIÓN LINEAL 1. Optimización de proyectos 2. Simplificación del modelo matemático 3. Modelización 3.1. Modelo de transporte 3.2. Modelo de asignación 3.3. Modelo de ordenación de tareas 3.4. Modelo de la mochila 3.5. Ford-Fulkerson 3.6. Algoritmo de Klein 3.7. Caminos hamiltonianos decoste mínimo 3.8. Kruskal 3.9. PERT-CPM 4. Métodos para la resolución de problemas en programación lineal 4.1. Método de representación gráfica 4.2. Método simplex 4.3. Método de las dos fases 4.4. Cambios de variable 5. Análisis de sensibilidad 5.1.Costes relativos o sombra 5.2. Las variables de holgura 5.3. Inclusión de variables 5.4. Modificación de coeficientes de variable no básica enrestricciones 5.5. Añadir nuevas restricciones 6. Dualidad 6.1 Teorema del método dual 7. Algoritmo simplex dual
7.1. 8.

Análisis de sensibilidad.

Problemas de programación lineal.

1

SONIA I. CABRERA RODRÍGUEZ

APLICACIÓN DE LA

PROGRAMAC. LINEAL A LA AGRONOMÍA

PROGRAMACIÓN LINEAL A esta parte se le debe dar una especial importancia debido a que es la herramienta más importantedentro 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. 1.OPTIMIZACIÓN DE PROYECTOS. Esta parte de la investigación operativa se encarga del tratamiento de problemas mediante una modelizaciónmatemática del problema. Se trata de optimizar sistemas partiendo de unas premisas. En todo sistema existirá un conjunto de variables y las relaciones entre dichas variables. Ejemplo: Si hemos plantado trigo tendremos una variable X que será el número de kilos plantados por hectárea y una variable Y que será la lluvia. Los valores de la variable X los puedo controlar, pero no los de la variable Y, luego lavariable X será una variable interna de nuestro problema, y la variable Y será una variable externa. El conjunto de todas las variables internas X nos define el conjunto o dominio donde estará nuestra solución óptima. Este dominio estará definido por el conjunto de premisas de nuestro problema. Definiremos función objetivo (F.O.) a la representación matemática de aquello que queremos optimizar.Definiremos como conjunto de restricciones, a un conjunto de ecuaciones o inecuaciones matemáticas que representarán las limitaciones de nuestro problema. Las restricciones son de la forma: Σ ai * Xi ≤ bi Σ ai *Xi ≥ bi siendo ai y bi coeficientes, y Xi variables. La programación lineal lleva siempre implícita la restricción de que las variables de la función objetivo sean siempre mayores o igualesde cero. Para todo i: Xi ≥ 0.

2

SONIA I. CABRERA RODRÍGUEZ

APLICACIÓN DE LA

PROGRAMAC. LINEAL A LA AGRONOMÍA

Denominaremos como solución factible a aquella solución que cumple las condiciones planteadas por nuestro problema. Llamaremos solución óptima a aquella solución factible que nos optimice el objetivo de nuestro problema. La solución óptima no tiene por qué ser única. 2.SIMPLIFICACIÓN DEL MODELO MATEMÁTICO. Una vez establecido correctamente el modelo matemático de nuestro problema, deberemos tener en cuenta una serie de consideraciones que simplificarán nuestro trabajo: 1) Eliminación de restricciones redundantes. Si alguna restricción está incluida en otra, es lógico pensar en su anulación. Por ejemplo, si tenemos las siguientes restricciones: (X1/a11) + (X2/b11) ≤1(X1/a21) + (X2/b21) ≤1 Si se cumple: A11/a21>1 B11/b21>1 Gráficamente se representa en la figura1.

3

SONIA I. CABRERA RODRÍGUEZ

APLICACIÓN DE LA

PROGRAMAC. LINEAL A LA AGRONOMÍA

Nuestra F.O. trata un problema de maximización; es evidente que podremos eliminar la restricción. (X1/a11) + (X2/b11)≤1 2) Eliminación de restricciones obvias. Dado que la restricción de para todo i: Xi...