PROGRAMACION DE METAS

INTRODUCCIÓN.

La mayoría de las situaciones de decisión real, sean personales o profesionales, se caracterizan por metas (atributos) y objetivos múltiples más que por un simple objetivo. Estas metas (atributos) pueden ser complementarias, pero frecuentemente son conflictivas y también inconmensurables. Por ejemplo, un productor de autos como la General Motors desearía construir un vehículo de pasajeros que pudiera venderse por menos de $200,000.00, tuviera 250 caballos y consiguiera 40 millas por galón. Consideremos, por ejemplo, las metas (atributos) de economía de combustible y de potencia. entre más alta sea la potencia, menor es la economía de combustible, indicando que las dos metas (atributos) están en conflicto. Además estas dos metas (atributos) son inconmensurables, pues la potencia y las millas por galón tienen diferentes escalas y dimensiones.

PROGRAMACIÓN META.

La formulación de un modelo de Programación Meta es similar al modelo de P.L.. El Primer paso es definir las variables de decisión, después se deben de especificar todas las metas gerenciales en orden de prioridad. Así, una característica de la Programación Meta es que proporciona solución para los problemas de decisión que tengan metas múltiples, conflictivas e inconmensurables arregladas de acuerdo a la estructura prioritaria de la administración.

La Programación Meta es capaz de manejar problemas de decisión con una sola meta o con metas múltiples. En tales circunstancias, las metas establecidas por el tomador de decisiones son logradas únicamente con el sacrificio de otras metas.

Las características que distinguen la programación Meta es que las metas se satisfacen en una secuencia ordinal. Esto es, las metas que deben clasificarse en orden de prioridad por el tomador de decisiones son satisfechas secuencialmente por el algoritmo de solución. Las metas con prioridad baja se consideran solamente después de que las metas de prioridad alta se han cumplido. La Programación meta es un proceso de satisfacción, en el sentido de que el tomador de decisiones tratará de alcanzar un nivel satisfactorio en vez del mejor resultado posible para un solo objetivo.

La noción fundamental de la Programación Meta, comprende incorporar todas las metas gerenciales en la formulación del modelo del sistema. En la programación Meta, en vez de intentar minimizar o maximizar la Función Objetivo directamente, como en la programación lineal, se minimizan las desviaciones entre las metas y los límites logrables dictados por el conjunto dado de restricciones en los recursos. Estas variables de desviación, que se denominan de "holgura" o "sobrantes" en programación lineal toman un nuevo significado en la Programación Meta. Ellas se dividen en desviaciones positivas y negativas de cada una de las submetas o metas. El objetivo se convierte entonces en la minimización de estas desviaciones, dentro de la estructura prioritaria asignada a estas desviaciones.

CONCEPTOS PARA LA TOMA DE DECISIONES CON ATRIBUTOS MULTIPLES EN AUSENCIA DE INCERTIDUMBRE: PROGRAMACIÓN DE METAS.

• Una Función valor v(x1,x2,....xn) es una función de valor aditivo si existen n funciones v1(x1), v2(x2),...vn(xn) que satisfagan

i=n

v(x1,x2,....xn) = " vi(xi)

i=1

• Una función costo c(x1,x2,....xn) es función de costo aditivo si existen n funciones c1(x1), c2(x2),....cn(xn) que satisfagan

i=n

c(x1,x2,....xn) = " ci(xi)

i=1

• Un atributo (llamémosle atributo 1) es preferencialmente independiente (pi) de otro atributo (el atributo 2) si las preferencias para valores del atributo 1 no dependen del valor del atributo 2.

• Si el atributo 1 es pi del atributo 2, y el atributo 2 es pi del atributo 1, entonces el atributo 1 es mutua y preferencialmente independiente (mpi) del atributo 2.

• Un conjunto S de atributos es mutua y preferencialmente independiente (mpi) de un conjunto S´ de atributos si (1) los valores de los atributos en S´ no afectan las preferencias para los valores de los atributos en S, y (2) los valores de los atributos en S no afectan las preferencias para los valores de los atributos en S´.

• Un conjunto de atributos 1,2,....,n es mutua y preferencialmente independiente (mpi) si para todos los.

• TEOREMA 1. Si el conjunto de atributos 1,2,....,n es mpi, las preferencias del tomador de decisiones se pueden representar por una función valor (o costo) aditiva.

FORMULACIÓN DE MODELOS.

Restricciones de meta

-Por cada meta

Componentes en la F.O. (minimizar suma de desviaciones con respecto a las metas)

| FORMULACIÓN

-Resticciones Estructurales (no tienen que ver con las metas)

Las suposiciones básicas que caracterizan el modelo de programación lineal se aplican igualmente al modelo de programación meta. La diferencia principal en la estructura es que la programación meta no intenta minimizar o maximizar la función objetivo como lo hace el modelo de programación lineal. En vez de ello, busca minimizar las desviaciones entre las metas deseadas y los resultados reales de acuerdo a las prioridades asignadas.. El objetivo de un modelo de programación meta es expresado en teérminos de las desviaciones de las metas a que se apunta. esto es las desviaciones de las metas se colocan en la función objetivo y deben minimizarse. El modelo general de la programación meta puede expresarse matemáticamente de la siguiente manera:

m

min Z = " wi(di+ + di-)

i=1

s.a.

n

"aijxj+di- - di+ = bi para toda i

j=1

xj,di-,di+" 0 para toda j

Donde:

w = Ponderación de las desviaciones con respecto a la meta.

di- = Desviación déficit

di+ = Desviación excedente

EJEMPLO: SATISFACCIÓN DE UNA SOLA META.

Una división de Schwim Manufacturing Company produce dos tipos de bicicletas: (1) una bicicleta de 3 velocidades y (2) una de 10 velocidades. La división obtiene una utilidad de $25 en la bicicleta de 10 velocidades y $15 en la bicicleta de 3 velocidades. Debido a la fuerte demanda de estos artículos, durante el período de planeación de verano la división cree que puede vender, a los precios que prevalezcan, todas los unidades de estas dos bicicletas que produzca. Las instalaciones de producción se consideran recursos escasos. estos recursos escasos corresponden al departamento de ensamblado y terminado. Los tiempos unitarios de procesamiento y las capacidades de cada uno de los departamentos se muestran en la tabla siguiente:

Hrs. requeridas para procesar cada bicicleta

Tipo de bicicleta	En el Depto. de ensamble	En el depto. de terminación	Contribución a la utilidad unitaria
3 velocidades	1	1	15
10 velocidades	3	1	25
Hrs. disponibles en cada depto.	60	40

