Libro Apoyo Cuantitativo
Libro Apoyo Cuantitativo
Libro Apoyo Cuantitativo
Apoyo Cuantitativo
a las Decisiones
Claudia E. Carignano
Sexta Edición
Catalina L. Alberto
ISBN: 978-987-3840-92-0
APOYO CUANTITATIVO
A LAS DECISIONES
SEXTA EDICIÓN
CLAUDIA CARIGNANO
CATALINA LUCÍA ALBERTO
Prólogo
Las autoras
Acerca de las autoras
CAPÍTULO 1 - INTRODUCCIÓN
1. Introducción 13
2. Breve historia de la Investigación Operativa 14
3. Los modelos utilizados en Investigación Operativa 16
4. Clasificación de los modelos 18
5. Limitaciones de los modelos matemáticos 19
6. Metodología científica 20
7. Diferentes tipos de Investigación Operativa 22
1. INTRODUCCIÓN
La evidente dificultad de tomar decisiones ha hecho que la humanidad se
aboque a la búsqueda de una herramienta o método que le permita tomar
las mejores decisiones de acuerdo con los recursos disponibles y los
objetivos que persigue. Si bien la experiencia e intuición resultan útiles
en muchas situaciones, cuando el problema a resolver es de naturaleza
compleja es conveniente recurrir a un proceso más racional que ayude a
tomar buenas decisiones.
Una decisión equivocada puede repercutir considerablemente en los
intereses y objetivos de una organización y, en ocasiones, pueden pasar
años para rectificar tal error. Cuando el problema es complejo, se requiere
que las decisiones sean eficientes, eficaces y que se tomen rápidamente,
pues el hecho de posponer una acción puede dar una desventaja decisiva
en el mundo de la competencia.
En muchas situaciones, por las características de los problemas a
resolver, se hace necesaria la participación de varias personas
especialistas, cuya visión multidisciplinaria facilitará el proceso de toma
de decisión.
En este contexto, la Investigación de Operaciones surge como una
metodología desarrollada para estudiar problemas de decisión de
naturaleza compleja. Su función es apoyar al tomador de decisiones
(quien está a cargo de la gerencia o de la administración, decisor),
proporcionándole información calificada para la formulación de políticas y
estrategias necesarias para la gestión.
DECISIÓN
TRADICIONAL RACIONAL
14 CAPÍTULO 1
Tabla 1
1
Simon señala que la mayoría de las personas son solo parcialmente racionales y que, de
hecho, actúan según impulsos emocionales no totalmente racionales en muchas de sus
acciones. Sostiene que la racionalidad personal está limitada por tres dimensiones: la
información disponible, la limitación cognoscitiva de la mente individual y el tiempo
disponible para tomar la decisión.
INTRODUCCIÓN 17
6. METODOLOGÍA CIENTÍFICA
El enfoque de la IO sigue las pautas del método científico. En particular,
el proceso comienza por la observación cuidadosa y la formulación del
problema y sigue con la construcción de un modelo científico que intenta
abstraer la esencia del problema real. En este punto, se propone la
hipótesis de que el modelo es una representación lo suficientemente
precisa de las características esenciales de la situación como para que la
solución obtenida sea válida también para el problema real. Esta hipótesis
se verifica y modifica mediante las pruebas adecuadas. Entonces, en
cierto modo, la Investigación Operativa incluye la investigación científica
creativa de las propiedades fundamentales de las operaciones.
El investigador operativo se ocupa además de la administración práctica
de la organización. Así, para tener éxito, deberá también proporcionar
conclusiones positivas y claras que pueda usar el tomador de decisiones
cuando las necesite.
• Programación Lineal
• Transporte y
Asignación
• Programación Lineal
Optimización Entera
• Flujo en Redes
Lineal • Programación
DETERMINÍSTICOS Multiobjetivo
• Análisis de Decisión
ESTOCÁSTICOS • Procesos Estocásticos
• Teoría de Fenómenos de espera en
fila
Gráfico 1
24 CAPÍTULO 1
análisis y relevamiento
de información
ESTRUCTURACIÓN
DEL PROBLEMA
Parámetros
Variables
MODELO
MATEMÁTICO
relaciones
técnica operacional
VALIDACIÓN
IMPLEMENTACIÓN
SEGUIMENTO y
CONTROL
Gráfico 2
CAPÍTULO 2
EL PROCESO DE DECISIÓN
1. INTRODUCCIÓN
En este capítulo, trataremos de dar una caracterización general de los
problemas de decisión, la cual nos resultará de utilidad al momento de
analizar los diferentes modelos a estudiar en este texto.
Básicamente, un proceso de toma decisión se presenta cuando, frente a
un problema, existe más de una alternativa o curso de acción posible.
En todo proceso de decisión intervienen dos actores, aunque en algunos
casos la misma persona asume los dos roles:
Decisor: es quien tiene el poder y la responsabilidad de ratificar
una decisión y asumir sus consecuencias.
Analista: es el encargado de estructurar el problema y ayudar al
decisor a visualizarlo.
Frente a un problema de decisión, consideramos conocido el conjunto de
las alternativas posibles, al que denominaremos X. Supondremos que este
conjunto está formado por un número finito de elementos, a los cuales
genéricamente llamaremos xi, es decir, X={x1, x2, ……, xn},
siendo n el número de alternativas de decisión.
Conocido este conjunto X, intentaremos establecer una relación entre los
elementos del conjunto, de forma tal que para cualquier par de elementos
podremos decir si uno es preferible o indiferente al otro.
Así para, x1X x2X, podemos establecer que x1 es preferible a x2:
x1 x2
Máx d(x)
Mín d(x)
2. DECISIÓN Y UNIVERSO
En un problema de decisión, a menudo los resultados que se obtienen al
seleccionar una alternativa se ven condicionados por la presentación de
ciertos sucesos que no dependen del tomador de decisiones. Llamaremos
a este conjunto de sucesos “estados de la naturaleza”.
Los estados naturales representan variables exógenas cuya presentación
modifica los resultados de la acción seleccionada.
Representaremos los estados de la naturaleza mediante el conjunto Y,
siendo:
Y = {y1, y2, ……, ym}
y1 y2 .. .. ym
x1 c(x1,y1) c(x1,y2) .. .. c(x1,ym)
x2 c(x2,y1) c(x2,y2) .. .. c(x2,ym)
x3 c(x3,y1) c(x3,y2) .. .. c(x3,ym)
. . . .. .. .
xn c(xn,y1) c(xn,y2) c(xn,ym)
Tabla 1
EL PROCESO DE DECISIÓN 27
y1 y2 . . . . ym
x1 c11 c12 . . . . c1m
x2 c21 c22 . . . . c2m
x3 c31 c32 . . . . c3m
. . . . . . . .
xn cn1 cn2 cnm
Tabla 2
0 150
0
✓ La segunda crítica se refiere a que el valor de la Esperanza
Matemática se vuelve significativo solamente cuando la decisión se repite
un número grande de veces. Por el contrario, si la decisión debe tomarse
por única vez, el criterio debe aplicarse con cautela, ya que podría
conducir a una elección equivocada.
y1 y2 y3
x1 150 110 100
x2 125 95 300
x3 120 130 250
Pj 0.3 0.5 0.2
Tabla 3
y1 y2 y3 C(xi,yj) pj
x1 150 110 100 150 (0.3) + 110 (0.5) + 100 (0.2) = 120
x2 125 95 300 125 (0.3) + 95 (0.5) + 300 (0.2) = 145
x3 120 130 250 120 (0.3) + 130 (0.5) + 250 (0.2) = 151
Pj 0.3 0.5 0.2
Tabla 4
x3 10 13 20 35 35
Tabla 6
01
Beneficios → d(x) =
y ( )
max c xi,y j + (1- ) min c xi,y j
y ( )
y i j ( )
Costos → d(x) = min c x ,y + (1- ) max c x ,y
y i j ( )
La decisión óptima se obtiene calculando:
x y
( )
Beneficios → max d(x) = max max c x ,y +(1- ) min c x ,y
i j y i j ( )
Costos →
x y
i j ( )
min d(x) = min min c x ,y + (1- ) max c x ,y
y i j ( )
APLICACIÓN PARA UN CASO DE BENEFICIOS (= 0,50)
Se sugiere aplicar
este criterio y1 y2 y3 Máx c (x,y) + (1-) Mín c (x,y)
haciendo variar los
x1 150 110 100 (0.50) 150 + (0.50) 100 = 125
valores de y
luego analizar los x2 125 95 300 (0.50) 300 + (0.50) 95 = 197,5
resultados. x3 120 130 250 (0.50) 250 + (0.50) 120 = 185
Tabla 8
x3 120 130 250 (0.50) 250 + (0.50) 120 = 185 120 250
Tabla 10
400 400
350 350
300 x 2 300
250 250
200 x 3 200
150 150
100 x1 100
0 α = 0 ,3 3 34 1
Es decir:
Beneficios r(xi,yj) = max c(xi,yj) – c(xi,yj)
x
1
Regret en inglés.
EL PROCESO DE DECISIÓN 35
Matriz R
y1 y2 y3 Max r(xi,yj) Para obtener la
matriz R se debe
x1 0 20 200 200
trabajar sobre las
x2 25 35 0 35 columnas de la
x3 30 0 50 50 matriz de
compensaciones.
Tabla 12
Observe que la
Matriz R decisión óptima,
y1 y2 y3 Max r (xi,yj) independientemente
del tipo de
x1 0 8 5 8 compensación
x2 5 0 10 10 (beneficios o costos),
siempre se obtiene
x3 0 3 0 3 aplicando mínimax.
Tabla 14
(
Beneficios → max d(x) = max E c x, y
x y
)
y1 y2 y3 (1/m) cij
x1 150 110 100 (1/3) 360 = 120
x2 125 95 300 (1/3) 520 = 173,33
x3 120 130 250 (1/3) 500 = 166.66
Tabla 15
6. ÁRBOLES DE DECISIÓN
Esta técnica es útil para resolver determinados problemas de decisión
bajo condiciones de riesgo. Un árbol de decisión es una forma gráfica y
analítica de representar todos los eventos (sucesos) que pueden surgir a
partir de una decisión asumida en cierto momento. Permite desplegar
visualmente un problema y organizar el trabajo de cálculos que deben
realizarse, y ayuda a tomar la mejor decisión desde un punto de vista
probabilístico ante un abanico de posibles decisiones.
Tiene la característica de que se elige todo un plan de acciones sucesivas
a lo largo del tiempo, en el que, en cada una de las etapas o puntos de
decisión, se tienen diferentes alternativas y cada una de estas tiene
eventos asociados con probabilidades concretas.
Elegir la mejor alternativa consiste en elegir la decisión de mayor valor
ponderado, en el caso de representar beneficios, a lo largo de una ruta
de decisiones adyacentes, como producir o comercializar, construir o
ampliar una planta, elegir entre diferentes proyectos de inversión,
etcétera.
Debemos mencionar, sin embargo, que visualizar eventos futuros
asociados a decisiones presentes es una cuestión sumamente compleja,
más aún cuando una decisión involucra muchas alternativas de decisión
en el tiempo.
EL PROCESO DE DECISIÓN 37
CONCEPTOS BÁSICOS
• Nodo de decisión: Indica la necesidad de tomar una decisión en ese
momento del proceso. Se representa por un cuadrado.
1. Definir el problema.
2. Dibujar el árbol de decisión.
3. Asignar probabilidades a los eventos aleatorios.
4. Estimar los resultados para cada combinación posible de
alternativas.
5. Resolver el problema obteniendo como solución la ruta que
proporcione la política óptima.
cada uno de los jugadores. Para analizarlos, los juegos se clasifican por
el número de jugadores, por la suma algebraica de todos los pagos y por
el número de estrategias o acciones posibles.
En este apartado, presentaremos un caso particular de juegos conocidos
como de “dos jugadores y suma cero”, esto significa que todo lo que
pierde o gana un jugador lo gana o pierde el otro respectivamente.
Se asume siempre que ambos jugadores son igualmente inteligentes y
racionales y que cada decisión de un jugador es efectuada con total
desconocimiento de la jugada que efectúa el oponente.
En estas circunstancias, será totalmente racional que cada jugador elija
una estrategia del tipo de las presentadas por el criterio pesimista,
extrayendo las peores consecuencias de cada decisión y eligiendo de entre
todas ellas a la mejor.
La matriz de compensaciones, que ahora se llama matriz de pagos, se
obtiene considerando al decisor como si fuera un jugador (jugador I), con
todas sus alternativas, y el universo fuera reemplazado por el oponente
(jugador II), representando a lo que antes eran los estados de la
naturaleza con las alternativas de este último. La matriz de pagos se
construye de forma tal que los pagos representan las ganancias del
jugador I (cuyas alternativas corresponden a filas) y consiguientemente
las pérdidas del oponente o jugador II (cuyas alternativas corresponden
a columnas).
I II
GANANCIAS PERDIDAS
MATRIZ
DE PAGOS
Para resolver este problema, parece lógico pensar que el jugador I elegirá Observar que esta
el máximo de los mínimos (criterio maximin) y el jugador II elegirá el forma de resolver el
problema equivale a
mínimo de los máximos (criterio minimax). aplicar el criterio de
Wald para ganancias
Si la elección hecha por ambos jugadores recae en el mismo par (x,y), para el jugador I y
diremos que el juego tiene punto de equilibrio, es decir que ambos para pérdidas para el
jugador II
jugadores elegirán su estrategia más conveniente y esta dará como
resultado el pago que recibirá el jugador I (que también podrá ser una
pérdida y entonces llevará signo negativo) por parte de su oponente (que
será ganancia para este si lleva signo menos). En este caso, al valor del
pago, ubicado en la intersección de la fila maximin y la columna minimax,
se lo designa “valor del juego” (V), porque si ninguno comete un error
siempre el juego se resolverá de esa forma, ya que le garantiza al jugador
I tener como mínimo ese beneficio (mayor si su oponente se equivoca) y
40 CAPÍTULO 2
Por lo tanto, el juego posee punto de silla y el valor del juego (V) = 10.
Decimos que a cada jugador le conviene jugar una estrategia única, que
justamente es la indicada por el criterio de Wald aplicado a ambos
jugadores. Cuando el juego se resuelve con una estrategia única se lo
denomina “juego con estrategia pura óptima”.
Ahora bien, no todos los juegos tienen estrategia pura óptima. En ese
caso, no hay un razonamiento válido que haga que cada jugador prefiera
una alternativa frente a otras, dado que cada uno puede inferir la jugada
del otro y cambiar en consecuencia y lo mismo puede hacer el contrario,
lo que lleva a cada uno a un círculo vicioso que le impide seleccionar
racionalmente una estrategia. Veamos un ejemplo:
EL PROCESO DE DECISIÓN 41
BI B II B III B IV
AI -12 19 4 0 -12
A II 8 -2 5 7 -2
DECISIONES DE A
A III 16 15 18 42 15
A IV -12 53 2 -26 -26
Observemos que:
0 pi 1 0 qj 1
n n n
max min ci1 pi , ci 2 pi ,...., cim pi
x
i =1 i =1 i =1
p1 + p2 +......+ pn =1
pi 0, i = 1, 2,..., n
c
i =1
ij pi v, j = 1, 2, ..., m
Max( z ) = v
sujeta a
n
v − cij pi 0
i =1
p1 +p2 +......+pn =1
pi 0, i = 1, 2,..., n
v sin restric.
Min( g ) = v
sujeta a
m
v − cij q j 0
j =1
q1 +q2 +......+qm =1
q j 0, j = 1, 2,..., m
v sin restric.
El problema (4) es el dual de (3), razón por la cual ambos problemas
optimizan la variable sin restricción v (valor del juego).
Ejemplo de aplicación
Para el ejemplo de la tabla 17, el modelo lineal que permite obtener las
probabilidades óptimas del jugador A es el siguiente:
Max (z) = v
Sujeta a
v + 12 p1 - 8 p2 - 16 p3 + 12 p4 ≤ 0
v - 19 p1 + 2 p2 - 15 p3 - 53 p4 ≤ 0
v - 4 p1 - 5 p2 - 18 p3 - 2 p4 ≤ 0
v - 7 p2 - 42 p3 + 26 p4 ≤ 0
p1 + p2 + p3 + p4 = 1
p1, p2 , p3 , p4 ≥ 0
v sin restricción de signo
La solución óptima es
p1 = 0
p2 = 0
p3 = 0,9848
p4 = 0,0152
v = 15,578
El programa lineal del jugador B es:
Min (g) = v
Sujeta a
v + 12 q1 - 19 q2 - 4 q3 ≥0
v - 8 q1 + 2 q2 - 5 q3 - 7 q4 ≥ 0
v - 16q1 - 15 q2 - 18 q3 - 42 q4 ≥ 0
v + 12q1 - 53 q2 - 42 q3 + 26 q4 ≥ 0
q1 + q2 + q3 + q4 = 1
q1, q2 , q3 , q4 ≥ 0; v sin restricción de signo
44 CAPÍTULO 2
A B PI PA TI
PI 0 -1 1
PA 1 0 -1
TI -1 1 0
Tabla 19
Tabla 20
Tabla 21
EL PROCESO DE DECISIÓN 45
Por lo tanto, A debe elegir una estrategia tal que el mínimo de sus valores
esperados sea el máximo posible. Si llamamos v a ese valor máximo
posible, entonces este debe ser tal que cumpla con:
v ≤ p2 – p3
v ≤ -p1+ p3
v ≤ p1 - p2
Con todo lo anterior, A puede plantear un PL para averiguar cuál es ese
máximo valor posible de v, considerando también que como p 1, p2 y p3
representan probabilidades, entonces su suma debe ser igual a 1.
Quedando el PL:
Max v
sa Resolviendo el programa:
v ≤ p2 – p3 v = $1,00
p1 = 1/3
v ≤ -p1+ p3
p2 = 1/3
v ≤ p1 - p2 p3 = 1/3
p 1 + p2 + p3 = 1
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
RESPONDA SI LAS SIGUIENTES AFIRMACIONES SON VERDADERAS O FALSAS:
A) Se puede considerar que el criterio de Wald es un caso particular del
criterio de Hurwicz.
ACTIVIDAD 2
RESPONDA LAS SIGUIENTES PREGUNTAS:
a) En una matriz de resultados de un problema de decisión, ¿qué
representan los cij?
ACTIVIDAD 3
Un inversionista posee un capital que asciende a $400.000. Tiene tres
alternativas de inversión que llamaremos A, B y C.
La alternativa A es invertir el 100 % del capital, la alternativa B es invertir
el 40 % del capital, mientras que la C propone invertir el 30 % del mismo.
El rendimiento de la inversión A será del 10 %, la de B rendirá el 11 % y la
de C el 17 %.
En el caso de B y C, al saldo no invertido lo guardará en el banco, que le
proporcionará un interés que se fijará al finalizar el período, según la
situación económica que se presente, la que podrá ser de gran inflación,
recesión o prosperidad económica. El interés anual que abonará el banco en
cada situación económica será del 10 %, 7 % y 5 % respectivamente.
¿Qué alternativa deberá elegir el inversionista si:
a) utiliza el criterio de Wald?
EL PROCESO DE DECISIÓN 47
ACTIVIDAD 4
La florería Claveles S.A. debe decidir cuántas orquídeas ordenar para el
Día de la Secretaria. La demanda de este tipo de flores en los días
especiales, como el de la Secretaria o el de la Madre, es una variable
aleatoria (D). El costo de cada flor es de $10 si se las compra con
anterioridad al Día de la Secretaria. Si la demanda excede el número de
flores disponibles, el faltante se satisface colocando una orden urgente.
En este caso, el costo de cada flor será $5 más caro que el costo normal.
Si la demanda es menor que el inventario que se tiene, las flores que
sobran se pueden vender con posterioridad. El precio de venta de las
flores que sobren será de $3 menos que su costo original, ya que no se
encontrarán igualmente frescas.
Se realizó un estudio sobre 100 días festivos y se registraron las
siguientes observaciones:
Demanda 10 15 20 25 30
Nº de días en que se produjo 10 25 30 20 15
ACTIVIDAD 5
Un pequeño supermercado pide semanalmente un tipo especial de yogurt
con cereales y vitaminas. El encargado de compras ha observado que las
posibles demandas son: 100, 200 o 300 unidades. El producto cuesta $0,8
cada uno y se vende a $1,25 la unidad. Los que sobran al final de la
semana se pueden devolver, obteniéndose un reintegro de $0,60 por cada
uno. Si durante la semana le faltan productos, puede solicitarlos al
proveedor en carácter de pedido urgente con un recargo de 10 %
ACTIVIDAD 6
Juan Rodríguez afirma haberse lesionado la espalda como resultado de
una caída cuando reparaba el techo de uno de los edificios de
departamentos de la constructora Márquez & Co. Juan entabló una
demanda contra Márquez, solicitando una indemnización por daños: él
afirma que el techo tenía secciones destruidas y su caída podría haberse
evitado si se lo hubiesen comunicado.
Márquez notificó a su compañía de seguros (Segurance) del accidente. Se
tomaron algunas declaraciones y ha tenido lugar una serie de reuniones
entre ambas partes. Como resultado de estas reuniones, Segurance le
propone un arreglo extrajudicial con una oferta de $500.000. Juan puede
aceptar el arreglo y, en ese caso, se da por concluido el conflicto; o iniciar
un juicio contra Márquez & Co.
En el caso de que Juan gane el juicio, puede obtener $400.000, $800.000
o $1.700.000 dependiendo de los fundamentos que la justicia considere
aceptables.
Sin embargo, si Juan pierde el juicio, como él deberá pagar costas y
accesorios, tendrá un costo de $50.000.
Ayude a Juan a tomar la decisión más adecuada, sabiendo que el 30 %
de los juicios se pierden y el 70 % se ganan; y de estos, en el 50 % se
obtiene la menor indemnización, en el 30 % la intermedia y en el 20 %
la más alta.
ACTIVIDAD 7
Un gerente está tratando de decidir si debe comprar una máquina o dos.
Si compra solo una y la demanda resulta ser excesiva, podría adquirir
después la segunda máquina. Sin embargo, perdería algunas ventas
porque el tiempo que implica la fabricación de este tipo de máquinas es
de seis meses. Además, el costo por máquina sería más bajo si comprara
las dos al mismo tiempo. La probabilidad de que la demanda sea baja se
ha estimado en 0,30. El valor presente neto, después de impuestos, de
los beneficios derivados de comprar las dos máquinas a la vez es de
$90.000 si la demanda es baja, y de $170.000 si la demanda es alta.
Si se decide comprar una máquina y la demanda resulta ser baja, el valor
presente neto sería de $120.000. Si la demanda es alta, el gerente tendrá
tres opciones: la de no hacer nada tiene un valor presente neto de
$120.000; la opción de subcontratar, $140.000; y la de comprar la
segunda máquina, $130.000.
a. Dibuje un árbol de decisiones para este problema.
b. ¿Cuántas máquinas debe comprar la compañía inicialmente? ¿Cuál
es el beneficio esperado de esta alternativa?
EL PROCESO DE DECISIÓN 49
ACTIVIDAD 8
Dos importantes cadenas de supermercados se disputan una franja del
mercado. Para captar a los clientes de esta franja, cada supermercado ha
pensado en una estrategia diferente. De esta manera, los clientes que
logre atraer uno de ellos los pierde el otro supermercado.
El supermercado I ha elaborado las siguientes estrategias alternativas:
▪ Otorgar una tarjeta para que los clientes puedan sumar puntos con sus
compras, los que luego podrán canjear por regalos según los puntos
acumulados. A esta la llamaremos estrategia A.
▪ Otorgar una tarjeta para que los clientes puedan sumar puntos con sus
compras, los que luego podrán aplicar en compras futuras como
descuentos. A esta la llamaremos estrategia B.
Las estrategias del supermercado II son:
▪ Otorgar una tarjeta que le permite a los clientes obtener un descuento
sobre productos no perecederos. A esta la llamaremos estrategia 1.
▪ Otorgar una tarjeta que le permite a los clientes obtener un descuento
sobre productos perecederos. A esta la llamaremos estrategia 2.
Cada uno desea elevar al máximo su número de clientes atraídos.
Mediante la teoría de juegos, determine la estrategia óptima para cada
supermercado y el valor del juego.
SUPERMERCADO II
SUPERMERCADO I ESTRATEGIA 1 ESTRATEGIA 2
ESTRATEGIA A 20000 20000
ESTRATEGIA B 30000 25000
ACTIVIDAD 9
Una pizzería está planificando su actividad para el próximo domingo. En
función de los datos que se reflejan en la siguiente tabla (beneficios
obtenidos), realizar el árbol de decisión correspondiente y, en función de
este, probar que la decisión más adecuada es hornear 170 pizzas.
1. INTRODUCCIÓN
Debido a que la esencia de la programación lineal (PL) puede
transmitirse mejor a través de un modelo concreto, comenzamos el
análisis de este tema mediante un ejemplo: una fábrica de cerámicos
quiere determinar el plan de producción óptimo de sus dos productos,
cerámicos esmaltados y cerámicos rústicos.
El proceso de producción de los cerámicos requiere diferentes
combinaciones de horas de mano de obra, horas de secado y de cocción.
Para la fabricación de un m2 de cerámico esmaltado, son necesarias 5
horas de mano de obra, 4 horas de secado y 6 horas de cocción.
Mientras, por cada m2 de cerámico rústico, se requieren 5 horas de
mano de obra, 8 horas de secado y 4 horas de cocción.
La contribución a las utilidades por cada m 2 de cerámico es: $8 para el
cerámico esmaltado y $6 para el cerámico rústico.
Teniendo en cuenta que la fábrica dispone de 300 horas de mano de
obra, 400 horas para secado y 320 horas para cocción por mes, formule
un modelo que le permita a la fábrica determinar el plan de producción
que maximice la contribución a las utilidades.
Disponibilidad
Cerámico Cerámico
horas
Esmaltado Rústico
mensuales
Horas de mano de obra / m2 5 5 300
Horas de secado / m 2
4 8 400
Horas de cocción / m2 6 4 320
Contribución a las utilidades / m 2
8 6
Tabla 1
Restricciones:
- La cantidad de horas de mano de obra a utilizar mensualmente no
debe superar las 300.
- La cantidad de horas de secado a utilizar mensualmente no debe
superar las 400.
- La cantidad de horas de cocción a utilizar mensualmente no debe
superar las 320.
MODELO MATEMÁTICO
$ Max z = 8 x1 + 6 x2
m2
2 sa
m
5 x1 + 5 x2 300 Hs de M O
Sujeto a: 4 x1 + 8 x2 400 Hs de Secado
5 x1 + 5 x2 300 HMO 6 x1 + 4 x2 320 Hs de Cocción
x1 y x2 0
hsMO
2
m2
hsMO
m
4 x1 + 8 x2 400 H Secado
6 x1 + 4 x2 320 H Cocción
x1 , x 2 0
x1 , x2 ,S1 ,S2 y S3 0
Siendo:
S1= cantidad de sobrante de horas de mano de obra
S2= cantidad de sobrante de horas de secado
S3= cantidad de sobrante de horas de cocción
54 CAPÍTULO 3
FORMA EXPLÍCITA
Maximizar Z = c1 x1 + c2 x2 + c3 x3 + ... + cn xn
Sujetas las xj a:
a11 x1 + a12 x2 + a13 x3 + ... + a1n xn b1
a21 x1 + a22 x2 + a23 x3 + ... + a2n xn b2
. . . . .
am1 x1 + am2 x2 + am3 x3 +… + amn xn bm
xj 0 (j = 1, 2, …, n)
Donde:
xj son las variables de decisión del modelo.
cj son parámetros que preceden a las variables en la función objetivo
(FO) y generalmente representan beneficios, ingresos o costos
unitarios, los que pueden ser monetarios o no.
aij (i=1, 2, …, m) son parámetros que representan coeficientes
técnicos en las restricciones.
bi son los términos independientes de las restricciones. Estos
parámetros generalmente representan disponibilidades de insumos o
requerimientos necesarios.
FORMA MATRICIAL
Maximizar Z = CX
AX B
X
1
En el anexo 1 se caracteriza un modelo de programación matemática.
PROGRAMACIÓN LINEAL 55
donde:
C = es un vector fila de orden 1xn
X = es un vector columna de orden nx1
A = matriz de orden mxn
B = es un vector columna de orden mx1
x1
a11 a12
... a1n
b
1
X
x2 C = c1, c2 , ...., cn a21 a22
A=
... a
2n
B=
b 2
...
=
.
... ... ... ...
am1 am2 ... amn b m
xn
FORMA VECTORIAL
Máx ∑nj=1 cj xj
Máx. CX a1j b1
s.a a b
2j 2
n Pj = . P0 = B = .
Pj xj = P0 . .
j=1
b
x j 0, j amj m
Maximizar CX Minimizar CX
AX = B AX = B
X X
Maximizar CX Minimizar CX
AX [ , =, ] B AX [ , =, ] B
X X
90
80
75
70
x2 65
55
50
5 x1 + 5 x2 300
45
40
35
30
25
20
15
10
x
0
x1
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 1 90 95 100
95
85
80
las restricciones. 75
70
x2 65
60 Payoff: 3.0 x1 + 6.0 x2 = 1135.7
55
50
45 5 x1 + 5 x2 300
40
35 4 x1 + 8 x2 400
30
25
20
15
10
xx11
0
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
Gráfico 3
2
Esto se logra reemplazando en la inecuación a x1 y x2 por las coordenadas de un punto,
como por ejemplo el (0, 0).
58 CAPÍTULO 3
z 8
x2 = − x1
6 6
Es aconsejable darle
a z un valor arbitrario
para poder dibujarla.
Gráfico 4
Analice cuál es el
sentido de optimidad
si el objetivo fuera:
max z = 8x1 – 6x2
Gráfico 5
6 x1 + 4 x2 = 320
5 x1 + 5 x2 = 300
Solución óptima:
x1 = 40 m2
x2 = 20 m2
PROGRAMACIÓN LINEAL 59
Horas de
4(40) + 8(20) = 320 400 80 No limitante
secado
Horas de
6(40) + 4(20) = 320 320 0 Limitante
cocción
Tabla 2
UN PROBLEMA DE MINIMIZACIÓN
El dueño de una pequeña tienda de mascotas prepara una mezcla
especial de comida para los perros que tiene en guardería durante el fin
de semana combinando dos alimentos, a los que llamaremos I y II.
El veterinario ha sugerido que la grasa contenida en la mezcla no debe
superar los 300 gramos y que, por lo menos, debe tener 40 unidades de
vitamina A.
El alimento I contiene 10 g de grasa y 4 unidades de vitamina A por
cada kg, mientras que el II contiene 20 g de grasa y 3 unidades de
vitamina A por kg. También aconsejó incluir en la mezcla por lo menos 3
kg de alimento II.
Además de lo indicado por el veterinario, debe tener en cuenta que del
alimento I solamente puede conseguir hasta 8 kg por semana y que,
debido a la cantidad promedio de perros en la guardería, necesita por lo
menos 12 kg de mezcla por fin de semana.
El costo del alimento I es de $5 por kg y el del alimento II es de $7 por
kg.
Para modelizar este problema, debemos identificar el objetivo, definir
las variables y enunciar las restricciones en forma verbal.
Variables:
x1 = kg de alimento tipo I a incluir en la mezcla
x2 = kg de alimento tipo II a incluir en la mezcla
Restricciones:
- El contenido máximo de grasa en la mezcla no debe superar los
300 g.
- La mezcla debe contener por lo menos 40 unidades de vitamina A.
- Se pueden conseguir hasta 8 kg. de alimento I por semana.
- La mezcla debe contener por lo menos 3 kg. del alimento II.
- Se necesitan por lo menos 12 kg. de mezcla por fin de semana.
- Las variables no pueden asumir valores negativos.
Gráfico 6
Gráfico 7
62 CAPÍTULO 3
x1 8
x1 + x2 12
Con ellas, planteamos un sistema de dos ecuaciones que nos permitirán
determinar los valores de las variables de decisión.
A continuación, se encuentran los valores de las variables de
holgura/excedente reemplazando a las variables de decisión por sus
respectivos valores en las restricciones.
La solución completa es:
VARIABLE VALOR
x1 8
x2 4
S1 140
S2 4
S3 0
S4 1
S5 0
4. CONCEPTOS BÁSICOS
A continuación, enunciaremos algunos conceptos necesarios para
continuar con el desarrollo de este capítulo.
Combinación lineal convexa de vectores: es una combinación lineal
convexa de r vectores V1, V2, ..., Vr es otro vector V, tal que:
r
Con la condición de que los i 0 y αi = 1 , para i= 1, 2, ..., r
i=1
PROGRAMACIÓN LINEAL 63
V1
V2
x1
Gráfico 8
NO DEGENERADA DEGENERADA
Exactamente m xi > 0 Menos de m xi > 0
Gráfico 9
TEOREMA 1
Este teorema se enuncia como: “Toda combinación lineal convexa de
soluciones factibles de un programa lineal es otra solución factible de
dicho programa”.
Para demostrarlo, partimos de un PL estándar matricial:
66 CAPÍTULO 3
Maximizar CX
AX = B
X
Sean X1, X2, ..., Xr, r vectores soluciones del PL, por lo tanto, se
verificará:
AX1 =B
AX2 =B
...... (1)
AXr =B
αi ≥ 0 y ∑ αi = 1
i=1
tendremos:
1 A X1 = 1 B
2 A X2 = 2 B
......... (2)
r A Xr = r B
∑ αi A Xi = ∑ αi B
i=1 i=1
r r
A ∑ αi Xi = B ∑ αi
i=1 i=1
Siendo,
r
∑ αi = 1
i=1
∑ αi Xi = Xk
i=1
TEOREMA 2
“Si existe más de una solución factible que le den el mismo valor a la
función objetivo, cualquier combinación lineal convexa de las mismas
dará al funcional igual valor”.
La demostración de este teorema es similar al anterior. Partimos de un
PL en forma estándar matricial:
Maximizar CX
AX = B
X
Sean X1, X2, Xr, r vectores soluciones del PL que dan a la función
objetivo igual valor, por lo tanto, se verificará:
CX1 = Z0
CX2 = Z0
. .. .. (3)
CXr = Z0
Si multiplicamos miembro a miembro las ecuaciones del sistema (3) por
escalares 1; 2, ..., r respectivamente, con la condición de que
r
i 0 y, i = 1 i= 1, 2, ..., r,
i=1
tendremos:
1CX1 = 1 Z0
2CX2 = 2Z0 (4)
. . .
r CXr = r Z0
r r
αiC Xi = i=1
i=1
αi Z0
de donde,
r r
C αi Xi = Z0 αi
i=1 i=1
Como,
r
i = 1
i=1
TEOREMA 3
“Si un PL es resoluble –es decir, que posee óptimo–, existirá siempre
por lo menos una solución factible básica que también sea óptima” 3.
7. MÉTODO SIMPLEX
Este método, desarrollado por George Dantzig en 1947, permite
encontrar la solución óptima de cualquier programa lineal, cualquiera
sea el número de variables y ecuaciones que lo forman, e identificar
aquellos problemas que no tienen solución, o cuya solución óptima es no
acotada4.
El algoritmo parte de una solución básica inicial (SF en un vértice) y, a
través de sucesivas iteraciones, explora sistemáticamente los vértices
del poliedro de soluciones del programa lineal hasta identificar la
solución óptima.
Si bien con posterioridad se han desarrollado métodos que teóricamente
son más eficientes en tiempo computacional para problemas de gran
tamaño, simplex ha demostrado, en la práctica, un mejor desempeño en
la mayoría de los casos, razón por la cual es aún el de mayor difusión.
El método simplex tiene en cuenta las siguientes propiedades de los
puntos extremos o soluciones factibles básicas:
3
La demostración de este teorema puede consultarse en Gass (1979), Capítulo 3.
4
El teorema que fundamenta el método simplex se enuncia y demuestra en el Anexo 2, al
final de este Capítulo.
PROGRAMACIÓN LINEAL 69
Su formulación matemática:
Definición de variables
x1: cantidad a producir del producto 1
x2: cantidad a producir del producto 2
Max z = 4 x1 + 7 x2
Sujetas las variables xj a:
10 x1 + 10 x2 ≤ 980 (h mano de obra)
12 x1 + 24 x2 ≤ 1932 (h máquina)
15 x1 + 10 x2 ≤ 1250 (unidades de material prima)
xj 0, j = 1, 2
Resolvemos gráficamente
x2
120
114
x
108 2
102
Vértice
96
90
: 15.0 x1 + 10.0 x2 = 1250.0
84
78
72
óptimo
66
60
54
48 Payoff: 4.0 x1 + 7.0 x2 = 292.3
42
36
30 : 12.0 x1 + 24.0 x2 = 1932.0
24
18 : 10.0 x1 + 10.0 x2 = 980.0
12
6
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 x150
1 160 170 180 190 200 x1
Gráfico 10
: 10.0x1 + 10.0x2 <= 980.0
: 12.0x1 + 24.0x2 <= 1932.0
: 15.0x1 + 10.0x2 <= 1250.0
70 CAPÍTULO 3
Gráfico 11
PROGRAMACIÓN LINEAL 71
5
O bien m vectores, tal que permutando el orden de sus columnas tengan configuración
de matriz identidad.
6
Posteriormente se analizará la forma de solucionar este inconveniente a fin de hallar una
solución básica de partida.
PROGRAMACIÓN LINEAL 73
• Si Z es de Maximización: (cj-zj) 0; j
• Si Z es de Minimización: (cj-zj) 0; j
• Para alguna variable no básica que pueda entrar a la base se
verifica que todos los ij son ≤ 0
EJEMPLO DE APLICACIÓN
Retomando nuestro problema de la fábrica de cerámicos, una vez
agregadas las variables de holgura a su formulación, nos queda:
S3 = 320
CB
CB Base VLD NOMBRE DE LAS VARIABLES
zj
cj - zj
Tabla3
Columna Base: nombre de las variables básicas. Hay un renglón para cada
variable básica y este renglón tiene un 1 en la columna que corresponde a dicha
variable básica.
Columna CB: coeficientes que preceden a las variables básicas en la función
objetivo.
Fila CB: coeficientes que tienen cada una de las variables en la función objetivo.
Columna VLD (vector del lado derecho): contiene los valores de las
variables básicas en la presente solución y el valor de la función objetivo.
El cuerpo de la tabla contiene tantas filas como ecuaciones de restricción
tenga el problema, más dos renglones, uno para zj y otro para cj – zj; y
tantas columnas como variables tenga el problema.
Cálculo de la fila zj: se determina cada valor como la suma de los
productos que se obtienen multiplicando los elementos de la columna C B
por los elementos correspondientes de la j-ésima columna.
Cálculo de la fila cj - zj: se determina cada valor restando zj de cj.
cB 8 6 0 0 0
Verifique en la
solución gráfica que cB Base VLD x1 x2 S1 S2 S3
esta solución
0 S1 300 5 5 1 0 0
corresponde al vértice
(0,0). 0 S2 400 4 8 0 1 0
0 S3 320 6 4 0 0 1
zj 0 0 0 0 0 0
cj - zj 8 6 0 0 0
Tabla 4
En esta solución, Z = 0.
PROGRAMACIÓN LINEAL 77
i
= min ; ij 0
ij
Una vez determinada la variable que sale de la base, en este caso S 3,
marcamos la fila correspondiente:
cB 8 6 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1 300 5 5 1 0 0 300/5=60
0 S2 400 4 8 0 1 0 400/4=100
0 S3 320 6 4 0 0 1 320/6=53,33
zj 0 0 0 0 0 0
cj - zj 8 6 0 0 0
Tabla 5
(
Znuevo = Z0 + C j − Zj )
Como x1 reemplaza a S3, la columna correspondiente a x1 en la nueva
tabla deberá ser el vector unitario:
0
0
1
cB 8 6 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1
0 S2
8 x1 320/6 1 4/6 0 0 1/6
zj
cj - zj
Tabla 7
0
0
1
cB 8 6 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1
0 S2 1120/6 0 32/6 0 1 -4/6
8 x1 320/6 1 4/6 0 0 1/6
zj
cj - zj
Tabla 9
cB 8 6 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1 200/6 0 10/6 1 0 -5/6 20
0 S2 1120/6 0 32/6 0 1 -4/6 35
8 x1 320/6 1 4/6 0 0 1/6 80
zj 1280/3 8 32/6 0 0 8/6
cj - zj 0 4/6 0 0 -8/6
Tabla 11
x2 = 0
S1 = 200/6
S2 = 1120/6
S3 = 0
Z = 1280/3
Z = 440
EJEMPLO DE APLICACIÓN
Supongamos el siguiente problema de PL:
Tablas simplex:
cB 15 25 0 0 0 -M
cB Base VLD x1 x2 S1 S2 S3 A1
0 S1 50 5 6 1 0 0 0 10
-M A1 30 8 4 0 -1 0 1 3,75
0 S3 5 0 1 0 0 1 0 ---
zj ---- -8M -4M 0 M 0 -M
cj - zj 15+8M 25+4M 0 -M 0 0
Tabla 13
cB 15 25 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1 31,25 0 3,5 1 0,625 0 8,92
15 x1 3,75 1 0,5 0 -0,125 0 7,5
0 S3 5 0 1 0 0 1 5
zj 56,25 15 7,5 0 -1,875 0
cj - zj 0 17,5 0 1,875 0
Tabla 14
Aún no llegamos a la solución óptima, la variable que entra es x 2 y la
que sale es S3.
cB 15 25 0 0 0
cB Base VLD x1 x2 S1 S2 S3 Para el cálculo de
no se consideran los
0 S1 13,75 0 0 1 0,625 -3,5 22
cocientes para las
15 x1 1,25 1 0 0 -0,125 -0,5 ---- filas de x1 y x2 porque
25 x2 5 0 1 0 0 1 ---- los denominadores
zj 143,75 15 25 0 -1,875 17,5 son negativo y nulo
respectivamente.
cj - zj 0 0 0 1,875 -17,5
Tabla 15
Luego de una iteración más, obtenemos la tabla óptima:
cB 15 25 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S2 22 0 0 1,6 1 -5,6
15 x1 4 1 0 0,2 0 -1,2
25 x2 5 0 1 0 0 1
zj 185 15 25 3 0 7
cj - zj 0 0 -3 0 -7
Tabla 16
S1 = 0
S2 = 22
S3 = 0
Z = 185
9. CASOS PARTICULARES
Al resolver un problema de PL, pueden presentarse situaciones
especiales, las cuales se conocen con el nombre de “casos particulares”.
x2
10
6
Payoff: 20.0 x1 + 14.0 x2 = 82.0
En el vértice óptimo se
sa
intersectan tres restricciones,
4
8x1 + 4x2 28 3
A
podríamos decir que el vértice A
: 8.0 x1 + 4.0 x2 = 28.0
x1 , x2 0 1
de n-m variables y, por lo tanto,
0
que la solución sea degenerada.
0 1 2 3 4 5 6 7 8 9 10 x1
Veamos ahora las últimas dos tablas simplex para este problema:
cB 20 14 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1 8 4 0 1 0 -2 2
0 S2 12 6 0 0 1 -1 2
14 X2 5 1 1 0 0 0,5 5
zj 70 14 14 0 0 0
cj – zj 6 0 0 0 -7
Tabla 17
sa
70
65
x1 40
50
x2 25
40
35
restricción.
30 D
x1, x2 0
: 0.0 x1 + 1.0 x2 = 25.0
25
Payoff: 80.0 x1 + 80.0 x2 = 4380.0
20
15
: 1.0 x1 + 0.0 x2 = 40.0
10
: 5.0 x1 + 5.0 x2 = 500.0
5
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 x1
80
70
sa 65
60
12x1+6x2 600 45
A isoutilidad (z) también es
40
86 24 CAPÍTULO 3
calculando,
Znuevo = Z0 + C j − Zj ( )
Znuevo = 4000 + 0(40) = 4000
sa es paralela a una de
8x1 + 4x2 28 las restricciones
2x1 + 2x2 10 limitantes, pero al ser
8x1 + 2x2 22 un óptimo degenerado,
x1, x2 : 2.0 x1 + 2.0 x2 = 10.0 no tiene múltiples
soluciones óptimas.
12
Sin embargo, esto no sucede en todos los problemas que tienen óptimo
degenerado, como puede verse a continuación.
0 degenerada. 10
Optimal Decisions(x1,x2): ( 0.0, 0.0)
: 8.0x1 + 4.0x2 <= 28.0
: 2.0x1 + 2.0x2 <= 10.0
7
Ver la demostración de este Teorema en el Anexo 2 al final de este capítulo.
x2
120
114
108
102
PROGRAMACIÓN LINEAL 87
96
90
84
78
72
60
54
48
Max 2x1 + x2 42
Z crece
sa
36
indefinidamente Observe que la recta z puede
ser desplazada en su sentido de
30
x1 − x2 10 24
12 óptimo.
x1 , x2 0 6
0
x1
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
Payoff: 2.0 x1 + 1.0 x2 = 117.6
: 1.0x1 - 1.0x2 >= 10.0
: 0.0x1 + 2.0x2 <= 40.0
cB 2 1 0 0
cB Base x2
120
VLD x1 x2 S1 S2
2 x1 30 1 0 -1 0,5
114
1 x2 20 0 1 0 0,5
zj 108
80 2 1 -2 1,5
102c - z 0 0 2 -1,5
j j
96 Tabla 20
48
36
sa 24
En el gráfico se puede ver que no
10x1 + 5x2 150
existe una región factible. El
18
x1, x2 0
: 10.0 x1 + 5.0 x2 = 150.0
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170
Payoff: 20.0 x1 + 30.0 x2 = -356.6
cB 20
: 0.0x1 + 1.0x2 >= 20.0
30 0 0 0 -1000
cB Base VLD x1 x2 S1 S2 S3 A1
0 S1 66,667 5,834 0 1 -0,834 0 0
30 x2 16,667 0,834 1 0 0,167 0 0
-1000 A1 3,334 -0,834 0 0 -0,167 -1 1
zj ------ 858,334 30 0 171,66 1000 -1000
cj - zj -838.34 0 0 -171,66 -1000 0
Tabla 21
SI NO
Según el
vector i-ésimo
¿Dónde?
unidad que
1º Solución falte
en Tabla
Máx => -M
Coeficiente
verificamos en z? Mín => M
NO
SI Variable artificial
observamos
FIN positiva en la
base?
SI NO
Mejoramiento
Problema No Solución
Factible Óptima
seleccionamos
Máximo: i
mín
mayor (cj-zj)>0 ij
ij 0
Mínimo
menor (cj-zj)<0
Max Z = 8 x 1 + 6 x2
S.a.
5 x1 + 5 x2 300 H Mano de Obra
4 x1 + 8 x2 400 H Secado
6 x1 + 4 x2 320 H Cocción
x1 , x2 0
Max Z = 8 x 1 + 6 x 2 + 0 S1 + 0 S2 + 0 S 3
S.a.
5 x1 + 5 x 2 + S1 = 300 H Mano de Obra
4 x1 + 8 x2 + S2 = 400 H Secado
6 x1 + 4 x2 + S3 = 320 H Cocción
x1 , x2 , S1 , S2 , S3 0
cB 8 6 0 0 0
cB Base VLD x1 x2 S1 S2 S3
0 S1 200/6 0 10/6 1 0 -5/6 20
0 S2 1120/6 0 32/6 0 1 -4/6 35
8 x1 320/6 1 4/6 0 0 1/6 80
zj 1280/3 8 32/6 0 0 8/6
cj - zj 0 4/6 0 0 -8/6
Tabla 23
horas de cocción
por m2 de cerámico m2 de cerámico
esmaltado esmaltado a disminuir
C2 – Z2 = 6 – 32/6 = 4/6
4/6 320/6
10/6 200/6
32/6 1120/6
El valor de que cumpla con las tres inecuaciones será el nuevo valor
para x2. Resolviendo:
10/6 200/6 20
32/6 1120/6 35
4/6 320/6 80
Vemos que el nuevo valor de x 2 es 20 (el único valor que verifica las
tres inecuaciones).
Utilizando todo lo que tenemos hasta ahora, podemos conocer la
solución completa.
El nuevo valor de Z:
Z = 1280/3 + (20 . 4/6) = 440
xi = i - ij (i = 1...m)
xj =
PROGRAMACIÓN LINEAL 93
xk = 0 (k 1, 2, ...m, j )
z0 + ( cj - zj)
94 CAPÍTULO 3
ANEXO 1
Óptimo z = f(x)
Sujeto a:
gi(x) bi para i 1
gi(x) bi para i 2
gi(x) = bi para i 3
Siendo 1, 2, e 3 una partición del conjunto de índices ={1, 2, …, m}.
Donde m representa el número total de ecuaciones y/o inecuaciones de
restricción existentes en el modelo.
Podemos decir que estamos frente a un problema de Programación
Matemática si el mismo trata de optimizar (maximizar o minimizar) una
función donde las variables pueden asumir únicamente los valores que
verifican un conjunto de restricciones expresadas como ecuaciones y/o
inecuaciones.
De acuerdo a las características de la función objetivo y las
restricciones, un modelo de Programación Matemática puede ser de:
ANEXO 2
1 0
2 0
.
.
X =
m 0
m +1 = 0
.
n = 0
z0 = c1 1 + c2 2 + ......+cm m (3)
sa
P1 1 + P2 +........+ Pmm = P0 (4)
Al ser una SFB, los vectores P1, P2, ..., Pm son linealmente
independientes (es decir, constituyen una base en el espacio m-
dimensional), por lo que podremos expresar cualquier vector no básico
como combinación lineal de ellos.
Tomemos un vector no básico cualquiera (Pj para j = m+1, m+2, ..., n.)
y lo expresemos como combinación lineal de los vectores básicos (P i, i =
1, 2, ..., m) mediante escalares que llamaremos ij.
(4) - (5)
(3) - (6)
En (7) despejamos P0
z0+ (cj-zj)=c1 (1- 1j) + c2 (2- 2j) + ..+cm (m - mj) + cj (10)
1 − 1 j
2 − 2 j
m − mj
xi = i - ij (i = 1...m)
xj = (12)
xk = 0 (k 1, 2, ...m, j )
PROGRAMACIÓN LINEAL 97
z0 + ( cj - zj)
Con lo cual hemos demostrado el teorema, puesto que:
Obsérvese que si para alguna j, donde se verifica c j > zj, “todos” los ij
0, entonces no tendrá límite superior, con lo cual tampoco lo tendrá z
(es función creciente de según (13) ) y estaremos ante el caso de un
funcional no acotado.
La nueva solución factible básica encontrada en (12) es utilizada como
una nueva base, a partir de la cual y desarrollándose todo el proceso
descripto, podemos ir encontrando nuevas SFB con valores cada vez
mejores del funcional siempre que para alguna j se verifique c j > zj
exista al menos un i que cumpla con (14).
El proceso se detendrá cuando para todo j se verifique que:
cj z j
Max Z = 8 x1 + 6 x2 + 0 x3 + 0 x4 + 0 x4
Sa
5 x1 + 5 x 2 + x3 = 300
4 x1 + 8 x2 + x4 = 400
6 x1 + 4 x2 + x5 = 320
xj 0 (j = 1, …, 5)
z0 = 1280/3
5 1 0 5
4 λ12 + 0 λ32 + 1 λ42 = 8 ;
6 0 0 4
c2 – z2 = 6 – 32/6 = 4/6
40
20
X = 0 ;
80
0
0 ( 2 2 )
z = z + c − z = 1280 / 3 + 20 (4 / 6) = 440
90
100 85
CAPÍTULO 3
80
ACTIVIDADES DE AUTOEXAMEN
75
70
65
ACTIVIDAD 1
En base al análisis del siguiente gráfico, responda:
60
55
x2
50
45
B
40
Payoff: 30.0 x1 + 30.0 x2 = 4080
35
A R1
30
: -15.0 x1 + 30.0 x2 = 145.0
25
C
20
: 6.0 x1 + 5.0 x2 = 150.0
15
5 R3
0
0 5 10 15 20 25 30 35 40 45 50 55 x601 65 70 75 80 85 90 95 100 x1
poliedro de soluciones?
ACTIVIDAD 2
¿Cuál será la región factible si al gráfico del problema anterior se le
agrega la restricción: x1 x2?
ACTIVIDAD 3
PROGRAMACIÓN LINEAL 101
ACTIVIDAD 4
Sea x1 el número de unidades producidas y x 2 el número de unidades
compradas. Si el costo unitario de producción es de $2, el de adquisición
de $3 y la demanda de 4000 unidades, entonces la función objetivo
será:
(a) Max 2 x1 + 3 x2
(b) Min 4000 (x1 + x2)
(c) Max 8000 x1 + 12000 x2
(d) Min 2 x1 + 3 x2
(e) Ninguna de las anteriores
ACTIVIDAD 5
Marque la o las alternativas correctas. En un PL, la degeneración ocurre
cuando:
(a) Existe una diferencia cj – zj = 0 para alguna variable no básica.
(b) Existe una diferencia cj – zj = 0 para alguna variable básica.
(c) Se produce un empate al decidir la variable que entra a la
base.
(d) Se produce un empate al decidir la variable que sale de la
base.
(e) Ninguna de las anteriores.
ACTIVIDAD 6
ACTIVIDAD 7
Responda Verdadero o Falso
ACTIVIDAD 8
Suponga que no se hubiera eliminado la variable básica con el menor
cociente i /ij para ij > 0, en una iteración específica del simplex. ¿Qué
efecto tendría esto sobre la tabla simplex para la siguiente solución?
ACTIVIDAD 9
Si de un problema de PL de maximización, con 5 variables y 3
restricciones, se conoce la siguiente solución factible básica:
x1 = 1 x2 = 2 x3 = 3 x4 = 0 x5 = 0
ACTIVIDAD 10
En la tabla simplex, para un problema de maximización, ¿cómo se
interpreta un valor Z4 = 10 si X4 es una variable de holgura?
ACTIVIDAD 11
Considerando la tabla simplex de un PL de maximización que se
presenta a continuación, se solicita:
30 20 15
CB Base VLD x1 x2 x3 S1 S2
5 0 0,5 1 -0,5 0
20 1 0,5 0 0,5 0
30 0 1,5 0 -0,5 1
Complete la tabla
a) ¿Es esta la solución óptima? ¿Por qué?
b) Si esta es la solución óptima, especifíquela.
c) Si no es la solución óptima, realice las iteraciones necesarias
para llegar a ella.
ACTIVIDAD 12
La siguiente tabla corresponde a un PL de maximización canónico (con
restricciones del tipo ):
104 CAPÍTULO 3
Cj 15 10 20 0 0 0
CB Base VLD x1 x2 x3 S1 S2 S3
50 2/3 1/3 1 1/3 0 0
200 7/3 5/3 0 -1/3 1 0
300 -1/3 7/3 0 -2/3 0 1
Zj
Cj - Zj
ACTIVIDAD 13
Dado el PL
Max z = 3 x1 + 6 x2 + 5 x3 Contribución Total a las Utilidades
Sujeto a:
50 x1 + 50 x2 + 40 x3 3900 Restricción de kilos de hierro
4 x1 + 8 x 2 + 6 x3 600 Restricción de Horas de Máquina
6 x1 + 3 x2 + 6 x3 330 Restricción de Horas de Mano de Obra
x1, x2, x3 0
Donde
x1: unidades de repuestos A a elaborar en una semana
x2: unidades de repuestos B a elaborar en una semana
x3: unidades de repuestos C a elaborar en una semana
ACTIVIDAD 14
Una compañía de auditores se especializa en preparar liquidaciones y
auditorías de empresas pequeñas. Tienen interés en saber cuántas
auditorías y liquidaciones pueden realizar mensualmente para
maximizar sus ingresos. Se dispone de 800 horas de trabajo directo y
320 horas para revisión. Una auditoría, en promedio, requiere de 40
horas de trabajo directo y 10 horas de revisión, además aporta un
ingreso de $300. Una liquidación de impuesto requiere de 8 horas de
trabajo directo y de 5 horas de revisión, produce un ingreso de $ 100. El
máximo de liquidaciones mensuales disponibles es de 50.
A. Plantee el problema y encontrar la solución óptima usando el método
gráfico.
B. Resuelva usando el método simplex.
C. A partir de la solución encontrada, elabore un informe para el decisor.
ACTIVIDAD 15
PROGRAMACIÓN LINEAL 105
NECESIDADES DE MANO
FX120 FX128
DE OBRA
Trabajador 1 2 1
Trabajador 2 1 2
ACTIVIDAD 16
Para los siguientes problemas se solicita:
a) Definir verbalmente el objetivo.
b) Definir las variables de decisión.
c) Identificar verbalmente a las restricciones.
d) Plantear el modelo lineal.
I. Desechos industriales
Una fábrica quiere minimizar los costos de deshacerse de las 100 t
diarias de basura que produce, las que puede enviar a dos plantas
procesadoras. En la Planta 1 (P1), el costo de procesamiento de la
basura es de $15 por t y en la Planta 2 (P2) es de $20 por t. Cada
Planta procesadora puede recibir hasta 80 t por día. Cada tonelada de
basura que entra en la P1 queda reducida a 0,25 t de desechos
industriales y en la P2 se reducen a 0,20 t. Estos desechos deben
enviarse a uno de los dos enterramientos sanitarios existentes en la
ciudad, los que tienen capacidad de recibir hasta 30 n por día cada uno.
Las distancias en kilómetros desde la fábrica hasta cada planta y desde
ellas a cada quemador son las que se muestran en el gráfico.
El costo de transportar una tonelada de material, sea basura o desecho,
es de $3 por kilómetro.
106 CAPÍTULO 3
10 Km
P1 E1
15 Km 15 Km
16 Km
20 Km P2 E2
12 Km
M2
M1 Embotelladora
M3
III. Inversiones
La AFJP Seguridad SA ha solicitado a un grupo de analistas financieros que
le indiquen recomendaciones de inversión para el fondo de jubilaciones.
Disposiciones del Estado hacen necesario diversificar las inversiones
asignando el fondo entre los siguientes instrumentos: certificados de
depósito (CD), bonos de tesorería (BT), acciones comunes (AC), acciones
especulativas (AE) y fondos comunes de inversión (FC). Los analistas han
estimado un rendimiento anual para cada clase de inversión y han
desarrollado un factor de riesgo para cada una de ellas. Este factor señala
la probabilidad de que el rendimiento real de la inversión en esa clase sea
inferior al rendimiento esperado. Esta información se presenta en la
siguiente tabla:
1. INTRODUCCIÓN
En el capítulo anterior se describieron las características de los modelos
de programación lineal, así como los diferentes caminos a partir de los
cuales encontrar la solución: resolución gráfica y algoritmo simplex.
En este capítulo se describen dos técnicas relacionadas con la
programación lineal: la dualidad y el análisis de sensibilidad. En la primera
parte se desarrolla la teoría asociada a la dualidad: cómo se obtiene el
dual de un programa lineal, la interpretación del concepto de precio
sombra y una serie de teoremas y resultados útiles para la interpretación
de un modelo lineal. En la segunda parte se muestran las posibilidades
del análisis de sensibilidad en la programación lineal, tratando de analizar
cómo varía la solución del modelo (tanto el valor de la función objetivo
como el valor de las variables de decisión) en función de dos conjuntos
de parámetros del modelo: los coeficientes de la función objetivo y los
términos independientes de las restricciones.
5 y1 + 4 y2 + 6 y3 8
5 y1 + 8 y2 + 4 y3 6
y1 , y2, y3 0
Observemos que, con los mismos datos del problema original, hemos
formulado otro PL que brindará información sobre el “valor” que los
recursos tienen para la empresa, lo que en economía se conoce como
precio sombra o valor marginal del recurso.
Si ahora resolvemos ambos problemas, observamos que los valores
óptimos son iguales; esto era de esperarse, ya que la empresa no
aceptaría, por la venta de sus insumos, menos dinero del que podría
obtener si los utiliza en la fabricación de sus productos.
EL PROBLEMA DUAL
Decimos entonces que, para cada problema de programación lineal existe
siempre, asociado al mismo, otro problema lineal. A este nuevo programa
se lo puede emplear para obtener la solución del problema original y,
DUALIDAD Y SENSIBILIDAD 111
Observemos que cada restricción del primal se relaciona con una variable
principal del dual, y viceversa. Es decir, la primera restricción primal se
corresponde con la primera variable dual; la segunda restricción primal,
con la segunda variable dual; y así sucesivamente. Razón por la cual
decimos que, si el programa primal tiene n variables principales y m
restricciones, el dual tendrá m variables principales y n restricciones.
Cabe aclarar que Bazaraa et. al. (1981) demuestran que “el dual del dual
es el primal”, por lo cual las definiciones dadas se pueden aplicar al revés
y los términos “primal” y “dual” son relativos al marco de referencia que
se seleccione.
No
Canónica ≤ → ≥0
Negativa
Restricción No Variable
≥ → ≤0 No Positiva
Canónica
No
Igualdad = → n/r
Restringida
No
≥0 → ≥ Canónica
Negativa
No
Variable No Positiva ≤0 → ≤ Restricción
Canónica
No
n/r → = Igualdad
Restringida
DUALIDAD Y SENSIBILIDAD 113
Veamos un ejemplo:
20 14 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P5 0 0 0 0 1,5 -2 1
P2 14 3 0 1 -0,25 1 0
P1 20 2 1 0 0,25 -0,5 0
Z 82 20 14 1,5 4 0
0 0 -1,5 -4 0
y1 y2 y3
54 45 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P5 0 1,667 0 0 0,333 -0,4 1
P1 54 5,556 1 0 -0,222 0,333 0
P2 45 6,667 0 1 0,333 -0,4 0
Z 600 54 45 3 0 0
0 0 -3 0 0
y1 y2 y3
DUALIDAD Y SENSIBILIDAD 115
Z * (B´Y*)
= = yi *
bi bi
Es imprescindible, para interpretar el significado económico de las
variables duales, tener muy en claro qué representa la función objetivo
del primal y qué representa la restricción relacionada a la variable dual
que se analiza.
Por ejemplo, si la i-ésima restricción representa la disponibilidad de b i
unidades de insumo para elaborar un producto y Z representa la
contribución total a las utilidades, entonces yi (variable dual) representa
el incremento en las utilidades por adicionar una unidad del i-ésimo
insumo.
Si, en cambio, la i-ésima restricción representa la demanda de al menos
bi unidades producidas y Z representa el costo total de producción,
entonces yi es el costo incremental de producir una unidad más del i-
ésimo producto.
Económicamente, puede interpretarse al vector de variables duales Y*
como un vector de precios sombra para el vector del lado derecho, es
decir que es el precio justo o valoración interna de los recursos.
3. ANÁLISIS DE SENSIBILIDAD
Uno de los supuestos sobre los que está basada la PL es el de certidumbre.
Es decir que el modelo supone que todos los parámetros que en él
intervienen se conocen con exactitud.
Nosotros sabemos que, en los problemas que se nos presentan
diariamente, existe un grado de incertidumbre o aleatoriedad en los datos
que poseemos. Por ejemplo, podemos estimar que la disponibilidad de
horas de mano de obra mensuales es, en promedio, de 500; pero, cada
mes en particular, la cantidad real de horas disponibles pueden no ser
exactamente 500, aunque sí un valor muy aproximado.
En general, al modelizar, se utilizan estimaciones estadísticas de los
parámetros del modelo y luego se los trabaja como valores ciertos.
Debido a esto, se hace necesario realizar un análisis de la sensibilidad de
la solución del problema. Esto es, estudiar los efectos que tienen
variaciones que puedan producirse en los valores de los parámetros en la
solución óptima del problema. Esto es lo que se conoce como análisis de
sensibilidad o análisis de pos-optimidad. Su objetivo es responder a
preguntas tales como:
1. ¿Cómo afecta a la solución óptima un cambio en el coeficiente de
costo de alguna variable no básica?
116 CAPÍTULO 4
114
96
La ecuación explícita
Max Z = 12 x1 +20 x2
de la recta de
90
de donde cualquier
cambio en los
15 x1 + 10 x2 600
72
66
coeficientes cj
modificará la
x1 y x2 ≥ 0
60
pendiente de la recta. 54
42
36
A
30
24
18
Payoff: 12.0 x1 + 20.0 x2 = 840.0
12
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170
Figura 1
Optimal Decisions(x1,x2): (20.0, 30.0)
:: 15.0
: 10.00.0
x1 x1
+x1+0.0
+ 12.0
10.0x2
x2 =x2==360.0
300.0
600.0
Figura 1
: 10.0x1 + 0.0x2 <= 300.0
: 0.0x1 + 12.0x2 <= 360.0
: 15.0x1 + 10.0x2 <= 600.0
120
114
108
102
DUALIDAD Y SENSIBILIDAD 96
117
90
60
54
48
42
36
A
30
24 x2
120
18
B Payoff: 20.0 x1 + 20.0 x2 = 1000.0
114
12
108
6
102
0
0 96 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 2
Figura 2
84 + 10.0x2 <= 600.0
: 15.0x1
78
54
48
42
36
A
30
Payoff: 35.0 x1 + 20.0 x2 = 1350.0
24
18
B
12
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 19
Figura 3
118 114
CAPÍTULO 4
108
las variables básicas eran x1, x2 y S2, siendo las no básicas S1y S3.
72
48
42 x2
120
36
114
A C
30
108
Payoff: 12.0 x1 + 20.0 x2 = 920.0
24
102
18
96
12
90
6
84
0
78
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
diferentes. 42
36
D A
30
Payoff: 12.0 x1 + 20.0 x2 = 760.0
24
18 x2
120
12
114
6 108
102
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
96
Figura 5
Optimal Decisions(x1,x2): (13.3, 30.0)
: 10.0x1
90 + 0.0x2 <= 300.0
: 0.0x1 + 12.0x2 <= 360.0
66
36
A E
30
24
18
12
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160
Figura 6
: 10.0x1 + 0.0x2 <= 300.0
: 0.0x1 + 12.0x2 <= 360.0
: 15.0x1 + 10.0x2 <= 800.0
x2
120
102
60
42
36
: 0.0 x1 + 12.0 x2 = 360.0
A
30
x2
120
24
114
18
108
12
102
6
: 15.0 x1 + 10.0 x2 = 600.0
96
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190
90
Figura 7
Optimal Decisions(x1,x2): (20.0, 30.0)
: 10.0x1 + 0.0x2 <= 400.0
: 84
0.0x1 + 12.0x2 <= 360.0
: 15.0x1 + 10.0x2 <= 600.0
x2
36
120
30
114 A
24 : 10.0 x1 + 0.0 x2 = 200.0
108
18
102
: 0.0 x1 + 12.0 x2 = 360.0
12
96
: 15.0 x1 + 10.0 x2 = 600.0
6
90
0
84
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160
36
A
30
18
: 0.0 x1 + 12.0 x2 = 360.0
12
0
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160
Figura 9
: 0.0x1 + 12.0x2 <= 360.0
: 15.0x1 + 10.0x2 <= 600.0
120 CAPÍTULO 4
REGLA DE 100 %
La validez de los cambios informados por el análisis de sensibilidad son
ceteris paribus, es decir, se deben analizar uno por vez. No obstante,
existe una regla práctica, conocida como regla del 100 %, que sostiene
que “para considerar cambios simultáneos se deben sumar los
porcentajes de cambio tanto de los incrementos como de las
disminuciones permisibles; si la suma de los cambios porcentuales no
excede el 100 %, la solución óptima no se modificará”. Esto es válido
tanto para cambios en el vector de términos independientes de las
restricciones como en los coeficientes que preceden a las variables en la
FO.
cj = c j + c j
Usando la condición de optimidad, podemos decir que xj seguirá siendo
no básica siempre que:
cj − zj 0
Reemplazando por el nuevo valor de c j y realizando algunas operaciones:
cj − zj 0
c j + c j - z j 0
c j -c j + z j
c j − ( c j − z j )
En general, para cualquier problema:
cj zj - cj
Si c j = z j - c j se obtiene una solución óptima alternativa.
afectados por Δc j . Para hacer esto, usamos las tasas de sustitución que
relacionan a la variable que sufrió un cambio en su coeficiente,
supongamos que sea xk, con cada una de las variables no básicas.
Si llamamos z0 al valor de la función objetivo, el nuevo valor se puede
determinar como:
z0 = z0 + λk Δck
Para que la solución actual siga siendo óptima, ningún valor cj - zj debe
hacerse positivo.
(c j ) ( )
- zj = c j - z j - λkjΔck para j = 1, 2, ..., n
(c j ) ( )
- zj = c j - z j - λkjΔck 0 para j = 1, 2, ..., n
1 1j 0
0
2 2j
3 + bi 3j 0
(1)
m mj 0
Solución actual
1 1j 0
2 2j 0
3 − bi 3j 0
(2)
m m j 0
ck − zk
Si ck − zk es positivo, convendrá introducir este nuevo producto o
actividad; y si es negativo, nos indicará la magnitud del cambio que
debería realizarse para poder introducirlo.
DUALIDAD Y SENSIBILIDAD 127
PRODUCTO
Alfombra Alfombra Alfombra Alfombra
Disponibilidad
I II III IV
Materia prima
3 4 8 6 22.000
(kg/unid.)
H sección
8 2 4 2 28.000
teñido
Definición de variables:
x1, x2, x3 y x4 indican las unidades de las alfombras I, II, III y IV a
fabricar, respectivamente.
1) 105000.0
Disminución que se produce en z
VARIABLE VALUE REDUCED COST por cada unidad en que se
incrementa la variable
X1 0.000000 0.500000
X2 500.000000 0.000000
X3 2500.000000 0.000000
X4 0.000000 35.000000
3) 17000.000000 0.000000
4) 0.000000 9.000000
Objetivo 0 105000
Celdas de variables
Nombre Valor original Valor final
Variables Alf. I 0 0
Variables Alf. IV 0 0
Restricciones
Nombre Valor de la celda Estado Holgura
Análisis de Sensibilidad
donde bi representa el incremento del valor del lado derecho que, en
este caso, es negativo.
cj 40 60 30 10 0 0 0
cj Base VLD x1 x2 x3 x4 S1 S2 S3
30 x3 2500 0,05 0 1 0,5 0,15 0 -0,10
0 S2 17000 6,5 0 0 -1 -0,5 1 0
60 x2 500 0,65 1 0 0,5 -0,05 0 0,20
zj 105000 40,5 60 30 45 1,5 0 9
cj - zj -0,5 0 0 -35 -1,5 0 -9
Tabla 2
x4= 10
S1= 0
S3= 0
Z = 105000 - (35)10 = $104650
Se trata de una solución factible no básica.
Para calcular los intervalos de sensibilidad, tanto de los coeficientes de la
función objetivo como de los valores del lado derecho, necesitamos la
tabla óptima de simplex:
cj 40 60 30 10 0 0 0
cj Base VLD x1 x2 x3 x4 S1 S2 S3
30 x3 2500 0,05 0 1 0,5 0,15 0 -0,10
0 S2 17000 6,5 0 0 -1 -0,5 1 0
60 x2 500 0,65 1 0 0,5 -0,05 0 0,20
zj 105000 40,5 60 30 45 1,5 0 9
cj - zj -0,5 0 0 -35 -1,5 0 -9
Tabla 3
i) Intervalo de sensibilidad para los coeficientes de las variables:
Como la variable x1 es no básica, el intervalo de sensibilidad de su
coeficiente se determina como:
− , c - z − , 0, 5
j j o sea
Como la variable x2 es básica, el intervalo de sensibilidad para su
coeficiente se calcula a partir de:
(c j ) ( )
- z j = c j - z j - λkjΔck
Entonces,
-0,5 - 0, 65Δc2 0
−35 − 0,5Δc2 0
−1,5 − (−0, 05)Δc2 0
−9 − 0,20Δc2 0
Δc2 −0,7692
Δc2 −70
Δc2 30
Δc2 −45
134 CAPÍTULO 4
1 1j 0
2 2j 0
3 + bi 3j 0
0
m mj
2500 0,15
17000 + Δb -0,5 0
1
500 -0, 05
Max (z) = 50 x1 + 10 x2
Sa
20 x1 + 10 x2 = 40
10 x1 + 10 x2 ≤ 60
20 x1 + 10 x2 ≥ 50
x1, x2 ≥ 0
Cj 50 10 0 -M -M 0
CB Base VLD x1 x2 S2 A1 A3 S3
50 x1 1 1 0 0 2/30 -1/30 1/30
0 S2 30 0 0 1 -1/3 -1/3 1/3
10 x2 2 0 1 0 -1/30 2/30 -2/30
zj 70 50 10 0 3 -1 1
cj - zj 0 0 0 -M -M -1
Tabla 5
En este caso, por tratarse de una “restricción de =”, se deben usar las
tasas de sustitución de la variable artificial A1. Planteamos el sistema de
restricciones:
1 2 / 30 0
30 + Δb -1 / 3 0
1
2 -1 / 30 0
2
1 + Δb1 0
30
-1
30 + Δb1 0
3
-1
2 + Δb1 0
30
Despejando nos queda que b1 ≥ -15 y b1 ≤ 60, es decir que b1 puede
disminuir hasta en 15 e incrementarse hasta en 60 o, lo que es lo mismo,
el valor de b1 puede estar entre [25, 100].
1 -1 / 30 0
30 + Δb -1 / 3 0
3
2 2 / 30 0
1 1 / 30 0
30 - Δb 1 / 3 0
3
2 -2 / 30 0
1
1 - Δb3 0
30
1
30 - Δb3 0
3
2
2 + Δb3 0
30
En ambos casos, despejando nos queda que b3 ≥ -30 y b3 ≤ 30, es
decir que b3 puede disminuir hasta en 30 e incrementarse hasta en 30
o, lo que es lo mismo, el valor de b3 puede estar entre [20, 80].
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
RESPONDA LAS SIGUIENTES PREGUNTAS
ACTIVIDAD 2
EXPLIQUE SI LAS SIGUIENTES AFIRMACIONES SON VERDADERAS O FALSAS:
ACTIVIDAD 3
Explique:
a) ¿Qué representa el costo reducido (reduced cost) que aparece en los
informes de computadora sobre la solución de un PL?
b) ¿Cuál es la utilidad de esta información?
c) ¿En qué parte de la tabla simplex se encuentra?
140 CAPÍTULO 4
ACTIVIDAD 4
En base al problema de la SuperMovil SA y su tabla óptima de simplex:
ACTIVIDAD 5
En la empresa Amarras SA, Juan es gerente de producción y está tratando
de decidir cuántos ganchos para tráiler debe hacer para usar un metal de
desperdicio. Tiene tres tipos de metal y puede hacer cualquiera de tres
tipos de ganchos. En la tabla siguiente se proporcionan los datos
necesarios:
La contribución a las utilidades es de $13 por cada gancho tipo 1, $16 por
gancho 2 y $14 por gancho tipo 3. Ya hay un pedido comprometido de 40
ganchos tipo 3.
El modelo lineal para este problema es:
max 13 G1 + 16 G2 + 14 G3
sa
4 G1 + 5 G2 + 6 G3 <= 950 Hierro acanalado
6 G1 + 3 G2 + 5 G3 <= 800 Hierro plano
4 G1 + 8 G2 + 6 G3 <= 1150 Hierro redondo
G3 >= 40 Producción mínima
Celdas de variables
Nombre Valor original Valor final
Variables G1 0 57,5
Variables G2 0 85
Variables G3 0 40
Restricciones
Nombre Valor de la celda Estado Holgura
H.Acanaldo 895 No vinculante 55
H. Plano 800 Vinculante 0
H. Redondo 1150 Vinculante 0
Prod. Mínima 40 Vinculante 0
Celdas de variables
Final Reducido Objetivo Permisible Permisible
Nombre Valor Coste Coeficiente Aumentar Reducir
Variables G1 57,5 0 13 19 1,7273
Variables G2 85 0 16 10 2,375
Variables G3 40 0 14 1,0556 1E+30
Restricciones
Final Sombra Restricción Permisible Permisible
Nombre Valor Precio Lado derecho Aumentar Reducir
H.Acanaldo 895 0 950 1E+30 55
H. Plano 800 1,1111 800 165 258,75
H. Redondo 1150 1,5833 1150 110 510
Prod. Mínima 40 -1,0556 40 41,25 40
142 CAPÍTULO 4
ACTIVIDAD 6
La siguiente tabla corresponde a un PL de maximización canónico:
Cj 40 60 50 0 0 0
CB Base VLD x1 x2 x3 S1 S2 S3
600 1/2 0 1 0 0 1/2
200 9/4 1 0 1/2 0 -1/4
200 -5/4 0 0 -1/2 1 1/4
Zj
C j - Zj
ACTIVIDAD 7
Caso: Fábrica de bolsos y carteras “Sureñas”
Rodrigo es un pequeño empresario que se dedica a la fabricación de
carteras y bolsos femeninos.
En este momento, está analizando el lanzamiento de dos nuevos modelos
de bolsos. En su confección utiliza cuero ecológico, herrajes, cierres, hilo
de seda reforzado y una tela especial con diseños originales.
Cj 0 0 0 0
Cj Básicas VLD X1 X2 X3 S1 S2 S3 S4
24 1 0 0 0 0 0 -1
428 0 0 0 0 1 -0.625 -0.125
23 0 0 1 -1 0 0.075 -0.125
160 0 1 0 0 0 0.125 0.625
Zj
Cj - Zj
TRANSPORTE, ASIGNACIÓN Y
TRANSBORDO
1. INTRODUCCIÓN
Un tipo particular de problemas de PL son los conocidos como de
transporte, de asignación y de transbordo. Ellos presentan ciertas
características que los hacen especiales, por lo que, en gran parte de la
literatura, se los estudia en forma separada bajo el nombre general de
problemas de flujo en redes. Además, su estructura matemática particular
ha permitido desarrollar procedimientos especializados de solución que
son más eficientes, en términos de tiempo computacional, que los otros
métodos de resolución de programas lineales.
2. EL PROBLEMA DE TRANSPORTE
El problema de transporte se presenta con frecuencia cuando se planea
la distribución de bienes o servicios desde varios lugares de suministro y
hasta varias ubicaciones de demanda.
Por lo general, es limitada la cantidad de bienes que están disponibles en
cada ubicación de oferta –orígenes– y los bienes se requieren en diversas
ubicaciones de demanda –destinos–.
El objetivo del problema de transporte es minimizar el costo total de
transportar los artículos desde los orígenes hacia los destinos.
Consideremos el problema de una fábrica de cerveza que distribuye, a
nivel nacional, a partir de dos plantas elaboradoras ubicadas en Córdoba
y Santa Fe. La cerveza se envía a tres mayoristas que se encuentran en
Buenos Aires, Salta y Neuquén y que se encargan de la distribución
posterior.
Los costos de distribución se presentan en la tabla, junto con la oferta
mensual de cada fábrica y la demanda mensual de cada mayorista.
146 CAPÍTULO 5
Mayorista Buenos
Salta Neuquén Oferta
Fábrica Aires
Córdoba 2 4 5 300
Santa Fe 1 3 7 400
Demanda 350 250 100
Tabla 1
CÓRDOBA SANTA FE ai
300 400
2 1 4 5 7 cij
3
Buenos Aires Salta Neuquén
350 250 100 bj
Gráfico 1
s.a.
h k
Minimizar Z = cijxij
i=1 j=1
s.a.
k
xij = ai (i = 1, 2, ...., h)
j=1
(1)
h
xij = bj (j = 1, 2, ...., k)
i=i
xij 0 i , j
El costo de envío desde cada origen hacia ese destino ficticio es nulo.
La o las variables positivas que en la solución final aparezcan relacionadas
con dicho destino indicarán dónde quedó el excedente de oferta.
k h
bj - ai
j=1 i=1
El costo de envío desde este origen hacia cada uno de los destinos nulo.
La o las variables positivas que en la solución óptima aparezcan
relacionadas con dicho origen indicarán los destinos que quedaron con
demanda insatisfecha.
Rutas inaceptables
Se eliminan del planteamiento de programación lineal a las
correspondientes variables de decisión.
Este ij nos indica el incremento que se produce en el costo total, es decir,
z, ante un incremento unitario de variable xij. Es decir, cuánto crece el
costo total si enviamos una unidad desde el origen i hacia el destino j.
Como lo que queremos es minimizar el costo total, entonces, si todos los
ij 0, la solución analizada es la óptima. Pero si algún índice ij nos da
un valor < 0, entonces la solución no es la óptima y debemos determinar,
al igual que en simplex, cuál es la variable que entra y cuál es la que sale
de la base.
EJEMPLO DE APLICACIÓN
Consideremos la siguiente tabla de transporte de un problema de
mínimo:
D1 D2 Oferta (ai)
O1 10 8 45
O2 9 5 50
O3 3 6 45
Demanda 90 30
(bj)
Tabla 2
Como en este caso ai =140 > bj =120, debe crearse un destino ficticio
(D3) con todos sus costos de envío (cij) iguales a cero, y con un
requerimiento de demanda igual a la diferencia entre el total ofrecido y el
total demandado.
Modificando la tabla de transporte, queda:
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 151
D1 D2 D3 Oferta (ai)
O1 10 8 0 45
O2 9 5 0 50
O3 3 6 0 45
Demanda (bj) 90 30 20
Tabla 3
D1 D2 D3 Oferta
10 8 0 45
O1 45 0
9 5 0 50 5
O2 45 5 0
3 6 0 45 20
O3 25 20 0
Demanda 90 30 20
45 25
0 0
Tabla 4
La solución factible básica inicial es:
x11=45 x23=0
x12=0 x31=0
x13=0 x32=25
x21=45 x33=20
x22=5
El valor de Z= 1030
152 CAPÍTULO 5
Variables básicas
Para resolver este sistema de ecuaciones
c11= u1+v1= 10; si u1= 0
indeterminado, asignemos un valor
v1=10 arbitrario a cualquier variable y luego
c21= u2+v1= 9; si v1=10 u2= - despejemos las restantes.
1
c22 = u2+v2= 5; si u2= -1 v2= 6 13 = 0 => indica que hay múltiples
c32 = u3+v2= 6; si v2= 6 u3= 0 soluciones que le dan a Z el valor de
c33 = u3+v3= 0; si u3= 0 v3= 0 $1.030.
31 = -7 => indica que z disminuye en $7
Variables no básicas
por cada unidad de mercadería que se envíe
12= c12-u1-v2= 8-0-6= 2
desde el origen 3 al destino 1.
13= c13-u1-v3= 0-0-0= 0
Esta es la variable que ingresa a la base.
23= c23-u2-v3= 0-(-1)-0= 1
31= c31-u3-v1= 3-0-10= -7
Tabla 5
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 153
El valor máximo que puede asumir la variable que entra (x31) estará dado
por el mínimo entre x21 y x32, esto es, donde se colocaron signos menos.
Es decir:
x31 = = minx21, x32 , x31 = 25
Para encontrar la nueva solución, se procede a actualizar la tabla,
sumando y restando el valor de x31 en todas las celdas donde haya algún
signo más o menos.
D1 D2 D3 Oferta
(-) 10 8 (+) 0
O1 45 45
9 5 0
O2 20 30 50
(+) 3 6 (-) 0
O3 25 20 45
Demanda 90 30 20
Tabla 6
x11=45 x23=0
x12=0 x31=25 Z= $855
x13=0 x32=0
x21=20 x33=20
x22=30
D1 D2 D3 Oferta
10 8 0
O1 25 20 45
9 5 0
O2 20 30 50
3 6 0
O3 45 45
Demanda 90 30 20
Tabla 7
x11=25 x23=0
x12=0 x31=45
x13=20 x32=0
x21=20 x33=0
x22=30 Z= $715
Sabemos que para que una solución sea posible básica no degenerada,
deberá tener tantas variables positivas como: nº de orígenes + nº de
destinos – 1, en este caso 5. Si nos fijamos en la tabla, vemos que
solamente hay 4 variables positivas.
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 155
Para las variables que están en la base: Para las variables que no están en la
base:
c11 = u1 + v1 = 3 u1 = 0 v1 = 3
c12 = u1 + v2 = 6 u2 = -1 v2 = 6 ij = cij – ui - vj
c22 = u2 + v2 = 5 u3 = 3 v3 = 8 13 = 7 – 0 – 8 = -1
c23 = u2 + v3 = 7 21 = 8 + 1 – 3 = 6
c33 = u3 + v3 = 11 31 = 4 – 3 – 3 = -2
32 = 9 – 3 – 6 = 0
Obsérvese que a la variable x23 se la
consideró como básica.
c11 = u1 + v1 = 3 u1 = 0 v1 = 3 13 = 7 – 0 – 8 = -1
c12 = u1 + v2 = 6 u2 = -1 v2 = 6 21 = 8 + 1 – 3 = 6
c22 = u2 + v2 = 5 u3 = 1 v3 = 8 32 = 9 – 3 – 6 = 2
c23 = u2 + v3 = 7 33 = 11 – 1 – 8 = 2
c31 = u3 + v1 = 4
D1 D2 D3 Oferta
3 6 7
O1 5 25 30 60
8 5 7
O2 30 30
4 9 11
O3 30 30
Demanda 35 55 30
Tabla 11
EJERCICIO ADICIONAL
En la tabla siguiente se dan los datos de un problema de transporte de
mínimo. Encuentre la solución óptima.
D1 D2 D3 Oferta
5 8 6
O1 60
4 10 6
O2 30
5 6 8
O3 30
Demanda 40 50 30
Tabla 12
3. EL PROBLEMA DE ASIGNACIÓN
Existen situaciones en las cuales es necesario asignar individuos
(personas, máquinas, etc.) a tareas (puestos de trabajo, zonas, etc.). A
este tipo particular de problema se lo conoce como asignación. Podemos
decir, entonces, que el problema de asignación considera m individuos
que deben distribuirse entre m tareas para minimizar el costo total de la
distribución.
Si definimos a las variables como xij = 1 ó 0 dependiendo si el individuo i
es asignado o no a la tarea j, y si cij es el costo de asignar el individuo i a
la tarea j, el modelo matemático general tiene la forma:
m m
mín cijxij
i=1 j=1
sa
m (4)
xij =1 i=1,2,...,m
j=1
m
xij =1 j=1,2,...,m
i=1
xij 0 i, j
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 157
EL MÉTODO HÚNGARO
Este método trabaja a partir de la tabla de costos originales y mediante
sucesivos cuadros, va reduciendo los mismos hasta encontrar la
asignación de costo mínimo. Podemos resumir el método mediante los
siguientes pasos:
III. Cubrir los ceros de la matriz: Cubrir todos los ceros de la matriz con
el menor número de líneas (horizontales y verticales) posibles.
EJERCICIOS DE APLICACIÓN
Ejercicio Nº 1:
Supongamos una empresa que tiene 4 operarios para asignar a cuatro
máquinas. Los costos de la asignación se encuentran en la tabla siguiente.
1 2 3 4
1 24 10 21 11
2 14 22 10 15
3 15 17 20 19
4 11 19 14 13
Tabla 13
1 2 3 4
1 14 0 11 1
2 4 12 0 5
3 0 2 5 4
4 0 8 3 2
Tabla 14
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 159
Al hacer esto, el costo óptimo será menor, pero la solución obtenida será
la misma.
1 2 3 4
1 14 0 11 0
2 4 12 0 4
3 0 2 5 3
4 0 8 3 1
Tabla 15
1 2 3 4
1 14 0 11 0
2 4 12 0 4
3 0 2 5 3
4 0 8 3 1
Tabla 16
1 2 3 4
1 15 0 12 0
2 4 11 0 3
3 0 1 5 2
4 0 7 3 0
Tabla 17
160 CAPÍTULO 5
1 2 3 4
1 15 0 12 0
2 4 11 0 3
3 0 1 5 2
4 0 7 3 0
Tabla 18
La asignación queda:
Ejercicio Nº 2:
En este caso, se nos presenta un problema de asignar 4 vendedores a 3
zonas con diferentes beneficios de acuerdo a la zona asignada.
1 2 3
A 40 30 20
B 18 28 22
C 12 16 20
D 25 24 27
Tabla 20
1 2 3 4
A 40 30 20 0
B 18 28 22 0
C 12 16 20 0
D 25 24 27 0
Tabla 21
4. EL PROBLEMA DE TRANSBORDO
Un problema de transbordo es una generalización del problema de
transporte, en el cual aparecen nodos intermedios llamados nodos de
transbordo, los que representan, por ejemplo, almacenes o depósitos.
En este problema, el flujo de mercadería que circula entre los nodos puede
ser, desde los orígenes hacia los destinos, pasando o no, por nodos de
transbordo.
En el ejemplo de las fábricas de cerveza, podemos suponer que existen
dos depósitos a los que se traslada la producción de ambas fábricas y
luego se distribuye.
Gráficamente, puede verse esta situación:
1 2
CÓRDOBA SANTA FE
300 400
3 4
Depósito Depósito
I II
5 6 7
Bs As Salta Neuquén
350 250 100
Gráfico 2
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 163
Depósito I Depósito II
Córdoba 1 2
Santa Fe 3 2
Tabla 24
Tabla 25
Min. Z = x13 + 2x14 + 3x23 +2x24 + 2x35 + 3x36 + 4x37 + 2x45 + 5x46 + 5x47
s.a.
x13 + x14 = 300
x23 + x24 = 400
x13 + x23 - x35 - x36 - x37 = 0
x14 + x24 – x45 - x46 - x47 = 0
x35 + x45 = 350
x36 + x46= 250
x37 + x47= 100
sa
xk
jk − xkj = L j
k
j = 1,2,..., n (5)
Donde (5) representa que el flujo total que sale menos flujo total que
entra es igual a la oferta del nodo.
Además, si:
Lj < 0 nodo de demanda
Lj > 0 nodo de oferta
Lj = 0 nodo de transbordo
EJEMPLO DE APLICACIÓN
Para la siguiente red de transbordo,
-30 plantear el PL correspondiente.
1 3
100 -40
1
2 6
2
2
4 2 2
1
2 7 -60
50 1 3
-20
arcos, tendríamos también una restricción por cada arco que tenga
capacidad.
Para plantear cada restricción, la forma más fácil es hacer:
flujo que entra al nodo (incluida la oferta en su caso) – flujo que sale al
nodo (incluida la demanda en su caso) = 0
min. 2x12 + x13 + x24 + x25 + 2x34 + 3x36 + 2x46 +3x57 + 2x67 + 2x76
sa :
100 - x13 - x12 = 0
50 + x12 – x24 – x25 = 0
x13 -30 – x34 – x36 = 0
x24 + x34 – x46 = 0
x36 + x46 + x76 – 40 – x67 = 0
x25 – x57 – 20 = 0
x57 + x67 – 60 – x76 = 0
xij 0
Recordemos que, para poder resolverlo, se debe dejar en el primer
miembro de cada igualdad todo lo que sea variable; y en el segundo, todo
lo que sea constante.
que, para cada nodo, a excepción del nodo fuente y del nodo destino,
debe darse la relación de equilibrio:
EJEMPLO DE APLICACIÓN
Consideremos la siguiente red
(5)
2 4
(10)
(8)
(3)
f 1 (7)
5 f
(6)
3 (8)
Maximizar f
sa
x12 + x13 = f
x12 - x23 - x24 = 0
x23 + x13 - x34 - x35 = 0
x24 + x34 - x 45 = 0
x35 + x 45 = f
x12 10
x13 6
x23 3
x24 5
x34 7
x35 8
x 45 8
xij 0 i j
168 CAPÍTULO 5
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
RESPONDA LAS SIGUIENTES PREGUNTAS:
1. ¿Cuántos valores nulos deberá tener una solución de un problema de
transporte para que sea no básica si se sabe que el problema tiene 8
orígenes, 6 destinos y, además, se conoce que el total de oferta es menor
que el total de demanda?
ACTIVIDAD 2
RESPONDA VERDADERO O FALSO:
ACTIVIDAD 3
La empresa de plásticos “Azteca” posee 3 plantas de producción de hojas
de acrílico, las cuales son transportadas a 2 diferentes fábricas para
producir diferentes productos. Los costos de transporte por lámina
transportada desde las plantas de producción a las factorías, así como los
datos de demanda y disponibilidad, son como sigue:
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 169
1 2 DISPONIBILIDAD
1 25 19 92
2 17 12 74
3 23 18 86
DEMANDA 173 215
ACTIVIDAD 4
Una empresa planea abrir 4 depósitos en 4 ciudades –Córdoba, Buenos
Aires, Rosario y Mendoza– para abastecer a 3 regiones. Desde cada
depósito se pueden enviar 100 unidades por semana de un cierto
producto. La región 1 requiere 80 unidades por semana, la 2 demanda 70
unidades y la 3 necesita 50 unidades. Los costos de transporte por enviar
una unidad desde cada planta a cada región se dan en la tabla.
Hasta ($)
Desde
Región 1 Región 2 Región 3
Córdoba 10 20 30
Buenos Aires 28 10 15
Rosario 15 15 10
Mendoza 20 30 20
Formule un PLE que se pueda usar para minimizar los costos semanales
de transporte para cumplir con las demandas.
ACTIVIDAD 5
El dueño de una agencia de publicidad trata de decidir cuál de 4
vendedores debe asignar a cada uno de 4 clientes. En la tabla se
presentan los costos estimados de la asignación de cada vendedor. Use
el método húngaro para encontrar la solución óptima del problema.
Establezca el valor óptimo de la función objetivo.
CLIENTE
VENDEDOR 1 2 3 4
A 15 19 20 18
B 14 15 17 14
C 11 15 15 14
D 21 24 26 24
170 CAPÍTULO 5
ACTIVIDAD 6
Una empresa debe distribuir 5 promotores de su nueva línea de máquinas
para riego automático a 4 regiones. En la tabla se muestran los
incrementos estimados en ventas de acuerdo a la asignación de cada
promotor. Use el método húngaro para encontrar la solución óptima del
problema. Establezca el valor óptimo de la función objetivo.
REGIONES
PROMOTOR 1 2 3 4
A 20 22 22 15
B 25 15 16 20
C 18 20 18 20
D 21 15 20 24
E 17 20 20 18
ACTIVIDAD 7
En la tabla siguiente se encuentran los costos de asignación de 5
empleados a 5 puestos de trabajo. Encuentre la asignación óptima usando
el método húngaro.
Trabajo
1 2 3 4 5
Empleado
1 20 14 6 10 22
2 16 8 22 20 10
3 8 6 24 14 12
4 20 22 2 8 6
5 4 16 22 6 24
ACTIVIDAD 8
En la tabla siguiente se encuentran los costos de asignación de 3 operarios
a 4 tareas. Encuentre la asignación óptima usando el método húngaro.
Los operarios 2 y 3 pueden ser asignados a dos tareas. Asimismo, observe
que las celdas tachadas significan que el operario no puede ser asignado
a dicha tarea.
1 2 3 4
1 50 46 42 40
2 51 48 44
3 47 45 45
ACTIVIDAD 9
TRANSPORTE, ASIGNACIÓN Y TRANSBORDO 171
x1 , x2 , x3 y x 4 0
ACTIVIDAD 10
Plantear los PL de las siguientes redes de flujo de costo mínimo:
150
200 1 70
1
A. 75 1 125
125 150
120
100 1 1 50
100 1 100
60
0,10
2 4 600
0,20
0,20
B. 2000 (1000)
1
0,15 0,15
(500)
3 5 800
0,25
C. 50
-30
8
1
4
2
2 3 4
2
(15) 3
1 (60)
2
5
40
-60
172 CAPÍTULO 5
ACTIVIDAD 11
Dibujar la red correspondiente al siguiente PL:
xij 0 i j
ACTIVIDAD 12
Plantear el PL de la siguiente red de flujo máximo:
2
100 400
100
300 300
f 1 3 5 f
200
200 650
4
CAPÍTULO 6
PROGRAMACIÓN LINEAL ENTERA
1. INTRODUCCIÓN
Este capítulo trata sobre modelos que podrían ser formulados y resueltos
como modelos de PL, con la condición de que algunas o todas sus
variables tienen que asumir valores enteros.
Recordemos que uno de los supuestos de los modelos de programación
lineal es la divisibilidad, es decir que las variables pueden asumir valores
fraccionarios. En el mundo real, frecuentemente nos encontramos con
problemas en los cuales las variables deben ser enteras. En tal caso, se
llegará a un valor objetivo óptimo menor (en caso de maximización) al
del problema que acepta soluciones continuas, salvo algún caso
particular en el cual la solución óptima resulta entera 1.
Otros casos de necesidad de programación entera (PE) se refieren, por
ejemplo, a variables de decisión que deben ser "binarias" (enteras que
asumen únicamente los valores 0 o 1). Estas variables permiten modelar
situaciones de opciones (elegir entre alternativas) o situaciones en las
que se deben respetar ciertas condiciones lógicas y que, sin la presencia
de ellas, no podría modelarse el problema.
Resumiendo, podemos decir que el modelo de programación entera es
un modelo de PL donde las variables deben asumir valores enteros. Si
solo es necesario que algunas variables sean enteras, entonces se trata
de un problema de programación entera mixta. Cuando las variables
pueden asumir solamente valores 0 o 1, se denomina programación
binaria.
2. RELAJACIÓN LINEAL
La relajación lineal (RPL) de un PE se obtiene al omitir la condición que
exige que las variables sean enteras. En consecuencia, el problema se
transforma en un PL continuo, resultando una versión menos restringida
del problema entero. En consecuencia:
1
Como es el caso de los problemas de transporte, asignación y transbordo.
174 CAPÍTULO 6
Max 10 A + 50 B
s.a.
6 A + 1 B 32 disponibilidad del insumo I
A, B 0 y enteras
11
PROGRAMACIÓN LINEAL ENTERA 175
10
B B
7
0
A 0 1 2 3 4 5
A6 7 8 9 10 11 12 13
s.a.
6x1 + x2 50
x1 + 12 x2 60
x1, x2 0 y enteras
176 CAPÍTULO 6
1) 25.63380
1) 25.00000
Ejemplo:
Max Z = 3x1 + 5x2
s.a.
6x1 + 8x2 20
x1 y x2 0 y enteros
x1 = 0 , x2 = 2,5 y Z = 12,5
Gráficamente,
Problema 1 Problema 2
Max 3x1 + 5x2 Max 3x1 + 5x2
Sa Sa
6x1 + 8x2 20 6x1 + 8x2 20
x2 2 x2 3
x1 y x2 0 x1 y x2 0
3 4
3
2 20
2
1
1
0 0
0 1 2 3 4 5 6 7 80 x1 x1
1 2 3 4 5 6 7
Problema 3
4
Max 3x1 + 5x2
Sa
6x1 + 8x2 20
x2 2
x1 0
0
x 1 y x2 0 0 5 10 15
Óptimo (x1,x2) (0.00, 2.00)
Optimal Decisions(x1,x2): (0.00, 2.00)
: Z=10
6.00x1 + 8.00x2 <= 20.00
: 0.00x1 + 1.00x2 <= 2.00
: 1.00x1 + 0.00x2 <= 0.00
180 CAPÍTULO 6
x2
7
Problema 4 6
Sa 4
6x1 + 8x2 20
x2 2 3
x1 1
2
x1 y x2 0 1
0
0 1 2 3 4 5 6 7 8 x1
x2
Óptimo (x1, x2) (1.00; 1.75)
Payoff:
7 Optimal Decisions(x1,x2): (1.00, 1.75)
: 6.00x1 + 8.00x2 <= 20.00
Z=11,75
: 0.00x1 + 1.00x2 <= 2.00
6 : 1.00x1 + 0.00x2 >= 1.00
5
Problema 5
4
6x1 + 8x2 20
2
x2 2
x1 1 1
x2 2
0
0 1 2 3 4 5 6 7 8 x1
x1 y x2 0
: 6x1 + 8x2 <= 19
: 0x1 + 1x2 <= 2
: 1x1 + 0x2 >= 1
: 0x1 + Problema no factible
1x2 >= 2
x2
7
Problema 6
5
Sa
6x1 + 8x2 20 3
x2 2
2
x1 1
x2 1 1
x1 y x2 0
0
0 1 2 3 4 5 6 7 8 x1
Z=11
: 0.00x1 + 1.00x2 <= 2.00
: 1.00x1 + 0.00x2 >= 1.00
: 0.00x1 + 1.00x2 <= 1.00
PROGRAMACIÓN LINEAL ENTERA 181
x1 = 0
x2 = 2,5
Z = 12,5
X2 ≤ 2 X2 ≥ 3
P1 P2
x1 = 0,67 No Factible TERMINAR
x2 = 2,00
Z = 12
X1 ≥ 1 X1 ≤ 0
P4 P3
x1 = 1 x1 = 0 FACTIBLE ENTERA
x2 = 1,75 x2 = 2 TERMINAR
Z = 11,75 Z = 10
X2 ≤ 1 X2 ≥ 2
P6 P5
x1 = 2 No Factible TERMINAR
x2 = 1
Z = 11
FACTIBLE ENTERA
TERMINAR
Si yj = 0 no se compra la acción j
Consideremos ahora agregar la restricción:
xj 150 yj
xj 50 yj
De esta forma, si yj = 1 se verificará que:
50 xj 150
xA y xB 0 y enteras
yA y yB binarias
250 300
Producción máxima de A está dada por el mínimo entre: y , en
5 7
este caso M = 42 unidades.
De la misma manera se procede para encontrar el máximo que se puede
producir de B, es decir, N= 83 unidades.
M y N no pueden ser inferiores a la máxima producción posible de cada
producto; de lo contrario, estaríamos introduciendo restricciones
innecesarias.
PROGRAMACIÓN LINEAL ENTERA 185
Tabla de horarios
8 a 10 10
10 a 12 12
12 a 14 17
14 a 16 14
Restricciones:
El primer conjunto de restricciones representa el número mínimo de
personas que se necesitan por período.
El segundo conjunto de restricciones representa la condición de que, en
cada turno, por lo menos el 60 % del personal ser a tiempo completo.
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
Una compañía dedicada a la fabricación de perfumes desarrolló 5 nuevas
fragancias para lanzar al mercado la próxima temporada de verano. La
administración deberá decidir sobre cuáles de estos productos se van a
producir y a qué niveles.
El costo fijo de puesta en marcha de la línea de producción para los 5
productos es de $26.000, $30.000, $28.000, $35.000 y $40.000 para las
fragancias Floral, Gardenia, Fresca, Madera y Tabaco, respectivamente.
La información referente a las contribuciones marginales, utilización de
insumos base y horas de mano de obra que se necesitan para producir
una onza de cada fragancia se presentan en la tabla siguiente:
FRAGANCIAS
Floral Gardenia Fresca Madera Tabaco
Cont. Marg. ($/onza) 35 39 40 51 58
Insumo I 8 7 2 10 15
Insumo II 8 9 16 15 12
Horas mano de obra 4 6 5 8 7
ACTIVIDAD 2
Una empresa planea abrir 4 depósitos en 4 ciudades: Córdoba, Buenos
Aires, Rosario y Mendoza, para abastecer a 3 regiones. Desde cada
depósito se pueden enviar 100 unidades por semana de un cierto
producto. El costo fijo semanal de mantener en operación cada depósito
es de $1.200 para Córdoba, $1.000 para Buenos Aires, $1.100 para
Rosario y $1.400 para Mendoza. La región 1 requiere 80 unidades por
semana, la 2 demanda 70 unidades y la 3 necesita 50 unidades. Los
costos, de producción y transporte, por enviar una unidad desde cada
planta a cada región se dan en la tabla.
Se desea cumplir con las demandas semanales a un costo mínimo
cumpliendo, además, con las siguientes condiciones:
• Si se abre el depósito de Córdoba, entonces se debe abrir el de
Buenos Aires.
• Se deben abrir no más de 2 depósitos.
• Se tiene que abrir el depósito de Rosario o el de Mendoza.
Hasta ($)
Desde
Región 1 Región 2 Región 3
Córdoba 20 40 50
Buenos Aires 48 15 26
Rosario 26 35 18
Mendoza 24 50 35
Formule un PLE que se pueda usar para minimizar los costos semanales
de cumplir con las demandas.
ACTIVIDAD 3
Metalcor, un autopartista de nuestra ciudad, está considerando en este
momento la planificación de la producción de 3 tipos de radiadores: A, B
y C. En la tabla se presentan los recursos requeridos, los costos fijos de
preparación de la producción y las contribuciones a las utilidades
proporcionadas por cada uno. En la actualidad, cuenta con 20 toneladas
de chapa, 100 toneladas de cobre y 4.500 horas de mano de obra. Para
que la producción del radiador A resulte redituable, deberán fabricarse
(si se fabrican) por lo menos 80 unidades. En el caso de los otros dos, en
caso de fabricarse, deberán producirse en lotes de entre 50 y 100
unidades.
A B C
Chapa (T/unid.) 0,015 0,020 0,020
Cobre (T/unid.) 0,025 0,035 0,030
Horas de mano de obra 10 12 15
Costo de prep. producc. 1000 2000 1500
Contrib. a las utilidades por unid. 20 35 30
ACTIVIDAD 4
Suponga que un producto, si se fabrica, debe hacerse en lotes de
tamaño Q. Si se simboliza por x a la cantidad de producto fabricado,
las dos restricciones adecuadas son las siguientes:
a) x + Uy 0 ; x – Qy 0
b) x - Uy 0 ; x – Qy 0
c) x - Uy 0 ; x – Qy 0
d) x - Uy 0 ; x – Qy 0
ACTIVIDAD 5
Suponga que P1, P2 y P3 son variables cuyos valores son 1 si se va a abrir
una planta en particular y 0 en cualquier otro caso. Escriba una restricción
lineal separada para cada una de las siguientes restricciones:
1. Si se abre la Planta 1, entonces la Planta 2 debería abrirse.
2. Debe abrirse la Planta 1 o la Planta 2, pero no ambas.
3. No se desea abrir la Planta 1 a menos que se abra la Planta 3.
4. Si se abre la Planta 1, entonces no podrá abrirse la Planta 2.
ACTIVIDAD 6
Responda Verdadero o Falso y justifique su respuesta:
ACTIVIDAD 7
Dados los siguientes PL enteros, resuélvalos utilizando el método de
ramificación y acotación.
Max 25 x1 + 20 x 2
sa
a) 35 x1 + 30 x 2 150
10 x1 + 15 x 2 50
x1 , x 2 0 y enteros
190 CAPÍTULO 6
Min 1x1 + 3x 2
sa
b) 1x1 + 5x 2 10
1 x1 + 2 x 2 5
x1 , x 2 0 y enteros
ACTIVIDAD 8
Considere el siguiente programa lineal entero mixto:
Max 4 x1 + 6 x 2
sa
8 x1 + 18x 2 72
14 x1 + 10 x 2 70
x1 , x 2 0 y x1 entera
PROGRAMACIÓN DINÁMICA
1. INTRODUCCIÓN
En muchas oportunidades, nos enfrentamos a situaciones en las cuales
debemos tomar una sucesión de decisiones interrelacionadas; esto es,
que la decisión que se adopte en un momento afectará a la que se toma
a continuación.
Se trata, generalmente, de problemas complejos que pueden dividirse
en subproblemas de menor tamaño. Veamos los siguientes ejemplos:
1. Se desea implementar una política de inversiones a lo largo de seis
meses, para ello es necesario determinar cuánto debe invertirse cada
mes. En este caso, los meses pueden entenderse como etapas en las
cuales debe decidirse la inversión a realizar.
2. El Banco Nación cuenta con un importante monto para entregar
créditos destinados a fomentar la incorporación de la computadora en
las escuelas primarias provinciales. ¿Cuánto conviene entregar a cada
una? En este caso, cada provincia constituye una etapa del problema
general, en la cual es necesario tomar una decisión.
En situaciones de este tipo podemos utilizar un modelo de optimización
llamado programación dinámica (PD).
En realidad, la PD es un enfoque que nos permite encontrar la solución
de problemas complejos, descomponiéndolos en una secuencia de
problemas más pequeños y, de esta manera, encontrar la combinación
de decisiones que optimice la efectividad global.
En este capítulo, trataremos problemas de PD en los cuales las
condiciones iniciales en cada subproblema pueden representarse por un
conjunto discreto y los resultados de cada decisión están completamente
determinados por la condición inicial y la decisión adoptada.
Los problemas con estas características corresponden a la programación
dinámica discreta determinista.
192 CAPÍTULO 7
2. METODOLOGÍA
Suponga que usted dispone de $4.000 que puede destinar a 3 opciones
de inversión diferentes. Las utilidades que se obtienen en cada opción
dependen de la cantidad invertida (tabla 1).
Si se supone que la cantidad invertida en cada opción debe ser múltiplo
exacto de $1.000, ¿cuál será la política de inversión que eleve al
máximo las utilidades ganadas?
Utilidades en miles de $
$ invertidos Inversión Inversión Inversión
(miles) 1 2 3
0 0 0 0
1 7 6 7
2 8 10 8
3 9 12 13
4 11 14 15
Tabla 1
Etapa 3:
x3 d3* f3*(x3)
$ disponibles para Decisión óptima Rendimiento
invertir
0 0 0
1 1 7
2 2 8
3 3 13
4 4 15
Tabla 2
Nótese que en la columna correspondiente a x3 hemos colocado todas
las alternativas posibles de dinero disponible para invertir; es decir, los
diferentes estados en los que podríamos encontrarnos al inicio de la
etapa.
En la columna correspondiente a d 3* identificamos la mejor decisión
frente a cada estado. En este caso, por ser la última etapa o último
proyecto, se decidirá invertir la totalidad del dinero disponible y, para
cada una de ellas, identificamos su resultado como f 3 (x3), esto es el
rendimiento obtenido.
Etapa 2:
194 CAPÍTULO 7
d2
x2 0 1 2 3 4 f2*(x2) d2*
0 0 0 0
1 0+7=7 6+0=6 7 0
2 0+8=8 6+7=13 10 13 1
3 13 14 17 12 17 2
4 15 19 18 19 14 19 1-3
Tabla 3
Etapa 1:
Al considerar la etapa 1, tengamos en cuenta que, como estamos al
inicio del proceso de decisión, el único estado posible es 4, es decir que
en este momento tenemos $4.000 disponibles para inversión.
d1
x1 0 1 2 3 4 f1*(x1) d1*
4 19 7+17=24 21 16 11 24 1
Tabla 4
Rendimiento máximo
Resumiendo:
d3 d2 d1
Donde:
fn (xn) = rendimiento en la etapa n para el estado xn
rn (dn) = rendimiento de la alternativa de inversión n, si decide invertir
dn
f*n+1(xn) = f*n+1 (xn – dn) = rendimiento óptimo para la etapa n, dado el
estado xn
PROGRAMACIÓN DINÁMICA DETERMINISTA 197
Rendimiento óptimo
para la etapa n dado Rendimiento Rendimiento
el estado xn = máx para la + óptimo de la
decisión dn etapa n+1
en adelante
3. CARACTERÍSTICAS COMUNES
Existe una serie de características que son comunes a la mayor parte de
las aplicaciones de programación dinámica, las que enumeramos y
analizamos en base al ejemplo presentado anteriormente.
El problema se puede dividir en etapas que requieren una política
de decisión en cada una de ellas. En el ejemplo, las etapas
estaban dadas por las diferentes alternativas de inversión. La
política de decisión fue elegir, en cada una, aquella que ofreciera
mayor rendimiento.
Cada etapa tiene un cierto número de estados asociados a ella.
En nuestro ejemplo, los estados asociados a cada etapa era el
dinero disponible para invertir.
198 CAPÍTULO 7
4. CONCEPTOS IMPORTANTES
En los modelos de PD, existen tres tipos de variables, a saber:
Variable de etapa: se trata de una variable ordenadora que representa
cada uno de los subproblemas en los cuales se divide un problema de
PD.
Variables de decisión (dn): representan a las acciones posibles a
tomar en la etapa n.
Variables de estado (xn): sirven de enlace entre las etapas,
describiendo la condición en que se encuentra el proceso al inicio de
cada una de ellas. Estas variables son las más difíciles de identificar.
Para facilitar este proceso, se deben realizar preguntas tales como ¿qué
PROGRAMACIÓN DINÁMICA DETERMINISTA 199
5. OTRAS APLICACIONES
5.1. Distribución de recursos
El Ministerio de Salud Pública está planeando una campaña de
vacunación contra la varicela para los meses de mayo, junio y julio.
Antes del periodo de vacunación, debe planificar su campaña de
publicidad televisiva. Cuenta con un presupuesto de $9 millones para
todo el período publicitario, que abarca el primer cuatrimestre del año.
El objetivo de la campaña es lograr un incremento significativo en la
cantidad de personas que conocen la enfermedad y la importancia de la
vacunación. Con datos de campañas anteriores, se elaboró una tabla
que refleja el número de personas dispuestas a vacunarse, de acuerdo
con lo invertido en publicidad relativa a difundir información sobre la
enfermedad.
Se ha impuesto la condición de que se invierta en publicidad por lo
menos $1 millón en cada mes.
200 CAPÍTULO 7
Gasto en
Enero Febrero Marzo Abril
publicidad
1 40 60 50 50
2 100 120 80 110
3 150 130 150 140
4 180 150 170 200
5 220 190 200 230
6 250 230 270 260
Tabla 6
¿Cómo deberá invertirse el presupuesto para maximizar el número de
personas dispuestas a vacunarse?
Resolución del problema
La característica particular de este problema es que deben asignarse
como mínimo $1 millón para publicidad en cada mes del periodo. Esto
hace que el monto máximo que puede destinarse a un mes en particular
es de $6 millones.
Las características fundamentales son:
1. El problema se puede dividir en subproblemas, en cada uno de ellos
debe tomarse una decisión. Cada subproblema corresponde a una
etapa en el proceso de resolución, en nuestro caso, un mes.
2. El número de personas dispuestas a vacunarse no es proporcional a
la cantidad de dinero invertido en publicidad.
3. Al principio de cada mes, el dinero disponible para invertir en
publicidad dependerá de lo invertido en los meses anteriores.
4. En cada mes, se debe invertir por lo menos $1 millón. Como
consecuencia, el dinero disponible al inicio de cada mes debe ser
suficiente para invertir $1 millón en ese mes y $1 millón en cada uno
de los meses subsiguientes.
5. En cada mes, como máximo, se puede invertir en publicidad hasta
$6 millones.
Corresponde ahora definir el objetivo y variables del problema.
Objetivo: maximizar el número de personas dispuestas a vacunarse.
Variables de etapa: cada uno de los próximos cuatro meses del primer
cuatrimestre del año.
Variables de decisión: las alternativas de decisión en la etapa i (di)
estarán representadas por el dinero destinado a publicidad en cada mes.
Variables de estado: para definir estas variables, nos preguntamos
¿qué información necesitamos para tomar decisiones factibles en la
etapa actual, sin reexaminar las decisiones que se tomaron en las
etapas anteriores? En otras palabras, ¿qué información necesito al inicio
de cada mes para decidir cuánto invertir en publicidad en ese mes?
Respondiendo esta pregunta, podemos decir que los estados en la etapa
i (xi) estarán representados por el dinero disponible al inicio del mes.
PROGRAMACIÓN DINÁMICA DETERMINISTA 201
Enero (etapa 1)
Dinero disponible $9 millones
Febrero (etapa 2)
Como mínimo, debe haber $3 millones, es decir, uno para cada uno de
los meses: febrero, marzo y abril.
Como máximo, pueden haber quedado $8 millones, dado que, por lo
menos, se invirtió $1 millón en enero.
Los estados se determinan como: x2 = x1-d1
Marzo (etapa 3)
Como mínimo, $2 millones, es decir, $1 millón para marzo y otro para
abril.
Como máximo, pueden haber $7 millones disponibles, que surgen de $9
millones iniciales menos $1 millón de enero y $1 millón de febrero.
Estados posibles: x3 = x2-d2
Abril (etapa 4)
Como mínimo, debe haber $1 millón.
Como máximo, pueden haber $6 millones disponibles.
Con la información anterior, podemos comenzar el análisis en reversa,
es decir, comenzando desde abril.
Estados posibles: x4 = x3-d3
Etapa 4 (abril)
En esta última etapa del proceso, las decisiones están completamente
determinadas por el objetivo, con lo cual la solución resulta ser trivial.
Así, como el objetivo es maximizar el número de personas que se
vacunarán, siempre se invertirá en publicidad todo el dinero disponible.
202 CAPÍTULO 7
x4 d4* f*4(x4)
$ disponibles para Decisión óptima Rendimiento
invertir (millones) (pers. vacunadas)
1 1 50
2 2 110
3 3 140
4 4 200
5 5 230
6 6 260
Tabla 7
Etapa 3 (marzo)
Debido a la restricción de invertir al menos $1 millón en cada mes, el
dinero disponible al inicio de marzo deberá ser por lo menos $2 millones
y como máximo $7 millones.
En el caso de tener $2 millones disponibles, la única decisión factible es
invertir $1 millón en marzo, ya que debemos dejar $1 millón para abril.
El rendimiento de marzo para el estado x3= 2 y la decisión d3= 1 estará
formado por el número de personas dispuesta a vacunarse por haber
invertido en marzo $1 millón más el número de personas dispuestas a
vacunarse por invertir en publicidad $1 millón en abril.
En fórmulas:
f (2) = r (1) + f * (2 -1) = 50 + 50 = 100
3 3 4
f3 (x3) = r (d3) + f4 (x3 – d3)
d3
1 2 3 4 5 6 d3* f*3(x3)
x3
2 50+50=100 1 100
3 50+110=160 80+50=130 1 160
4 50+140=190 80+110=190 150+50=200 3 200
5 50+200=250 80+140=220 150+110=260 170+50=220 3 260
6 50+230=280 80+200=280 150+140=290 170+110=280 200+50=250 3 290
7 50+260=310 80+230=310 150+200=350 170+140=310 200+110=310 270+50=320 3 350
Tabla 8
Etapa 2 (febrero)
En febrero, el dinero disponible para inversión podrá estar entre $3 a $8
millones.
Para el estado x2=5, las decisiones posibles serán d2=1, 2 o 3, ya que,
al menos, deberán quedar $2 millones para los meses siguientes.
El rendimiento, para x2=5 y d2=1 por ejemplo, se obtiene sumando el
rendimiento de invertir $1 millón en esta etapa más el óptimo si
PROGRAMACIÓN DINÁMICA DETERMINISTA 203
d2
1 2 3 4 5 6 d2* f*2(x2)
x2
3 60+100=160 1 160
4 60+160=220 120+100=220 1-2 220
5 60+200=260 120+160=280 130+100=230 2 280
6 60+260=320 120+200=320 130+160=290 150+100=250 1-2 320
7 60+290=350 120+260=380 130+200=330 150+160=310 190+100=290 2 380
8 60+350=410 120+290=410 130+260=390 150+200=350 190+160=350 230+100=330 1-2 410
Tabla 9
Etapa 1 (enero)
En enero, como estamos al inicio del periodo, el dinero disponible es el
total de $9 millones.
d1
1 2 3 4 5 6 d1* f*1(x1)
x1
9 40+410=450 100+380=480 150+320=470 180+280=460 220+220=440 250+160=410 2 480
Tabla 10
Inversión Rendimiento
Mes (millones de $) (personas)
Enero 2 100
Febrero 2 120
Marzo 3 150
Abril 2 110
Total $9 $ 480
Tabla 11
0 2 3 4 5 6
1 año
Hoy 2 años
3 años
5 años
Etapa 4: inicio del
cuarto año
Etapa 2:
De acuerdo con los resultados que muestran las tablas, para lograr el
beneficio de $28.800 en los próximos 4 años, comenzando con una
máquina de 2 años, la empresa tiene dos opciones. La primera opción es
conservar durante el primer año, reemplazar en el segundo año y
conservar hasta el final del quinto año; en tanto que la segunda opción
plantea reemplazarla el primer año, reemplazarla en el segundo año y
conservar hasta el final del quinto año.
Adoptando la siguiente simbología:
Ingreso = I(t)
Mantenimiento = M(t)
Costo de reemplazo = C(t)
Donde t representa a la edad del torno, la decisión óptima en la etapa n
se encuentra recursivamente como:
Mes 1 (etapa 1)
• Inventario al inicio = 10 unidades
• Capacidad máxima de producción = 50 unidades
• Demanda = 50 unidades
Teniendo en cuenta estas tres restricciones, podemos decir que,
partiendo de un inventario inicial de 10 unidades, produciendo a la
capacidad máxima y con una demanda de 50 unidades, el número
máximo de unidades que pueden quedar al final del mes es 10.
Mes 2 (etapa 2)
• Inventario máximo al inicio = 10 unidades
• Capacidad máxima de producción = 40 unidades
• Demanda = 30 unidades
Analizando las condiciones de la etapa notamos que, si comenzamos el
mes con el máximo posible de unidades en inventario (10) y producimos
a máxima capacidad (40), dado que la demanda es de 30 unidades,
como máximo nos pueden quedar 20 unidades al final del mes.
Mes 3 (etapa 3)
En este mes, iniciamos con 20 unidades en inventario como máximo y
debemos tener presente que la empresa no quiere inventarios al final
del trimestre, es decir que Inventario Final = 0.
El análisis anterior puede observarse gráficamente en la figura
siguiente:
d1 d2 d3
x1 x2= x1 + d1 - D1
Etapa 1 Etapa 2 x3= x2 + d2 – D2 Etapa 3
D1 D2 D3
210 CAPÍTULO 7
Etapa 3
En esta etapa, debemos considerar:
• Demanda (D3) = 40 unidades
• Capacidad de Producción = 50 unid.
• Máximo inventario al inicio = 20 unid.
• Inventario Final = 0 unid.
• x3 = x2 + d2 – D2
• f*3(x3) = 0,20 (x3) + 2 (d3)
x3 d3* f*3(x3)
0 40 80
10 30 62
20 20 44
Etapa 2
Consideraciones:
• Demanda (D2) = 30 unid.
• Capacidad de Producción = 40 unid.
• Máximo inventario al inicio = 10 unid.
• x2 = x1 + d1 – D1
• f2(x2, d2) = 0,30 (x2) + 1,5 (d2)+f*3(x2 + d2 – D2 )
• f*2(x2) = min f2(x2, d2)
d2
20 30 40 d*2 f*2(x2)
x2
45+80 60+62
0 NO FACTIBLE 40 122
=125 =122
3+30+80 3+45+62 3+60+44
10 40 107
=113 =110 =107
Tabla 18
Etapa 1
Consideraciones:
• Demanda (D1) = 50 unid.
• Capacidad de Producción = 50 unid.
• Inventario Inicial (x1) = 10 unid.
• f1(x1, d1) = 0,30 (10) + 2 (d1)+f*2(10 + d1 – D1 )
• f*1(x1) = min f1(x1, d1)
d1
40 50 d*1 f*1(x1)
x1
Recuerde que:
Inventario Inicial 3+80+122 3+100+107
xn = xn-1+dn-1-Dn-1 10 40 205
= 205 = 210
Tabla 19
PROGRAMACIÓN DINÁMICA DETERMINISTA 211
Probabilidad de reprobar
Días
Álgebra Economía Sociología
0 0,60 0,45 0,30
1 0,50 0,40 0,25
2 0,40 0,35 0,15
3 0,35 0,20 0,10
4 0,15 0,15 0,05
Tabla 21
Etapa 3 (Sociología)
x3 d3* f3*(x3)
0 0 0,30
Verifique los cálculos
para las tres etapas. 1 1 0,25
2 2 0,15
3 3 0,10
4 4 0,05
Tabla 22
Etapa 2 (Economía)
d2
0 1 2 3 4 d2* f2*(x2)
x2
0,45(0.3)=
0 0 0,135
0,135
0,45(0,25)= 0,4(0,3)=
1 0 0,12
0,1125 0,12
0,45(0,15)= 0,4(0,25)= 0,35(0,3)=
2 0 0,0675
0,0675 0,10 0,105
0,45(0,1)= 0,4(0,15)= 0,35(0,25)= 0,2(0,3)=
3 0 0,045
0,045 0,06 0,0875 0,06
0,45(0,05)= 0,4(0,1)= 0,35(0,15)= 0,20(0,25)= 0,15(0,3)=
4 0 0,0224
0,0225 0,04 0,0525 0,05 0,045
Tabla 23
Etapa 1 (Álgebra)
d1
0 1 2 3 4 d1* f1*(x1)
x1
0,6(0,0225)= 0,5(0,045)= 0,4(0,0675)= 0,35(0,1125)= 0,15(0,135)=
4 0 0,0135
0,0135 0,0225 0,027 0,0394 0,02025
Tabla 24
Mínima probabilidad
de falla en los tres
exámenes
RECOMENDACIONES ÚTILES:
Defina primero las variables de decisión, teniendo presente el logro
del objetivo.
Defina ahora las etapas, considerando que debe tomar una decisión
para cada etapa. Esto le permitirá identificar a cada uno de los
subproblemas.
Para identificar a las variables de estado, hágase preguntas tales
como ¿qué es lo cambia de una etapa a otra?, ¿qué información se
necesita para identificar la política óptima de aquí en adelante?,
¿cómo se puede describir la situación actual?
Quizás esta sea la recomendación más importante: dividir el
problema en subproblemas es solo una estrategia de solución; si
usted no los enlaza, no logrará la optimización global.
214 CAPÍTULO 7
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
Emergencias Córdoba ha adquirido 6 nuevas ambulancias con el objetivo
de reducir sus tiempos de llegadas al momento de producirse una
urgencia médica. Debe distribuirlas entre 3 de sus bases, entregándole
por lo menos una a cada una.
Con el fin de tomar la mejor decisión posible, se ha hecho una
estimación de los tiempos promedio de llegada para cada asignación
posible de las nuevas unidades, la que se presenta en la siguiente tabla.
1 2 3 4
Base 1 5 4 2 1
Base 2 4 3 2 1
Base 3 5 4 3 1
ACTIVIDAD 2
Para mejorar sus ingresos, Tomás ha decido destinar parte del terreno
de su granja para sembrar vegetales. Planea plantar tres tipos de ajíes:
verdes, rojos y amarillos. El huerto, que mide 10 x 20, está dividido en
hileras de 20 metros de largo cada una. Las hileras de ajíes verdes y
rojos tienen dos metros de ancho cada una, y las de pimientos amarillos
deben ser de tres metros de ancho. Debido a la diferente productividad
de las plantas, Tomás ha estimado que cada hilera de ajíes verdes le
producirá un ingreso de $100 y el ingreso de cada hilera de ajíes rojos y
amarillos será de $70 y $50 respectivamente. Ha decidido, además, que
deberá plantar por lo menos una hilera de ajíes verdes y no más de tres
de los amarillos.
a) Utilice la programación dinámica para determinar cuántas hileras de
cada tipo de ají debe plantar Tomás para maximizar sus ingresos.
b) Identifique la fórmula recursiva utilizada.
ACTIVIDAD 3
Una estudiante universitaria tiene 7 días para preparar los exámenes
parciales de 4 cursos y quiere asignar el tiempo que tiene para estudiar
de la manera más eficiente posible. Necesita por lo menos un día para
cada curso y quiere concentrarse solo en un curso cada día. Como hace
PROGRAMACIÓN DINÁMICA DETERMINISTA 215
ACTIVIDAD 4
Una empresa de aparatos electrónicos tiene un contrato para entregar el
siguiente número de placas de video durante los tres meses siguientes:
MES 1 2 3
N° de unidades 400 300 200
ACTIVIDAD 5
La empresa CompuTar SA, fabricante de procesadores para
computadoras, quiere determinar el programa anual de producción e
inventario que maximice su contribución total. La información relevante
del problema se da en la siguiente tabla:
216 CAPÍTULO 7
ACTIVIDAD 6
Julián debe armar un dispositivo electrónico de control. El dispositivo
está formado por 3 componentes en serie, de manera que la falla en
uno alguno de los componentes origina la falla en el dispositivo. Se
puede mejorar la confiabilidad del dispositivo de control instalando, en
paralelo, una o dos unidades de reserva para cada uno de los
componentes. De esta manera, ante la falla de uno de los componentes,
entra en funcionamiento la unidad de reserva. En la figura se muestra
esta situación:
Comp. 1 Comp. 2 Comp. 3
UR 1 UR 1 UR 1
UR 2 UR 2 UR 2
1. INTRODUCCIÓN
En numerosos problemas, las funciones o relaciones matemáticas que
intervienen no son necesariamente lineales. De hecho, tal vez se puede
decir que los problemas del mundo económico y empresario que se
ajustan totalmente a la linealidad son la excepción y no la regla.
Entre los supuestos del modelo de PL que comúnmente no se cumplen y
originan programas no lineales (PNL), se pueden mencionar:
• Aditividad. Es decir que las contribuciones de dos o más variables
al objetivo o a las restricciones funcionales no son independientes
entre sí. En forma general, podríamos decir que el total no es igual
a la suma de las partes, y esto se da cuando existe una interacción
entre las variables, por ejemplo, cuando se mezclan sustancias
químicas en la elaboración de un producto.
• Proporcionalidad. Este supuesto no se cumple en problemas en
los cuales, por ejemplo, el ingreso obtenido por la venta de un
producto no es proporcional a las unidades vendidas, ya que esta
cantidad está en función del precio, el que será, en estos casos,
una variable de decisión. Otro ejemplo del no cumplimiento de esta
hipótesis se da cuando demasiados operarios son asignados para
realizar una tarea, el rendimiento de cada trabajador puede
disminuir en lugar de mantenerse constante, es decir que existen
deseconomías o economías de escala.
En resumen, la existencia de diferentes tipos de relaciones, sean de
carácter económico, lógico, físico, estructural, etc., puede dar lugar a la
aparición de características de no linealidad en un modelo matemático.
Es importante destacar que, aunque los fenómenos no lineales son
comunes, la posibilidad de lograr la optimización de estos modelos es
mucho más difícil que en los modelos lineales y que los algoritmos
desarrollados para su resolución son menos eficientes. Así, a diferencia
de la PL, no se puede asegurar que un algoritmo de resolución de PNL
logrará siempre encontrar la solución óptima para cualquier problema.
Además, en muchos casos, mediante PL se pueden obtener buenas
aproximaciones a los modelos no lineales. Esto, conjuntamente con la
218 CAPÍTULO 8
2. CARACTERÍSTICAS GENERALES
De la misma manera que en PL, un problema de PNL, cuando tiene solo
dos variables de decisión, puede representarse gráficamente. Esto nos
será particularmente útil para mostrar algunas características de las
soluciones óptimas, a saber:
La región factible no necesariamente es un poliedro, como en el caso
de la PL, y la solución óptima puede no encontrarse en un vértice.
Recordemos que, en el caso de programación lineal, el análisis gráfico
permite identificar las restricciones limitantes en el vértice óptimo y la
solución óptima se obtiene resolviendo el sistema de dos ecuaciones
con dos incógnitas formado por estas restricciones. En general, este
método no funciona para el caso no lineal. A título ilustrativo,
observemos el siguiente gráfico:
x2
Región factible
Función objetivo
El óptimo no está
en un vértice
x1
Gráfico 1
Función objetivo
Región factible
x1
Gráfico 2
Gráfico 3
220 CAPÍTULO 8
f(x) Cóncava
f(x)
Convexa
-1 x
f(x) Convexa
x1, f(x1)
x2, f(x2)
x1 x2 x
Gráfico 7
222 CAPÍTULO 8
Programación separable
Se agrega el supuesto adicional de que todas las funciones f(x) y g i(x)
son separables.
Una función es separable cuando cada término solo incluye una variable,
por lo que puede expresarse como una suma de funciones de distintas
variables. Este tipo de problemas satisface el supuesto de aditividad, pero
no el de proporcionalidad.
Por ejemplo, la función
f(x1, x2) = -10x12 + 20x22 + 50 x1 - 25x2
puede expresarse como
f(x1, x2) = f(x1) + f(x2)
Donde
f(x1) = -10x12 + 50 x1
f(x2) = 20x22 - 25x2
4. MULTIPLICADOR DE LAGRANGE
Una semejanza entre la PL y la PNL es la posibilidad de utilizar, al menos
parcialmente, el análisis de sensibilidad. Sabemos que, en PL, un
incremento en el valor del lado derecho (bi) de la i-esima restricción
produce un incremento en el valor óptimo de la función objetivo igual a
(yi.bi) (siendo yi la variable dual correspondiente), siempre que el
incremento del lado derecho se mantenga dentro de un cierto intervalo,
en el cual la variable dual permanece constante. En PNL, este concepto
se conoce como multiplicador de Lagrange1; al igual que las variables
duales, existe un multiplicador de Lagrange por cada restricción y
usualmente se lo simboliza como i. Sin embargo, los multiplicadores de
Lagrange, por lo general, se van modificando al variar el incremento del
valor del lado derecho de la restricción a la cual corresponden. Por esta
razón, su interpretación económica indica que, en el punto óptimo, el i-
ésimo multiplicador de Lagrange representa cuánto crecería el valor
óptimo de la función objetivo por cada unidad de crecimiento del lado
derecho de la i-esima restricción, bajo la hipótesis de que la misma siga
creciendo con la misma fuerza o intensidad con que está creciendo en ese
punto. En general, esta hipótesis no se cumple, dado el carácter no lineal
de la función objetivo y/o de las restricciones. Esta interpretación
proviene del hecho que, matemáticamente, los multiplicadores de
Lagrange, al igual que las variables duales, son las derivadas parciales de
la función objetivo con respecto a un bi.
Ejemplo 1
Una fábrica elaborará un producto cuyo proceso productivo pasa
fundamentalmente por dos máquinas. Definimos como x1 a la cantidad de
producto fabricada en la máquina 1 y x2 a la cantidad de producto
fabricada en la máquina 2.
Los costos de producción del producto, según sea la máquina en la cual
se procese, están dados por las siguientes funciones:
a1 x1 + b1 x12 = costo de producción en la máquina 1
a2 x2 + b2 x22 = costo de producción en la máquina 2
Podemos formular un modelo que permita encontrar las cantidades a
producir en cada máquina para minimizar el costo total de producción
1
Este nombre proviene del conocido método de los multiplicadores de Lagrange para el
cálculo de máximos o mínimos locales de funciones de n variables sujetas a m restricciones
dadas bajo la forma de ecuaciones. Más recientemente (a mediados del siglo XX), Kuhn y
Tucker generalizaron estos conceptos para el caso que existan restricciones bajo la forma
de inecuaciones.
PROGRAMACIÓN NO LINEAL 225
Ejemplo 2
El presupuesto disponible para producir tres bienes es de R pesos.
Supongamos que p1, p2 y p3 son los precios de cada bien y que la utilidad
derivada de producir x1 unidades del bien 1, x2 unidades del bien 2 y x3
unidades del bien 3 la representamos como x1K1 + x2K2 + x3K3, siendo K1,
K2 y K3 constantes previamente determinadas.
Podemos encontrar la mezcla de producción que maximice la utilidad,
respetando la restricción presupuestaria, formulando el modelo no lineal:
Max Z = x1K1 + x2K2 + x3K3
s.a.
p1 x1 + p2 x2 + p3 x3 ≤ R
x1, x2, x3 0
Ejemplo 3
Una empresa desea optimizar la asignación presupuestaria en publicidad.
Dispone, en promedio, de $1.000 por día y se asigna su totalidad a
comerciales en TV y/o anuncios en periódicos. El costo total anual que
paga en publicidad se ha estimado en:
C (x1, x2) = 2 x12 + 1,2 x22 + x1 x2
Siendo:
x1: pesos promedio diarios gastados en anuncios en televisión.
x2: pesos promedio diarios gastados en anuncios en periódicos.
El modelo a resolver tiene la siguiente estructura:
Min Z = 2 x12 + 1,2 x22 + x1 x2
s.a.
x1 + x2 = 1000
x1 0, x2 0
La salida del software Solver de este problema se muestra en la tabla 1.
Podemos observar que el multiplicador de Lagrange indica que el
incremento total anual del costo en el departamento de publicidad sería
de $1.954,54 aproximadamente por cada peso adicional de presupuesto
gastado en anuncios. Sin embargo, como dijimos anteriormente, no es
226 CAPÍTULO 8
posible decir sobre qué rango de aumento o disminución del VLD es válido
dicho multiplicador. Incluso podríamos afirmar que posiblemente dicho
incremento sea variable a medida que se modifica el presupuesto para
anuncios. Por su parte, los valores del gradiente reducido incluidos en el
informe de sensibilidad de PNL tienen una interpretación análoga a la de
los valores de costo reducido en PL.
1 n t
Ri = Ri
n t =1
Los rendimientos históricos periódicos Rit se utilizan también para estimar
las varianzas y covarianzas.
1 n
( )
2
Rit − R i es la varianza del rendimiento para el activo i
n t =1
También se define:
b = límite inferior del rendimiento esperado de la cartera
Si = límite superior de la fracción del activo i que puede estar en la
cartera
En función de los parámetros, la formulación de esta programación
cuadrática para el modelo de tres activos es
Min. x2 X2 + y2 Y2 + z2 Z2 + 2 xy XY + 2 xz XZ + 2 yz YZ
S.a.
RxX + RyY + RzZ b
X+Y+Z=1
X Sx
Y Sy
Z Sz
X, Y, Z 0
Supongamos tres acciones y sus rendimientos históricos para 12 años.
Llamaremos A, B y C a los tres tipos de acciones elegidas. Los
rendimientos históricos se muestran en la tabla siguiente.
Tabla 3
COVARIANZAS
A B C
A
B 0,01071706
C 0,01010352 0,03050009
Tabla 4
Solución de Solver
Celdas de variables
Nombre Valor final
% en acciones A 52,27 %
% en acciones B 35,12 %
% en acciones C 12,61 %
Restricciones
Valor de la
Nombre celda
% en acciones Ttotal 100,00 %
Rendimiento esperado total 15,00 %
Máximo % en acciones A 52,27 %
Máximo % en acciones B 35,12 %
Máximo % en acciones C 12,61 %
Tabla 5
232 CAPÍTULO 8
Celdas de variables
Final Gradiente
Nombre valor reducido
% en acciones A 0,522686472 0
% en acciones B 0,351227381 0
% en acciones C 0,126086147 0
Restricciones
Final Multiplicador
Nombre valor Lagrange
% Total en acciones 1 0,000516256
Rendimiento esperado total 15 % 0,222895544
Tabla 6
•
•
Rendimiento
esperado
XR
i=1
i i
X σ
i=1
2
i
2
i +2 XX σ
i=1 j=i+1
i j ij
S.a:
n
XR
i=1
i i bi
Xi 0
234 CAPÍTULO 8
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
RESPONDA LAS SIGUIENTES PREGUNTAS:
1. ¿Existe alguna similitud conceptual entre las variables duales de la
programación lineal y los multiplicadores de Lagrange de la
programación no lineal? En caso de una respuesta afirmativa, explique:
a) cuáles son las semejanzas; b) cuáles son las diferencias.
2. Dado un programa matemático, con variables continuas, cuya función
objetivo es no lineal, sujeta a restricciones dadas por ecuaciones y/o
inecuaciones lineales, responda a las siguientes preguntas justificando
su respuesta:
a) ¿El conjunto de soluciones posibles es siempre un conjunto
convexo?
b) ¿El conjunto de soluciones óptimas (si existe más de una) es
siempre un conjunto convexo?
c) ¿Siempre existirá una solución óptima en un punto extremo
(vértice) del conjunto de soluciones posibles?
d) ¿Siempre toda solución óptima será un punto de la frontera del
conjunto de soluciones posibles?
e) ¿Nunca un punto interior del conjunto de soluciones posibles puede
corresponder a un óptimo?
f) Si la función objetivo es cóncava: i) ¿Todo máximo relativo o local
es también un máximo absoluto o global?; ii) ¿todo mínimo
relativo o local es siempre un mínimo absoluto o global?
g) Si la función objetivo es convexa: i) ¿Todo máximo relativo o local
será también un máximo absoluto o global?; ii) ¿todo mínimo
relativo o local es también un mínimo absoluto o global?
ACTIVIDAD 2
Una fábrica de amortiguadores produce dos modelos a los que
denominaremos Modelo A y Modelo C. Hay dos líneas de producción, una
para cada modelo, e intervienen dos departamentos en la producción de
cada modelo. La capacidad de la línea de producción del Modelo A es de
450 amortiguadores por día. La capacidad de producción del Modelo C es
de 520 amortiguadores diarios. En el departamento 1, se fabrican los
componentes. En este departamento, se requiere de tres horas de trabajo
para cada amortiguador Modelo A y dos horas por cada unidad del Modelo
C. En la actualidad se dispone de 20 trabajadores con una jornada laboral
de 8 horas. En el departamento 2, se ensamblan los componentes y se
hacen las pruebas de calidad del producto. Aquí se requiere de una hora
de trabajo para cada Modelo, en este departamento hay 10 operarios.
PROGRAMACIÓN NO LINEAL 235
ACTIVIDAD 3
Una cooperativa que produce electricidad enfrenta demandas de energía
en periodos que pueden denominarse de horas pico y periodos de
consumo reducido. Si el precio durante las horas pico es de $p 1 por kwh,
los clientes demandarán (185 – 1,25 p1) kwh de potencia. Si durante las
horas de consumo reducida se cobra un precio de $p 2, entonces los
clientes demandan (150 – p2) kwh. La cooperativa eléctrica debe tener la
capacidad suficiente para satisfacer la demanda durante las horas de
consumo máximo y de consumo reducido. Cuesta $150 por día mantener
cada kwh de capacidad. Determine cómo la cooperativa eléctrica puede
maximizar los ingresos diarios menos los costos de operación.
ACTIVIDAD 4
Una empresa utiliza una cierta materia prima para elaborar dos tipos de
productos. Se necesitan 0,5 unidades de MP y 2 horas de mano de obra
(HMO) para elaborar un producto 1, por cada unidad de producto 2 se
necesitan 1 unidad de MP y 3 HMO; mensualmente se dispone de 500
HMO. Actualmente tiene 100 unidades de materia prima, pero puede
comprar más a un costo de $150 por unidad.
Si se fabrican X1 unidades de producto 1, entonces cada unidad se puede
vender a $(80–2X1); si se producen X2 unidades de producto 2, entonces
cada unidad se puede vender en $(60 – 1X2).
¿Cuál debe ser el plan de producción?
¿Cuánto es el precio máximo que la fábrica estaría dispuesta a pagar por
una unidad extra de materia prima?
236 CAPÍTULO 8
ACTIVIDAD 5
La empresa K&C está planificando la campaña publicitaria de su nuevo
producto, el perfume Armony. Con esta finalidad, quiere contratar
anuncios en la radio y/o comerciales en televisión de 2 minutos de
duración. Cada anuncio en la radio cuesta $300, el costo del minuto
televisivo es de $350. Si se compran x1 anuncios en radio, serán
escuchados por 4x1 miles de potenciales clientes hombres y 1x12 miles de
potenciales clientes mujeres. Si se compran x2 comerciales de TV, serán
vistos por 2(3 x2 ) miles de hombres y 4( x2 ) miles de mujeres. La
empresa quiere que, por lo menos, 200.000 hombres y 300.000 mujeres
vean sus anuncios a un mínimo costo.
ACTIVIDAD 6
Una fábrica utiliza el compuesto AZ10 para elaborar dos tipos de
fertilizantes: Jardín Verde y Bello Parque. Puede comprar hasta 700 kg
del compuesto a $50 por kg. Con un kg de AZ10 puede obtenerse un kg
de Jardín Verde a un costo de $75 o un kg de Bello Parque a un costo de
$90. Si se producen X1 kg de Jardín Verde, este se vende a un precio de
$(270 – 2X1) por kg. Si se producen X2 kg de Bello Parque, este se vende
a un precio de $(150 – X2) por kg. ¿Cuánto debería producirse de cada
fertilizante para maximizar la ganancia?
ACTIVIDAD 7
Una empresa utiliza una cierta materia prima para elaborar dos tipos de
productos. Cada kg de materia prima rinde 500 g de producto A y 200 g
de producto B. Actualmente tiene disponibles 150 kg de materia prima.
En la producción se utiliza una máquina que tiene disponible 200 horas,
se necesitan 2 horas para procesar cada kg de producto A y 3 horas por
cada kg de producto B.
Si se fabrican x1 kg de producto A, entonces cada kg se puede vender a
$(500 – 3 x1 ); el precio de venta del producto B es de $95 por kg.
¿Cuál debe ser el plan de producción?
ACTIVIDAD 8
La siguiente tabla muestra los precios históricos al 31/12 de las acciones
de Acindar, Molinos y Ledesma entre los años 1992 y 2004.
ACTIVIDAD 9
La siguiente tabla muestra los precios históricos al 31/12 de las acciones
de Banco Francés, Minetti y Renault, entre los años 1992 y 2004.
238 CAPÍTULO 8
OPTIMIZACIÓN Y PLANIFICACIÓN
CON GRAFOS
1. INTRODUCCIÓN
Existen otros tipos de problemas en los cuales la teoría de redes puede ser
muy útil al decisor, valgan como ejemplo las dos situaciones que mostramos
a continuación.
Damián se encuentra en General Cabrera, necesita enviar un camión con
mercadería a Cruz Alta y quiere seleccionar una ruta cuyo kilometraje total
sea el mínimo posible.
GRAFO O RED
Definiremos grafo o red a un par ordenado del tipo (X,U), donde X es un
conjunto finito a cuyos elementos llamaremos vértices o nodos de la red, y
U representa una relación binaria entre los elementos del conjunto X, es
decir,
U X2 = {(xi, xj)/ xiX xjX}
U + xi = x j /( x i , x j ) U
242 CAPÍTULO 9
U - x j = x i /( x i , x j ) U
Otra forma de definir una red es mediante el par ordenado (X, ), donde
es una aplicación del conjunto X en el conjunto (X) llamado “partes de
X”.
El conjunto partes de X está compuesto por todos los subconjuntos que
se pueden formar a partir de X. incluyendo al conjunto vacío y el propio
conjunto X, al que denominaremos conjunto A
: X →(X)
(X) = A / A X
Así, para un elemento cualquiera xi X, esta aplicación relaciona a dicho
elemento con un único conjunto de vértices que es su imagen. Este
conjunto está integrado por los vértices finales de todos los arcos que
tienen como vértice inicial a xi:
xj ( xi ) (xi , xj ) U
En la red del ejemplo, tendríamos:
(x1) = {x3, x5, x7}
(x2) = {x4}
(x3) = {x1, x2}
(x4) = {x3}
(x5) = {x1}
(x6) =
(x7) = {x4, x6}
En forma similar, -1(xj) estará integrado por los vértices iniciales de todos
los arcos que tienen como vértice final a xj
xi -1
( xj ) (xi , xj ) U
Aclaremos que la
función -1(xj) no es Así:
la inversa de (xi)
-1
(x1) = {x3, x5}
-1(x2) = {x3}
-1(x3) = {x1, x4}
-1(x4) = {x2, x7}
-1(x5) = {x1}
-1(x6) = {x7}
-1(x7) = {x1}
Gráfico 1
TEOREMA DE LA OPTIMIDAD
Este teorema tiene su origen en la programación dinámica, propuesto por
Richard Bellman, bajo el nombre de principio de optimidad. Con
posterioridad se adaptó el mismo a la teoría de redes. Es importante
destacar que en él se basan la mayoría de los métodos utilizados en la
determinación de caminos de valuación óptima (mínima o máxima), como
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 245
ALGORITMO DE DIJKSTRA
El algoritmo está diseñado para identificar los caminos de valor mínimo
que unen el vértice origen con cada uno de los nodos del grafo.
Consiste en establecer una etiqueta a cada nodo de la red, la que luego
de sucesivas actualizaciones, contendrá el valor del camino de valor
mínimo que une el nodo inicio del grafo con el nodo considerado y el
vértice precedente en dicho camino.
Para etiquetar cada uno de los nodos se procede de la siguiente forma:
Paso 1: Considere todos los vértices que estén conectados con el origen
por un camino de longitud 1. A cada uno de ellos se le colocará una etiqueta
de la siguiente forma: [ j , d ]
El componente d de la etiqueta mide la distancia desde el origen al nodo
considerado (i). El otro componente (j) es el nodo precedente, el origen en
este caso. Estas etiquetas serán temporales.
Paso 2: De todos los nodos con etiqueta temporal, se elige uno cuya
componente de distancia sea la menor y se lo etiqueta como permanente.
Los empates se rompen arbitrariamente. Cuando todos los nodos son
permanentes se pasa al Paso 4.
Paso 3: Si i es el último etiquetado permanente considere todos los vértices
que estén conectados directamente con éste a través de un camino de
longitud 1, siempre y cuando no estén etiquetados como permanentes. Para
cada uno de ellos calcular la suma de su distancia a i más la distancia de la
etiqueta de i.
246 CAPÍTULO 9
2 1
4
5 3
3
1 3 3 6
3 1
3 5
4
Gráfico 2
Los empates se
resuelven El primer paso del método consiste en identificar a todos los nodos que
arbitrariamente.
estén conectados con el origen por un camino de longitud 1. En este caso
son los vértices 2 y 3. A ellos les colocamos una etiqueta temporal.
Luego, siguiendo con el paso 2 de todos los nodos con etiqueta temporal,
se selecciona el que tiene menor componente de distancia y se lo etiqueta
como permanente. En el gráfico 3 el nodo permanente está marcado más
oscuro. [1 , 5]
2 1
4
5 3
3
1 3 3 6
3 1
3 5
4
[1 , 3]
Gráfico 3
[1 , 5]
[2 , 6]
2 1
4
5 3
3
1 3 3 6
3 1
3 5
4
[1 , 3] [3 , 7]
Gráfico 4
3 1
3 5
4
[1 , 3] [3 , 7]
Gráfico 5
3 1
3 5
4 [3 , 7]
[1 , 3]
Gráfico 6
Gráfico 7
Cuando ya no quedan nodos por investigar, procedemos a identificar el
camino de valor mínimo a través del análisis de las etiquetas de cada vértice
como lo indica el paso 4. Esto se muestra en el gráfico 8.
248 CAPÍTULO 9
1 6
3 1
3 5
4
Gráfico 8
Para este grafo el camino de valor mínimo por los arcos es:
= {(1, 3), (3, 5), (5, 6)} y el valor del camino es v() = 8
Un Árbol de expansión es una subred conexa que incluye a todos los nodos
Ciclo: secuencia de de la red y no contiene ciclos no dirigidos. Todo árbol de expansión tiene
arcos que tiene el
mismo nodo inicio
exactamente n-1 arcos, ya que este es el número mínimo de arcos
y fin. necesarios para tener un grafo conexo y el máximo número posible para
que no haya ciclos no dirigidos.
B
D No es un árbol de expansión
ya que no hay conexión
A F
entre todos los nodos
C E
Gráfico 9
B
D
Hay conexión, pero tiene
A F ciclos, entonces no es un
árbol.
C E
Gráfico 10
B
D
Es un árbol de expansión porque
A F tiene n-1 aristas y ningún ciclo.
C E
Gráfico 11
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 249
Ejemplo:
Encontrar el árbol de expansión mínima del siguiente grafo.
250 CAPÍTULO 9
6
B
2 E
2 4
A 4
5
1 G
D
4 3
1 8
F
C
5
Gráfico 12
4
A 5
1 G
D
4 3
1 8
F
C
5
Gráfico 13
4
A 5
1 G
D
4 3
1 8
F
C
5
Gráfico 14
4
A 5
1 G
D
4 3
1 8
F
C
5
Gráfico 15
El nodo conectado a A, B, D o C con arista de menor valor es F(con
respecto a D), lo conectamos a D
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 251
6
B
2 E
2 4
4
A 5
1 G
D
4 3
1 8
F
C
5
Gráfico 16
4
A 5
1 G
D
4 3
1 8
F
C
5
Gráfico 17
4
A 5
1 G
D
4 3
1 8
F
C
5
Gráfico 18
Gráfico N° 19
252 CAPÍTULO 9
Actividades Precedencias
A -
B A
C A
D B
E C
F DyE
Tabla 1
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 253
B D
A
F
C E
Gráfico N° 19
A F
1 2 5 6
Gráfico N° 20
1
Para el desarrollo de CPM/PERT por el método de arcos actividades, puede consultarse en
Giuliodori R. (1999)
254 CAPÍTULO 9
i Di
MIi MFi
MIi* MFi*
DT Di μ Cˆ
iμ
ACTIVIDADES CRÍTICAS
Las actividades que no admiten demoras en su ejecución, son llamadas
actividades críticas.
Observemos que las actividades críticas son aquellas que cumplan con la
condición:
MIi = MIi* MFi = MFi*
Al camino formado por estas tareas se lo conoce como camino crítico, lo
simbolizamos por * y es el camino de valor máximo que une el vértice
Inicio con el vértice Fin.
EJEMPLO DE APLICACIÓN
Supongamos que el siguiente proyecto simplificado, muestra la
operación de lanzamiento al mercado de un nuevo producto:
Tabla 2
Para calcular los momentos MIi, MIi*, MFi y MFi* de cada actividad se
puede trabajar sobre la gráfica de la red:
El primer paso consiste en representar el proyecto en un grafo, para luego
calcular, para cada nodo, los momentos de inicio y fin más tempranos y
más tardíos.
Vamos a adoptar como convención colocar siempre un nodo Inicio y un
nodo Fin.
Asimismo nombraremos como actividades iniciales a aquellas que no
tienen ninguna precedente, y se conectarán directamente con el nodo
Inicio.
Llamaremos tareas finales a las que no preceden a ninguna otra, es decir
tienen ninguna siguiente y éstas se conectarán directamente con el nodo
Fin.
E
D 10
B 30
I 1 J 1 Fin 0
Inicio 0 A 15
F
H
C 8 G 5
Gráfico N° 21
Inicio 0 A 15
0 0 0 15
Gráfico N° 22
Inicio 0 A 15
0 0 0 15
C 8
15
Gráfico N° 23
Inicio 0 A 15
0 0 0 15
C 8
15 23
Gráfico N° 24
Para calcular el MID, cmo tiene más de una precedente, comparamos MFB
y MFC, el máximo de ellos será el MID.
45 D 10
B 30 45
15 45
23
Inicio 0 A 15
0 0 0 15
C 8 G
15 23
Gráfico N° 25
Es decir que MID = máx {MFB, MFC}, recordemos que para que una
actividad pueda iniciarse deben estar finalizadas todas sus precedentes.
260 CAPÍTULO 9
J 1 Fin 0
65 66 66 66
66 66
Gráfico N° 26
Ahora vamos a recorrer la red desde el Fin al nodo Inicio calculando para
cada actividad los momentos MF* y MI*.
Para las actividades que poseen una única actividad siguiente el momento
más tarde de finalización permitido es igual al momento más tarde de
inicio de la tarea siguiente.
Así para la actividad I el MFI* = 65 ya que J es la única actividad siguiente
a I.
I 1 J 1 Fin 0
64 65 65 66 66 66
65 65 66 66 66
Gráfico N° 27
Gráfico N° 28
Para las actividades que tienen más de una tarea siguiente, el momento
más tarde en que debe estar finalizada es igual mínimo de los momentos
más tardes de inicio de las actividades siguientes.
Así vemos que:
MFC* = mín { MID*, MIG*}
45 D 10
B 30 45 55
15 45 45 55
23
45
C 8 G 5
15 23 57 23 28
45 57 62
Gráfico N°29
Igualmente para A el MFA* = mín { MIB*, MIC*} y su MIA*= MFA*- DA
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 261
B 30
15 45
15 45
Inicio 0 A 15 15
0 0 0 15
37
0 15
C 8
15 23
37 45
Gráfico N° 30
Inicio 0 A 15 1
0 0 0 15
0 0 0 15
Gráfico N° 31
B 30 D 10 E 7
15 45 45 55 55 62 I 1 J 1 Fin 0
Inicio 0 A 15 15 45 45 55 55 62 64 65 65 66 66 66
0 0 0 15 64 65 65 66 66 66
0 0 0 15 C 8 F 5
15 23 55 60
37 45 G 5 57 62 H 2
23 28 62 64
57 62 62 64
Gráfico 32
DT = 66 días
* = {A, B, D, E, H, I, J}
Tabla 3
DT N E (Di ) ; V (Di )
i* i *
2
Para más información sobre esta discusión consultar a Pérez Mackeprang et al 1996.
264 CAPÍTULO 9
V(DT) = V(D ) i
i*
____
Una vez calculado DT y V(DT), es necesario realizar un análisis posterior,
con el fin de evaluar probabilísticamente el tiempo de terminación del
proyecto. Para ello se trabaja con el supuesto establecido en la hipótesis
7, calculando por ejemplo, la probabilidad que el proyecto se retrase
cierto plazo establecido previamente, con respecto al valor medio, o bien
determinar el tiempo de finalización para un nivel de confianza dado.
EJEMPLO DE APLICACIÓN
De un proyecto complejo se desconoce la distribución de probabilidad de
la duración de sus actividades, no obstante se pueden estimar los tiempos
optimista, normal y pesimista, los cuales se muestran en la siguiente
tabla.
Se desea calcular el tiempo mínimo esperado de finalización del proyecto.
Obsérvese que en la tabla siguiente, se calculó la media, varianza y
desviación estándar de la duración de cada actividad (Di) a partir de las
fórmulas propuestas en la Hipótesis 5.
Gráfico 33
V(DT) = i = 1 + 4 + 4 = 9
2
DT = = 2
i
9 =3
i* i *
DT = 3
19 DT
Gráfico 34
estandarizando la variable DT :
__
DT0 - DT 24 -19 = Prob ( z 1,67 ) = 0, 9525
Prob Z = Prob Z
σDT 3
de donde :
Z0 = 3,09;
DAi Di DNi
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 267
C(Di)
ki
CAi
CNi
DAi DNi Di
Gráfico 35
CAi -CNi
c i=
DNi -DAi
C(DTA)
C(DTN
DTA DTN T
Gráfico 41
costo. Para redes con más de dos caminos críticos se utiliza el mismo
criterio.
Resulta claro que esta forma de operar resulta sumamente lenta para
proyectos con gran cantidad de actividades.
A continuación se presenta un ejemplo de esta metodología:
Se desea disminuir la duración total de un proyecto complejo, desde su
duración total normal (DTN) hasta la duración total acelerada (DTA), con
el mínimo incremento posible del costo directo.
Datos:
De un proyecto complejo se conocen los datos que se detallan en la tabla
siguiente:
ACT. PREC DNi CNi DAi CAi Reduc. Máx. Ci
A* - 3 $ 70 2 $ 130 1 $ 60
B* A 4 $ 500 2 $ 900 2 $ 200
C* B 6 $ 1000 3 $ 1600 3 $ 200
D* C, H 4 $ 500 3 $ 550 1 $ 50
E B 5 $ 1000 2 $ 1300 3 $ 100
F E 3 $ 500 3 $ 500 0 $ 0
G A 6 $ 800 5 $ 1050 1 $ 250
H G 3 $ 600 2 $ 900 1 $ 300
Tabla 5
* actividades críticas del programa con duración normal
Etapa 1: Con los datos de las actividades, sus predecesoras inmediatas y
los tiempos normales de cada actividad, armamos la red del proyecto y
calculamos el tiempo en que puede estar terminado el proyecto en el
tiempo normal (DTN).
La red resultante es la de la Figura I. El tiempo mínimo de terminación
del proyecto en un tiempo normal es de 17 días con un costo de ejecución
de $ 4.970.- (sumatoria del costo normal de ejecución de todas las
actividades del proyecto)
Las actividades críticas para este proyecto son: A, B, C y D.
Etapa 2: Para realizar el proceso de reducción debemos calcular la
reducción máxima por actividad (DNi) y el costo de reducción por unidad
de tiempo (ci). Los cálculos se encuentran en las dos últimas columnas de
la Tabla 5.
Etapa 3: El procedimiento de reducción consiste en analizar las
actividades críticas y seleccionar aquella tarea que tenga el mínimo costo
de reducción por unidad de tiempo. Se aconseja reducir la actividad
seleccionada de a una unidad de tiempo por vez y en cada caso revisar la
red para identificar si hubo modificaciones en la ruta crítica. Tener en
270 CAPÍTULO 9
E 5
7 12 F 3
9 14 12 15
14 17
Ini 0 A 3 B 4 C 6 Fin 0
cio 17 17
0 0 0 3 3 7 7 13
0 0 0 3 3 7 7 13 17 17
D 4
13 17
13 17
G 6 H 3
3 9 9 12
4 10 10 13
Gráfico 36
2. Analizamos nuevamente las actividades críticas y elegiremos para
su reducción la que tenga menor ci. En este caso es A con un costo de $
60, pudiendo reducirse en 1 día. Con la reducción de A obtenemos la red
del Grafico 37. El tiempo mínimo de terminación del proyecto (T) es de
15 días y el costo de ejecución asciende a $ 5.080 (5.020+60). Las
actividades críticas continúan siendo A, B, C y D.
E 5
6 11 F 3
7 12 11 14
12 15
Fin 0
Inicio 0 A 3 2 B 4 C 6
15 15
0 0 0 2 2 6 6 12
15 15
0 0 0 2 2 6 6 12 D 3
12 15
12 15
G 6 H 3
2 8 8 11
3 9 9 12
Gráfico 37
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 271
5 10 F 3
6 11 10 13
11 14
Fin 0
Inicio 0 A 2 B 4 3 C 6
14 14
0 0 0 2 2 5 5 11
14 14
0 0 0 2 2 5 5 11 D 3
11 14
11 14
G 6 H 3
2 8 8 11
2 8 8 11
Gráfico 38
4 9 F 3
5 10 9 12
10 13
Fin 0
Inicio 0 A 2 B 3 2 C 6
13 13
0 0 0 2 2 4 4 10
13 13
0 0 0 2 2 4 4 10 D 3
10 13
10 13
G 6 5 H 3
2 7 7 10
2 7 7 10
Gráfico 39
272 CAPÍTULO 9
A - - A - -
B - - G - -
C 3 200 H 1 300
D - - D - -
Tabla 6
Reduciendo C y H en forma simultánea obtenemos la red del Grafico 40.
Observemos que ya no se puede continuar reduciendo, con lo cual
decimos que la duración acelerada del proyecto (DTA) es de 12 días, el
costo de ejecución para ese tiempo es de $ 6.230.- (5.730 + 200 + 300)
y tenemos tres rutas críticas: 1) A, B, C y D; 2) A, G, H y D y 3) A, B,
E y F. E 5
4 9 F 3
4 9 9 12
9 12
Fin 0
Inicio 0 A 2 B 2 C 6 5
12 12
0 0 0 2 2 4 4 9
12 12
0 0 0 2 2 4 4 9 D 3
9 12
9 12
G 5 H 3 2
2 7 7 9
2 7 7 9
Gráfico 40
por lo tanto,
MIi MFk k (-1)(i) (3)
Como:
MFi = MIi + Di MIi = MFi - Di
Sujeto a:
o lo que es lo mismo:
Di + yi = DNi
EJEMPLO DE APLICACIÓN
A fin de mostrar una aplicación de este tema, trabajaremos con el
proyecto enunciado en la tabla 2, del cual suponemos que conocemos los
siguientes datos respecto a la aceleración de sus actividades:
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 275
Tabla 7
B D E
Inicio A 30 10 7
0 15
F
5 H
2
C G
8 5
I J Fin
1 1 0
Gráfico 42
Utilizaremos para este ejemplo, el modelo lineal plantado en (5), para ello
definimos a las variables como:
MFi = momento de finalización más temprana de la actividad i (i = A, B,
..., J)
yi = cantidad de unidades de tiempo que se acelera la actividad i (i = A,
B.., J)
El objetivo es minimizar el costo total de la reducción, por lo que la función
objetivo queda:
Min Z = 25 yA + 60 yB + 20 yC + 15 yD + 50 yE + 20 yF + 0yG + 30yH + 0
yI + 0 yJ
A las restricciones del modelo podemos agruparlas en tres conjuntos:
1.- Conjunto de restricciones que describen la red usando los momentos
de finalización más temprana. Esto es que, para cada actividad, el
momento de finalización más temprano no debe ser inferior al momento
más temprano de finalización de la/s precedente más la duración normal
de la actividad, menos los días que se reducirán.
Por ejemplo para la actividad A:
MFA MFInicio + 15 - yA
Como MFInicio es igual a cero, la restricción queda:
276 CAPÍTULO 9
MFA 0 + 15 - yA
Para la B:
MFB MFA + 30 – yB
En el caso de tener más de una precedente, como por ejemplo la actividad
D, se debe plantear una restricción para cada una, es decir:
MFD MFB+ 10 – yD
MFD MFC+ 10 – yD
2.- Este conjunto está formado por una sola restricción, la que limita la
duración total del proyecto. Si simbolizamos con T a la duración
requerida:
MFFin T
yA 2; yB 5; yC 2; yD 2; yE 1
yF 1; yG 0; yH 1; yI 0; yJ 0
yA 2 yF 1
yB 5 yG 0
yC 2 yH 1
yD 2 yI 0
yE 1 yJ 0
MFi 0
yi 0 Se recomienda
plantear este problema
i= A, , C, D, E, F, G, H, I, J utilizando el PL (4).
Posteriormente,
resolver ambos
En la tabla 8 se resumen los resultados obtenidos, para cada posible valor modelos y comparar
los resultados
de T comprendido entre la DTN y la DTA del proyecto. Es decir, obtenidos.
55 T 66
Como lo expresáramos anteriormente, DTA se determina calculando el
valor del camino crítico considerando que todas las actividades se realizan
en su tiempo acelerado (DAi). Mientras que, para calcular la duración total
normal del proyecto, se asume que todas las actividades se realizan en el
tiempo DNi.
En la tabla 7 se observa claramente cómo aumenta el costo total directo
mínimo a medida que reducimos la duración total del proyecto, así, para
el tiempo de finalización del proyecto de 55 días, el costo total directo se
incrementó en $460.-
Para valores de finalización inferiores a 55 días, se comprobó
empíricamente que el programa es no factible, lo cual indica que uno o
varios de los caminos críticos tienen actividades que ya no pueden
acelerarse y por lo tanto, no es posible realizar el proyecto en un tiempo
menor a ese plazo.
Por otra parte, tampoco resulta conveniente analizar duraciones totales
del proyecto superiores a 66 días, ya que en base a los supuestos con que
trabajamos, la función de costo directo de cada actividad deja de tener
validez para valores de Di DNi. En realidad, si se deseara prolongar la
duración de la actividad i, más allá de DNi, la función de costo directo a
partir de este valor, debería ser constante o creciente, no produciendo
ninguna ventaja económica considerar tiempos superiores a los normales.
Es importante además recordar que, a los fines de la toma de decisiones,
que una vez calculados los costos directos de aceleración del proyecto,
debemos relacionarlos con los costos indirectos (tales como multas,
intereses, instalaciones) asociados a los distintos tiempos de finalización,
si estos existieran. La suma de estos costos, proporcionará el costo total
mínimo del proyecto para los diferentes valores de T, siendo, la duración
óptima del proyecto, aquella que minimice dicha función de costo total.
Para ello se deberá adicionar a la tabla 8 una columna para los costos
indirectos. Esta situación se muestra en el gráfico siguiente.
278 CAPÍTULO 9
C(T)
Costo Total
Costo Indirecto
Costo Directo
T
T óptimo
Gráfico 43
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 279
Tabla 8
280 CAPÍTULO 9
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
RESPONDA SI LAS SIGUIENTES AFIRMACIONES SON VERDADERAS O FALSAS
A. Si una actividad no crítica se retrasa más allá de su tiempo de holgura,
sin cambiar alguno de los demás factores, la duración total del
proyecto se extenderá.
B. Para todas las actividades del camino crítico, el momento de
finalización más tardío es igual al momento de inicio más temprano.
C. En un diagrama de grafo PERT/CPM que utiliza el método americano,
cada actividad está representada por un nodo de la red.
ACTIVIDAD 2
Para cada uno de los siguientes grafos, encuentre el camino de valor
mínimo usando el método de Dijkstra
6
1) 3 4 6
2 7
5
4
1 2 8
3
4 8
3 1 6 7
5
25 4
2 25
20 20 10
12 10
7
2) 1 5
15
15
3 30 35
20
6
OPTIMIZACIÓN Y PLANIFICACIÓN CON GRAFOS 281
ACTIVIDAD 3
Para cada uno de los siguientes grafos, encuentre el árbol de expansión
mínima
4
1) 2 4
5
3
9 7
1 3
8
2 6
5 6
2) 2
7
5
12 10
9
10
1 4 15
8 7
15 20
8
3
6
10
ACTIVIDAD 4
Fresh S.A. fabrica heladeras del tipo frigobar. La compañía adquiere con
proveedores externos todos los componentes que utiliza en su fabricación.
A continuación se presentan las actividades y sus relaciones. Los tiempos
asociados con el proceso de fabricación se muestran en la tabla.
Las primeras actividades pueden ejecutarse en forma simultánea:
(1) Comprar el plástico para los anaqueles.
(2) Comprar las láminas de chapa enlozada y el aislante térmico.
(3) Comprar el motor.
Cuando se ha recibido el plástico,
(4) se deben moldear los anaqueles.
Después que se recibe la chapa y el aislante,
(5) se fabrican las estructuras y, después
(6) se les coloca el aislante.
Luego de haber terminado las actividades (4), (3) y (6),
(7) se ensamblan las tres unidades en una sola.
Una vez concluida la actividad (7), se puede
(8) inspeccionar la unidad,
(9) empacar la unidad, y
(10) enviar la unidad.
282 CAPÍTULO 9
Activid. 1 2 3 4 5 6 7 8 9 10
Tpo. semanas 4 2 10 3 2 4 3 1 1 1
ACTIVIDAD 5
Los datos que se detallan a continuación corresponden a las actividades
necesarias para llevar a cabo una campaña política:
Actividad A B C D E F G H I J
Tiempo
3 8 5 2 4 3 6 7 9 3
esperado
Desviación 0,33 0,25 1 2 0,55 1 2 0,16 1 1
ACTIVIDAD 6
De un proyecto complejo formado por 9 actividades, al aplicar el Método
P.E.R.T. se obtiene:
* = a, b, d, g, i ;
ACTIVIDAD 7
La siguiente tabla indica las actividades de un proyecto de investigación
de mercado y sus datos sobre tiempos y costos.
Actividad Precedente Tiempo Tiempo acelerado Costo de
normal (días) reducción
(días) ($/día)
A -- 8 6 15
B A 9 5 25
C A 10 5 25
D C 15 10 15
E B-D 10 6 10
F E 2 1 30
1. INTRODUCCIÓN
Gráfico 1
t1 2t1 t
Gráfico 2
2. CLASIFICACIÓN ABC
4º Graficar la curva ABC del porcentaje acumulado del uso del dinero
en función del porcentaje acumulado de ítems.
En el gráfico siguiente, se muestra un esquema de clasificación ABC donde
la curva representa el del porcentaje acumulado del uso del dinero en
función del porcentaje acumulado de artículos.
Gráfico 3
S=q
t1 2 t1 3 t1 t
Gráfico 4
N q Tq N
h= = ; t1 = ; v= (1)
T t1 N q
El costo total variable puede expresarse como la suma del costo total
variable de hacer los pedidos y el costo total variable de almacenamiento.
ADMINISTRACIÓN DE INVENTARIOS 293
donde:
q
CTs=(Cs t ) v
2 1
CTp=Cp v
q N Tq q
CTs = Cs = Cs T
2 q N 2
N
CTp = Cp v = Cp
q
CT
=0
q
CT Cs T Cp N
= - 2
=0 (4)
q 2 q
Cs T Cp N
= 2
;
2 q
294 CAPÍTULO 10
2 Cp N 2 Cp N
q2 = , despejando q se obtiene: q* =
Cs T Cs T
2
CT 2 Cp N
= (5)
q 3
q
CTp
q* q
Gráfico 5
Ejemplo de aplicación
2 Cp N 2 (500) 10950
q* = = 100 amortiguadores
Cs T 3 (365)
S(t)
t2 t3
t
R=q - S
t1
2 t1 3 t1
Gráfico 6
ADMINISTRACIÓN DE INVENTARIOS 297
N N q S q- S
v= ; h= = = = ;
q T t1 t t
2 3
de donde : (1)
Tq TS T (q - S)
t1 = ; t = ; t =
N 2 N 3 N
S TS N T S2
CTs = Cs = Cs
2 N q 2q
N
CTp = Cp v = Cp
q
(q- S) T(q- S) N T(q- S)2
CTr = Cr = Cr
2 N q 2q
Reemplazando en (2) obtenemos el CT
T S2 N T (q- S)2
CT = Cs + Cp + Cr
2q q 2q
CT CT
= 0; =0
q S
Ejemplo de aplicación
Tq 365(200) TS 365(50)
t1 = = = 6,67 días ; t2 = = = 1,67 días ;
N 10950 N 10950
Plantear diferentes
t = t - t = 5 días
3 1 2 escenarios asignando
diferentes valores a Cr y
N 10950 comparar los resultados
v= = = 54,75 pedidos en el período T obtenidos en cada
q 200 situación. Particularmente
2 2 2 2 observar lo que ocurre
TS N T (q - S) 365(50) 10950 365(200-50)
CT = Cs + Cp + Cr =3 + 500 +1 = $54.750. - cuando Cr asume un valor
2q q 2q 2(200) 200 2(200) muy grande.
Cr
En S del segundo modelo, aparece el término , el cociente bajo el
Cr+Cs
signo de radicación se llama tasa de ruptura () y es justamente este
término el que hace la diferencia entre el inventario máximo en ambos
modelos. Vamos a analizar qué ocurre con la tasa de ruptura a medida
que el costo de ruptura aumenta. Para ello, tomamos límite para Cr→:
Cr
Cr→ Cr+Cs
Con lo cual podemos afirmar que la relación que existe entre ambos
modelos es la siguiente: el modelo 1 es un caso particular del modelo 2
cuando el costo de ruptura es inmensamente alto. Es decir que, cuando
el costo de ruptura es muy grande (Cr→ ), el modelo 2 se transforma en
el modelo 1, que justamente no admite rupturas porque tienen un costo
imposible de afrontar.
S(t)
t1 2t1
t4 t5
Gráfico 7
t 1 = t4 + t 5 ; t 5 = t1 – t 4
Debido a que, durante el período t4, ingresa y sale mercadería, la tasa a
la cual se acumula el inventario es (a - h), por lo que el stock máximo,
que se da al final del periodo t4 será:
q h
S = (a - h) t4 ; reemplazando a t4 S = (a - h) ; S = q 1 -
a a
Recordando que la función de costo total es igual al costo total de pedir
más el costo total de almacenar, para este modelo será:
N S S N
CT = Cp + (Cs t + Cs t ) ;
4 5
q 2 2 q
N SN N S N
CT = Cp + Cs (t + t ) = Cp + Cs t ;
4 5 1
q 2 q q 2 q
h
q (1 - )
N S N Tq N a N Tq
CT = Cp + Cs = Cp + Cs ;
q 2 q N q 2 q N
CT (q) = Cp
N q h
+ Cs T 1-
q 2 a
2 Cp N 2 Cp N 1
q* = =
h Cs T
1-
h
Cs T 1-
a a
*
N q h
Cp = Cs T 1- a
q
* 2
2 Cp N 1
q*RU =
Cs T h >1
1-
a
q*RU q*SR
2 Cp N
q*SR =
Cs T
v <v
RU SR
N q h
CT(q) = Cp + Cs T 1 -
q 2 a <1
CT < CT
RU SR
N q
CT(q) = Cp + Cs T
q 2
q*SR h
*
CTS (qRU ) = CS T 1 −
2 a
Ejemplo de aplicación
Supongamos que una fábrica de jabón en polvo produce en una línea con
capacidad de 5000 cajas mensuales. La demanda anual se estima en
30.000 cajas, manteniéndose la tasa de demanda prácticamente
constante durante todo el año.
La limpieza, preparación y puesta en marcha de la línea de producción
cuesta aproximadamente $140. El costo de producción es de $2 por caja.
El costo anual de almacenamiento se calcula en un 24 %.
Determinar el tamaño del lote de producción y el costo total asociado.
304 CAPÍTULO 10
T = 12 meses t = mes
a = 5.000 unidades por mes; h = 2.500 unidades por mes
N = 30.000 unidades por año;
Cp = $140;
Cs = $ 0.04 por unidad y por mes
2 Cp N 2 (140) 30000
q*= = 5916 unidades
h 2500
Cs T 1 - 0, 04 (12) 1 -
a 5000
MODELO CEP
ADMINISTRACIÓN DE INVENTARIOS 305
Gráficamente:
S=q
x0
t1 t
Gráfico 8
S(t)
S
x q
t3 t
t2
R
Gráfico 9
306 CAPÍTULO 10
t2 q
t
x t3
t1 R
Gráfico 10
S(t)
x t
4
t5
t
t
1
Gráfico 11
El nivel de reorden, en este caso, lo calculamos como:
x0 = h
x
t4 t5
t
t1
Gráfico 12
x0 = (a-h) (t1- )
tendrá una distribución normal, con una media igual a m y un desvío igual
a m .
Es decir que, si fijáramos como nivel de reorden a la demanda media en
, el 50 % de las veces nos quedaríamos sin stock.
Lo que a nosotros nos interesa es establecer un nivel de reorden (x) que
nos proporcione una cierta confianza de que, durante el periodo , este
nivel x de inventario no será excedido por la demanda. Esto es:
m> x0
m x0
1-
m x0 Demanda en
Gráfico 13
x-m
z1- =
σm
En consecuencia:
x0 = m + z1- .σ m
Donde:
m=h.
σ m = h.σ
Podemos observar que ahora el nivel x está formado por m , más una
cierta cantidad representada por z1-α .σ m . Esta cantidad se llama stock de
ADMINISTRACIÓN DE INVENTARIOS 309
seguridad y tiene como función cubrir los excesos de la demanda real, por
encima de la demanda media, en el periodo de retardo.
Ejemplo de aplicación
x0 = m = h = 30(1) = 30 amortiguadores
Es decir que la empresa Metalúrgica SA deberá iniciar un nuevo lote de
producción cada vez que el inventario llegue a 30 amortiguadores.
Supongamos ahora que el tiempo para producir cada lote es una variable
aleatoria normal con media 2 días y desvío 0,5. Es decir:
N (2 ; 0, 5)
m = h = 30(2) = 60 amortiguadores
Entonces :
m N (60 ; 15)
Fijando un nivel de confianza de 0,05, entonces z0,95 = 1,645
Buscamos:
Prob (m x0 ) = 0, 95
x0 − m
Prob z0,95 = 0, 95
m
x0 − 60
Prob 1,645 = 0, 95
15
q
CT = Cp + Cs t1 + q pi v
(q, pi) 2
N q N N
CT = Cp + (a + b pi) t1 + q pi
(q, pi) q 2 q q
Tq
Reemplazando a t1 = y operando :
N
N Tq
CT = Cp + (a + b pi) + pi N
(q, pi) q 2
N Tq
CT = Cp + (a+b p ) + p N si 0 q < q
(q, p ) q 1 2 1 1
i
N Tq
CT = Cp + (a+b p ) + p N si q q < q
(q, p ) q 2 2 2 1 2
i
N Tq
CT = Cp + (a+b p ) + p N si q q < q
(q, p ) q 3 2 3 2 3
i
2 Cp N
q *=
i (a+b p ) T
i
Gráfico 14
Gráfico 15
Procedimiento
Calcular
q3*
si El óptimo es
q2 < q3* q3*
no
Calcular
q2*
si Calcular:
q1 < q2* CT3(q2)
CT2(q2*)
no
Calcular si El óptimo es
CT3(q2)< q2
q1* CT2(q2*)
no
Calcular : El óptimo es
CT3(q2), CT2(q1) q2*
y CT1(q1*)
El menor CT
indica el
valor de q*
Gráfico 16
Ejemplo de aplicación
Primero calculamos :
2 (50) 15900
q *= = 17,04 unidades
3 [1+ 0,035 (400)] 365
2 (50) 15900
q *= = 15,34 unidades
2 [1+ 0,035 (500)] 365
2 (50) 15900
q *= = 14,07 unidades
1 [1+ 0,035 (600)] 365
Todos los modelos de inventario que tratamos hasta ahora requieren que
la demanda se conozca con certeza. Sin embargo, en muchas situaciones
nos enfrentamos a problemas en los cuales la demanda se describe mejor
a través de una variable aleatoria.
En el modelo que analizaremos ahora se considera un único periodo de
análisis con una demanda probabilística. Esta situación se da
generalmente cuando los productos son perecederos o de temporada. El
caso más típico es el del “vendedor de diarios”, que debe decidir cada día
cuántos periódicos comprar.
316 CAPÍTULO 10
S(t) S(t)
q q
q -N
t N -q t
Gráfico 17
q
CT(q,N) = Ce (q - N) PN + Cf (N - q) PN (2)
N=0 N=q+1
CT(q-1) - CT(q) > 0
CT(q-1) > CT(q) < CT(q+1) (3)
CT(q+1) - CT(q) > 0
q-1
CT(q-1,N) = Ce (q-1-N) PN+ Cf (N- q+1) PN
N=0 N=q
q-1 q-1
CT(q-1,N) = Ce (q-N) PN - Ce PN +Cf (N- q) PN +Cf PN (4)
N=0 N=0 N=q N=q
I II III IV
q-1 q
I = (q-N) PN = (q-N) PN
N=0 N=0
III = (N- q) PN = (N- q) PN
N=q N=q+1
q-1
II = PN = P(N q-1)
N=0
IV = PN =1-P(N q-1)
N=q
318 CAPÍTULO 10
Reemplazando en (4):
q
CT(q-1,N) = Ce (q-N) PN - Ce P(N q-1) + Cf (N- q) PN +Cf 1-P(N q-1)
N=0 N=q+1
q
CT(q-1,N) = Ce (q-N) PN + Cf (N- q) PN - Ce P(N q-1) + Cf - Cf P(N q-1)
N=0 N=q+1
Reemplazando los dos primeros sumandos del lado derecho por su igual en (2) :
CT(q-1,N) = CT(q,N) - Ce P(N q-1) + Cf - Cf P(N q-1)
De donde :
Cf
P(N q - 1) <
Ce + Cf
Por lo que podemos afirmar que el valor de q que minimiza el costo total
variable esperado del modelo, será aquel para el cual se verifique :
Cf
P(N q - 1) < P(N q)
Ce + Cf
Ejemplo de aplicación
Cf
1 paso: Identificamos Ce, Cf y calculamos
Ce+Cf
Cf 0, 50
= = 0, 625
Ce+Cf 0, 30 + 0, 50
Probabilidad
Demanda
acumulada
50 0,25
55 0,45
0,625
60 0,70
65 0,80
70 1
320 CAPÍTULO 10
Entonces q* = 60 periódicos
N PN Ce (q-N)PN Cf(N-q)PN
50 0,25 0,75
55 0,20 0,30
60 0,25
65 0,10 0,25
70 0,20 1,00
TOTAL: 1,05 1,25
N-
z=
σ
q - 62
*
P z = 0,625
8
ADMINISTRACIÓN DE INVENTARIOS 321
S(t)
S(t)
q
q
q -N
t2 t3 T
t t
N -q
Gráfico 18
322 CAPÍTULO 10
Donde:
S(t): mercadería almacenada en el momento t
q = S(0): volumen del pedido
t2 = periodo de tiempo durante el cual existe inventario
t3 = periodo de ruptura
q+ ( q - N)
Cs T = C q- N T ; si N q
s
2 2
CT ( q) =
Recordando que
q N- q
Cs t2 + Cr t3 ; si N > q
2 2
N q N- q
h= = =
T t2 t3
De donde:
t2 =
Tq
; t3 =
(
T N- q )
N N
q N q N - q
CT (q) = Cs q - T PN + Cs t2 PN + Cr t3 PN
N=0 2 N=q+1 2 N=q+1 2
Reemplazando a t2y t3
q N
CT (q) = Cs q - T PN + Cs
q Tq
PN + Cr
(N - q) T (N - q) PN
N=0 2 N=q+1 2 N N=q+1 2 N
2
q N
CT (q) = Cs q- T PN+ Cs
q2 T
PN+ Cr
(N- q) T PN
N=0 2 N=q+1 2 N N=q+1 2N
q N q2 (N- q) PN
2
Cr
L (q - 1) < L (q)
Cr + Cs
siendo
1 PN
L (q) = P (N q) + q +
2 N =q+1 N
Ejemplo de aplicación
Demanda Probabilidad
0 0,15
1 0,11
2 0,23
3 0,26
4 0,17
5 0,08
Cr 20
= = 0,7142
Cs + Cr 20 + 8
324 CAPÍTULO 10
q PN 1 PN
PN PN
N=q PN (q + ) L(q)
N=0 N=q+1 N
N 2 N=q+1 N
0 0,15 0,15 - 0,370 0,185 0,335
1 0,11 0,26 0,110 0,260 0,390 0,650
0,7142
2 0,23 0,49 0,115 0,145 0,363 0,853
3 0,26 0,75 0,087 0,059 0,205 0,955
4 0,17 0,92 0,043 0,016 0,072 0,992
5 0,08 1,00 0,016 0 0 1,000
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
2 2
q -N q (N - q)
N T Cs PN Cs PN Cr PN CT
2 2N 2N
0 30 8 2 0,15 72,00
1 30 8 1,50 0,11 39,60
2 30
CT = (1) {[(2) (3) (4)] + [(5) (6) (7)] + [(8) (9) (10)]} = $2.311,28
Es importante destacar que, al momento de calcular el lote óptimo, debe
tenerse en cuenta que siempre la demanda (N) deberá variar en valores
discretos consecutivos a partir del cero (porque el modelo teórico
considera esta variación de N). Por lo tanto, cuando en el enunciado
original del ejercicio la variación sea en otra escala, deberá previamente
hacerse un cambio de escala para trabajar con la fórmula tal como se
ha visto.
El enfoque JIT o Just in Time supone una forma de gestión formada por
un conjunto de técnicas y prácticas de organización de la producción que
pretende que el cliente sea servido cuando lo precise (justo a tiempo) y
en la cantidad y calidad requeridas. Las dos estrategias básicas de este
enfoque consisten en:
1
El modelo matemático de esta situación excede los alcances de este texto.
2
Extraído de DOMÍNGUEZ MACHUCA, J. Y LUNA HUERTAS, P.: “La Filosofía Just In
Time. Objetivos e Instrumentos”. Publicación: Alta Dirección, Nº 155, 1991.
326 CAPÍTULO 10
3
Extraído de DOMÍNGUEZ MACHUCA: “M.R.P. Planificación de las Necesidades de
Materiales”. Publicación: Alta Dirección, Nº 118, 1984.
ADMINISTRACIÓN DE INVENTARIOS 327
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
1. RESPONDA LAS SIGUIENTES PREGUNTAS:
a) Cuáles son los supuestos básicos que diferencian a los distintos
modelos con demanda determinista:
I. Modelo sin ruptura vs. Modelo con ruptura
II. Modelo sin ruptura vs. Reabastecimiento uniforme
III. Modelo sin ruptura vs. Modelo con función de costo total
discontinua
3. DEMUESTRE QUE:
h
CT(q*RU ) = CT(q*SR ) 1-
a
ADMINISTRACIÓN DE INVENTARIOS 329
ACTIVIDAD 2
Para el siguiente conjunto de ítems de un inventario, realice una
clasificación ABC.
Consumo
Costo
Artículo anual
unitario ($)
(unidades)
1 5000 1,5
2 1500 8
3 10000 10,5
4 6000 2
5 3500 0,5
6 6000 13,6
7 5000 0,75
8 4500 1,25
9 7000 5
10 3000 2
11 6000 10
12 2000 15
13 6500 28
14 9300 31
15 3060 14
16 3177 4
17 1500 1,2
18 1962 8
19 7000 30
20 1246 15
ACTIVIDAD 3
Un importador de equipos de aire acondicionado para automóviles tiene
una demanda promedio de 6.000 equipos al año. Cada vez que hace un
pedido, incurre en un costo de $300. El costo anual del capital
inmovilizado lo estima en 12 % y, además, tiene contratado un seguro
por el que paga una prima del 13 % anual sobre el valor de la mercadería
en inventario. El costo de cada equipo es de $200. Entre el momento en
que hace el pedido y este ingresa al almacén, transcurre una semana.
En base a esta información, responda:
(a) ¿Cuántos equipos deben ordenarse cada vez?
(b) ¿Cuántos pedidos se deben colocar en un año?
(c) Calcule los costos totales anuales.
(d) Determine el nivel de reorden.
330 CAPÍTULO 10
ACTIVIDAD 4
En un modelo de stock donde no se permiten rupturas y el pedido no tiene
demora e ingresa en un solo lote, el costo total de pedido óptimo para
satisfacer una demanda de 4.800 unidades en 12 meses, realizando 30,98
pedidos al año, es de $1.859,03.
Se pide:
a) Determine el volumen óptimo de pedido.
b) Determine el costo de almacenamiento unitario mensual.
ACTIVIDAD 5
Una fábrica está revisando el tamaño de su lote de fabricación de un
producto en particular. Actualmente, la capacidad de producción de la
planta para este producto es de 12 unidades por día con un costo de
preparación del proceso de producción de $300. La demanda es de 40
unidades por semana. El costo de conservación del producto se estima en
$1,60 por unidad y por año. En este momento, se realizan corridas de
producción de 520 unidades cada 13 semanas. Considerando 52 semanas
al año y 5 días laborables por semana:
a) ¿Recomendaría usted cambiar el tamaño del lote de producción? ¿Por
qué sí o por qué no?
b) ¿Cuánto se podría ahorrar cambiando el tamaño del lote de producción
según su recomendación?
ACTIVIDAD 6
AutoCor SA ha decidido aplicar una política apropiada de manejo de
inventarios para aquellos repuestos que tienen un alto precio de costo.
Para uno en particular, determinó que debían adquirirse lotes de 1.500
unidades cada 15 días. Además de esto, como el periodo que transcurre
entre el momento de emitirse la orden de pedido y el momento en que la
mercadería llega es aleatorio, la empresa quisiera fijar un nivel de
reorden. La empresa quiere que la probabilidad de que el nivel fijado sea
suficiente para atender a la demanda durante ese periodo sea de 0,95.
Sabiendo que la demora del pedido se distribuye normal con media 3 días
y desviación estándar 1 día, ¿cuál deberá ser este nivel de reorden? ¿Cuál
será el stock de seguridad?
ADMINISTRACIÓN DE INVENTARIOS 331
ACTIVIDAD 7
SEGURIDAD SA es una empresa multinacional que se ha instalado
recientemente en nuestro país. Su principal actividad, en la nueva planta
de Córdoba, es la fabricación y venta de equipos integrales de alarmas,
en particular, los sistemas de seguridad inteligentes para casas y edificios.
La gerencia de producción ha estimado que durante el próximo año se
requerirán 10.000 detectores de movimiento inteligentes cada mes.
Dado que enfrentan problemas de espacio físico y limitaciones en ciertos
recursos esenciales, la empresa ha decidido adquirir el 60 % de estos
detectores a un proveedor externo y fabricar en su propia planta los
restantes.
El proveedor puede entregarlos el mismo día en que se piden y a un precio
de $50 cada uno. A la empresa le cuesta $30 producir cada detector
inteligente. El costo de almacenamiento es del 12 % anual del precio de
costo (de producción o compra). El costo de pedido por la adquisición
externa de las unidades es de $100 por pedido. El costo de preparación
de la producción asociado con la fabricación de los detectores es de $150.
SEGURIDAD SA tiene capacidad de producción suficiente para fabricar
5.000 detectores por mes, a tasa constante.
Teniendo en cuenta que los detectores que le demandan en parte los
produce y en parte los compra:
a) Calcule la cantidad óptima de pedido que debe adquirirse al proveedor
externo.
b) Determine el tamaño óptimo del lote de producción interno.
c) Determine el número óptimo de pedidos por mes.
d) Determine el número óptimo de corridas de producción por mes.
e) ¿Cuál es el costo total anual de esta política combinada de inventario?
ACTIVIDAD 8
La imprenta de la Facultad trata de determinar cómo minimizar los costos
anuales relacionados con la compra del papel para imprimir los exámenes
y parciales. Cada vez que se hace un pedido, se incurre en un costo de
$20. El precio por caja de papel depende del número de cajas pedidas
(ver tabla). El costo anual de almacenamiento es del 20 % del valor del
inventario. Cada mes, la Facultad utiliza 80 cajas de papel.
Considere el año de 250 días hábiles.
ACTIVIDAD 9
Considere el modelo de inventario con demanda cierta, sin ruptura, con
puntos de discontinuidad (variaciones por saltos) en la función de costo
total variable (CT), originados en la existencia de tres precios diferentes
del producto, p1, p2 y p3, tales que p3 < p2 < p1, donde los precios p2 y p3
son válidos a partir de determinadas cantidades de q 1 y q2,
respectivamente. Es decir:
- Si el pedido es entre q1 y q2 unidades, el precio unitario es p2
- Si el pedido es entre q2 y q3 unidades, el precio unitario es p3
Indicando como q1*, q2*, q3* las cantidades óptimas correspondientes a
los precios dados, se solicita:
a) Graficar, en forma completa, el problema anterior, considerando a
q1 y q2 menores que la cantidad óptima correspondiente a la
función de costo total correspondiente al mayor precio. Indique,
para cada curva y cantidad óptima respectiva, a qué precio se
refieren.
b) Para el gráfico que realizó en el punto a), señale cuál es la cantidad
óptima de pedido y porqué.
ACTIVIDAD 10
La florería CLAVELES SA debe decidir cuántas orquídeas ordenar para el
Día de la Secretaria. La demanda de este tipo de flores en los días
especiales, como este o el de la Madre, es una variable aleatoria (D). Si
la demanda excede el número de flores disponibles, el faltante se satisface
colocando una orden urgente. En este caso, el costo de cada flor será $5
más caro que el costo normal. Si la demanda es menor que el inventario
que se tiene, las flores que sobran se pueden vender con posterioridad.
El precio de venta de las flores que sobren será $3 menos que su costo
original, ya que no se encontrarán igualmente frescas.
Demanda 10 15 20 25 30
Probabilidad 0,10 0,25 0,30 0,20 0,15
ADMINISTRACIÓN DE INVENTARIOS 333
1. INTRODUCCIÓN
Hasta ahora nos hemos ocupado de la formulación de modelos que se
resolvieron en forma analítica y, en casi todos ellos, nuestra finalidad fue
encontrar soluciones óptimas.
Para utilizar estos modelos matemáticos tuvimos que incluir, en cada
caso, supuestos o hipótesis simplificadoras. Por ejemplo, en algunos
modelos de stock supusimos que el costo de almacenamiento era
proporcional a las unidades almacenadas.
Sin embargo, y por diversas razones, no todos los problemas de la vida
real pueden ser representados a través de un modelo analítico. En estos
casos, un decisor racional deberá hacer uso de otro tipo de modelos,
llamados modelos de simulación, que le permiten representar y estudiar
a estos problemas.
2. CONCEPTO DE SIMULACIÓN
Si buscamos en el diccionario la palabra simular, nos encontraremos con
que simular “es representar una cosa, fingiendo o imitando lo que no es”.
Justamente, la simulación es un método que le permite al decisor estudiar
el comportamiento de un sistema real experimentando con un modelo que
lo representa, llamado modelo de simulación. Este está formado por las
expresiones matemáticas y las relaciones lógicas entre los componentes
fundamentales del sistema y permiten calcular el valor de las salidas de
interés dadas las entradas controlables del sistema.
El objetivo del proceso de simulación es la ejecución del modelo a través
del tiempo, en general en una computadora, para generar mediciones de
determinados valores de eficiencia del sistema.
A diferencia de los modelos de optimización, en los cuales las entradas
son parámetros y las salidas son decisiones óptimas, en los modelos de
simulación las entradas son decisiones o parámetros y las salidas son
medidas de eficiencia del sistema.
En el siguiente esquema podemos observar la diferencia entre ambos
tipos de modelos.
336 CAPÍTULO 11
INPUTS OUTPUTS
Decisiones y Valores
paramétricos SIMULACIÓN Medidas de eficiencia
INPUTS OUTPUTS
Gráfico 1
3. VENTAJAS DE LA SIMULACIÓN
Los modelos de simulación de un sistema mejoran el proceso decisorio
debido a que permiten:
✓ Analizar los efectos que se producen en el comportamiento de un
sistema ante cambios internos o externos.
✓ Entender el comportamiento de un sistema y, por consiguiente,
sugerir estrategias que mejoren su operación y eficiencia.
✓ Comprender mejor la operación de sistemas complejos, detectar las
variables más importantes y entender la relación entre ellas.
✓ Experimentar con nuevas situaciones sobre las cuales se tiene poca
información. A través de esta experimentación, se pueden anticipar
resultados no previstos.
✓ Anticipar problemas que puedan surgir en el comportamiento del
sistema cuando se introducen nuevos elementos.
➢ Experimentación.
➢ Interpretación.
Con estos datos, podemos realizar un análisis del tipo “que pasa si”, que
implica generar valores para las entradas probabilísticas y calcular el valor
resultante para la salida.
El modelo que representa la utilidad para el primer año es:
También podemos sugerir un escenario del mejor caso con los costos más
bajos y la demanda más alta:
deseada. Por supuesto que, para generar estos valores, es necesario que
conozcamos cuál es la distribución de probabilidad de cada entrada
aleatoria. Existen varios procedimientos para lograr este objetivo. Entre
los procedimientos más comunes, se encuentra el método de
transformación inversa.
F(x)
1
Rn
x0 x
xx
x0
Gráfico 2
F(x)
1
0,95
Rn
0,45
0,15
0 1 2 3 4 5 X
x0
Gráfico 3
Costo/unid. Probabilidad
25 0,02
26 0,03
27 0,05
28 0,10
29 0,15
30 0,17
31 0,20
32 0,12
33 0,08
34 0,05
35 0,03
Tabla 1
F(x)
1/30
60 75 90 x
Gráfico 4
Demanda del primer año puede aproximarse con una distribución normal
con media de 20.000 unidades y una desviación estándar de 5.000
unidades:
Desviación estándar
= 5.000 unidades
20.000
Número de unidades vendidas
Gráfico 5
Para simular nuestro problema, debemos generar valores para las tres
entradas probabilísticas que sean representativos de los que pudiéramos
observar en la realidad, y calcular la utilidad resultante. Luego,
generamos otro conjunto de valores para las entradas probabilísticas y
calculamos un segundo valor para la utilidad, etc.
El cálculo de la utilidad completa un ensayo de la simulación.
Continuamos con este proceso hasta estar seguros de tener suficientes
ensayos para describir la distribución de probabilidad para la utilidad.
MODELOS DE SIMULACIÓN 341
Pv
Utilidad del
CD (150 – c1 – c2) x – 475.000 primer año
CP
Gráfico 6
Entradas probabilísticas:
c1 = costo de la mano de obra directa por unidad
c2 = costo de los materiales por unidad
x = demanda para el primer año
Generar costo de la
mano de obra directa, c1
Calcular utilidad
Utilidad = (150 – c1 – c2) x – 475.000
Gráfico 7
342 CAPÍTULO 11
Para ejecutar nuestro modelo, colocamos los datos en una planilla, por
ejemplo, podemos usar Excel. En cada fila de la planilla, resumimos un
ensayo, entonces esta podría tener la siguiente estructura:
Tabla 2
Primer ensayo:
- Generar el costo de la mano de obra directa (MO directa) utilizando el
método de la transformación inversa:
1. Generar un nº aleatorio.
Probabilidad
Costo/unid. Probabilidad
acumulada
25 0,02 0,02
26 0,03 0,05
27 0,05 0,10
28 0,10 0,20
29 0,15 0,35
30 0,17 0,52
31 0,20 0,72
32 0,12 0.84
33 0,08 0,92
34 0,05 0,97
35 0,03 1
Tabla 3
x-a x - 60
2. Rn = F(x) = =
b - a 90 - 60
1. Generar un nº aleatorio.
2. Usar este valor Rn para encontrar un valor x para el que:
F(x) = P(D x) = Rn
3. Es decir, encontrar el valor de x para el que el área bajo la curva
normal a la izquierda es Rn. Para hacer esto, usar la tabla normal
estándar y luego calcular x de la siguiente manera:
x= + ( * z)
Tabla 5
Distribución de Frecuencias
0,73
0,55
frecuencia relativa
0,37
0,18
0,00
-124 284 693 1102 1511 1919
Utilidad (en miles de pesos)
Gráfico 8
Gráfico 9
Probabilidad
Llegadas Probabilidad
acumulada
0 0.135 0.135
1 0.271 0.406
2 0.271 0.677
3 0.180 0.857
4 0.090 0.947
5 0.036 0.983
6 0.012 0.995
7 0.003 0.998
8 0.002 1
Tabla 8
-x = ln 1 - F(x)
1
x= − ln 1 - F(x)
Como F(x) = Rn
1
x=− ln 1 - Rn
12
12
0,5743 0,8893
0,6444 0,0329
0,6734 0,0908
0,6771 0,1679
0,7211 0,5122
0,1362 0,4157
Tabla 9
n = 5.5350
a) Comprar cada día una cantidad igual a la demanda del día anterior.
b) Comprar diariamente una cantidad fija de 53 unidades.
Política a)
qi = Ni-1
N0 = 53
350 CAPÍTULO 11
n
CTDi
CTP = i=1 , siendo n el número de días simulados
n
Política b)
qi = 53
N0 = 53
n
CTDi
CTP = i=1 , siendo n el número de días simulados
n
Definir Parámetros
i=0
No= 53
CTDi = 0
i=i+1
qi= Ni-1 a)
qi= 53 b)
Generar
Ni
Registrar
resultados
es i = 200 ?
no
si
Calcular CTP
Fin
Gráfico 10
Política a)
352 CAPÍTULO 11
Política b)
Ensayo
n=n+1
Si Día soleado? No
Si No
D > 180 ?
Gráfico 11
Tabla 16
Gráfico 12
356 CAPÍTULO 11
Gráfico 13
Gráfico 14
Gráfico 15
Tiempo Tiempo
Nº Hora Unidades. Nº Duración Inicio Fin
NºCliente entre espera en
Random llegada en la fila Random servicio servicio servicio
llegadas la fila
1 0.1634 5.33 5.33 0 0.2396 5.71 5.33 11.04 0
2 0.7344 6.47 11.8 0 0.5582 2.33 11.8 14.13 0
3 0.2809 5.56 17.36 0 0.7556 1.12 17.36 18.48 0
4 0.0746 5.15 22.51 0 0.7468 1.17 22.51 23.68 0
5 0.3049 5.61 28.12 0 0.0858 9.83 28.12 37.95 0
6 0.6203 6.24 34.36 1 0.4840 2.9 37.95 40.85 3.59
7 0.2923 5.58 39.94 1 0.0382 13.06 40.85 53.91 0.91
8 0.6696 6.34 46.28 1 0.1011 9.17 53.91 63.08 7.63
9 0.4031 5.81 52.09 2 0.8934 0.45 63.08 63.53 10.99
10 0.2875 5.75 57.84 2 0.9525 0.19 63.53 63.72 5.69
11 0.3496 5.70 63.54 1 0.4466 3.22 63.72 66.94 0.18
12 0.8306 6.66 70.20 0 0.6117 1.97 70.20 72.17 0
13 0.4229 5.84 76.04 0 0.0579 11.40 76.04 87.44 0
14 0.9751 6.95 82.99 1 0.8758 0.53 87.44 87.97 4.45
15 0.8950 6.79 89.78 0 0.5867 2.13 89.78 91.91 0
Tabla 17
Cliente nuevo
n = n+1
Gráfico 16
Tabla 18
inicio
i=0, j=0
MCi=0, MOj=0
Dj=0, LFi=0,
TEi=0, ITi=0
j=j+1
Generar Dj
MOj=15 j+Dj
LFi=0
i=i+1
Generar ITi
MCi=MCi-1+ITi
No
MCi < MOj?
Si
LFi = LFi-1+1
TEi=MCi-MOj
No
MCi 120?
Si
Analizar datos
Fin
Gráfico 17
Tiempo total
Personas en la fila Frecuencia relativa
(frec. Absoluta)
0 9.69 0.1615
1 6.20 0.1034
2 8.76 0.1460
3 8.50 0.1417
4 7.28 0.1213
5 6.25 0.1042
6 3.83 0.0639
7 4.60 0.0767
8 3.74 0.0623
9 1.15 0.0191
Tabla 19
10
0
1
Tiempo en min.
Gráfico 18
Recordemos que, para realizar un análisis de resultados que sea útil para
la toma de decisiones, se deberá ejecutar una cantidad grande de
simulaciones de dos horas cada una, tanto con frecuencia de 15 minutos
como de la que actualmente está dando quejas de los clientes (cada 20
minutos). A partir del estudio de estos resultados, evaluar la política de
cambiar la frecuencia.
Tabla 20
Definición de variables
i = número de autos llegados al lavadero
j = número de autos que no se atiende porque hay más de 2 esperando.
K = número de autos atendidos
TELLi = tiempo entre llegadas del auto i (variable aleatoria)
TLLn = momento de llegada del auto i
DSi = duración del servicio del auto i (variable aleatoria)
MISi = momento de inicio del servicio del auto i
MFSi = momento de finalización del servicio del auto i
Tabla 21
11
0,9
0,84 0,8
0,7
0,6
0,53 0,5
0,4
0,33 0,3
0,2
0,09 0,1
0 0
0 5 10 15 20 30
Gráfico 19
= 0 x 0
0,09
F(x) = = x 0 x 5
5
0,33 - 0,09
= 0,09 + (x - 5) 5 x 10
10 - 5
F(b) - F(a)
F(x) = F(a) + (x - a) a x b
b-a
de donde si despejamos x :
(b - a)
x = [F(x) - F(a)] +a
F(b) - F(a)
Inicio
i=i+1
generar
TELLi
Si Calcular
¿MLLi >= 480’ ? Fin
K= i - j
No
No Calcular LFi = 0
MLLi < MFSi-1?
MISi = MLLi
Si
No Calcular LFi = 1
MLLi < MFSi-2 ? MISi = MFSi-1
Si
Si Abandona
MLLi < MFSi-3 ? j = j+1
No
DSi=0
Calcular
MISi = MFSi-2 LFi = 2
MFSi=MISi=MLLi
Generar
DSi
Calcular
MFSi = MIi + DSi
Gráfico 20
MODELOS DE SIMULACIÓN 369
ACTIVIDADES DE AUTOEXAMEN
ACTIVIDAD 1
El conjunto de datos de la tabla 22 representa la demanda diaria de un
artículo de perfumería en particular. Simule 15 días de demanda
utilizando los números aleatorios de la tabla 23.
Demanda
Frecuencia Nº Aleatorio
diaria
15 25 0.508
16 30 0.935
17 50 0.486
18 80 0.263
19 25 0.510
20 40 0.460
Tabla 22 0.386
0.779
0.972
0.763
0.157
0.979
0.532
0.361
0.896
Tabla 23
ACTIVIDAD 2
Utilizando los números aleatorios de la tabla 23, simule 15 días de
demanda de un producto en particular, suponiendo que:
a) La demanda de este artículo se puede aproximar con una
distribución uniforme en el intervalo [20, 30].
b) La demanda de este artículo se puede aproximar con una
distribución normal de media 40 y desviación estándar 5.
ACTIVIDAD 3
La empresa ConstruCor SA está preparando su oferta para presentarse
en la licitación de reparación de la avenida Sabatini de nuestra ciudad.
Otros dos contratistas presentarán ofertas para el mismo proyecto. Con
base en el análisis de licitaciones anteriores, ConstruCor estima que las
ofertas de los otros contratistas pueden describirse con las siguientes
distribuciones de probabilidad:
370 CAPÍTULO 11
ACTIVIDAD 4
ARG Líneas Aéreas opera un vuelo diario entre Córdoba y Mendoza con
un avión que tiene capacidad para 50 pasajeros. ARG obtiene un margen
de utilidad de $120 con cada pasajero en el vuelo. El análisis de los vuelos
del último año ha demostrado que, en promedio, dos pasajeros
reprograman su vuelo. Como resultado de esto, con 50 reservaciones, la
empresa está promediando una utilidad de $5.760 por vuelo. ARG quiere
analizar el resultado que se obtendría con una política de reservaciones
en exceso en la que se aceptarían hasta 52 reservas.
El costo por cualquier pasajero al que se le niegue un asiento en el vuelo
debe cubrir los gastos de reprogramación del pasajero más un importe
estimado por pérdida del cliente, este total fue calculado en $150 por
pasajero.
La distribución de probabilidad para la cantidad de pasajeros que se
presentan puede aproximarse con una distribución normal de media 50 y
desviación estándar de 2.
Utilice un modelo de simulación para evaluar esta política.
ACTIVIDAD 5
El hotel Zona Sur se encuentra en la provincia de La Pampa, en el cruce
de las rutas provincial Nº 20 y nacional Nº 151. Este cruce se constituye
MODELOS DE SIMULACIÓN 371
un paso casi obligado para los que viajan a la zona de los parques
nacionales Nahuel Huapi y Lanín. El hotel tiene 100 habitaciones y cada
noche de la temporada de vacaciones de verano se reciben hasta 105
reservaciones, debido a la posibilidad de que no todos se presenten. Los
registros indican que el número de reservaciones diarias se puede
aproximar con una distribución uniforme en el intervalo [96, 105]. Los
que no llegan, se representan mediante la distribución de la tabla que se
presenta a continuación:
Nº de los que no
0 1 2 3 4 5
se presentan
Tabla 26
ACTIVIDAD 6
K&C SA compra cada semana 80 unidades de un determinado producto,
sabiendo que los que no se pueden vender deben desecharse al finalizar
la semana.
El gerente de comercialización opina que una política de compras de 100
unidades por semana será más beneficiosa para la empresa, tanto desde
el punto de vista de la utilidad obtenida como del nivel de servicio
ofrecido.
Al gerente le interesa saber si es conveniente cambiar la política actual y,
en ese caso, a cuánto ascendería la utilidad promedio y el nivel de servicio
ofrecido.
Estudios realizados sobre la demanda del producto indican que se puede
aproximar con una distribución normal de media 100 unidades y
desviación estándar 20 unidades.
372 CAPÍTULO 11
Nº Aleatorio
0.028 0.005 0.214 0.377
0.076 0.687 0.432 0.011
0.286 0.108 0.769 0.957
0.025 0.132 0.506 0.923
0.294 0.163 0.023 0.171
0.842 0.615 0.746 0.748
0.208 0.903 0.412 0.684
0.605 0.673 0.955 0.677
0.292 0.711 0.188 0.144
0.444 0.993 0.298 0.339
Tabla 29
ACTIVIDAD 7
Los autos que llegan a la playa de un supermercado presentan una
distribución Poisson con media de 50 autos/hora. El tiempo de demora
dentro del supermercado sigue una distribución uniforme en el intervalo
[15, 25]. En la playa existe un techo que proporciona sombra para 15
autos.
a) Simule la llegada de 20 automóviles a la playa, utilice los números
aleatorios que se dan en la tabla 30.
b) Defina las variables y parámetros que utiliza en el modelo.
c) Indique cuál es la probabilidad de que al ingresar un auto a la playa
encuentre un lugar con sombra.
Nº Aleatorios
0.4226 0.2485
0.3833 0.9373
0.2330 0.0181
0.8542 0.7318
0.8220 0.5335
0.3455 0.1124
0.4618 0.9564
0.7612 0.9546
0.0215 0.1326
0.3846 0.7435
Tabla 30
CAPÍTULO 12
Conocimientos básicos previos
1.1. VECTORES
Definición
Sean p1, p2, ..., pn, n números reales, un vector fila o renglón se define
como un conjunto ordenado de dichos números escritos de la siguiente
manera:
P = p1 p2 .. .. pn
p1
p
2
.
P=
.
.
pn
Vector unidad
Es un vector cuya i-ésima componente es igual a la unidad y todos los
demás elementos son nulos.
Ejemplo:
0 1 1 0 1 0 0 0 0 1 0
Vector nulo
Es aquel vector cuyas componentes son todas iguales a cero.
Ejemplo: = 0 0 0 0
Igualdad de vectores
Dos vectores V y P son iguales, y se escribe V=P si todas sus componentes
correspondientes son iguales.
V =P vi = pi i
Dos vectores no pueden ser iguales a menos que tengan el mismo número
de componentes.
Notar que si V=P P=V
n
X Y = xi yi = escalar
i =1
Ejemplo:
X = 1 −2 0 2 Y = −1 3 2 6
Propiedades:
1. XY=YX
2. (X) Y = (X Y)
3. (X + Y) Z = X Z + Y Z
4. XX0 XX=0 X=
P = + p1 + p2 + .... + pn
2 2 2
n
P =+ p
2
i
i =1
P = + P.P
a x
X = + a2 + b2
376 CAPÍTULO 13
P + Q = ( p1 + q1 ) ( p2 + q2 ) .. .. ( pn + qn )
Propiedades:
1. P + Q = Q + P
2. P+ (Q +S) = (P + Q) + S
3. P + (-P) =
Propiedades:
1. c(P+S) = cP + cS
2. (c + d)P = cP + dP
3. c(dP) = (cd) P
4. 1P = P
5. 0P =
n
V = 1V1 + 2V2 + ..... + nVn = iVi
i =1
CONOCIMIENTOS BÁSICOS PREVIOS 377
se dice que es una combinación lineal de los vectores V1, V2, ..., Vn siendo
los i los coeficientes de esa combinación lineal.
Ejemplo:
2 0
V1 = V2 = 1 =2 y 2 = −1
−1 −3
El vector V será:
2 0 4 0 4
V = 2 + (−1) = + =
−1 −3 −2 3 1
Observaciones:
1. El vector nulo es combinación lineal de cualquier conjunto de vectores.
Para ello es suficiente con elegir los escalares todos iguales a cero.
0 a c
= V1 = V2 =
0 b d
a c 0
1 + 2 = es suficiente con que 1 = 2 = 0
b d 0
n
W = 1V1 + 2V2 + ..... + nVn = iVi
i =1
1 = 2 = 3 = .... = n = 0
De esta manera, ningún vector podrá ser expresado en función de los
restantes.
Observaciones:
1. Cualquier vector puede expresarse de una única forma como
combinación lineal de k vectores linealmente independientes.
2. Todo conjunto de vectores que contenga al vector nulo es linealmente
dependiente.
3. Un conjunto que contiene un solo vector es linealmente dependiente
si se trata del vector nulo y linealmente independiente en cualquier
otro caso.
4. El conjunto formado por los vectores unidad, en todos los casos, es
linealmente independiente.
1.2. MATRICES
Definición
CONOCIMIENTOS BÁSICOS PREVIOS 379
2 1 0
4 0 8
Algunos conceptos:
Diagonal principal:
x
x
x
5 − 1 1
0 3 9
0 0 4
1 0 0
0 1 0
0 0 1
380 CAPÍTULO 13
Matriz nula: si todos los elementos son iguales a cero, se simboliza como
.
0 0 0
= 0 0 0
0 0 0
Suma de matrices
Sean A=(aij) y B=(bij) dos matrices mxn. La suma A+B de las dos matrices
es la matriz mxn:
A+B = (aij) + (bij) = (aij + bij)
Propiedades:
1. A + = A
2. A + B = B + A
3. A + (B + C) = (A + B) + C
Propiedades:
Sean A y B dos matrices mxn y y escalares, entonces:
6. (A+B) = A + B
7. ( + )A = A + A
8. (A) = () A
9. 1A = A
10. 0A =
Multiplicación de matrices
Sean A una matriz de orden mxr y B una matriz de orden rxn el producto
AB es la matriz mxn cuya componente ij-ésima es el producto interno del
renglón i-ésimo de A y la columna j-ésima de B.
Para que puedan multiplicarse deben ser compatibles, es decir:
CONOCIMIENTOS BÁSICOS PREVIOS 381
AM N BN P = CM P
Propiedades:
(AB) C = A (BC)
1. A (B+C) = AB + AC
2. (B + C) A = BA + CA
no es conmutativa
Matrices Reducidas
1 0 0 0 1 4 2 0 1
1 0 0 0 1 0 0 -1 1 0 0 0
0 1 0 1 0 0 0
1 5 1 0 0 1 0 0 0 2 0 0
0 0 1 0 0 0 1 3 0
0 0 1 0 0 1 2 0 0 1 1
0 0 0 0 0 0 0 1 2
Matrices No Reducidas
Esta matriz tiene rango 2, ya que la segunda fila es igual a la primera más
la tercera, esto implica que el rango final no puede ser igual a 3.
De la definición de rango podemos deducir que este es un número entero
no negativo asociado a la matriz dada.
Por ejemplo, para una matriz A3x5, el valor del rango debe ser menor o
igual a 3. No puede ser mayor, ya que esto significaría que la matriz tiene
más de 3 filas linealmente independientes y esto es imposible.
En general, considerando una matriz Anp, el valor numérico del rango de
A que simbolizamos r(A) estará acotado de la siguiente manera:
CONOCIMIENTOS BÁSICOS PREVIOS 383
0 ≤ r(A) ≤ mín (n , p)
Podemos decir que el rango de una matriz está dado por el número de
líneas (filas o columnas) no nulas de su matriz reducida. Según contemos
filas o columnas, tendremos el rango y fila y el rango columna.
Matriz traspuesta
Si A es una matriz mxn, entonces la traspuesta de A, que simbolizamos
como A, es una matriz nxm cuyo i-ésimo renglón es la j-ésima columna
de A y cuya j-ésima columna es el i-ésimo renglón de A.
En símbolos, si
A = (aij) A = (aji)
Ejemplo:
2 4
2 0 -1
A= A = 0 6
4 6 8 -1 8
donde x1, x2, …, xn son las variables y los coeficientes aij y bi son
constantes numéricas reales.
En forma matricial:
384 CAPÍTULO 13
a 11
a12 .. a1n x b
1 1
a a22 .. a2n x b
21
=
2 1
. . . . .. ..
a am2 .. amn
x b
m1 n m
es decir:
AX =B
SISTEMA DE ECUACIONES
COMPATIBLE INCOMPATIBLE
a 11
a12 .. a1n x b
1 1
a a22 .. a2n x b
21
=
2 1
. . . . .. ..
a am2 .. amn
x b
m1 n m
a11
a12 . . a1n b1
a a22 . . a2n b 2
21
AB = . . . . . .
a
m1
am2 . .amn bm
De acuerdo al concepto de sistemas de ecuaciones equivalentes, si
obtenemos la matriz AB por aplicación de operaciones elementales en fila
sobre la matriz AB, entonces los sistemas de ecuaciones AX = B y AX = B
serán equivalentes.
Basándose en esto, el método de Gauss Jordan aplica sistemáticamente
operaciones elementales en fila sobre la matriz ampliada del sistema
hasta obtener un sistema de ecuaciones equivalente. La utilización de
estas operaciones se realiza hasta obtener la matriz reducida por filas de
A. Esquemáticamente el método consiste en:
A B
OPERACIONES
ELEMENTALES EN FILA
RA B
R AX = B
Soluciones básicas
Ya dijimos que los sistemas de ecuaciones pueden ser incompatibles,
cuando no tienen solución, o compatibles si tienen solución. A su vez, los
sistemas compatibles pueden ser determinados cuando tienen una única
solución o indeterminados cuando tienen infinitas soluciones.
Dentro de las infinitas soluciones de un sistema compatible
indeterminado, existe un subconjunto de soluciones con características
particulares a las que se las denomina soluciones básicas (SB).
La particularidad de una solucione básica (SB) es que, de los n valores de
las variables, tendrá como máximo m valores distintos de cero y los
restantes n-m serán nulos. Así, por ejemplo, si tenemos un sistema de
ecuaciones indeterminado con siete variables y tres ecuaciones, una SB
tendrá como máximo tres valores de las variables distintos de cero y los
restantes, cuatro en este caso, serán nulos.
A su vez, si la SB tiene exactamente m valores distintos de cero o, lo que
es lo mismo, exactamente n-m valores iguales a cero, se llama solución
CONOCIMIENTOS BÁSICOS PREVIOS 387
n!
C nm =
m ! (n − m )!
Esquemáticamente:
Primer ejemplo:
18 x1 + 9 x2 = 90
5 x1 + 10 x2 = 50
x1 x2 B Matriz Ampliada
F1 18 9 90
F2 5 10 50
F1´ 1 0,5 5 1ero) F1´= F1/18
2 ) F2´= F1´x (-5)+ F2
do
F2´ 0 7,5 25
F1" 1 0 3,3333
F2" 0 1 3,3333 1ero) F2”= F2´/5
2 ) F1”= F2”x (-0,5)+ F1´
do
1x1 + 0 x2 = 3,3333
0 x1 + 1 x2 = 3,3333
Segundo ejemplo:
8 x1 + 10 x2 + 12 x3 = 160
15 x1 + 10 x2 + 5 x3 = 250
x1 x2 x3 B
F1 8 10 12 160
F2 15 10 5 250
F1´ 1 1,25 1,5 20
F2´ 0 -8,75 -17,5 -50
F1" 1 0 -1 12,85
F2" 0 1 2 5,71
x1 x2 x3 B
1 0 -1 12,85
0 1 2 5,714
1 0,5 0 15,714
0 0,5 1 2,857
1 x1 + 0 x3 = 15,714 (2)
0 x1 + 1 x3 = 2,857
x1 = 15,714
x2 = 0
x3 = 2,857
x1 x2 x3 B
1 0,5 0 15,714
0 0,5 1 2,857
2 1 0 31,429
-1 0 1 -12,857
1 x2 + 0 x3 = 31,429
0 x2 + 1 x3 = -12,857
390 CAPÍTULO 13
x1 = 0
x2 = 31,429
x3 = -12,857
La expresión:
2x +y ≤ 12
se llama inecuación lineal en las variables x e y. Esta expresión se cumple
para algunos valores de las variables y su gráfica es un semiplano.
Las inecuaciones pueden ser de una o varias variables, una inecuación
con dos incógnitas (o variables) puede presentarse de alguna de las
formas que se muestran a continuación:
ax + by + c ≤ 0
ax + by + c < 0
ax + by + c ≥ 0
ax + by + c > 0
Ejemplo de aplicación
Representemos gráficamente el siguiente sistema de inecuaciones:
8X+ 5 Y ≤ 240
3X+ 5 Y ≤ 150
X ≥0
Y ≥0
Como ya dijimos, el conjunto de puntos solución de cada inecuación lineal
es un semiplano espacio bidimensional y la intersección de los semiplanos
correspondientes a cada inecuación forma el conjunto solución del
sistema.
La forma más sencilla de representar este semiplano es partiendo de la
ecuación de la recta que está implícita en la inecuación (es decir,
CONOCIMIENTOS BÁSICOS PREVIOS 391
8X + 5 Y = 240
X + 5 Y = 150
1.5. FUNCIONES
Concepto de función
Dados dos conjuntos no vacíos X e Y, se llama función de X en Y a una
regla que asigna a cada elemento x que pertenece a X un único elemento
y que pertenece a Y. Simbólicamente y = f(x).
Ejemplos de funciones:
f ( x) = 25 + 5x ➔ Función lineal
5x + 5
f ( x) =
x −1
Dándole valores a x, obtendremos los valores de la función.
Concavidad y convexidad
En general, una función cóncava tiene la propiedad de que el segmento
de recta que conecta dos puntos cualesquiera de la gráfica de la función
nunca pertenecen al espacio ubicado por arriba de la gráfica.
f(x) Cóncava
Función cóncava
f(x)
Convexa
x
Función convexa
-1 x
Ni cóncava ni convexa
394 CAPÍTULO 13
Definición:
Sea f: Rn→ R
f es convexa si el dominio de f es un conjunto convexo y si para todo x 1,x2
que pertenece al dominio de f y para todo número real t entre 0 y 1, se
satisface que:
f(x) Convexa
x1, f(x1)
x2, f(x2)
x1 x2 x
Máximos y mínimos
Funciones de una variable
Una función f tiene un máximo relativo en el punto a, si f(a)
es mayor o igual que los puntos próximos al punto a.
Una función f tiene un mínimo relativo en el punto a, si f(a)
es menor o igual que los puntos próximos al punto a.
Es decir que tanto los máximos como los mínimos son llamados relativos
porque los comparamos con puntos vecinos muy cercanos y no podemos,
por lo tanto, afirmar que sean máximos o mínimos absolutos, es decir,
considerando toda la función.
Entonces:
Un punto (a,f(a)) es llamado máximo relativo de f(x) si existe un
intervalo abierto alrededor de a tal que f(x) ≤ f(a) para todo x
perteneciente el intervalo.
CONOCIMIENTOS BÁSICOS PREVIOS 395
2 f 2 f 2 f
.....
x1
2
x1x2 x1xn
2 f 2 f 2 f
.....
H ( f ) = x2 x1 x22 x2 xn
..... ..... ...... .....
2 f 2 f 2 f
......
xn x1 xn x2 xn2
Variables aleatorias
Una variable aleatoria es cierto fenómeno de interés cuyas respuestas o
resultados pueden expresarse numéricamente.
Formalmente, dado un espacio de probabilidad (, A, P), una variable
aleatoria unidimensional X es una función real definida sobre el espacio
muestral que transfiere la estructura probabilística del espacio muestral
a los números reales R definidos.
X: → R
Tal que [X=x] es un evento aleatorio para todo x que pertenece a los
reales.
Donde:
: es el conjunto de resultados posibles de un experimento aleatorio.
A: es el álgebra de conjuntos y/o familia de eventos.
P: es la probabilidad asociada a cada resultado del conjunto y del
conjunto A.
Función de probabilidad
En el caso discreto, se denomina función de cuantía p(x) y asocia una
probabilidad a cada posible valor de la variable.
Condiciones esenciales que debe cumplir una función de
cuantía:
1 - Las probabilidades asociadas a los distintos valores que puede
asumir la variable deben ser no negativos → p(x) 0 para todo x
2 - La suma de todas esas probabilidades debe dar uno →
∑ki=1 p(xi )=1
Donde k es la cantidad de valores que asume la variable.
CONOCIMIENTOS BÁSICOS PREVIOS 397
Función de distribución
La función de distribución F(x) de una variable aleatoria X acumula
probabilidades desde el valor mínimo que asume la variable hasta un valor
genérico 𝑥0 perteneciente a su recorrido. Es decir, la función de
distribución permite obtener la probabilidad que la variable asuma
cualquier valor menor o igual que 𝑥0 .
Formalmente:
F: R → [0,1]
𝐹(𝑥0 ) = 𝑃(𝑋 ≤ 𝑥0 ); 𝑥0 ɛ 𝑅
Esperanza Matemática
La Esperanza Matemática E(X) es el valor promedio que se presentará si
el experimento se repite un número grande de veces.
𝐸(𝑋) = µ = ∑ 𝑥𝑖 𝑝(𝑥𝑖 )
𝑖=1
+∞
𝐸(𝑋) = µ = ∫−∞ 𝑥 𝑓(𝑥)𝑑𝑥
Varianza
La varianza V(X) mide la dispersión de los datos en torno a la Esperanza
Matemática si el experimento se repite un número grande de veces. Se
define como la esperanza de los desvíos al cuadrado de los valores de la
variable respecto al valor esperado, razón por la cual asume siempre
valores no negativos.
𝑉(𝑋) = 𝜎 2 = 𝐸[𝑋 − µ] 2
Desviación estándar
La desviación estándar DS(X) de una variable aleatoria X se define a partir
de su varianza como:
𝐷𝑆(𝑋) = 𝜎 = √𝑉(𝑋)
Distribución Poisson
La variable Poisson se define como:
X = Número de sucesos independientes en un intervalo de longitud fija
(tiempo o espacio)
𝑒 −𝜆 𝜆𝑥
𝑃(𝑋 = 𝑥) = { 𝑥 = 0,1,2, …
𝑥!
0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
CONOCIMIENTOS BÁSICOS PREVIOS 399
𝑠
𝑒 −𝜆 𝜆𝑥
𝑃(𝑋 ≤ 𝑠) = ∑
𝑥!
𝑥=0
Distribución exponencial
La variable exponencial se define como:
X = Tiempo entre la ocurrencia de dos sucesos consecutivos
𝑓(𝑥) = { 𝜆𝑒
−𝜆𝑥
𝑥0
0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜
0 𝑥˂ 0
𝐹(𝑥) = {
1 − 𝑒 −𝜆𝑥 𝑥0
1
Esperanza Matemática 𝐸(𝑋) =
𝜆
1
Varianza 𝑉(𝑋) =
𝜆2
1
Desviación estándar 𝐷𝑆(𝑋) =
𝜆
Distribución uniforme
Una variable X con distribución uniforme es aquella que tiene la misma
probabilidad de ocurrir cualquiera fuera el valor que asuma dentro de un
intervalo determinado (a,b), donde los límites a y b constituyen los
parámetro de esta distribución.
400 CAPÍTULO 13
(𝑎+𝑏)
Esperanza Matemática 𝐸(𝑋) =
2
(𝑏−𝑎)2
Varianza V(X) =
12
(𝑏−𝑎)
Desviación estándar 𝐷𝑆 (𝑋) =
√12
Distribución normal
Es un modelo de variable continua con distribución perfectamente
simétrica, constituyéndose sumamente relevante en la estadística por sus
variadas aplicaciones en gran cantidad de fenómenos reales.
La variable con distribución normal puede asumir valores en el intervalo
(-∞, +∞) y los parámetros que caracterizan a esta distribución son:
media µ y varianza σ2.
1 1(𝑥−µ)2
−
𝑓(𝑥) = 𝑒 2 𝜎2 − ∞ ≤ 𝑥 ≤ +∞
𝜎√2
𝑋− µ
𝑍= ~ N (0,1)
σ
1 𝑧2
𝑓(𝑧) = 𝑒− 2 − ∞ ≤ 𝑧 ≤ +∞
√2
𝑧 𝑡2
1
𝐹(𝑧) = 𝑃(𝑍 ≤ 𝑧) = ∫ 𝑒 − 2 𝑑𝑡
−∞ √2
0 1,2 z
-1,4 0 z
0 1,4 z
3. 𝑃(−1,40 < 𝑍 < 1,20) = 𝐹(1,20) – 𝐹(−1,40) = 𝐹(1,20) – 𝑃(𝑍 > 1,40) =
𝐹(1,20)– [1 – 𝐹(1,40)] = 0,8849 – [1– 0,9192] = 𝟎, 𝟖𝟎𝟒𝟏
-1,4 0 1,2 z
4. 𝑃(−1,40 < 𝑍 < −0,70) = 𝑃(0,70 < 𝑍 < 1,40) = 𝐹(1,40) – 𝐹(0,70) =
0,9192– 0,7580 = 𝟎, 𝟏𝟔𝟏𝟐
-1,4 -0,7 0 z
CONOCIMIENTOS BÁSICOS PREVIOS 403
0 0,7 1,4 z
Distribución beta
Es una distribución de probabilidad continua con parámetros: y , donde
la variable está acotada entre un máximo a y un mínimo b.
𝑏+ 𝛽 𝑎
Esperanza Matemática 𝐸(𝑋) =
( + )
(𝑏 − 𝑎)2
Varianza V(X) = ( + )2 ( + + 1)
(𝑏 − 𝑎)2
Desviación estándar 𝐷𝑆 (𝑋) = √ ( )2
+ ( + + 1)
( − 1)𝑏 + ( − 1)𝑎
𝑚=
+−2
𝑎+4𝑚+𝑏
Esperanza Matemática 𝐸(𝑋) =
6
𝑏−𝑎 2
Varianza V(X) = ( )
6
𝑏−𝑎
Desviación estándar 𝐷𝑆 (𝑋) =
6
404 CAPÍTULO 13
CAPÍTULO 13
RESPUESTAS A PROBLEMAS
SELECCIONADOS
CAPÍTULO 2
ACTIVIDAD 4
DATOS:
Demanda 10 15 20 25 30
Nº de días 10 25 30 20 15
Probabilidad 0,1 0,25 0,3 0,2 0,15
DEFINICIÓN DE VARIABLES:
Oferta/Demand
a Y1= 10 Y2= 15 Y3= 20 Y4= 25 Y5= 30 d(x)
X1= 10 100 175 250 325 400 253.75
X2= 15 115 150 225 300 375 232.75
X3= 20 130 165 200 275 350 221.75
X4= 25 145 180 215 250 325 222.75
X5= 30 160 195 230 265 300 231.75
Pj 0.1 0.25 0.3 0.2 0.15
ACTIVIDAD 5
DATOS:
Pr. venta por unidad: $1,25
406 CAPÍTULO 13
Definición de variables:
Xi = cantidad de yogurt a comprar por semana
Yj = cantidad de yogurt demandado por semana
Matriz R = Y1 Y2 Y3 Savage
[rij] 100 200 300 d(x)
X1: 100 0 8 16 16.00
X2: 200 20 0 8 20.00
X3: 300 40 20 0 40.00
ACTIVIDAD 7
El árbol que describe este problema y las probabilidades asociadas a las
posibles alternativas es el siguiente:
RESPUESTAS A PROBLEMAS SELECCIONADOS 407
CAPÍTULO 3
ACTIVIDAD 11
a) Complete la tabla
30 20 15 0 0
CB Base VLD x1 x2 x3 S1 S2
15 x3 5 0 0,5 1 -0,5 0
30 x1 20 1 0,5 0 0,5 0
0 S2 30 0 1,5 0 -0,5 1
Zj 675 30 22,5 15 7,5 0
0 -2,5 0 -7,5 0
ACTIVIDAD 12
La siguiente tabla corresponde a un PL de maximización canónico (con
restricciones del tipo ):
Cj 15 10 20 0 0 0
CB Base VLD x1 x2 x3 S1 S2 S3
Cj 15 10 20 0 0 0
CB Base VLD x1 x2 x3 S1 S2 S3
20 x3 10,00 0,20 0,00 1,00 0,40 -0,20 0,00
10 x2 120,00 1,40 1,00 0,00 -0,20 0,60 0,00
0 S3 20,00 -3,60 0,00 0,00 -0,20 -1,40 1,00
Zj 1400,00 18,00 10,00 20,00 6,00 2,00 0,00
C j - Zj -3,00 0,00 0,00 -6,00 -2,00 0,00
Solución óptima:
x1 = 0
x2 = 120
x3 = 10
S1 = 0
S2 = 0
S3 = 20
Z = 1400
RESPUESTAS A PROBLEMAS SELECCIONADOS 409
ACTIVIDAD 16
I. DESECHOS INDUSTRIALES
Objetivo: minimizar el costo total de procesamiento de la basura y de
transporte. Para el cálculo de los costos, se deben tener en cuenta tanto
los costos de transporte por t como el costo de quemar cada tonelada de
basura.
Definición de variables:
x1 = t de basura que se transporta desde la fábrica al quemador 1
x2 = t de basura que se transporta desde la fábrica al quemador 2
x3 = t de desechos que se transportan desde el quemador 1 al
enterramiento 1
x4 = t de desechos que se transportan desde el quemador 1 al
enterramiento 2
x5 = t de desechos que se transportan desde el quemador 2 al
enterramiento 1
x6 = t de desechos que se transportan desde el quemador 2 al
enterramiento 2
Restricciones:
1. La fábrica produce 100 t de basura diaria que deben ser
transportadas a alguno de los dos quemadores.
2. Cada quemador puede recibir hasta 80 t de basura.
3. La basura que entra a cada quemador se transforma en desechos
que deben ser transportados a los enterramientos.
4. Cada enterramiento puede recibir hasta 50 t de desechos cada
uno.
Modelo lineal:
Min 60 x1 + 80 x2 + 30 x3 + 45 x4 + 48 x5 + 36 x6
Sa:
x1 + x2 = 100
x1 ≤ 80
x2 ≤ 80
x3 + x4 = 0,25 x1
x5 + x6 = 0,20 x2
x3 + x5 ≤ 50
x4 + x6 ≤ 50
x1; x2; x3; x4; x5; x6 ≥ 0
410 CAPÍTULO 13
NARANJA POMELO
Precio de venta 5(0,525) = 2,625 6(0,455) = 2,73
Costo MP 0,75 0,8
Costo M1 (1/125)30 =0,24 (1/125)30 = 0,24
Costo M2 (1/55)80(0,7) =1,018
Costo M3 (1/60)90(0,65) = 0,975
Costo Envase 0,10(0,525) = 0,0525 0,10(0,455) = 0,0455
Contribución por kg 0,5645 0,6695
Observaciones:
1
= 0,008 tiempo de procesamiento de 1 kg de fruta en la M1
125
1
= 0,01818 tiempo de procesamiento de 1 lt. de jugo de naranja en la M2
55
1
= 0,01666 tiempo de procesamiento de 1 lt. de jugo de pomelo en la M2
60
Modelo lineal:
CAPÍTULO 4
ACTIVIDAD 5
a) G1 = 57,5 unid. ; G2 = 85 unid. ; G3 = 40 unid
S1 = 55; S2 = S3 = S4 = 0
Z = $2.667,50
b) El precio dual del Hierro Redondo es de 1,5833, como el precio dual es
> 1 , conviene comprar.
c) De acuerdo al análisis de sensibilidad, la máxima cantidad a comprar
está dada por el análisis de sensibilidad, que es de 110 u. hasta el límite;
el precio dual es válido para realizar el análisis.
d) La utilidad total podría incrementarse hasta en 1,111111.
ACTIVIDAD 6
Cj 40 60 50 0 0 0
CB Base VLD x1 x2 x3 S1 S2 S3
Zj 42000 160 60 50 30 0 10
ZDUAL = 42000
Nueva solución:
b3 = 100
1
x3 = 600 + 100 = 650
2
−1
x2 = 200 + 100 = 175
4
1
S2 = 200 + 100 = 225
4
1
c1 − z1 = −120 − c3 0 c3 −240
2
1
c6 − z6 = −10 − c3 0 c3 −20
2
RESPUESTAS A PROBLEMAS SELECCIONADOS 413
600 0 0
200 + b 1/2
1
=
0
200 −1 / 2 0
1
200 + b1 0 b1 −400
2
1
200 − b1 0 b1 400
2
1
600 + b2 0 b2 −1200
2
−1
200 − b2 0 b2 800
4
1
200 + b2 0 b2 −800
4
CAPÍTULO 5
ACTIVIDAD 1
1) h= 9; k= 6
414 CAPÍTULO 13
Cantidad de valores nulos que deberá tener una solución para que sea no
básica= (h x k)-(k+k-1)= 38
2) h= 5; k= 8
Cantidad de valores positivos que deberá tener una solución para que sea
básica degenerada= h+k-1= 12
3) X34 = 20, si el origen 3 es ficticio, indica que quedan 20 unidades de
demanda insatisfecha en el destino 4.
ACTIVIDAD 2
FALSO: xij son las variables de decisión. Representa la cantidad a enviar
desde el origen i al destino j.
El costo de enviar una unidad desde el origen i hacia el destino j se
representa por los parámetros cij.
ACTIVIDAD 3
Solución óptima:
Se deberán enviar:
92 unidades desde elorigen 1 al destino 2.
74 unidades desde el origen 2 al destino 2.
El origen 3 deberá enviar 37 unidades al destino 1 y 49 unidades al
destino 2.
El destino 1 queda con 136 unidades de demanda insatisfecha.
El costo total de envío óptimo es de $4.369.
RESPUESTAS A PROBLEMAS SELECCIONADOS 415
ACTIVIDAD 5
Se debe asignar de la siguiente manera:
A ➔ 1 ➔ $15
B ➔ 4 ➔ $14
C ➔ 3 ➔ $15
D ➔ 2 ➔ $24
Costo Total: $68.
ACTIVIDAD 10
B)
Min 0,20 x12 + 0,15 x13 + 0,10 x24 + 0,20 x25 + 0,15 x34 + 0,25 x35
Sa
2000 = x12 + x13
x12 = x24 + x25
x13 = x34 + x35
x24 + x34 ≥ 600
x25 + x35 ≥ 800
x12 ≤ 1000
x13 ≤ 500
416 CAPÍTULO 13
ACTIVIDAD 11
60
3
100 50 90
1 6
4
150
2 100
7
ACTIVIDAD 12
Max f
Sa
f= x12 + x13 + x14
x12 = x23 + x25
x13 + x23 = x34 + x35
x14 + x34 = x45
x25 + x35 + x45 = f
x12 ≤ 100
x13 ≤ 300
x14 ≤ 200
x23 ≤ 100
x25 ≤ 400
x34 ≤ 200
x35 ≤ 300
x45 ≤ 650
xij ≥ 0 para todo i,j f≥0
CAPÍTULO 6
ACTIVIDAD 1
RESPUESTAS A PROBLEMAS SELECCIONADOS 417
ACTIVIDAD 2
Objetivo: minimizar los costos totales.
Variables:
xij = Unidades fabricadas y enviadas desde el depósito i a la Región j
i = Córdoba, Buenos Aires, Rosario y Mendoza
j = Región I, Región II y Región III
yi = Se abre o no el depósito i
418 CAPÍTULO 13
Modelo lineal:
Min 20 x11+ 40x12 + 50x13 + 48x21 + 15x22 + 26 x23 + 26x31 + 35x32 +
18x33 + 24x41 + 50x42 + 35x43 +1200 y1 + 1000y2 + 1100y3 + 1400y4
Sa
1.
x11+ x12 + x13 ≤ 100y1
x21 + x22 + x23 ≤ 100y2
x31 + x32 + x33 ≤ 100y3
x41 + x42 + x43 ≤ 100y4
2.
x11 + x21 + x31 + x41 ≥ 80
x12 + x22 + x32 + x42 ≥ 70
x13 + x23 + x33 + x43 ≥ 50
3.
y1 – y2 ≤ 0
y1 + y2 + y3 + y4 ≤ 2
y3 + y4 = 1
xij ≥ 0 y enteras
(i = Córdoba, Buenos Aires, Rosario y Mendoza) , (j = Región I,
Región II y Región III)
yi = 0 ó 1
ACTIVIDAD 3
Objetivo: maximizar el beneficio total.
Variables:
A = unidades del radiador A a producir
B = unidades del radiador B a producir
C = unidades del radiador C a producir
yi = se produce o no el radiador i (i = A, B ó C)
Modelo lineal:
Max 20A + 35B + 30C - 1000 yA - 2000 yB -1500 yC
Sa
0,015A + 0,020B + 0,020C ≤ 20
0,025A + 0,035B + 0,030C ≤ 100
RESPUESTAS A PROBLEMAS SELECCIONADOS 419
ACTIVIDAD 4
Respuesta correcta: c)
ACTIVIDAD 5
1. P1 – P2 ≤ 0
2. P1 + P2 = 1
3. P1 – P3 ≤ 0
4. P1 + P2 ≤ 1
ACTIVIDAD 6
Falso. x2 – x 1 ≤ 0
CAPÍTULO 7
ACTIVIDAD 2
Cada hilera de los ajíes verdes y rojos tiene 2 m de ancho, por lo tanto,
el máximo de hileras para cualquiera de ellos es de 5, en tanto que el
máximo de hileras para los ajíes amarillos es de 3.
De los ajíes verdes quiere sembrar, por lo menos, una hilera; y de los
amarillos, como máximo, 3 hileras.
Las etapas serán:
A ➔ R ➔ V, por lo que empezamos por la tercera etapa.
Variables de estado (x) los metros de terreno disponibles.
Variables de decisión (d) las hileras de cada tipo de ají a sembrar.
420 CAPÍTULO 13
d2
0 1 2 3 4 d2* f2*(x2)
x2
10 500 470 440 410 380 0 500
7 300 270 240 0 300
4 200 170 0 200
d1
0 1 2 3 d1* f1*(x1)
x1
10 500 350 100 0 500
La función recursiva:
fn (xn) = rn (dn) + f*n+1 (xn – k dn)
rn = rendimiento de la etapa n
k = ancho de la hilera
El rendimiento óptimo de la etapa n será:
fn*(xn) = máx rn {(dn) + f*n+1 (xn – k dn) }
CAPÍTULO 8
ACTIVIDAD 4
Objetivo: maximizar las utilidades.
RESPUESTAS A PROBLEMAS SELECCIONADOS 421
Variables:
x1 = unidades de producto 1 a producir
x2 = unidades de producto 2 a producir
x3 = unidades de materia prima a comprar
Max (80 -2x1)x1 + (60 – x2)x2 – 150 x3
Sa
0,5 x1 + 1 x2 – x3 = 100
2 x1 + 3 x2 ≤ 500
x1, x2 ≥ 0
ACTIVIDAD 5
Objetivo: minimizar el costo de la publicidad.
Variables:
x1 = número de anuncios en la radio a contratar
x2 = número de comerciales de TV a contratar
ACTIVIDAD 6
Objetivo: maximizar las utilidades.
Variables:
x1 = kg de Jardín Verde a producir
x2= kg de Bello Parque a producir
x3 = kg de compuesto químico a comprar
Max x1(270-2X1) + x2(150-x2) – 50x3 – 75x1 – 90x2
Sa
x1 + x2 = x3
x3 ≤ 700
xi ≥ 0
ACTIVIDAD 7
422 CAPÍTULO 13
max (500 − 3
)
x1 x1 + 95x2
sa
x1 = 0,5x3
x2 = 0, 2 x3
2 x1 + 3x2 200
x3 150
x1 , x2 0
ACTIVIDAD 9
Objetivo: minimizar el riesgo de la cartera de inversiones.
Variables:
x1 = porcentaje de la cartera a invertir en B. Francés
x2 = porcentaje de la cartera a invertir en Minetti
x3 = porcentaje de la cartera a invertir en Renault
CAPÍTULO 9
ACTIVIDAD 1
A. VERDADERO. Si una actividad no crítica se retrasa más allá de su
tiempo de holgura sin cambiar alguno de los demás factores, la
duración total del proyecto se extenderá en el tiempo que supera a la
holgura.
ACTIVIDAD 2
1) = { (1,3) ; (3,5) ; (5,6) ; (6,8)}
V() = 16
ACTIVIDAD 3
2)
ACTIVIDAD 5
a) El tiempo esperado de finalización de la campaña política es de 28
días. La probabilidad de que este tiempo se cumpla es de 0,5.
424 CAPÍTULO 13
b)
Prob (DT 35) = 0,5
2 2 2 2 2 2
σ = 0,33 +1 + 0,55 + 2 + 0,16 +1 2,54
DT
CAPÍTULO 10
ACTIVIDAD 2
% Particip. %
Artículo % Total Clasificación
de los art. Acumulado
14 0,254623721 5 25,46 % A
19 0,185469932 10 44,01 % A
13 0,160740608 15 60,08 % A
3 0,092734966 20 69,36 % A
6 0,072068317 25 76,56 % A
11 0,052991409 30 81,86 % B
15 0,037835866 35 85,65 % B
9 0,030911655 40 88,74 % B
12 0,026495705 45 91,39 % B
20 0,016506824 50 93,04 % B
18 0,013862553 55 94,42 % B
16 0,01122358 60 95,55 % B
4 0,010598282 65 96,61 % C
2 0,010598282 70 97,67 % C
1 0,006623926 75 98,33 % C
10 0,005299141 80 98,86 % C
8 0,004967945 85 99,36 % C
7 0,003311963 90 99,69 % C
17 0,001589742 95 99,85 % C
5 0,001545583 100 100,00 % C
RESPUESTAS A PROBLEMAS SELECCIONADOS 425
ACTIVIDAD 4
a) Cálculo de la cantidad económica a pedir:
V= N/q;
q= N/V = 4800/30,98 = 154,94
CTs = CTp
CTs = $1859,03
CTs = Cs T q/2
Cs = (2 CTs)/Tq
Cs = 2(1859,03)/12(154,94) = 3718,06/1859,28 = $ 2
ACTIVIDAD 5
POLÍTICA ACTUAL:
q = 520 unidades
t1 = 13 semanas
q h N 8 2080
= 1,6 520 1 1 −
CT = Cs T 1 − + Cp + 300
2 a q 2 12 520
= 138,66667+1200 = $1338,66667
POLÍTICA ÓPTIMA:
2 Cp N 2 (300) 2080
q* = = = 1529,70
h 8
Cs T 1 - 1,6 1 −
a 12
N q h
CT = Cp + Cs T 1 -
q 2 a
2080 1529,70 8
CT = 300 + 1, 6 1- = 407, 92 + 407, 92 = $815, 84
1529,70 2 12
AHORRO DE COSTOS:
1338,667 – 815, 84 = 522,82
426 CAPÍTULO 13
ACTIVIDAD 8
DATOS
t = 250 días
T=1
N = 960 (80x12)
Cp = 20
Cs = 0.2 Pi (por unidad y por año)
PASO 1
2 (20) 960
q *= = 140,69 unidades
3 1,94 (1)
2 (20) 960
q *= = 139,97 unidades
2 1,96 (1)
2 (20) 960
q *= = 138,56 unidades
1 2 (1)
PASO 2
Cs = 0.2 pi
N Tq
CT = Cp + Cs + pi N;
(q, pi) q 2
960 138,56
CT = 20 + 0,2 (10) + 960 (10) = $9.877.-
q*=138.56, p =10
1
138,56 2
1
RESPUESTAS A PROBLEMAS SELECCIONADOS 427
960 300
CTq =300, p =9,8 = 20 + 0,2 (9,8) + 960 (9,80) = $9.766.-
2 3
300 2
960 500
CTq =500, p =9,7 = 20 + 0,2 (9,7) + 960 (9,70) = $9.835,40.-
3 3
500 2
CAPÍTULO 11
Costo por Costo por Utilidad
Ensayo Reserva Asientos Nº Aleatorio Z0 Llegan Entero
sobreventa ausentes Total
ACTIVIDAD 4
DATOS
Capacidad: 50 pasajeros
Utilidad por pasajero: $120
Utilidad promedio con la política actual: $5.760
Analizar la política de aceptar 52 reservas
Costo por asiento vacío: $120
Costo por cada pasajero que no pueda abordar: $150
Utilidad Total = 120 (50) - Costo
Para generar los que llegan x = 50 + (Z0)*2
ACTIVIDAD 5
428 CAPÍTULO 13
DATOS
Hotel tiene 100 habitaciones
Se aceptan hasta 105 reservas
Las reservas se pueden aproximar con una distribución uniforme [96;
105]
Los que no se presentan
P.
Ausentes Probabilidad
Acumlada
0 0,1 0,1
1 0,15 0,25
2 0,2 0,45
3 0,3 0,75
4 0,15 0,9
5 0,1 1
ACTIVIDAD 6
Demanda se puede aproximar Normal con media 100 y desviación 20
unidades
Datos económicos:
Margen Bruto: $50.
Costo almacenamiento unitario: $15 (semanal)
Costo unitario de escasez: $30 (semanal)
RESPUESTAS A PROBLEMAS SELECCIONADOS 429
BIBLIOGRAFÍA
Blanch, N., Caro, N., Casini, R., Chiavassa, N., Díaz, M., Joekes, S. y
Stimolo, M.: Estadística I. Ciclo Básico a Distancia. FCE. UNC. Córdoba,
Argentina.