martes, 2 de marzo de 2010

problemas de metodo grafico

El gerente de personal de “La Tortuga Veloz, S.A. de C.V.”, está analizando la necesidad de mano de obra semi calificada durante los próximos seis meses. Se lleva 1 mes adiestrar a una persona nueva. Durante este período de entrenamiento un trabajador regular, junto con uno en adiestramiento (aprendiz), producen el equivalente a lo que producen 1.2 trabajadores regulares. Se paga $500.00 mensuales a quien está en entrenamiento, mientras que los trabajadores regulares ganan $800.00 mensuales. La rotación de personal entre los trabajadores regulares es bastante alta, del 10% mensual. El gerente de personal debe decidir cuántas personas necesita contratar cada mes para adiestramiento. En seguida se da el número de meses-hombre necesarios. También se desea tener una fuerza de trabajo regular de 110 al principio de julio. En cuanto al 1º de enero, hay 58 empleados regulares.

Mes
Meses-hombre requeridos
Mes
Meses-hombre requeridos

Enero
60
Abril
80

Febrero
50
Mayo
70

Marzo
60
Junio
100


Este problema tiene un aspecto dinámico, ya que la fuerza de trabajo en cualquier mes depende de la fuerza de trabajo regular y en adiestramiento del mes anterior. Para cualquier mes, el número total de meses-hombre disponibles se puede expresar como sigue:

Meses-hombre disponibles: Ri + 0.2Ai

en donde: Ri = número de trabajadores regulares al principio del mes

Ai = número de aprendices contratados en el mes.

Entonces los requerimientos de cada mes pueden expresarse por las restricciones:

enero
R1 + 0.2A1
³
60

febrero
R2 + 0.2A2
³
50

marzo
R3 + 0.2A3
³
60

abril
R4 + 0.2A4
³
80

mayo
R5 + 0.2A5
³
70

junio
R6 + 0.2A6
³
100

julio (principio)
R7
³
110


Debido a la rotación, el 10% de los trabajadores regulares se van cada mes. Así, el número de trabajadores regulares disponibles, por ejemplo, al principio de febrero sería:

R2 = 0.9R1 + A1

En la misma forma, pueden escribirse las ecuaciones para el número de trabajadores disponibles al principio de cada mes:

enero
R1
=
58 (dado)

febrero
R2
=
0.9R1 + A1

marzo
R3
=
0.9R2 + A2

abril
R4
=
0.9R3 + A3

mayo
R5
=
0.9R4 + A4

junio
R6
=
0.9R5 + A5

julio
R7
=
0.9R6 + A6


El objetivo global del gerente de personal es minimizar el costo. La función objetivo es:

Minimizar: Z = 800(R1 + R2 + R3 + R4 + R5 + R6) + 500(A1 + A2 + A3 + A4 + A5 + A6)

Ahora se tiene el problema en el formato general de PL con 13 variables y 14 restricciones.

Los tomadores de decisiones en las empresas establecen criterios que debe cumplir una solución y, después, buscan esa solución. En PL, los criterios se expresan como restricciones. Se exploran las soluciones posibles y se usa la función objetivo para elegir la mejor de entre aquellas que cumplen con los criterios. La PL se denomina técnica de optimización, pero optimiza sólo dentro de los límites de las restricciones. En realidad es un método de satisfacción de criterios.

Forma estándar de los modelos de Programación Lineal.