La división durante este período de planeación se enfrenta a cambios grandes de organización y cree que el maximizar la utilidad no es un objetivo realista. Sin embargo, desearía lograr un nivel satisfactorio de utilidad durante este período de dificultad. La dirección cree que la utilidad diaria de $600 debería satisfacerse y desea determinar, dadas las restricciones del tiempo de producción, la mezcla de producto, que debería llevar a esta tasa de contribución a utilidades.

Formula un modelo de programación meta que satisfaga estos requerimientos

Definición de variables:

x1 = Número de bicicletas de 3 velocidades producidas por día

x2 = Número de bicicletas de 10 velocidades producidas por día

d1- = Cantidad por debajo de la utilidad perseguida

d1+ = cantidad por encima de la utilidad perseguida

Minimizar Z = d1- + d1+

s.a.

x1 +3x2 " 60 (horas de ensamble).

Restricciones estructurales

x1 + x2 " 40 ( (horas de terminación)

15x1 +25x2 +d1- - d1+ = 600 (Utilidad perseguida) Restricción meta

x1,x2,d1-,d1+ " 0

Nota: Puesto que tanto d1-,d1+ aparecen en la función objetivo y a ambas se les asigna pesos iguales, esto indica que la administración desea lograr la utilidad meta exactamente..

TAREA.

Plantea este mismo modelo con las siguiente consideración:

La administración cree que es dos veces más importante sobrelograr que sublograr la meta de utilidad perseguida.

1.4.2 EJEMPLO METAS MÚLTIPLES.

Considera la información que se presenta en la siguiente tabla:

Departamentos

Producto	1	2	3	4
1	.10	2.1	1	.3	415
2	.08	1.4	.7	.2	362
3	.05	1.1	.6	.15	216
4	.04	.9	.5	.1	68
Disp. hrs/mes	320	2400	800	450

*El producto 2 no debe exceder 90 unidades al mes.

*Cada hora extra aumenta los costos en $20.00

Metas:

Alcanzar utilidades de por lo menos $350,000.00 al mes.

Maximizar la utilización de los 4 departamentos.

No producir más del 50% de la producción total en cualquiera de los 4 productos (en unidades).

Limitar el número de horas extras en el departamento 2 a 300 hrs. al mes.

Definición de variables:

xi = cantidad a producir del producto i mensualmente. i = 1,2,3,4.

F.O.

Min Z = d1- +d2- +d3- +d4- + d5- +d6+ +d7+ +d8+ +d9+ +d10+

s.a.

1) 415x1 +362x2 +216x3 + 68x4 -20d2+ - 20d3+ - 2 0d4+ - 20d5+ -d1 + + d1- =350,000

2).10x1+.08x2+.05x3+.04x4 -d2+ + d2- = 320

2.1x1 +1.4x2 +1.1x3 +0.9x4 -d3+ + d3- = 2400

x1+.7x2+.6x3+.5x4 -d4+ +d4- = 800

.3x1 +.2x2 +.15x3 +.1x4 -d5+ +d5- = 450

3)x1-d6+ +d6- = .5(x1+x2+x3+x4) ! .5x1-.5x2-.5x3-.5x4 -d6+ +d6- = 0

-.5x1 +.5x2 -.5x3-.5x4 -d7+ +d7- = 0

-.5x1-.5x2+.5x3-.5x4 -d8+ +d8- = 0

-.5x1-.5x2-.5x3+.5x4 -d9+ +d9- = 0

4)d3+ -d10+ +d10- = 300

Restricciones estructurales:

x2" 90

xi" 0 para toda i

di+,di- " 0 para toda i.

EJEMPLO METAS MÚLTIPLES CON PRIORIDAD.

Considera la situación de Schwim Manufacturing Company en donde la administración desea alcanzar varias metas. Ahora supondremos que la administración desea ordenar dichas metas en orden de importancia y que la meta más importante tiene prioridad absoluta sobre la siguiente meta más importante y así sucesivamente.

Para lograr que las metas de baja prioridad se consideren solamente después de lograr las metas de alta prioridad, se clasifican las metas en k rangos y las variables de desviación asociadas con las metas, se les asigna un número prioritario Pj(j = 1,2,....,k). Los factores de prioridad satisfacen

P1>>>P2>>>...Pj>>>Pj+1.

Las relaciones de prioridad implican que la multiplicación por n, no importa que tan grande sea n, no puede hacer una meta de baja prioridad tan importante como una meta de alta prioridad (por ejemplo: Pj>nPj+1).

Ahora supongamos que la división de bicicletas de Schwim, además de lograr sus $600.00 de meta primaria de utilidad, desea utilizar completamente sus departamentos de ensamblaje y terminación durante la reorganización que se avecina. Esto es, como una meta secundaria, la división desea minimizar el tiempo ocioso. La formulación del modelo es:

Minimizar Z = P1(d1- + d1+) + P2(d2-+d3-)

s. a.

15x1+25x2 +d1- -d1+ = 600

x1 +3x2 + d2- -d2+ = 60

x1 +x2 +d3- -d3+ = 40

x1,x2,di-,di+ " 0

Donde:

x1 = Número de bicicletas de 3 velocidades producidas por día

x2 = Número de bicicletas de 10 velocidades producidas por día

d1- = Cantidad por debajo de la utilidad perseguida

d1+ = cantidad por encima de la utilidad perseguida

d2- = Tiempo ocioso diario en el departamento de ensamble

d2+ = Tiempo extra diario en el departamento de ensamble

d3- = Tiempo ocioso diario en el departamento de terminación.

d3+ = Tiempo extra diario en el departamento de terminación.

Nota: Puesto que d1- y d1+ se incluyen en la función objetivo, el modelo intentará lograr exactamente la utilidad diaria perseguida de $600, minimizando tanto las desviaciones positivas como las negativas. Con d2+ d3+ y eliminados de la función objetivo, sin embargo, el modelo no se preocupará del tiempo extra en el departamento de ensamble o terminación e intentará minimizar solamente el tiempo ocioso en estos departamentos. Debido a que la meta de utilidad perseguida es más importante que la meta de minimización del tiempo ocioso, a esta se le asigna prioridad P1 . El modelo intentará lograr esta meta hasta donde más le sea posible antes de considerar la meta secundaria de minimizar el tiempo ocioso de producción.

EJERCICIO:

Resolver gráficamente este problema.

DIFERENCIAS ENTRE EL SIMPLEX DE PROGRAMACIÓN DE METAS Y EL SIMPLEX NORMAL.

El simplex normal tiene un solo renglón 0, mientras que el simplex de programación de metas necesita n renglones 0, uno por cada meta.

