PROGRAMACIÓN POR METAS

Apl
Aplic
ic
icació
ació
aciónnd
dee lla
a vvida
ida real
real.. Asig
Asignac
nac
nación
ión de tie
tiempo
mpo de qui
quirófa
rófa
rófano
no en el hosp
hospit
it
ital
al Monte Sinaí
La situación ocurre en Canadá, donde el seguro de asistencia médica es obligatorio y
universal. El financiamiento, basado en una combinación de primas e impuestos, lo
controlan las provincias. Según este sistema, a los hospitales se les asigna un presu-
puesto anual fijo, y cada provincia les paga posteriormente a los médicos por medio de
un mecanismo de financiamiento de pago por servicio. Este arreglo de financiamiento
limita la disponibilidad de las instalaciones hospitalarias (por ejemplo quirófanos), lo
que a su vez frena la tendencia de los médicos a elevar sus ganancias personales por la
atención de más a sus pacientes. El objetivo del estudio es determinar un programa
diario equitativo para el uso de los quirófanos disponibles. El problema se modela apli -
cando una combinación de programación de metas y entera.

1.- F OR
ORMU
MU
MULA
LA
LACC IÓ
IÓNND
DEE U NA PR
PROO GR
GRAA MA
MACI
CI
CIÓÓ N D E M ETAS

La idea de la programación de metas se ilustra con un ejemplo.

