Transcript
Ap Apuntes
Inve nvestig stiga aci ción ón de de Operaci peracion one es Lic. Miguel González Hipólito y Lic. Oscar Mayo Leytte
http://omlay.iespana.es
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
INDICE DEL MODULO:
CONTENIDO
Página
3. PROGRAMACION LINEAL 3.1 Definición 3.2 3.2 Requerimientos básicos 3.3 3.3 Etapas Etapas de solución soluci ón y prob lemas de ejemplo ejemplo Problema 1 Problema 2 Problema 3 Problema 4 Problema 5
3.4 Casos especiales 3.5 3.5 L a dualidad y los precios somb ra (análisis (análisis prelimi nar) 3.6 3.6 Probl emas propuestos propu estos
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
2
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Capítulo
3 PROGRAMACION LINEAL 3.1 Definición La Programación Lineal (PL) puede definirse como la técnica matemática para determinar la mejor asignación de recursos limitados. La programación lineal es un método determinista de análisis para elegir la mejor entre varias alternativas. Cuando esta mejor alternativa incluye un conjunto coordinado de actividades, se le puede llamar plan o programa. Programar significa seleccionar la mejor combinación de actividades. Con frecuencia seleccionar una alternativa incluye satisfacer varios criterios al mismo tiempo, por ejemplo, cuando se alquila una habitación en un hotel se tiene el criterio de que la habitación sea confortable, limpia, con las comodidades básicas, el precio accesible, etc. Se puede ir un paso más adelante y dividir estos criterios en dos categorías: las restricciones y el objetivo. Las restricciones son las condiciones que debe satisfacer una solución que esta analizándose. Si más de una alternativa satisface todas las restricciones, el objetivo se usa para seleccionar la mejor entre todas las alternativas factibles, a lo cual se le llama optimizar. Optimizar va en uno de dos posibles sentidos: maximizar maximizar o minimizar. Se optimizará maximizando, cuando nuestra intención es alcanzar los mas altos beneficios posibles, en tanto que se optimizará minimizando, cuando nuestra intención es obtener los menores costos posibles en un problema específico. Existen muchos problemas administrativos que se ajustan a este molde de tratar de maximizar o minimizar un objetivo que esta sujeto a una lista de restricciones. Un hotelero, por ejemplo, trata de maximizar sus utilidades en relación a mejorar y ampliar sus diferentes servicios, con el empleo más óptimo de sus recursos y la satisfacción de sus clientes. Un Restaurante debe planear que las comidas satisfagan ciertas restricciones sobre sabor, propiedades nutritivas, tipo y variedad, al mismo tiempo que se trata de minimizar el costo. La programación lineal se ha aplicado con éxito a estos y otros problemas. La programación lineal es una técnica determinista, no incluye probabilidades. El objetivo y cada una de las restricciones se deben expresar como una relación lineal, de ahí su nombre. El tema de programación lineal es muy extenso. Forma una de las ramas del campo de la programación matemática, como se ilustra a continuación:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
3
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
PROGRAMACIÓN MATEMÁTICA
PROGRAMACIÓN LINEAL
OTRAS OPCIONES
Método Gráfico
Programación no lineal
Método Simplex
Programación estocástica
Programación por objetivos
Programación Dinámica
Programación entera
Otras
Método del transporte Método de asignación de recursos
3.2 3. 2 Re Requerimientos querimientos básicos La Programación Lineal tiene los siguientes requerimientos básicos: 1. Que se defina defina claramente claramente una función funci ón objetivo en forma matemática matemática 2. Debe haber varios cursos alternativos de acción 3. Las ecuaciones ecuaciones y desigu desigualdades aldades deben describir describi r el el problema en forma lineal 4. Debe ser posible posi ble establecer relaciones entre las variables a través través de formulaciones matemáticas que pueden describir el problema y todas las relaciones entre las variables 5. Existe un suministro sumin istro limitado limi tado de recursos
3.3 3. 3 Et Etapa apass de soluci solución ón y prob problemas lemas El método grafico es una de las formas más sencillas para resolver problemas de programación lineal, cuando estos se refieren a únicamente dos variables. Este método permite visualizar el MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
4
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
proceso de solución de la programación lineal. Sin embargo, esta severamente limitado en sus aplicaciones por que el numero de dimensiones en la grafica es igual que el numero de variables. Pero aún con todas sus limitaciones, el método gráfico nos es muy útil para entender como funciona la Programación Lineal para optimizar (maximizar o minimizar) y como una ilustración de la manera como el Método Simplex (que veremos mas adelante), analizará y determinará la mejor solución posible.
Etapas de solución de un problema de programación lineal por el método grafico: ETAPA 1.-
FORMULA FORMULAR R EL PROBL PROBLEMA EMA Y CONSTRU CONSTRUIR IR EL MODELO MATEMÁTICO DE PROGRAMACIÓN PROGRAMACIÓN LINEAL .
El primer paso, consiste en plantear el problema y expresarlo en términos matemáticos bajo el formato general de la programación lineal, en otras palabras determinar el modelo matemático de programación lineal, compuesto de una función objetivo y las restricciones (condiciones) a las cuales esta sujeta Se puede iniciar respondiendo a las siguientes preguntas:
¿Que busca determinar el modelo?, es decir, ¿Cuales son las variables (incógnitas) variables (incógnitas) del problema? ¿Que r estricciones deben estricciones deben imponerse a las variables a fin de satisfacer las limitaciones del sistema representado por el modelo? ¿Cual es el objetivo (meta) objetivo (meta) que necesita alcanzarse para determinar la solución óptima (mejor) de entre todos los valores factibles de las variables?
El punto crucial del modelo matemático consiste en identificar en 1er. lugar las variables y después expresar el objetivo y las restricciones como funciones funci ones matemáticas de las variables.
ETAPA 2.-
GRAFICAR LAS RESTRICCIO RESTRICCIONES NES Y DETERMI DETERMINAR NAR EL AREA DE SOLUCIONES SOLUCIONES BASICAS FACTIBLES
El segundo paso es graficar cada restricción en el plano cartesiano, para definir definir el espacio de soluciones básicas factibles a que dan lugar, es decir, identificando hacia donde esta el área que de acuerdo al signo de de desigualdad corresponde a cada ecuación. Determinando luego, las coordenadas que están en los cruces de las restricciones entre sí y con los ejes MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
5
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
cartesianos, pero dentro del espacio de soluciones, es decir, dentro de las áreas que de acuerdo al signo de desigualdad les correspondan. ETAPA 3.- OBTENER LA SOLUCION OPTIMA. OPTIMA. El tercer paso consiste en sustituir en la función objetivo del modelo matemático, cada una de las coordenadas donde se cruzan las restricciones entre sí ó con los ejes cartesianos pero dentro del espacio o área de soluciones básicas factibles, en otras palabras, las coordenadas que están en los “picos” del espacio de soluciones, observando donde se alcanza el valor mas alto (si estamos maximizando) o donde se obtiene el valor mas bajo (si estamos minimizando). Luego, seleccionaremos como resultado óptimo, las coordenadas donde se alcanza el máximo (si estamos maximizando) o el mínimo valor en la función objetivo (si estamos minimizando). ETAPA 4.- ANA LISIS DE SENSIBILIDAD. SENSIBILIDAD. Esta etapa consiste en determinar que tanto podrían variar los recursos considerados en el problema, sin que se afecte el óptimo alcanzado, se aplica tanto a los coeficientes de la Función Objetivo, como a los coeficientes de cada una de las restricciones. En los problemas de ejemplo se dejará para más adelante su aplicación, con el fin de permitir el aprendizaje de las primeras tres etapas.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
6
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
PROBLEMAS DE EJEMPLO: PROBLEMA Núm. 1 Una empresa dedicada a la transportación turística ofrece dos recorridos en un parque arqueológico, uno diurno y otro nocturno. Al guía se le pagan 6 dólares por recorrido recorrido diurno y 5 dólares por recorrido recorrido nocturno. El recorrido incluye la entrada a una galería que cuesta 2 dólares en el diurno y 3 dólares en el nocturno. Los costos de operación operación ascienden a 3 dólares por recorrido recorrido diurno y 12 dólares por recorrido nocturno. La utilidad es de 2 dólares por el recorrido diurno y 1 dólar por el nocturno. Únicamente se cuenta con 30 dólares para salarios de guías, 12 dólares para entradas a la galería y no se quiere que los costos de operación excedan 36 dólares. ¿Cuántos recorridos diurnos y cuántos recorridos nocturnos se deben programar para obtener las mayores utilidades?
SOLUCION DEL PROBLEMA ETAPA No. 1.- FORMULACION DEL PROBLEMA Y CONSTRUCCION DEL MODELO MATEMATICO OBJETIVO (VERBAL).- Se desea determinar cuántos recorridos diurnos y nocturnos se deben programar para obtener las mayores utilidades por tanto, se trata de una maximización. RESTRICCIONES (VERBALES) 1.- Solo se dispone de 30 dólares para salarios de los guías. 2.- Solo se dispone de 12 dólares para entradas a la galería. 3.- No se quiere que los costos de operación excedan los 36 dólares. VARIABLES (ESTRUCTURA MATEMÁTICA) Para representar las variables de decisión (o incógnitas del problema) se establece que: X1 = Número de recorridos diurnos X2 = Número de recorridos nocturnos
VARIABLES DE DECISIÓN DECISIÓN ó INCÓGNITAS DEL PROBLEMA
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
7
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COEFICIENTES DE LA FUNCION OBJETIVO (Z) La función objetivo se expresa en dólares y representa maximizar las utilidades de cada tipo de recorrido, por tanto se establece que: C1 = $2 dólares = utilidad por recorrido diurno C2 = $1 dólares = utilidad por recorrido nocturno Función Objetivo:
Max
Z = C1X1 + C2X2
Max
Z = 2X1 + X2
Apoyándonos ahora, en una tabla de doble entrada entrada para facilitar la construcción del modelo matemático, asentamos la información de referencia en el problema de la siguiente forma:
RECORRIDOS RUBROS SALARIOS COSTO DE ENTRADA A GALERÍA COSTOS DE OPERACION Función Objetivo: Max Z
Recorrido Diurno X1
Recorrido Nocturno X2
6 2 3 $2
5 3 12 $1
Restricciones 30 12 36
Observamos la interrelación entre los datos y determinamos el modelo matemático, al considerar que la tabla se puede re-escribir de la siguiente manera:
RECORRIDOS RUBROS SALARIOS COSTO DE ENTRADA A GALERÍA COSTOS DE OPERACION Función Objetivo: Max Z
Recorrido Diurno X1
Recorrido Nocturno X2
Restricciones
6 X1 2 X1 3 X1 $2 X1
5 X2 3 X2 12 X2 $1 X2
≤ 30 ≤ 12 ≤ 36
El modelo matemático para el problema estará dado entonces por:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
8
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Función Objetivo:
Max Z = 2X1 + X2
Sujeto a: 6 X 1 + 5 X 2 ≤ 30 ...... I 2 X 1 + 3 X 2 ≤ 12 ...... II
Restricciones
3 X 1 + 12 X 2 ≤ 36 .... III X 1 ≥ 0 , X 2 ≥ 0
ETAPA No. No. 2
GRAFICAR LA S RESTRICCIONES RESTRICCIONES Y DETERMINAR DETERMINAR EL AREA DE SOLUCIONES BASICAS FACTIBL FA CTIBLES ES
Obtener los parámetros para graficar cada una una de las restricciones: restricciones: Para la restricción I
6 X 1 + 5 X 2 = 30..... I Si X 1 = 0
30
X 2 =
5
=6
Si X 2 = 0 X 1 =
30 6
=5
B (5, 0)
A(0, 6)
Para la restricción II
2 X 1+3 X 2 = 12....... II Si X 1 = 0 X 2 =
12 3
=4
Si X 2 = 0 X 1 =
12 2
=6
D (6, 0)
C (0, 4)
Para la restricción III
3 X 1 + 12 X 2 = 36........ III Si X 1 = 0 X 2 =
36
12 E (0, 3)
Si X 2 = 0
X1 =
3
36 3
12
F(12, 0)
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
9
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE RESTRICCION I
7
A (0,6)
6 5 4 2
X
3
ESPACIO DE SOLUCIONES
2 1
B (5,0)
0 0
1
2
3
4
5
6
X1
GRAFICA DE RESTR ICCION II
4.5
C (0,4)
4 3.5 3 2
2.5
X
2 1.5
ESPACIO DE SOLUCIONES
1 0.5
D (6,0)
0 0
1
2
3
4
5
6
7
X1
GRAFICA DE RESTRICCION III
3.5
E (0,3)
3 2.5 2 2
X
1.5 1
ESPACIO DE SOLUCIONES
0.5
F (12,0)
0 0
2
4
6
8
10
12
14
X1
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
10
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COLOCANDO TODAS LAS RESTRICCIONES EN UN SOLO GRAFICO E IDENTIFICANDO EL AREA O ESPACIO DE SOLUCIONES SIMULTANEAS, TENEMOS: TENEMOS: GRAFICA DE TODAS LAS RES TRICCIONES TRICCIONES 7
E (0,3)
6 5
I
4
R
2
X
II
3
III III
S
2
ESPACIO DE SOLUCIONES
1 0 0
2
4
6
B (5,0)
8
10
12
14
X1
ETAPA No. No . 3 OBTENER LA SOLUCION OPTIMA OPTIMA POR PRUEBA Y ERROR Considerando cada coordenada del área de soluciones básicas factibles (área sombreada de la gráfica), donde se cruzan las restricciones entre sí ó con los ejes cartesianos, se obtiene en la Función Objetivo, el resultado de la sustitución de tales coordenadas se muestra a continuación:
CALCULO DE ¨R¨ (Cruce de Ecuación II con Ecuación III)
(−4)2 X 1 + 3 X 2 = 12 II L
3X 1 + 12X 2 = 36 III L
Sustituyendo X 1 en Ecuación II , tenemos :
2 X 1 + 3 X 2 = 12....... II
__________ _________ - 8X 1 - 12X 2 = -48
2(2.4) + 3 X 2 = 12
3X 1 + 12X 2 = 36
4.8 + 3 X 2 = 12 3 X 2 = 12 − 4.8
__________ _________ - 5X 1 X1 X1
3 X 2 = 7.2
= -12 = -12/ - 5 = 2.4
X 2 = 7.2 / 3 X 2 = 2.4
Nota: No puede haber X1 = 2.4 recorridos diurnos, solo para efectos de estos cálculos no se redondea R (2.4, 2.4)
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
11
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
CALCULO DE ¨S¨ (Cruce de Ecuación I con Ecuación II)
6 X 1 + 5 X 2 = 30 I
sustituyendo X 2 = 1.5
L
(−3)2 X 1 + 3 X 2 = 12 II
en Ecuación I , se tiene :
L
__________ ________
6 X 1 + 5 X 2 = 30
6 X 1 + 5 X 2 = 30
6 X 1 + 5(1.5) = 30
− 6 X 1 − 9 X 2 = −36
6 X 1 + 7.5 = 30 6 X 1 = 30 − 7.5
__________ ________
− 4 X 2 = −6 X 2 = −6 / − 4 X 2 = 1.5
6 X 1 = 22.5 X 1 = 22.5 / 6 X 1 = 3.75
Nota: No Nota: No puede haber X 1 = 3.75 recorridos diurnos, solo para efectos de estos cálculos no se redondea S (3.8, 1.5)
GRAFICA DE TODAS LAS RES TRICCIONES TRICCIONES 7
E (0,3)
6 5 2
X
I
R (2.4, 2.4)
4
II 3
S (3.8, 1.5)
III III
2
ESPACIO DE SOLUCIONES
1 0 0
2
4
6
B (5,0)
8
10
12
14
X1
Los cruces de las restricciones entre si y con los ejes cartesianos dentro del Espacio de Soluciones (los picos), constituyen los puntos de solución factible, los cuales al sustituirlos en la Función Objetivo, nos permitirán identificar cual de ellos alcanza el valor máximo, es decir, el valor optimo
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
12
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
SUSTITUYENDO CADA UNA DE LAS COORDENADAS EN LA FUNCION OBJETIVO TENEMOS Punto E (0, 3) Implica: Ningún Recorrido diurno y 3 nocturnos Max Z = 2 X 1 + X 2
Punto R (2.4, 2.4) Implica: 2.4 Recorridos diurnos y 2.4 nocturnos Max Z = 2 X 1 + X 2
Z = 2(0) + 1(3)
Z = 2( 2.4) + 1( 2.4)
Z = 0 + 3
Z = 4.8 + 2.4
Z = $3.00 dólares
Z = $7.20 dólares
de utilidad
de utilidad
Punto S (3.8, 1.5) Implica: 3 Recorridos diurnos y un nocturno Max Z = 2 X 1 + X 2
Punto B (5, 0) Implica: 5 Recorridos diurnos y ningún nocturno Max Z = 2 X 1 + X 2
Z = 2(3.8) + 1(1.5)
Z = 2(5) + (0)
Z = 7.6 + 1.5
Z = 10 + 0
Z = $9.10 dólares
Z = $10.00 dólares
de utilidad
de utilidad
<<>> Los resultados nos indican que el punto “B” es donde se obtienen las mayores utilidades, con 5 recorridos diurnos y ningún recorrido nocturno para alcanzar así, $10.00 dólares de utili dad.
Grafiquemos ahora la Función Objetivo Elegimos de manera arbitraria un número, por ejemplo el 6 para la igualdad de la Función Objetivo, como primera aproximación: Max Z = 2 X 1 + X 2 = 6 Si X 2 = 0
Si X 1 = 0
X 1 =
X 2 = 6
6
2 H (3, 0)
G (0, 6)
=3
Observamos a continuación la Gráfica de la Función Objetivo preliminar en líneas punteadas:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
13
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO 7 6 5 4 X2 3 2 1 0
I II III Z
ESPACIO DE SOLUCIONES
0
2
4
6
Z
8
10
12
14
X1
Ahora desplacemos paralelamente la recta de la Función Objetivo “cuesta arriba”, hasta el máximo punto donde tenga contacto con el Espacio de Soluciones, esto será generalmente en alguno de los cruces de las restricciones entre sí o con los ejes cartesianos; en este caso es donde se cruza la Restricción (I) con el eje de las X 1, es decir, en el punto ¨B¨ de coordenadas (5, 0) como se ilustra a continuación:
GRAFICA DE TODAS RESTRICCIONES Y DE FUNCION OBJETIVO 7 6 5 4 X2 3 2 1 0
I II III
OPTIMO
Z
ESPACIO DE SOLUCIONES
0
2
4
6 B (5,0)
8
10
12
14
X1
Es otra manera de determinar gráficamente el punto óptimo (máximo), donde se obtienen los mayores beneficios y que por supuesto, coincide con lo calculado por prueba y error
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
14
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Al sustituir estas coordenadas en la Función Objetivo, vemos que se alcanza una utilidad máxima de: Max Z = 2 X 1 + X 2 Z = 2(5) + 0 Z = 10 + 0 Z = $10.00 dólares de utilidad
Esto significa realizar 5 recorridos diurnos y ninguno nocturno, como antes ya habíamos visto.
GRAFICA DE SOLUCION COMPLETA COMPLETA POR EL METODO METODO GRAFICO
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
15
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
PROBLEMA Núm. 2 Se contrato una agencia de edecanes para realizar un servicio de guías en una exposición. La exposición se divide en dos secciones: 1) Sección de Exhibición y 2) Sección de Talleres Un grupo de estudiantes de secundaria tarda una hora en el área de exhibición y 3 horas en el área de talleres; mientras que un grupo de estudiantes de primaria tarda 2 horas en el área de exhibición y una hora en el área de talleres. El área de exhibición permanece abierta un máximo de 10 horas, mientras que el área de talleres puede abrirse hasta 15 horas. No se puede atender a más de 4 grupos de primaria por día. La utilidad por grupo de primaria es de $60.00 y por grupo de secundaria es de $50.00 ¿Cuántos ¿Cuántos g rupos de cada nivel se deben p rogramar diariamente para obtener obtener las mayores ut il i dades?
SOLUCION DEL PROBLEMA ETAPA No. 1.- FORMULACION DEL PROBLEMA Y CONSTRUCCION DEL MODELO MATEMATICO OBJETIVO (VERBAL).- Se desea determinar cuántos grupos de primaria y cuantos grupos de secundaria se deben programar diariamente para obtener las mayores utilidades por esa razón, se trata de una maximización. RESTRICCIONES (VERBALES) 1.- El área de exhibición permanece abierta un máximo de 10 horas 2.- El área de talleres puede abrirse hasta 15 horas. 3.- No se puede atender a más de 4 grupos de primaria por día.
VARIABLES ( ESTRUCTURA MATEMÁTICA) Para representar las variables de decisión (o incógnitas del problema) se establece que:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
16
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
X1 = Número de grupos de primaria programados por día
VARIABLES DE DECISIÓN DECISIÓN ó INCÓGNITAS DEL PROBLEMA
X2 = Número de grupos de secundaria programados por día
COEFICIENTES DE LA FUNCION OBJETIVO (Z) La función objetivo se expresa en dólares y representa maximizar las utilidades de cada tipo de recorrido, por tanto se establece que: C1 = $60 = utilidad por grupo de primaria C2 = $50 = utilidad por grupo de secundaria Función Objetivo:
Max
Z = C1X1 + C2X2
Max
Z = 60X1 + 50X2
Apoyándonos ahora, en una tabla de doble entrada entrada para facilitar la construcción del modelo matemático, asentamos la información de referencia en el problema de la siguiente forma: Grupos de Primaria
Grupos de Secundaria
INSUMOS
X1
X2
EXHIBICION TALLERES DISPONIBILIDAD DISPONIBILIDAD DE ATENCION Función Objetivo: Max Z
2 1
1 3
TIPO DE GRUPO
X1
$60
Restricciones 10 15 4
$50
Observamos la interrelación entre los datos y determinamos el modelo matemático, al considerar que la tabla se puede re-escribir de la siguiente manera: Grupos de Primaria
Grupos de Secundaria
INSUMOS
X1
X2
EXHIBICION TALLERES DISPONIBILIDAD DISPONIBILIDAD DE ATENCION Función Objetivo: Max Z
2X1
TIPO DE GRUPO
X1 X1 60X1
Restricciones
X2
3X2 50X2
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
≤ 10 ≤ 15 ≤ 4
17
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
El modelo matemático para el problema probl ema estará dado entonces por: Función Objetivo:
Max Z = 60X1 + 50X2
Sujeto a: 2 X 1 + X 2 ≤ 10 ...... I X 1 + 3 X 2 ≤ 15 ...... II
Restricciones
X 1 ≤ 4 .... III X 1 ≥ 0 , X 2 ≥ 0
ETAPA No. No. 2
GRAFICAR LA S RESTRICCIONES RESTRICCIONES Y DETERMINAR DETERMINAR EL AREA DE SOLUCIONES BASICAS FACTIBL FA CTIBLES ES
Obtener los parámetros para graficar cada una una de las restricciones: restricciones: Para la restricción I
2 X 1 + X 2 = 10..... I
Si X 2 = 0
⎫ ⎪ 10 ⎬ B (5, 0) X 1 = = 5⎪ 2 ⎭
Si X 1 = 0 ⎫
⎬ A(0, 10)
X 2 = 10⎭
Para la restricción II X 1 + 3 X 2 = 15..... II Si X 1 = 0
⎫ ⎪ 15 ⎬ C (0, 5) X 2 = = 5⎪ 3 ⎭
Si X 2 = 0 ⎫
⎬ D(15, 0)
X 1 = 15⎭
La restricción III (X 1 = 4) es una constante, constante, desde X2 = 0 hasta X2 = infinito
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
18
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COLOCANDO TODAS LAS RESTRICCIONES EN UN SOLO GRAFICO E IDENTIFICANDO EL AREA O ESPACIO DE SOLUCIONES, TENEMOS: GRAFICA DE TODAS LAS R ESTRICCIONES
X1=4
12 10
A (0,10) I
8 2
X
6
R
II
C (0,5)
III III
S
4
ESPACIO DE SOLUCIONES
2
B (5,0)
0 0
2
4
6
D (15,0) 8
10
12
14
16
X1
E (4,0)
ETAPA No. No . 3 OBTENER LA SOLUCION OPTIMA OPTIMA POR PRUEBA Y ERROR Considerando cada coordenada del área de soluciones básicas factibles (área sombreada de la gráfica), donde se cruzan las restricciones entre sí ó con los ejes cartesianos, se obtiene en la Función Objetivo, el resultado de la sustitución de tales coordenadas se muestra a continuación: CALCULO DE ¨R¨ (Cruce de Ecuación I con Ecuación II)
2 X 1 + X 2 = 10 I L
(−2) X 1 + 3 X 2 = 15 II
Sustituyendo X2 = 4 en Ecuación I, tenemos:
L
2 X 1 + X 2 = 10
2 X 1 + X 2 = 10 2 X 1 + 4 = 10
− 2 X 1 − 6 X 2 = −30 − 5 X 2 = −20
2 X 1 = 10 − 4 2 X 1 = 6
X 2 =
− 20 −5
X 1 =
6 2
X 2 = 4 X 1 = 3
Las coordenadas del punto “R” son: (3, 4) MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
19
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
CALCULO DE ¨S¨ (Cruce de Ecuación I con Ecuación III)
2 X 1 + X 2 = 10..... I X 1 = 4....... III
Sustituyendo X1 = 4 en Ecuación I, tenemos:
2 X 1 + X 2 = 10 2(4) + X 2 = 10 8 + X 2 = 10 X 2 = 10 − 8 X 2 = 2
Las coordenadas del punto “S” son: (4, 2)
GRAFICA DE TODAS LAS R ESTRICCIONES
X1=4
12 10
A (0,10) I
8 2
X
R (3, 4) 6
II
C (0,5)
III III
S (4, 2)
4
ESPACIO DE SOLUCIONES
2
B (5,0)
0 0
2
4
E (4,0)
6
D (15,0) 8
10
12
14
16
X1
Los cruces de las restricciones entre si y con los ejes cartesianos pero dentro del Espacio de Soluciones, constituyen los puntos de solución factible, los cuales al sustituirlos en la Función Objetivo, nos permitirán identificar cual de ellos alcanza el valor máximo, es decir, el valor optimo
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
20
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
SUSTITUYENDO CADA UNA DE LAS COORDENADAS EN LA FUNCION OBJETIVO TENEMOS Punto C(0,5)
Punto R(3,4)
Punto S(4,2)
Punto E(4,0)
Max Z = 60 X 1 + 50 X 2 Max Z = 60 X 1 + 50 X 2 Max Z = 60 X 1 + 50 X 2 Max Z = 60 X 1 + 50 X 2 Z = 60(4) + 50(2) Z = 60(3) + 50(4) Z = 60(4) + 50(0) Z = 60(0) + 50(5) Z = 0 + 250
Z = 180 + 200
Z = 240 + 100
Z = $250.00
Z = $380.00
Z = $340.00
Z = $240.00
<<>> Se concluye que el punto “R” es donde se obtienen las mayores utilidades, debiendo programarse por día 3 grupos de primaria y 4 grupos de secundaria logrando así la más alta utilidad que será de $380.00
Grafiquemos ahora la Función Objetivo Elegimos de manera arbitraria un número, por ejemplo el 180 para la igualdad de la Función Objetivo, como primera aproximación: Max Z = 60X1 + 50X2 = 180 Si X1 = 0
Si X2 = 0
X2 = 3.6
X1 = 3
G (0, 3.6)
H (3, 0)
Observamos a continuación la Gráfica de la Función Objetivo preliminar en líneas punteadas:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
21
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO X2
12 10
X1=4 A (0,10)
8 6
I II III Z
R (3, 4) C (0,5) S (4, 2)
4 ESPACIO DE SOLUCIONES
2
B (5,0)
0 0
2
4
6
D (15,0)
8
10
12
14
16 X1
E (4,0)
Ahora desplacemos paralelamente la Gráfica de la Función Objetivo “cuesta arriba”, hasta el máximo punto donde tenga contacto con el Espacio de Soluciones, esto será generalmente en alguno de los cruces de las restricciones entre sí o con los ejes cartesianos; en e ste caso es donde se cruza la Ecuación 1 con la Ecuación II, es decir, en el punto ¨R¨ de coordenadas (3, 4) como se ilustra a continuación:
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO X2
12 10
X1=4 A (0,10)
8 6
I II III Z
R (3, 4) C (0,5) S (4, 2)
4 ESPACIO DE SOLUCIONES
2
B (5,0)
0 0
2
4
6
D (15,0)
8
10
12
14
16 X1
E (4,0)
Es otra manera de determinar gráficamente el punto óptimo (máximo), donde se obtienen los mayores beneficios y que por supuesto, coincide con lo calculado por prueba y error Al sustituir estas coordenadas en la Función Objetivo, Objetivo, vemos que se alcanza una utilidad de: MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
22
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Max Z = 60 X 1 + 50 X 2 Z = 60(3) + 50( 4) Z = 180 + 200 Z = $380.00
Esto significa que deben programarse por día 3 grupos de primaria y 4 grupos de secundaria, como ya se había definido.
GRAFICA DE SOLUCION COMPLETA COMPLETA POR EL METODO METODO GRAFICO
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
23
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
PROBLEMA Núm. 3 Una agencia de viajes está planeando dos paquetes diferentes para visitar el sureste mexicano: “Sureste Inolvidable” y “Sureste Mágico”. La agencia normalmente vende todos los paquetes que ofrece. El primer paquete consiste en dos noches de estancia en Mérida, una noche en Chetumal y cuatro noches en Cancún. El segundo paquete consiste en dos noches en Mérida, dos noches en Chetumal y dos noches en Cancún. La agencia de viajes ha establecido un contrato con varios hoteles en los destinos visitados y tiene 160 noches reservadas en Mérida, 120 en Chetumal y 280 en Cancún. La ganancia que se obtiene por cada paquete “Sureste Inolvidable” es de $1,000.00 y por cada paquete “Sureste Mágico” es de $1,500.00 ¿Cuántos paquetes de cada tipo se deben ofertar para obtener las mayores utilidades?
SOLUCION DEL PROBLEMA ETAPA No. 1.- FORMULACION DEL PROBLEMA Y CONSTRUCCION DEL MODELO MATEMATICO OBJETIVO (VERBAL).- Se desea determinar cuántos paquetes de cada tipo se deben ofertar para obtener las mayores utilidades por tanto, se trata de una maximización. RESTRICCIONES (VERBALES) 1.- Solo se dispone de 160 noches para Mérida. 2.- Solo se dispone de 120 noches para Chetumal. 3.- Solo se dispone de 280 noches para Cancún. VARIABLES ( ESTRUCTURA MATEMÁTICA) Para representar las variables de decisión (o incógnitas del problema) se establece que: X1 = Número de paquetes “Sureste Inolvidabl e” X2 = Número de paquetes “Sureste Mágico”
VARIABLES DE DECISIÓN DECISIÓN ó INCÓGNITAS DEL PROBLEMA
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
24
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COEFICIENTES DE LA FUNCION OBJETIVO (Z) La función objetivo se expresa en pesos y representa maximizar las utilidades de cada tipo de paquete, por tanto se establece que: C1 = $1,000 pesos = utilidad por paquete “Sureste Inolvidable” C2 = $1,500 pesos = utilidad por paquete “Sureste “Sureste Mágico” Función Objetivo:
Max
Z = C1X1 + C2X2
Max
Z = 1000X1 + 1500X2
Apoyándonos ahora, en una tabla de doble entrada entrada para facilitar la construcción del modelo matemático, asentamos la información de referencia en el problema de la siguiente forma:
PAQUETES NOCHES DE ESTANCIA MERIDA CHETUMAL CANCUN Función Objetivo: Max Z
“Sureste Inolvidable” X1
“Sureste Mágico” X2
2 1 4 $1,000
2 2 2 $1,500
Restricciones (Disponibilidad)
160 120 280
Observamos la interrelación entre los datos y determinamos el modelo matemático, al considerar que la tabla se puede re-escribir de la siguiente manera:
PAQUETES NOCHES DE ESTANCIA MERIDA CHETUMAL CANCUN Función Objetivo: Max Z
“Sureste Inolvidable” X1
“Sureste Mágico” X2
Restricciones
2 X1 1 X1 4 X1 $1000 X1
2 X2 2 X2 2 X2 $1500 X2
≤ 160 ≤ 120 ≤ 280
(Disponibilidad)
El modelo matemático para el problema estará dado entonces por:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
25
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Función Objetivo:
Max Z = 1000X1 + 1500X2
Sujeto a: 2 X 1 + 2 X 2 ≤ 160 ...... I X 1 + 2 X 2 ≤ 120 ...... II
4 X 1 + 2 X 2 ≤ 280 .... III
Restricciones
X 1 ≥ 0 , X 2 ≥ 0
ETAPA No. No. 2
GRAFICAR LA S RESTRICCIONES RESTRICCIONES Y DETERMINAR DETERMINAR EL AREA DE SOLUCIONES BASICAS FACTIBL FA CTIBLES ES
Obtener los parámetros para graficar cada una una de las restricciones: restricciones: Para la restricción I
2 X 1 + 2 X 2 = 160..... I Si X 1 = 0 ⎫
Si X 2 = 0 ⎫
X 2 = 80⎭
X 1 = 80⎭
⎬ A(0, 80)
⎬ B (80, 0)
Para la restricción II X 1 + 2 X 2 = 120........ II Si X 1 = 0 ⎫
Si X 2 = 0 ⎫
X 2 = 60⎭
X 1 = 120⎭
⎬ C (0, 60
⎬ D(120, 0)
Para la restricción III
4 X 1 + 2 X 2 = 280..... III Si X 1 = 0
⎫ ⎬ E (0, 140) X 2 = 140⎭
Si X 2 = 0 ⎫
⎬ F (70, 0)
X 1 = 70⎭
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
26
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COLOCANDO TODAS LAS RESTRICCIONES EN UN SOLO GRAFICO E IDENTIFICANDO EL AREA O ESPACIO DE SOLUCIONES SIMULTANEAS, TENEMOS: TENEMOS:
GRAFICA DE TODAS LAS RESTRICCIO RES TRICCIONES NES 160 140
E (0,140)
120 I
100 2
X
80
A (0,80)
II
R
III III
60
C (0,60)
S
40
ESPACIO DE SOLUCIONES
20
D (120,0)
0 0
20
40
60
80
X1
F (70,0)
100
120
140
B (80,0)
ETAPA No. No . 3 OBTENER LA SOLUCION OPTIMA OPTIMA POR PRUEBA Y ERROR Considerando cada coordenada del área de soluciones básicas factibles (área sombreada de la gráfica), donde se cruzan las restricciones entre sí ó con los ejes cartesianos, se obtiene en la Función Objetivo, el resultado de la sustitución de tales coordenadas se muestra a continuación: CALCULO DE ¨R¨ (Cruce de Ecuación I con Ecuación II)
2 X 1 + 2 X 2 = 160.... I (−1) X 1 + 2 X 2 = 120..... II 2 X 1 + 2 X 2 = 160
− X 1 − 2 X 2 = −120 X 1 = 40
Sustituyendo X 1 = 40 en Ecuación I , tenemos :
2 X 1 + 2 X 2 = 160........ I 2(40) + 2 X 2 = 160 80 + 2 X 2 = 160 2 X 2 = 160 − 80 2 X 2 = 80 X 2 =
80 2
X 2 = 40
Las coordenadas del punto “R” son: (40, 40) MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
27
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
CALCULO DE ¨S¨ (Cruce de Ecuación I con Ecuación III) Sustituyendo X 1 = 60
2 X 1 + 2 X 2 = 160 ≤ 160..... I (−1)4 X 1 + 2 X 2 = 280....... III
en Ecuación I , tenemos :
2 X 1 + 2 X 2 = 160
2 X 1 + 2 X 2 = 160
− 4 X 1 − 2 X 2 = −280 − 2 X 1 = −120
2(60) + 2 X 2 = 160 120 + 2 X 2 = 160 2 X 2 = 160 − 120
− 120 X 1 = −2
2 X 2 = 40
X 1 = 60
X 2 =
40 2
X 2 = 20
Las coordenadas del punto “S” son: (60, 20)
GRAFICA DE TODAS LAS RESTRICCIO RES TRICCIONES NES 160 140
E (0,140)
120 I
100 2
X
80
A (0,80)
60
C (0,60)
II
R (40, 40)
III III
S (60, 20)
40
ESPACIO DE SOLUCIONES
20
D (120,0)
0 0
20
40
60
F (70,0)
80
X1
100
120
140
B (80,0)
Los cruces de las restricciones entre si y con los ejes cartesianos pero dentro del Espacio de Soluciones, constituyen los puntos (coordenadas) de solución factible, los cuales al sustituirlos en la Función Objetivo, nos permitirán identificar cual de ellos alcanza el valor máximo, es decir, el valor optimo
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
28
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
SUSTITUYENDO CADA UNA DE LAS COORDENADAS EN LA FUNCION OBJETIVO TENEMOS Punto C (0, 60)
Punto F (70, 0)
Max Z = 1000 X 1 + 1500 X 2
Max Z = 1000 X 1 + 1500 X 2
Z = 1000(0) + 1500(60) Z = 0 + 90000
Z = 1000(70) + 1500(0) Z = 70000 + 0 Z = $70,000
Z = $90,000
Punto S (60, 20)
Punto R (40, 40)
Max Z = 1000 X 1 + 1500 X 2
Max Z = 1000 X 1 + 1500 X 2
Z = 1000(60) + 1500(20)
Z = 1000(40) + 1500( 40)
Z = 60000 + 30000
Z = 40000 + 60000
Z = $90,000
Z = $100,000
<<>> Se concluye que el punto “R” es donde se obtienen las mayores utilidades, debiendo ofertarse 40 paquetes “Sureste Inolvidable” y 40 paquetes “Sureste Mágico” logrando así la más alta utilidad que será de $100,00 pesos
Grafiquemos ahora la Función Objetivo Elegimos de manera arbitraria un número, por ejemplo el 50,000 para la igualdad de la Función Objetivo, como primera aproximación: Max Z = 1000X1 + 1500X2 = 50,000 Si X1 = 0
Si X2 = 0
X2 = 33
X1 = 50
G (0, 33)
H (50, 0)
Observamos a continuación la Gráfica de la Función Objetivo preliminar en líneas punteadas:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
29
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO 160 140 E (0,140) 120 100 X 2 80 A (0,80) 60 C (0,60) 40 ESPACIO DE SOLUCIONES 20 0 0 20
I II III Z
R (40, 40) S (60, 20) D (120,0)
40
60
F (70,0)
80 X1
100
120
140
B (80,0)
Ahora, desplacemos paralelamente la Gráfica de la Función Objetivo “cuesta arriba”, hasta el máximo punto donde tenga contacto con el Espacio de Soluciones, esto será generalmente en alguno de los cruces de las restricciones entre sí o con los ejes cartesianos; en este caso es donde se el cruza la Ecuación 1 con la Ecuación II, es decir, en el punto ¨R¨ de coordenadas (40, 40) como se ilustra a continuación:
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO 160 140 120 100 X 2 80 60 40 20 0
I II III Z
R (40, 40)
0
20
40
60
80
100
120
140
X1 Es otra manera de determinar gráficamente el punto óptimo (máximo), donde se obtienen los mayores beneficios y que por supuesto, coincide con lo calculado por prueba y error Al sustituir estas coordenadas en la Función Función Objetivo, vemos que se alcanza una utilidad utilidad de:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
30
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Max Z = 1000 X 1 + 1500 X 2 Z = 1000( 40) + 1500(40) Z = 40,000 + 60,000 Z = $100,000.00
Esto significa que deben ofertarse 40 paquetes “Sureste Inolvidable” y 40 paquetes “Sureste Mágico”, como ya antes se había definido.
GRAFICA DE SOLUCION COMPLETA COMPLETA POR LE METODO METODO GRAFICO
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
31
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
PROBLEMA Núm. 4 Un dietista esta tratando de seleccionar la combinación más barata de dos tipos de alimentos concentrados “K” y “W” de importación, que deben cumplir con ciertas necesidades diarias de vitaminas para turistas adultos mayores. Los requerimientos vitamínicos diarios son de al menos 40 unidades de vitamina “A”, 50 unidades de vitamina “B” y 49 unidades de vitamina “D”. Cada onza del alimento “K” proporciona 4 unidades de vitamina “A”, 10 unidades de vitamina “B” y 7 unidades de vitamina “D”, Cada onza del alimento “W” proporciona 10 unidades de vitamina “A”, 5 unidades de “B” y 7 unidades de “D”. El alimento “K” cuesta 0.50 centavos de dólar la onza y el alimento “W” cuesta 0.80 centavos de dólar la onza. ¿Cuantas onzas de cada alimento deben utilizarse para satisfacer las necesidades vitamínicas diarias diarias con el menor desembolso mon etario?
ETAPA No. 1.- FORMULACION DEL PROBLEMA Y CONSTRUCCION DEL MODELO MATEMATICO OBJETIVO (VERBAL).- Se pretende seleccionar la manera manera menos costosa para satisfacer las necesidades vitamínicas diarias, considerando la combinación de los alimentos “K” y “W”.
RESTRICCIONES (VERBALES) 1.- Se deben consumir por lo menos 40 unidades de Vitamina A 2.- Se deben consumir por lo menos 50 unidades de Vitamina B 3.- Se deben consumir por lo menos 49 unidades de Vitamina D
VARIABLES (ESTRUCTURA MATEMÁTICA) Determinar el número de onzas a elaborar de cada platillo esto define dos variables de decisión:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
32
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
X1 = Cantidad de onzas del alimento K
VARIABLES DE DECISIÓN ó INCÓGNITAS DEL PROBLEMA
X2 = Cantidad de onzas del alimento W
COEFICIENTE DE LA FUNCION OBJETIVO La función objetivo se expresa en dólares y nos muestra el desembolso en que se incurre por concepto de la compra de dos alimentos, por tanto, la función objetivo deberá ser una minimización con coeficientes: C1 = $0.50
Costo por onza de Alimento “K”
C2 = $0.80
Costo por onza de Alimento “W”
Función Objetivo es:
Min
Z = C1X1 + C2X2
Min
Z = 0.5X1 + 0.8X2
Apoyándonos ahora, en una tabla de doble entrada entrada para facilitar la construcción del modelo matemático, asentamos la información de referencia en el problema de la siguiente forma: AL IMENTOS VITAMINAS VITAMINA A VITAMINA B VITAMINA D Función Objetivo: Min Z
AL IMENTO K X1
AL IMENTO W X2
4 10 7 0.50
10 5 7 0.80
REQUERIMIENTOS 40 50 49
Observamos la interrelación entre los datos y determinamos el modelo matemático, al considerar que la tabla se puede re-escribir de la siguiente manera: AL IMENTOS VITAMINAS VITAMINA A VITAMINA B VITAMINA D Función Objetivo: Min Z
AL IMENTO K X1
AL IMENTO W X2
4 X1 10 X1 7 X1 0.50 X1
10 X2 5 X2 7 X2 0.80 X2
REQUERIMIENTOS
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
40 50 ≥ 49 ≥
≥
33
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
El modelo matemático para el problema estará dado entonces por: Función Objetivo:
Min
Z = 0.5X1 + 0.8X2
Sujeto a: 4X1 + 10X2 > 40 ………………..I 10X1 + 5X2 > 50 ………………..II Restricciones
7X1 + 7X2 > 49 ………………..III X1 > 0, X 2 > 0
ETAPA No. No. 2
GRAFICAR LA S RESTRICCIONES RESTRICCIONES Y DETERMINAR DETERMINAR EL AREA DE SOLUCIONES BASICAS FACTIBL FA CTIBLES ES
Obtener los parámetros para graficar cada una una de las restricciones: restricciones:
Para restricción I
4 X 1 + 10 X 2 = 40..... I Si X 1 = 0 X 2 = 4 A(0, 4)
Si X 2 = 0 ⎫
⎬ B (10, 0)
X 1 = 10⎭
Para restricción II
10 X 1 + 5 X 2 = 50..... II Si X 1 = 0 X 2 = 10 C (0, 10)
Si X 2 = 0⎫
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
⎬ D(5, 0)
X 1 = 5 ⎭
34
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Para restricción III
7 X 1 + 7 X 2 = 49..... III Si X 1 = 0
Si X 2 = 0⎫
X 2 = 7
⎬ F (7, 0)
X 1 = 7 ⎭
E (0, 7)
GRAFICA DE RESTRICCION I 4.5
A (0, 4)
4
ESPACIO DE SOLUCIONES
3.5 3 2
X
2.5 2 1.5 1 0.5
B (10, 0)
0 0
2
4
6
8
10
12
X1
GRAFICA DE RESTRICCION RES TRICCION II II 12 10
C (0, 10)
ESPACIO DE SOLUCIONES
8 2
X
6 4 2
D (5, 0)
0 0
1
2
3
4
5
6
X1
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
35
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA GRAFICA DE RESTRICCION III 8
E (0, 7)
7
ESPACIO DE SOLUCIONES
6 5 2
X 4
3 2 1
F (7, 0)
0 0
2
4
6
8
X1
COLOCANDO TODAS LAS RESTRICCIONES EN UN SOLO GRAFICO E IDENTIFICANDO EL AREA O ESPACIO DE SOLUCIONES SIMULTANEAS, TENEMOS: TENEMOS:
GRAFICA DE TODAS LAS RESTRICCIO RES TRICCIONES NES 12 10
C (0, 10)
ESPACIO DE SOLUCIONES
8
E (0, 7) 2
X
6
II
R
4
A (0, 4)
I
III III
S
2
B (10, 0)
0 0
2
4
D (5, 0)
6
X1
8
10
12
F (7, 0)
ETAPA No. No . 3 OBTENER LA SOLUCION OPTIMA OPTIMA POR PRUEBA Y ERROR Considerando cada coordenada del área de soluciones básicas factibles (área sombreada de la gráfica), donde se cruzan las restricciones entre sí ó con los ejes cartesianos, se obtiene en la Función Objetivo, el resultado de la sustitución de tales coordenadas se muestra a continuación:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
36
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
CALCULO DE ¨R¨ (Cruce de Ecuación II con Ecuación III)
(−7)10 X 1 + 5 X 2 = 50 II
Sustituyendo X 2 = 4
(10)7 X 1 + 7 X 2 = 49 III
en Ecuación II , tenemos :
L
L
__________ _________
10 X 1 + 5 X 2 = 50....... II
- 70X1 − 35X 2 = -350
10 X 1 + 5(4) = 50
70X1 + 70X 2 = 490
10 X 1 + 20 = 50
__________ _________ R (3, 4)
10 X 1 = 50 − 20
35X 2 = 140
10 X 1 = 30 / 10
X 2 = 140/35
S (5, 2)
X2 = 4
X 1 = 3
Las coordenadas son R (3, 4)
B (10, 0)
CALCULO DE ¨S¨ (Cruce de Ecuación I con Ecuación III)
(−7)4 X 1 + 10 X 2 = 40 I L
(4)7 X 1 + 7 X 2 = 49 III L
__________ _________
Sustituyendo X 2 = 2 en Ecuación I , tenemos :
4 X 1 + 10 X 2 = 40....... I
- 28X1 - 70X 2 = -280
4 X 1 + 10(2) = 40
28X1 + 28X 2 = 196
4 X 1 + 20 = 40
__________ _________
− 42X 2 = −84 X 2 = −84/ - 42 X2 = 2
4 X 1 = 40 − 20 X 1 = 20 / 4 X 1 = 5
Las coordenadas son S (5, 2)
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
37
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE TODAS LAS RESTRICCIO RES TRICCIONES NES 12 10
E (0, 7) 2
X
C (0, 10)
ESPACIO DE SOLUCIONES
8 6
II
R (3, 4)
4
A (0, 4)
I
III III
S (5, 2)
2
B (10, 0)
0 0
2
4
D (5, 0)
6
8
X1
10
12
F (7, 0)
Los cruces de las restricciones entre si y con los ejes cartesianos dentro del Espacio de Soluciones, constituyen los puntos de solución factible, los cuales al sustituirlos en la Función Objetivo, nos permitirán identificar cual de ellos alcanza el valor máximo, es decir, el valor optimo SUSTITUYENDO CADA UNA DE LAS COORDENADAS EN LA FUNCION OBJETIVO TENEMOS Punto C (0, 10) Implica: ninguna onza de alimento “K” y 10 onzas de alimento “W” Min Z = 0.5 X 1 + 0.8 X 2
Punto R (3, 4) Implica: 3 onzas de alimento “K” y 4 onzas de alimento “W” Min Z = 0.5 X 1 + 0.8 X 2
Z = 0.5(0) + 0.8(10)
Z = 0.5(3) + 0.8( 4)
Z = 0 + 8
Z = 1.5 + 3.2
Z = $8.00 dólares
Z = $4.70 dólares
de cos to
de cos to
Punto S (5, 2) Implica: 5 onzas de alimento “K” y 2 onzas de alimento “W” Min Z = 0.5 X 1 + 0.8 X 2
Punto B (10, 0) Implica: 10 onzas de alimento “K” y ninguna de alimento “W” Min Z = 0.5 X 1 + 0.8 X 2
Z = 0.5(5) + 0.8( 2)
Z = 0.5(10) + 0.8(0)
Z = 2.5 + 1.6
Z = 5 + 0
Z = $4.10 dólares
Z = $5.00 dólares
de cos to
de cos to
<<>> MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
38
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Se obtiene el menor costo de $ 4.10, utilizando 5 o nzas del alimento “K” y 2 onzas del alimento “W”
Grafiquemos ahora la Función Objetivo Elegimos de manera arbitraria un número, por ejemplo el 6 para la igualdad de la Función Objetivo, como primera aproximación: Min Z = 0.5 X 1 + 0.8 X 2 = 6
Si X 2 = 0
Si X 1 = 0 X 2 = 7.5
X 1 = 12
G (0, 7.5)
H (12, 0)
Observamos a continuación la Gráfica de la Función Objetivo preliminar en líneas punteadas:
GRAFICA DE RESTRICCIONES RESTRICCIONES Y DE FUNCION OBJETIVO OBJ ETIVO 12 10 E (0, 7)
C (0, 10)
I
8
II
X2 6
III
4 A (0, 4)
R (3, 4)
Z S (5, 2)
2
B (10, 0)
0 0
2
4
6
8
10
12
14
X1 D (5, 0)
F (7, 0)
Ahora desplacemos paralelamente la Gráfica de la Función Objetivo “cuesta abajo”, abajo”, porque se trata de una minimización, hasta el mínimo punto donde tenga contacto con el Espacio de Soluciones, es decir, hasta el punto más cercano al origen pero dentro del espacio de soluciones, esto será generalmente en alguno de los cruces de las restricciones entre sí o con los ejes cartesianos; en este caso es donde se el cruza la Ecuación I con la Ecuación III, es decir, en el punto ¨S¨ de coordenadas (5, 2) como se ilustra a continuación:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
39
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO 12 10 I
8
II
X2 6
III
4
Z S (5, 2)
2 0 0
2
4
6
OPTIMO
8
10
12
14
Z
X1
Es otra manera de determinar gráficamente el punto óptimo (mínimo), donde se obtienen los menores costos y que por supuesto, coincide con lo calculado por prueba y error Al sustituir estas coordenadas en la Función Función Objetivo, vemos que se determina un costo de: Min Z = 0.5 X 1 + 0.8 X 2 Z = 0.5(5) + 0.8(2) Z = 2.5 + 1.6 Z = $4.10 dólares de cos to
Esto significa emplear 5 onzas del alimento “K” y 2 onzas del alimento “W”, para cumplir con los requerimientos al menor costo, como antes ya habíamos visto.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
40
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
GRAFICA DE SOLUCION COMPLETA COMPLETA POR EL METODO METODO GRAFICO
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
41
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
PROBLEMA Núm. 5 En el Restaurante del Hotel “Xalpa” de Ciudad Victoria, se acostumbra preparar la carne para albondigón con una combinación de carne molida de res y carne molida de cerdo, ambas de importación. La carne molida de res contiene 20% de grasa, 12% de proteína y le cuesta al restaurante $8.00 por libra La carne molida de cerdo contiene 32% de grasa, y 20% de proteína y le cuesta al restaurante $6.00 por libra. ¿Que cantidad de cada tipo de carne debe usar el restaurante en cada libra de albondigón; si se desea minimizar el costo, manteniendo el contenido de grasa en no mas d el 25% 25% y manteniendo el cont enido de pro teína teína en no m enos del 15%? 15%?
SOLUCION DEL PROBLEMA ETAPA No. 1.- FORMULACION DEL PROBLEMA Y CONSTRUCCION DEL MODELO MATEMATICO OBJETIVO (VERBAL).- Se desea determinar cuanta carne molida de res y cuanta carne molida de cerdo deben utilizarse en cada libra de albondigón para obtener el menor costo posible, por tanto se trata de una minimización RESTRICCIONES (VERBALES) 1.- El contenido de grasa debe ser cuando mas del 25% 2.- El contenido de proteínas debe ser cuando menos del 15% 3.- La suma de los dos tipos de carne molida de res y de cerdo deben dar una libra de albondigón VARIABLES ( ESTRUCTURA MATEMÁTICA) Para representar las variables de decisión (o incógnitas del problema) se establece que: X1 = Cantidad de carne molida de res X2 = Cantidad de carne molida de cerdo
VARIABLES DE DECISIÓN ó INCÓGNITAS DEL PROBLEMA
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
42
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COEFICIENTES DE LA FUNCION OBJETIVO (Z) La función objetivo se expresa en dólares y representa minimizar los costos de cada tipo de carne molida, por tanto se establece que: C1 = $8 = costo por libra de carne molida molida de res C2 = $6 = costo por libra de carne molida molida de cerdo Función Objetivo:
Max
Z = C1X1 + C2X2
Max
Z = 8X1 + 6X2
Apoyándonos ahora, en una tabla de doble entrada entrada para facilitar la construcción del modelo matemático, asentamos la información de referencia en el problema de la siguiente forma: Carne Molida de Res
Carne Molida de Cerdo
CONTENIDO
X1
X2
GRASA PROTEINA COMBINACION Función Objetivo: Min Z
20 12
32 20
X1
X2
TIPO DE CARNE
$8
Restricciones 25 15 1
$6
Observamos la interrelación entre los datos y determinamos el modelo matemático, al considerar que la tabla se puede re-escribir de la siguiente manera:
TIPO DE CARNE CONTENIDO GRASA PROTEINA COMBINACION Función Objetivo: Min Z
Carne Molida de Res
Carne Molida de Cerdo
X1
X2
20 X1 12 X1
32 X2 20 X2
$8 X1
$6 X2
X1
X2
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
Restricciones 25 15 =1
≤ ≥
43
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
El modelo matemático para el problema probl ema estará dado entonces por: Función Objetivo:
Min Z = 8X1 + 6X2
Sujeto a: 20 X 1 + 32 X 2 ≤ 25 ....... I 12 X 1 + 20 X 2 ≥ 15 ........ II
Restricciones
X 1 + X 2 = 1 .......... ...... III X 1 ≥ 0 ,
ETAPA No. No. 2
X 2 ≥ 0
GRAFICAR LA S RESTRICCIONES RESTRICCIONES Y DETERMINAR DETERMINAR EL AREA DE SOLUCIONES BASICAS FACTIBL FA CTIBLES ES
Obtener los parámetros para graficar cada una una de las restricciones: restricciones: Para la restricción I
20 X 1 + 32 X 2 = 25.......... I Si X 1 = 0
⎫ ⎪ 25 ⎬ A(0, 0.78) X 2 = = 0.78⎪ 32 ⎭
Si X 2 = 0
⎫ ⎪ 25 ⎬ B (1.25, 0) 1.25⎪ X 1 = 20 ⎭
Para la restricción II
12 X 1 + 20 X 2 = 15........... II Si X 1 = 0
⎫ ⎪ 15 ⎬ C (0, 0.75) X 2 = = 0.75⎪ 20 ⎭
Si X 2 = 0
⎫ ⎪ 15 ⎬ D(1.25, 0) X 1 = 1 = .25⎪ 12 ⎭
Para la restricción III X 1 + X 2 = 1.............. III Si X 1 = 0⎫
⎬ E (0, 1) X 2 = 1 ⎭
Si X 2 = 0⎫
⎬ F (1, 0)
X 1 = 1 ⎭
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
44
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COLOCANDO TODAS LAS RESTRICCIONES EN UN SOLO GRAFICO E IDENTIFICANDO EL AREA O ESPACIO DE SOLUCIONES SIMULTANEAS, TENEMOS: TENEMOS:
GRAFICA DE RESTRICCION I
0.9
A (0, 0.78)
0.8 0.7 0.6 2
0.5
X
0.4
ESPACIO DE SOLUCIONES
0.3 0.2 0.1
B (1.25, 0)
0 0
0.2
0.4
0.6
0.8
1
1.2
1.4
X1
GRAFICA DE RESTR ICCION II
C (0, 0.75)
0.8
ESPACIO DE SOLUCIONES
0.7 0.6 0.5 2
X 0.4
0.3 0.2 0.1
D (1.25, 0)
0 0
0.2
0. 4
0. 6
0. 8
1
1. 2
1. 4
X1
GRAFICA DE RESTRICCION III
1.2
E (0, 1)
1 0.8 2
X
0.6 0.4 0.2
F (1, 0)
0 0
0.2
0.4
0.6
0.8
1
1.2
X1
EL ESPACIO DE SOLUCIONES DE LA RESTRICCION III ESTA SOBRE LA LINEA RECTA
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
45
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
COLOCANDO TODAS LAS RESTRICCIONES EN UN SOLO GRAFICO E IDENTIFICANDO EL AREA O ESPACIO DE SOLUCIONES SIMULTANEAS, TENEMOS: TENEMOS:
GRAFICA DE TODAS LAS L AS RESTRICC RESTRICCIONE IONES S X2 A (0, 0.78) C (0, 0.75)
1.2 1
E (0, 1)
0.8 0.6
I II III
R
0.4 S
0.2
B,D (1.25, 0)
0 0
0.5
1 X1
1.5 F (1, 0)
En este caso, el espacio de soluciones simultáneas, es decir, donde convergen a su vez todos los espacios de soluciones de las tres restricciones, esta sobre la línea recta que representa a la Restricción III, entre la pequeña franja al centro, en el segmento donde se cruza con la Restricción I por un lado y donde se cruza con la Restricción II,
ETAPA No. No . 3 OBTENER LA SOLUCION OPTIMA OPTIMA POR PRUEBA Y ERROR Considerando cada coordenada del área de soluciones básicas factibles (área sombreada de la gráfica), donde se cruzan las restricciones entre sí ó con los ejes cartesianos, se obtiene en la Función Objetivo, el resultado de la sustitución de tales coordenadas como se muestra a continuación:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
46
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
CALCULO DE ¨R¨ (Cruce de Ecuación III con Ecuación I) Sustituyendo X2 = 0.4167 en la Ecuación I, se tiene:
20 X 1 + 32 X 2 = 25........ I (−20) X 1 + X 2 = 1......... III
20 X 1 + 32 X 2 = 25
20 X 1 + 32 X 2 = 25
− 20 X 1 − 20 X 2 = −20 12 X 2 = 5
I
KK
20 X 1 + 32(0.4167) = 25 20 X 1 + 13.334 = 25 20 X 1 = 25 − 13.334
X 2 =
20 X 1 = 11.667
5 12
X 1 =
X 2 = 0.4167
11.667 20
X 1 = 0.5833
Las coordenadas del punto “R” son: (0.5833, 0.4167) CALCULO DE ¨S¨ (Cruce de Ecuación III con Ecuación II)
12 X 1 + 20 X 2 = 15..... II (−12) X 1 + X 2 = 1..... III
Sustituyendo X2 = 0.38 en Ecuación III, se tiene: X 1 + X 2 = 1......... III
12 X 1 + 20 X 2 = 15
X 1 + 0.38 = 1
− 12 X 1 − 12 X 2 = −12 8 X 2 = 3
X 1 = 1 − 0.38
3 8 X 2 = 0.375 Las coordenadas del punto “S” son: (0.625, 0.375) X 2 =
X 1 = 0.625
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
47
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE TODAS LAS RESTRICCIONES 1.2
A (0, 0.78) C (0, 0.75)
X2
1
E (0, 1)
0.8 I II III
R (0.58, 0.42)
0.6 0.4 S (0.625, 0.375)
0.2
B,D (1.25, 0)
0 0
0.5
1 X1
F (1, 0)
1.5
Aquí las posibles soluciones están solo en dos opciones: el cruce entre la Restricción III con la I, representada por “R” ó el cruce entre la Restricción III con la II, representada por “S”. “S”. SUSTITUYENDO CADA UNA DE LAS COORDENADAS EN LA FUNCION OBJETIVO TENEMOS Punto R (0.5833, 0.4167) Min Z = 8 X 1 + 6 X 2
Punto S (0.625, 0.375) Min Z = 8 X 1 + 6 X 2
Z = 8(0.5833) + 6(0.4167)
Z = 8(0.625) + 6(0.375)
Z = 4.6664 + 2.5
Z = 4.96 + 2.28
Z = $7.17
Z = $7.25
<<>> Se concluye que el punto “R” es donde se obtienen las menores costos, debiendo incorporarse 0.58 libras de carne molida de res y 0.42 libras de carne molida de cerdo, para de esa manera obtener el costo más bajo, es decir, $7.17 dólares para elaborar una libra de albondigón.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
48
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Grafiquemos ahora la Función Objetivo Elegimos de manera arbitraria un número, por ejemplo el 6 para la igualdad de la Función Objetivo, como primera aproximación: Min Z = 8X1 + 6X2 = 6 Si X1 = 0
Si X2 = 0
X2 = 1
X1 = 0.75
G (0, 1)
H (0.75, 0)
Observamos a continuación la Gráfica de la Función Objetivo preliminar en líneas punteadas de color rojo
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO 1.2
A (0, 0.78) C (0, 0.75)
1 E (0, 1) 0.8
I
X 2 0.6
II
R (0.58, 0.42)
III Z
0.4 S (0.62, 0.38)
0.2
B,D (1.25, 0)
0 0
0.5
Z
1
F (1, 0)
1.5
X1
Ahora desplacemos paralelamente la Gráfica de la Función Objetivo “cuesta abajo” por tratarse de una minimización, hasta el mínimo punto donde tenga contacto con el Espacio de Soluciones, esto será generalmente en alguno de los cruces de las restricciones entre sí o con los ejes cartesianos; en este caso es donde se el cruza la Ecuación III con la Ecuación I, es decir, en el punto ¨R¨ de coordenadas (0.58, 0.42) como se ilustra a continuación:
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
49
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
GRAFICA DE RESTRICCIONES Y DE FUNCION OBJETIVO 1.2 1 0.8
I II
OPTIMO R 0.58 0.42
X 2 0.6
III Z
0.4 0.2 0 0
0.5
Z
1
1.5
X1
Es otra manera de determinar gráficamente el punto óptimo (máximo), donde se obtienen los mayores beneficios y que por supuesto, coincide con lo calculado por prueba y error Al sustituir estas coordenadas en la Función Objetivo, Objetivo, vemos que se obtiene el menor costo: costo: Min Z = 8 X 1 + 6 X 2 Z = 8(0.5833) + 6(0.4167) Z = 4.6664 + 2.5 Z = $7.17
Esto significa que debe componerse el albondigón de 0.58 libras de carne molida de res y 0.42 libras de carne molida de cerdo, para de esa manera obtener el costo más bajo, es decir, $7.17 dólares.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
50
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
GRAFICA DE SOLUCION COMPLETA COMPLETA POR EL METODO METODO GRAFICO
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
51
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
3.4 3. 4 Ca Casos sos especiales
Nos vamos a encontrar con problemas que son especiales, por diversas razones, los cuales podrían tener un error en el planteamiento o efectivamente estar en alguna de las situaciones descritas a continuación.
Soluciones múltiples: Cuando múltiples: Cuando la Función Objetivo es paralela a una restricción, como se ilustra en la siguiente grafica:
X2
9 8 7 6 5 4 3 2 1 0 -1 0 -2
1
2
3
4
5
6
7
8
9 10 X
1 Función Objetivo
Problemas sin solución: ocurren solución: ocurren cuando los espacios de solución de cada una de las restricciones no se intersectan entre sí:
X2
Espacio de soluciones
9 8 7 6 5 4 3 2 1 0
Espacio de soluciones
0 1 2 3 4 5 6 7 8 9 10 X1
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
52
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Soluciones no acotadas: Se presenta esta situación cuando en un problema no se delimita apropiadamente cada restricción, como se ilustra a continuación:
5
4
AREA DE SOLUCIONES FACTIBLES (NO ACOTADA)
3 2
X
2
1
0
0
1
2
3
4
X1
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
53
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
3.5 3. 5 La dualidad y los precios sombr sombra a (a (análisis nálisis preliminar) LA SIMETRÍA EN LA PROGRAMACIÓN LINEAL Todo problema de programación lineal esta asociado con un problema complementario llamado dual. Para distinguir entre estos dos problemas, al problema original original se le denomina primal. primal . Si el problema primal trata de maximizar, entonces el problema dual será dual será minimizar y viceversa. Veamos un ejemplo para comprobar como se formula, resuelve e interpreta el dual.
CASO 1 Un fabricante tiene dos recursos disponibles: R 1 y R2. Estos recursos pueden usarse para producir dos productos diferentes “A” y “B”, de acuerdo con la siguiente regla: Para producir “A” se emplean 1 unidad de R1 y 4 unidades de R 2; para producir “B” se emplean 1 unidad de R1 y 2 unidades de R 2. El fabricante cuenta con 3 unidades de R 1 y 8 unidades de R 2. Recibe una ganancia por unidad de “A” de $3.50 y por unidad de “B” de $2.50. ¿Cuantas ¿Cuantas unidades unidades de “A” y “ B” debe produ cir para maximizar sus ganancias?
SOLUCION POR EL METODO GRAFICO PRIMAL Apoyándonos en una tabla de doble entrada se tiene: PRODUCTO RECURSO R1 R2 Función Objetivo: Max Z
Product Producto o “ A” X1
Producto Producto “ B” X2
RESTRICCIONES
1 4 $3.50
1 2 $2.50
3 8
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
54
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Re-escribiendo la tabla considerando l as interrelaciones existentes, tenemos: PRODUCTO RECURSO R1 R2 Función Objetivo: Max Z
Product Producto o “ A” X1
Producto Producto “ B” X2
RESTRICCIONES
X1 4 X1 $3.50 X $3.50 X1
X2 2 X2 $2.50 X $2.50 X2
≤3 ≤8
El Modelo Matemático de Programación Lineal quedará dado por Max Z = 3.5X 1 +2.5X2
...........
PRIMAL
Sujeto a: X1 + X2 ≤ 3............I 3............I 4X1 + 2X2 ≤ 8............II X1 ≥ 0, X2 ≥ 0 GRAFICA DE SOLUCION COMPLETA COMPLETA DEL PRIMAL
A (0, 3)
S (1, 2)
D (2, 0)
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
55
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
DUAL La simetría de los problemas de programación lineal puede ilustrarse colocando los coeficientes del modelo en una matriz o tabla de doble entrada como se hizo al principio del problema. La tabla tiene renglones y columnas que pueden invertirse. Rotamos la tabla dándole vuelta 900 grados en sentido opuesto a las manecillas manecillas del reloj. Los resultados son:
DESPUÉS DE LA ROTACIÓN DE 90º GRADOS
B A
3
8
1 1 R1
2 4 R2
2.5 3.5
Reescribiendo Reescribiendo la tabla tenemos:
3r 1
8r 2
1r 1 1r 1
2r 2 4r 2
2.5 3.5
≥ ≥
Esto representa el DUAL, DUAL, donde los coeficientes coeficientes de la Función Objetivo Objetivo están ahora arriba. arriba. Puede re-escribirse en forma directa el modelo general para este problema. Solo se necesitan nuevas letras para las variables. Entonces el problema puede quedar de la siguiente manera: Min Z = 3r 1 + 8r 2
...........
DUAL
Sujeto a: r 1 +2r 2 ≥ 2.5....................I 2.5....................I r 1 +4r 2 ≥ 3.5……………..II r 1 ≥ 0 , r 2 ≥ 0 Nótese que las restricciones restricciones son ahora del tipo y la Función Objetivo Objetivo es para minimizar, minimizar, lo contrario que plantea el problema inicial (el PRIMAL). MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
56
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
La minimización nos lleva al siguiente resultado: GRAFICA DE SOLUCION COMPLETA COMPLETA DEL DUA L
NOTESE Que El resultado nos muestra que el valor “Z” de la Maximización del Primal y el valor “Z” de la Minimización del Dual es el mismo, 8.5, este valor recibe el nombre de Precio Sombra, Sombra, en tanto que los coeficientes resultantes en la Función Objetivo del Dual reciben el nombre de Costos de Oportunidad
INTERPRETACION INTERPRETACION DEL DEL PROBLEMA PROBL EMA DUAL El problema dual puede entenderse reinterpretando el problema original. Supóngase que el fabricante prefiere vender directamente al mercado los dos recursos R 1 y R2 en lugar de usarlos para fabricar los l os productos “A” y “B”. Los recursos tienen un valor, puesto que pueden usarse para crear productos que luego se comercializarán. Pero, aun cuando se conoce el valor unitario de los productos, no se conoce el valor unitario de los recursos. Esto es lo que se quiere encontrar. encontrar.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
57
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
¿Cuánto ¿Cuánto debe cobrarse por los recursos s i tuviesen que venderse directamente? directamente?
Por supuesto, en un mercado libre los recursos deben venderse en la cantidad más alta que el mercado acepte. Sin embargo, existe un precio mínimo abajo del cual le conviene mas al fabricante usar los recursos para los productos productos “A” y “B” que venderlos directamente. Para analizar esta situación consideremos L1 y L2 como los precios unitarios de unitarios de los recursos r 1 y r 2, respectivamente. La cantidad total recibida de la venta directa de los dos recursos seria L 1r 1 + L2r 2. Como lo que se busca es determinar el precio mínimo que se debe cobrar por estos estos recursos, la Función Objetivo es: Min Z = L1r 1 + L2r 2 Min Z = 3r 1 + 8r 2 Como se menciono antes, seria un error vend er los recursos por menos de lo que puede obtenerse al usarlos en la fabricación de los productos “A” y “B”. El precio de cada producto proporciona un límite inferior o una restricción sobre el precio del recurso. El resultado de la minimización en el Dual, es decir, 8.50 es llamado Precio Sombra y Sombra y es el mismo resultado que en el Primal. Vemos entonces, que r 1=1.5 llamado Costo de Oportunidad de r 1, porque significa que el fabricante puede aumentar su ganancia total en $1.50 si dispone de una Unidad Adicional de r 1, es decir, si de 3 pasara a 4, lo cual a su vez, implicaría que Z sería igual a $10 en vez de los $8.50 originales (8.50 + 1.50), si permanece invariable r 2 También significa que $1.50 es el precio máximo que debe pagar el fabricante por una Unidad Adicional del Recurso r 1 r 2=0.50, significa el Costo de Oportunidad de r 2, que aumentaría la ganancia Z, en 0.50 si dispone de una Unidad Adicional de r 2, es decir, si de 8 pasara a 9, implicaría que Z sería igual a $9.00 en vez de los $8.50 originales (8.50 + 0.50), si permanece invariable r 1.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
58
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
CASO 2 Un fabricante tiene dos recursos disponibles: Q 1 y Q2. Estos recursos pueden usarse para producir dos productos diferentes “M” y “N”, de acuerdo con la siguiente regla: Para producir “M” se emplean 7 unidad de Q 1 y 10 unidades de Q2; para producir “N” se emplean 7 unidad de Q1 y 5 unidades de Q 2. El fabricante cuenta cuenta con 49 49 unidades de Q1 y 50 unidades de Q2. Recibe una ganancia por unidad de “M” de $7 y por unidad de “N” de $10. ¿Cuantas ¿Cuantas unidades de “ M” y “ N” d ebe produc ir para maximizar maximizar sus ganancias? ganancias?
SOLUCION POR EL METODO GRAFICO PRIMAL Apoyándonos en una tabla de doble entrada se tiene: PRODUCTO
Producto “M”
Producto “N”
X1
X2
RESTRICCIONES
Q1
7
7
49
Q2
10
5
50
Función Objetivo: Max Z
$7
$10
RECURSO
Re-escribiendo la tabla considerando l as interrelaciones existentes, tenemos: PRODUCTO RECURSO Q1 Q2 Función Objetivo: Max Z
Producto Producto “M” X1
Producto Producto “N” X2
RESTRICCIONES
7 X1 10 X 10 X1 $7 X $7 X1
7 X2 5 X2 $10 X $10 X2
≤ 49 ≤ 50
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
59
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
El Modelo Matemático de Programación Lineal quedará dado por Max
Z = = 7 X 1 + 10 X 2 ………… PRIMAL
Sujeto a:
7 X 1 + 7 X 2 ≤ 49..... I 10 X 1 + 5 X 2 ≤ 50..... II X 1 ≥ 0, X 2 ≥ 0
SOLUCION POR EL METODO GRAFICO: GRAFICA DE SOLUCION COMPLETA COMPLETA DEL PRIMAL
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
60
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
DUAL DESPUÉS DE LA ROTACIÓN DE 90º GRADOS
N M
Min Z = 49r 1 + 50r 2
49
50
7 7 R1
5 10 R2
49r 1
50r 2
7r 1 7r 1
5r 2 10r 2
...........
10 7
≥ 10 ≥ 7
DUAL
Sujeto a: 7r 1 +5r 2 ≥ 10....................I 10....................I 7r 1 +10r 2 ≥ 7……………..II r 1 ≥ 0 , r 2 ≥ 0
Nótese que las restricciones son ahora del tipo ≥ y la Función Objetivo trata de minimizar.
La minimización nos lleva al siguiente resultado:
GRAFICA DE SOLUCION COMPLETA COMPLETA DEL DUA L
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
61
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
INTERPRETACION INTERPRETACION ECONOMICA ECONOMICA DEL PROBLEMA PROBL EMA DUAL El resultado de la minimización en el Dual, es decir 70, es llamado Precio Precio Sombra y Sombra y es el mismo resultado que en el Primal. Vemos entonces, que r 1=1.43 llamado Costo de Oportunidad de r 1, significa que el fabricante puede aumentar su ganancia total en $1.43 si dispone de una Unidad Adicional de r 1, es decir, si de 49 pasara a 50, esto implicaría que Min Z sería $71.43 en vez de los $70 originales (porque 70 + 1.43 = 71.43), considerando que permanece invariable r 2. También significa que $1.43 es el precio máximo que debe pagar el fabricante por una Unidad Adicional del Recurso r 1 r 2=0, es llamado el Costo de Oportunidad de r 2, significa por ser cero, que no impacta en la ganancia Min Z
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
62
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
Limitaciones de Método Gráfico
Para dos variables es posible visualizar en un gráfico la solución del óptimo y realizar los análisis de sensibilidad tanto a restricciones como a los coeficientes de la Función Objetivo, sin embargo, para el Método Dual, si el numero de variables se incrementa al rotar la tabla de doble entrada, ya no será posible visualizar los resultados gráficamente, por tales limitaciones, solo es un paso ilustrativo para entender y comprobar el METODO SIMPLEX, SIMPLEX, que veremos mas adelante, en Módulo.
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
63
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
3.6 3. 6 Problemas prop propuestos uestos A. Una empresa produce dos artículos turísticos promocionales “A” y “B” para Hoteles. La elaboración de una unidad del articulo A se lleva $20.00 de mano de obra obra y la de una unidad del articulo B se lleva $10.00 de mano de obra. De materia prima se utilizan $10.00 por unidad de A y $30.00 por unidad de B. El desgaste del equipo se supone supone proporcional a la producción y es $5.00 por cada unidad de A y de $1.00 por unidad de B. La utilidad por unidad de artículo es de $8.00 para A y $5.00 para B. Si solamente se cuenta con $100,000 para salario, $180,000 para materia prima y no se quiere que el desgaste de los equipos supere los $40,000, ¿Cuál es la cantidad que se debe producir de cada artículo para obtener las utilidades más altas posibles? B. Un fabricante está tratando decidir sobre las cantidades de producción para dos artículos: mesas y sillas especiales para restaurantes en costas a base de bambú. Se cuentan con 96 unidades de material y con 72 horas de mano de obra. Cada mesa requiere 12 unidades de material y 6 horas de mano de obra. Por otra parte, las sillas usan 8 unidades de material cada una y requieren 12 horas de mano de obra por silla. El margen de contribución es el mismo para las mesas que para las sillas: $5.00 por unidad. El fabricante prometió construir por lo menos 2 mesas por mes ¿Cuántas mesas y cuantas sillas deberá producir para obtener las mayores utilidades? C. Un dietista en un restaurante esta tratando tratando de seleccionar la combinación más barata de dos tipos de alimentos “A” y “B”, que deben cumplir con ciertas necesidades diarias de vitaminas para turistas adultos mayores. mayores. Los requerimientos vitamínicos diarios diarios son de al menos 40 unidades de vitamina “W”, 50 unidades de vitamina “X” y 49 unidades de vitamina “Y”. Cada onza del alimento alimento “A” proporciona 4 unidades de vitamina vitamina “W”, 10 unidades de vitamina “X” y 7 unidades de vitamina “Y”, Cada onza del alimento “B” proporciona 10 unidades de vitamina “W”, 5 unidades de “X” y 7 unidades de “Y”. El alimento “A” cuesta 0.50 centavos de dólar la onza y el alimento “B” cuesta 0.80 centavos de dólar la onza. ¿Cuantas onzas de cada alimento deben utilizarse para satisfacer las necesidades vitamínicas diarias con el menor desembolso monetario? D. Una empresa dedicada a la limpieza en Hoteles, prepara sus propias soluciones mezclando dos ingredientes importados: “A” y “B”: Esto lo hace para obtener una solución combinada apropiada de fosfatos fosfatos y cloruro. El ingrediente “A” tiene 5% de fosfato y 2% de cloruro y cuesta $0.25 centavos la onza. onza. El ingrediente “B” tiene 7% de fosfato y 1% de cloruro y cuesta $0.20 centavos la onza. La empresa necesita que la mezcla final tenga no mas del 6% de fosfatos y no mas del del 1.5% de cloruro. ¿Cuántas onzas de cada ingrediente debe mezclar para formar la solución apropiada al menor costo? E. Una fábrica de de automóviles y camiones consta de los departamentos que a continuación se enumeran: 1.- Estampado de planchas metálicas 2.- Armado de motores 3.- Montaje de automóviles 4.- Montaje de camiones MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
64
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
Apuntes sobre Investigación de Operaciones
El Departamento 1 puede estampar, por mes las planchas necesarias para 25,000 automóviles ó 35,000 camiones ó las correspondientes combinaciones de autos y camiones. El Departamento 2 puede armar por mes 33,000 motores motores de autos ó 16,000 motores de camión ó sus correspondientes combinaciones de autos y camiones. El Departamento 3 puede montar y terminar 22,500 automóviles y el Departamento 4 puede montar y terminar 15,000 camiones. Si cada automóvil deja una utilidad de $300.00 dólares y cada camión de $250.00 dólares ¿Qué cantidades de automóviles y camiones deben producirse para obtener las mayores utilidades? F. La compañía “Pegasus” de carga aérea desea maximizar los ingresos ingresos que obtiene por la carga que transporta. La compañía tiene un solo avión diseñado para transportar dos clases de carga: carga frágil y carga normal. La compañía no recibe pago extra por transportar carga frágil, sin embargo, para asegurar ciertos contratos de negocios, la compañía a acordado transportar cuando menos 5 toneladas de carga frágil. Este tipo de carga debe llevarse en una cabina presurizada, mientras que la carga normal debe llevarse en una cabina normal, no presurizada. La cabina presurizada no puede llevar más de 10 toneladas de carga y la cabina normal 20 toneladas. El avión tiene una restricción de peso que le impide llevar más de 28 toneladas de carga. Para mantener el equilibrio de peso la carga de la cabina presurizada debe ser menor o igual que 2/3 de la cabina principal, mas una tonelada. La compañía recibe $1,000 por tonelada de cualquiera de los dos tipos de carga que transporta ¿cuantas toneladas de cada tipo de carga debe transportar el avión para obtener las mayores utilidades y mantener el equilibrio del avión? G. Desde hace muchos años la agencia de viajes “Tur Mundo” Mundo” se ha especializado en elaborar 2 tipos de paquetes turísticos: 1) “Acapulco de ensueño” y 2) “Exótico Puerto Vallarta”. Cada paquete para Acapulco utiliza 80 dólares por concepto de servicios hoteleros, 200 dólares para transportación transportación y 50 dólares para alimentos e impuestos. Cada paquete a Puerto Vallarta utiliza 70 dólares por servicios hoteleros, 100 dólares para transportación y 60 dólares para alimentos e impuestos. El beneficio por unidad de paquete es de 40 dólares para Acapulco y de 35 dólares para para puerto Vallarta. El departamento de comercialización y ventas pronostica que en la próxima temporada vacacional pueden venderse cuando mucho 450 paquetes para Acapulco y no mas de 350 paquetes a puerto Vallarta. Si la agencia tiene una línea de crédito de únicamente únicamente 56,000 dólares para servicios hoteleros, solo 100,000 dólares para transportación y 30,000 dólares para alimentos e impuestos. ¿Cuántos paquetes de cada tipo debe armar y vender para obtener las mayores utilidades? H. Una empresa produce colorantes para interiores y exteriores especiales para pinturas de hoteles en lugares húmedos, que se distribuyen al mayoreo. Se utilizan dos materiales básicos “ A” A” y “B”, para producir las pinturas. La disponibilidad máxima de “ A” A” es de 6 toneladas mensuales, la de “B” es de 8 toneladas por mes. Los requisitos mensuales de materia prima por tonelada de pintura para interiores y exteriores se resume como sigue: Colo olorant rante es para para Pintu intura ra:: EXTERIOR INTERIOR
Materia Prima A Materia Prima B
1 2
2 1
Dispo ispon nibili ibilida dad d Máxima ima (ton ton.)
6 8
Un estudio de mercado determinó que la demanda mensual de pintura para interiores no puede ser mayor que la de pinturas para exteriores en más más de una tonelada. El mismo estudio señala que la demanda máxima de pintura para interiores está limitada a 2 toneladas por mes. El precio en miles de pesos, al mayoreo por tonelada es de $3 para la MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
65
Apuntes sobre Investigación de Operaciones
MIGUEL GONZÁLEZ HIPÓLITO y OSCAR MAYO LEYTTE
pintura de exteriores y $2 para la pintura de interiores. ¿Cuanta pintura para exteriores e interiores debe producir la empresa mensualmente para maximizar su ingreso?
MODULO PROGRAMACION LINEAL: Método Gráfico http://omlay.iespana.es
66