En el simplex de programación de metas se emplea el método siguiente para la variable de entrada: se encuentra la meta de máxima prioridad (la meta i' ) que no se haya alcanzado, o se encuentra la meta i' de máxima prioridad que tenga Zi (Término de la función objetivo que incluye la meta i) > 0 . se calcula la variable con el coeficiente más positivo en el renglón 0, meta i', y se anota esta variable en la base, sujeta a la siguiente restricción. Con ello se reduce Zi y se asegura que esta cerca el cumplimiento de la meta i'. Sin embargo, si una variable tiene un coeficiente negativo en el renglón 0 asociado con una meta que tiene mayor prioridad que i', la variable no puede entrar a la base. Introducir en la base esa variable aumentaría la desviación con respecto a alguna meta de mayor prioridad. Si la variable con el coeficiente más positivo en el renglón 0 (variable i') no puede entrar en la base, intente encontrar otra variable con un coeficiente positivo en el renglón 0 (meta i'). Si ninguna variable del renglón 0 (meta i') puede entrar en la base, no hay manera de acercarse al cumplimiento de la meta i' sin aumentar la desviación con respecto a alguna meta de mayor prioridad. en este caso, se pasa al renglón 0 (meta i' + 1) para tratar de satisfacer la meta i' + 1.

Cuando se lleva a cabo un pivoteo, se debe actualizar el renglón 0 para cada meta.

Una tabla dará la solución óptima si todas las metas se satisfacen (esto es, Z1 = Z2 = .....= Zn = 0 ), o si cada variable que puede entrar en la base y reducir el valor de Z'i de una meta i' no satisfecha aumenta la desviación con respecto a una meta i que tiene más prioridad que la meta i'.

Resuelve el ejemplo de METAS MULTIPLES CON PRIORIDAD Utilizando el método simplex.

EJMPLO DE METAS MULTIPLES Y SUBMETAS.

En el ejemplo de la Schwim, la máxima utilidad alcanzada, tomando 60 horas de tiempo de ensamble, 40 horas de tiempo de terminación y resolviendo como un problema de programación lineal, es de $700.00. Debido a la reorganización de la división se han considerado casos en donde la administración quedaría satisfecha (al menos temporalmente) con un plan de producción que conduzca a una utilidad más baja que $600.00.

Supongamos que la reorganización se ha llevado a cabo y que la administración desea lograr una tasa de utilidad diaria de $750.00. Esto significaría que algunas restricciones previas anexas deberían violarse. Sin embargo, supongamos que las 60 y 40 horas representan la capacidad de producción de los departamentos de ensamble y terminación en tiempo normal solamente, utilizando la fuerza laboral existente. El tiempo extra podría utilizarse en cualquier departamento; por tanto, las desviaciones por encima como por debajo de las 40 y 60 horas serían factibles. La tasa de pago de horas extras es 3 veces más alta que la del departamento de ensamble. Las metas prioritarias de la administración, de mayor a menor importancia, son las siguientes:

P1 = Lograr tasa diaria de utilidad perseguida de $750.00

P2 = Minimizar el tiempo ocioso en ambos departamentos.

P3 = Minimizar el tiempo extra en ambos departamentos

La formulación de la programación meta es:

Minimizar Z = P1(d1- + d1+) + P2(d2-+d3-) + 3P3d2+ + P3d3+

s. a.

15x1+25x2 +d1- -d1+ = 750 (Utilidad perseguida)

x1 +3x2 + d2- -d2+ = 60 (Horas de ensamble)

x1 +x2 +d3- -d3+ = 40 (Horas de terminación)

x1,x2,di-,di+ " 0 Para todo i

Nota: En este ejercicio se han asignado pesos diferentes (cardinales) o prioridades dentro de una meta dada, como también prioridades diferentes (ordinales o cardinales) a metas diferentes.

EJERCICIOS:

La agencia de publicidad Leon Burnit quiere determinar el programa de anuncios en TV para la Priceler Auto Company. Priceler tiene tres objetivos:

Objetivo 1 Sus anuncios deben ser vistos por un mínimo de 40 millones de personas con ingresos altos (PIA)

Objetivo 2 Sus anuncios deben ser vistos por un mínimo de 60 millones de personas con ingresos bajos (PIB).

Objetivo 3 Sus anuncios deben ser vistos por un mínimo de 35 millones de mujeres con ingresos altos (MIA)

Leon Burnit puede comprar dos tipos de anuncios: los que aparecen durante los juegos de fútbol y los que aparecen durante los melodramas; a lo más puede gastar $600,000.00 dólares. Los costos del comercial y las audiencias potenciales de un anuncio de 1 minuto se muestran en la siguiente tabla:

	PIA	PIB	MIA	COSTO
Anuncio en el fútbol	7 millones	10 millones	5 millones	100,000
Anuncio en los melodramas	3 millones	5 millones	4 millones	60,000

Leon Burnit debe plantear un modelo de programación por metas que determine cuántos minutos comprar durante el fútbol y cuántos durante los melodramas, reduciendo al mínimo la penalización total por ventas perdidas. Dicha penalización, en miles de dólares es : $200.00 para la meta 1, $100.00 para la meta 2 y $50.00 para la meta 3

Elabora el modelo de programación por metas.

Supongamos que se añade a este modelo la restricción de que se debe cumplir con un presupuesto de $600,000.00 dólares. Si se decide que se tenga una penalización de 1 dólar por cada dólar de diferencia con esa meta, entonces ¿cuál sería la formulación correcta del modelo modificado?.

Utiliza el método simplex para resolver este problema (modificado).

Utiliza LINDO para resolver este problema (modificado).

EJERCICIOS DE TAREA.

Considera el siguiente problema de inversión:

Se cuenta con $2000000 para invertir en 6 años. Los instrumentos de inversión, junto con sus respectivas tasas de interés a ganar, se muestran en la siguiente tabla:

1 2 3 4 5 6 Años

1 )Acciones

2 )Bonos

3) Prestamos

4) Bienes Raíces

5) Ahorro

Formula el problema como un modelo de P.L.

Formula el problema como un modelo de metas, considera las siguientes metas:

Maximizar rendimientos.

Invertir cuando menos 400,000 en bienes raíces.

No tener invertido más de 700,000 en cualquier instrumento financiero.

Formula el modelo considerando que la meta 1 es tres veces más importante que la meta 2 y cinco veces más importante que la meta 3

Formula el modelo considerando que la meta 1 es la más prioritaria, la 2 la que sigue y por último la meta 3.

Como cambia la función objetivo del modelo de la Schwim (para el caso de Metas múltiples y submetas), si el costo del tiempo ocioso en el departamento de ensamble es del doble del departamento de terminación

