programación lineal
DESCRIPTION
IOTRANSCRIPT
ESCUELA DE POSTGRADO
MAESTRÍA EN GESTIÓN EMPRESARIAL
INVESTIGACIÓN DE OPERACIONES
Mg. Denis Benavente Riveros
2007
Programación Lineal
PROGRAMACIÓN LINEAL OBJETIVOS
Fijar los requerimientos para establecer un modelo de programación lineal.
Representación y solución gráfica de un modelo de programación lineal bidimensional.
Uso del Método Simplex para planteamiento y resolución de problemas de PL multidimensional (más de 2 variables).
Ventajas del modelo de programación lineal:
* Obtención de una solución óptima única.
* Obtención de soluciones alternativas
* Consideración de Modelos no acotados.
* Consideración de Modelos no factibles.
.
PROGRAMACION LINEAL
Modelo matemático de optimización utilizado para la mejor asignación de recursos cuyo uso esté sometido a restricciones y se busque maximizar o minimizar una función objetivo.
Requerimientos para construir un modelo de Programación Lineal:
1. Función Objetivo: debe haber un objetivo o meta que la empresa desea alcanzar: Ejs. - Maximizar las utilidades
- Minimizar los costos- Maximizar el Nro. potencial de clientes esperados- Minimizar el tiempo total de fabricación.
3. La función objetivo y las Restricciones son lineales: la f.o. y las ecuaciones e inecuaciones que restringen
las decisiones deben ser LINEALES (las variables se afectan con exponente 1).
2. Restricciones y decisiones: los valores de las variables quedan limitados a cier-tos rangos y dentro del número de alternativas de
decisión debe haber una que permite hallar la función objetivo
I. Construcción de Modelos de Programación Lineal
Programación Lineal
Un modelo de programación lineal está compuesto de lo siguiente:* Un conjunto de variables de decisión
* Una función objetivo
* Un conjunto de restricciones
Un modelo de programación lineal busca maximizar o minimizar una función lineal, sujeta a un conjunto de restricciones lineales.
En conclusión:
PROGRAMACION LINEAL
Etapas para la construcción de modelos de Programación Lineal:
a. Plantear el modelo de PL: establecer las variables de decisiónb. Plantear el objetivo en términos de las variables de decisión; esto es la rela-
ción entre la f.o. y las restricciones. c. Definir las restricciones o limitaciones de uso para la asignación de los recur-
sos escasos. d. Restringir todas las variables a no negatividad.
II. Soluciones a los modelos de PL.a. Método Gráfico (Maximización y Minimización): sólo para dos variablesb. Método Simplex (Maximización y Minimización): dos o más variables.
PROGRAMACION LINEAL
Ejemplo 1:Aplicación del modelo Programación Lineal-Maximización
La FMA (Fábrica de Muebles Arequipa ) produce dos tipos de muebles de comedor: Virginia (V) y Mariana (M). Cada comedor requiere de una cantidad de tiempo diferente para la construcción y la pintura. La FMA desea determinar el número de unidades de cada tipo de comedor a producir diariamente de tal manera que las utilidades generadas sean máximas. Los requerimientos y capacidades de producción diarios se resumen en:
RECURSOS REQUERIDOS RECURSOS DISPONIBLESPARA PRODUCIR UNA UNIDAD Virginia (V) Mariana (M) ( Capacidad por Día)
Tiempo de Construcción C (Hrs.) 6 12 120
Tiempo de Pintado P ( Hrs.) 8 4 64
Margen de Contribución ( S/.) 200 240
PRODUCTO
Programación LinealSolución: Caso Fábrica de Muebles Tacna FMT
xV = 4 Juegos Modelo Virginia xM = 8 Juegos Modelo Mariana con una ganancia máxima de S/2720
La utilidad máxima ocurre en un vértice del conjunto de soluciones factibles.
22
20
18
16
14
12 P1 (0,10)
10 P4 (4,8)
8
6
4
2 P2 (0,0) P3 (8,0)
2 4 6 8 10 12 14 16 18 20 22
Depto. C.: 6xV + 12xM > 120
Depto. P.: 8xV + 4xM > 64
xV
xM
Z: 200xV + 240xM = 2720
Programación LinealEjemplo 2: Aplicación de la PL en Minimización
Artefactos Tacna S.A.
La empresa Artefactos Tacna S.A. (ATSA), tiene que planificar para el mes siguiente una nueva estrategia de publicidad para lanzar una nueva línea de TV Color. Para esto, desea lanzar publicidad por los siguientes medios:
a. TV Tacna b. Diario El Correo de TacnaPor estudios anteriores se sabe que:1) La publicidad por TV llega al 2% de familias de Ingresos Altos y al 3%
de las familias de Ingresos Medios. 2) La publicidad en periódico llega al 3% de las familias de Ingresos Altos y
al 6% de las familias de Ingresos Medios
La publicidad en periódico cuesta S/.500 por anuncio y por TV cuesta S/.2000 por spot. ATSA, desea obtener una presentación como mínimo al 36% de familias de Ingresos Altos y al 60% de familias de Ingresos Medios. ¿Cuántos anuncios por los dos medios o por uno solo debe contratar para optimizar los costos de publicidad?
Programación LinealSolución: Caso Artefactos Tacna S.A. (ATSA)
xt
22
20
18
16
14
12
10
8
6
4
2
2 4 6 8 10 12 14 16 xp
Seg. Medio.: 6xP + 3xT > 60
Seg. Alto.: 3xP + 2xT >36
P3 (0,20)
P2 (12,0)
P5 (4,12)
xP = 12 avisos en Diario xM = 0 avisos en TV con un costo mínimo de S/6000
Min C = 2000xt + 500xp
PROGRAMACION LINEAL
Ejemplo 3: Aplicación del modelo Programación LinealPROBLEMA: FABRICA DE JUGUETES GALAXIA.
• La F.J. Galaxia produce dos tipos de juguetes:
* Space Ray
* Zapper
• Los recursos están limitados a:
* 1200 Kgs. de plástico especial.
* 40 horas de producción semanalmente.
PROGRAMACION LINEAL
• Requerimientos de Marketing.
* La producción total no puede exceder de 800 docenas/sem.* El número de docenas de Space Rays no puede exceder al número de docenas de Zappers por más de 450.
• Requerimientos Tecnológicos.
* Space Rays requiere 2 Kgs. de plástico y 3 minutos de producción por docena.* Zappers requiere 1 Kg. de plástico y 4 minutos de producción por docena.
PROGRAMACION LINEAL
• Plan Actual de producción:
* Fabricar la mayor cantidad del producto que deje mejores ganancias, el cual corresponde a Space Ray ($8 de utilidad por docena).
* Usar la menor cantidad de recursos para producir Zappers, porque estos dejan una menor utilidad ($5 de utilidad por docena).
• El plan actual de producción consiste en fabricar:
Space Rays = 550 docenas x semana
Zappers = 100 docenas x semana
Utilidad = $4900 por semana
Queremos determinar si es el mejor Plan…!
Un buen gerente siempre buscará un esquema de
producción que incremente las ganancias
de su compañía.
EL MODELO DE PROGRAMACIÓN
LINEAL PROVEE UNA SOLUCIÓN MATEMÁTICAMENTE CALCULADA PARA SOLUCIONAR ESTE PROBLEMA, ESTO ES, OPTIMIZAR LA PRODUCCION Y VENTA DE LA MEZCLA DE PRODUCTOS.
PROGRAMACION LINEAL
Solución problema Juguetería Galaxia
• Variables de decisión
* X1 = Cantidad producida de Space Rays (en docenas por
semana).
* X2 = Cantidad producida de Zappers (en docenas por
semana).
• Función objetivo
* Maximizar la ganancia semanal.
PROGRAMACION LINEAL
• Modelo de Programación Lineal
Max Z = 8X1 + 5X2 (ganancia semanal)
Sujeto a:
2X1 + 1X2 <= 1200 (Cantidad de plástico)
3X1 + 4X2 <= 2400 (Tiempo de producción)
X1 + X2 <= 800 (Limite producción total)
X1 - X2 <= 450 (Producción en exceso)
Xj >= 0 , j= 1, 2. (Resultados positivos)
PROGRAMACION LINEAL
Conjunto de soluciones factibles para el modelo lineal.
• El conjunto de puntos que satisface todas las
restricciones del modelo es llamado:
REGION FACTIBLE
PROGRAMACION LINEAL
EL PROBLEMA PUEDE SER RESUELTO USANDO EL
METODO GRAFICO, PUES SE PUEDEN REPRESENTAR
TODAS LAS RESTRICCIONES, LA FUNCION OBJETIVO Y LOS
TRES TIPOS DE PUNTOS DE FACTIBILIDAD.
PROGRAMACION LINEAL
1200
600
Factible
Restricción del plástico: 2X1+X2<=1200
X2
No Factible
Horas deProducción3X1+4X2<=2400
Restricción del total de producción: X1+X2<=800
600
800
Restricción del exceso de producción:X1-X2<=450
• Tipos de puntos de factibilidad
Punto InferiorPunto Medio
Punto Extremo
X1
PROGRAMACION LINEAL
600
800
1200
400 600 800
X2
X1
Se toma un valor cercano al punto óptimo
FeasibleregionRegiónFactible
Región no factible
PROGRAMACION LINEAL
• Resumen de la solución óptima
Space Rays = 480 docenas
Zappers = 240 docenas
Ganancia = $5040
* Esta solución utiliza todas las materias primas (plástico) y
todas las horas de producción.
* La producción total son 720 docenas (no 800).
* La producción de Space Rays excede a la de Zappers por solo
240 docenas y no por 450.
PROGRAMACION LINEAL
• Soluciones óptimas y puntos extremos.
* Si un problema de programación lineal tiene una solución
óptima, entonces esta corresponde a un punto extremo.
• Múltiples soluciones óptimas.
* Cuando existen múltiples soluciones óptimas implica que la
función objetivo es una recta paralela a uno de los lados
de la región factible.
* Cualquier promedio ponderado de la solución óptima es
también una solución óptima.
PROGRAMACION LINEAL
Resumen de conclusiones de metodo gráfico de PL:
PROGRAMACION LINEAL
El Método Simplex, sus pasos......Adicione las variables de Holgura a
todas las desigualdades
Encontrar una Solución Básica Factible
¿Puede encontrar una solución Básica Factible “Mejor” una que aporte una utilidad más alta?
Resuelva para la nueva “mejor”
Solución Básica factible,
La solución básica factible es óptima
PARE
Paso 0 :
Paso 1 :
Paso 2 :
Sí No
Paso 3 :
Paso 4 :
PROGRAMACION LINEAL
Conceptos básicos para el método SIMPLEX:
1. Variable de Holgura, es una variable de artificio que permite completar el faltante para convertir una inecuación en ecuación cuando el primermiembro es menor o igual al segundo.
5x1 + 7x2 145
Al adicionarle la variable de holgura h1 es equivalente a:
5x1 + 7x2 + h1 = 145
2. Variables básicas y soluciones básicas factibles
- Variables básicas son las que tienen valor positivo y diferente de cero ( 0 ) - La solución factible es aquella que satisface las restricciones de no negatividad - Una solución básica es aquella que teniendo más variables que restricciones permi-
te un conjunto de variables extra iguales a cero (igual # de ecuaciones y variables) - Una solución básica factible es la solución básica que no tiene valores de variables
y que tiene a lo sumo el # de ecuaciones con variables positivas y el resto ceros. 3. Forma de los coeficientes separados: permite considerar sólo los coeficientes de
las variables de las restriccionesColumna Pivote: columna de coeficientes con la VNB que se escoge para ser VB Entrante.Fila Pivote: fila de coeficientes con la VB actual con valor +1 que se escoge para ser VB
# Pivote: coeficiente que está en la intersección de la columna y la fila pivote.Saliente.
PROGRAMACION LINEAL
Básica Z XV XM h1 h2 Valor Razón de Valor/ Coeficiente
Variable
Básica Z XV XM h1 h2 Valor Razón de Valor/ CoeficienteVariable
Básica Z XV XM h1 h2 Valor Razón de Valor/ Coeficiente
Variable
z
z
z
PROGRAMACION LINEAL
Básica Z XV XM h1 h2 Valor Razón de Valor/ Coeficiente
h1 0 6 12 1 0 = 120 120 / 12 = 10
h2 0 8 4 0 1 = 64 64 / 4 = 16
Z 1 -200 -240 0 0 = 0 0 /-240 = 0
Variable
Básica Z XV XM h1 h2 Valor Razón de Valor/ Coeficiente
XM 0 1/2 1 1/12 0 = 10 10 / 1/2 = 20
h2 0 6 0 - 1/3 1 = 24 24 / 6 = 4
Z 1 -80 0 20 0 = 2400 2400/-80 = -30
Variable
Básica Z XV XM h1 h2 Valor Razón de Valor/ Coeficiente
XM 0 0 1 1/9 -1/12 = 8 10 / 1/2 = 20
XV 0 1 0 - 1/18 1/6 = 4 24 / 6 = 4
Z 1 0 0 140/9 40/3 = 2720 2400/-80 = -30
Variable
f.p.
f.p.
c.p
c.p
n.p
n.p
PROGRAMACION LINEAL
INICIE EXCEL
CONSTRUYA O ABRA SU MODELO DE OPTIMIZACION
GRABE SU LIBRO
SELECCIONE “SOLVER” EN EL MENU DE HERRAMIENTAS
ESPECIFIQUE EN EL CUADRO DE DIALOGO DE SOLVER:
1. LA CELDA QUE VA A OPTIMIZAR 2. LAS CELDAS CAMBIANTES 3. LAS RESTRICCIONES
EN EL DIALOGO OPCIONES, HAGA CLICK EN “ASUMIR MODELO LINEAL” ENSEGUIDA EN EL BOTON “ACEPTAR”
HAGA CLICK EN EL BOTON “RESOLVER” PARA QUE EMPIECE LA OPTIMIZACION
LEA ATENTAMENTE EL MENSAJE DE TERMINACIÓN DE SOLVER
¿ENCONTRÓ SOLVER
LA SOLUCION ÓPTIMA?
1
HAGA CLICK EN “UTILIZAR LA SOLUCION DE SOLVER” Y LUEGO EN EL BOTÓN “ACEPTAR”
¿DESEA MODIFICAR
EL MODELO Y VOLVER A OPTIMIZAR?
GRABE EL MODELO FINAL Y SALGA DE EXCEL
1
MODIFIQUE EL MODELO
SI
NO
Si
NO
Análisis de sensibilidad para la solución óptima.
• ¿Es sensible la solución óptima a cambios en los parámetros de entrada?
• Posibles razones para responder la pregunta anterior:
* Los valores de los parámetros usados fueron los mejores
estimados.
* Medio ambiente por ser dinámico puede producir cambios.
* El análisis del “qué pasa si” puede proveer información
económica y operacional.
PROGRAMACION LINEAL
Análisis de sensibilidad de los coeficientes de la función objetivo
• Rango de optimalidad– La solución óptima permanecerá inalterable mientras:
• Un coeficiente de la función objetivo se encuentre dentro del rango de optimalidad.
• No haya cambios en ningún otro parámetro.
– El valor de la función objetivo cambiará si el coeficiente
multiplica una variable cuyo valor es distinto de cero.
PROGRAMACION LINEAL
• Los efectos de los cambios en un coeficiente de la función objetivo, sobre la solución óptima
600
800
1200 X2
X1
Max 8x1 + 5x2
Max 4x1 + 5x2Max 3.75x1 + 5x2 Max 2x1 + 5x2
400 600 800
PROGRAMACION LINEAL
• Los efectos del cambio de un coeficiente de la función objetivo, sobre la solución óptima
600
800
1200
400 600 800
X2
X1Max8x1 + 5x2
Max 3.75x1 + 5x2
Max8x1 + 5x2
Max 3.75 x1 + 5x2M
ax 10 x1 + 5x23.75
10
Rango de optimalidad
PROGRAMACION LINEAL
• Cambios Múltìples
• El rango de optimalidad es válido cuando un único coeficiente de la función objetivo cambia.
• Cuando cambia más de una variable se utiliza la regla del 100%.
PROGRAMACION LINEAL
• Regla del 100%
• Para cada aumento (disminución) en un coeficiente de la función objetivo calcular (y expresar como un porcentaje) la relación de cambio del coeficiente al máximo aumento posible (disminución) determinada por los límites del rango de optimalidad.
• Sumar todos los cambios de porcentaje. Si el total es menor que 100%, la solución óptima no cambiará. Si este total es mayor que 100%, la solución óptima puede cambiar.
PROGRAMACION LINEAL
• Reducción de costosLa reducción de costos de una variable a su cota inferior (comúnmente cero) implica que:
– Los coeficientes de la función objetivo deben cambiar antes que la variable pueda tomar un valor sobre la cota inferior.
– Con lo anterior la cantidad de ganancia óptima cambiará según las variables aumentadas desde la cota inferior.
• Holgura complementaria
– Existe holgura en la solución óptima, cuando cada variable está en su cota inferior o el costo reducido es 0.
PROGRAMACION LINEAL
Análisis de Sensibilidad del coeficiente del lado derecho
• Cualquier cambio en el lado derecho (bi) de una restricción activa cambiará la solución óptima.
• Cualquier cambio en el lado derecho de una restricción no activa que sea menor que la holgura o o el exceso, no produce ningún cambio en la solución óptima.
PROGRAMACION LINEAL
•Para el análisis de sensibilidad de la validez de los coeficiente del lado derecho nos interesa responder las
siguientes preguntas :
• ¿ Manteniendo todos los otros coeficientes , en cuánto cambiaría el valor óptimo de la función objetivo (por ejemplo, la ganancia) si el coeficiente del lado derecho de una restricción cambia en una unidad?
• ¿ Hasta cuántas unidades se puede agregar o disminuir para que la solución siga siendo válida?
PROGRAMACION LINEAL
1200
600
X2
Restricción materiales (plásticos)
FeasibleX1
600
800
Restricción del tiempo de producción
Ganancia máxima= 5040
2x1 + 1x2 <=1200
Nueva restricción materiales (plásticos)2x1 + 1x2 <=1350 Combinación de restricciones en la producción
Puntos extremos
PROGRAMACION LINEAL
• Interpretación correcta del precio sombra
• Los costos amortizados: El precio sombra, es el valor por una unidad extra del recurso, ya que el costo del recurso no es incluido en el cálculo de los coeficientes de la función objetivo.
• Los costos incluidos: El precio sombra es el valor superior por unidad del recurso, el costo del recurso se incluye en el cálculo del coeficiente de la función objetivo.
PROGRAMACION LINEAL
• El rango de factibilidad
• El conjunto de los coeficientes del lado derecho entregan el rango para que el mismo conjunto de restricciones determine el punto óptimo.
• Dentro del rango de factibilidad, los precios sombras permanecen constante; sin embargo, la solución óptima cambiará.
PROGRAMACION LINEAL
Otros cambios para optimizar la función objetivo
• La incorporación de una restricción.
• La eliminación de una restricción.
• La incorporación de un variable.
• La eliminación de un variable.
• Cambio en el lado izquierdo de los coeficientes.
PROGRAMACION LINEAL
Modelo sin solución óptima
• No factible: Ocurre cuando en el modelo no hay ningún punto de factible.
• No acotado: Ocurre cuando el objetivo puede crecer infinitamente (objetivo a maximizar).
PROGRAMACION LINEAL
Infactibilidad
Ningún punto se encuentra, simultáneamente, sobre la línea la línea y
1
2
3 1
2 3
PROGRAMACION LINEAL
Solución No Acotada
La región factible
Maximizar
La función objetivo
PROGRAMACION LINEAL
Dieta Marina
• Un problema de minimización del costo de la dieta:
• Mezcle dos porciones de los productos:
Texfoods, Calration.
• Minimice el costo total de la mezcla.
• Mantenga los requerimientos mínimos
de Vitamina A, Vitamina D, y hierro.
PROGRAMACION LINEAL
Variables de decisión:x1 (X2) - - La cantidad de Texfoods (Calration) que se usó en
cada porción (cada 2 onzas).• El modelo
minimizar 0.60X1 + 0.50X2
sujeto a
20X1 + 50X2 100
25X1 + 25X2 100 Vitamina D
50X1 + 10X2 100 hierro
X1, X2 0
Costo por 2 oz.
% Vitamina A por 2 oz.
% requerido
PROGRAMACION LINEAL
La solución gráfica
5
4
2
2 44 5
Región factibleRegión factible
Restricción de vitamina D
Restricción de vitamina A
Restricción de hierro
PROGRAMACION LINEAL
• Resumen de la solución óptima
• Producto Texfood = repartir 1.5 (= 3 onzas)
• Producto Calration = repartir 2.5 (= 5 onzas)
• Costo =$ 2.15 por porción servida.
• El requisito mínimo para la Vitamina D y el hierro no se encuentran en superávit.
• La mezcla provee 155% del requerimiento para Vitamina A.
PROGRAMACION LINEAL
Solución para problemas lineales con muchas variables de decisión usando el computador
• Los paquetes de programas lineales resuelven modelos lineales con gran cantidad de variables y restricciones.
• La mayoría de los software usan la técnica algebraica llamada algoritmo Simplex.
• Los paquetes incluyen:
• El criterio de la función objetivo (Max. o Min.)
• El tipo de cada restricción: .
• Los coeficientes reales para el problema.
, ,
PROGRAMACION LINEAL
•La solución generada por un software de programación lineal incluye:
• Los valores óptimos de la función objetivo.
• Los valores óptimos de las variables de decisión.
• La minimización del costo para los coeficientes de la función objetivo.
• Los rangos de optimización para los coeficientes de la función objetivo.
• La cantidad de holgura o exceso sobre cada restricción.
• Los precios sombra (o dual) para las restricciones.
• Los rangos de factibilidad para el coeficiente del lado derecho.
PROGRAMACION LINEAL
WINQSB datos de entrada WINQSB datos de entrada para el problema de las para el problema de las industrias galaxiaindustrias galaxia
Las variables y los nombres de las restricciones pueden ser cambiados aquí. Las variables son
restringidas a >=0 Ningún límite superior
Click pararesolver
FINALIZAMOS……………
Gracias