Manual Investigacion de Operaciones 2013
Transcript of Manual Investigacion de Operaciones 2013
[email protected] Facebook: Giovanny Rodriguez 1
Material de Apoyo y Consulta
MANUAL DE INVESTIGACIÓN DE OPERACIONES
(Versión Preliminar para Revisión)
Ing. Giovanny Rodríguez Martínez
Bogotá, D.C. Mayo de 2013
[email protected] Facebook: Giovanny Rodriguez 2
CONTENIDO
Página
1. Definiciones básicas de programación lineal …….3
2. Aplicaciones y modelos lineales……………………..6
3. Solución por método gráfico…………………………20
4. Solución por Solver……………………………………23
5. Solución por el método Simplex…………………….28
6. Dualidad ……………………………………………..…38
7. Análisis de sensibilidad……………………………….46
8. Modelos de Asignación y Transporte……………….48
9. Programación Entera …………………………………63
[email protected] Facebook: Giovanny Rodriguez 3
DEFINICIONES BÁSICAS PROGRAMACION LINEAL
La programación lineal satisface un tipo especial de problema, uno en el cual todas las relaciones entre las variables son lineales, tanto en las restricciones como en la función objetivo.
CARACTERÍSTICAS
- La función objetivo maximiza o minimiza.
Maximiza = Utilidades/recursos
Minimiza = Costos/recursos
Se llama solución factible a la solución que satisfaga la condición de no negatividad.
PAUTAS PARA UN BUEN PLANTEAMIENTO DE UN MODELO DE PROGRAMACION LINEAL
Formule cada restricción con sus propias palabras, teniendo en cuenta si es de la signo >= (mayor o igual que, al menos, por lo menos, como mínimo), o =< (menor o igual que, no mayor que, como máximo), o = (igual).
Exprese las restricciones de forma que en ambos lados del símbolo se manejen bien sea horas, pesos, kilogramos, etc.
Formule el modelo con la rapidez que le sea posible no intente colocar mas datos de los que le piden, puede llegar a confundir o a desviar el objetivo
ANÁLISIS DE PROBLEMAS
Metodología de Investigación de Operaciones
Definir el problema
Desarrollar un modelo matemático
Resolución del modelo
Validación de la solución
Poner en práctica y supervisar la solución
[email protected] Facebook: Giovanny Rodriguez 4
PROGRAMACION LINEAL “ELEMENTOS”
Variables = cambios
Restricciones =limite ≤ o ≥
Función objetivo = Max o Min Z = C1X1 + C2X2…..+ CnXn
Sujeto a = a11x1 + aijxj ………≤ ó ≥ b1
ai 1 + aijxj ………≤ó ≥ bi
x1, x2 ≥ 0
APLICACIONES DE LA PROGRAMACION LINEAL
Finanzas: El problema del inversor podría ser un problema de selección del mix de su cartera de inversiones. En general, la variedad de carteras puede ser mucho mayor que lo que indica el ejemplo y se pueden agregar muchas más restricciones distintas. Otro problema de decisión implica determinar la combinación de métodos de financiación para una cantidad de productos cuando existe más de un método de financiación disponible. El objetivo puede ser maximizar las ganancias totales cuando las ganancias de un producto determinado dependen del método de financiación.
Administración de Producción y Operaciones: En las industrias de proceso, una materia prima en particular puede transformarse en una gran variedad de productos. Por ejemplo, en la industria petrolera, el crudo puede refinarse para producir nafta, kerosene, aceite. Según el margen de ganancia actual de cada producto, el problema es determinar la cantidad que se debería fabricar de cada producto. Esta decisión está sujeta a numerosas restricciones tales como límites de las capacidades de diversas operaciones de refinado, disponibilidad de materia prima, demandas de cada producto y políticas gubernamentales con respecto a la fabricación de determinados productos. En la industria de productos químicos y de procesamiento de alimentos existen problemas similares.
[email protected] Facebook: Giovanny Rodriguez 5
Recursos Humanos: Los problemas de planificación de personal también se pueden analizar con programación lineal. Por ejemplo, en la industria telefónica, la demanda de servicios de personal de instalación / reparación son estacionales. El problema es determinar la cantidad de personal de instalación / reparación y reparación de líneas que debemos tener incorporada en la fuerza laboral por cada mes a fin de minimizar los costos totales de contratación, despido, horas extras y salarios en horas ordinarias. El conjunto de restricciones comprende restricciones con respecto a la demanda de servicio que se debe satisfacer, uso de horas extra, acuerdos con los sindicatos y la disponibilidad de personal calificado para contratar. Este ejemplo es opuesto a la hipótesis de divisibilidad. Sin embargo, los niveles de fuerza laboral de cada mes normalmente son lo suficientemente altos como para poder redondear al número entero más cercano sin problemas, siempre y cuando no se violen las restricciones.
[email protected] Facebook: Giovanny Rodriguez 6
APLICACIONES Y MOLDELOS DE PROGRAMACIÓN LINEAL
PROBLEMAS DE PRODUCCION
Un taller tiene (3) tipos de maquina A,B,C ; puede fabricar (2) productos 1y2, todos los productos tienen que ir a cada máquina y cada máquina y cada una va en el mismo orden: primero a la maquina A, luego a la B y luego a la C. La tabla siguiente muestra:
Las horas requeridas en cada máquina, por unidad de producto.
Las horas totales disponibles para cada máquina por semana.
La ganancia por unidad vendida de cada producto.
Tipo de Máquina Producto 1 Producto2 Horas disponibles
Por semana
A 2 2 16
B 1 2 12
C 4 2 28
Ganancia por unidad
1
1.50
¿Qué cantidad de cada producto (1y2) se debe manufacturar cada semana, para obtener la máxima ganancia?
¿Cuantas horas semanales sobran en cada departamento?
[email protected] Facebook: Giovanny Rodriguez 7
Solución
Formulación: Definición de las variables:
Xj = Unidades semanales a producir del articulo j- esimo (j=1 y 2)
X1= Cantidad de Producto 1.
X2= Cantidad de Producto 2.
Función Objetivo:
Maximizar Z = X1 + 3/2 X2
Restricciones:
2X1 + 2X2 ≤ 16 Restricción debida a las horas disponibles por semana de la MQ A
X1 + 2x2 ≤ 12 Restricción debida a las horas disponibles por semana de la MQ B
4X1 + 2X2 ≤ 28 Restricción debida a las horas disponibles por semana de la MQ C
Condición de no negatividad
Xj ≥ 0 ; j= 1y2
BODEGAS
Un barco de carga tiene tres bodegas: Proa, Popa y Centro cuya capacidad máxima de peso a transportar en cada una de ellas es: 2000, 1500 y 3000 toneladas respectivamente. Cada bodega tiene un volumen de: 100.000, 200.000 y 135.000 pies cúbicos respectivamente. Se ofrecen tres tipos de carga denominadas A, B, C en las siguientes cantidades: 6000, 4000 y 2000 toneladas respectivamente. Si cada tonelada de los productos A, B, C ocupa 60, 50 y 25 pies cúbicos y el capitán del barco tiene como política de seguridad cargar el mismo porcentaje de toneladas en cada bodega, de tal forma que maximice las utilidades de la carga, sabiendo que por cada tonelada de los productos A, B, C obtiene una utilidad de $6, $8, $5 respectivamente.
[email protected] Facebook: Giovanny Rodriguez 8
Definición de Variables
- Toneladas de producto A, B, C
- Transportar a bodegas (1)Proa, (2)Popa, (3)Centro
Función Objetivo
Max Z= 6(Xa1+ Xa2 + Xa3) + 8(Xb1+ Xb2 + Xb3) + 5(Xc1+ Xc2 + Xc3)
Restricciones
- Capacidad de bodega: * Proa: Xa1+Xb1+Xc1 =< 2000
(Peso) * Popa: Xa2+Xb2+Xc2 =<1500
* Centro: Xa3+Xb3+Xc3 =< 3000
- Capacidad de bodega: * Proa: 60Xa1 + 50Xb1 + 25Xc1 =< 100.000
(Volumen) * Popa: 60 a2 + 50b2 + 25c2 =< 300.000
* Centro: 60 a3 + 50b3 + 25c3 =< 135.000
Condición de No Negatividad
A, B, C, 1, 2, 3 >= 0
TUERCAS Y TORNILLOS
Un distribuidos de ferreteria planea vender paquetes de tuercas y tornillos mezclados. Cada paquete pesa por lo menos 2Lb. Tres tamaños de tornillos y tuercas componen el paquete y se compran en lotes de 200 Lb. Los tamaños 1,2,3 cuestan respectivamente $20, $8, $12, además:
- El peso combinado de los tamaños 1 y 3 debe ser al menos la mitad del peso total del paquete.
- El peso de los tamaños 1, 2 no debe ser mayor que 1,6Lb.
- Cualquier tamaño de tornillo debe ser al menos el 10% del paquete total.
[email protected] Facebook: Giovanny Rodriguez 9
Variables de decisión
- Tamaño tuercas y tornillos que conforman el paquete: 1, 2, 3.
Función objetivo
Min Z: 20/200X1 + 8/200X2 + 12/200X3
Restricciones
- X1+X2+X3 >= 2
- X1 + X3 =< X1 + X2 + X3 / 2
- X1 + X2 =< 1,6
- X1 >= (X1 + X2 + X3)0,1
- X2 >= (X1 + X2 + X3)0,1
- X3 >= (X1 + X2 + X3)0,1
Condición de no negatividad
X1, X2, X3 >= 0
EL PROBLEMA DE LAS JOYAS
Una pequeña empresa de muebles JBC produce sillas y mesas . cada silla vendida representa una ganancia neta de $ 3000 y cada mesa $ 5000 . se dispone de 30 horas-hombre de capacidad de corte y fabricación por día y de 18 horas – hombre de capacidad de terminado y pintura por día. Igualmente existe un suministro de madera de 30 tablas diarias. Se asume por ahora que estas capacidades no son necesariamente en juegos completos. Para fabricar una silla se requieren dos horas de corte y fabricación , una hora de acabado y pintura y consume una tabla. A su vez cada mesa requiere una hora de corte y fabricación, una hora de acabado y pintura y consume dos tablas. Se desea conocer cuantas sillas y cuantas mesas deberán fabricarse para maximizar las ganancias diarias de la empresa.
[email protected] Facebook: Giovanny Rodriguez 10
Solución
Formulación
Definición de las variables
X1= Cantidad de sillas vendidas
X2= Cantidad de mesas vendidas
Función Objetivo
Max Z = 3000 X1 + 5000 X2
Restricciones
- Restricción en horas en el departamento de corte y pintura
2X1 + X2 ≤ 30 horas-hombre
- Restricción en horas en el departamento de terminado y pintura
X1 + X2 ≤ 18 horas-hombre
- Restricción en materia prima cantidad de tablas
X1 + 2X2 ≤ 30 tablas
- Restricciones de no negatividad
X1, X2 ≥ 0
Una empresa fabrica PC’s de dos tipos:
Procesador intel® Celeron®440 (2.00GHz, 800FBS), Sistema Operativo
Windows VIsta®Home Basic original SP1, Memoria.
2GB Dual Channel DDR2 SDRAM at 800MHz-2DIMMs
Disco Duro
Disco Duro de 160Gb Serial ATA (7200RPM) c/Data Burst Cache
Unidades de CD/DVD
[email protected] Facebook: Giovanny Rodriguez 11
Quemador de DVD 16X DVD+/-RW
El otro:
Procesador
Procesador intel®Pentium®dual-core E2180 (1MB L2 Cache, 2.00GHz,80)
Sistema Operativo
Ubuntu Linux, versión 7-1 con DVD Playback
Memoria
Disco Duro
Disco Duro de 16GB Serial ATA (7200RPM) c/DataBurst Cache
Unidades de CD/DVD
Unidad Quemadora de DVD+/RW de 16X-
Su costo de fabricación, para el primero es de $8 dólares y para el segundo es de $6 dólares. La fabricación de sus componentes se realiza en dos laboratorios.
En el laboratorio 1 (L1) se necesitan dos horas para la fabricación del primer equipo y 1 hora para la fabricación del segundo equipo. En L1 se quiere tener al menos de 10 horas de trabajo.
En el laboratorio 2 (L2) se necesitan 2 horas para la fabricación del primer equipo y 2 horas para la fabricación del segundo equipo. En L2 se quiere tener al menos de 16 horas de trabajo.
Plantee el modelo de manera tal que minimice los costos de fabricación.
Solución
Formulación
[email protected] Facebook: Giovanny Rodriguez 12
Definición de variables
X1= Cantidad de PC1
X2= Cantidad de PC2
Función Objetivo
Min Z= 6X1 + 8X2
Restricciones
Laboratorio 1 (L1) = 2X1 + X2 >= 10 h
Laboratorio 2 (L2) = 2X1 + 2X2 >= 16h
Restricciones no Negatividad
X1, X2 ≥ 0
EJERCICIOS
Problema 3.1
Definir Variables
A= Cantidad de Producto Aritex
B= Cantidad de Producto Extendex
R= Cantidad de Producto Resistex
Función Objetivo
Max Z = 7A + 7E + 6R
[email protected] Facebook: Giovanny Rodriguez 13
Restricciones
- De la Demanda
Aritex → Demanda Producto A ≥ 1000
Extendex→ Demanda Producto B ≥ 500
Resistex → Demanda Producto C ≥ 400
- De Inventarios
Polimero A → 4A + 3E + 6R ≤ 500 Lb → 8000 Oz
Polimero B → 2A + 2E + 3R ≤ 425 Lb → 6800 Oz
Polimero C → 4A + 2E + 5R ≤ 650 Lb → 10400 Oz
Base → 6A + 9E + 2R≤ 1100 Lb →17600 Oz
Problema 3.2
Definir Variables
A= Tubos de Tamaño A
B= Tubos de Tamaño B
C= Tubos de Tamaño C
AJ= Tubos de Japon A
BJ = Tubos de Japon B
CJ= Tubos de japon C
Función Objetivo
Max Z = 7ª + 8B + 5C + 3AJ + 2BJ + 3 CJ
Restricciones
[email protected] Facebook: Giovanny Rodriguez 14
- Por Demanda
A + AJ = 2000
B + BJ = 4000
C + CJ = 5000
- Por Fabricación
0.5 A + 0.45B + 0.6 ≤ 2400
- Material a Soldar
A + B + C ≤ 5500
Problema 3.3
Definición de las Variables
Espagueti = E
Pavo =P
Papas = Pa
Espinacas = Es
Pastel de Manzana= Ma
Función Objetivo
Min Z = 5000E + 5000P + 7900Pa + 3000Es + 14300Ma
Restricciones
→ Por Proteínas
5000E + 29300P + 5300Pa + 3000Es + 4000Ma ≥ 63000(mg)
→Por Hierro
1.1E + 1.8P + 0.5Pa + 2.2Es + 1.2 Ma ≥ 10(mg)
[email protected] Facebook: Giovanny Rodriguez 15
→Por Tiacina
1.4E + 5.4P + 0.9Pa + 0.5Es + 0.6Ma ≥ 15(mg)
→Por Tiamina
0.18E + 0.06P + 0.06Pa + 0.07Es + 0.15Ma ≥ 1(mg)
→Por Vitamina C
0.0E + 0.0P + 10.0Pa + 28.0Es +3.0Ma ≥ 50 (mg)
Una joyeria produce dos tipos de joyas: Tipo 1 y Tipo 2. Cada joya tipo 1 contiene, 2 Rubies y 4 diamantes y se vende a $ 10 Unidad y tiene un costo de producción de $5 Unidad. Cada joya tipo 2 contiene 1 Rubi y 1 diamante, se vende a $6 Unidad y tiene un costo de producción de $4 unidad. La joyeria dispone de 30 Rubies y 40 diamantes para producir las joyas. Por la situación del mercado, se deben producir al menos 10 joyas del tipo 2.
Formule el problema de programación lineal para maximizar la utilidad neta de la joyeria.
Solución
Definición de las Variables
X1 = Joyas tipo 1
X2 = Joyas tipo 2
Función Objetivo
Max Z = 5X1 + 2X2
Restricciones
Rubies: 2X1 + 1X2
Diamantes: 4X1 + 1X2
No Negatividad: X1, X2 >= 0.
[email protected] Facebook: Giovanny Rodriguez 16
UN PROBLEMA DE DIETA
Como es conocido cada ser viviente necesita cantidades diarias de calorías, vitaminas, proteínas, minerales y otros elementos. También se tienen preferencias por los tipos de comidas y marcas. La dieta optima será aquella combinación de alimentos que cumpla con los requerimientos nutricionales y a un costo mínimo. Para simplificar el estudio del problema, se va a suponer que solo existen los requerimientos relacionados con la cantidad minima diaria de tres vitaminas que llamaremos V1, V2, V3. También se supone que solo se están considerando dos tipos de alimentos y productos comerciales que contienen dichas vitaminas y a la vez minimizar el costo de la dieta. Tenemos información que el producto comercial A cuesta $12 el gramo y contiene 2 unidades de vitamina V1, 4 unidades de vitamina V2 y 12 unidades de vitamina V3 por gramo. El producto B cuesta $8 el gramo y contiene 3.75 unidades de V1 gramo, 4 de V2 y 4 de V3. Se requiere que la dieta diaria individual contenga por lo menos 30 unidades de V1, 40 unidades de V2 y 60 unidades de V3. Como deberá formularse un modelo para la dieta a un costo mínimo que satisfaga estos requerimientos?
Solución
Definición de Variables
X1: Cantidad de producto A
X2: Cantidad de producto B
Función objetivo
Min Z: 12X1 + 8X2
Restricciones
2X1 + 3,75X2 >= 30
4X1 + 4X2 >= 40
12X1 + 4X2 >= 60
Condición de No Negatividad
X1, X2 >= 0
UN PROBLEMA DE TRANSPORTE
[email protected] Facebook: Giovanny Rodriguez 17
X,Y,Z productora de motores Diesel tiene cuatro plantas establecidas en Europa. Están ubicadas en Leipzing, Alemania oriental (1); Nancy, Francia (2); Lieja, Belgica (3) y Tilburgo, Holanda (4). Las maquinas ensambladoras usadas en esas plantas se produce en Estado Unidos y se embarcan a Europa. Llegaron a los puertos de de Amsterdan (A), Amberes (B) y el Havre (C).
Los planes de producción del primer trimestre (julio – Septiembre ) ya ha sido formulados.
Los requerimientos de motores diesel E4 son los siguientes:
PLANTA CANTIDAD DE MOTORES
Leipzing 400
Nancy 900
Lieja 200
Tilburgo 500
2000
La cantidad disponible de maquinas E4 en los puertos a tiempo para usarse en el tercer trimestre se muestran enseguida:
PUERTO CANTIDAD DE MOTORES
A) Amsterdam 500
B) Amberes 700
C) El Havre 800
2000
Solución
Definición de Variables
-Cantidad de Planta: 1,2,3
-Cantidad de Puertos: a,b,c.
[email protected] Facebook: Giovanny Rodriguez 18
Función Objetivo
Max Z: 400X1 + 900X2 + 200X3 + 500X4
Restricciones
- Oferta: Xa1 + Xa2 + Xa3 + Xa4 =< 500
Xb1 + Xb2 + Xb3 + Xb4 =< 700
Xc1 + Xc2 + Xc3 + Xc4 =< 800
- Demanda: X1a + X1b + X1c =< 400
X2a + X2b + X2c =< 900
X3a + X3b + X3c =< 200
X4a + X4b + X4c =< 500
Condición de No negatividad: 1,2,3,a,b,c >= 0
CENTROS DE DISTRIBUCION Y DETALLISTAS
Un fabricante tiene tres centros de distribución en Bogota, Medellín y Cali. Estos centros tiene disponibilidad de 20, 40, y 40 unidades respectivamente. Sus detallistas requieren cantidades: Pereira 25, Tulua 10, Ansermo 20, Ibague 30 y Armenia 15. El costo de transporte por unidad en pesos entre cada centro de distribución y las localidades de los detallista se dan en la siguiente tabla:
DETALLISTAS
CENTRO DE DISTRIBUCIO
N
PEREIRA
TULUA
ANSERMO
IBAGUE
ARMENIA
BOGOTA
55 35 40 50 40
MEDELIN
35 30 100 45 60
CALI 40 60 95 35 30
Cuantas unidades debe mandar el fabricante desde cada centro de distribución a cada detallista, de manera que los costos totales de transporte sean minimos?
[email protected] Facebook: Giovanny Rodriguez 19
Variables de decisión
- Centros de Distribución: (1)Bogota, (2)Medellín, (3)Cali; (1), (2), (3), (4), (5)
Función objetivo
Min Z: 55 X11 + 30 X12 + 40 X 13 + 50 X14 + 40 X15 + 35 X21 + 30 X22 + 100 X23 + 45 X24 + 60X25 + 40X31 + 60X32 + 95 X 33 + 35 X 34 + 30X 35
Restricciones
- Oferta: * Bogota: X11 + X12 + X13 + X14 + X15 =< 20
* Medellín: X21 + X22 + X33 + X44 + X45 =< 40
* Cali: X31 + X32 + X33 + X34 + X35 =< 40
- Demanda: * Pereira: X11 + X21 + X31 = 25
* Tulua: X21 + X212+ X23 = 10
* Armensa: X31 + X32 + X33 = 20
* Ibague: X41 + X42 + X43 = 30
* Armenia: X51 + X52 + X53 = 25
Condición de no negatividad: 1,2,3 , 1,2,3,4,5 >= 0
[email protected] Facebook: Giovanny Rodriguez 20
SOLUCIÓN POR EL MÉTODO GRÁFICO
Lo utilizamos para resolver problemas de programación lineal con 2 variables.
Se grafican las restricciones del modelo y la función objetivo.
Región Factible: Conjunto de posibles soluciones -> Cumplen todas las restricciones
Se encuentra la solución óptima(mejor) o soluciones optimas si las hay.
PASOS
1. En las restricciones, transformar los términos de las desigualdades en igualdades ≤ ó ≥ → =.
2. Igualar una de las variables a cero, con el fin de encontrar los puntos de corte con los ejes
3. Trazar las rectas en el plano cartesiano.
4. Hallar los puntos de corte entre las rectas, puede utilizar igualación
5. Tener en cuenta las condiciones de no negatividad(debe trabajar en el cuadrante 1, del plano cartesiano)
6. Los puntos de solución óptima, deben ser reemplazados en la función objetivo, a fin de encontrar el valor máximo o mínimo, que cumpla todas las restricciones.
7. Hallar los puntos ó área de soluciones factibles que satisfagan todas las restricciones
Para poder graficar la solución factible óptima existen dos procedimientos:
- Evaluar la función objetivo en cada punto del área de soluciones factibles, lo tedioso es que si se tienen muchas restricciones van a generar muchos puntos que por supuesto implica la solución de ecuaciones.
[email protected] Facebook: Giovanny Rodriguez 21
- Usando la función objetivo para determinar el punto de soluciones factible que la optimiza. Lo ineficiente de este método es que cuando la FO es paralela a uno de los lados del punto de soluciones factibles causa una duda sobre cual de los puntos es que se hace que la FO sea optima.
Problema sin solución: Este caso se presenta cuando entre las restricciones existe al menos una de ellas que sean excluyentes
RESOLUCIÓN POR EL MÉTODO GRÁFICO
Revise el ejercicio de fabricación de sillas y mesas
Max Z = 3000X1 + 5000X2
Sa = 2X1 + X2 ≤ 30
X1 + X2 ≤18
X1 + X2 ≤30
X1, X2 ≥ 0
VARIABLES X1= Cantidad de Sillas a fabricar
X2 = Cantidad de Mesas a fabricar
Resolver por el método gráfico
Solución:
En las restricciones, transformar los términos de las desigualdades en igualdades ≤ ó ≥ → =.
2X1 + X2 = 30
X1 + X2 = 18
X1 + X2 = 30
Pasos 2,3,4,5
[email protected] Facebook: Giovanny Rodriguez 22
→ X1 + X2 = 18
Si X1=0 , X2= 18
Si X2=0 , X2=18
→ 2X1 + X2 = 30
SI X1 = 0 , X2=15
SIX2= 0 , X1 = 15
→X1 + 2X2 = 30
SI X1= 0 , X2= 15
SI X2 = 0 , X1= 30
GRÁFICA
Paso 6
[email protected] Facebook: Giovanny Rodriguez 23
Reemplazamos en la Función Objetivo
(0,15 ) = (3000)(0) + (15)(5000)= 75000
(0,12) = (3000)(6) + (12)(5000)= 78000→ Punto de solución optima
(12,6) = (3000)(12) + (6)(5000) = 66000
(15,0) = Ø
El punto de solución óptima debe satisfacer las restricciones
2X1 + X2 ≤ 30→ (2)(6) + 12 ≤ 30
12 + 12 ≤ 30
24 ≤ 30
X1 + X2 ≤ 18→ 6 + 12 ≤ 18
18 = 18
X1 + 2X2 ≤ 30→ 6 + 24 ≤ 30
30 = 30
RESPUESTA→ Se deben producir 6 sillas y 12 mesas para maximizar la ganancia que es de $ 78000
[email protected] Facebook: Giovanny Rodriguez 24
UTILIZACION DE COMPLEMENTO SOLVER DE MS EXCEL
Es una herramienta para resolver y optimizar ecuaciones mediante el uso de métodos numéricos.
Con solver se puede buscar el valor óptimo para una celda, denominada objetivo , en donde se escribe la fórmula de la función objetivo F(X1, X2, X3, …).
Solver cambia los valores de un grupo de celdas, denominadas celdas cambiantes y que estén relacionadas, directa o indirectamente, con la fórmula de la celda objetivo. En estas celdas se encuentran los valores de las variables controlables X1, X2, X3,…Xn.
Puede agregar restricciones a Solver, escribiendo una formula Gi(X, X2, X3… Xn) en una celda y especificando que la celda deberá ser mayor o igual, igual, o menor o igual que otra celda que contiene constante Cj.
También puede especificar valores sea enteros, para evitar dar resultados absurdos de algunos problemas, tales como que se necesitan 3.5 empleados.
Solver ajustara los valores de las celdas cambiantes, para generar el resultado especificado en la fórmula de la celda objetivo.
Solver es un excelente complemento de MS Excel que permite la resolución de
pequeños y medianos problemas de Programación Lineal. En la mayoría de las
aplicaciones con fines estudiantiles es suficiente para resolver dichas instancias.
Ahora, veamos cómo funciona con un simple ejemplo1:
MAX 10X + 16Y
S.A. 2X + 2Y <= 8
...... 1X + 2Y <= 6
..... .X>= 0, Y>= 0
PASO 1. Se ingresan los parámetros a una planilla de cálculo. Las celdas
marcadas en amarillo corresponde a las "Celdas Cambiantes" o variables de
1 http://www.programacionlineal.net/programacion_lineal.html.
[email protected] Facebook: Giovanny Rodriguez 25
decisión del modelo. La Celda C2 corresponde al Valor de la Función Objetivo que
esta dada por: A2*A3 + C2*C3. Las Celdas C5 Y C6 almacenan el valor o lado
izquierdo de las restricciones 1 y 2, quedando definidas como A2*A5 + B2*B5 y
A2*A6 + B2*B6, respectivamente.
PASO 2. Se inicia la aplicación Solver y se cargan los datos de la planilla.
PASO 3. Una vez ingresados los parámetros se selecciona "Opciones". Una vez
dentro de este menu se deben activar las opciones de "Adoptar modelo lineal" y
"Asumir no negativos". Luego se selecciona "Aceptar" y luego "Resolver.
PASO 4. Si el modelo admite solución se obtienen los resultados. Se recomienda
seleccionar los Informes que sugiere Solver para una mayor comprensión del
modelo resuelto.
[email protected] Facebook: Giovanny Rodriguez 26
PASO 5. Los resultados son desplegados en las celdas cambiantes y se verifica el
cumplimiento de las restricciones del problema. La Solución Óptima
es X=2,Y=2 con Valor Óptimo V(P)=52. Adicionalmente, ambas restricciones se
encuentran activas, es decir, se cumplen en igualdad.
PASO 6. Al seleccionar los Informes de Respuesta, en particular el "Informe de
Sensibilidad" se obtiene información relevante sobre el modelo propuesto.
Respecto a las celdas cambiantes (variables de decisión) se incluye un intervalo
de variación para los coeficientes en la función objetivo que mantienen la actual
Solución Óptima. Por ejemplo C1 (Coeficiente que acompaña a X en la función
objetivo, actualmente igual a 10) puede variar en el siguiente intervalo
garantizando la actual Solución Óptima: {10 - 2, 10 + 6} = {8, 16}. De la misma
forma el intervalo para C2 (Coeficiente que acompaña a Y en la función objetivo,
actualmente igual a 16) es {10, 20}
[email protected] Facebook: Giovanny Rodriguez 27
En cuanto a las restricciones, el precio sombra de la restricción 1 es 2, el cual es
válido siempre y cuando la variación en el lado derecho se encuentre en el
intervalo {8 - 2, 8 + 4} = {6, 12}. De la misma forma, el precio sombra para la
restricción 2 es 6, válido en el intervalo de variación del lado derecho entre {4, 8}.
[email protected] Facebook: Giovanny Rodriguez 28
SOLUCIÓN POR EL MÉTODO SIMPLEX
Es muy dispendioso, en razón a que trabaja con todos los datos de las ecuaciones, para mejorar este aspecto se creo el método simplex cuya virtud es su sencillez, este método solo trabaja con los coeficientes de la función objetivo y de las restricciones.
Criterio de decision
Maximizar Minimizar
Variable que entra
- M +M
Variable que entra
La más negativa de los Zj – Cj
La más positiva de los Zj - Cj
Variable que sale
La menos positiva de los b/a, siendo a>0, de lo contrario no restringe
La menos positiva de los b/a, siendo a>0, de lo contrario no restringe a la variable que entra
Solución optima
Cuando todos los Zj – Cj >=0
Cuando todos los Zj – Cj <=0
Para tener en cuenta:
- Si en el tablero simplex de la solución optima queda al menos una variables de Superavit o artificial dentro de las variables básicas, con un valor .0, el problema no tiene solución, esto quiere decir que al menos existen dos restricciones excluyentes, por lo tanto no existe área de soluciones factible y menos una solución, en este caso se debe revisar la formulación del problema.
- Si al escoger la variable que sale ninguna de las variables básicas restringe el crecimiento de la variable no básica escogida para entrar, el problema tiene solución indeterminada y se debe revisar la formulación en busca de una nueva restricción que no se tuvo en cuenta en la formulación inicial.
- Si en el tablero simplex del optimo, al menos una de las variables no básicas tiene coeficiente cero (0) en la función objetivo, esto es si Zj – Cj = 0, el problema tiene múltiples soluciones y se nos esta ofreciendo una de ellas.
[email protected] Facebook: Giovanny Rodriguez 29
Proceso interactivo que permite solucionar modelos de programación lineal de tamaño “n” restricciones y “m” variables.
ACTIVIDADES FUNDAMENTALES
- Prueba de Optimidad
- Identificar las variables que entran y salen
- Realizar un análisis de la tabla característica para desarrollar una nueva solución
PROCEDIMIENTO
1. Estandarize el modelo de programación lineal
2. Construya la tabla característica
3. Identificar las variables que entran y salen
4. Determine la solución básica
5. Probar la optimalidad de la función
ESTANDARIZACION DEL MODELO
Tiene que ver con las restricciones aumentadas es decir cada restricción del problema se debe aumentar utilizando variables de holgura y/o variables artificiales
[email protected] Facebook: Giovanny Rodriguez 30
Cualquier desigualdad “≤” se puede conventir en una igualdad agregando variables de holgura “Si” i= 1,2,3,4……. Para que represente el Superavit
Cualquier desigualdad “≥” se puede convertir en una igualdad restando variables de excedente o de holgura “Si” y sumando una variable artificial. Agregar una variable artificial se justifica para dar cumplimiento al criterio de no negatividad
A las restricciones donde el signo es una igualdad se le agrega una variable artificial para que represente la expresión de lado izquierdo en ausencia de las variables de holgura o excedente
La estandarización del modelo de programación lineal , también tiene que ver con la función objetivo por lo que deben agregarse a esta función todas las variables que aparecen como extras en las restricción
Los coeficientes o contribuciones de las variables extras que deben aparecer en la función objetivo tienen valores : 0, +M, -M, teniendo en cuenta: toda variable de holgura tiene una contribución de 0 para problemas de maximización o minimización.
Las variables artificiales deben tener un coeficiente positivo aproximadamente 100 veces mayor que el coeficiente mas grande que la función objetivo , cuando el problema es de minimización ; esto con el fin de evitar que estén en la solución final
Cuando el problema es de maximización el coeficiente de la variable artificial debe ser negativo y muy pequeño, para que la variable artificial no se mantenga en la base . este coeficiente se representa con la letra “M” y la variable artificial con la letra “A”.
Todo problema de programación lineal que se formule de la forma Maximice, con todas sus restricciones,<= y con la condición de no negatividad, le llamaremos Forma estándar o forma normal.
Aquí al igual que en el método algebraico debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales.
EJEMPLO
Min Z = 8X1 + 2X2
Sa = 2X1 + 3X2 ≤ 40
[email protected] Facebook: Giovanny Rodriguez 31
4X1 + 6X2 ≥ 10
5X1 + 2X2 = 20
ESTANDARIZACIÓN
2X1 + 3X2 + S1 =40
4X1 + 6X2 -S2 + A1 =10
5X1 + 2X2 + + A2= 20
Función objetivo
Min Z = 8X1 + 2X2 + 0S1 – 0S2 + MA1 + MA2
CARACTERISTICAS DE LAS VARIABLES DE ESTANDARIZACION
VARIABLE Si = representan el superávit o déficit de recursos excasos. Puede ser variable básica en la solución óptima.
VARIABLE ARTIFICIAL Ai = son ficticias ya que solo se usan al comienzo del proceso simplex para la estandarización del modelo y cumplir con el criterio de no negatividad . no pueden ser variables básicas en la solución optima. Si esto llega a suceder el problema no tiene solución. Son instrumentos de calculo que se usan en las restricciones “≥” ó “=”.
DISEÑO DE LA TABLA
EJEMPLO
Max Z = C1X1 + C2X2………+ CnXn
[email protected] Facebook: Giovanny Rodriguez 32
Sa = a11X1+ a12X2……+ a1nXn ≤ B1
a21X1 + …………….+ a2nXn ≤ B2
Xi ≥ 0
Ci X1 X2 ….Xn Ѳi
C1
C2
C3
X1
X2
X3
B1
B2
B3
a 11
..
..
a 12
..
..
…a1n
..
..
Ѳ1
Ѳ2
Ѳ3
Zj BФ
Cj - Zj
Cj – Zj = Parámetro de optimización ( costos reducidos ).
Ѳi = Bi = Parametro de factibilidad (marca la pauta de la variableque sale)
aij
m
Zj = BФ = ∑ CiBi
i = 1
Ci = contribución de la variable básica (VB )
Xj = Variables Basicas y No Basicas.
Bi = Disponibilidad de recursos al comienzo y valor de las variables básicas al final o sobrante de un recurso
BФ = Valor del Z optimo
[email protected] Facebook: Giovanny Rodriguez 33
DETERMINACION DE LA VARIABLE QUE ENTRA Y SALE
COLUMNA PIVOTE = variable que entra a partir de Cj – Zj se busca el numero mas positivo a partir de cero para problemas de maximización.
VARIABLE QUE ENTRA = se obtiene a partir de Cj – Zj desde cero buscando el mas negativo para el caso de minimización.
FILA PIVOTE (variable que sale)= se optiene a partir de Ѳi mas cercano a cero para cualquier criterio de optimización en la intersección de la columna y la fila se encuentra la celda pivote
DETERMINACION DE LA NUEVA SOLUCIÓN
Introducir a la base la variable correspondiente a la columna pivote que tomara el puesto que corresponde a la fila pivote. Una vez se haga el intercambio se aplica Gauss Jordan para hacer la interaccion simplex.
PROBAR LA OPTIMALIDAD DE LA FUNCIÓN
El proceso simplex se termina cuando todos los Cj – Zj son ceros o negativos en problemas de Maximizacion ; y ceros o positivos en problemas de minimizacion las iteraciones tienen en cuenta la elección de la celda pivote y luego la iteraccion simplex.
ELECCIÓN DE LA CELDA PIVOTE
Se tienen en cuenta 2 criterios
[email protected] Facebook: Giovanny Rodriguez 34
Criterio de optimalidad = El mayor o menor negativo, según el caso, costo reducido dado por Cj – Zj este valor es llamado costo de oportunidad neto y esta dado por la suma de algebraica de la contribución de la variable que sale y la variable que entra.
Criterio Dos = seleccionada la fila pivote se toma como base los aij de la columna anterior para relacionarlos con los recursos disponibles Bi, al fin de obtener el valor de Ѳi que permite aplicar el criterio de factibilidad a partir del Ѳi mas cercano a cero. La excogencia del menor Ѳi se debe a que explica la relación existente entre la disponibilidad del recurso y la tasa de susutitucion , es decir permite visualizar cuanto es lo máximo que puede producir.
Se llama tasa de susutitucion porque susutituye el recurso disponible por un recurso determinado o durante el proceso sustituye lo requerido entre dos variables.
INTERACCIÓN SIMPLEX
Para hacer la iteraccion simplex debe elaborarse un nuevo tablero donde en la base debe aparecer la variable que entra con sus respectivas contribuciones y a partir de esta fila aplicar Gauss Jordan a fin de obtener el nuevo valor de a función objetivo . la solución optima se encuentra en aquel tablero en que los costos de oportunidad sean ceros o negativos o positivos según el caso. La existencia de valores positivos como costos de oportunidad significa que hay incentivos para hacer una nueva combinación que optimiza el valor de Z positivo en caso de Maximizacion y negativo en caso de Minimizacion.
En todos los procesos simplex donde alla costos de oportunidad o Ѳi iguales debe decidirse arbitrariamente.
EJEMPLO METODO SIMPLEX
Min Z = X1 + X2
Sa= X1 + X2 ≥ 2
[email protected] Facebook: Giovanny Rodriguez 35
-X1 + X2 ≥ 3
X1 +3X2 ≥ 12
ESTANDARIZACIÓN
1X1 + 1X2 -1S1 +1A1 = 2
-X1 +1X2 -S2 +1A2 = 3
1X1 + 3X2 +S3 = 12
X1,X2,Si,Ai ≥ 0
Funcion Objetivo
Min Z = X1 + 2X2 + 0S1 + OS2 + 0S3 + MA1 + MA2
Cj 1 2 0 0 0 M M θi
Ci VB Bi X1 X2 S1 S2 S3 A1 A2 Bi/ai
M A1 2 1 1 -1 0 0 1 0 2
M A2 3 -1 1 0 -1 0 0 1 3
0 S3 12 1 3 0 0 1 0 0 4
Zj 5M 0 2M -M -M 0 M M
Cj-Zj 1 2-2M M M 0 0 0
Cj 1 2 0 0 0 M M θi
Ci VB Bi X1 X2 S1 S2 S3 A1 A2 Bi/ai
[email protected] Facebook: Giovanny Rodriguez 36
2 X2 2 1 1 -1 0 0 1 0
M A2 1 -2 0 1 -1 0 -1 1 1
0 S3 6 -2 0 3 0 1 -3 0 2
Zj 4+M 2-2M 2 -2+M -M 0 2-M M
Cj-Zj -1+2M 0
2-M
M
0 -2+2M 0
Cj 1 2 0 0 0 M M θi
Ci VB Bi X1 X2 S1 S2 S3 A1 A2 Bi/ai
2 X2 3 -1 1 0 -1 0 0 1
0 S1 1 -2 0 1 -1 0 -1 1
0 S3 3 4 0 0 3 1 0 -3
Zj 6 -2 2 0 -2 0 0 2
Cj-Zj 3 0 0 2 0 M M-2
CASOS ESPECIALES
Un problema de programación lineal tiene soluciones multiples cuando en el tablero optimo existe una variable no básica con Cj – Zj = 0
Existe una solución degenerada cuando el tablero optimo aparece una variable básica en cero
Existe una solución ilimitada cuando las iteraciones son infinitas
Sin solución o no factible aquellas en el que el tablero optimo aparece una variable básica artificial.
[email protected] Facebook: Giovanny Rodriguez 37
DUALIDAD
Si el primal tiene criterio de optimización maximización, en el dual se incluye minimización y viceversa
[email protected] Facebook: Giovanny Rodriguez 38
Si el primal tiene signos “≥” el dual tiene signos “≤” y viceversa
Las constantes de beneficio Cj de la función objetivo se reemplazan por las constantes de capacidad Bi y viceversa.
En las desigualdades de restricción los coeficientes que se encontraron de izquierda a derecha se coloca en ellos de arriba hacia abajo y viceversa.
Los coeficientes tecnológicos que componen las filas de cada uno de los modelos conforman las columnas del modelo dual y viceversa.
Ignorando el numero de condiciones de no negatividad si en el primal hay “n” variables y “m” desigualdades , en el dual abra “m” variables y “n” desigualdades.
Se desea generalmente en los problemas de minimización que sus restricciones sean ≥ si no es asi se multiplican ambos términos de lado derecho e izquierdo por -1 y se cambia la desigualdad.
EJEMPLO
Min Z = 40 X1+ 200 X2
Sa = 4X1 + 40X2 ≥ 160
3X1 + 10X2 ≥ 60
8X1 + 10X2 ≥ 80
X1, X2 ≥ 0
Primal →2 variables
3 desigualdades
Max Z = 160Y1 + 60Y2 + 80Y3
Sa = 4 Y1 + 3Y2 + 8Y3 ≤ 40
40Y1 + 10Y2 + 10Y3
≤ 200
[email protected] Facebook: Giovanny Rodriguez 39
Y1,Y2,Y3 ≥ 0
Dual → 3 Variables
2 Desigualdades
METODO “SIMPLEX”, DUALIDAD Y SENSIBILIDAD
Utilice el método simplex para resolver los siguientes problemas:
1- MAXIMIZAR Z = X1 +X2
C.S.R: 5X1 + 3X2 ≤ 15
3X1 + 5X2 ≤ 15
CON X1,X2 ≥ 0
Solución:
Maximizar Z = X1 + X2 + 0S1 +0S2
S.a: 5X1 + 3X2 + S1 ≤ 15
3X1 + 5X2 + S2≤ 15
X1, X2, S1, S2 ≥ 0
Cj 1 1 0 0 Θi
[email protected] Facebook: Giovanny Rodriguez 40
Ci Vb Bi X1 X2 S1 S2 Bi/ai
0 S1 15 5 3 1 0 3
0 S2 15 3 5 0 1 5
Zj 0 0 0 0 0
Cj-Zj 1 1 0 0
Cj 1 1 0 0 Θi
Ci Vb Bi X1 X2 S1 S2 Bi/ai
1 X1 3 1 0.6 0.2 0 5
0 S2 6 0 3.2 -0.6 1 1.875
Zj 3 1 0.6 0.2 0
Cj-Zj 0 0.4 -0.2 0
Cj 1 1 0 0 Θi
Ci Vb Bi X1 X2 S1 S2 Bi/ai
1 X1 1.875 1 0 0.3125 -0.188
1 X2 1.875 0 1 -0.1875 0.3125
Zj 3.75 1 1 0.125 0.125
Cj-Zj 0 0 -0.125 -0.125
Z= 3.75
X1= 1.875 X2= 1.875
[email protected] Facebook: Giovanny Rodriguez 41
2- La cia Peer fabrica cuatro productos (1,2,3,4) . En la siguiente tabla se enumeran, los requerimientos de materia prima , el especio de almacenamiento necesario, las tasas de producción y ganancia. La cantidad total de material, disponible diariamente, para todos los cuatro productos es 180 libras. El espacio total disponible para almacenamiento es de 230 pies cuadrados y en producción se utilizan 7 horas por día .
CUADRO RESUMEN Producto 1 Producto 2 Producto 3 Producto 4
Materia Prima, libras/unidad 2 2 1,5 4
Espacio, pies cuadrado/unidad 2 2,5 2 1,5
Tasa de producción, unidades/ hora 15 30 10 15
Ganancia, $/unidad 5 6,5 5 5,5
¿Cuántas unidades de cada producto deben fabricarse para maximizar la ganancia?
Maximizar Z= 5X1 + 6.5X2 + 5X3 +5.5X4
S.A.:
2X1 + 2X2 + 1.5X3 + 4X4 ≤ 180
2X1 + 2.5X2 + 2X3 + 1.5X4 ≤ 180
15X1 + 30X2 + 10X3 + 1.5X4 ≤ 180
X1, X2, X3, X4 ≥ 0
Solución:
Maximizar Z= 5X1 + 6.5X2 + 5X3 + 5.5X4 + 0S1 + 0S2 + 0S3
[email protected] Facebook: Giovanny Rodriguez 42
S.A.:
2X1 + 2X2 + 1.5X3 + 4X4 + S1 ≤ 180
2X1 + 2.5X2 + 2X3 + 1.5X4 + S2 ≤ 180
15X1 + 30X2 + 10X3 + 1.5X4 + S3≤ 180
X1, X2, X3, X4, S1, S2, S3 ≥ 0
Cj 5 6.5 5 5.5 0 0 0 Θi
Ci Vb Bi X1 X2 X3 X4 S1 S2 S3 Bi/ai
0 S1 180 2 2 1.5 4 1 0 0 90
0 S2 230 2 2.5 2 1.5 0 1 0 92
0 S3 7 15 30 10 15 0 0 1 0.2333
Zj 0 0 0 0 0 0 0 0
Cj-Zj 5 6.5 5 5.5 0 0 0
Cj 5 6.5 5 5.5 0 0 0 θi
Ci Vb Bi X1 X2 X3 X4 S1 S2 S3 Bi/ai
0 S1 179.5 1 0 0.833333 3 1 0 -0.067 215.44
0 S2 229.4 0.75 0 1.166667 0.25 0 1 -0.083 196.64
6.5 X2 0.233 0.5 1 0.333333 0.5 0 0 0.033 0.7
Zj 1.517 3.25 6.5 2.166667 3.25 0 0 0.217
[email protected] Facebook: Giovanny Rodriguez 43
Cj-Zj 1.75 0 2.833333 2.25 0 0 -0.217
Cj 5 6.5 5 5.5 0 0 0 Θi
Ci Vb Bi X1 X2 X3 X4 S1 S2 S3 Bi/ai
0 S1 179 -0.25 -2.5 0 1.75 1 0 -0.15
0 S2 228.6 -1 -3.5 0 -1.5 0 1 -0.2
5 X3 0.7 1.5 3 1 1.5 0 0 0.1
Zj 3.5 7.5 15 5 7.5 0 0 0.5
Cj-Zj -2.5 -8.5 0 -2 0 0 -0.5
De acuerdo al primal del ejercicio anterior:
Transfórmelo en un problema dual.
Minimizar C= 180Y 1 + 230Y2 + 7Y3
S.A.: 2Y1 + 2Y2 + 15Y3 ≥ 5
2Y1 + 2.5Y2 + 30Y3 ≥ 6.5
1.5Y1 + 2Y2 + 10Y3 ≥ 5
4Y1 + 1.5Y2 + 15Y3 ≥ 5.5
VARIABLES Y1 Y2 Y3
180 230 7
CANTIDAD 0 0 0.5
3.5
[email protected] Facebook: Giovanny Rodriguez 44
S.A.
2 2 15 7.5 >= 5
2 2.5 30 15 >= 6.5
1.5 2 10 5 >= 5
4 1.5 15 7.5 >= 5.5
¿Cuál es su interpretación económica?
Y1= costo de una unidad de materia prima.
Y2= costo de una unidad de espacio de almacenamiento.
Y3= costo de unidad de tiempo de producción por cada unidad de producto.
Para el Producto 1: 2Y1 + 2Y2 + 15 Y3, la suma es el valor total de los insumos para producir una unidad de este producto. El valor de los insumos que entran en la producción de una unidad de este producto, que es $7.5 debe ser mayor o igual al beneficio que la empresa hace al producir una unidad del Producto 1, el cual es $5.
Y asi sucesivamente se va realizando el análisis con cada uno de los productos.
Resuélvalo por Solver, realice el análisis de sensibilidad y explique:
Variables X1 X2 X3 X4
Ganancia 5 6.5 5 5.5
Cantidad 0 0 0.7 0
Utilidad 3.5
[email protected] Facebook: Giovanny Rodriguez 45
S.A
mat prim lb/u 2 2 1.5 4 1.05 <= 180
espacio, pies cua 2 2.5 2 1.5 1.4 <= 230
tasa prod unid/h 15 30 10 15 7 <= 7
ANÁLISIS DE SENSIBILIDAD
INFORME DE SENSIBILIDAD:
Celdas cambiantes
Valor Gradiente Coeficiente Aumento Disminución
Celda Nombre Igual reducido objetivo permisible permisible
$C$11 x1 0 -2.5 5 2.5 1E+30
$D$11 x2 0 -8.5 6.5 8.5 1E+30
$E$11 x3 0.7 0 5 1E+30 1.333333333
$F$11 x4 0 -2 5.5 2 1E+30
Restricciones
[email protected] Facebook: Giovanny Rodriguez 46
Valor Sombra Restricción Aumento Disminución
Celda Nombre Igual precio lado derecho permisible permisible
$G$4 mat prim lb/u Suma Prod 1.05 0 180 1E+30 178.95
$G$5 espacio, pies cua Suma Prod 1.4 0 230 1E+30 228.6
$G$6 tasa prod unid/h Suma Prod 7 0.5 7 1143 7
Informe de límites:
Celda objetivo
Celda Nombre Igual
$C$13 Utilidad x1 3.5
Celdas cambiantes Límite Celda Límite Celda
Celda Nombre Igual inferior objetivo superior objetivo
$C$11 x1 0 0 3.5 0 3.5
$D$11 x2 0 0 3.5 0 3.5
$E$11 x3 0.7 0.7 3.5 0.7 3.5
$F$11 x4 0 0 3.5 0 3.5
- ¿Cuál es el valor de la función objetivo y los valores de cada variable?
[email protected] Facebook: Giovanny Rodriguez 47
El valor de la función objetivo es 3.5 y los valores de las variables X1, X2, X3, y X4 son 0, 0, 0.7 y 0 respectivamente.
-¿Qué interpretación tienen los precios sombra, los costos reducidos, limites, Aumento permisible, disminución permisible?
Precio sombra: Si se dispone de mas horas en la producción, se podría mejorar la utilidad global incrementándose en $ 0.5 por cada hora extra.
Costos reducidos: Las variables X1, X2 y X4 son negativas, es decir no conviene producir estos productos, en cambio X3 es positiva (conviene producir este producto), por lo que su costo reducido es cero.
Limites: El menor valor que puede tomar las variables X1, X2, X3, X4 es 0, 0, 0, y 0 respectivamente (suponiendo que las demás mantienen el valor optimo encontrado), el cual es el mismo valor mayor que pueden tomar y así satisfacer todas las restricciones.
Aumento permisible: Los coeficientes de la función objetivo tienen un incremento admisible de 2.5, 8.5,1E+30, 2 respectivamente sin que cambien los valores óptimos de las variables controlables.
Disminución permisible: Es lo contrario de aumento, es decir que es la disminución admisible en los coeficientes de la función objetivo que para este caso son: 1E+30, 1E+30, 1.333333, 1E+30 respectivamente, sin que los valores óptimos de las variables controlables cambien.
[email protected] Facebook: Giovanny Rodriguez 48
MODELO DE ASIGNACIÓN Y TRANSPORTE
MÉTODO HÚNGARO:
En cada fila establezca el menor costo y reste este a toda la fila. Continúe esta operación con las filas siguientes
Establezca el menor costo por columnas
Establezca la menor cantidad de líneas rectas que agrupen los ceros (Horizontal o vertical).
De acuerdo a la matriz nxn se debe establecer que el número de líneas horizontales y verticales sea igual o mayor al número de filas o columnas. Una vez se cumple con el criterio, hemos encontrado una solución óptima.
Asigne los elementos a cada centro de trabajo, teniendo en cuenta que cada elemento asignado a un centro de trabajo excluye su operación o asignación.
EJEMPLO:
Una organización tiene 3 centros de trabajo (CT1, CT2, CT3), elabora piezas especiales para aviones boing. A continuación se detallan los costos que tendría que realizar en cada centro de trabajo para la fabricación de cada producto:
Encontramos el costo menor por filas:
[email protected] Facebook: Giovanny Rodriguez 49
CT1 CT2 CT3
R34 11 9 6
S67 12 8 10
T-50 3 4 9
El costo menor se resta a cada valor de la fila con el fin de buscar la solución óptima:
CT1 CT2 CT3
R34 5 3 0
S67 4 0 2
T-50 0 1 6
Se traza el menor número de líneas que pasen por los valores iguales a cero:
CT1 CT2 CT3
R34 5 3 0
S67 4 0 2
T-50 0 1 6
[email protected] Facebook: Giovanny Rodriguez 50
Por último se realiza la asignación de cada uno teniendo en cuenta que se deben elegir valores que estén dentro de las líneas trazadas y los de menor costo, es decir, costo=0:
R34 CT3
S67 CT2
T-50 CT1
MÉTODO DE LA ESQUINA NOROESTE:
Consiste en igualar el elemento e la esquina superior izquierda con el menor valor entre su disponibilidad y su demanda. Se completa la fila o columna correspondiente hasta saturarla, es decir, hasta que se haya agotado la disponibilidad correspondiente o se haya satisfecho la demanda de este destino. Repetiremos este proceso, eliminando la fila o columna que se encuentre saturada, hasta completar la solución.
EJEMPLO:
Cierto fabricante dispone de tres centros de distribución para sus productos que denominaremos A, B y C, y cuyas disponibilidades de materia prima son respectivamente 100, 120 y 120 Tm. Esta materia prima debe ser entregada en cinco fábricas donde se elabora el producto final. Las necesidades en Tm de materia prima de cada una de las fábricas son 40, 50, 70, 90 y 90. Señala una solución factible utilizando el método de la esquina noroeste.
Construimos la tabla de transporte del problema:
[email protected] Facebook: Giovanny Rodriguez 51
1 2 3 4 5 bi
A 100
B 120
C 120
dj 40 50 70 90 90 340
Comenzamos asignando en la casilla superior izquierda, es decir, en la casilla noroeste el primer valor de dj. o sea transportaremos 40 Tm de materia prima desde el centro de distribución A hasta la fábrica , satisfaciendo así las necesidades de este destino, con lo cual saturamos la primera columna, pues ya no se transportarán más unidades de materia prima a esta fábrica.
1 2 3 4 5 bi
A 40 100
B 120
C 120
dj 40 50 70 90 90 340
Seguiremos asignando en la casilla de la esquina noroeste, en este caso X12. La asignación será igual al mínimo entre su disponibilidad (una vez ajustado el efecto de la asignación anterior) y su demanda. De esta forma se satisface la demanda del destino 2, por lo que esta columna queda saturada y la eliminaremos en los siguientes pasos.
[email protected] Facebook: Giovanny Rodriguez 52
1 2 3 4 5 bi
A 40 50 100
B 120
C 120
dj 40 50 70 90 90 340
La nueva casilla noroeste es la X13 en la que asignaremos el mínimo entre su disponibilidad y su demanda, es decir, 10 en este caso. De esta forma se satura la primera fila al haberse agotado la disponibilidad de materia prima del centro de distribución A.
1 2 3 4 5 bi
A 40 50 10 100
B 120
C 120
dj 40 50 70 90 90 340
La siguiente asignación en la casilla noroeste será X23, que equivale a 60, con lo que saturamos la tercera columna, correspondiente a la fábrica 3.
[email protected] Facebook: Giovanny Rodriguez 53
1 2 3 4 5 bi
A 40 50 10 100
B 60 120
C 120
dj 40 50 70 90 90 340
Volvemos a seleccionar la casilla noroeste y asignamos hasta saturar la fila o la columna correspondiente, es decir, X24=60
1 2 3 4 5 bi
A 40 50 10 100
B 60 60 120
C 120
dj 40 50 70 90 90 340
Completamos el proceso de búsqueda de una solución inicial factible a través de la esquina noroeste, obteniendo X34=30, con lo que restaría la única asignación más en la casilla X35=90. De esta forma, una solución inicial factible sería la señalada en la siguiente tabla:
1 2 3 4 5 bi
A 40 50 10 100
[email protected] Facebook: Giovanny Rodriguez 54
B 60 60 120
C 30 90 120
dj 40 50 70 90 90 340
MÉTODO DEL MÍNIMO DE FILAS Y COLUMNAS:
MÍNIMO DE FILAS:
Siendo C1j el menor costo de transporte correspondiente a la primera fila de la tabla de transporte, igualaremos X1j al menor valor entre su disponibilidad (b1) y su demanda (dj), saturando de esta forma la fila o la columna respectiva. Si es la fila la que resulta saturada, seguiremos asignando en la misma fila hasta saturar la capacidad de dicho origen (bi).
MÍNIMO DE COLUMNAS:
Es similar al anterior, pero se actúa por columnas en lugar de hacerlo por filas.
EJEMPLO:
Resolver el problema anterior utilizando el método del mínimo de filas y del mínimo de columnas. Teniendo en cuenta que presentaremos a continuación la tabla de datos:
[email protected] Facebook: Giovanny Rodriguez 55
1 2 3 4 5
A 10 20 5 9 10
B 2 10 8 30 5
C 1 20 7 10 4
Aplicando el método de mínimo de filas, la tabla de transporte sería:
O D 1 2 3 4 5 bi
A 10 X11 20 X12 5 X13 9 X14 10 X15 100
B 2 X21 10 X22 8 X23 30 X24 5 X25 120
C 1 X31 20 X32 7 X33 10 X34 4 X35 120
dj 40 50 70 90 90 340
Comenzando con la primera fila, seleccionamos la casilla de menor costo unitario de transporte y asignamos hasta saturar la fila o la columna correspondiente. En este caso, la variable de menor costo unitario de transporte es X13 (C13=5), por lo que el valor de dicha variable será 70, satisfaciendo de esta forma las necesidades de materia prima en la fábrica 3 y eliminaremos, por tanto, esta columna.
[email protected] Facebook: Giovanny Rodriguez 56
O D 1 2 3 4 5 bi
A 10 X11 20 X12 5 70 9 X14 10 X15 100
B 2 X21 10 X22 8 30 X24 5 X25 120
C 1 X31 20 X32 7 10 X34 4 X35 120
dj 40 50 70 90 90 340
Como no hemos saturado la fila con la que estamos trabajando, volvemos a iterar el procedimiento. La variable de menor costo unitario será ahora X14, de manera que X14=30, saturando la fila 1 al haber transportado toda la disponibilidad del origen A.
O D 1 2 3 4 5 bi
A 10 20 5 70 9 30 10 100
B 2 X21 10 X22 8 30 X24 5 X25 120
C 1 X31 20 X32 7 10 X34 4 X35 120
dj 40 50 70 90 90 340
Continuamos desarrollando el proceso de búsqueda de una solución factible a través de las filas de la matriz de transporte obteniendo el siguiente resultado:
[email protected] Facebook: Giovanny Rodriguez 57
O D 1 2 3 4 5 bi
A 10 20 5 70 9 30 10 100
B 2 40 10 8 30 5 80 120
C 1 20 50 7 10 60 4 10 120
dj 40 50 70 90 90 340
Aplicando el método de mínimo de columnas se genera la siguiente solución inicial factible:
O D 1 2 3 4 5 bi
A 10 20 5 70 9 30 10 100
B 2 10 50 8 30 5 70 120
C 1 40 20 7 10 60 4 20 120
dj 40 50 70 90 90 340
MÉTODO DE VOGEL:
Se trata de un procedimiento de búsqueda que podemos examinar a través del siguiente proceso:
Para cada fila y cada columna calculamos la diferencia en valor absoluto entre el menor costo unitario y el siguiente menor, seleccionando aquella fila o columna que proporcione MAYOR diferencia.
[email protected] Facebook: Giovanny Rodriguez 58
En dicha fila o columna seleccionamos la variable (Xij) con menor costo unitario y asignamos hasta completar la demanda (dj) o la disponibilidad (bi). La fila o columna que resulte saturada no se considerará en posteriores iteraciones.
Volvemos a iniciar el proceso hasta completar una solución inicial factible.
EJEMPLO:
A continuación aplicaremos el método de Vogel al ejemplo que venimos utilizando anteriormente. Tener en cuenta la siguiente tabal de datos:
1 2 3 4 5
A 10 20 5 9 10
B 2 10 8 30 5
C 1 20 7 10 4
Comenzaremos calculando las diferencias de costo en cada fila y cada columna:
O D 1 2 3 4 5 bi Diferencia de costos
A 10 X11 20 X12 5 X13 9 X14 10 X15 100 4
B 2 X21 10 X22 8 X23 30 X24 5 X25 120 3
C 1 X31 20 X32 7 X33 10 X34 4 X35 120 3
dj 40 50 70 90 90 340
[email protected] Facebook: Giovanny Rodriguez 59
Dif de costos
1 10 2 1 1
Seleccionamos la diferencia de mayor valor, que se corresponde con la columna 2, y asignamos en la casilla de menor costo de este columna (X22) el mínimo entre su disponibilidad y su demanda, es decir, 50. Con lo que saturamos la columna que dejaremos de considerar en las siguientes iteraciones de este proceso de búsqueda de Vogel.
A continuación, volvemos a calcular diferencias de costo para cada fila y cada columna:
O D 1 2 3 4 5 bi Diferencia de costos
A 10 X11 20 5 X13 9 X14 10 X15 100 4
B 2 X21 10 50 8 X23 30 X24 5 X25 120 3
C 1 X31 20 7 X33 10 X34 4 X35 120 3
dj 40 50 70 90 90 340
Dif de costos
1 -- 2 1 1
En esta segunda iteración, la mayor diferencia se encuentra en la fila 1 para la que seleccionamos la variable de menor costo unitario de transporte (X13) en la que asignaremos X13=70, saturando, de esta forma, la columna 3:
[email protected] Facebook: Giovanny Rodriguez 60
O D 1 2 3 4 5 bi Diferencia de costos
A 10 X11 20 5 70 9 X14 10 X15 100 1
B 2 X21 10 50 8 30 X24 5 X25 120 3
C 1 X31 20 7 10 X34 4 X35 120 3
dj 40 50 70 90 90 340
Dif de costos
1 -- -- 1 1
En la tercera iteración se produce un empate para las menores diferencias de costo entre los orígenes B y C que, o bien se rompe arbitrariamente, o bien se examina cuál de las dos columnas posee la casilla de menor costo, seleccionando esta. Nosotros optamos por la segunda alternativa y elegimos la fila 3, que incluye la variable de menor costo unitario (C31=1), asignando hasta saturar la fila o la columna correspondiente: X31=40
O D 1 2 3 4 5 bi Diferencia de costos
A 10 20 5 70 9 X14 10 X15 100 1
B 2 10 50 8 30 X24 5 X25 120 25
C 1 40 20 7 10 X34 4 X35 120 6
dj 40 50 70 90 90 340
Dif de costos
-- -- -- 1 1
Nuevamente calculamos las diferencias de costo y seleccionamos la de mayor valor absoluto, que en este caso corresponde a la fila 2, en l que asignaremos en su variable de menor costo unitario, X25=70
[email protected] Facebook: Giovanny Rodriguez 61
O D 1 2 3 4 5 bi Diferencia de costos
A 10 20 5 70 9 X14 10 X15 100 1
B 2 10 50 8 30 5 70 120 --
C 1 40 20 7 10 X34 4 X35 120 6
dj 40 50 70 90 90 340
Dif de costos
-- -- -- 1 6
El cálculo de las nuevas diferencias de costo señala como variable básica X35 en la que asignaremos hasta saturar la fila o columna correspondiente X35=20
O D 1 2 3 4 5 bi
A 10 20 5 70 9 X14 10 100
B 2 10 50 8 30 5 70 120
C 1 40 20 7 10 X34 4 20 120
dj 40 50 70 90 90 340
Finalmente, completaremos la solución inicial factible con las variables restantes de manera que se satisfagan las restricciones del problema, obteniendo el siguiente resultado:
[email protected] Facebook: Giovanny Rodriguez 62
O D 1 2 3 4 5 bi
A 10 20 5 70 9 30 10 100
B 2 10 50 8 30 5 70 120
C 1 40 20 7 10 60 4 20 120
dj 40 50 70 90 90 340
[email protected] Facebook: Giovanny Rodriguez 63
PROGRAMACIÓN ENTERA
MÉTODO DE EGON Y BALAS (Min):
Este es un método iterativo que permite encontrar soluciones enteras cuando se tienen problemas de más de dos variables.
Pasos de solución:
En la primera iteración iguala cada una de las variables de las restricciones a cero.
Iguala una de las variables de las restricciones a uno (1) y las demás se toman como un valor igual a cero. Continúe repitiendo este punto con cada variable presente.
Cada respuesta se compara al reemplazar cada valor en la restricción y si cumple con el signo que presenta se toma como verdadero, lo cual no se penaliza y se pone cero; de lo contrario se toma como falso y se penaliza con el monto obtenido en valor absoluto. Luego se suma esto y la respuesta es la infactibilidad.
Elije la menor infactibilidad y reemplaza el valor elegido en cada una de las restricciones.
Realiza la segunda iteración realizando cada paso anterior con las nuevas restricciones obtenidas.
Reemplaza en la función objetivo y elije la e menor costo.
[email protected] Facebook: Giovanny Rodriguez 64
EJEMPLO:
Mín W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5
Restricciones:
3X1 - X2 + X3 + X4 - 2X5 - 2 0
X1 + 3X2 - X3 - 2X4 + X5 + 0 0
-X1 - X2 + 3X3 + X4 + X5 - 1 0
Primera iteración:
X1= X2 = X3 = X4 = X5 =0
-20 F 2
00 V 0
-10 F 1
3 infactibilidad
X1=1 X2 = X3 = X4 = X5 =0
10 V 0
10 V 0
-20 F 2
2 infactibilidad
[email protected] Facebook: Giovanny Rodriguez 65
X2=1 X1 = X3 = X4 = X5 =0
-30 F 3
30 V 0
-20 F 2
5 infactibilidad
X3=1 X1 = X2 = X4 = X5 =0
-10 F 1
-10 F 1
20 V 0
2 infactibilidad
X4=1 X1 = X2 = X3 = X5 =0
-10 F 1
-20 F 2
00 V 0
3 infactibilidad
X5=1 X1 = X2 = X3 = X4 =0
-40 F 4
10 V 0
00 V 0
[email protected] Facebook: Giovanny Rodriguez 66
4 infactibilidad
Reemplazo el menor valor de factibilidad en las restricciones:
X1=1
- X2 + X3 + X4 - 2X5 + 1 0
3X2 - X3 - 2X4 + X5 + 1 0
- X2 + 3X3 + X4 + X5 - 2 0
Segunda iteración:
X2=1 X3 = X4 = X5 =0
00 V 0
40 V 0
-30 F 3
3 infactibilidad
X3=1 X2 = X4 = X5 =0
20 V 0
00 V 0
10 V 0
0 infactibilidad
X4=1 X2 = X3 = X5 =0
[email protected] Facebook: Giovanny Rodriguez 67
20 V 0
-10 F 1
-10 F 1
2 infactibilidad
X5=1 X2 = X3 = X4 =0
-10 F 1
20 V 0
-10 F 1
2 infactibilidad
Reemplazo los valores menores e infactibilidad en la función objetivo:
X3=1
X1=1
W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5
=12
X1 = 1
X4 =1
W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5
=13
[email protected] Facebook: Giovanny Rodriguez 68
X1 = 1
X5 =1
W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5
=14
La solución óptima es la de X3=1 y X1=1, ya que es la que representa menor costos