E je
jemm pl
ploo 1-
1-11 ((P
P la
lani
ni
niff ic
icaa ci
cióó n t ri
ribu
bu
butt ar
arii a)
Fairville es una pequeña ciudad con una población de aproximadamente 20,000 habitantes. La base tributaria
anual por el impuesto predial asciende a $550 millones. Las recaudaciones anua les por alimentos y medicinas así
como por ventas generales es de $35 y $55 millones, respectivamente. El consumo anual de gasolina local se
estima en 7.5 millones de galones. El concejo municipal desea desarrollar las tasas tributarias con base en cuatro
metas principales:

1. Los ingresos fiscales deben ser por lo menos de $16 millones para satisfacer los compromisos financieros de la
ciudad.
2. Los impuestos sobre alimentos y medicinas no deben exceder el 10% de todos los impuestos recaudados.
'Este ejemplo está basado en Chissman and Associates, 1989
3. Los impuestos sobre las ventas generales no deben exceder el 20% de todos los impues¬tos recaudados.
4. El impuesto sobre la gascilina no debe exceder de 2 centavos por galón.

Sean las variables xp, xf y xs las tasas tributarias (expresadas como proporciones de las bases tributarias) sobre
la propiedad, alimentos, medicinas y ventas generales, y defina la variable xg como el impuesto sobre la
gasolina en centavos por galón. Las metas del concejo municipal se expresan entonces como
Cada una de las desigualdades del modelo representa una meta que el concejo municipal aspira satisfacer. Es
muy probable, sin embargo, que lo mejor que se puede hacer sea una solu¬ción compromiso que implique
estas metas conflictivas.
La forma en que la programación de metas determina una solución compromiso es convertir cada desigualdad
en una meta flexible en la cual la restricción correspondiente pueda ser violada, si es necesario. En función del
modelo de Fairville, las metas flexibles se expresan como sigue:

Las variables no negativas sT y s-iF, i = 1, 2, 3, 4 son variables de desviación que representan las
desviaciones por debajo y por arriba del lado derecho de la restricción i.
Las variables de desviación sT y st son dependientes por definición, y de ahí que no pueden ser las variables
básicas al mismo tiempo (de acuerdo con la teoría del método simplex). Esto sig¬nifica que en cualquier
iteración simplex, no más de una de las dos variables de desviación puede asumir un valor positivo. Si la
desigualdad i-ésima original es del tipo y su si- 0, entonces se satisface la meta i-ésima; en caso contrario, no
se satisface la meta i. En esencia, la definición de sT y st permite satisfacer o violar la meta i-ésima a
voluntad. Éste es el tipo de flexibilidad que ca¬racteriza a la programación de metas cuando se busca una
solución compromiso. Lógicamente, una buena solución compromiso busca minimizar la cantidad por la que
se viole cada meta.

En el modelo de Fairville, dado que las tres primeras restricciones son del tipo > y la cuarta es del tipo 5_, las
variables de desviación s1, s2, s3 y s-ti (que en el modelo aparecen en negritas) representan las cantidades por
las cuales se violan las metas respectivas. Por lo tanto, la solución compromiso busca satisfacer en cuanto sea
posible los siguientes cuatro objetivos:
Estas funciones se minimizan sujetas a las ecuaciones de restricción del modelo.
¿Cómo podemos optimizar un modelo de múltiples objetivos con metas conflictivas? Con este fin se
desarrollaron dos métodos: (1) el método de los pesos, y (2) el Método preventivo. Ambos métodos se basan
en la conversión de los múltiples objetivos en una sola función. La sec¬ción .2 proporciona los detalles.

CONJUNTO DE PROBLEMAS .1A

*1. Formule el problema fiscal de Fairville, suponiendo que el concejo municipal especifique una meta más,
G5, que requiera que el impuesto sobre la gasolina sea igual por lo menos a 10% de la factura fiscal total.
2. El Centro Comercial NW gestiona eventos especiales para atraer clientes potenciales. Entre los eventos que
parecen atraer a los adolescentes, al grupo de jóvenes de mediana edad y a los adultos mayores, los dos más
populares son los conciertos de bandas y las ex¬posiciones de arte. Sus costos por presentación son de $1500
y $3000, respectivamente. El presupuesto anual (estricto) total asignado a los dos eventos es de $15,000. El
gerente del centro comercial estima la asistencia como sigue:
Cantidad de personas que asisten por presentacion
Evento Adolescentes Media edad Adultos mayores
Concierto de bandas 200 100 0
Exposicion de arte 0 400 250
El gerente ha fijado metas mínimas de 1000, 1200 y 800 para la asistencia de adolescen¬tes, personas de
mediana edad y adultos mayores, en ese orden. Formule el problema como un modelo de programación de
metas.
*3. La oficina de admisión de la Universidad de Ozark está recibiendo solicitudes de estu¬diantes de primer
año para el año académico venidero. Las solicitudes caen dentro de tres categorías: estudiantes del estado, de
fuera del estado, e internacionales. Las relacio-
nes hombres-mujeres de los solicitantes del estado y de fuera del estado son 1:1 y 3:2; para estudiantes
internacionales, la relación correspondiente es de 8:1. La calificación en el Examen de Universidades
Americanas (ACT, por sus siglas en inglés) es un importan¬te factor en la aceptación de nuevos estudiantes.
Las estadísticas recopiladas por la uni¬versidad indican que las calificaciones promedio de estudiantes del
estado, fuera del esta¬do e internacionales, son de 27, 26 y 23, respectivamente. El comité de admisiones ha
establecido las siguientes metas deseables para lá nueva clase de primer año:
(a) Que la clase que empieza sea por lo menos de 1200 estudiantes.
(b) Que la calificación promedio de todos los solicitantes sea por lo menos de 25.
(c) Que los estudiantes internacionales constituyan por lo menos 10% de la clase.
(d) Que la relación mujeres-hombres sea por lo menos de 3:4. a
(e) Que los estudiantes de fuera del estado comprendan por lo menos 20% de la clase.
Formule el problema como un modelo de programación de metas.
*4. Las granjas Circle K consumen 3 toneladas diarias de un alimento especial, el cual está constituido por una
mezcla de piedra caliza (carbonato de calcio), maíz y soya, y que debe satisfacer los siguientes requisitos
nutricionales:
Calcio. Al menos 0.8%, pero no más de 1.2%.
Proteína. Por lo menos 22%.
Fibra. A lo sumo 5%.
La siguiente tabla muestra el contenido nutricional de los ingredientes alimenticios.
Ib por lb de ingrediente
Ingrediente Calcio Proteina Fibra
Piedra caliza .380 .00 .00
Maíz .001 .09 .02
Soya .002 .50 .08

Formule el problema como un modelo de programación de metas, y establezca su opi¬nión con respecto a la
aplicabilidad de la programación de metas a esta situación.
*5. Mantel produce un carruaje de juguete, cuyo ensamble final debe incluir cuatro ruedas y dos asientos. La
fábrica que produce las piezas trabaja tres turnos al día. La siguiente tabla proporciona las cantidades
producidas de cada pieza en los tres turnos.
Unidades producidas por carrera de producción
Unidades producidas por carrera de producciom
Turno Ruedas Asientos
1 500 300
2 600 280
3 640 360

Idealmente, la cantidad de ruedas producidas es el doble de la de asientos. Sin embargo, como las tasas de
producción varían de turno a turno, el balance exacto en la producción puede no ser posible. A Mantel le
interesa determinar la cantidad de corridas de produc¬ción en cada turno que minimice el desbalance en la
producción de las piezas. Las limita¬ciones de la capacidad restringen las corridas a entre 4 y 5 para el turno
1; 10 y 20 para el turno 2, y 3 y 5 para el turno 3.
Formule el problema como un modelo de programación de metas.
6. Camyo Manufacturing produce cuatro piezas que requieren el uso de un torno y un tala¬dro vertical. Las
dos máquinas operan 10 horas al día. La siguiente tabla proporciona el tiempo en minutos que se requiere por
pieza:

Tiempo de producción en min

Pieza Torno Taladro vertical

1 5 3
2 6 2
3 4 6
4 7 4

Se desea balancear las dos máquinas limitando la diferencia entre sus tiempos de opera¬ción totales a lo sumo
a 30 minutos. La demanda del mercado. de cada pieza es de al menos 10 unidades. Además, la cantidad de
unidades de la pieza 1 no puede exceder la de la pieza 2. Formule el problema como un modelo de
programación de metas.
7. Se fabrican dos productos en dos máquinas secuenciales. La siguiente tabla da los tiem¬pos de maquinado
en minutos por unidad para los dos productos.

Tiempo de maquinado en min

Máquina Producto 1 Producto 2
1 5 3
2 6 2
Las cuotas de producción diarias para los dos productos son de 80 y 60 unidades. Cada máquina opera 8 horas
al día, y si es necesario, aunque no deseable, puede utilizarse tiempo extra para satisfacer las cuotas de
producción. Formule el problema como un mo¬delo de programación de metas.

8. El hospital de Vista City planea la asignación de camas sobrantes (las que no estén ya ocupadas) para
estancias cortas, con 4 días de anticipación. Durante el periodo de planifi¬cación de 4 días, alrededor de 30,25
y 20 pacientes requerirán estancias de 1, 2 o 3 días, respectivamente. Las camas sobrantes durante el mismo
periodo se estiman en 20, 30, 30 y 30, respectivamente. Aplique la programación de metas para resolver el
problema de sobreadmisión y subadmisión en el hospital.
9. La familia Von Trapp planea irse a vivir a una nueva ciudad donde los dos padres han aceptado nuevos
trabajos. Al tratar de encontrar una ubicación ideal para su nuevo hogar, los Von Trapp enumeran las
siguientes metas:
(a) Debe estar lo más cerca posible al lugar de trabajo de la señora Vox]. Trapp (alrede¬dor de á de milla).
(b) Debe estar lo más lejos posible del ruido del'aeropuerto (mínimo a 10 millas).
(e) Debe estar razonablemente cerca de un centro comercial (a lo sumo a 1 milla).
El señor y la señora Von Trapp utilizan un sitio destacado en la ciudad como punto de referencia y localizan
las coordenadas (x,y) del lugar de trabajo, el aeropuerto y el centro comercial en (1,1), (20,15) y (4,7),
respectivamente (todas las distancias están en millas). Formule el problema como un modelo de programación
de metas. (Nota: Las res¬tricciones resultantes son no lineales.)
10. Análisis de regresión. En un experimento de laboratorio, suponga que yi es el resultado i-ésimo observado
(independiente) asociado con: las mediciones experimentales dependientes i= 1, 2,...,m; j = 1, n.
Se desea determinar una regresión lineal que encaje en estos datos. Sea bi, j = 0, n, los coeficientes de la
regresión. Se desea determi nar todas las bi de modo que la suma de las desviaciones absolutas entre los
resultados observados y los estimados sea mínima. Formule el problema como un modelo de pro-gramación
de metas.
11. Problema de Chebyshev. Una meta alterna para el modelo de regresión del problema 10. es minimizar
sobre bi el máximo de las desviaciones absolutas. Formule el problema como un modelo de programación de
metas.

