Programación lineal:
Postulados básicos
Universidad Nacional Mayor de San Marcos Facultad de Ingeniería Industrial
2015-0
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
¿Quién podrá ayudarme?
¿Cuántas hectáreas de cada verdura debo cultivar para gastar lo mínimo y maximizar los ingresos de mi cosecha?
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Naturaleza de la Investigación Operativa
También llamada, Ciencia de la Administración o Management Science .Data de la segunda guerra mundial, pero por sus aplicaciones, se dice que su impacto social es amplio Las aplicaciones de la Investigación de Operaciones, van desde el aspecto laboral hasta el plano criminal, pasando por el de polución y de la segregación racial.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Orígenes
Primera revolución industrial, se trajo consigo el desarrollo de la energía, las maquinarias y los equipos .Segmentación funcional y geográfica de la administración.Durante la segunda guerra mundial existían grupos especialistas ( matemáticos, físicos, psicólogos, ingenieros, etc.) Por el año de 1941 se establece una sección de Operations Research en la RAF Al finalizar la Gran Guerra, un grupo de ellos se dedicó a la industria y al gobierno; empezando a aparecer la palabra IO para designar a aquellos científicos que se preocupaban por dar solución a los problemas que aparecían en la administración
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Objetivos de la Investigación Operativa
El objetivo más importante de la aplicación de la Investigación Operativa es apoyar en la “toma óptima de decisiones” en los sistemas y en la planificación de sus actividades.Para hallar la solución, la Investigación Operativa generalmente representa el problema como un modelo matemático, que es analizado y evaluado previamente.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Características de la I.O
Enfoque de sistema. considera a los sistemas tomados en conjuntos y no en sus partes individuales
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Características de la I.O
El uso del equipo interdisciplinario, es indispensable, cuando nos encontramos ante una situación compleja, como lo es el sistema de la organización hombre-máquina.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Características de la I.O
La adopción del método científico , automáticamente se relaciona con el método de la experimentación; realmente sería muy costoso que el investigador de operaciones experimentara sus decisiones y por otro lado las consecuencias fatales que traería una mala decisión dentro de una empresa
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Modelos en la I.O
SimbólicosMatemáticos Ello radica en la facilidad que se consigue de expresar las relaciones de causa-efecto de un sistema La formulación de hipótesis, no es otra cosa que la construcción de un modelo matemático y la predicción del comportamiento del sistema, la obtención de la solución del mismo
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Condiciones de un modelos en I.O
Variables de decisión y parámetros.- Las variables de decisión son las variables no conocidas y que deben de ser determinadas en el modelo. Los parámetros representan la variables controlables.Restricciones.- Están representadas por las limitaciones físicas del sistema; el modelo incluye restricciones para limitar el valor de la variable de decisión. Funciones objetivo.- Define la medida de efectividad del sistema en función de las variables de decisión.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Diagrama del Modelo de la I.O
VARIABLES
DECISION
VARIABLES
INCONTROLABLESEFECTIVIDAD
MEDIDAS DE
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Fases de un Estudio de Inv.Operativa
Formulación del problema Construcción del modelo Solución del modelo Validación del modelo Control del modelo Implantación del modelo
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Fases de un Estudio de Inv.Operativa
PONER LA
SOLUCION A
TRABAJAR: EJECUCION
ESTABLECIMIENTO
DE CONTROLES
SOBRE LA SOLUCION
PRUEBA DEL
MODELO Y
DE LA SOLUCION
DEDUCCION DE
UNA SOLUCION
A PARTIR DEL MODELO
CONSTRUCCION DE UN
MODELO PARA
REPRESENTAR EL SISTEMA
FORMULACION
DEL
PROBLEMA
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Validez de un modelo de Inv. Operativa
Se dice que un modelo es válido cuando representa la realidad de una manera adecuada; siendo para ello necesario: Comprobar con la data histórica el rendimiento del sistema real y el del ofrecido por el modelo. Comprobar el rendimiento del sistema en funcionamiento (sin cambios) y el del modelo.
“Un modelo es construido en base a parámetros y restricciones que con el transcurso del tiempo pueden cambiar”
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
SOLUCIÓN AL PROBLEMA DELSISTEMA REAL
SISTEMAREAL
SOLUCIÓNAL MODELO
MODELOCUANTITATIVO
SISTEMA ASUMIDO
JUICIOS YEXPERIENCIAS
VARIABLESRELEVANTES
RELACIONESRELEVANTES
MÉTODODE SOLUCIÓN
INTERPRETACIÓNDECISIONES
Validez de un Estudio de Inv.Operativa
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
El impacto de la Investigación Operativa
Las aplicaciones de la investigación de operaciones han llegado diversos campos como:
Finanzas. Cadenas de abastecimiento. Localización de facilidades. Manufactura. Construcción y mantenimiento. Mercados. Personal Desarrollo e investigación.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Ventajas de la Inv. Operativa
En general, ayudan a tomar 2 tipos de decisiones : Decisiones estratégicas.- Es una decisión de una sola vez, que involucra políticas con consecuencias a largo plazo para la organización.Se consideran decisiones importantes, considera la incertidumbre y escoge entre varias alternativas.
Decisiones Operacionales.- Es una decisión que implica cuestiones de planeación a corto plazo que generalmente deben hacerse repetidamente.Se consideran decisiones de menor importancia y frecuentes por ser dadas para el corto plazo. Ignoran la incertidumbre y no evita barajear alternativas nuevas.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Ventajas de la Inv. Operativa
Método de determinación de la mejor forma de
lograr un objetivo
Por la forma de evaluar el impacto de un nuevo sistema
sin el costo ni el tiempo de llevarlo a cabo
Permite evaluar la fortaleza de la solución
óptima (problemas de sensibilidad)
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Limitaciones de la Inv. Operativa
Frecuentemente es necesario hacer simplificaciones del problema original para poder manipularlo y tener una solución.
La mayoría de los modelos sólo considera un solo objetivo y frecuentemente en las organizaciones se tienen objetivos múltiples.
Rara vez se realizan análisis costo-beneficio de la implantación de soluciones definidas por medio de la I de O, en ocasiones los beneficios potenciales se ven superados por los costos ocasionados por el desarrollo e implantación de un modelo.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Limitaciones de la Inv. Operativa
Existe la tendencia a no considerar la totalidad de las restricciones en un problema práctico, debido a que los métodos de enseñanza y entrenamiento dan la aplicación de esta ciencia centralmente se basan en problemas pequeños para razones de índole práctico, por lo que se desarrolla en los alumnos una opinión muy simplista e ingenua sobre la aplicación de estas técnicas a problemas reales.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Conclusiones
Los problemas complicados del mundo real no suelen tener solución óptima
No se debe permitir que el modelo tome las decisiones sin analizar los resultados
El modelo de optimización produce la respuesta óptima al problema matemático propuesto por el modelo, que puede no ser una buena respuesta para el problema real
Óptimo significa grandes esperanzas de buena decisión, pero no certeza
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La programación Lineal PL
Universidad Nacional Mayor de San Marcos Facultad de Ingeniería Industrial
2015-0
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La programación lineal o PL, tiene el propósito de construir modelos a una amplia clase de problemas de decisión; siendo muy solicitados en la industria, el gobierno, la economía y la ingeniería.
Conceptos
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Un programa lineal es aquel en el cual la función objetivo es lineal y las restricciones están dadas por un conjunto de ecuaciones e inecuaciones también lineales.
Definicion de un PL
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
George B. Dantzig, es considerado como el padre de la programación lineal.
La PL descansa en 4 supuestos, los que son:
La proporcionalidad.La aditividadLa divisibilidad.La certeza.
Postulados básicos
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La proporcionalidad.Así, cuando en el Dpto. de corte se utilizan 3 horas-hombre para procesar una mesa, entonces para la actividad k se tiene 3k como el tiempo total para cortar toda la producción de mesas.
Postulados básicos
xcx
c
mesa
mesa
1
11
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La aditividad.Cada función en un modelo de programación lineal (ya sea la función objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las contribuciones individuales de las actividades respectivas.
Postulados básicos
2211
22
11
xcxc
cx
cx
sillas
mesas
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La divisibilidad.Como cada variable de decisión representa el nivel de alguna actividad, se supondrá que las actividades se pueden realizar a niveles fracciónales.
X1 = 50 carpetas
X2 = 25.32 escritorios ← ACEPTABLE
X3 = - 12 mesas ¿?
Postulados básicos
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La certeza.Esta dado por la confianza que dará el resultado de elaborar un PL.
Postulados básicos
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
¿Qué pasaría, si en vez de sumarse las variables, por ejemplo se multiplicarán? Estaríamos ante el dominio de la programación no lineal. Este es un campo fértil, en nuestros días actuales.
Considerar lo siguiente:
Postulados básicos
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Postulados básicos
0
5
10
15
20
25
1 2 3 4 5
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
La solución a un PL es resultado de la manipulación de un sistema de ecuaciones lineales; por tanto, las unidades de las actividades pueden dividirse en niveles fraccionarios, de modo que pueden permitirse valores no enteros para las variables de decisión.
Muchos problemas de PL obtienen valores enteros, porque sus estructuras se ajustan al principio de la unimodularidad.
Postulados básicos
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Estructura general de un modelo PL
jx
bxaxaxa
bxaxaxa
bxaxaxa
asujeto
xcxcxczMax
j
mnmnmm
nn
nn
n
0
+
+
+
+
2211
22222121
11212111
n2211
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Estructura general de un modelo PL
nxcxcxczMax n2211 +
Donde el vector c también conocido como el vector costos, viene dado por:
nn ccccc 121
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Estructura general de un modelo PL
El vector de la mano derecha o b, viene dado por:
m
m
b
b
b
b
b
1
2
1
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.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Estructura general de un modelo PL
La matriz A, representa los coeficiente tecnológicos; es la matriz para el sistema de ecuaciones Ax = b:
nmmm
n
n
aaa
aaa
aaa
A
,2,1,
22221
12111
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Soluciones básicas
Sea una matriz A de m x n; es decir se consideran m ecuaciones y n incógnitas. El sistema de ecuaciones:
Ax = b
origina la matriz aumentada (A, b) con m filas y (n+1) columnas.
Cuando el rango ( A , b)= rango ( A) = k, entones se puede escribir :
( , )A bA b
A b
1 1
2 2
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Soluciones básicas
Con A1 de orden k x n y A2 de orden (m-k) x n;
satisfaciendo:
A1x = b1
donde el sistema A2x = b2 es redundante.
Puesto que el rango ( A1) = k, entonces seleccionando k
columnas linealmente independientes, se tiene :
A1 = (B,N)
Donde B es una matriz no singular de orden k x k ( llamada matriz básica ) y N de orden n x (n-k) (matriz no básica). El sistema queda expresado A1x = b1
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Puntos extremos y solución básica
Sea una x BFS (una solución básica factible) a las restricciones:
Ax = b
Luego, la matriz A, se descompone en (B,N) y x en (xB,xN); siendo la solución desde BxB = b; igual :
xB = B-1b, xN = 0
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Existencia de una solución básica factible
Si un PL con restricciones no redundantes, tiene solución factible (dado que la restricción es ser las variables no negativas); entonces tiene solución básica factible.
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Ejemplo
Sea el PL:
Ax = b
x 0
Donde A es de orden m x n, por ejemplo :
2 1 1 0
1 1 0 1
40
40
1
2
3
4
x
x
x
x
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Formato canónico de un PL
Min Max
sa.
sa.
Canónica
sa.
sa.
Estándar
Min CXZ
0X
AX
b
Max CXZ
0X
AX
b
Min CXZ
0X
AX
b
Max CXZ
0X
AX
b
MSc. Ing. Ezzard Omar Alvarez DíazMSc. Ing. Ezzard Omar Alvarez Díaz
Ventajas de un PL
Resultan más fáciles de definir y formular. Permiten trabajar de manera eficiente con mayor número de variables de decisión.
Se adaptan mejor al tratamiento algorítmico con computadores, aprovechando la rapidez de cálculo de éstos.
Formulación de problemas en PL
Universidad Nacional Mayor de San Marcos Facultad de Ingeniería Industrial
2015-0
Introducción.Introducción.
El principal objetivo de esta área de conocimientos consiste en formular y resolver diversos problemas orientados a la toma de decisiones.
La naturaleza de los problemas abordados puede ser determinística, como en los Modelos de Programación Matemática, donde la teoría de probabilidades no es necesaria, o bien de problemas donde la presencia de incertidumbre tiene un rol preponderante, como en los Modelos Probabilísticos.
IntroducciónIntroducción
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.
Elementos de un modelo de Elementos de un modelo de optimizaciónoptimización
Supongamos que se dispone de determinadas piezas para la elaboración de dos productos finales. Se dispone de 8 “piezas pequeñas” y 6 “piezas grandes”, que son utilizadas para elaborar sillas (usando 2 piezas pequeñas y 1 pieza grande) y mesas (usando 2 piezas de cada tipo).
Interesa decidir cuántas sillas y mesas fabricar de modo de obtener la máxima utilidad, dado un beneficio neto de U$ 15 por cada silla y de U$20 por cada mesa fabricada.
Elementos de un modelo de Elementos de un modelo de optimizaciónoptimización
Posibles soluciones factibles a considerar, esto es soluciones que respetan las restricciones del número de piezas disponibles, son por ejemplo, fabricar:
• 4 sillas, que reportan una utilidad de U$60• 1 sillas y 2 mesas , utilidad de U$55• 3 mesas, utilidad de U$60• 1 mesa y tres sillas, utilidad de U$65• 2 sillas y 2 mesas, utilidad de U$70• etc.
Elementos de un modelo de Elementos de un modelo de optimizaciónoptimización
Un modelo matemático para hallar la mejor solución factible a este problema tiene tres componentes básicas:
i) Las variables de decisión, que consiste en definir cuáles son las decisiones que se debe tomar. En el ejemplo,
x: número de sillas elaboradas.
y: número de mesas elaboradas.
Elementos de un modelo de Elementos de un modelo de optimizaciónoptimización
ii) La función objetivo del problema, que permita tener un criterio para decidir entre todas las soluciones factibles. En el ejemplo, maximizar la utilidad dada por:
z = f(x,y) = 15x + 20y
Elementos de un modelo de Elementos de un modelo de optimizaciónoptimización
iii) Restricciones del problema, que consiste en definir un conjunto de ecuaciones e inecuaciones que restringen los valores de las variables de decisión a aquellos considerados como factibles. En el ejemplo, respetar la disponibilidad de piezas para la fabricación de sillas y mesas:
Piezas pequeñas: 2x + 2y 8Piezas grandes : x + 2y 6También se impone restricciones de no – negatividad:
x,y 0
Elementos de un modelo de Elementos de un modelo de optimizaciónoptimización
En resumen: Max 15x + 20ysa: 2x + 2y 8
x + 2y 6x,y 0
El ejemplo corresponde a un modelo de Programación Lineal. Si además restringimos los valores de x e y a números enteros, tendríamos un modelo de Programación Entera. Por otra parte, si hubiese retornos crecientes a escala, deberíamos emplear una función objetivo no lineal como f(x,y) = cxa + dyb con a,b >1, y tendríamos un modelo de Programación No Lineal.
Un programa lineal puede formularse de muy diferentes formas, pero dentro de la Programación Lineal se adopta como estándar la siguiente:
Formulación de problemas en PL
0x
bAx
cx
:sa
zMax
Definición de Variables Coeficientes de costos (o de utilidades) Función Objetivo (F.O) Término independiente o del lado derecho (recursos o requerimientos) Coeficientes tecnológicos Restricciones funcionales Restricciones de signo de las variables
Etapas en la Formulación de problemas en PL
Alguno de los tipos de problemas que se pueden formular son:
Planeación de la producción e inventarios Mezcla de Alimentos Transporte y asignación Planeación financiera Mercadotecnia Asignación de recursos
Usos de los PL
Considere la producción de 3 artículos; cada uno produciendo una ganancia unidades monetarias por unidad. Los artículos hacen uso de los recursos de dos departamentos; siendo los tiempos estándares consumidos por cada artículo por departamento:
Mezcla de productos...
Artículo Ganancia Dpto. 1 Dpto. 21 c1 a11 a21
2 c2 a12 a22
3 c3 a13 a23
Si existen un total de tiempos disponibles de b1 y
b2, respectivamente por los departamentos 1 y 2.
¿Cuál es la mejor decisión, con la finalidad de optimizar la ganancia total?
...Mezcla de productos
Artículo Ganancia Dpto. 1 Dpto. 21 c1 a11 a21
2 c2 a12 a22
3 c3 a13 a23
Analizando:
¿Cuál es el objetivo de la modelación?
¿Como queremos maximizar la ganancia total ?
Mediante el producto de la cantidad de unidades por cada artículo
Entonces nuestras variables de decisión, corresponden al número de unidades a producir por cada artículo.
Solución
Sea; xj la cantida de unidades a producir para el articulo j entonces la FO (función objetivo), expresará la maximización de la ganancia total; producto de la contribución de cada uno de los artículos, de la sgte manera:
Solución
332211Max xcxcxcz
Para la producción de las unidades expresadas en las variables de decisiones; se hace necesario, balancear el uso de los recursos de cada Dpto., con su disponibilidad; así se tiene que para cada departamento :
Departamento 1:
Solución
1313212111 bxaxaxa
Departamento 2:2323222121 bxaxaxa
3,2,1 ,0 jx j
El modelo de PL, completo se presenta a continuación:
Solución
3,2,1 ,
:sa
Max
2323222121
1313212111
332211
jx
bxaxaxa
bxaxaxa
xcxcxcz
j
En una fábrica de muebles se producen dos tipos: mesa y silla, adicionalmente la empresa dispone de 2 áreas en su planta: Corte y acabado.
Ejercicios
Para producir una mesa se requiere de 2hr y 1hr en las áreas respectivas. Para la producción de una silla se requiere de 1.5 hr. y 0.5 hr. en las diferentes áreas. Adicionalmente se sabe que la mesa da una utilidad de S / 10.00 y la silla S /. 8.00 ¿Qué cantidad de muebles se debe producir?, si se sabe que la capacidad de producción en el área de corte y acabado es de 80hr y 60 hr. respectivamente.
Ejercicios
Solución
Elaborando la tabla:
SecciónCorte(Hr)
SecciónAcabado(Hr)
Utilidad unit.(s.)
Mesas 2.0 1.0 10.0
Sillas 1.5 0.5 8.0
Cap. Prod. 80.0 60.0
Solución
Sección de
Corte
Sección de
Acabado
X1
X2
Mesa
Silla
80 hr. 60 hr.
Solución
SecciónCorte(Hr)
SecciónAcabado(Hr)
Utilidad unit.(s.)
Mesas 2.0 1.0 10.0Sillas 1.5 0.5 8.0Cap. Prod. 80.0 60.0
Mesa 2X1 + 1.5X2 < 80Silla 1X1 + 0.5X2 < 60
Función Objetivo: Max Z = 10X1 + 8X2
Solución
El PL queda de la siguiente manera:
Max Z = 10X1 + 8X2
s.a: 2X1 + 1.5X2 < 80
1X1 + 0.5X2 < 60 X1,X2 > 0
Ejercicio
Se fabrica mesas y sillas. Para una mesa se necesitan 40 pies tabla de madera, y para una silla 30 pies tabla. Se puede conseguir la madera a 1 dólar el pie tabla, y se pueden comprar 40000 pies tabla. Se necesitan 2 horas de trabajo especializado para producir una mesa y una silla sin acabado. Tres horas mas de trabajo especializado convertirán una mesa sin acabar, en una mesa acabada, y se necesitan 2 horas de trabajo especializado para acabar una silla. Se disponen de 6000 horas para cada trabajo especializado (que ya se han pagado).
Todos los muebles producidos se pueden vender a los siguientes precios unitarios: una mesa sin acabar, 70 dólares; una mesa acabada, 140 dólares; una silla sin acabar, 60 dólares; y una silla acabada, 110 dólares. Formule un programa lineal que maximice la ganancia de la producción de mesas y sillas.
Ejercicio
Todos los muebles producidos se pueden vender a los siguientes precios unitarios: una mesa sin acabar, 70 dólares; una mesa acabada, 140 dólares; una silla sin acabar, 60 dólares; y una silla acabada, 110 dólares. Formule un programa lineal que maximice la ganancia de la producción de mesas y sillas.
Solución
Colocando los Datos:
Mesas 40 US$.1 2 70 3 140Sillas 30 US$.1 2 60 2 110
Requerimientos xpies-tabla de madera
Productos Tiempo (hr.)/Precios US$Sin acabar Acabado
Costo x pie-tablar
Solución
Variable de decisión:
Xij = Cantidad de unidades del producto i que
esta en el proceso j
i = 1 => mesa
i = 2 => silla
j =1 => sin acabar
j = 2 => acabado.
Solución
Función Objetivo:
MAX Z = HI – E
Max Z = 70X11 + 60X21+140X12+110X22-40(X11+X12)-
30(X21+X22)
Max Z = 30X11 +100X12+30X21+80X22
Solución a) Restricciones:
RR de insumos: 40(X11+X12)+30(X21+X22)<=40000
RR de capacidad sección acabado
2X11+2X21<=6000
RR de capacidad sección sin acabar
3X12+2X22<=6000
RR de no negatividad
X11,X12,X21,X22>=0
Solución
Max Z = 30X11 +100X12+30X21+80X22
s.a 40(X11+X12)+30(X21+X22)<=40000
2X11+ 2X21 <=6000
3X12 +2X22<=6000
X11,X12,X21,X22>=0
El granjero Lopez tiene 480 hectáreas de tierra en la que se puede sembrar ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del verano. ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál es ésta utilidad máxima? Si se tiene la siguiente información de utilidad y requerimiento de mano de obra:
Ejemplo
Utilidad $. Cant. Trabajo Hr
Maíz: 40 2
Trigo: 30 1
Como primer paso para la formulación matemática de este problema, se tabula la información dada.
Solucion.
Maíz TrigoElementos disponibles
Horas 2 1 800
Hectáreas 1 1 480
Utilidad por unidad $ 40 30
Si llamamos x a las hectáreas de maíz e y a las hectáreas de trigo. Entonces la ganancia total Z, en dólares, está dada por:
Z=40x+30y
Que viene a ser la función objetivo por maximizar.
Solución.
La cantidad total de tiempo por hectáreas para sembrar maíz y trigo está dada por:
2x+y
Haciendo la restricción por disponibilidad
2x+y < 800
Solución.
Maíz TrigoElementos disponibles
Horas 2 1 800
La cantidad de hectáreas para sembrar maíz y trigo está dada por:
x+y
Haciendo la restricción por disponibilidad
x+y < 480
Solución.
Maíz TrigoElementos disponibles
Hectáreas 1 1 480
En resumen, el problema en cuestión queda de la siguiente manera:
Maximizar Z=40x+30y
Sujeto a:
2x+y < 800 Hora disp.
x+y < 480 Terreno disp.
x > 0 Positiva
y > 0 Positiva
Solución.
Un nutricionista asesora a un individuo que sufre una deficiencia de hierro y vitamina B, y le indica que debe ingerir al menos 2400 mg de Hierro y 2100 mg de vitamina B-1 (tiamina) y 1500 mg de vitamina B-2 (riboflavina) durante cierto período de tiempo. Existen dos píldoras de vitaminas disponibles, la marca A y la marca B. Cada píldora de la marca A contiene 40 mg de hierro, 10 mg de vitamina B-1, 5 mg de vitamina B-2 y cuesta 6 centavos. Cada píldora de la marca B contiene 10 mg de hierro, 15 mg de vitamina B-1 y de vitamina B-2, y cuesta 8 centavos (tabla). Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?
Ejemplo
¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus requerimientos de hierro y vitamina al menor costo?
Ejemplo
Marca A Marca B Req. mínimos
Hierro 40 mg 10 mg 2400 mg
Vitamina B-1 10 mg 15 mg 2100 mg
Vitamina B-2 5 mg 15 mg 1500 mg
Cost *píldora(US$) 0,06 0,08
¿Cual es el objetivo? Sea “x” el número de píldoras de la marca A; “y” el número de píldoras de la marca B por comprar. El costo Z, medido en centavos, está dado por
Z = 0.06x+ 0.08y
Que viene a ser la función objetivo por minimizar.
Solución.
La cantidad de hierro contenida en x píldoras de la marca A e y el número de píldoras de la marca B está dada por:
40x+10y Haciendo la restricción por cantidad mínima requerida.
40x+10y >= 2400
Solución.
Marca A Marca B Req. mínimos
Hierro 40 mg 10 mg 2400 mg
La cantidad de Vitamina B-1 contenida en x píldoras de la marca A e y el número de píldoras de la marca B está dada por:
10x+15y Haciendo la restricción por cantidad mínima requerida.
10x+15y >= 2100
Solución.
Marca A Marca B Req. mínimos
Vitamina B-1 10 mg 15 mg 2100 mg
La cantidad de Vitamina B-2 contenida en x píldoras de la marca A e y el número de píldoras de la marca B está dada por:
5x+15y Haciendo la restricción por cantidad mínima requerida.
5x+15y >= 1500
Solución.
Marca A Marca B Req. mínimos
Vitamina B-2 5 mg 15 mg 1500 mg
En resumen, el problema en cuestión queda de la siguiente manera:
Minimizar Z = 0.06x+ 0.08y
Sujeto a:
40x+10y >= 2400 Hierro.
10x+15y >= 2100 Vitamina B-1
5x+15y >= 1500 Vitamina B-2
y > 0 Positiva
x > 0 Positiva
Solución.
La demanda de un artículo ha sido pronosticada, para los siguientes 4 periodos en las siguientes cantidades: . . Se sabe que los costos variables de producción son: . Asumiendo que se puede utilizar inventarios, a un costo de h/unidad . Formular un programa lineal para minimizar los costos totales, combinación de costos de producción mas costos por llevar inventario.
Modelo de Inventario-Producción
D D D D1 2 3 4, , ,4321 ,,, CCCC
De lo siguiente:
Inv. final = Inv. inicial + Producción – Demanda
Definiendo :
x Cantidad a producir por periodo.
I0 Como el inventario Inicial.
I Como el inventario Final.
Solución
Período 1:
Período 2:
Período 3:
Período 4:
Solución
I I x D1 0 1 1
I I x D2 1 2 2
I I x D3 2 3 3
I I x D4 3 4 4
Luego el costo total viene dado por la
z = c1x1 + c2x2 + c3x3 + c4x4 + h(I1+I2+I3+I4)
Generalizando para un horizonte de planeación a n periodos:
Solución
Generalizando para un horizonte de planeación a n periodos:
Solución
niI
x
niDxII
hIx
i
i
iiii
i
iin
i
n
i
,,2,1, 0
0
,,2,1,
: sa
=zMin
1
11
Una persona compra y vende artículos. Su depósito posee una capacidad de B unidades. Cada mes puede vender cualquier cantidad sin sobrepasarse el inventario a principios del mes.
Sean ci y pi, el valor de compra y el precio respectivo para cada mes. ¿Cuál deberá ser la política óptima para n períodos, si el inventario inicial es Io?
El Problema del Almacén
Sea:
yi = cantidad a vender.
xi = cantidad a comprar.
La función objetivo:
Solución
Max z ( )p y c xi i i i
i
n
1
La función objetivo:
Restricciones:
Solución
Max z ( )p y c xi i i i
i
n
1
niyx
niByxI
BienfinalInventario
niIxy
yxIy
imesdeinicioaInventarioy
ii
kk
kk
kki
i
i
k
i
k
i
k
i
k
,,2,1, 0,
,,2,1,
,,2,1,
: a eequivalent
1
1
11
1
1
0
0
0
Necesito obtener informacion para una semana de 3 turnos, tengo que producir como maximo 500 unid, se dispone de 10 trabajadores ´para el primer turno, 7 para el segundo, 5 para el tercero.
Para ofrecer un minimo de 300 unidades, dispongo de 10 trabajadores en el primer turno, 7 en el segundo y 5 en el tercer turno.Por cada articulo se va a recibir una renta de S/.2.00para el primero y los dos productos se procesan secuencialment en los 3 turnos empleando tiempos diferentes.
1 turno requiere 2 horas; 2turno tambien 2 horas y en el 3 turno, 1 hora para el primer producto para el segundo producto requiero 1 hora para el primer turno 2 horas para el segundo turno y media hora para el tercer turno.
El señor Martínez tiene un pequeño camión con capacidad interior de 20m3en el cual transporta mercancía. Una reconocida empresa de la ciudad le ha contratado para hacer acarreos de esta mercancía, desde la planta de producción, hacia los puntos de distribución. La mercancía está empacada en cajas de 3 tamaños diferentes. Además la ganancia por transportar cada tipo de caja es distinta.
Ejemplo: Asignación de Recursos
¿ Cómo debe llenar el señor Martínez su camión para maximizar las ganancias en cada viaje que realice, si tiene que transportar como mínimo 8 cajas tipo 1 y 5 cajas tipo 3 en cada viaje ?
Caja tipo 1
Caja tipo 2
Caja tipo 3
1 m3 $ 1000 c/u
1,2 m3 $ 1120 c/u
0.8 m3 $ 900 c/u
X1: Número de cajas tipo 1 : transportados en cada viaje [caja/viaje]
X2: Número de cajas tipo 2 : transportados en cada viaje [caja/viaje]
X3: Número de cajas tipo 3 : transportado
Definición de Variables.
Coeficientes de costo (utilidad): Datos
Medida de la eficiencia (F. O.)
Z: Ganancia total (pesos) por el transporte de : los 3 tipos de cajas en cada viaje.
Max Z = 1000X1+ 1120X2 + 900X3
[$/ caja] * [caja/viaje] = [$/ viaje]
R1: Capacidad del camión (recurso)
X1+ 1.2X2 + 0.8 X3 ≤ 20
[m3/ caja] * [caja/viaje ] = [m3/viaje]R2: Mínimo de mercancía tipo 2 (requerimiento)
X1≥8 [caja/viaje ]
R3 : Mínimo de mercancía tipo 2 (requerimiento)
X3 ≥ 5 [caja/viaje ]
Restricción de signo de las variables
X1, X2 , X3 ≥ 0
Restricciones funcionales
Max Z = 1000X1+ 1120X2 + 900X3
s.a.
X1+ 1.2X2 + 0.8 X3 ≤ 20
X1 ≥8
X3 ≥ 5
X1, X2 , X3 ≥ 0
Modelo completo.
Top Related