UNIVERSIDAD LAICA “ELOY

ALFARO” DE MANABÍ

FACULTAD
INGENIERIA INDUSTRIAL

PORTAFOLIO

MATERIA
INT. A LA INVESTIGACIÓN DE OPERACIONES

DOCENTE
ING. ANTONIO ZAVALA ALCÍVAR

CURSO
4 “A”
 AUTORES

BRAVO ESPINAR ANGÉLICA

CABADA HERRERA JAIRO

CABRICES LOPEZ BRANDO

CARRILLO PALMA BRYAN

JARAMILLO HOYOS MIGUEL

LEON LOAYZA FABIAN

LOPEZ VERA THALÍA

MENDOZA VILLAVICENCIO LINDA

MOREIRA DELGADO ALEX

MOREIRA MUÑOZ MARÍA

MOREIRA REYES DENNYS

MOREIRA ROMERO BRYAN

NARVÁEZ VERA KRUSKAYA

PANTA ZAMBRANO RICKY

RIVERA PINARGOTE DIEGO

VALVERDE RODRIGUEZ CÉSAR

VELEZ PARRAGA NICOLS

ZAMBRANO SALTOS MADELYN

ZAMBRANO SANTANA LUIS

 Agradecimiento

De parte de las personas que participaron en la creación

del presente documento, mostramos nuestro
agradecimiento por su tiempo, paciencia y dedicación,
comprometiéndonos a mejorar nuestro desempeño para un
próximo parcial.
 1 er

Parcial

Contenido

¿Por qué nace la IO?

Modelo Matemático

Construcción de modelos
determinísticos

Un problema de minimización
 ¿Por qué nace la IO?

Complejidad Escases de Toma de

industrial recursos decisiones

Recursos Lograr el objetivo utilizando

Adaptabilidad al
limitados menos recursos
mercado

Bajos recursos Polifuncional

Características:

• Método científico
• Asignación de los recursos o actividades de forma eficaz
• Gestión y organización de sistemas complejos
• Ayuda y toma de decisiones
• Enfoque interdisciplinario

Metodología de la IO:

• Planear el problema
• Observar el sistema: recabar información
• Formular modelo matemático del sistema
• Verificar el modelo y predecir
• Seleccionar una opción adecuada (toma de decisiones)
• Sociabilización los resultados de la empresa
• Conformación equipo y puesta en marcha
 Modelo Matemático

Traducción de un modelado matemático:

• Objetivos: Función objetivo

• Alternativas: Variables de decisión
• Limitaciones del sistema: Restricciones

Categorías básicas del problema:

✓ Problemas determinísticos: (se conocen todos los datos) toda información

necesaria para obtener una solución se conoce con certeza.
✓ Problemas estadísticos: (no se conocen todos los datos) parte de la
información no se conoce con certeza.

Técnicas de resolución:
✓ Métodos óptimos: Método usado en la administración que produce los
mejores valores posibles para las variables de decisión
✓ Métodos heurísticos: Método usado en la administración que proporciona
valores aceptables (aunque no necesariamente óptimos) para los variables de
decisión

Identificación de las variables de decisión:

• Proporcionan la solución del problema

• Se le asigna un nombre simbólico (X,Y): nombre descriptivo a una variable de
un modelo matemático que ayuda a la comprensión del significado de la
variable
• Incluyen las unidades asociadas con las cantidades de variables

Tipos de datos:
• Datos no controlados de la situación del problema
• Datos controlados se pueden cuando se especifica el problema
 Construcción de modelos determinísticos
EJERCICIO #1
Un pastelero tiene 150 kg de harina, 22 kg de azúcar y 275 kg de mantequilla para
hacer dos tipos de pasteles P y Q. Para hacer una docena de pasteles de tipo P
necesita 3 kg de harina, 1 kg de azúcar y 1 de mantequilla y para hacer una docena
de tipo Q necesita 6 kg de harina, 0.5 kg de azúcar y 1 kg de mantequilla.
El beneficio que obtiene por una docena de tipo P es $20 y por una docena de tipo
Q es $30. Hallar utilizando las técnicas de programación lineal, el número de
docenas que tiene que hacer de cada clase para que el beneficio sea máximo.
Solución:
MODEL
Max de f (p, q) =$20 * p +$30* q FO

SUBJECT TO
3P + 6Q =150 Kg Harina
1P + 1/2Q <=22 Kg Azúcar
1P + 1Q <=275 Kg Mantequilla
p, q >= 0 No Negatividad

Max 20 P +30 Q
3P + 6Q <=150 Kg Harina Deben tener al
menos una variable
P+ <=22 Kg Azúcar
de decisión
P+Q <=275 Kg Mantequilla
p, q >= 0 NoNegatividad

Información

Pasteles Harina Azúcar Mantequilla Beneficio/Docena

P 3 1 1 20

Q 6 1 30

Disponibles 150 22 275

 Ejercicio #2
En la elaboración de un producto A se necesita una sustancia B. La cantidad de A
obtenida es menor o igual que el doble de B utilizada, y la diferencia entre las
cantidades del producto B y A no supera los 2g mientras que la suma no debe
sobrepasar los 5g. Además, se utiliza por lo menos 1g de B y se requiere 1 g de A.
La sustancia A se vende a 5 millones de u.m y la B cuesta 4 millones de u.m el gramo.
Calcular la cantidad de sustancia B necesaria para que el beneficio sea máximo.
Plantear y resolver el anterior problema como un modelo de programación lineal.

Solución:

TITLE Producción_ AB
DATA
VARIABLES
a; ! Cantidad a fabricar del producto del A
b; ! Cantidad de la sustancia B requerida para fabricar A
MODEL
MAX Profit: 5a - 4b

SUBJECT TO
a <= 2b; a -2b=0
b-a<=2;
a+b <=5;

