Programación lineal y simplex

ALGEBRA Y GEOMETRÍA ANALÍTICA PROGRAMACIÓN LINEAL Y MÉTODO SIMPLEX
Introducción La Programación Lineal es una técnica matemática muy utilizada en estudios de planificación, que trata de maximizar o minimizar un objetivo primario, sujeto a una serie de restricciones. Los objetivos más comunes pueden concretarse en dos: maximizar beneficios o rendimientos o bien, minimizar los costos, ya seamonetarios o de medios. Las restricciones más usuales son de carácter presupuestario, humanos, de tiempo, de energía, etc. Ejemplos: 1) Maximizar el rendimiento de los quirófanos de un hospital, sin disminuir la calidad del servicio o el tiempo necesario para cada operación y sin incrementar el personal médico. 2) Planificar un territorio, de modo que se minimice el costo de la obra, sujeto arestricciones como un número mínimo de viviendas, un máximo número de hectáreas dedicadas a espacios verdes, un mínimo de escuelas, etc. Concretemos un ejemplo: Supongamos que se tienen dos alimentos, A y B, cuyos costos respectivos son $200 y $100 por paquete. Dichos alimentos proporcionan dos nutrientes, M y N. Un paquete de alimento A proporciona 300 unidades del nutriente M y 4 del nutriente N. Elalimento B proporciona 100 unidades del nutriente M y 8 del nutriente N por paquete. Si las necesidades nutritivas son de 30 000 unidades como mínimo del nutriente M y 800 del nutriente N, ¿qué cantidad hay que comprar de cada alimento, para que la inversión sea mínima? Podemos organizar los datos en una tabla: Alimento A (x) Nutriente M Nutriente N Costo 300 4 $200 Alimento B (y) 100 8 $100 30 000800

Si x representa la cantidad de paquetes del alimento A e y la cantidad de paquetes del alimento B, podemos decir que el costo total estará representado por la expresión 200 ⋅ x + 100 ⋅ y . Dicho costo deberá minimizarse de acuerdo con las siguientes condiciones: Nutriente M: Nutriente N:

300 ⋅ x + 100 ⋅ y ≥ 30000 4 ⋅ x + 8 ⋅ y ≥ 800

Además, las variables x e y no pueden ser negativas,ya que se trata de cantidades de paquetes. Esto podemos expresarlo así: x ≥ 0 e y ≥ 0

Podemos “resumir” la situación matemáticamente así:

Prof. Estela Simonovich

1

ALGEBRA Y GEOMETRÍA ANALÍTICA PROGRAMACIÓN LINEAL Y MÉTODO SIMPLEX

Minimizar z = 200 ⋅ x + 100 ⋅ y

}función objetivo

⎧300 ⋅ x + 100 ⋅ y ≥ 30000 ⎪ ⎪4 ⋅ x + 8 ⋅ y ≥ 800 sujeto a ⎨ ⎪x ≥ 0 ⎪y ≥ 0 ⎩

⎫⎬restriccionesocondicionesestructurales ⎭ ⎫ ⎬restriccionesocondiciones de no negatividad ⎭

En general, podemos esquematizar de este modo cualquier problema de Programación Lineal: Optimizar (Maximizar o Minimizar) z = f (x1; x2; x3;........xn )

}función objetivo

⎧g1 (x1; x2; x3;.............; xn ) ≤ 0 ⎫ ⎪ ⎪ ⎪g2 (x1; x2; x3;.............; xn ) ≤ 0 ⎪ ⎪ ⎪........... ⎬restriccionesocondic..estructurales ⎪sujeto a ⎨ ⎪ ⎪........... ⎪ ⎪gm (x1; x2; x3;.............; xn ) ≤ 0 ⎪ ⎭ ⎪ ⎪x1; x2; x3;.............; xn ≥ 0 }restriccionesocondiciones de no negatividad ⎩
La solución del problema consiste en encontrar los valores x1; x2 ; x3;........xn que optimicen la función objetivo, al tiempo que verifiquen todas las restricciones, tanto las estructurales como las de no negatividad. Dicha solución se llamaSOLUCIÓN ÓPTIMA. Las variables ESTRUCTURALES O DE DECISIÓN. El conjunto de todas las soluciones posibles se llama CONJUNTO DE SOLUCIONES FACTIBLES o REGIÓN FACTIBLE. Dicho conjunto puede o no estar acotado. SOLUCIÓN GRÁFICA Si el problema de programación lineal es en dos variables, como en el ejemplo anterior, admite de manera sencilla una solución gráfica, ya que cada una de las restriccionesrepresenta un semiplano. Ejemplos: 1) Representa gráficamente la inecuación 2x − 3y ≥ 6 Transformamos la desigualdad en una igualdad, la cual representa la recta borde o frontera del semiplano a representar: 2x − 3y = 6 . Es cómodo, si la recta no contiene al origen de coordenadas, expresar dicha ecuación en forma segmentaria para su representación:

x1; x2; x3;........xn

se llaman VARIABLES

x...