PROGRAMACION_LINEAL_La_programacion_line

Vista previa del material en texto

PROGRAMACION LINEAL
La programación lineal (PL) 
Es una técnica de modelado matemático diseñada para optimizar el empleo de recursos limitados. Implica maximizar o minimizar una función lineal de múltiples variables sujeta a una serie de restricciones, expresadas por inecuaciones y/o ecuaciones lineales. Un problema es lineal porque su función objetivo y restricciones son lineales, es decir, cumplen con las propiedades de proporcionalidad y aditividad. 
En economía y finanzas, es una técnica matemática utilizada en modelos informáticos (simulación) para encontrar la mejor solución posible en la asignación de recursos limitados (energía, máquinas, materiales, dinero, personal, espacio, tiempo, etc) para lograr el máximo beneficio o costo mínimo. Sin embargo, es aplicable únicamente cuando todas las relaciones son lineales (ver relación lineal), y puede acomodar solamente una clase limitada de funciones de costes.
La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos 
El modelo de PL incluye, al igual que otros modelos dentro de la Investigación de Operaciones, tres elementos básicos:
– Variables (que tratamos de determinar)
– Objetivo (que tratamos de optimizar)
– Restricciones (que necesitamos cumplir)
Función objetivo
En cualquier PPL, la decisión a tomar es como maximizar (normalmente el beneficio) o minimizar (el costo) de alguna función de las variables de decisión. Esta función a maximizar o minimizar se llama función objetivo, Una función objetivo puede ser el resultado de un intento de expresar un objetivo de negocio en términos matemáticos para su uso en el análisis de toma de decisiones, operaciones, estudios de investigación o de optimización. es una función lineal de varias variables:
f(x,y) = ax + by.
Variables:
 Con las variables de decisión nos referimos al conjunto de variables cuya magnitud deseamos determinar resolviendo el modelo de programación lineal. Representan los elementos s del sistema a modelar r que son controlables por el decisor. En los modelos lineales continuos estas variables toman como valores números reales y se representan por letras con subíndices como se acostumbra a hacer con las variables matemáticas, o literales alusivos a su significado: peso, valor, etc. Son las entradas controlables en el una decisión.
Restricciones
La función objetivo está sujeta a una serie de restricciones, estás desigualdades que limitan los posibles valores de las variables de decisión. En este problema las restricciones vienen dadas por la disponibilidad de horas de minado y concentración y por la demanda de cc. expresadas por inecuaciones lineales. Las restricciones pueden ser de la forma:
x ≥ 0 , y ≥ 0
a1x + b1y ≤ c1
a2x + b2y ≤ c2
... ... ...
anx + bny ≤ cn
Cada desigualdad del sistema de restricciones determina un semiplano.
Región Factible
El conjunto intersección, de todos los semiplanos formados por las restricciones, determina un recinto, acotado o no, que recibe el nombre de regió de validez o zona de soluciones factibles.
Solución óptima
El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso).
}Ejemplo:
MINA DEL PACIFICO S.R. L., manufactura dos tipos de concentrados: Pb y Zn.
Cada Tm de CC de Pb:
· Produce un beneficio neto de 3 €.
· Requiere 2 horas de minado.
· Requiere 1 hora de trabajo de concentración.
Cada Tm de cc de Zn:
· Produce un beneficio neto de 2 €.
· Requiere 1 hora de minado.
· Requiere 1 hora trabajo de concentración.
Cada semana MP puede disponer de:
· Todo el material que necesite.
· Solamente 100 horas de minado
· Solamente 80 horas de concentración. También:
· La demanda de cc de Zn puede ser cualquiera (sin límite).
· La demanda de cc de cc de Pb es como mucho 40.
MDP quiere maximizar sus beneficios. ¿Cuántas TM de cc de Pb y cuántas Tm de cc de Zn debe fabricar?
Este problema es un ejemplo típico de un problema de programación lineal (PPL).
Variables de Decisión
x = nº de Tm de cc de Pb producidos a la semana
y = nº de Tm de cc de Zn producidos a la semana
Función Objetivo
 El objetivo de MDP es elegir valores de x e y para maximizar 3x + 2y. Usaremos la variable z para denotar el valor de la función objetivo. La función objetivo de MDP es:
Restricciones
Cuando x e y crecen, la función objetivo de MDP también crece. Pero no puede crecer indefinidamente porque, para MDP, los valores de x e y están limitados por las siguientes tres restricciones:
Restricción 1: No más de 100 horas de tiempo de minado pueden ser usadas
Restricción 2: No más de 80 horas de tiempo de concentración pueden ser usadas.
Restricción 3: Limitación de demanda, no deben fabricarse más de 40 tm de cc 
Estas tres restricciones pueden expresarse matemáticamente por las siguientes desigualdades:
Restricción 3: 2 x + y ≤ 100
Restricción 2: x + y ≤ 80
Restricción 1: x ≤ 40
Además, tenemos las restricciones de signo: x ≥ 0 e y ≥ 0.
Variable de decisión 
x = nº de Tm de cc de Pb producidos a la semana
y = nº de Tm de cc de Zn producidos a la semana
3x + 2y = función objeto MAX
2x + 1y≤ 100 minado
X + y ≤ 80
≤ 40
X ≥ 0 (restricción de signo) y y≥ 0 (restricción de signo)
Formulación Matematica
Para el problema de MDP, combinando las restricciones de signo x ≥ 0 e y ≥ 0 con la función objetivo y las restricciones, tenemos el siguiente modelo de optimización:
Región Factible 
de un PPL es el conjunto de todos los puntos que satisfacen todas las restricciones. Es la región del plano delimitada por el sistema de desigualdades que forman las restricciones.
x = 40 e y = 20 está en la región factible porque satisfacen todas las restricciones de MDP.
Sin embargo, x = 15, y = 70 no está en la región factible porque este punto no satisface la restricción de Concentración
[15 + 70 > 80].
Solucion Optima
Para un problema de maximización, una solución óptima es un punto en la región factible en el cual la función objetivo tiene un valor máximo. Para un problema de minimización, una solución óptima es un punto en la región factible en el cual la función objetivo tiene un valor mínimo.
La mayoría de PPL tienen solamente una solución óptima. Sin embargo, algunos PPL no tienen solución óptima, y otros PPL tienen un número infinito de soluciones.
Más adelante veremos que la solución del PPL de MDP es x = 20 e y = 60. Esta solución da un valor.
Se puede demostrar que la solución óptima de un PPL está siempre en la frontera de la región factible, en un vértice (si la solución es única) o en un segmento entre dos vértices contiguos (si hay infinitas soluciones)
 la función objetivo de]:
Cuando decimos que x = 20 e y = 60 es la solución óptima, estamos diciendo que, en ningún punto en la región factible, la función objetivo tiene un valor (beneficio) superior a 180.
· Cualquier PPL con sólo dos variables puede resolverse gráficamente.
· Por ejemplo, para representar gráficamente la primera restricción, 2x + y ≤ 100 : Dibujamos la recta 2x + y = 100
· Elegimos el semiplano que cumple la desigualdad: el punto (0, 0) la cumple
(2·0 + 0 ≤ 100), así que tomamos el semiplano que lo contiene.
Dibujar la Región factible
Puesto que el PPL de MDP tiene dos variables, se puede resolver gráficamente. La región factible es el conjunto de todos los puntos que satisfacen las restricciones:
Dibujar Región Factible
Dibujar Región Factible
Dibujar Región Factible
Dibujar Región Factible
La intersección de todosestos semiplanos (restricciones) nos da la región factible
Vértices de la Región Factible
Restricciones
2 x + y ≤ 100 
x + y ≤ 80
x ≤ 40
x ≥ 0
y ≥ 0
 La región factible (al estar limitada por rectas) es un polígono. En esta caso, el polígono ABCDE.
Como la solución óptima está en alguno de los vértices (A, B, C, D o E) de la región factible, calculamos esos vértices.
Vértices de Región Factible
Resolución Analítica
La solución óptima es:
X:=20 TM de Cc de Pb
Y=60 TM de Cc de Zn
Z=180€ de beneficio
Resolución Analítica
Resolución Analítica
Hemos identificado la región factible para el problema de CDP y buscado la solución óptima, la cual era el punto en la región factible con el mayor valor posible de z.
Recuerda que:
· La región factible en cualquier PPL está limitada por segmentos (es un polígono, acotado o no).
· La región factible de cualquier PPL tiene solamente un número finito de vértices.
Cualquier PPL que tenga solución óptima tiene un vértice que es óptimo
	 15
image1.png
image2.png
image3.png
image4.png
image5.png
image6.png
image7.png
image8.png
image9.png
image10.png
image11.png
image12.png
image13.png
image14.png
image15.png
image16.png
image17.png
image18.png
image19.png