2 ALGORITMOS DE PROGRAMACIÓN DE MET METASAS

Esta sección presenta dos algoritmos para resolver la programación de metas. Ambos métodos se basan en la
representación de múltiples metas por una sola función objeti¬vo. En el método de pesos, la función objetivo
única es la suma ponderada de las fun¬ciones que representan las metas del problema. El método preventivo
inicia priorizando las metas por orden de importancia. Luego, el modelo optimiza las metas de una en una en
el orden de prioridad de modo que no degrade una solución de más alta prioridad.
Por lo común, los dos métodos propuestos no presentan la misma solución. Ninguno de los métodos, sin
embargo, es superior al otro porque las dos técnicas pre¬suponen preferencias distintas en la toma de
decisiones.

2.1 Método de los pesos

Suponga que el modelo de programación de metas tiene n metas y que la meta i-ésima se da como
Minimizar Gi, i = 1, 2, ... , n
La función objetivo combinada utilizada en el método de pesos se define entonces como
Minimizar z = wiGi + w2G2 + • • • + wnGyi
Los parámetros wi, i = 1, 2,..., n son pesos positivos que reflejan las preferencias de la toma de decisiones con
respecto a la importancia relativa de cada meta. Por ejemplo, wi = 1, para todas las i, significa que todas las
metas tienen una misma importancia. La determinación de los valores específicos de estos pesos es subjetiva.
En realidad, los procedimientos analíticos aparentemente complejos, desarrollados en la literatura (vea, por
ejemplo, Cohon, 1978) aún están arraigadas en evaluaciones subjetivas.