Resolver los problemas de Murty: 8.2, 8.5

Winston: Sección 14.1: 5,9,10

1.4.7. APLICACIÓN DE CASOS DE PROGRAMACIÓN POR METAS.

La Preslow Company fabrica tres clases de abrigos para caballeros: (A) deportivo, (B) Formal y (C) Ejecutivo. Aún y cuando la compañía es un negocio familiar, la mayoría de los empleados no son miembros de la familia. Debido a la naturaleza competitiva del negocio y a la gran demanda de mano de obra de la industria, es de gran importancia mantener satisfechos a los empleados. Los administradores de la Preslow consideran que una medida importante para satisfacer las necesidades de sus empleados es ofrecerles empleo de tiempo completo, aun cuando esto exija producir en exceso e incurrir en alguna pérdidas. por fortuna, los administradores esperan que las demandas de sus productos siga siendo bastante elevada. De hecho, para satisfacer parte de la demanda, podría ser necesario operar en tiempo extra.

Las tres líneas de abrigos de la Preslow se fabrican en dos departamentos. la siguiente tabla es un programa semanal de requerimientos de mano de obra y materiales para el proceso de fabricación. Los precios unitarios para las tres líneas son: $100, $150 y $250, respectivamente. Los administradores han determinado que a un nivel normal de producción los costos variables son de $70, $80 y $100 por abrigo, respectivamente. Los costos de tiempo extra son $2 por hora por encima del salario normal para el departamento 1 y $3 para el 2. Los materiales extra pueden adquirirse a un costo de $2 por yarda por encima del costo normal.

Los administradores de la empresa han pronosticado que la demanda del mercado para el abrigo deportivo es de 1,000 unidades por semana, y la demanda de las otras dos líneas es de 500 y 200 unidades, respectivamente. El nivel de equilibrio de producción es de 100 unidades del producto uno y 50 unidades de cada uno de los otros 2 productos.

Para ayudarse analizar el problema, los administradores de la Preslow han identificado, en orden de prioridad, las siguientes metas:

utilizar toda la capacidad de producción disponible.

Alcanzar los niveles de producción de punto de equilibrio en cada una de las líneas de producción.

dado que es probable que exista escasez de mano de obra en el departamento 2, y dado que puede enviarse personal, en tiempo extra a ese departamento, el tiempo extra aquí puede ser mayor que el del departamento 1. Sin embargo, el tiempo extra del departamento 2 debe estar limitado a 600 horas. El tiempo extra del departamento 1 no debe ser mayor de 200 horas.

Alcanzar una meta de utilidades semanales de $20,000

Satisfacer todas las demandas del mercado. Dentro de esta meta, deben utilizarse ponderaciones distintas para reflejar la contribución unitaria normal a las utilidades

	Requerimientos	de productos	(por unidad)
	Deportivo	Formal	Ejecutivo	Recursos (mano de obra y materiales)
Departamento 1	4 horas	12 horas	10 horas	8,000 horas
Departamento 2	6 horas	6 horas	16 horas	4,000 horas
Material	8 yardas cuadradas	6 yardas cuadradas	12 yardas cuadradas	8,000yardascuadradas

Plantea el problema como un modelo de programación por metas.

La compañía de distribución Alpha suministra un solo producto a tres clientes en diversos sitios desde bodegas diferentes. Durante el período de planeación considerado, la compañía no puede cumplir la demanda de los clientes. Sin embargo, la compañía ha determinado que las demandas de ciertos clientes deben satisfacerse a expensas de otros. Para evitar desequilibrios serios, es importante balancear la porción de demanda satisfecha entre ciertos clientes. también debido a acuerdos sindicales, la compañía debe satisfacer ciertos requisitos mínimos en los niveles de embarque en ciertas rutas. Finalmente, varias de las rutas sobre las cuales se podría embarcar el producto son peligrosas y deben evitarse.

A continuación se resume el problema de transporte y los costos de embarque se dan en cada una de las celdas y los valores de demanda en los márgenes. Nota que la demanda total excede al suministro total en 1,500 unidades.

	Cliente 1	Cliente 2	Cliente 3	Suministro
Bodega 1	10	4	12	3000
Bodega 2	8	10	3	4000
Bodega 3	2000	1500	5000

La administración tiene la siguientes preferencias en las metas (en orden decreciente de importancia):

Satisfacer la demanda total del cliente 3 ( entrega garantizada)

Satisfacer por lo menos el 75% de la demanda de cada cliente.

Minimizar el costo de transporte para los artículos embarcados.

Embarcar por lo menos 1000 unidades en la ruta de la Bodega 2 al Cliente 1 (convenio sindical)

Minimizar el costo de embarque en las rutas de la bodega 1 al cliente 3 y de la bodega 2 al cliente 2 (peligros).

Balancear el porcentaje de demanda satisfecha entre los clientes 1 y 2.

Plantear el modelo de programación meta.

La compañía Bevco ha desarrollado recientemente tres nuevos productos haciendo uso del exceso de capacidad en sus tres plantas sucursales existentes. Cada producto puede fabricarse en cualquiera de las tres plantas. El análisis ha mostrado que sería rentable utilizar el exceso de capacidad para producir estos nuevos productos. En realidad, el propósito principal de la gerencia al desarrollar los nuevos productos era lograr la utilización completa de la capacidad productiva de exceso sobre una base rentable. Mientras que las plantas Bevco generalmente operan a capacidad plena en sus líneas de productos existentes, la producción por debajo de la capacidad normal ocurre con poca frecuencia, presentando problemas con la fuerza laboral. Aunque la compañía no necesita la fuerza laboral plena durante los períodos de holgura, el costo de los despidos sería considerable, y Bevco desearía evitar esto tanto como fuera posible.

Además, la gerencia desearía balancear la utilización del exceso de capacidad entre las plantas sucursales. esto serviría para distribuir equitativamente la carga de trabajo del personal de supervisores asalariados y reducir los agravios de la fuerza laboral que se le paga por horas, que de otra manera se sentiría discriminada con respecto a las cargas de trabajo o a los despidos.

Para el período que se está considerando, las plantas tienen las siguientes capacidades de producción en exceso ( en términos de unidades) de nuevos productos y capacidades de embarque disponibles asignadas a los nuevos productos:

Planta	Capacidad de exceso de producción (unidades)	Capacidad de embarque (pies cúbicos)
1	750	12,000
2	300	10,000
3	450	6,500