a>=1;
b>=1;

a,b>=0 ! Restricción redundante (no negatividad)

END
 Ejercicio #3

El problema de mezcla de productos

de Blubbermaid, Inc.

BlubberMaid, Inc, fabrica tres productos de caucho: Airtex (material esponjoso),

Extendex (material elástico) y Resistex (material rígido). Los tres productos requieren
los mismos tres polímeros químicos y una base. La cantidad de cada ingrediente
usada por libra del producto final se muestra en la tabla 3.1.

INGREDIENTE (oz/lb de producto)

POLIMERO POLIMERO POLIMERO

PRODUCTO BASE
A B C

Airtex 4 2 4 6

Extandex 3 2 2 9

Resistex 6 3 5 2

BlubberMaid, Inc, tiene el compromiso de producir al menos 1000 libras de Airtex, 500
libras de Extendex y 400 libras de Resistex para la próxima semana, pero la gerencia
de la compañía sabe que puede vender más de cada uno de los tres productos. Los
inventarios actuales de los ingredientes son 500 libras del polímero A, 425 libras del
polímero B, 650 libras del polímero C y 1100 libras de base. Cada libra de Airtex
produce a la compañía una ganancia de $7, cada libra de Extendex una ganancia de
$7 y cada libra de Resistex una ganancia de $6. Como gerente del departamento de
producción, usted necesita determinar un plan de producción óptimo para esta
semana.
Solución:

TITLE BlubberMaid

VARIABLES A: Cantidad a fabricar del producto Airtex (libras)

E: Cantidad a fabricar del producto Extendex (libras)

R: Cantidad a fabricar del producto Resistex (libras)

FUNCION OBJETIVO (FO)

Maximizar 7 A + 7 E + 6 R

SUBJECT TO
Cantidad del polímero A empleada en Airtex = 4(100) = 400
Cantidad del polímero A empleada en Extendex = 3(300) = 900
Cantidad del polímero A empleada en Resistex = 6(200) = 1200

4 A + 3 E + 6 R ≤ 500

4 A + 3 E + 6 R ≤ 8000 (polímero A)

2 A + 2 E + 3 R ≤ 6800 (polímero B)

4 A + 2 E + 5 R ≤ 10400 (polímero C)

6 A + 9 E + 2 R ≤ 17600 (base)

A ≥ 1000 (Airtex)

E ≥ 500 (Extendex)

R ≥ 400 (Resistex)

A, E, R ≥ 0
 Ejercicio #4

Case Chemical produce dos solventes, CS-01 y CS-02 en su planta de Cleveland. La

planta opera 40 horas a la semana y emplea a cinco trabajadores de tiempo completo
y a dos de tiempo parcial, que trabajan 15 horas a la semana para operar las 7
máquinas que mezclan ciertos químicos para producir cada solvente. Esta fuerza de
trabajo proporciona hasta 230 horas de trabajo disponible en el departamento de
mezclado.

Los productos una vez mezclados para son refinados en el departamento de

purificación, que actualmente tienen siete purificadores y emplea a seis trabajadores
de tiempo completo y a uno de tiempo parcial, que trabaja 10 horas a la semana.

Este trabajo proporciona hasta 250 horas de trabajo disponible en el departamento

de purificación. Las horas requeridas en los departamentos de mezclado y purificación
para producir mil galones de cada uno de los solventes se enumeran en la tabla 4.1.

REQUERIMIENTOS DE MEZCLADO Y PURIFICACIÓN ( hr/100 gal)

Cs-01 Cs-02

Mezclado 2 1

Purificación 1 2

Case Chemical tiene una provisión casi ilimitada de la materia prima que necesita
para producir los dos solventes. Puede vender cualquier cantidad de Cs-01, pero la
demanda del producto más especializada, CS-02 está limitada a lo mas a 120000
galones por semana.

El departamento de contabilidad estima un margen de ganancia de $0.30 por galón

de CS-01 y $0.50 por galón de CS-02. Como todos los empleados son asalariados y
por tanto, se les paga la misma cantidad sin importar cuántas horas trabajen, estos
salarios y los costos de las máquinas se consideran fijos y no se incluyen en el cálculo
del margen de ganancia. Como Gerente de Planeación de Producción, usted desea
determinar el plan de fabricación semanal óptimo para Case Chemicals.
Solución:

TITLE Case_Chemical

VARIABLES
X; !Cantidad a producir de CS01 (miles galones x semana)

Y; !Cantidad a producir de CS02 ( miles galones x semana)

MODEL
MAX 300 X+500 Y

SUBJECT TO

Y <= 120: !Limite de demanda del Cs02

2x +Y <= 230 !Mezclado

x +2Y <= 250 !Purificado

END

A 300(0) +500 (120)=60000

B 300(10) +500 (120)=63000

C 300(70) +500 (90)=66000

D 300(115) +500 (0)=34500

X + 2Y <= 250: Y<=120 2X+Y <= 230;

70 + 2(90) <= 250; 90 <= 120 2(70) +90 <=230

250 <=250; 230 <=230

Gráfica:

Un problema de minimización
Dorian Auto; fabrica y vende autos y furgonetas. La empresa quiere emprender una
campaña publicitaria en TV y tiene que decidir comprar los tiempos de anuncios en
dos tipos de programas: del corazón y fútbol.

• Cada anuncio del programa del corazón es visto por 6 millones de mujeres y 2
millones de hombres.
• Cada partido de fútbol es visto por 3 millones de mujeres y 8 millones de
hombres.
• Un anuncio en el programa de corazón cuesta U$50.000 y un anuncio del fútbol
cuesta U$100.000.
• Dorian Auto quisiera que los anuncios sean vistos por lo menos 30 millones de
mujeres y 24 millones de hombres.