Ejemplo 2-1
TopAd, una nueva agencia de publicidad con 10 empleados, firmó un contrato para promover un
• nuevo producto. La agencia puede hacer publicidad por radio y televisión. La siguiente tabla
proporciona la cantidad de personas alcanzadas diariamente por cada tipo de anuncio publicita-
rio, así cómo los requerimientos de costos y mano de obra. El contrato prohíbe a TopAd utilizar

Radio Televisión
Exposición (en millones de personas)/min 4 8
Costo (en miles de dólares)/min 8 24
Empleados asignados/min 1 2

más de 6 minutos de publicidad por radio. Además, los anuncios de radio y televisión tienen que llegar al
menos a 45 millones de personas. TopAd tiene una meta presupuestaria de $100,000 para el pro¬yecto.
¿Cuántos minutos de anuncios de radio y televisión debe utilizar TopAd?
Sean x1 y x2 los minutos asignados a los anuncio de radio y televisión. La formulación de la programación de
metas para el problema se da como
Minimizar Gí = s7 (Satisfacer la meta de exposición)
Minimizar GI =(Satisfacer la meta de presupuesto)
sujeto a
La gerencia de TopAd estima que la meta de exposición es dos veces más importante que la meta de
presupuesto. Por lo tanto, la función objetivo combinada se convierte en