Los productos 1, 2 y 3 requieren 30,20 y 15 pies cúbicos por unidad, respectivamente. Las contribuciones unitarias a la utilidad de los productos 1,2 y 3 son $15 $18 y $12 respectivamente. Los pronósticos de ventas indican que Bevco puede esperar ventas tan altas como 900, 1,000 y 700 unidades de los productos 1, 2 y 3 respectivamente, durante el período de planeación en consideración.

Dada esta situación, la administración ha expresado las siguientes metas de preferencia en orden de importancia decreciente.

Lograr una utilidad perseguida de $15,000

Utilizar tanto, como sea posible, la capacidad de exceso. Debido al bajo costo de la mano de obra, la administración cree que es 1.5 veces más importante utilizar la capacidad de exceso de la planta 1 que la de las plantas 2 y 3.

Lograr un balance de la carga de trabajo en la utilización de exceso de capacidad entre todas las plantas. debido a ciertas demandas adicionales de los trabajadores de la planta 1, la administración cree que si ocurre algún desbalance en la carga de trabajo, es dos veces más importante favorecer a la planta 1 con menor trabajo con respecto a las plantas 2 y 3.

Lograr el pronóstico de ventas para el producto 2, puesto que éste tiene la mayor contribución a la utilidad por unidad.

Producir suficiente cantidad de los productos 1 y 3 para cumplir con las ventas pronosticadas.

No exceder la capacidad de embarque disponible.

Plantear el modelo de programación meta.

TEOÍA DE REDES

MODELOS DE REDES

Una red es una construcción matemática formada principalmente por dos conjuntos: un conjunto de nodos (N) y un conjunto de arcos (A), estos dos conjuntos están relacionados de tal forma que cada arco está siempre definido por un par de nodos. La figura 1 muestra un ejemplo sencillo de una red, la cual consta de cinco nodos (representados con círculos) y de siete arcos (representados con líneas).

Figura 1 : Red

Los modelos de redes son muy usados debido a su estructura, aún cuando es muy simple, sirve para capturar las variables y relaciones importantes existentes en muchos sistemas reales. El caso más importante es precisamente en los sistemas de carreteras o vialidades. Por ejemplo la red de la figura 1 puede fácilmente interpretarse con los arcos como tramos de carreteras y los nodos como ciudades o intersecciones de carreteras. Adicionalmente los modelos de redes sirven para representar una gran cantidad de sistemas para los cuales la interpretación no es tan directa como la descrita anteriormente. De manera arbitraria diferentes modelos de redes pueden clasificarse como: redes físicas, redes logísticas y redes de programación.

REDES FÍSICAS

Estos modelos representan redes tales como las redes de: carreteras, vialidades urbanas, teléfonos, agua potable, etc. Para este tipo de redes existe una relación directa entre los nodos del modelo y puntos o zonas en el espacio y entre los arcos del modelo y tramos de infraestructura física. Dentro de las redes físicas, la modelación de sistemas de carreteras o de vialidades urbanas cobra una gran importancia.

Para analizar el movimiento de transporte en una zona urbana, la atención se centra en las vialidades principales ( las vialidades secundarias generalmente se omiten). La zona urbana en sí se divide en zonas, las cuales se representan mediante nodos, localizados en el "centroide" de la zona. Estos centroides se conectan a la vialidad principal mediante arcos artificiales. Otro tipo de nodos que se tienen son los que representan las intersecciones de vialidades principales. En cuanto a los arcos, además de los arcos artificiales mencionados, se tienen a los arcos que representan segmentos de la vialidad principal. En la figura 2 se tiene un ejemplo en el cual los centroides y los arcos artificiales se representan con líneas punteadas y las intersecciones y vialidades principales se representan con líneas continuas. Los modelos de redes de carreteras son muy similares, excepto que los nodos y arcos artificiales son menos comunes. En estos modelos, los centroides de zonas o regiones se acostumbran poner en ciudades importantes. De esta manera, los nodos de estas redes son regularmente ciudades e intersecciones de carreteras, mientras que los arcos son tramos de carreteras.

Figura 2 : Red de vialidades

REDES LOGÍSTICAS

Estas redes se usan para representar las decisiones logísticas en una empresa (almacenamiento, producción, distribución, etc.). Generalmente los nodos están relacionados con puntos en el espacio, como en el caso anterior, pero los arcos representan algo más abstracto que un tramo físico. Por ejemplo, en la figura 3 se tiene una red en la que los nodos representan plantas y almacenes. Los arcos que los unen pueden representar toda una serie de acciones logísticas para transportar producto de una planta a un almacén. Parte del transporte podría ser realizado mediante ferrocarril y parte mediante autotransporte y todo estaría representado por un solo arco. Estas redes se generalizan fácilmente para incluir además de plantas de producción, diferentes niveles de almacenes (regionales, locales, etc) y de clientes (mayoristas, minoristas, etc).

Figura 3: Red Logística

REDES DE PROGRAMACIÓN

En estas redes los nodos representan "eventos", esto es puntos en el tiempo y los arcos representan la posibilidad de realizar alguna actividad. Por ejemplo en la figura 4 se tiene una red que representa al problema de planeación de la producción. En este ejemplo los nodos representan cada uno de los meses del año (excepto el nodo 0) y los arcos representan la posible realización de actividades de producción y de conservación de inventario. Los arcos (0, i) indican la posibilidad de producción durante el mes i; los arcos (i, i+1) la posibilidad de almacenar inventario del mes i al mes i+1. Los arcos que llegan al nodo 0 y al nodo 1 representan la posibilidad de producción y de tener un inventario inicial respectivamente. Los arcos que salen de los nodos i representan la posibilidad de satisfacer la demanda del producto y de guardar producto en inventario para el siguiente período. Otro ejemplo son las redes de actividades para la planeación de proyectos. En estas redes los arcos representan la realización de actividades y los nodos representan la terminación o inicio de estas actividades. En este caso, la red sirve también para modelar las relaciones de precedencia entre distintas actividades del proyecto.

P

P1 P2 ........... P12

I0 I1 I2 I11 I I12

.......................

D1 D2 D12

Figura 4: Red de Programación

Combinaciones de uno o varios de estos tipos de redes dan lugar a "redes mixtas", por ejemplo, el problema de planeación de la producción puede estar referido a un conjunto de plantas y a un conjunto de almacenes, lo que daría lugar a una combinación de red logística y red de programación.

DEFINICIONES BÁSICAS DE REDES

GRÁFICAS Y REDES

Una gráfica G, se define como un conjunto N de nodos y un conjunto A de arcos, tales que cada arco se define especificando un par de nodos. en forma matemática se escribe como:

G = (N, A)