Dorian Auto quiere saber cuántos anuncios debe contratar en cada tipo de programa
para que el coste de la campaña publicitaria sea mínimo.
 TITLE Dorian_Auto

VARIABLES DE DECISION

X; !Cantidad de anuncios en el programa corazón

Y; !Cantidad de anuncios en el programa fútbol

FUNCIÓN OBJETIVO

MIN 50 000 X+100 000Y

RESTRICCIÓN

2X + 8Y <= 24 !Hombres

6x +3Y <= 30 !Mujeres

X, Y >=0;

END

GRAFICA:

CONCLUSIÓN:

Contratar 4 anuncios en el programa corazón y 2 anuncios en el programa de futbol con un costo

total de 400 000
Ejemplo del Case chemical en el software MPL
Ejemplo del ejercicio Dorian Auto en el software MPL
 R1/EP
[0 6 0 1 0 -2 12]
[6 6 6 6 6 6]
[0 1 0 1/6 2]
0

VARIABLES BASICAS Z X1 X2 S1 S2 S3 SOLUCIÓN

Función Objetivo Z 1 -6 0 0 0 10 120

Restriccion 1 S1 1 0 1/6 0 -1/3 2 12

Restriccion 2 S2 0 1 0 0 1 0 8
Restriccion 3 S3 0 0 1 0 0 1 12

R1/ EP [0 6 0 1 0 -2 12]
[6 6 6 6 6 6]

[0 1 0 1/6 0 2]

FO + 8R1

[1 -6 0 0 0 10 120]
6[0 1 0 1/6 0

R2 +1R1 [1 0 0 1 0

[1 1 0 0 1 0 8]
-1[0 1 1 1/6 0 -1/3 2]
[0 0 0 -1/6 1 1/3 6]
 Z=132 Z= 8x1 +10x2= 8(2)+10(12)=132
X1= 2 8x1+2x2<=36 8(2)+2(12)<=38
X2=12 X1<= 8; 2<=8;
X2<= 12; 12<=12;

Método Simplex: Minimización

MIN Z = 500X1, + 600X2

S.A. 10X1 ≥ 100

1000X1 + 200X2 ≥ 800

250X1 + 300X2 ≤ 1500 X1, X2 ≥ 0

Resolución:
Reescribir las desigualdades a igualdades:

Z – 500X1 – 600X2 = 0

10X1 – S1 = 100 *

100X1 + 200X2 – S2 = 800 *

250X1 + 300X2 + S3 = 1500

Una vez formado las ecuaciones se convierte las variables S a positivas

Z – 500X1 – 600X2 = 0
 -100X1 + S1 = -100

-100X1 – 200X2 + S2 = -800

250X1 + 300X2 + S3 = 15000

Resultado:

Z = 26000

X1 = 10

X2 = 35
 Ejercicio de Case Chemical aplicando el Método Solver (excel)

Case Chemical produce dos solventes, CS-01 y CS-02 en su planta de Cleveland. La

planta opera 40 horas a la semana y emplea a cinco trabajadores de tiempo completo
y a dos de tiempo parcial, que trabajan 15 horas a la semana para operar las 7
máquinas que mezclan ciertos químicos para producir cada solvente. Esta fuerza de
trabajo proporciona hasta 230 horas de trabajo disponible en el departamento de
mezclado.

Los productos una vez mezclados para son refinados en el departamento de

purificación, que actualmente tienen siete purificadores y emplea a seis trabajadores
de tiempo completo y a uno de tiempo parcial, que trabaja 10 horas a la semana.

Este trabajo proporciona hasta 250 horas de trabajo disponible en el departamento

de purificación. Las horas requeridas en los departamentos de mezclado y purificación
para producir mil galones de cada uno de los solventes se enumeran en la tabla 4.1.

Requerimientos de mezclado y purificación

(hr/100 gal)

Cs-01 Cs-02

Mezclado 2 1

Purificación 1 2

Case Chemical tiene una provisión casi ilimitada de la materia prima que necesita
para producir los dos solventes. Puede vender cualquier cantidad de Cs-01, pero la
demanda del producto más especializada, CS-02 está limitada a lo mas a 120000
galones por semana.

El departamento de contabilidad estima un margen de ganancia de $0.30 por galón

de CS-01 y $0.50 por galón de CS-02. Como todos los empleados son asalariados y
por tanto, se les paga la misma cantidad sin importar cuántas horas trabajen, estos
salarios y los costos de las máquinas se consideran fijos y no se incluyen en el cálculo
del margen de ganancia. Como Gerente de Planeación de Producción, usted desea
determinar el plan de fabricación semanal óptimo para Case Chemicals.
 Modelado matemático MPL

Una empresa fabrica 4 productos. Estos productos tienen que pasar por los procesos
de lavado, pintura, inspección y ensamble. Las tasas de producción en unidades por
hora para cada uno de los productos en cada departamento se muestran en la Tabla
1.

Como estrategia de operación de la empresa programa actividades de mantenimiento

preventivo, capacitación y mejora continua. Por ello, no siempre se tiene la misma
disponibilidad de tiempo en cada departamento. La Tabla 2 muestra el tiempo
disponible en horas por departamento para las siguientes tres semanas. Las
demandas máximas esperadas para las siguientes tres semanas para cada producto,
así como la utilidad generada por cada uno de ellos se muestren en la Tabla 3. Si una
unidad de producto se fabrica por arriba de la demanda esta puede ser inventariada
para satisfacer demanda futura. Sin embargo, el costo de inventario por semana por
unidad es de $2, $1.5, $4 y $1.2 para cada producto respectivamente. Al inicio de la
semana actual se tienen inventarios de 40 unidades para el producto 1, 15 unidades
del producto 2, 10 unidades del producto 3 y 30 unidades del producto 4. Como
estrategia de manejo de inventario, se desea que nunca se tengan más de 150
productos en almacenamiento por semana. Por otro lado, el gerente de ventas ha
solicitado que al final de la semana 3 se tengan 20 unidades de inventario de cada
tipo.
Como encargado de la producción, se te pide:

a) Generar un modelo de programación lineal para determinar la cantidad de

productos de cada tipo para fabricarlos en cada una de las semanas. Considere
que puede obtener valores fraccionarios en su respuesta.

b) Si requiere de obtener valores enteros como respuesta, ¿tendría un resultado

