Embed Size (px)
DESCRIPTION
investigacion
Citation preview
INVESTIGACIÓN DE OPERACIONES I
PROGRAMA DE ESTUDIO
Objetivo
Familiarizar al alumno con las técnicas de modelamiento y metodologías de resolución de problemas de la Investigación de operaciones, con especial énfasis en la aplicación de algoritmos de solución para modelos de programación matemática, en especial modelos lineales
Contenido
Introducción • Investigación de operaciones• Modelos matemáticos• Programación Lineal
ProgramaciónLineal
• Formulación de modelos• Métodos Gráfico• Método Simplex• Problema Dual y Análisis de Sensibilidad• Programación Entera, Binaria y Mixta
INVESTIGACION DE OPERACIONESPROGRAMA DEL CURSO
DESCRIPCION
El curso trata principalmente sobre la aplicación de los modelos usuales de Investigación de Operaciones en la solución de problemas reales, tales como modelos de Programación Lineal, Entera, Binaria y Mixta
OBJETIVOS• Aplicar modelos cuantitativos en la resolución de problemas
lineales.• Optimizar soluciones usando la Investigación de Operaciones.
METODOLOGÍA• Clases expositivas para conceptos teóricos con discusiones sobre
cada tema.
• Practicas en laboratorio, donde se conocerán diversos software de apoyo a la Investigación de Operaciones.
BIBLIOGRAFIA
• TAHA HAMDY A. Investigación de operaciones. PEARSON. 9 Ed. 2012
• HILLIER, FREDERICK Y LIEBERMAN, GERALD: “Introducción a la Investigación de Operaciones”, McGraw – Hill Interamericana
• WINSTON WAYNE L.: “Investigación de Operaciones: Aplicaciones y Algoritmos”. Grupo Editorial Iberoamericana.
• DAVIS K ROSCOE y MC KEOWN Patrick. Modelos Cuantitativos para Administración. Grupo editorial Iberoamerica. 2 Ed. 1986.
• PRAWDA, Juan. Métodos y modelos de Investigación de operaciones. Limusa.
• JORGE ALVAREZ ALVAREZ, Investigación de Operaciones, Universidad Nacional de Ingeniería, Edición 2001
INVESTIGACION DE OPERACIONES
Definición:Conjunto de técnicas matemáticas y estadísticas aplicable a diversos sistemas con el fin de mejorarlos, buscando las mejores alternativas de acción; esto mediante el modelamiento matemático de los problemas en estudio.
¿Qué es la investigación de operaciones?
Lawrence y Pasternak, (1998) “Es un enfoque científico para la toma de decisiones ejecutivas, que consiste en:
• El arte de modelar situaciones complejas,• La ciencia de desarrollar técnicas de
solución para resolver dichos modelos.• La capacidad de comunicar efectivamente
los resultados”.
Kamblesh Mathur: “Es el uso de la Matemática y computadoras para ayudar a tomar decisiones racionales frente a problemas de administración”.
Jorge Alvarez: “Es un procedimiento o un enfoque para resolver problemas relacionados con la toma de decisiones”.
¿Qué es la investigación de operaciones?
La Investigación de Operaciones es el uso de la matemática e informática para resolver problemas del mundo real, tomando decisiones acertadas que garanticen el éxito.
La investigación de operaciones tiene como objetivo buscar las soluciones que sean significativamente mas eficientes (en tiempo, recursos , beneficios , costos , etc.)
Toda toma de decisión empieza con la detección de un problema.
Definir el problema en forma clara
Identificar las restricciones
Identificar las alternativas de solución
Formular el o los objetivos
Evaluar las alternativas y elegir la mejor
Para tomar la decisión correcta, se debe:
TOMA DE DECISIONES
Tiende a representar el problema cuantitativamente para poder analizarlo y evaluar un criterio común.
¿Como se elige la mejor alternativa?
¿Como se elige la mejor alternativa?
Métodos Cualitativos
Métodos Cuantitativos
En base a la experiencia y al juicio profesional de la persona que toma la decisión
En base a la utilización de herramientas matemáticas que permitan maximizar la efectividad en la toma de decisiones.
TOMA DE DECISIONES
La dificultad de tomar decisiones ha hecho que el hombre se aboque en la búsqueda de una herramienta o método que le permita tomar las mejores decisiones de acuerdo a los recursos disponibles y a los objetivos que persigue.
Este conjunto de herramientas o métodos es lo que llamaremos Investigación de Operaciones.
“Enfoque científico de la toma de decisiones que requiere la operación de sistemas organizacionales”.
Definición más formal
La IO nos ofrece una serie de herramientas cuantitativas para la toma de decisiones.
La IO nos ofrece una serie de herramientas cuantitativas para la toma de decisiones.
INVESTIGACIÓN DE OPERACIONES
Modelos de IO
Programación Lineal
MétodosClásicos
Determinísticos Híbridos Estocásticos
Transporte yAsignación
Prog Enteray 0,1
Redes
Optimización Lineal
Optimización no Lineal
Métodosde búsqueda
Programación no lineal
ProgramaciónDinámica
Teoría de Inventarios
Simulación
Pert / CPM
Heurísticas
Cadenas de Markov
Teoría de Colas
ProcesosEstocásticos
Teoría de Decisionesy Juegos
MODELOS DE LA INVESTIGACIÓN DE OPERACIONES
¿Qué se busca en el curso de Investigación de Operaciones?
Se intenta encontrar una mejor solución llamada solución óptima.
Areas de Aplicación de la Investigación de Operaciones
Manufactura.
Transporte.
Telecomunicaciones.
Salud.
Planeación.
Servicios.
Finanzas.
Otros.
LA NATURALEZA DE UN SISTEMA
Un sistema es un conjunto de dos o más elementos que satisface las siguientes tres condiciones:
• La conducta de cada elemento tiene un efecto sobre la conducta del todo.
• La conducta de los elementos y sus efectos sobre el todo son interdependientes.
• Sin considerar cómo se formen los subgrupos de elementos, cada uno tiene un efecto sobre la conducta del todo, y ninguno tiene un efecto independiente sobre él.
• Proceso: Conjunto de actividades que crean una salida o resultado a partir de una o más entradas o insumos.
• Sistema: Un conjunto de elementos interconectados utilizados para realizar el proceso. Incluye subprocesos pero también incluye los recursos y controles para llevar a cabo estos procesos.
• En el diseño de procesos nos enfocamos en QUÉ se ejecuta.
• En el diseño del Sistemas el énfasis está en los detalles de CÓMO, DÓNDE Y CUÁNDO.
SISTEMAS V/S PROCESOSSISTEMAS V/S PROCESOS
SISTEMAS V/S PROCESOSSISTEMAS V/S PROCESOS
Entidadesque Entran
Entidadesque Salen
Reglas deOperación(Controles)
Sistema
Recursos
Actividades
Problema
Es identificar, comprender y describir en términos precisos, el problema que la organización enfrenta. El enunciado es la definición del problema. Un problema no se formula sino se define.
Cada vez es más difícil asignar los recursos o actividades de la forma más eficaz
Los recursos son escasos
Los sistemas son cada vez
más complejos
METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES
MÉTODOS EN INVESTIGACIÓN OPERATIVA
• Métodos determinísticos: Programación lineal, programación entera, probabilidad de transporte, teoría de la localización o redes, programación multicriterio, teoría de inventarios, etc.
• Métodos probabilísticos: Cadenas de markov, teoría de juegos, líneas de espera, teoría de inventarios, etc.
• Métodos híbridos: Conjugan métodos determinísticos y probabilísticos.
• Métodos heurísticos: soluciones basadas en la experiencia.
INVESTIGACION DE OPERACIONESClasificación de los modelos según la
Investigación Operaciones• Modelo Matemático
Es aquel modelo que describe el comportamiento de un sistema a través de relaciones matemáticas y supone que todas las variables relevantes son cuantificables. Por ende tiene una solución optima.
• Modelo de Simulación
Es un modelo que imita el comportamiento de un sistema sobre un periodo de tiempo dado, esta basado en observaciones estadísticas. Este tipo de modelo entrega soluciones aproximadas.
• Modelo Heurístico
Es una regla intuitiva que nos permite la determinación de una solución mejorada, dada una solución actual del modelo, generalmente son procedimientos de búsqueda. Este tipo de modelo también entrega soluciones aproximadas.
INVESTIGACION DE OPERACIONESEl Arte del Modelado
La Investigación de Operaciones debe ser considerada como una ciencia y la vez como un arte.
• Una ciencia por el uso de técnicas matemáticas para la resolución de los problemas.
• Un arte ya que la formulación del modelo depende en gran parte de la creatividad y la experiencia de las operaciones del equipo investigador.
ELEMENTOS PARA FORMULACIÓN DE PROBLEMAS
Habilidad para describir el diseño en términos matemáticos
• Variables• Parámetros• Funciones
VARIABLES DE DISEÑO
• Las variables de diseño son aquellas que asumen más de un valor o estado durante el rango de validez del modelo.
• Los valores del conjunto de estas variables caracterizan un diseño particular
• Cambian en un determinado rango a medida que buscamos el diseño óptimo
• Son las incógnitas del problema Tamaño de un objeto, número de objetos, …
• Deben ser linealmente independientes
VARIABLES DE DISEÑO
• El conjunto de variables de diseño se identifica como vector de diseño
• Nomenclatura [ X ] X ó x [x1, x2, …, xn]
xi, i = 1,2,…,n
FUNCIÓN OBJETIVO
• Problema: “Minimizar o maximizar cierta cantidad que se calcula con una función”
• Un problema de maximización se puede convertir en uno de minimización sin más que cambiar el signo de la función objetivo
• Nomenclatura: f f(x1, x2, …, xn) o f(X)
PARÁMETROS DE DISEÑO
• Parámetros de diseño son aquellos que no cambian o no pueden cambiar su valor durante el rango de validez del modelo matemático o físico de un proceso.
• Constantes que no cambian para los diferentes diseños
• Importantes en modelo pero no en la búsqueda del diseño óptimo
• Nomenclatura: [ P ] P [p1, p2, …, pq]
RESTRICCIONES
• Comparación con un valor numérico que limita
• Tipos: De igualdad: = De desigualdad: ,
• Ejemplo 1 Volumen de la lata: fun1(X) = 500 cm3
• Ejemplo 2 Deflexión: fun2(X) 1 mm
RESTRICCIONES
• Si las restricciones no se cumplen No hay solución
• Diseño factible Todas las restricciones se satisfacen
• Un diseño óptimo debe ser factible
• El espacio definido por las restricciones se llama dominio factible
FORMATO ESTÁNDAR
• Minimizar f(x1, x2, …, xn)
• Sujeto a hk(x1, x2, …, xn) = 0, k=1,2,…,l
gj (x1, x2, …, xn) 0, j=1,2,…,m
xil xi xi
u, i=1,2,…,n
• Lenguaje natural “Minimizar la función objetivo f, sujeto a 1 restricciones
de igualdad, m restricciones de desigualdad, con n variables de diseño comprendidas entre unos límites inferior y superior”
MODELADO EJEMPLO 1
• Variables de diseño: d, h• Parámetro de diseño: C (coste del material por unidad área)• Volumen = d2h/4• Área = dh• Restricción “estética”: h2d
h
d
MODELO EJEMPLO 1
• Minimizar f(d,h): Cdh
Sujeto a h1(d,h): d2h/4 – 500 = 0
g1(d,h): 2d – h 0
6 d 9; 5 h 20
• Minimizar f(x1,x2): Cx1x2
Sujeto a h1(x1,x2): x1
2x2/4 – 500 = 0
g1(x1,x2): 2x1 – x2 0
6 x1 9; 5 x2 20
Para la aplicación de la IO se siguen los siguientes pasos:
• La IO comienza con la observación cuidadosa de la realidad.
• Formular el problema.
• Construir un modelo que intente abstraer la esencia del problema real.
• Solución del modelo.
• Análisis de sensibilidad, hay que ver como se comporta el modelo ante cambios en las restricciones y/o parámetros del modelo
• Implementar los resultados, se debe interpretar los resultados y dar conclusiones y cursos de acción para la optimización del problema real
INVESTIGACIÓN DE OPERACIONES
Desarrollo de un modelo matemático Es la traducción del problema a términos matemáticos.
Es formular un modelo matemático:Identificando variablesIdentificando la Función Objetivo Identificando las restricciones
Objetivos: función objetivoalternativas: variables de decisiónlimitaciones del sistema: restricciones
METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES
I) Identificacion de las variables Xij = # de consultores que viajan del origen i al destino j II) Identificacion de la funcion objetivo Max 540X11+300X12+420X13+ 500X21+330X22+330X23+ 520X31+310X32+350X33 III) Identificacion de las restricciones X11+X12+X13 ≤ 2 X21+X22+X23 ≤ 1 X31+X32+X33 ≤ 4 X11+X21+X31 = 3 X12+X22+X32 = 2 X13+X23+X33 = 1 Xij ≥ 0 ; entero
Desarrollo de un modelo matemático
Paso 1. Identificar las variables de decisión¿Sobre qué tengo control?¿Qué es lo que hay que decidir?¿Cuál sería una respuesta válida del caso?
Paso 2. Identificar la función objetivo¿Qué pretendemos conseguir?¿qué me interesaría más?
Paso 3. Identificar las restricciones o factores que limitan la decisión, recursos disponibles
(trabajadores, máquinas, material), fechas límite, naturaleza de las variables (no negatividad, enteras, binarias).
Paso 4.Traducción de los elementos básicos a un modelo matemático.
METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES
Resolución del modelo
Es resolver el modelo usando una técnica adecuada, es decir obtener valores numéricos para la variable de decisión.
Es determinar los valores de las variables de decisión de modo que la solución sea óptima (o satisfactoria) sujeta a las restricciones.
Puede haber distintos algoritmos y formas de aplicarlos. En esta parte se usa el Software WIN QSB. Hay otros como el LINDO, MLP y TORA
METODOLOGÍA DE LA INVESTIGACION DE OPERACIONES
Un método óptimo para lograr un objetivo.Una forma de evaluar preguntas de sensibilidad de la forma: ¿Qué sucedería sí ...?
VENTAJA DE LOS MODELOS
EL MODELO DE PROGRAMACIÓN LINEAL PROVEE UNA SOLUCIÓN INTELIGENTE PARA ESTE
PROBLEMA
Es un Arte que mejora con la práctica…
¡ PRACTIQUEMOS!
Hoy en día, la toma de decisiones abarca una gran cantidad de problemas reales cada más complejos y especializados, que necesariamente requieren del uso de metodologías para la formulación matemática de estos problemas y, conjuntamente, de métodos y herramientas de resolución, como los que provee la Investigación de Operaciones.
La Programación Lineal es una herramienta para resolver problemas de optimización que se caracterizan por tener como función objetivo y restricciones combinaciones lineales de las variables de decisión.
Función Objetivo: Max o Min (Z) = C X
Sujeto a : A X B Xi 0 ; i = 1, 2,...., n
Conceptos Básicos:
• Variables de Decisión• Función Objetivo• Restricciones• Restricciones de Signo
FORMULACION DE UN PROBLEMA PROGRAMACIÓN LINEAL
Consideremos los siguientes ejemplos para describir los conceptos básicos presentes en todo problema de programación lineal (PPL)
CONSTRUCCIÓN DE MODELOS DE PROGRAMACION LINEAL
Ejemplo N° 1
La Compañía PARGOLF es un pequeño fabricante de equipo y suministros para golf. El distribuidor de PARGOLF cree que existe un mercado tanto para una bolsa de golf de precio moderado, denominada modelo estándar, como para una bolsa de precio elevado, denominada modelo de lujo. El distribuidor está tan confiado en el que, si PARGOLF puede hacer las bolsas a un precio competitivo, el distribuidor comprará todas las bolsas que PARGOLF pueda fabricar durante los siguientes tres meses. Un análisis cuidadoso de los requerimientos de tiempo de producción para las cuatro operaciones de manufactura y la estimación hecha por el departamento de contabilidad de la contribución a la ganancia por bolsa.
Producto
Estándar
De lujo
Corte y teñido Costura Terminado
Inspección y empaque
Ganancia por bolsa
7/10
1
1/2
5/6
1
2/3
1/10
1/4
S/. 10
S/. 9
Tiempo de producción (horas/bolsa)
El director de manufactura estima que dispondrán de 630 horas de tiempo de corte y teñido, 600 horas de tiempo de costura, 708 horas de tiempo de terminado y 135 horas de tiempo de inspección y empaque para la producción de bolsas de golf durante los siguientes tres meses.
a) Si la compañía desea maximizar la contribución a la ganancia total, ¿Cuántas bolsas de cada modelo debería fabricar?
b) ¿Cuántas horas de tiempo de producción se programaran para cada operación?
c) ¿Cuántas horas de tiempo de ocio se tendrán en cada operación?
Formulación:
Variable de decisión:
Xi = Número de bolsas de modelo i a fabricar por trimestre i = 1, 2
Objetivo:
Maximizar: Ganancia/trimestre
Restricciones:
Tiempo disponible por trimestre
Corte y teñido
Corte
Acabado
Condiciones técnicas.
X1, X2 > 0
Inspección y empaque
Modelo Matemático de Programación Lineal:
Máx: Ganancia
Max. (Z) = 10X1 + 9X2
Sujeto a:
7/10X1 + X2 < 630 Corte y teñido
1/2X1 + 5/6X2 < 600 Costura
X1 + 2/3X2 < 708 Acabado
X1, X2 > 0
S/.
Trimestre = S/.
Bolsa
Bolsa
Trimestre
Hora
Bolsa
Bolsas
Trimestre=
Horas
Trimestre
1/10X1 + 1/4X2 < 135 Inspección y empaque
Ejemplo N° 2: El problema de la industria de juguetes “Galaxia”.
• Galaxia produce dos tipos de juguetes:
* Space Ray
* Zapper
• Los recursos están limitados a:
* 1200 libras de plástico especial.
* 40 horas de producción semanalmente.
• Requerimientos de Marketing.
* La producción total no puede exceder de 800 docenas.
* 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 libras de plástico y 3 minutos de
producción por docena.
* Zappers requiere 1 libra de plástico y 4 minutos de producción
por docena.
• Plan común de producción para:
* Fabricar la mayor cantidad del producto que deje mejores
ganancias, el cual corresponde a Space Ray (S/. 8 de utilidad
por docena).
* Usar la menor cantidad de recursos para producir Zappers,
porque estos dejan una menor utilidad (S/. 5 de utilidad por
docena).
Solución
• 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.
• 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)
• El plan común de producción consiste en:Space Rays = 550 docenas
Zappers = 100 docenas
Utilidad = S/. 4900 por semana
EJEMPLO N° 3
Una firma industrial elabora dos productos, en los cuales entran cuatro componentes en cada uno. Hay una determinada disponibilidad de cada componente y un beneficio por cada producto. Se desea hallar la cantidad de cada articulo que debe fabricarse con el fin de maximizar los beneficios.
El siguiente cuadro resume los coeficientes de transformación o sea la cantidad de cada componente que entra en cada producto.
Producto Componente
P1 P2 Disponibilidad (kilogramos)
A B C D
1 2 2 1
3 1 2 1
15,000 10,000 12,000 10,000
Beneficios S/./unidad
4 3
X1 = Nº de unidades de producto P1
X2 = Nº de unidades de producto P2
Entonces el programa lineal correspondiente es:
Max (Z) = 4X1 + 3X2
Sujeto a :
1X1 + 3X2 ≤ 15,000
2X1 + 1X2 ≤ 10,000
2X1 + 2X2 ≤ 12,000
1X1 + 1X2 ≤ 10,000
X1, X2 ≥ 0
EJEMPLO Nº 4
En una fábrica de cerveza se producen dos tipos: rubia y negra. Su precio de venta es de S/. 0.5 / litro y S/. 0.3 / litro, respectivamente. Sus necesidades de mano de obra son de 3 y 5 empleados, y de 5,000 y 2,000 soles de materias primas por cada 10,000 litro.
La empresa dispone semanalmente de 15 empleados y 10,000 soles para materias primas, y desea maximizar su beneficio. ¿Cuántos litros debe producir?
FORMULACIÓN
1 2Max (Z) = 5,000X + 3,000X
1 2
1 2
1 2
S. A.
3X + 5X 15
5,000X + 2,000X 10,000
X , X 0
Una mueblería produce mesas y sillas de madera. Cada mesa es vendida en $27.000 y se requiere $10.000 en materiales para su construcción, además, el costo unitario por mano de obra es de $14.000. En el caso de las sillas, el precio de venta es de $21.000 y los costos de materiales y mano de obra son $9.000 y $10.000 respectivamente.
La fabricación de cada producto requiere de dos labores: carpintería y terminaciones. Una mesa requiere de 1 hora de carpintería y 2 de terminaciones, mientras que la silla requiere de 1 hora en cada labor.
Ejemplo N° 5
Cada semana, la mueblería puede obtener todos los materiales que desee, sin embargo, se pueden dedicar hasta 100 horas a las terminaciones y hasta 80 horas a la carpintería. La demanda por mesas no está limitada, mientras que la demanda por sillas es de 40 unidades.
Formule un modelo matemático que permita maximizar las utilidades de la mueblería.
Variables de decisión: Variables de decisión:
Se debe comenzar definiendo las variables de decisión relevantes. En un PPL las variables de decisión deben ser capaces de describir completamente las decisiones que puedan ser tomadas y todas las variantes que existan.
Formulación
Antes de definir las variables de decisión es importante definir las unidades involucradas en el problema.
En este caso, se habla de unidades de sillas y mesas, de horas de trabajo por unidad y de demanda semanal. De acuerdo a ello, una buena opción para definir las variables de decisión consiste en asociar las variables al número de unidades de sillas y mesas a producir por semana. Por lo tanto, podemos definir:
X1 = Número de mesas producidas por semana.X2 = Número de sillas producidas por semana.
X1 = Número de mesas producidas por semana.X2 = Número de sillas producidas por semana.
Función Objetivo: Función Objetivo:
En un PPL, se debe tomar la decisión de maximizar (usualmente las utilidades) o de minimizar (usualmente los costos) cierta función de las variables de decisión.
En el ejemplo, los costos e ingresos no dependen del valor de X1 o X2 por lo tanto basta concentrarse en maximizar la diferencia entre:
La función que se va a optimizar se llama Función Objetivo y en ella no aparece ningún término independiente o constante. Los valores de las variables de decisión son independientes de cualquier constante.
Ingresos Semanales – Costos de Materiales – Costos por mano de obraIngresos Semanales – Costos de Materiales – Costos por mano de obra
Luego se deben expresar los términos anteriores en función de las variables de decisión X1 y X2.
Por lo que la función objetivo queda (expresada en miles de $):
(27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2 (27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2
Así, el objetivo de la mueblería es escoger los valores X1 y X2 tal que se maximice 3X1 + 2X2
Denotando por Z el valor de la Función Objetivo para cualquier Problema de Programación Lineal, la función de la mueblería es:
Max Z = 3X1 + 2X2 Max Z = 3X1 + 2X2
El coeficiente que acompaña a cada variable en la Función Objetivo se denomina coeficiente en la función objetivo de la variable y refleja el aporte unitario de dicha variable.
Restricciones: Restricciones:
En las medidas que las variables crecen, la Función Objetivo aumenta su valor. Por lo tanto si se pudiera escoger arbitrariamente el valor de la variables, la mueblería podría hacer crecer el valor de sus utilidades en forma infinita. En la práctica esto no es posible y en el ejemplo el valor que toman las variables está limitado por las siguientes 3 restricciones:
• Máximo 100 horas semanales para terminaciones.• Máximo 80 horas semanales para carpintería.• Producción máxima de 40 sillas semanales.
Luego, el próximo paso consiste en formular matemáticamente las restricciones anteriores en función de las variables de decisión.
Para formular la primera restricción en función de las variables X1 y X2 observamos que:
Hrs. terminaciones x mesa + hrs. terminaciones x silla hrs. disponibles para terminaciónHrs. terminaciones x mesa + hrs. terminaciones x silla hrs. disponibles para terminación
Por lo que la restricción queda:
2X1 + X2 1002X1 + X2 100
Es importante notar que todos los valores en la expresión anterior son por semana, ya que las variables de decisión se han escogido con esa referencia.
Análogamente la segunda restricción queda:
X1 + X2 80X1 + X2 80
Finalmente, la tercera restricción sólo limita el valor de la variable X2
X2 40X2 40
Restricciones de Signo: Restricciones de Signo:
Para completar la formulación del modelo es importante definir si existe alguna restricción de signo para cada variable de decisión.
Si una variable de decisión Xi debe cumplir condiciones de NO NEGATIVIDAD, debemos agregar la siguiente restricción:
Xi 0Xi 0
Si la variable de decisión Xi puede asumir valores positivos o negativos se dice que Xi no tiene restricción de signo (SRS).
Combinando todas las expresiones anteriores, es posible completar el modelo matemático para este problema de optimización, quedando de la siguiente forma:
En el ejemplo ambas variables de decisión se refieren a cantidades a producir, por lo tanto son no negativas. Sin embargo, en otros ejemplos las variables pueden ser SRS, por ejemplo en el caso de que Xi se refiere al saldo de alguna cuenta.
Definición de variables:
X1: número de mesas producidas por semana.X2: número de sillas producidas por semana.
Función Objetivo:
Max Z = 3X1 + 2X2
Sujeto a:
2X1 + X2 100 Horas disponibles para terminaciones por semana
X1 + X2 80 Horas disponibles para carpintería por semana
X2 40 Producción máxima de sillas por semana
Xj 0 j = 1 y 2 No negatividad
Sujeto a:
. . . . .
. . . . .
. . . . .
X1,2,.....n > 0
Variables de decisiónCoeficientes objetivo
Coeficientes tecnológicos Coeficientes recurso
Condiciones técnicas o
No negatividad
MODELO GENERAL DE PROGRAMACIÓN LINEAL
nnXCXCXCMax(Z)
Optimizar
+++= ......2211
22222121
1
),,(..... bXaXaXann
≥=≤+++
1212111),,(..... bXaXaXa
nn≥=≤+++
mnmnmm bXaXaXa ),,(.....
2211≥=≤+++
• Donde el vector c también conocido como el vector costos, viene dado por:
• El vector de lado derecho o b, viene dado por:
• Este es un vector columna, que representa los recursos de las m actividades. Es por lo tanto el elemento de la mano derecha de cada una de las m ecuaciones.
...1 2 n-1 nC = c c c c
1
2
m-1
m
b
b
.b
.
b
b
• La matriz A, representa los coeficiente tecnológicos; es la matriz para el sistema de ecuaciones Ax = b:
• El sistema de ecuaciones o el modelo de PL, queda representado por:
Max (Z) = C X
Sujeto a:
A X = bi
A X ≤ bi
A X ≥ bi
X ≥ 0
A
11 12 1n
21 22 2n
m,1 m,2 m,n
a a ... a
a a ... a
. . ... .
a a ... a
EL MODELO DE P.L.
Z: función objetivoC (c1,...,cn): vector de coeficientes de la f. o.X (x1,...,xn): vector de variables de decisiónA (...,aij,...): matriz de coeficientes técnicosb (b1,...,bm): vector de demandas
Matricialmente,
Optimización Max o Min = CXS.A.
AX bx 0 Forma canónica
Problema N° 1
Variables de Decisión
X1 = Cantidad de Manteles comprados (sólo se puede comprar el
primer día).
X2 = Cantidad de Manteles mandados a lavar en servicio rápido el primer día.
X3 = Cantidad de Manteles mandados a lavar en servicio normal el primer día.
X4 = Cantidad de Manteles mandados a lavar en servicio rápido el segundo día.
Día 1(40)
Día 2(70)
Día 3(60)
X1
X2 X4
X3
Restricciones.a) Satisfacción de la necesidad de manteles al primer día X1 ≥ 40b) Satisfacción de la necesidad de manteles al segundo día. (X1 − 40) + X2 ≥ 60 ↔ X1 + X2 ≥ 100c) Satisfacción de la necesidad de manteles al tercer día. (X1 − 40) + X2 − 60 + X3 + X4 ≥ 70 ↔ X1 + X2 + X3 + X4 ≥ 170d) El número de manteles mandados a lavar el primer día, puede a l
o mas ser igual al número de manteles usados ese día. X2 + X3 ≥ 40e) El número de manteles mandados a lavar hasta el segundo día,
puede a lo mas ser igual al número de manteles usados hasta ese día.
X2 + X3 + X4 ≥ 40 + 60 ↔ X2 + X3 + X4 ≥ 100f ) No negatividad. X1, X2, X3, X4 ≥ 0
Función ObjetivoMin (Z) = 20X1 + 15X2 + 8X3 + 15X4
Problema N° 2
Variables de DecisiónX1 = numero de libras de carne molida de res empleadas en cada libra de albóndigas.X2 = numero de libras de carne molida de cerdo empleadas en cada libra de albóndigas. Restricciones
Cada libra de albóndigas tendrá 0.20 X1, libras de grasa provenientes de la carne de res y 0.32 X2 libras de grasa de la carne de cerdo. El contenido total de grasa de una libra de albóndigas no debe ser mayor de 0.25 libras. Entonces:
0.20X1 + 0.32X2 ≤ 0.25 El número de libras de carne de res y de cerdo empleadas en cada libra de albóndigas debe sumar 1; entonces:
X1 + X2 = 1Finalmente, la tienda no puede usar cantidades negativas de ninguna de las carnes, así que hay dos restricciones de no negatividad: X1≥ 0 y X2 ≥ 0.
Función Objetivo
Min (Z) = 80X1 + 60X2
Problema N° 3
• Variables de decisiónX1: Unidades de A producidas en totalX2: Unidades de B producidas en totalX3: Unidades de C producidas en totalX4: Unidades de A vendidasX5: Unidades de B vendidas
• Función Objetivo
Max (Z) = 700 X4 + 3,500 X5 + 7,000 X3
• Restricciones
Sujeto a:
X1 + 2X2 + 3X3 ≥ 40
X1 = X4 + 2X2
X2 = X5 + X3
X1, X2, X3, X4, X5 ≥ 0
Problema N° 5
Un fabricante cuyo negocio es mezclar aguardiente, compra tres grados A, B, y C. Los combina de acuerdo a las recetas que especifican los porcentajes máximo y mínimo de los grados A y C en cada mezcla. Estos porcentajes se dan en la tabla N° 1.
La provisión de los tres grados de aguardientes básicos, junto con sus costos se presente en la tabla N° 2.
TABLA N° 2 DISPONIBILIDAD Y COSTOS DE AGUARDIENTE
AGUARDIENTEMAXIMA CANTIDAD
DISPONIBLEBOTELLAS POR DIA
COSTO POR BOTELLA
A 2000 S/. 7.00
B 2500 S/. 5.00
C 1200 S/. 4.00
TABLA N° 1 ESPECIFICACIONES DE MEZCLAS
MEZCLA ESPECIFICACION PRECIO POR BOTELLA
Súper FuerteNo menos de 60% de ANo mas de 20% de C
S/. 6.80
FuerteNo más de 60% de CNo menos de 15% de A
S/. 5.70
Menos Fuerte No más de 50% de C S/. 4.50
Indique cómo se obtiene la primera matriz en un modelo de programación lineal de una política de producción que haga máxima la ganancia.
Solución
X11 : Cantidad de A usada para el super fuerteX21 : Cantidad de B usada para el super fuerteX31 : Cantidad de C usada para el super fuerteX12 : Cantidad de A usada para el fuerteX22 : Cantidad de B usada para el fuerteX32 : Cantidad de C usada para el fuerte
Max (Z) = 6.80 (X11 + X21 + X31) + 5.7 (X12 + X22 + X32) – [ 7(X11 + X12) + 5(X21 + X22) + 4(X31 + X32)]Sujeto a:X11 + X12 ≤ 2,000X21 + X22 ≤ 2,500 DisponibilidadX31 + X32 ≤ 1,200
X11 ≥ 0.60 (X11 + X21 + X31) X31 ≤ 0.20 (X11 + X21 + X31)
X32 ≤ 0.60 (X12 + X22 + X32)
X12 ≥ 0.15 (X12 + X22 + X32)
Xij ≥ 0 : i = 1, 2, 3 ; j = 1, 2
Problema N° 6
Una compañía fabrica dos clases de cinturones de piel. El cinturón A es de alta calidad, y el cinturón B es de baja calidad. La ganancia respectiva por cinturón es de S/. 0.40 y S/. 0.30. Cada cinturón de tipo A requiere el doble de tiempo que el que usa el de tipo B, y si todos los cinturones fueran de tipo B, la compañía podría fabricar 1000 día, el abastecimiento de piel es suficiente únicamente para 800 cinturones diarios (A y B combinados) el cinturón A requiere una hebilla elegante, de las que solamente se dispone 400 diarias. Se tiene únicamente 700 hebillas al día para el cinturón B. Establezca las ecuaciones de programación lineal para el problema.
Tipo de cinturón Ganancia Disponibilidad
S/. / Cin hebillas/día
A 0.4 400
B 0.3 700
Xi: Número de cinturones producidos por día del tipo i; donde i =
A, B
tA = 2tB
FUNCIÓN OBJETIVO: Max (Z) = 0.4 XA + 0.3 XB
Sujeto a:
2 XA + XB ≤ 1,000
XA + XB ≤ 800
XA ≤ 400
XB ≤ 700
XA, XB ≥ 0
Problema N° 5
Un fabricante cuyo negocio es mezclar aguardiente, compra tres grados A, B, y C. Los combina de acuerdo a las recetas que especifican los porcentajes máximo y mínimo de los grados A y C en cada mezcla. Estos porcentajes se dan en la tabla N° 1.
La provisión de los tres grados de aguardientes básicos, junto con sus costos se presente en la tabla N° 2.
TABLA N° 2 DISPONIBILIDAD Y COSTOS DE AGUARDIENTE
AGUARDIENTEMAXIMA CANTIDAD
DISPONIBLEBOTELLAS POR DIA
COSTO POR BOTELLA
A 2000 S/. 7.00
B 2500 S/. 5.00
C 1200 S/. 4.00
TABLA N° 1 ESPECIFICACIONES DE MEZCLAS
MEZCLA ESPECIFICACION PRECIO POR BOTELLA
Súper FuerteNo menos de 60% de ANo mas de 20% de C
S/. 6.80
FuerteNo más de 60% de CNo menos de 15% de A
S/. 5.70
Menos Fuerte No más de 50% de C S/. 4.50
Indique cómo se obtiene la primera matriz en un modelo de programación lineal de una política de producción que haga máxima la ganancia.
Solución
X11 : Cantidad de A usada para el super fuerteX21 : Cantidad de B usada para el super fuerteX31 : Cantidad de C usada para el super fuerteX12 : Cantidad de A usada para el fuerteX22 : Cantidad de B usada para el fuerteX32 : Cantidad de C usada para el fuerte
Max (Z) = 6.80 (X11 + X21 + X31) + 5.7 (X12 + X22 + X32) – [ 7(X11 + X12) + 5(X21 + X22) + 4(X31 + X32)]Sujeto a:X11 + X12 ≤ 2,000X21 + X22 ≤ 2,500 DisponibilidadX31 + X32 ≤ 1,200
X11 ≥ 0.60 (X11 + X21 + X31) X31 ≤ 0.20 (X11 + X21 + X31)
X32 ≤ 0.60 (X12 + X22 + X32)
X12 ≥ 0.15 (X12 + X22 + X32)
Xij ≥ 0 : i = 1, 2, 3 ; j = 1, 2
Problema N° 7
Mineral N° 1
Mineral N° 2
X1 = toneladas de mineral 1 en el molde
X2 = toneladas de mineral 2 en el molde
Mineral 1 Mineral 2
Hierro forjado 60% 13%
Plomo 10% 3%
Min (Z) = 260 X1 + 80 X2
Sujeto a:
0.60 X1 + 0.13 X2 ≥ 0.20 (X1 + X2)
0.10 X1 + 0.03 X2 ≥ 0.05 (X1 + X2)
X1, X2, ≥ 0
Problema N° 8
Una industria de muebles requiere de 350 barras de 2x4x20 cm. y de 200 barras de 2x3x20 cm., si dicha empresa dispone de barras cuyas dimensiones son 7x5x20 cm., cual debe ser el programa que debe seguir para minimizar desperdicios sabiendo que el máximo debe ser de 140 cm3.
Solución
2
3 3
2
1
1
2
2
3 4
1
3 4
3
2
2 2 2 1
2 2 2 1
3 3
3
2
2 2 2
4
1
1
X1
X2X3
20
7
5
140 cm3 = 7 cm2
20 cm
350 2 x 4 x 20
200 2 x 3 x 20
Xi = cantidad de barras a obtenerse en la modalidad de corte i
Min (Z) = 100 X1 + 60 X2 + 140 X3
X1 X2 X3
2 x 4 x 20 0 1 2
2 x 3 x 20 5 4 2
Sujeto a:
X2 + 2 X3 ≥ 350
5 X1 + 4 X2 + 2 X3 ≥ 200
X1, X2, X3 ≥ 0
Problema N° 9
Un fabricante de láminas metálicas recibe un pedido para producir 2000 láminas de tamaño 2’ x 4’ y 1000 láminas de tamaño 4’ x 7’. Se dispone de dos láminas estándar de tamaño 10’ x 3000’ y 11’ x 2000’. El personal del departamento de ingeniería decide que los tres siguientes patrones de corte son adecuados para satisfacer el pedido y minimizar el desperdicio. Formule el problema como un modelo de programación lineal.
2' 72' 2' 7'
4'
Patron N° 1 Patron N° 2
4'
Patron N° 3
2' 2' 2' 2' 2'
4'
Solución
4
2
7
1
2
2
7
4
1
Láminas 2 x 4 2,000 10’ x 3,000’
4 x 7 1,000 11’ x 2,000’
Xij = Cantidad de patrones i utilizado para cortar
en la lámina j
Sujeto a:
2’ x 4’ 1 X11 + 5 X31 + 2 X22 + 5 X32 ≥ 2,000
4’ x 7’ 1 X11 + 0 X31 + 1 X22 + 0 X32 ≥ 1,000
X11 + X31 ≥ 3,000/4
X22 + X32 ≥ 2,000/4 X11, X31, X22, X32 ≥ 0
Min (Z) = 4 X11 + 0 X31 + 0 X22 + 4 X32
2
3
3
750 para cortar
500 para cortar
Problema N° 10
• El Real Hotel opera los 7 días a la semana. Las mucamas son contratadas para trabajar seis horas diarias. El contrato colectivo especifica que cada mucama debe trabajar 5 días consecutivos y descansar 2 días. Todas las mucamas reciben el mismo sueldo semanal. El Real hotel requiere como mínimo las horas de servicio.
Lunes 150, Martes 200, Miércoles 400, Jueves 300, Viernes 700, Sábado 800 y Domingo 300. El administrador desea encontrar un plan de programación de empleos que satisfaga estos requerimientos y a un costo mínimo.
Formule este problema como un modelo de programación lineal.
Solución
L Ma Mi J V S D L Ma Mi J V S D L Ma Mi J XL
XMa
XMi
XJ
XV
XS
XD
XL
XMa
XMi
XJ
XV
XS
XV
Continuación…..
Xi = Número de mucamas que empiezan a trabajar el día i durante
cinco dias consecutivos
XJ + XV + XS + XD + XL ≥ 150 / 6 XV + XS + XD + XL + XMa ≥ 200 / 6
XS + XD + XL + XMa+ XMi ≥ 400 / 6 XD + XL + XMa+ XMi+ XJ ≥ 300 / 6
XL + XMa+ XMi+ XJ + XV ≥ 700 / 6 XMa+ XMi+ XJ + XV +XS ≥ 800 / 6 XMi+ XJ + XV +XS + XD ≥ 300 / 6XL , XMa, XMi, XJ , XV , XS , XD ≥ 0
Min (Z) = XL + XMa+ XMi+ XJ + XV + XS + XD
Problema
• El hospital ESSALUD ha decidido ampliar su servicio de urgencias (abierto las 24 horas) con la consiguiente necesidad de nuevo personal de enfermería. La gerencia del hospital ha estimado las necesidades mínimas de personal por tramos horarios para poder cubrir las urgencias que se presenten. Se definieron 6 tramos de 4 horas. La necesidad mínima de personal en cada tramo se indica en el cuadro mostrado. Por otro lado, el departamento de recursos humanos ha informado a gerencia que los contratos laborales han de ser de ocho horas seguidas, según el Convenio firmado con los sindicatos, independientemente de los horarios de entrada y salida del personal.
El problema es encontrar el número mínimo de personal necesario para cubrir la
demanda.
Cuadro: Necesidades de personal por tramos horarios
J Tramos Horarios
1 0:00 - 4:00
2 4:00 – 8:00
3 8:00 – 12:00
4 12:00-16:00
5 16:00-20:00
6 20:00-24:00
Personal Nj
9 5 3 7 5 6
Solución
Min (Z) = X1 + X2 + X3 + X4 + X5 + X6
Sujeto a:
X1 + X2 ≥ 5
X2 + X3 ≥ 3
X3 + X4 ≥ 7
X4 + X5 ≥ 5
X5 + X6 ≥6
X6 + X1 ≥ 9
Xj ≥ 0, j= 1,...,6
Cuadro: Necesidades de personal
Hora Tramos Horarios
1 0:00 - 4:00
2 4:00 – 8:00
3 8:00 – 12:00
4 12:00-16:00
5 16:00-20:00
6 20:00-24:00
0:00 4:00 8:00
12:00 16:00 20:00
X1
X6
X1 X2
X2 X3
X3 X4
X4 X5
X5 X6
Personal Nj
9 5 3 7 5 6
ProblemaDos aleaciones, A y B, están hechas de cuatro metales diferentes: I, II, III y IV, según las especificaciones siguientes:
Los cuatro metales se extraen de tres minerales metálicos diferentes:
Suponiendo que los precios de venta de las aleaciones A y B son US$ 200 y US$ 399 por tonelada, formule el problema como un modelo de programación lineal.
Sugerencia: supóngase que Xijk representa el número de toneladas del i-ésimo metal obtenido de la j-ésimo mineral metálico y asignado a la k-ésima aleación.
Aleación Especificaciones
A B
Cuando mucho el 80% de I Cuando mucho el 30% de II Por lo menos el 50% de IV Entre 40% y el 60% de II Cuando menos el 30% de III A lo más el 70% de IV
Mineral
Capacidad máxima (ton)
Constituyentes (%) Precio (US$ / ton)
I II III IV Otros
1 2 3
1000 2000 3000
20 10 5
10 20 5
30 30 70
30 30 20
10 10 0
30 40 50
Solución
Xijk = número de toneladas del i – esimo metal obtenido de la j – esimo mineral metálico
asignado a la k – esima aleación
Max (Z) = [(X11A + X21A + X31A + X41A + X12A + X22A + X32A + X42A + X13A + X23A + X33A + X43A)200
(X11B + X21B + X31B + X41B + X12B + X22B + X32B + X42B + X13B + X23B + X33B + X43B)399] - (X11A + X21A + X31A + X41A )30 – (X11B + X21B + X31B + X41B)30 – (X12A + X22A + X32A +
X42A)40 - (X12B + X22B + X32B + X42B)40 – (X13A + X23A + X33A + X43A)50 – (X13B + X23B + X33B + X43B)50
Sujeto a:
X11A + X21A + X31A + X41A + X11B + X21B + X31B + X41B ≤ 1,000
X12A + X22A + X32A + X42A + X12B + X22B + X32B + X42B ≤ 2,000 Disponibilidad
X13A + X23A + X33A + X43A + X13B + X23B + X33B + X43B ≤ 3,000
X11A + X12A + X13A ≤ 0.80 [X11A + X21A + X31A + X41A + X12A + X22A + X32A + X42A + X13A +
X23A + X33A + X43A]
Xijk ≥ 0
Problema N° 11
La Compañía XYZ produce tornillos y clavos. La materia Prima para los tornillos cuesta S/. 2 por unidad, mientras que la materia prima para el clavo cuesta S/. 2.50. Un clavo requiere dos horas de mano de obra en el departamento N° 1 y tres en el departamento N° 2, mientras que un tornillo requiere 4 horas en el departamento N° 1 y 2 horas en departamento N° 2, el jornal por hora en ambos departamentos es de S/. 2. Si ambos productos se venden a S/. 18, y el número de horas de mano de obra disponibles por semana en los departamentos son de 160 y 180 respectivamente. Expresar el problema propuesto como un programa lineal, tal que maximice las utilidades.
DPTO 1 DPTO 2 MATERIA
PRIMA JORNAL PRECIO
Clavos 2 hrs. 3 hrs. S/. 2 / unid S/. 2 / hora S/. 18 / unid. Tornillo 4 hrs. 2 hrs. S/. 2.5/unid. S/. 2 / hora S/. 18 / unid Disponibilidad 160 hrs./sem. 180 hrs./sem.
Solución
X1 : unidades de clavos a producirse por semana
X2 : unidades de tornillos a producirse por semana
Max (Z) = 18(X1 + X2) – [10 X1 + 2 X1 + 12 X2 + 2.5 X2]
Sujeto a:
2 X1 + 4 X2 ≤ 160
3 X1 + 2 X2 ≤ 180
X1 , X2 ≥ 0
Problema N° 12
Xi : cantidad de unidades del tipo i a ser fabricados para ser vendidos a la semana
i : 1, 2, y 31 = válvula globo2 = válvula aguja3 = módulo
Max (Z) = 10 X1 + 20 X2 + 60 X3
Sujeto a:
10X1 + 15X2 + (25 + 2 x 10)X3 ≤ 25,000
5X1 + 5X2 + (10 + 2 x 5) X3 ≤ 15,000
5X1 + 5X2 + 10 X3 ≤ 45,000
5X2 + 10 X3 ≤ 45,000
5X2 + 20 X3 ≤ 45,000
X3 ≥ 200
X1, X2 , X3 ≥ 0
Problema N° 13
TAKAGAKI S. A. fabrica dos tipos de alimentos balanceados, recibe un pedido especial de 200 TN de una mezcla de proteínas y carbohidratos, la mezcla debe contener a lo más 40% de proteínas y por lo menos 30% de carbohidratos, el costo de cada TN de proteínas es de S/. 3 y de cada TN de carbohidratos es de 8, determinar la mezcla óptima.
XP: TN. de proteínas utilizadas en la mezcla
Xc: TN. de carbohidratos utilizadas en la mezcla
Max (Z) = 3 XP + 8 XC
Sujeto a:
XP + XC = 200
XP ≤ 0.40 ( XP + XC)
XC ≥ 0.30 ( XP + XC)
XP , XC ≥ 0
Problema N° 14
Xi: Número de acres que se destinan a cada cosecha en cada comunidad
I = 1, 2, 3, 4, 5, 6, 7, 8, 9
Max (Z) = 1,000 (X1 + X2 + X3) + 750 (X4 + X5 + X6) + 250 (X7 + X8 + X9)
Sujeto a:
Terreno para uso en cada comunidad
X1 + X4 + X7 ≤ 400
X2 + X5 + X8 ≤ 600
X3 + X6 + X9 ≤ 300
Comunidad Cosecha
1 2 3 1 Remolacha 2 Algodón 3 Sorgo
X1 X4 X7
X2 X5 X8
X3 X6 X9
Comunidad Cosecha
1 2 3 1 Remolacha 2 Algodón 3 Sorgo
X11 X21 X31
X12 X22 X32
X13 X23 X33
ContinuaciónAsignación de agua para cada comunidad
3 X1 + 2 X4 + X7 ≤ 600
3 X2 + 2 X5 + X8 ≤ 800
3 X3 + 2 X6 + X9 ≤ 375
Total de acres para cada cosecha
X1 + X2 + X3 ≤ 600
X4 + X5 + X6 ≤ 500
X7 + X8 + X9 ≤ 325
Igual proporción del área planteada
X1 + X4 + X7 = X2 + X5 + X8
400 600
X2 + X5 + X8 = X3 + X6 + X9
600 300
Xi ≥ 0 , i = 1,………,9
Problema N° 15
Variable de decisión
Xi = El uso de cada uno de los tres métodos de abatimiento en cada tipo de horno, expresado como una fracción de la capacidad de abatimiento de tal manera que Xi no exceda a 1
Función Objetivo
Min (Z) = 8X1 + 10X2 + 7X3 + 6X4 + 11X5 + 9X6 Sujeto a:
12X1 + 9X2 + 25X3 + 20X4 + 17X5 + 13X6 ≥ 60
35X1 + 42X2 + 18X3 + 31X4 + 56X5 + 49X6 150
37X1 + 53X2 + 28X3 + 24X4 + 29X5 + 20X6 125
X1 + X2 + X3 + X4 + X5 + X6 ≤ 1
X1, X2 , X3 , X4, X5, X6 0
Método de abatimiento
Tecnología
METODOS DE SOLUCION DE PROBLEMAS LINEALES
Métodos: Gráfico. Fácilmente comprensible y permite visualizar
algunas propiedades. Analítico. El método simplex ha demostrado ser
eficiente por el uso del computador. Algeibraíco
Método Gráfico: Este método consiste en delinear sobre el primer cuadrante (debido a la condición de no negatividad) la región de soluciones factibles; luego sobre ella se grafica la función objetivo.
Ejemplo 1Xi = Número de unidades del producto i
Max (Z) = X1 + X2 Sujeto a:
2 X1 + 2 X2 ≤ 8 6 X1 + 2 X2 ≤ 18 2 X1 + 4 X2 ≤ 16 X1 , X2 ≥ 0
SOLUCION GRAFICA
Cualquier punto dentro de la región cumple simultáneamente con las tres restricciones y con la no negatividad. Ahora el problema consiste en maximizar la función objetivo Z = X1+X2 sobre la región sombreada que representa a las restricciones del problema lineal en estudio:
X1+X2 = 0 M = - X2
X1
La recta X1+X2 = 4 representa el máximo valor de Z, Sujeta a las restricciones del programa lineal propuesto. Cualquier valor de Z > 6, no tendrá ningún punto con la región sombreada
Z = 0
Z = 2
Región Factible. Es aquella que cumple con todas las restricciones y las condiciones de no negatividad.
Solución Factible. Es cualquier punto situado en la región factible.
Solución Básica. Es aquella que se encuentra en la intersección de rectas o hiperplanos o en la intersección con los ejes coordenados.
Solución Básica Factible. Es una solución básica que pertenece a la región factible.
Solución Optima. Es una solución factible que maximiza o minimiza la función objetivo según sea el caso
Solución Básica Factible Degenerada. Es una solución factible básica en la que una o más variables básicas toman el valor de cero.
TEOREMA 1. El conjunto de todas las soluciones factibles al problema de programación lineal es un conjunto convexo.
TEOREMA 2. La función objetivo alcanza su máximo en un punto extremo del conjunto convexo, generado por el conjunto de soluciones factibles al problema de programación lineal.
1. Existe un punto extremo del polígono (poliedro) convexo en el
cual la función objetivo tiene su máximo (mínimo).
2. Cada solución factible básica corresponde a un punto extremo
del polígono (poliedro) convexo.
Se tendrá que buscar que investigar únicamente los puntos extremos del polígono (poliedro) convexo y buscar aquel punto que proporcione el mayor (menor) valor para que la función objetivo y así obtendremos la solución buscada.
Restricción de mayor o igual que cero, límite mínimo
Ejemplo 2
Min (Z) = 2 X1 + 6 X2
Sujeto a:
12 X1 + 6 X2 ≥ 16
4 X1 + 12 X2 ≥ 12
X1 , X2 ≥ 0
Ejemplo 3
Min (Z) = 2 X1 + 3 X2
Sujeto a:
X1 + X2 ≤ 4
6 X1 + 2 X2 = 8
X1 + 5 X2 ≥ 4
X1 ≤ 3
X2 ≤ 3
X1 , X2 ≥ 0
La solución se encuentra en el segmento A y B, donde X1 = 8/7 y X2 = 4/7. la función objetivo toma el valor de 4.
A
B
Ejemplo 4
Max (Z) = X1 + X2
Sujeto a:
- 4 X1 + 2 X2 ≤ 2
2 X1 ≤ 4
2 X1 + 2 X2 ≤ 6
X1 , X2 ≥ 0
Se aprecia que la recta de la función objetivo no es ahora tangente a un vértice del polígono factible, si no es coincidente con uno de los lados del mismo.
¿Cuál es entonces la solución?
En este caso es posible definir cualquier punto sobre la recta BC y hallar en consecuencia los valores X1 y X2.
X1 = 2 ; X2 = 1; Z = 3, otro resultado X1 = 2/3 , X2 = 7/3 ; Z = 3
C
B(2,1)
(2/3,7/3)
Ejemplo 5
Max (Z) = 2 X1 + 2 X2
Sujeto a:
X1 - X2 ≥ 1
1/ 2 X1 + X2 ≤ 2
X1 , X2 ≥ 0
No tiene un valor máximo finito.
En problemas prácticos no puede presentarse este tipo de solución
(6,5)
Ejemplo 6
Max (Z) = 3 X1 + 2 X2
Sujeto a:
X1 + X2 ≤ 1
2 X1 + 2 X2 ≥ 4
X1 , X2 ≥ 0
Ejemplo 7
Max (Z) = X1 + X2
Sujeto a:
3 X1 - X2 ≥ - 3
X1 + X2 ≤ 4
X1 , X2 ≥ 0
No se puede garantizar que todo problema tenga solución factible.
USANDO UN GRAFICO SE PUEDEN REPRESENTAR TODAS
LAS RESTRICCIONES, LA FUNCION OBJETIVO Y LOS
TRES TIPOS DE PUNTOS DE FACTIBILIDAD.
Ejemplo: El problema de la industria de juguetes “Galaxia”.
• Galaxia produce dos tipos de juguetes:
* Space Ray
* Zapper
• Los recursos están limitados a:
* 1200 libras de plástico especial.
* 40 horas de producción semanalmente.
• Requerimientos de Marketing.
* La producción total no puede exceder de 800 docenas.
* 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 libras de plástico y 3 minutos de
producción por docena.
* Zappers requiere 1 libra de plástico y 4 minutos de producción
por docena.
• Plan común de producción para:
Fabricar la mayor cantidad del producto que deje mejores ganancias, el cual corresponde a Space Ray (S/. 8 de utilidad por docena).
Usar la menor cantidad de recursos para producir Zappers, porque estos dejan una menor utilidad (S/. 5 de utilidad por docena).
Solución
• 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.
• 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)
• El plan común de producción consiste en:Space Rays = 550 docenas
Zappers = 100 docenas
Utilidad = S/. 4900 por semana
Tipos de Puntos de factibilidad
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
Punto InferiorPunto Medio Punto Extremo
X1
• Resolución gráfica para encontrar la solución optima
Recalcular la re
gión factib
le
600
800
1200
400 600 800
X2
X1
comenzar con una ganancia dada de = S/. 2,000...
Util. = S/. 000 2,
Entonces aumente la ganancia...
3,4,
...y continúe hasta que salga de la región factible
Ganancia = S/. 5,040
600
800
1200
400 600 800
X2
X1
Se toma un valor cercano al punto óptimo
FeasibleregionRegiónFactible
Región no factible
• Resumen de la solución óptima
Space Rays = 480 docenas
Zappers = 240 docenas
Ganancia = S/. 5,040
*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.
• 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.
METODO SIMPLEX
1. bi ≤ 02. Restricciones ≤3. Restricciones ≥4. Restricciones =
5. Xj ≤ 0; xi = - Xi, donde Xi ≥ 0
6. Xi Sin Restricción de Signo (SRS)+ , - , 0
X1 ; SRS
X1 = X1+
- X1-
X1 = A1 - D1
A1 > D1; X1 > 0; X1 = A1 - 0
A1 = D1; X1 = 0; X1 = 0 - 0
A1< D1; X1 < 0; X1 = 0 - D1
donde :
A1, D1 ≥ 0
7. Empate en el criterio en la variable que ingresa se escoge arbitrariamente cualquiera.
Seleccionamos la variable que sale {θi menor}
8. Empate en el criterio en la variable que sale se escoge arbitrariamente cualquiera.
Criterio de Optimalidad
Max Zj - Cj ≥ 0 ; Cj - Zj ≤ 0
Min Zj - Cj ≤ 0 ; Cj - Zj ≥ 0
9. Tipo de soluciones.
Ejemplo – Método Simplex
La compañía SONYT S. A. produce radios y televisores, cada radio se vende con una ganancia de S/. 30, mientras que cada televisor vendido se gana S/. 50. Ambos productos deben pasar por los departamentos A y B (impresión de circuitos y ensamble) respectivamente: mensualmente se dispone de 200 horas en el departamento A y 140 horas en el departamento B. Cada radio requiere de una hora en departamento A como en el departamento B, cada televisor requiere de 2 horas en departamento A y una hora en el departamento B. Cuál es el programa de producción que maximiza la ganancia.
REQUERIMIENTOS DEPARATMENTO RADIO TELEVISOR
DISPONIBILIDAD
A B
1 hr. 1 hr.
2 hrs. 1 hr.
200 hrs / mes 140 hrs. / mes
Xi: Numero de unidades del producto tipo i que se deben producir mensualmente.
Max (Z) = 30 X1 + 50 X2
Sujeto a:
X1 + 2 X2 ≤ 200
X1 + X2 ≤ 140
X1 , X2 ≥ 0
Solución
(80,60)
(140,0)
(0,100)
Cj 30 50 0 0
Ci XB X1 X2 S1 S2 bi θi
0 S1 1 2 1 0 200 100
0 S2 1 1 0 1 140 140
Cj -Zj 30 50 0 0 0
Solución
Iteración N° 1
Cj 30 50 0 0
Ci XB X1 X2 S1 S2 bi θi
50 X2 1/2 1 1/2 0 100 200
0 S2 1/2 0 -1/2 1 40 80
Cj -Zj 5 0 -25 0 5000
Iteración N° 2
Cj 30 50 0 0
Ci XB X1 X2 S1 S2 bi θi
50 X2 0 1 1 -1 60
30 X1 1 0 -1 2 80
Cj -Zj 0 0 -20 -10 5400
Solución
Iteración N° 3
¿Cuántos artefactos de A y B deben de producir para obtener el máximo beneficio?
ARTEFACTO A
(min/unid)
ARTEFACTO B
(min/unid)DISPONIBILIDAD
Maquinado
Armado
Montaje
Beneficio
4
5
12
100
8
6
6
120
480
600
540
Xi: Cantidad de artefactos del tipo i a producirse al día.
FUNCIÓN OBJETIVO
• Max (Z) = 100 X1 + 120 X2
• Sujeto a:
4 X1 + 8 X2 480 → Area de Maquinado
5 X1 + 6 X2 600 → Area de Armado
12 X1 + 8 X2 540 → Area de Montaje
X1, X2 0
(15/2, 225/4)
(0, 60)
(45, 0)
Cj 100 120 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 4 8 1 0 0 480 60
0 S2 5 6 0 1 0 600 100
0 S3 12 8 0 0 1 540 135/2
Cj -Zj 100 120 0 0 0 0
Solución
Iteración N° 1
Cj 100 120 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
120 X2 1/2 1 1/8 0 0 60 120
0 S2 2 0 -3/4 1 0 240 120
0 S3 8 0 -1 0 1 60 15/2
Cj -Zj 40 0 -15 0 0 7200
Iteración N° 2
Iteración N° 3
Cj 100 120 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
120 X2 0 1 3/16 0 -1/16 225/4
0 S2 0 0 -1/2 1 -1/4 225
100 X1 1 0 -1/8 0 1/8 15/2
Cj -Zj 0 0 -10 0 -5 7500
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = 4 X1 + 3 X2
Sujeto a:
4 X1 + 2 X2 12
X1 + 3 X2 9
7 X1 + 2 X2 28
X1, X2 0
Cj 4 3 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 2 8 1 0 0 12 3
0 S2 3 6 0 1 0 9 9
0 S3 7 8 0 0 1 28 4
Cj -Zj 4 3 0 0 0 0
Tipos de Solución
Iteraciones
4 X1 1 1/2 1/4 0 0 3 6
0 S2 0 5/2 -1/4 1 0 6 12/5
0 S3 0 -3/2 -7/4 0 1 7 -
Cj -Zj 0 1 -1 0 0 24
4 X1 1 0 3/10 -1/5 0 9/5
3 X2 0 1 -1/10 2/5 0 12/5
0 S3 0 0 -19/10 3/5 1 53/5
Cj -Zj 0 0 -9/10 -2/5 0 72/5
Solución Optima Unica
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = 3 X1 + 5 X2
Sujeto a:
X1 4
2 X2 12
3 X1 + 2 X2 18
X1, X2 0
Cj 3 5 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 1 0 1 0 0 4 -
0 S2 0 2 0 1 0 12 6
0 S3 3 2 0 0 1 18 9
Cj - Zj 3 5 0 0 0 0
Tipos de Solución
Iteraciones
0 S1 1 0 1 0 0 4 4
5 X2 0 1 0 1/2 0 6 -
0 S3 3 0 0 -1 1 6 2
Cj - Zj 3 0 0 -5/2 0 30
0 S1 0 0 1 1/3 -1/3 2
5 X2 0 1 0 1/2 0 6
3 X1 1 0 0 -1/3 1/3 2
Cj - Zj 0 0 0 -3/2 -1 36
Solución Optima Unica
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = 3 X1 + 2 X2
Sujeto a:
X1 4
2 X2 12
3 X1 + 2 X2 18
X1, X2 0
Cj 3 2 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 1 0 1 0 0 4 4
0 S2 0 2 0 1 0 12 -
0 S3 3 2 0 0 1 18 6
Cj - Zj 3 2 0 0 0 0
Tipos de Solución
Iteraciones
3 X1 1 0 1 0 0 4 -
0 S2 0 2 0 1 0 12 6
0 S3 0 2 -3 0 1 6 3
Cj - Zj 0 2 -3 0 0 12
3 X1 1 0 1 0 0 4
0 S2 0 0 3 1 -1 6
2 X2 0 1 -3/2 0 1/2 3
Cj - Zj 0 0 0 0 -1 18
3 X1 1 0 0 -1/3 1/3 2
0 S1 0 0 1 1/3 -1/3 2
2 X2 0 1 0 1/2 0 6
Cj - Zj 0 0 0 0 -1 18
Solución Optima Altenativa
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = 10 X1 + 5 X2
Sujeto a:
-3 X1 + 4 X2 12
X1 - 2 X2 2
X1 + 2 X2 8
X1, X2 0
Cj 10 5 0 0 0 -M
Ci XB X1 X2 S1 S2 S3 A3 bi θi
0 S1 -3 4 1 0 0 0 12 3
0 S2 1 -2 0 1 0 0 2 -
-M A3 1 2 0 0 -1 1 8 4
Cj - Zj 10+M 5 + 2M 0 0 -M 0 0
Tipos de Solución
Iteraciones
5 X2 -3/4 1 1/4 0 0 0 3 -
0 S2 -1/2 0 1/2 1 0 0 8 -
-M A3 5/2 0 -1/2 0 -1 1 2 4/5
Cj - Zj 55/4+5M/2 0 -5/4-M/2 0 -M 0 15
5 X2 0 1 1/10 0 -3/10 3/10 18/5
0 S2 0 0 4/10 1 -1/5 1/5 42/5
10 X1 1 0 -1/5 0 -2/5 2/5 4/5
Cj - Zj 0 0 3/2 0 11/2 -M-11/2 26
Solución No Acotada
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Min (Z) = X1 + X2
Sujeto a:
9 X1 + 3 X2 9
3 X1 + 3 X2 15
3 X1 + 4 X2 = 12
X1, X2 0
Cj 1 1 0 0 M M
Ci XB X1 X2 S1 S2 A1 A3 bi θi
M A1 9 3 -1 0 1 0 9 1
0 S2 3 3 0 1 0 0 15 5
M A3 3 4 0 0 0 1 12 4
Cj – Zj 1-12M 1-7M M 0 0 0
Tipos de Solución
Iteraciones
1 X1 1 1/3 -1/9 0 1/9 0 1 3
0 S2 0 2 1/3 1 -1/3 0 12 6
M A3 0 3 1/3 0 -1/3 1 9 3
Cj - Zj 0 2/3-3M 1/9-M/3 0 -1/9+4M/3 0
1 X1 1 0 -4/27 0 4/27 -1/9 0
0 S2 0 0 1/9 1 -1/9 -2/3 6
1 X2 0 1 1/9 0 -1/9 1/3 3
Cj - Zj 0 0 1/27 0 M-1/27 M-2/9 3
Solución Degenerada
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Min (Z) = X1 + X2
Sujeto a:
9 X1 + 3 X2 9
X1 - 2 X2 15
X1 + 2 X2 = 12
X1, X2 0
Cj 1 1 0 0 M M
Ci XB X1 X2 S1 S2 A1 A3 bi θi
M A1 9 3 -1 0 1 0 9 1
0 S2 1 -2 0 1 0 0 15 15
M A3 1 2 0 0 0 1 12 12
Cj – Zj 1-10M 1-5M M 0 0 0
Tipos de Solución
Iteraciones
1 X1 1 1/3 -1/9 0 1/9 0 1 3
0 S2 0 -7/3 1/9 1 -1/9 0 14 -
M A3 0 5/3 1/9 0 -1/9 1 11 33/5
Cj - Zj 0 2/3-5M/3 1/9-M/9 0 -1/9+M/9 0
1 X2 3 1 -1/3 0 1/3 0 3 -
0 S2 7 0 -2/3 1 2/3 0 21 -
M A3 -5 0 2/3 0 -2/3 1 6 9
Cj - Zj -2+5M 0 1/3-2M/3 0 5M/3-1/3 0 3
1 X2 1/2 1 0 0 0 1/2 6
0 S2 2 0 0 1 0 1 27
0 S1 -15/2 0 1 0 -1 3/2 9
Cj - Zj 1/2 0 0 0 M M-1/2 6
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = 3X1 + 5X2
Sujeto a:
X1 8
2 X2 12
3 X1 + 2 X2 = 18
X1, X2 0
GRAFICA
Cj 3 5 0 0 0 -M
Ci XB X1 X2 S1 S2 S3 A1 Bi θi
-M A1 1 0 -1 0 0 1 8 8
0 S2 0 2 0 1 0 0 12 -
-M A3 3 2 0 0 1 0 18 6
Cj – Zj 3 + M 5 + 2M -M 0 0 0
Tipos de Solución
Iteraciones
-M A1 0 -2/3 -1 0 -1/3 0 2
0 S2 0 2 0 1 0 0 12
3 X1 1 2/3 0 0 1/3 1 6
Cj - Zj 0 5-2M/3 -M 0 -M/3-1 0
Solución No Factible
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = 460X1 + 200X2
Sujeto a:
18 X1 + 3 X2 ≤ 800
9 X1 + 4 X2 600
X1 ≥ 80
X1, X2 0
Cj 460 200 0 0 0 -M
Ci XB X1 X2 S1 S2 S3 A3 bi θi
0 S1 18 3 1 0 0 0 800 400/9
0 S2 9 4 0 1 0 0 600 200/3
-M A3 1 0 0 0 -1 1 80 80
Cj – Zj 460+M 200 0 0 -M 0
Tipos de Solución
Iteraciones
460 X1 1 1/6 1/18 0 0 0 400/9
0 S2 0 5/2 -1/2 1 0 0 200
-M A3 0 -1/6 -1/18 0 -1 1 320/9
Cj – Zj 0 370/3-M/6 230/9-M/18 0 -M 0
Solución No Factible
Xi: Variable de decisión
FUNCIÓN OBJETIVO
• Max (Z) = X1 + X2
Sujeto a:
2 X1 + 2 X2 ≤ 8
6 X1 + 2 X2 18
2 X1 + 4 X2 ≤ 16
X1, X2 0
Cj 1 1 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 2 2 1 0 0 8 4
0 S2 6 2 0 1 0 18 3
0 S3 2 4 0 0 1 16 8
Cj - Zj 1 1 0 0 0 0
Tipos de Solución
Iteraciones
0 S1 0 4/3 1 -1/3 0 2 -
1 X1 1 1/3 0 1/6 0 3 6
0 S3 0 10/3 0 -1/3 1 10 3
Cj - Zj 0 2/3 0 -1/6 0 3
1 X1 0 0 3/4 -1/4 0 3/2
1 X2 10 0 -1/4 1/4 0 5/2
0 S3 0 1 -5/2 -1/2 1 5
Cj - Zj 0 0 -1/2 0 0 4
1 X2 1 1 1/2 0 0 4
0 S2 4 0 -1 1 0 10
0 S3 2 0 -3 0 1 10
Cj - Zj 0 0 -1/2 0 0 4
Solución Optima Altenativa
Max (Z) = 4 X1 + 8 X2
Sujeto a:
6 X1 + 8 X2 ≤ 24
20 X1 = 10X2
8 X1 - 4 X2 ≤ 16
X1, X2 0
Cj 4 8 0 -M 0
Ci XB X1 X2 S1 A2 S3 bi θi
0 S1 6 8 1 0 0 24 4
-M A2 20 -10 0 1 0 0 0
0 S3 8 -4 0 0 1 16 2
Cj - Zj 4+20M 8 -10M 0 0 0
Tipos de Solución
Iteraciones
0 S1 0 11 1 -3/10 0 24 24/11
1 X1 1 -1/2 0 1/20 0 0 -
0 S3 0 0 0 -2/5 1 16 -
Cj - Zj 0 10 0 -1/6 0
1 X2 0 1 1/11 -3/110 0 24/11
1 X1 1 0 1/22 2/55 0 12/11
0 S3 0 0 0 -2/5 1 16
Cj - Zj 0 0 -10/11 -M-4/55 0 240/11