Si el par de nodos es un par ordenado, lo cual significa que es importante la dirección del arco, se habla de gráficas dirigidas. En este caso, cada arco tiene nodo inicial y un nodo final. La red de la figura 2 es una gráfica no-dirigida, lo cual podría ser consecuencia de considerar solamente vialidades con movimientos en ambas direcciones. Por el contrario, la red de la figura 3 tiene arcos dirigidos (representados con flechas), debido a que el movimiento de producto es siempre de plantas a almacenes y no en ambas direcciones.

Una red también llamada gráfica ponderada, es una gráfica con "pesos" asociados a cada uno de los arcos. Un peso es una función que a cada arco le asocia un número real y puede tener diversas interpretaciones tales como las de distancia, tiempo o costo. En la red de la figura 2 cada arco podría tener un peso asociado significando la distancia en el tramo de vialidad que representa.

Una red de flujo es una red en la que cada arco tiene asociada una variable, llamada comúnmente flujo. El flujo puede interpretarse en el caso de una red de carreteras como la cantidad de vehículos o de bienes que circulan en cada arco de la red. En otros casos, el flujo significa la cantidad que se tiene de alguna actividad en los arcos de la red. Por ejemplo en la red de la figura 3. el flujo asociado con cada arco es la cantidad de producto que se distribuye entre una planta y un almacén determinado. En el caso de la figura 4, el flujo en algunos arcos indica la producción a realizar en algún período determinado y en otros la cantidad de producto destinada a satisfacer la demanda o a guardarse como inventario. En redes de flujo, el peso asociado a cada arco toma la interpretación de "impedancia" o resistencia al flujo, la cual aumenta con el flujo sobre el arco. En estas redes, pesos tales como la distancia de un arco son menos usados, pues no dependen del flujo. En la red de la figura 3, se podría tener un costo por cada unidad transportada entre una planta y un almacén y entonces el costo total sobre el arco sería función de su flujo. Es común tener en redes de flujo otra función asociada con cada arco, que es su capacidad, que significa la máxima cantidad de flujo que puede ocurrir en un arco.

RUTAS Y CICLOS

Una ruta es una secuencia de nodos y arcos:

n0a1n1a2n2........aknk

en donde el arco ai = (ni-1,ni), lo cual garantiza "continuidad" en la secuencia. Una ruta siempre se define para un par de nodos, siendo n0 el nodo inicial y nk el nodo final de ésta. Si los arcos de la ruta son dirigidos, entonces se habla de una ruta dirigida. Por ejemplo, tomando la red de la figura 1, las siguientes secuencias definen tres diferentes rutas entre los nodos 1 y 5:

1(1,3)3(3,5)5

1(1,3)3(3,4)4(4,5)5

1(1,2)2(2,4)4(4,5)5

Una ruta es simple si no usa ningún arco más de una vez. Una ruta es elemental si no usa ningún nodo más de una vez. Si una ruta es elemental, necesariamente tiene que ser simple, pues una ruta que no es simple no puede ser elemental ya que usar un arco más de una vez implica usar sus nodos también más de una vez. Las tres rutas definidas anteriormente entre los nodos 1 y 5 de la figura 1 son elementales y por lo tanto simples.

Un ciclo es una ruta simple en la cual coinciden el nodo inicial y el nodo final. Es una secuencia de nodos y arcos que regresan al nodo inicial sin repetir ningún arco. De esta manera, en la red de la figura 1, la secuencia:

1(1,3)3(3,1)1

no es un ciclo, pues el arco (1,3) es igual al arco (3,1). Podría ser un ciclo si la red fuera dirigida y por lo tanto los dos arcos mencionados fueran diferentes.

Al igual que en las rutas, existen ciclos dirigidos y no dirigidos, ciclos elementales y ciclos simples. Así un ciclo simple no repite ningún arco y un ciclo elemental no repite ningún nodo, excepto el nodo inicial que debe ser igual al nodo final. Un caso importante de ciclos es el ciclo Hamiltoniano, el cual es un ciclo elemental que visita todos los nodos de la red. Un caso particular de ciclos es el anillo, el cual consiste de un solo arco, el cual empieza y termina en el mismo nodo. En el ejemplo de la figura 1, las siguientes secuencias son todas ciclos:

1(1,2)2(2,3)3(3,1)1

1(1,2)2(2,4)4(4,3)3(3,1)1

1(1,2)2(2,4)4(4,5)5(5,3)3(3,1)1

En el caso de la red dirigida de la figura 3, la secuencia:

1(1,4)4(4,2)2(2,3)3(3,1)1

es un ciclo, sin embargo no es un ciclo dirigido puesto que los arcos (4,2) y (3,1) no tienen la dirección definida en la red. De hecho no existe ningún ciclo dirigido en toda esta red

CONEXIÓN Y ÁRBOLES

Un par de nodos en una gráfica están conectados si existe una ruta entre ellos. Una gráfica es conexa si cualquier par de sus nodos están conectados entre sí. Una gráfica dirigida se dice que es conexa si la gráfica resultante de no considerar la dirección de sus arcos es conexa. Un árbol es una gráfica conectada que no contiene ciclos. Un árbol T es un árbol de expansión de una gráfica G si contiene todos sus nodos. En la red de la figura 1, la gráfica T con conjunto de nodos N = {1,2,3} y conjunto de arcos A = {(1,2), (1,3)} es un árbol, pero no es un árbol de expansión al no contener todos los nodos de la red original. Por otra parte, el árbol T con N = {1,2,3,4,5} y A = {(1,2),(1,3),(3,4),(4,5)} es un árbol de expansión, al cumplir con la definición de árbol y contener a todos los nodos de la red.

TIPOS DE GRÁFICAS

Algunos tipos importantes de gráficas son las gráficas: simple, completa y bipartita. Una gráfica simple es aquella que no tiene anillos ni arcos paralelos. Dos arcos son paralelos si se definen con los mismos nodos. En el caso de redes dirigidas, dos arcos son paralelos si tienen el mismo nodo inicial y el mismo nodo final. Una gráfica completa es aquella gráfica simple que tiene un arco uniendo a cualquier par de nodos. Una gráfica bipartita es una gráfica en la cual existe una partición del conjunto de nodos, de tal manera que cada arco tiene un extremo en uno de los conjuntos y otro extremo en el otro. Una partición significa que todos los nodos están en cualquiera de sus subconjuntos y que ningún nodo pertenece a más de uno de éstos. En el caso de redes dirigidas se habla del conjunto de nodos origen y del conjunto de nodos destino y así cada arco empieza en un nodo origen y termina en un nodo destino. Un ejemplo de gráfica bipartita es la mostrada en la figura 3, en donde se puede observar que el conjunto de nodos origen comprende a los nodos 1, 2 y el conjunto de nodos destino a los nodos 3, 4, 5.