diferente al obtenido del inciso anterior. Comente a qué atribuye su respuesta
comparando ambas respuestas en caso de ser diferentes.

Modelo matemático

TITLE Company_4

VARIABLES

X; !Cantidad a producir de cada producto en cada departamento

I; !Cantidad a inventariar de cada producto en cada semana
V; !cantidad a vender de cada producto en cada semana

X11;
X12;
X13;
X14;
X21;
X22;
X23;
X24;
X31;
X32;
X33;
X34;
X41;
X42;
X43;
X44;
I10;
I11;
I12;
I13;
I20;
I21;
I22;
I23;
I30;
I31;
I32;
I33;
I40;
I41;
I42;
I43;
V11;
V12;
V13;
V21;
V22;
V23;
V31;
V32;
V33;
V41;
V42;
V43;

Max
6V11+6V12+6V13+4V21+4V22+4V23+8V31+8V32+8V33+5V41+5V42+5V43-
2I11-2I12-2I13-1.5I21-1.5I22-1.5I23-4I31-4I32-4I33-1.2I41-1.2I42-1.2I43

SUBJECT TO
! Demanda

V11<=150;
V12<=120;
V13<=100;
V21<=250;
V22<=300;
V23<=200;
V31<=180;
V32<=140;
V33<=160;
V41<=160;
V42<=220;
V43<=180;

! Inventario

I13 = 20;
I23 = 20;
I33 = 20;
I43 = 20;
I11+I21+I31+I41<=150;
 I12+I22+I32+I42<=150;
I13+I23+I33+I43<=150;
I10=40;
I20=15;
I30=10;
I40=30;

! Producción

x11+1.5x21+3x31+0.5x41<=2280;
x12+1.5x22+3x32+0.5x42<=2000;
x13+1.5x23+3x33+0.5x43<=2160;
1.5x11+1.2x21+0.5x31+4x41<=1920;
1.5x12+1.2x22+0.5x32+4x42<=2040;
1.5x13+1.2x23+0.5x32+4x43<=2280;
0.5x11+2x21+x31+1.5x41<=2100;
0.5x12+2x22+x32+1.5x42<=2280;
0.5x13+2.23+x33+1.5x43<=2160;
4x11+x21+1.2x31+x41<=2340;
4x12+x22+1.2x32+x42<=2280;
4x13+x23+1.2x33+x43<=2160;

! Balance inventario
I11=I10+X11-V11;
I21=I20+X21-V21;
I31=I30+X31-V31;
I41=I40+X41-V41;
I12=I11+X12-V12;
I22=I21+X22-V22;
I32=I31+X32-V32;
I42=I41+X42-V42;
I13=I12+X13-V13;
I23=I22+X23-V23;
 I33=I32+X33-V33;
I43=I42+X43-V43;

END

Resultados del MPL

 2 do

Parcial

Contenido

Terminología de redes

Teoría de grafos

Algoritmos y métodos

Problemas del árbol de expansión mínima

Problemas de redes de distribución

 Terminología de Redes
Grafo: Una gráfica es una serie de puntos llamados nodos que van unidos por
una red.

Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales.
Por ejemplo, una gráfica cuyo flujo en sus ramales sea la electricidad es una
red eléctrica. En las redes se usa una simbología especifica para denotar su
tamaño y elementos que la constituyen, dicha notación es la (N, A) donde el
número de nodos que contiene la red y A representa el número de arcos o
ramales.

Problemas de redes

➢ Problemas de la ruta más corta.

➢ Problemas del árbol de expansión mínima.
➢ Problemas del flujo máximo.
➢ Problemas del costo mínimo.
 Algoritmo de Dijkstra
La idea subyacente en este algoritmo consiste en ir explorando todos los
caminos más cortos que parten del vértice origen y que se llevan a todos los
demás vértices; cuando se obtiene el camino más corto desde el vértice origen
hasta el resto de los vértices que componen el grafo; el algoritmo se detiene. Se
trata de una especialización de la búsqueda de costos uniforme y, como tal,
no funciona en grafos con aristas de coste negativo (al elegir siempre el nodo
con distancia menor, pueden quedar excluidos de la búsqueda nodos que en
próximas iteraciones bajarían el costo general del camino al pasar por una arista
con costo negativo).

Descripción detallada:

• Sea G= (V, A) un grafo dirigido y etiquetado.

• Sean los vértices a ꞓ V y z ꞓ V; a es el vértice de origen y z el vértice de
destino.
• Sean un conjunto C V, que contiene los vértices de V cuyo camino más
ꓵ

corto desde a todavía no se conoce

• Sea un vector D, con tantas dimensiones como elementos tiene V, y que
“guarda” las distancias entre a y cada uno de los vértices de V.
• Sea, finalmente, otro vector, P, con las mismas dimensiones que D, y que
conserva la información sobre que vértice precede a cada uno de los
vértices en el camino.
 Ejemplo:

[E, II]
[F, 10]
[D, 15]

𝑗:𝑛
Min {𝑁𝑖−1,𝑗; ∑𝑖∗𝐼 𝑁𝑖𝑗 } Nodo anterior, sumatoria acumulada

Min {D, A, C, F, T}
Min {10}
[D, I3]
[F, 10]
[E, 11]

Min {D, A, C, F, T}
Min {10}