El hecho de que el valor óptimo de z no sea cero indica que al menos una de las metas no se cumple.
Específicamente; si = 5 significa que la meta de exposición (de al menos 45 millones de perso¬nas) falla por 5
millones de personas. Por otra parte, la meta de presupuesto (de no exceder $100,000) no se viola porque s2 =
0.
Comentarios. La programación de metas busca sólo una solución eficiente, más que óptima, al problema. Por
ejemplo, la solución x1 = 6 y x2 = 2 produce la misma exposición (4 x 6 + 8 x 2) = 40 mi¬llones de personas)
pero cuesta menos (8 x 6 + 24 x 2) = $96,000). En esencia, lo que la programa¬ción de metas hace es hallar
una solución que satisfaga las metas del modelo sin tomar en cuenta la optimización. La falla de no hallar la
solución óptima levanta dudas sobre la viabilidad de la programación de metas como una técnica de
optimización (vea el ejemplo 2-3 para un tratamiento más amplio).

CONJUNTO DE PROBLEMAS .2A

*1. Considere el problema 1, conjunto .1a que se refiere a la situación tributaria de Fairville. Resuelva el
problema, suponiendo que las cinco metas tienen el mismo peso. ¿Satisface la so¬lución todas las metas?
2. En el problema 2, conjunto 1a, suponga que la meta de atraer personas de mediana edad es dos veces más
importante que la de las otras dos categorías (adolescentes y adultos mayores). Encuentre la solución asociada,
y verifique si todas las metas se han cumplido.
3. En la situación de la admisión a la Universidad de Ozark descrita en el problema 3, conjunto 1a suponga
que [Link] cumplir con el límite en el tamaño de la clase de estu¬diantes de primer año, pero los requisitos
restantes pueden tratarse como metas flexibles. Suponga, además, que la calificación del examen ACT es dos
veces más importante que cualquiera de las metas restantes.
(a) Resuelva el problema y especifique si se cumplen o no todas las metas.
(b) Si, además, el tamaño de la clase de estudiantes de primer año puede tratarse como una meta flexible
que es dos veces más importante que la meta del examen ACT, ¿cómo afectaría este cambio a la solución?
*4. En el modelo de Circle K del problema 4, conjunto 1a, ¿es posible satisfacer todos los requerimientos
nutricionales?
5. En el problema 5, conjunto 1a, determine la solución, y especifique si puede balancearse o no la producción
diaria de ruedas y asientos.
6. En el problema 6, conjunto 1a, suponga que la meta de la demanda del mercado es dos veces más
importante que la de balancear las dos máquinas, y que no se permite tiempo extra. Resuelva el problema, y
determine si se cumplen las metas.
*7. En el problema 7, conjunto 1a, suponga que la producción se esfuerza por satisfacer las cuotas de los dos
productos, utilizando tiempo extra si es necesario. Encuentre una solución al problema, y especifique la
cantidad de tiempo extra, si se requiere, para cumplir con las cuotas de producción.
8. En el hospital de Vista City del problema 8, conjunto 1a, suponga que solamente los límites de camas
representan metas flexibles y que todas las metas tienes pesos iguales. ¿Puede cumplirse con todas las metas?

9. La compañía Maleo ha recopilado la siguiente tabla de los archivos de cinco de sus em¬pleados, para
estudiar el impacto en el ingreso de tres factores: edad, educación (expresa¬da en años de universidad
terminados), y experiencia (expresada en años en los negocios).
Edad (años) Educación (años) Experiencia (años) Ingreso anual ($)
30 4 5 40,000
39 5 10 48,000
44 2 14 38,000
48 0 18 36,000
37 3 9 41,000

Aplique la formulación de programación de metas del problema 10, conjunto 1a, para encajar los datos en la
ecuación lineal y = b0 + bixi + b2x2 + b3x3.
10. Resuelva el problema 9 siguiendo el método de Chebyshev proptesto en el problema 11, conjunto 8.1a.

2.2 Método preventiv

preventivo
o
En este tipo de método, el tomador de decisiones clasifica las metas del problema en orden de importancia.
Dada una situación de n metas, los objetivos del problema se escriben como

Minimizar G1 = Pi (Máxima prioridad)

Minimizar G,, = p,, (Mínima proridad)

