1
Programacin Lineal
La programacin lineal es muy usada en la microeconoma y la administracin de empresas, ya sea para aumentar al mximo los ingresos o reducir al mnimo los costos de un sistema de produccin.
A continuacin aplicacin.
se
muestra
un
ejemplo
de
Ventajas
Permite comprar un alto rango de soluciones alternativas y analizar sus consecuencias, requiriendo para ello poco tiempo. Indica al administrador como emplear eficazmente sus factores, seleccionandolos y distribuyendolos adecuadamente. Permite al administrador ser ms objetivo en sus decisiones.
Una orista sabe hacer solo 2 tipos distintos de arreglos orales (x1 y x2) para los cuales dispone de 3 tipos distintos de ores: rosas, tulipanes e hibiscos. Los requerimientos de ores para cada arreglo, la disponibilidad de ores y los precios de cada arreglo vienen dados por:
La Programacin Lineal es un procedimiento mediante el cual se resuelve un problema indeterminado, formulado a travs de ecuaciones lineales, optimizando la funcin objetivo, tambin lineal.
FLORES Rosas Tulipanes Hibiscos PRECIO
TIPO1
TIPO2 3 1 1 1 1 3 2000 1000
DISPONIBILIDAD 300 140 300 -
Construccin del Modelo (Planteamiento)
Consiste en optimizar (minimizar o maximizar) una funcin lineal, denominada funcin objetivo, de tal forma que las variables de dicha funcin estn sujetas a una serie de restricciones que expresamos mediante un modelo de inecuaciones lineales. La construccin se puede iniciar respondiendo a las siguientes preguntas: 1. Qu busca determinar el modelo? Cuales son las variables del problema? 2. Qu restricciones deben imponerse a las variables a fin de satisfacer las limitaciones del sistema? 3. Cul es el objetivo para determinar la solucin ptima de entre todos los valores factibles de las variables?
max z = 2000x1 + 1000x2 sujeto a 3x1 + x2 300 x1 + x2 140 x1 + 3x2 300 Solucin ptima z x1 zj-cj 1 0 x1 0 1 x2 0 0 x5 0 0
x1. x1 0
x2 0 0 1 0
x3 500 0.5 -0.5 1
x4 500 -0.5 1.5 -4
x5 Sol. 0 220000 0 80 0 60 1 40
Todo problema de optimizacin (primal), tiene un problema asociado (dual) con numerosas propiedades que los relacionan y nos permiten hacer un mejor anlisis de los problemas. Relaciones Primal-Dual Estas relaciones nos permiten pasar de un problema de primal a su dual en forma bastante algortmica, tanto para problemas de minimizacin como de maximizacin. MIN Restricciones = MAX Variables 0 No Restringida 0
Tabla ptima del Dual w 0 1 0 y1 0 1 0 y2 0 0 1 y3 40 -1 4 y4 80 -0.5 0.5 y5 60 0.5 -1.5 Sol 220000 500 500
Como se interpreta esto?
La orista vender rosas y tulipanes a un precio de $500 cada una y entregar como oferta los hibiscos gratis, pero esto solo si se vende todo como un paquete. Esto toma sentido pues si vende todas las rosas y tulipanes (dado que solo sabe hacer los arreglos orales descritos) no podr sacarle provecho alguno a los hibiscos La orista ofrecer por las ores una cantidad idntica a lo que ella ganara por ellas. Este valor viene dado nuevamente por los ptimos duales o precios sombras: y1=500 y2=500 y3=0 x1. x1 0
y1 y2
Resolviendo el sistema: y1=500, y2=500, y3=0, z(x) = w(y) = 220000
Anlisis de Sensibilidad
Cambios en B Suponiendo un nuevo modelo max z = 2000x1 + 1000x2 sujeto a 3x1 + x2 280 x1 + x2 120 x1 + 3x2 280 XB = | - | |- 3/2| |350| |100| = |125| |-25 |
MAX MIN Variables Restricciones 0 No Restringida = 0 Ahora tenemos el modelo dual mn w = 300y1 + 140y2 + 300y3 sujeto a 3y1 + y2 + y3 2000 y1 + y2 + 3y3 1000 y1, y2, y3 0 Esta formulacin resuelve el problema de un agente externo que quiere saber que precio unitario ofrecer por cada una de las ores si quiere comprarle todas las ores a la orista. As, y1, y2 y y3 son los precios asociados a las rosas, tulipanes e hibiscos.
El cambio de signo implica perdida de factibilidad y aplicacin del mtodo Dual Simplex Z= (3, 1) |80|= [300] |60|