[D, I3]
[F, 14]
[E, 11]
R1= Min {D, A, C, F, T} = 11
R2= Min {D, B, E, T} = 11
 Algoritmo de Floyd Warshall
• El algoritmo de Floy-Warshall, descrito en 1959 por Bernard Roy, es un
algoritmo de análisis sobre grafos para encontrar el camino mínimo en
grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos
los pares de vértices en una única ejecución. El algoritmo de Floy-Warshall
es un ejemplo de programación dinámica.
• El algoritmo de Floyd es muy similar, pero trabaja con grafos ponderados. Es
decir, el valor de la “fecha” que representamos en la matriz puede ser
cualquier entero o infinito. Infinito marca que no existe unión entre los nodos.
Esta vez, el resultado será una matriz donde estarán representadas las
distancias mínimas entre nodos, seleccionando los caminos más
convenientes según su ponderación (“peso”). Por ejemplo, si de “A” a “B” hay
36 (Km), pero de “A” a “C” hay 2 (Km) y de “C” a “B” hay 10 (Km), el algoritmo
nos devolverá finalmente que de “A” a “B” hay 12 (Km).

Ejemplo:

MATRIZ DE DISTANCIA
A B C D E
A 0 4 8 ꝏ ꝏ
B 4 0 1 2 ꝏ
C 8 ꝏ 0 4 2
D ꝏ 2 4 0 7
E ꝏ ꝏ 2 7 0

MATRIZ DE RECORRIDO
A B C D E
A B C D E
B A C D E
C A B D E
D A B C E
E A B C D
 MATRIZ DE DISTANCIA
A B C D E
A 0 4 8 ꝏ ꝏ
B 4 0 1 2 ꝏ
C 8 ꝏ 0 4 2
D ꝏ 2 4 0 7
E ꝏ ꝏ 2 7 0
MATRIZ DE RECORRIDO
A B C D E
A B C D E
B A C D E
C A B D E
D A B C E
E A B C D

MATRIZ DE DISTANCIA MATRIZ DE RECORRIDO

A B C D E A B C D E

A 0 4 5 6 7 A B B B C

B 4 0 1 2 3 B A C D C

C 8 6 0 4 2 C A D D E

D 6 2 3 0 5 D B B B C

E 10 8 2 6 0 E C D C C
 Teoría de Grafos
Optimización de redes

Terminología de redes:
• Gráfica: Es una serie de puntos llamados nodos que van unidos por unas
líneas llamadas ramales o arcos
• Red: Es una gráfica que presenta algún tipo de flujo en sus ramales. Por
ejemplo, una gráfica cuyo flujo en sus ramales sea la electricidad es una
red eléctrica.
• Ciclo: Un ciclo corresponde a la cadena que une a un nodo consigo
mismo, en el siguiente ejemplo el ciclo este compuesto por la cadena:
[4-2, 2-5, 5-7, 7-4]

• Ramal orientado: Un ramal o arco orientado es aquel que tiene un

sentido determinado, es decir que posee un nodo fuente y un nodo
destino

• Grafica orientada: Es aquella en la cual todos sus ramales se

encuentran direccionados.
• Cadena: Corresponde a una serie de elementos ramales que van de un
nodo a otro. En el siguiente ejemplo se realiza una cadena que va desde
el nodo 1 hasta el 7 y se compone por los elementos [1-4, 4-7].
• Ruta: Corresponde a los nodos que constituyen una cadena, en el
siguiente ejemplo [1,4,7].

• Nodo fuente: Es aquel nodo en el cual todos sus ramales se encuentran

orientados hacia afuera.
• Nodo destino: Es aquel en el cual todos sus ramales se encuentran
orientados hacia él.

• Árbol: Un árbol es una gráfica en la cual no existen ciclos como el

siguiente ejemplo.
 • Árbol de expansión: Es aquel árbol que enlaza todos los nodos de la
red, de igual manera no permite la existencia de ciclos.

Problemas del árbol de expansión mínima

Características:
• Es apropiado para problemas en los cuales la redundancia es expansiva,
o el flujo a lo largo de los arcos se considera instantáneo
• El problema surge cuando los nodos de una red deben conectarse entre
ellos sin formar un ciclo
• La aplicación de estos problemas de optimización se ubica en las redes
de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea,
marítima, hidráulica o de gas, etc., donde los nodos representan puntos
de consumo eléctrico, teléfonos, aeropuertos, computadores y los arcos
podrían ser de alta tensión, cable de fibra óptica, rutas aéreas, agua, gas
etc.
• También es conocido como árbol generador mínimo, es una red conexa y
ponderada que se refiere a utilizar los arcos de la red para llegar a todos
los nodos de esta, de manera tal que se minimiza la longitud total.

Para la solución se presentan los algoritmos de PRIM Y KRUSKAL:

• Método Prim:
o Inicializar un árbol con un único vértice, elegido arbitrariamente del
grafo
o Aumentar el árbol, por un lado. Llamamos lado a la unión entre dos
vértices: de las posibles uniones que pueden conectar el árbol a los
vértices que no están aún en el árbol, encontrar el lado de menor
distancia y unirlo al árbol
o Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)
 Ejemplo:

GRAFO NO DIRECCIONADO

Min {g-f; y-b; b-d; h-e; h-c; c-d}

Min {13}

Min {g, f. h. e. c, d; a, b}
 Método Kruskal
El algoritmo de kruskal es un ejemplo de algoritmo voraz.
Características:
1. Se |crea un bosque B (conjunto de árboles), donde cada vértice del grafo es
un árbol separado
2. Se crea un conjunto C que contenga a todas las aristas del grafo mientras C
es no vacío
➢ Eliminar una arista de peso mínimo de C
➢ Si esa arista conecta dos árboles diferentes se añade al bosque,
combinando los dos árboles en un solo árbol.
➢ En caso contrario, se desecha la arista
3. Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un
árbol de expansión mínimo del grafo.
4. En un árbol de expansión mínimo se cumple:
➢ La cantidad de aristas del árbol es la cantidad de nodos menos 1.