REPRESENTACIÓN DE REDES

Una red se representa naturalmente en forma gráfica, con lo que se pueden apreciar fácilmente las relaciones entre los diferentes elementos de la red. Sin embargo, esta representación no es la más adecuada para resolver problemas que involucran modelos de redes. Matemáticamente, existen dos formas principales de representar a una red: la matriz de incidencia y la matriz de adyacencia. Un nodo y un arco son incidentes si el nodo es uno de los dos nodos que definen al mencionado arco. Dos nodos son adyacentes, si ambos definen a un mismo arco.

Para definir estas matrices, se usará a n como el número de nodos de una gráfica y a m como el número de sus arcos. La matriz de incidencia, U, es una matriz de orden n x m, en la que cada uno de sus elementos, Uij , toma un valor igual al número de veces que el nodo nj y el arco aj son incidentes. Este valor es usualmente igual a 0 ó 1, excepto cuando se tiene un anillo, en cuyo caso un nodo y un arco inciden dos veces. La matriz de adyacencia V, es una matriz de orden m x m, en la que cada uno de sus elementos, Vij, toma un valor igual al número de arcos que los unen. Para gráficas simples, estos valores son solamente igual a 0 ó 1.

Para la red de la figura 1, la matriz de incidencia es U:

1 2 3 4 5 6 7

1 1 1 0 0 0 0 0

2 1 0 1 1 0 0 0

3 0 1 1 0 1 1 0

4 0 0 0 1 1 0 1

5 0 0 0 0 0 1 1

Para la misma red, la matriz de adyacencia es V:

1 2 3 4 5

1 0 1 1 0 1

2 1 0 1 1 0

3 1 1 0 1 1

4 0 1 1 0 1

5 0 0 1 1 0

Para redes grandes, lo usual es que estas matrices tengan una gran cantidad de elementos igual a cero, por lo que casi no son usadas para almacenar los datos de una red en computadora. Una estructura de datos muy usada para este fin es una lista llamada "estrella". En esta estructura los arcos son numerados en forma sucesiva. Primero se numeran los arcos que empiezan con el nodo 1, luego los que empiezan con el nodo 2 y así sucesivamente. Para los arcos que empiezan en el mismo nodo, se pueden numerar en forma ascendente con respecto al nodo final. Una vez numerados los arcos, se guardan secuencialmente sus nodos inicial y final, junto con un apuntador, apun( i ) , que para cada nodo i indica el primer arco que empieza con ese nodo. Se puede tomar apun ( 1 ) = 1, y los arcos que salen del nodo i serán los arcos de apun ( i ) a apun ( i + 1 ) - 1 en la lista. En redes dirigidas se hace apun ( n + 1 ) = m + 1 y en redes no dirigidas apun ( k + 1) = m + 1, con k igual al nodo inicial del último arco considerado.

Para la red de la figura 1 se tendrá:

i	apun ( i )
1	1
2	3
3	5
4	7
5	8
arco		nodo inicial		nodo final
1		1		2
2		1		3
3		2		3
4		2		4
5		3		4
6		3		5
7		4		5
8		-		-

PROBLEMAS EN MODELOS DE REDES

DEFINICIÓN DE PROBLEMAS

Los problemas varían de acuerdo al tipo de redes son muy diferentes los problemas en redes que en redes de flujo. Cuando se tiene una red, esto es una gráfica ponderada, los pesos usualmente significan distancia o tiempo, por lo que los problemas típicos son los de cómo conectar entre sí los nodos de la red o que arcos elegir para ir de u nodo a otro. Cuando se tiene una red de flujo el tipo de problemas es diferente, un problema muy común es el de encontrar un flujo sobre la red que satisfaga ciertas restricciones al menor costo posible. Otro problema sobre estas redes es encontrar el flujo máximo que puede circular sobre una red determinada.

PROBLEMA DEL ÁRBOL DE EXPANSIÓN MÍNIMA

Como se definió anteriormente, un árbol de expansión mínimo es una red conectada, sin ciclos y que comprende a todos los nodos de una red. Dentro de todos los posibles árboles de expansión que puede tener una red, el mínimo es aquel que tiene la menor suma de los pesos en los arcos del árbol. Si el peso que se tiene en la red es la distancia de cada uno de los arcos, este problema consiste en encontrar la forma más económica de conectar entre sí a todos los nodos de una red. Este problema tiene una de las formas más sencillas que existen para resolver problemas. En particular, algoritmos voraces obtienen al aplicarse en este problema la solución óptima. Un algoritmo voraz, es un algoritmo que en cada iteración trata de obtener el mejor valor posible con respecto a un objetivo sin preocuparse por las implicaciones que esto pueda tener en subsecuentes iteraciones. Para este problema un algoritmo voraz es como sigue: ordenar todos los arcos de menor a mayor peso. Construir un árbol escogiendo en cada iteración el arco con el menor peso que no haya sido seleccionado y que no forme un ciclo con los arcos ya seleccionados. Terminar cuando todos los nodos estén ya conectados.

PROBLEMA DE LA RUTA MAS CORTA

Este problema consiste en escoger aquella ruta entre dos puntos determinados que tenga la menor suma de los pesos en cada uno de sus arcos. Usualmente los pesos se refieren a la distancia o al tiempo de viaje en cada uno de los arcos de la red. Si la red es una red de carreteras o de vialidades urbanas, este problema consiste en escogerlos arcos de la red más favorables para viajar entre un par de puntos de ésta. Este problema tiene métodos eficientes de solución, algunos de los cuales se verán más adelante.

PROBLEMA DEL AGENTE VIAJERO

Este problema consiste en escoger un ciclo que visite a todos los nodos de una red y que tenga la menor suma de los pesos en cada uno de los arcos del ciclo. Al igual que en el problema de la ruta más corta, los pesos se refieren usualmente a distancias o tiempos de viaje. Este problema tiene aplicación para el diseño de las rutas que deberá recorrer un vehículo al visitar un conjunto de clientes y retornar posteriormente a su base. A diferencia del problema anterior, este problema no cuenta con un método eficiente para resolverlo, por lo que los problemas que se modelan de este tipo, son pequeños o se resuelven solamente de manera aproximada.

PROBLEMA DE FLUJO A COSTO MÍNIMO