Supóngase que existe cualquier número (digamos m) de recursos limitados de cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual que las actividades (1, 2, ..., n). Sea xj (una variable de decisión) el nivel de la actividad j, para j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea cj el incremento que resulta en Z por cada incremento unitario en xj (para j = 1, 2, ..., n). Ahora sea bi la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase aij como la cantidad de recurso i que consume cada unidad de la actividad j (para i = 1, 2, ..., m y j = 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2, ..., xn para:

Maximizar Z = c1x1 + c2x2 + ... + cnxn,

sujeto a las restricciones:

a11x1 + a12x2 + ... + a1nxn £ b1

a21x1 + a22x2 + ... + a2nxn £ b2



am1x1 + am2x2 + ... + amnxn £ bm y

x1 ³ 0, x2 ³0, ..., xn ³ 0

Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de PL.

En este momento se puede resumir la terminología que usaremos para los modelos de PL. La función que se desea maximizar, c1x1 + c2x2 + ... + cnxn, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m restricciones (aquellas con una función del tipo ai1x1 + ai2x2 + ... + ainxn, que representa el consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera parecida, las restricciones xj ³ 0 se llaman restricciones de no negatividad. Las variables xj son las variables de decisión. Las constantes de entrada, aij, bi, cj, reciben el nombre de parámetros del modelo.

Otras formas de modelos de Programación Lineal.

Es conveniente agregar que el modelo anterior no se ajusta a la forma natural de algunos problemas de programación lineal. Las otras formas legítimas son las siguientes:

1. Minimizar en lugar de maximizar la función objetivo:

Minimizar Z = c1x1 + c2x2 + ... + cnxn,

2. Algunas restricciones funcionales con desigualdad en el sentido mayor o igual:

ai1x1 + ai2x2 + ... + ainxn, ³ bi, para algunos valores de i,

3. Algunas restricciones funcionales en forma de ecuación:

ai1x1 + ai2x2 + ... + ainxn, = bi, para algunos valores de i,

4. Las variables de decisión sin la restricción de no negatividad:

xj no restringida en signo para algunos valores de j.

Cualquier problema que incluya una, varias o todas estas formas del modelo anterior también se clasifica como un problema de PL, siempre y cuando éstas sean las únicas formas nuevas introducidas. Puede ser que la interpretación que se ha dado de asignación de recursos limitados entre actividades que compiten no se aplique, pero independientemente de la interpretación o el contexto, lo único que se necesita es que la formulación matemática del problema se ajuste a las formas permitidas. Se verá que estas otras cuatro formas legales se pueden reescribir en una forma equivalente para que se ajuste al modelo que se presentó. Entonces, todo problema de PL se puede poner en nuestra forma estándar si se desea.

2.3. Solución Gráfica de Modelos Lineales con dos Variables.

Para la solución gráfica de programas lineales con dos variables, lo que se tiene que hacer es trazar un eje de coordenadas cartesianas, para graficar las desigualdades dadas por el problema, después encontrar el Área de Soluciones Factibles y proceder a graficar la función objetivo para conocer el valor óptimo (maximizar o minimizar) que será la solución del problema.

Ejemplo: Problema de mezcla de productos.

Un fabricante está tratando de decidir sobre las cantidades de producción para dos artículos: mesas y sillas. Se cuenta 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 dos mesas.

Paso 1: formulación del problema.

El primer paso para resolver el problema es expresarlo en términos matemáticos en el formato general de PL. ¿Cuál es el objetivo? Es maximizar la contribución a la ganancia. Cada unidad de mesas o sillas producidas contribuirá con $5 en la ganancia. Así las dos alternativas son la producción de mesas y la producción de sillas. Ahora puede escribirse la función objetivo:

Maximizar Z = 5x1 + 5x2

en donde: x1 = número de mesas producidas

x2 = número de sillas producidas

¿Cuáles son las restricciones o limitaciones del problema? Existen tres restricciones. Primero, el material está limitado a 96 unidades. Cada mesa se lleva 12 unidades de material y cada silla usa 8 unidades. La primera restricción es, entonces:

12x1 + 8x2 £ 96

La segunda restricción es el total de horas de mano de obra. Una mesa se lleva 6 horas, una silla 12 horas y se dispone de un total de 72 horas. Así:

6x1 + 12x2 £ 72

Existe una limitación más. El fabricante prometió producir por lo menos dos mesas. Esto puede expresarse como:

x1 ³ 2

Por último, las restricciones de no negatividad son:

x1 ³ 0, x2 ³ 0

Poniendo todo junto el modelo se tiene:

Maximizar Z = 5x1 + 5x2

Restricciones: 12x1 + 8x2 £ 96

6x1 + 12x2 £ 72

x1 ³ 2

x1 ³ 0, x2 ³ 0

Paso 2: gráfica de las restricciones.

El siguiente paso en el método gráfico es dibujar todas las restricciones en una gráfica. Esto puede hacerse en cualquier orden. Por conveniencia se comenzará con las restricciones de no negatividad. Éstas se muestran en la siguiente figura:



En esta gráfica, una solución se representaría por un punto con coordenadas x1 (mesas) y x2 (sillas). Las coordenadas representarían las cantidades de cada artículo que se deben producir. El cuadrante superior derecho se llama Región Factible puesto que es el único cuadrante en que pueden estar las soluciones. Los otros tres cuadrantes no son factibles, ya que requerirían la producción de cantidades negativas de mesas o de sillas o de ambas.

La siguiente restricción es x1 ³ 2. La manera más sencilla de dibujar las restricciones de recursos es en dos pasos: (1) convertir una desigualdad en una ecuación y graficar la ecuación y (2) sombrear el área apropiada arriba y abajo de la línea que resulta en el paso 1. Convertir una igualdad en una ecuación aquí significa ignorar la parte de “mayor que” o “menor que” de la restricción.

Así, en el ejemplo, x1 ³ 2 se convierte en x1 = 2. Esta ecuación está trazada en la siguiente figura:



Cualquier punto en la línea x1 = 2 satisface la ecuación. Sin embargo, la restricción es más amplia, ya que cualquier punto x1 > 2 también la cumplirá. Esto incluye todos los puntos que están a la derecha de la línea x1 = 2. Entonces, la región factible incluye todos los valores de x1 que están sobre o a la derecha de la línea x1 = 2.

La limitación sobre las horas de mano de obra es la siguiente restricción. Como antes, primero se convierte en una ecuación: 6x1 + 12x2 = 72. Puede graficarse esta línea si se encuentran dos puntos sobre ella. El par de puntos más sencillos de localizar son las intersecciones con los ejes X1 y X2. Para encontrar la intersección con el eje X2 se hace x1 = 0. La ecuación se reduce, entonces, a:

12x2 = 72

x2 = 6

La intersección con el eje X1 se encuentra haciendo x2 = 0. Así:

6x1 = 72

x1 = 12

Estos dos puntos y la línea que los une se muestran en la siguiente figura:



Cualquier punto que está sobre o abajo de esta línea cumplirá con la restricción. Cualquier punto arriba de esta línea requerirá más de 72 horas de mano de obra y no es aceptable. En la siguiente figura se combina esta restricción con la anterior. En la región factible, ambas restricciones se cumplen.


La última restricción es la de material. Siguiendo el procedimiento anterior, primero se encuentran las intersecciones para la igualdad. Éstas son x1 = 0, x2 = 12 y x1 = 8, x2 =0. Se localizan los dos puntos en la gráfica; se traza la línea, y como la restricción es del tipo menor o igual que, se sombrea el área que está abajo de la línea. El resultado se muestra en la siguiente figura:


Cualquier solución que esté en la frontera o dentro del área sombreada cumplirá con todas las restricciones. Ahora se utilizará la función objetivo para seleccionar la solución óptima.

Paso 3: obtención de la solución óptima: líneas de indiferencia.

Para encontrar la solución óptima, se grafica la función objetivo en la misma gráfica de las restricciones. La función objetivo en este problema es Z = 5x1 + 5x2. Como todavía no se conoce el máximo valor factible de Z, no puede trazarse el óptimo de la función objetivo. No obstante, es posible suponer algunos valores para Z y graficar las líneas resultantes. En la siguiente figura se muestran las líneas para Z = 25 yZ = 50:


Las líneas de este tipo se llaman líneas de indiferencia, porque cualquier punto sobre una línea dada da la misma ganancia total. Nótese que la distancia perpendicular del origen a la línea aumenta al aumentar el valor de Z. También, todas las líneas de indiferencia son paralelas entre sí. Estas propiedades gráficas pueden usarse para resolver el problema.

En la siguiente figura, se ilustran todas las restricciones y las dos líneas de indiferencia supuestas. En la gráfica puede observarse que la línea de indiferencia para Z = 50 está completamente fuera de la región factible. Para Z = 25, parte de la línea cae dentro de la región factible. Por tanto, existe alguna combinación de x1 y x2 que satisface todas las restricciones y da una ganancia total de $25. Por inspección, puede observarse que hay ganancias más altas que son factibles.


Imaginando que la línea de indiferencia Z = 25 se mueve hacia la línea Z = 50, de las propiedades de la gráfica que se hicieron notar antes, el punto óptimo estará sobre la línea de indiferencia más lejana al origen pero que todavía toque la región factible. Esto se muestra en la siguiente figura:


Con el punto óptimo localizado gráficamente, la única tarea que queda es encontrar las coordenadas del punto. Nótese que el punto óptimo está en la intersección de las líneas de restricción para materiales y horas de mano de obra. Las coordenadas de este punto se pueden encontrar resolviendo el sistema de ecuaciones que forman estas dos restricciones utilizando cualquiera de los métodos de solución (suma y resta, sustitución o igualación). Las coordenadas de este punto resultan ser (6, 3). La sustitución de este punto en la función objetivo da la ganancia máxima:

Z = 5(6) + 5(3) = $45

Resumen del método gráfico.

Para resolver gráficamente problemas de programación lineal:

1. Exprésense los datos del problema como una función objetivo y restricciones.

2. Grafíquese cada restricción.

3. Localícese la solución óptima.
EJEMPLO 2.



Un departamento de publicidad tiene que planear para el próximo mes una estrategia de publicidad para el lanzamiento de una línea de T.V. a color tiene a consideración 2 medios de difusión: La televisión y el periódico.

Los estudios de mercado han mostrado que:



1. La publicidad por T.V. Llega al 2 % de las familias de ingresos altos y al 3 % de las familias de ingresos medios por comercial.



2. La publicidad en el periódico llega al 3 % de las familias de ingresos altos y al 6 % de las familias de ingresos medios por anuncio.



La publicidad en periódico tiene un costo de 500 dls. por anuncio y la publicidad por T.V. tiene un costo de 2000 dls. por comercial. La meta es obtener al menos una presentación como mínimo al 36 % de las familias de ingresos altos y al 60 % de las familias de ingresos medios minimizando los costos de publicidad.



OBJETIVO : Minimizar los costos de publicidad.



VARIABLE DE DECISION: Anuncios para las familias de ingreso alto (X1).

Anuncios para las familias de ingreso medio (X2).



RESTRICCIONES : Porcentaje de presentación.




Minimizar

Sujeto a:









SOLUCION OPTIMA:







EJEMPLO 3.



Un expendio de carnes acostumbra preparar carne para hamburguesa con una combinación de carne molida de res y carne molida de cerdo. La carne de res contiene 80 % de carne y 20 % de grasa y le cuesta a la tienda 80 centavos por libra. La carne de cerdo contiene 68 % de carne y 32 % de grasa y cuesta 60 centavos por libra. ¿Qué cantidad de cada tipo de carne debe emplear la tienda por cada libra de carne para hamburguesa si desea minimizar el costo y mantener el contenido de grasa no mayor de 25 %?



Minimizar

Sujeto a:







SOLUCION OPTIMA:

No hay comentarios:

Publicar un comentario en la entrada