Ejemplo:

Es lo mismo que el método Prim con la diferencia que en el método Kruskal

debe existir un ramal no direccionado.

Algoritmo de Ford - Fulkerson

• El algoritmo de Ford-Fulkerson propone buscar caminos en los que se
pueda aumentar el flujo, hasta que se alcance el flujo máximo. Es
aplicable a los flujos maximales. La idea es encontrar una ruta de
penetración con un flujo positivo neto que una los nodos origen y destino.
Su nomnre viene dado por sus creadores, Ford- Fulkerson.
• Una red de flujo es un grafo dirigido G= (V, E) en donde cada arco (u, v)
ꞓE tiene una capacidad no negativa c(u,v) >0.
• Se distinguen dos vértices: la fuente s y el resumidero t.
• Se asume que cada vértice se encuentra en alguna ruta de s a t.
• Un flujo en G es una función f: VxV R tal que
o Restricción de capacidad: Ɐ u, v en V, f(u,v)
o Simetría: f(v, u)
o Conservación: Ɐ u en V-{s, t} Ʃv en Vf(u, v) = 0
• El valor del flujo es |f| = Ʃv en Vf(u, v) = 0
• El problema de flujo máximo trata de maximizar este flujo.
• Este método depende de tres ideas importantes: Camino de aumento y
red residual.
• Este método es iterativo. Se comienza con f(u, v) = 0 para cada par de
nodos.
• En cada iteración se incrementa el valor del flujo buscando un camino de
aumento, el cual es un camino desde la fuente al resumidero que puede
conducir más flujo.
Ford-Kulkerson method (G, s, t)
Inicializar flujo f a o;
While (exista un camino de aumento p) do
Aumentar el flujo f a lo largo de p;
Return f;
• Se repite el proceso previo hasta no encontrar un camino de aumento.
• Capacidad residual: es la capacidad adicional de flujo que un arco puede
llevar: cf (u, v) = c(u, v) – f (u,v)
• Dado una red de flujo G = (V, E) y un flujo f, la red residual: inducida por
f es Gf= (V, Ef), con Ef = {(u, v) ꞓ VxV: cf (u, v) >o}
Metodología. Pasos a seguir
1. Preparar el grafo. Se van a poner flechas en el sentido del flujo para una
mejor visualización, y se pone a cero capacidades usadas de todos los
arcos.
2. Obtener una trayectoria de aumento, siguiendo el criterio de ir siempre por
el camino que proporcione una mayor capacidad residual en cada nodo.
3. Determinar el flujo de la trayectoria de aumento. Será el mínimo de las
capacidades residuales de los arcos que la forman.
4. Actualizar el grafo. Se modifican las capacidades residuales y usadas de
cada arco, así como el flujo total.
5. Volver al punto 2 hasta que no existan más trayectorias de aumento.

Ejercicio\

Max {Flujo i -> j}