La variable pi es el componente de las variables de desviación, .s7- o s-T, que representan la meta i. Por
ejemplo, eh el modelo de TopAd (ejemplo 2-1), pi = siT y P2 =
El procedimiento de solución se inicia con la optimización de la prioridad máxi¬ma, G1, y termina con la
optimización de la prioridad mínima, Gn. El método preventi¬vo está diseñado de modo que una solución de
menor prioridad nunca degrade a una solución de alta prioridad.
La literatura sobre programación de metas presenta un método simplex "especial" que garantiza la no
degradación de soluciones de alta prioridad. El método utiliza la regla de eliminación de columnas que exige
eliminar una variable xj no básica con un costo re-ducido diferente de cero (zj – cj ≠ 0) de la tabla óptima de
metas Gk antes de resolver el problema de la meta Gk+1. La regla reconoce que tales variables no básicas, si
se elevan por encima del nivel cero en las optimización de metas subsiguientes, pueden degradar (pero nunca
mejorar) la calidad de una meta de mayor prioridad. El procedimiento re¬quiere incluir las funciones objetivo
de todas las metas en la tabla simplex del modelo.
La modificación propuesta de eliminación de columnas complica sin necesidad la programación de metas. En
esta presentación demostramos que se pueden alcanzar los mismos resultados de una manera más simple
dando los siguientes pasoS:
Paso O. Identifique las metas del modelo y clasifíquelas en orden de prioridad:

Establezca i = 1.
Paso general Resuelva la PL que minimice y que pi = p7 defina el valor óptimo
correspondiente de la variable de desviación pi. Si i = n, deténgase; la PL„ re-suelve el problema de n metas.
En caso contrario, agregue la restricción pi = pi a las restricciones del problema G para garantizar que el valor
de pi no se degrade en problemas futuros. Establezca i = i + 1, y repita el paso i.
La adición sucesiva de las restricciones especiales pi = p7 puede no ser tan "elegante" teóricamente como la
regla de eliminación de columnas; no obstante, se logra el mismo resultado. Pero lo más importante es que es
más fácil de implementar y de entender.
Comentarios. Algunas personas pueden argumentar que la regla de eliminación de columnas ofrece una
ventaja computacional porque hace el problema sucesivamente más pequeño al eliminar variables, en tanto
que nuestro procedimiento lo hace más grande al agregar nuevas restricciones. Considerando la naturaleza de
las restricciones adicionales (p = p7) , podemos modificar el algoritmo simplex para implementar la
restricción adicional implícitamente sustituyendo pi = . La sustitución (que afecta sólo a la restricción en la
que aparece pi) reduce el número de variables a medida que el algoritmo se mueve de una meta a la siguiente.
De otra manera, podemos utilizar el método simplex acotado, reemplazando pi = p7 con pi 5- p;-', en cuyo
caso las restricciones adicionales se toman en cuenta de manera tácita. Al respecto, la regla de eliminación de
columnas, aparte de su atractivo teórico no parece ofrecer una ventaja computacional particular. .,
Para completar el planteamiento, el ejemplo 2-3 ilustrará cómo funciona la regla de eliminación de columnas.
Ejemplo 2-2
El problema del ejemplo 2.1 se resuelve por el método preventivo. Suponga que la meta de exposición tiene la
prioridad más alta.
Paso O. G1>G2

Paso 1. Resuelva la PLi

La solución óptima (determinada por TORA) es x1 = 5 minutos, x2 = 2.5 minutos, si = 5 millones de

personas, con las variables restantes iguales a cero. La solución muestra que 5 millones de personas violan la
meta de exposición, G1. La restricción adicional que se añade al problema G2 es si = 5 (o, lo que es lo mismo,
si 5).
Paso 2. La función objetivo de la PL2 es
Minimizar G2 =
Las restricciones son las mismas que en el paso 1 más la restricción adicional si = 5. (Puede aplicarse la
opción MODIFY de TORA para representar la nueva restricción asignando 5 tanto a la cota inferior como a la
cota superior de si .)
Por lo general, la restricción adicional si = 5 también puede explicarse al sustituir en la primera restricciórÉ El
resultado es que el lado derecho de la restricción de la meta de exposición cambiará de 45 a 40, lo que reduce
la LP2 a