Dada una red de flujo, este problema consiste en encontrar el flujo que al menor costo posible cumpla con un conjunto de restricciones. Estas restricciones son principalmente de tres tipos: restricciones de balance de flujo, restricciones de capacidad y restricciones de no-negatividad. Las restricciones de balance de flujo consisten en que para cada nodo, el flujo que entra al nodo debe ser igual al flujo que sale de él. Las restricciones de capacidad dicen que para cada arco de la red, el flujo no debe exceder cierta cantidad. Las restricciones de no-negatividad simplemente evitan que el flujo en cada arco sea una cantidad negativa. Existen métodos eficientes para resolver este tipo de problemas.

Ejemplos de estos problemas se tienen en las redes de las figuras 3 y 4. En la red de la figura 4, las restricciones de balance de flujo indican que en cada mes la cantidad producida más el inventario del mes anterior deben ser igual a la demanda del producto en ese mes más la cantidad enviada a inventario para el siguiente. Las restricciones de capacidad indican que hay límites en la cantidad a producir en cada mes o en la cantidad que puede guardarse como inventario en cualquier tiempo. Las restricciones de no-negatividad se tienen, dado que no tiene sentido hablar de flujos negativos, pues éstos significarían alguna cantidad negativa a producir o guardar como inventario. El costo del flujo estaría dado a partir de costos unitarios de producción y de conservación de inventario.

PROBLEMA DE FLUJO MÁXIMO

Este problema también está definido en redes de flujo, a diferencia del problema anterior, no se toman en cuenta los costos del flujo en cada uno de los arcos de la red. En este problema se quiere, dado que se tiene especificada la capacidad de cada arco, encontrar el flujo máximo que podría circular entre un nodo origen y un nodo destino. Este flujo máximo debería adicionalmente cumplir con restricciones de balance de flujo y de no-negatividad. Para este problema también se cuenta con algoritmos eficientes para resolverlos.

PLANTEAMIENTO DE MODELOS DE REDES

PROBLEMAS DE TRANSBORDO.

Si un problema de redes se refiere a la minimización de los costos de flujo de algún producto entre nodos, en donde cada nodo puede ser un punto de abastecimiento, un punto de demanda, o ambos, entonces se considera que el problema de redes es un problema de transbordo. El problema de transbordo es el más general de los problemas de redes, dado que cada nodo puede tener al mismo tiempo oferta y demanda y no existen restricciones sobre los flujos o sobre los tipos de nodos.

Ejemplo: La Ahab Oil Company tiene un solo campo petrolero desde donde envía todo el petróleo, a través de un oleoducto, a uno de dos centros de embarque, en donde se almacena en buques tanque para su envío a refinerías de Estados Unidos. La oferta diaria en el campo es de, 2,000 barriles. Deben considerarse los costos del oleoducto, los costos de embarque y las cantidades de petróleo que pueden enviarse a través de los oleoductos. Los costos del oleoducto y las capacidades diarias de éste, se muestran en la tabla 2.1. En la tabla 2.2 se presentan los costos de embarque de cada estación de embarque a cada refinería y las demandas diarias de las refinerías. Plantear el problema en forma de Red y de Programación Lineal.

Instalación de envío	Costo por barril	Capacidad del oleoducto (en barriles)
1	$0.20	1000
2	$0.15	500

Tabla 2.1 Costos y capacidades de los ductos

Refinería Costo de transporte por barril

Número	Ubicación	Desde centro 1	Desde centro 2	Demanda diaria
1	Nueva Jersey	$0.10	$0.15	600
2	Houston	$0.20	$0.25	800

Tabla 2.2 Costo de transporte y demandas

PROBLEMA TRANSPORTE.

Es un caso especial del problema de transbordo, en el que todos los nodos son o fuentes (nodos de oferta) o destinos (nodos de demanda). En un problema de transporte no existen nodos de transbordo.

Ejemplo. La Boor´s Brewery Company elabora una cerveza que se distribuye a nivel nacional a partir de dos fabricas de cerveza, Una en cada una de las costas de E.U.. La cerveza se envía a cuatro mayoristas que se encargan de la distribución subsecuente, por lo que la Boor´s se ocupa sólo de la distribución a los mayoristas. Los costos de distribución, por conjunto de 100 cajas que se envían a cada mayorista, se presentan en la tabla 2.3 , junto con la oferta mensual en cada fabrica y la demanda mensual de cada mayorista. Plantear el problema en forma de Red y de Programación Lineal.

Fábrica de cerveza	Albany N.Y.	Ames, Iowa	Luckenbach, Tx	Needles, Calif.	Oferta (en cientos de cajas)
Silver, Wa Apple Chill, N.C.	$21 $10	$15 $14	$18 $16	$9 $23	550 650
Demanda (cientos de cajas)	200	250	400	350

Tabla 2.3 Costos de distribución

PROBLEMA DE LA RUTA MAS CORTA

Trata el problema de encontrar el camino más corto (el camino de longitud mínima) desde el nodo 1 hacia cualquier otro nodo en la red.

EJEMPLO. Acabo de comprar (en el tiempo 0) un automóvil nuevo en 12,000 dólares. El costo del mantenimiento anual de un automóvil depende de la edad del automóvil al inicio del año, como se da en la tabla 2.4. Para evitar los altos costos de mantenimiento de un automóvil más viejo, puedo dar como adelanto mi automóvil y comprarme un automóvil nuevo. El precio que recibo al dar como adelanto automóvil depende de su edad al momento de la transacción (tabla 2.5). Para simplificar los cálculos, suponemos que en cualquier momento, me cuesta 12,000 dólares comprar un automóvil nuevo. Mi meta es minimizar el costo neto (costos de compra + costos de mantenimiento - dinero recibido por el automóvil viejo) incurrido durante los próximos cinco años. Formula la red del modelo

Edad del automóvil (Años)	Costo anual de mantenimiento (Dólares)
0	2000
1	4000
2	5000
3	9000
4	12000

Tabla 2.4 Costos de mantenimiento del automóvil

Edad del automóvil (años)	Costo al dar precio (dólares)
1	7000
2	6000
3	2000
4	1000
5	0

Tabla 2.5 Precios del automóvil al darlo como adelanto

PROBLEMA DEL ÁRBOL DE EXPANSIÓN MÍNIMA

La tarea consiste en construir un árbol que conecte todos los nodos de la red con un costo total mínimo, por el momento, nos conformaremos con plantear la red del siguiente problema (más adelante construiremos el árbol de expansión mínima).

EJEMPLO. Se va a instalar una red de comunicación entre doce ciudades. Los costos de los posibles enlaces directos entre pares permisibles de ciudades aparece en la tabla 2.6. Cada unidad de costo representa 10,000 dólares.

A la ciudad

Descargar

De la Ciudad

1

2

3

4

5

6

7

8

9

10

11

Enviado por:	Elprofe
Idioma:	castellano
País:	México