Max {I-A, A-C, C-E*EI, F}
Max {1, 2, 3, 2}
Mim {Max {1, 2, 2, 3, 2}
Max {Flujo i -> j}
Max {I-A, A-C, C-E*EI, F}
Max {1, 2, 3, 2}
Mim {Max {1, 2, 2, 3, 2}

Max {Flujo i -> j}

Max {I-A, A-C, C-E r, F-T}
Max {3, 4, 2, 4}
Mim {Max {3, 4, 2, 4}

Max {Flujo i -> j}

Max {I-D, B-F, E-T}
Max {5, 4, 6}
Mim {Max {5, 4, 6}
 Max {Flujo i -> j}
Max {I-A, A-D, D-r}
Max {8, 5, 6}
Mim {Max {8, 5, 6}

Max {Flujo i -> j}

Max {I-D, B-F, E-T}
Max {5, 4, 6}
Mim {Max {5, 4, 6}

Min {D-A-D-T} = 5
Min {D-B-E-T} = 4
Min {D-A-C-F-I} = 2
Min {D-A-C-E-F-I} = 1
Total= 12
 Problemas de redes de distribución:

Transporte, transbordo y problemas de

asignación.

1. Redes de distribución
Las redes de transporte de mercancías surgen por la necesidad de
conectar y transportar los bienes de consumo desde su punto de
producción hasta el mercado.

En la fase de distribución, la mercancía puede ser transportada con una

gran variedad de modos de transporte y puede realizar varias paradas en
almacenes nodos de cambio hasta llegar a su destino final.

La configuración de la red de transporte condiciona los costes de

distribución de la mercancía, así como la planificación y la organización
temporal de la cadena de suministro de los productos al mercado.

2. Modelos de transporte
Consiste en determinar qué cantidad de un determinado articulo se debe
enviar desde m orígenes, hasta n destinos.

Se sabe que cada origen tiene una disponibilidad u oferta y que cada
destino tiene una demanda.

El objetivo final es minimizar los costos totales de transporte generados

por la cantidad enviada de cada origen a casa destino.
 • Ejercicio 1:
Cada mes se imprimen 5000 copias de “News Magazine” en cada una de dos
imprentan: una ubicada en Quito y otra en Guayaquil. Ahí las revistas son enviadas a
tres distribuidores regionales:

1.- Regional Manabí que ha solicitado 4000 copias

2.- Regional centro Sierra que ha solicitado 2000 copias
3.- Regional norte que ha solicitado 2500 copias
El costo de envió por revistas de cada imprenta a cada centro de distribución
se establece en la tabla.

REGIONALES
DISTRIBUIDORES
IMPRENTAS REGIONAL MANABÍ REGIONAL REGIONAL
CENTRO SIERRA NORTE
QUITO 0.07 0.05 0.10
GUAYAQUIL 0.03 0.11 0.04

Oferta=Demanda
10.000=8500+1500
 D=0
10.000=10.000

• Resultado Esquina Noroeste

• Resultado con Coste mínimo:
• Resultado Vogel:
 • Ejercicio 2:
Distribuciones de combustible S.A tiene una refinería localizada en Napo, con
una capacidad de producción de 200,000 barriles a la semana, y una en
Sucumbíos con una capacidad de producción de 300,000 barriles a la semana.
Esta gasolina es enviada a 4 tanques de almacenamiento. Para la siguiente
semana, el T1 necesita 200,000 barriles, el T2 requiere 100,000 barriles, el T3
400,000 barriles, y el T4 necesita 300,000 barriles. El costo de envió esta en la
siguiente tabla:

TANQUES ALMACENAMIENTO
DE
REFINERIA T1 T2 T3 T4
NAPO 0.10 0.05 0.07 0,09
SUCUMBÍOS 0.05 0.11 0.08 0,07

Ofertas Demanda Costos asociados

Oferta=demanda
500 000=1000 000
500 000+500 000=1000 000

Algortimo del
escalón

Solución inicial: Evaluación y mejora:

-Esquina Noroeste Algortimo de salto de Solución optima
-Coste mínimo piedra
-Vogel
• Resultado Esquina Noroeste
• Resultado con Coste mínimo:
 • Resultado Voguel:

Costo= 3400000

• Ejercicio 3
CCC posee tres plantas de ensamblado de microcomputadores. La
ubicada en San francisco tiene una capacidad de producción
mensual de 1700 unidades, la ubicada en Los Ángeles tiene una
capacidad de 2000 unidades mensuales, y la ubicada en Phoenix
tiene una capacidad 1700 unidades mensuales. Los productos
vendidos a través de tiendas menudeo. La demanda pronosticada
para el siguiente mes es de: Tienda en San Diego de 1700
unidades, en Barstow necesita 1000 unidades, la de Tucson 1500
unidades y la ubicada en Dallas 1200 unidades. El costo de envió
se observa en la siguiente tabla. Como gerente de producción
requiere hacer la distribución de los productos al menos costo
posible.
ALMACENAMIENTO
TANQUES
DE
PLANTAS SAN DIEGO BARSTOW TUCSON DALLAS
SAN 5 3 2 6
FRANCISCO
LOS 4 7 8 10
ANGELES
PHOENIX 6 5 3 8
 5400 oferta= Demanda 5400

Matriz de transporte:

DEMANDA
OFERTA

X= Variables (lo que se buscara)

ESQUINA NOROESTE:
Es un algoritmo heurístico capaz de solucionar problemas de transporte o de
distribución mediante la consecución de una solución básica inicial que satisfaga todas
las restricciones existentes sin que esto implique que se alcance el costo optimo total.
• Resultado con Coste mínimo:
• Resultado Voguel:
 Problemas de redes de distribución:

Transporte, transbordo y problemas de

asignación

Modelos de Transporte

1) Solución inicial
✓ Esquina Noroeste
✓ Coste mínimo
✓ Vogel

Algoritmo del escalón 3) Evaluación y mejora

Algoritmo de salto de piedra

2) Solución óptima

Ejercicio:

Costo total = 34600

1.- Si es degenerada mi matriz de transporte
F + c – 1 = casillas designadas
3+4–1=5
6= 5 La matriz es degenerada
2.- Asignación de variables ui + vj
Solo trabajo con casillas asignadas
Para mis variables básicas:
Ui + vj = cij
 ui + vj = cij ui + vj = cij ui + vj = cij ui + vj = cij ui + vj = cij

u1 + v1 = c11 u1 + v2 = c12 u2 + v2 = c22 u2 + v3 = c23 u3 + v3 = c33

0 + v1 = 5 0 + v2 = 3 u2 + 3 = 8 5 + v3 = 8 u3 + 2 = 8

V1 = 5 V2 = 3 V2 = 5 V3 = 2 u3 = 1

3.- Asignar costos asociados a mis casillas no asignadas

Cij = Cij – (ui + vj) Cij = v1 + vj - Cj)
Elegir el valos más negativo para asignación nueva
Si todos son positivos, el ejercicio ha encontrado su óptimo factible

Cij = Cij – (ui + vj)

C13 = C13 – (u1 + v3)
C13 = 2 – (0 + 2)
C13 = 0
C14 = C14 – (u1 + v4)
Cij = Cij – (ui + vj)
C14 = 6– (7 + 10)
C14 = - 1

Cij = Cij – (ui + vj)

 Cij = Cij – (ui + vj)

Cij = Cij – (ui + vj)

2 – (0 + 8)
2 - 8 = -1
6 – (13 - 0)
6 – 13 = -7
Costo total = 28600

Cij = Cij – (ui + vj)

5 – (3 - 5)
5– (-2)
5+2=7

Costo total = 28600

Costo Total= 23700

 Cij = Cij – (ui + vj)

Costo total= 23100

Costo total = + 23100

Penalización Penalización Penalización
1 1 4

3 1 3

2 2 5

Penalización 1 2 1 2
Penalización
Penalización 2 1 2
1 2
Ejercicio 1

CCC posee tres plantas de ensamble de microcomputadoras. La ubicada en San

Francisco tiene una capacidad de producción mensual de 1700 unidades, la
ubicada en los Ángeles una capacidad de 2000 unidades mensuales. Los
productos son vendidos a través de tiendas de menudeo. La demanda
pronosticada para el siguiente mes es de: tienda en San Diego de 1700, en
Barstow necesita 1000 unidades, la de Tucson 1500 unidades y la ubicada en
Dallas 1200 unidades. El costo de envió se observa en la siguiente tabla. Como
gerente de producción requiere hacer la distribución de los productos al menor
costo posible.
MPL
 SOLVER

DESTINOS
MATRIZ DE COSTOS
SD BA TU DA
SF 5,00 € 3,00 € 2,00 € 6,00 €
ORIGEN LA 4,00 € 8,00 € 7,00 € 10,00 €
PH 6,00 € 5,00 € 3,00 € 8,00 €

DESTINOS
MATRIZ DE DESTINO
SD BA TU DA SUMA OFERTA
SF 0 1000 0 700 1700 = 1700
ORIGEN LA 1700 0 0 300 2000 = 2000
PH 0 0 1500 200 1700 = 1700
SUMA 1700 1000 1500 1200
= = = =
DEMANDA 1700 1000 1500 1200

COSTO TOTAL = 23.100,00 €

Ejercicio 2
MPL
 SOLVER

14 15 24 25 35 46 47 56 57 68 69 670 79 710 711

2 4 3 4 5 8 6 7 4 7 6 8 7 5 6

14 15 24 25 35 46 47 56 57 68 69 670 79 710 711

100 0 200 0 80 200 100 0 80 120 80 0 0 70 110

1 1 1 100 = 100
2 1 1 200 = 200
3 1 80 = 150
4 1 1 -1 -1 0 = 0
5 1 1 1 -1 -1 0 = 0
6 1 1 -1 -1 -1 0 = 0
7 1 1 -1 -1 -1 0 = 0
8 1 120 = 120
9 1 1 80 = 80
10 1 1 70 = 70
11 1 110 = 110

costos $6.050,00
Ejercicio 3
Método Húngaro- Minización

METODO HUNGARO- MINIMIZACION

M1 M2 M3 M4 F1 F2
T1 8 5 8 5 0 0
T2 7 4 2 6 0 0
T3 5 4 7 5 0 0
T4 3 2 4 4 0 0
T5 4 5 4 4 0 0
T6 8 3 7 4 0 0

1) Balanceo
2) El menor costo asociado de asignación, restar al resto