La nueva formulación tiene una variable menos que la de la PL 1, la cual es lá idea general anticipada por la regla
de eliminación de columnas.
En realidad, la optimización de la PL 2 no es necesaria en este problema porque la solución óptima al
problema G 1 ya da por resultado sl = 0; es decir, ya es óptima para la PL 2 . Tales oportunidades de ahorro de
cálculos deben aprovecharse siempre que se presenten durante el curso de implementación del método
preventivo.

E je
jemm pl
ploo2
2-3
-3 (R
(Reg
eg
egll a de el
elii mi
minn ac
ació
ió
iónnd
dee cco
o lu
lumm na
nass )
En este ejemplo demostramos que puede obtenerse una mejor solución para el problema de los ejemplos 8.2-1 y
8.2-2 si se utiliza el método preventivo para optimizar los objetivos en lugar de satisfacer las metas. Más adelante,
el mismo ejemplo se resuelve aplicando la regla de eliminación de columnas.
 Las metas del ejemplo 8.2-1 se puede formular como
Prioridad 1: Maximizar la exposición (P 1)

Prioridad 2: Minimizar el costo (P 2 )

Matemáticamente, los dos objetivos se dan como

Maximizar P 1 = 4x 1 + 8x 2 (Exposición)
Minimiz a r P 2 = 8 x 1 2 4 x 2 (Costo)
Los límites específicos para las metas de exposición y de costo (= 45 y 100) en los ejemplos 8.2-1 y 8.2-2 se
eliminan, porque dejaremos que el método simplex determine estos límites óptimamente.
Por lo tanto el nuevo problema se formula como
Maximizar P 1 = 4x 1 + 8x 2

M in imiz a r P 2 = 8 x 1 2 4 x 2

sujeto a
x 1 + 2x 2 ≤ 10
x1 ≤6

X1, X2 ≥ O

Primero resolvemos el problema siguiendo el procedimiento presentado en el ejemplo 8.2-2. Paso 1.

Resuelva la PL1.

Maximizar P 1 = 4x 1 + 8x 2

sujeto a
x 1 + 2x 2 ≤ 10
x1 ≤6

X1, X2 ≥ O
La solución óptima (obtenida por TORA) es x 1 = 0, x2 = 5 con P 1 = 40, lo que demuestra que la exposición
máxima que podemos obtener es de 40 millones de personas.
Paso 2. Agregue la restricción 4x 1 + 8x2 40 para asegurarnos de que la meta G 1 no se degrade. Por lo tanto,
resolvemos la PL 2 como
Minimizar P2 = 8x1 24x2
sujeto a

x1 + 2x, ≤ 10
xl ≤6
4x1 + 8x2 ≥ 40 (restricción adicional)
xl, X2 ≥O

La solución óptima de la PL 2 es P2 = $96,000, x 1 = 6 minutos, y x 2 = 2 minutos. Esto da por resultado la misma

exposición (P 1 = 40 millones de personas) pero a un costo menor que el del ejemplo 8.2-2, donde buscamos
satisfacer en lugar de optimizar las metas.
El mismo problema se resuelve ahora con la regla de eliminación de columnas. La regla indica que incluyamos las
filas objetivo asociadas con todas las metas en la tabla simplex, como se demostrará a continuación.
PL1 (Maximización de la exposición). La tabla simplex de la PL1 incluye ambas filas objetivo P1 y
P2. La condición de optimalidad aplica sólo a la fila objetivo P 1 . La fila P2 desempeña un rol
pasivo en la PL 1 , pero debe ser actualizada (mediante las operaciones de filas de simplex) con el
resto de la tabla simplex en preparación para la optimización de la PL 2.
La PL 1 se resuelve en dos iteraciones como sigue:
Iteración Básica X1 sl s2 Solución
1 Pi —8 0 0 0
—8 —24 0 0 0
sl 1 2 1 0 10
S2 1 0 0 1 6
2 PI 0 0 4 0 40
P2 4 0 12 0 120
x2 1 1 _ 0 5
2
S2 1 0 0 1 6

La última tabla da por resultado la solución óptima xi = 0, x2 = 5 y P i = 40.

La regla de eliminación de columnas pide que se eliminé cualquier variable no básica xi con z1
— 9 O a partir de la tabla óptima de la PL 1 antes de optimizar la PL 2. La razón es que si estas
variables no se verifican, podrían volverse positivas en problemas de optimización de baja prioridad,
las cuales pueden degradar la calidad de soluciones de alta prioridad.
PL2 (Minimización de costos). La regla de eliminación de columnas elimina s1 (con z1 — = 4 en la
PL1). En la fila P2 podemos ver que si no se elimina s 1 será la variable de entrada en el inicio de las
iteraciones P2 y el resultado será la solución óptima x 1 = x2 = O, la cual degradará el valor objetivo
óptimo del problema P1 desde P1 = 40 hasta Pi = O (i compruébelo!).

El problema P2 es del tipo de minimización. Después de la eliminación de s l, la variable x1 con z 1

— 9 = 4 (> 0) puede mejorar el valor de P 2 : La siguiente tabla muestra las iteraciones la PL2. Se
eliminó la fila P 1 porque no tiene ningún propósito en la optimización de la PL2

Iteración Básica x1 x2 s1 S2 Solución

1 Pi 40
P2 4 0 0 120
1 0 5
s2 1 0 1 6
2 P1 40
P2 0 0 —4 96
x2 0 1 —
5 2
x1 1 0 1 6

La solución óptima (x i = 6, x 2 = 2) con una exposición total de P 1 = 40 y un costo total de P9

= 96 es la misma que se obtuvo antes.

M o m ento de AM P L
AMPL se presta muchísimo para la aplicación de la idea presentada en el ejemplo 2-2, donde se agregan
restricciones simples para garantizar que las soluciones de alta prioridad no se degra den. El archivo amplEx..1 [Link]
-
 proporciona un código AMPL genérico que permite aplicar el método preventivo. El modelo debe
implementarse de manera interactiva como se explica en la sección C9 en el sitio web.

CO
CONJ
NJ
NJUN
UN
UNTO
TO D
DEE PRO
PROBL
BL
BLEM
EM
EMAS
AS 2
1. En el ejemplo 2-2, suponga que la meta de presupuesto se incrementa a $110,000. La meta de exposición
permanece en 45 millones de personas. Demuestre cómo determinará una solución el método preventivo.
*2. Resuelva el problema 1, conjunto 1a, utilizando el siguiente orden de las prioridades para las metas: G1 > G2 >
G3 > G4 > G5.
3. Considere el problema 2, conjunto 1a, que se refiere a la presentación de conciertos y exposiciones de arte en el
centro comercial NW. Suponga que las metas establecidas para adolescentes, el grupo de mediana edad y el de
adultos mayores se designan como G1, G7 y G3, respectivamente. Resuelva el problema para cada uno de los
siguientes órdenes de prioridad.
(a ) G i > G2 > G 3
(b) G3 > G2 > G1

2
Puede ver que es computacionalmente conveniente utilizar AMPL de manera interactiva para resolver los problemas de este
conjunto.

Demuestre que la satisfacción de las metas (o falta de ella) puede ser una funcuon del orden de las prioridades.

4. Resuelva el modelo de la univerdidad de Ozark (problema 3, conjunto .1ª) siguiendo ek método preventivo; a
reserva de que las metas se hayan priorizado en el mismo orden que se dio el problema.

BILBIOGRAFIA

Chissman, J., Fey, G. Reeves, H. Lewis y R. Weinstein “A multiobjetive Linear. Programming Metholodogy for
Public Sector Tax Planning”, interfaces, vol. 19, nún 5, pags 13-22, 1989.
Cohon T. L, Multiobjetive Programmin and Planning . Academic Press Nueva York, 1978.
Ignizio, J. P y T. M. Cavalier, Linear Programming. Academic Press, Nueva York, 1978.
Steuer, R.E., Multiple Criterio Optimization Theory, Computations, and Application, Wiler: Nueva York, 1986.