M1 M2 M3 M4 F1 F2
T1 8 5 8 5 0 0
T2 7 4 2 6 0 0
T3 5 4 7 5 0 0
T4 3 2 4 4 0 0
T5 4 5 4 4 0 0
T6 8 3 7 4 0 0

M1 M2 M3 M4 F1 F2
T1 5 3 6 1 0 0
T2 4 2 0 2 0 0
T3 2 2 5 1 0 0
T4 0 0 2 0 0 0
T5 1 3 2 0 0 0
T6 5 1 5 0 0 0

3) Mínima cantidad de líneas voy a tachar la mayor cantidad de ceros

4) Números sin seleccionar Escoger el menor valor Resta
Números seleccionados simples Nada
Números seleccionados dobles Suma
 M1 M2 M3 M4 F1 F2
T1 5 3 6 1 0 0
T2 4 2 0 2 0 0
T3 2 2 5 1 0 0
T4 0 0 2 0 0 0
T5 1 3 2 0 0 0
T6 5 1 5 0 0 0

5) Resultados óptimos factibles

M1 M2 M3 M4 F1 F2
T1 4 2 5 1 0 0
T2 4 2 0 3 1 1
T3 1 1 4 1 0 0
T4 0 0 2 1 1 1
T5 0 2 1 0 0 0
T6 4 0 4 0 0 0

M1 M2 M3 M4 F1 F2
T1 4 2 5 1 0 0
T2 4 2 0 3 1 1
T3 1 1 4 1 0 0
T4 0 0 2 1 1 1
T5 0 2 1 0 0 0
T6 4 0 4 0 0 0

Costos
0
2
0
3
4
3
12
MPL
 SOLVER

M1 M2 M3 M4 F1 F2
T1 8 5 8 5 0 0
T2 7 4 2 6 0 0
T3 5 4 7 5 0 0
T4 3 2 4 4 0 0
T5 4 5 4 4 0 0
T6 8 3 7 4 0 0

M1 M2 M3 M4 F1 F2
T1 0 0 0 0 0 1 1 = 1
T2 0 0 1 0 0 0 1 = 1
T3 0 0 0 0 1 0 1 = 1
T4 1 0 0 0 0 0 1 = 1
T5 0 0 0 1 0 0 1 = 1
T6 0 1 0 0 0 0 1 = 1
1 1 1 1 1 1
= = = = = = COSTO $12,00
1 1 1 1 1 1
Ejercicio 4
 Metodo CPM- PERT
Tiempos estimados

• El tiempo total de finalización es de 55 semanas.

• Actividades con holguras son: G=1 B=13 C=5
• Ruta crítica: A-D-E-F-H
TIEMPOS DE CHOQUE

• El tiempo total de finalización es de 46 semanas.

• Actividades con holguras son: B=11 C=4 D=2 E=2
• Ruta crítica: A-G-F-H
 TAREA TIEMPO TIEMPO DE REDUCCION COSTO POR
NORMAL COSTO NORMAL CHOQUE COSTO DE CHOQUE MAXIMA AUMENTO EN DINERO SEMANA
A 30 5000 26 9000 4 4000 1000
B 6 6000 4 9000 2 3000 1500
C 4 10000 3 10500 1 500 500
D 5 5000 3 6500 2 1500 750
E 10 4500 7 6300 3 1800 600
F 8 20000 6 22500 2 2500 1250
G 14 10000 12 15000 2 5000 2500
H 2 25000 2 25000 0 0 0
$ 85.500,00 $ 103.800,00 $ 18.300,00
|

La reducción de 55 a 46 semanas me cuesta $ 18.300,00 lo cual representa el 21,4% de aumento. Al contrario si solo nos referimos
a la ruta crítica solo sería un aumento de $12.100,00 lo cual representa el 14,15%.
MPL