ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Sabemos que para que un ordenador pueda llevar adelante una tarea
cualquiera, se tiene que contar con un algoritmo que le indique, a través de un
programa, que es lo que debe hacer con la mayor precisión posible. Consecuencia
de lo anterior es la importancia del estudio de los algoritmos.
Concepto de Algoritmo
Un algoritmo es un conjunto ordenado y finito de pasos o instrucciones que
permite realizar una actividad mediante pasos sucesivos sin generar dudas a
quien deba realizar dicha actividad, conduciendo a la solución de un problema
determinado. De esta manera, dados un estado inicial y una entrada, siguiendo los
pasos sucesivos se llega a un estado final y se obtiene una solución. En la vida
cotidiana, frecuentemente se emplean algoritmos para resolver problemas.
Algoritmos especiales
Son diseñados para problemas de programación lineal, son problemas
enunciados con ecuaciones lineales y con una función objetivo, y una o más
funciones restricciones, para lograr la optimización de la función objetivo que se
analiza. Algunos de ellos son: Gran M, Flujo mínimo, Algoritmo Fraccional, Método
Dual Simplex, entre otros.
Aplicación
Son empleados principalmente en problemas de flujo de redes y problemas
de flujo de mercancías. Son muy usados en la microeconomía y la administración
de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo
los costos de un sistema de producción.
Introducción
¿Qué significa problema de transporte? Supongamos que un fabricante tiene tres
plantas que producen el mismo producto. Estas plantas a su vez mandan el
producto a dos depósitos. Cada planta puede mandar productos a todos los
depósitos, pero el costo de transporte varía con las diferentes combinaciones. El
INTRODUCCION
3.1 EL PROBLEMA DE TRANSPORTE
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
problema es determinar la cantidad que cada planta debe mandar a cada depósito
con el fin de minimizar el costo total de transporte.
La manera más fácil de reconocer un problema de transporte es por su
naturaleza o estructura
“de-hacia”: de un origen hacia un destino, de una fuente hacia un usuario, del
presente hacia el futuro, de aquí hacia allá, una relación de uno a otro . Al
enfrentar este tipo de problemas, la intuición dice que debe haber una manera de
obtener una solución. Se conocen las fuentes y los destinos, las capacidades y
demandas y los costos de cada trayectoria. Debe haber una combinación óptima
que minimice el costo (o maximice la ganancia). La dificultad está en el gran
número de combinaciones posibles , debido a eso el problema del transporte
recurre a buscar soluciones con la computara y software especializado..
El responsable de gestión del trasporte debe determinar una política
óptima: cómo hacer llegar los productos de sus diversos depósitos, plantas de
producción o bodegas a sus consumidores o clientes, con el objeto de satisfacer la
demanda a un costo mínimo de transporte o de envío.
Planteamiento del problema
El problema del transporte en general se especifica mediante la siguiente
información:
1. Un conjunto de m puntos de oferta desde los cuales se envían utilidades o
bienes.
2. Una lista de capacidades de suministro máximo de cada sitio de oferta si
para i = 1, 2,. . ., m.
3. Un conjunto de n puntos de demanda hacia los cuales se envía una utilidad
o bien.
4. Una lista de demandas de utilidades o bienes dj de cada punto de demanda
j las cuales deben satisfacerse mínimamente.
5. Una matriz de valores que indica el costo fijo en el que se incurre al enviar
una unidad producida en el punto de oferta i y enviada al punto de demanda
j, cij .
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Modelo de programación lineal del problema de transporte
Sea: X i j = Unidades enviadas del origen i ( i =1,2,...m), al destino j ( j = 1,2,...,n)
C i j = Costo unitario desde el nodo origen i hasta el nodo destino j.
= Oferta del origen i, ( i = 1, 2,...,m); b j = Demanda del destino j ( j = 1, 2,...,n)
El modelo de programación lineal aquí mostrado se presenta para un problema balanceado con las restricciones de oferta y demanda en igualdad. Para el caso
de un problema no balanceado (oferta y demanda en desigualdad) es necesario el
Equilibrio: = b j; además, debe cumplirse que toda X i j >= 0
Tabla del problema de transporte
D1 D2 ............... Dn ai
O1
c11 c12
...............c1n
a1
O2
c12 c22
...............c2n
a2
.........
.........
.........
...............
.........
.........
Om
cm1 cm2
...............
cmn
am
bj b1 b2 ................ bn
D E S T I N O S
O R
I G
E N
E S
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Determinación de la Solución Básica Factible
La utilización del método SIMPLEX no resulta eficiente para resolver el Problema
de Transporte, por lo cual se utilizan otros métodos como:
a) Método de la Esquina Nor-Oeste (N-O)
b) Método de la Matriz de Costo Mínimo
c) Método de Vógel
Método de la esquina noroeste
Características
Sencillo y fácil de hacer
No tiene en cuenta los costos para hacer las asignaciones
Generalmente nos deja lejos del óptimo
Algoritmo
1. Construya una tabla de ofertas (disponibilidades) y demandas (requerimientos).
2. Empiece por la esquina noroeste.
3. Asigne lo máximo posible (Lo menor entre la oferta y la demanda,
respectivamente)
4. Actualice la oferta y la demanda y rellene con ceros el resto de casillas (Filas ó
Columnas) en donde la oferta ó la demanda halla quedado satisfecha.
5. Muévase a la derecha o hacia abajo, según halla quedado disponibilidad para
asignar.
6. Repita los pasos del 3 al 5 sucesivamente hasta llegar a la esquina inferior
derecha en la que se elimina fila y columna al mismo tiempo.
Nota: No elimine fila y columna al mismo tiempo, a no ser que sea la última
casilla. El romper ésta regla ocasionará una solución en donde el número de
variables básicas es menor a m+n-1, produciendo una solución básica factible
degenerada.
Problema de ejemplo
Una compañía tiene 3 fábricas ubicadas en A, B y C, las cuales proveen a los
almacenes que están ubicados en D, E, F y G. La capacidad de producción de las
fábricas es de 70, 90 y 115 unidades mensuales respectivamente, mientras que
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
las capacidades de los almacenes son de 50, 60, 70 y 95 unidades
respectivamente. El costo de envió de una unidad desde cada una de las fábricas
a cada una de los almacenes se presenta en el siguiente cuadro (en pesos):
Se colocan los datos en forma tabular:
Por consiguiente la solución es:
D1 D2 D3 D4
O1 17 20 13 12
O2 15 21 26 25
O3 15 14 15 17
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Método del costo mínimo
Características:
Es más elaborado que el método de la esquina noroeste
Tiene en cuenta los costos para hacer las asignaciones
Generalmente nos deja alejados del óptimo
Algoritmo:
1. Construya una tabla de disponibilidades, requerimientos y costos
2. Empiece en la casilla que tenga el menor costo de toda la tabla, si hay empate, escoja arbitrariamente (Cualquiera de los empatados).
3. Asigne lo máximo posible entre la disponibilidad y el requerimiento (El menor de los dos).
4. Rellene con ceros (0) la fila o columna satisfecha y actualice la disponibilidad y el requerimiento, restándoles lo asignado.
Nota: Recuerde que no debe eliminar ó satisfacer fila y columna al mismo tiempo, caso en que la oferta sea igual a la demanda, en tal caso recuerde usar la ε (Épsilon).
5. Muévase a la casilla con el costo mínimo de la tabla resultante (Sin tener en
cuenta la fila o columna satisfecha). 6. Regrese a los puntos 3,4,5 sucesivamente, hasta que todas las casillas queden
asignadas.
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Problema ejemplo:
El hospital Saludmuch pertenece a la Compañía de Seguros Todosalud SA. Esta
sociedad tiene un Centro de Asistencia Primaria (CAP) en 5 ciudades de una
región (un CAP en cada ciudad). Para obtener un buen funcionamiento global del
servicio y poder planificar el número de visitas en función del personal previsto en
cada CAP y de su dimensión, Todosalud S.A. ha decidido organizar el servicio de
tal forma que todos sus asegurados tengan un CAP de referencia asignado, pero
que sea éste el más cercano posible a su lugar de residencia. En la región hay 5
ciudades y la compañía sabe cuántos asegurados tiene en cada uno de ellos. Los
CAP tienen una capacidad máxima de pacientes que pueden soportar. El objetivo
es asignar a los asegurados a los CAPs minimizando el coste de desplazamiento
o la distancia total.
Si no existiera el problema de capacidad de los CAPs, el modelo sería trivial, ya
que bastaría asignar cada ciudad al CAP más cercano, obteniéndose el coste de
transporte más barato. Al tener límites en la capacidad, puede ser que no todas
las ciudades tengan asignado el centro más cercano, ya que esto implicaría una
sobre utilización. Entonces, puede ser que alguna ciudad, o parte de ella tenga
asignada un CAP que no es el más cercano, en función de la disponibilidad o
holgura del sistema.
En su forma tabular quedaría de la siguiente manera:
CAP 1 CAP 2 CAP 3 CAP 4 CAP 5Número de
asegurados
Ciudad 1 2 5 4 8 6 500
Ciudad 2 5 6 3 8 7 700
Ciudad 3 6 2 8 10 5 1000
Ciudad 4 6 8 9 5 3 800
Ciudad 5 8 5 7 10 6 600
Capacidad
máxima de
atención
750 800 650 900 500
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Método de Vogel
Características
Es más elaborado que los anteriores, más técnico y dispendioso.
Tiene en cuenta los costos, las ofertas y las demandas para hacer las
asignaciones.
Generalmente nos deja cerca al óptimo.
Algoritmo
1. Construir una tabla de disponibilidades (ofertas), requerimientos (demanda) y
costos.
2. Calcular la diferencia entre el costo más pequeño y el segundo costo más
pequeño, para cada fila y para cada columna.
3. Escoger entre las filas y columnas, la que tenga la mayor diferencia (en caso de
empate, decida arbitrariamente).
4. Asigne lo máximo posible en la casilla con menor costo en la fila o columna
escogida en el punto 3.
5. asigne cero (0) a las otras casillas de la fila o columna donde la disponibilidad ó
el requerimiento quede satisfecho.
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
6. Repita los pasos del 2 al 5, sin tener en cuenta la(s) fila(s) y/o columna(s)
satisfechas, hasta que todas las casillas queden asignadas.
Nota: Recuerde que no debe satisfacer filas y columnas al mismo tiempo; caso en
que la disponibilidad sea igual al requerimiento; en tal caso use el ε (epsilon).
Problema ejemplo
Fíjese que la mayor diferencia la tiene la columna 4 con un valor de 19, escogido
entre 2,2,3,0,15,13,19 y 16.
El menor costo de la columna 4 es cero (0), se asigna lo máximo posible entre 50
y 40, que es 40, se satisface la columna y se actualiza la oferta y la demanda.
Ahora recalculamos las diferencias, sin tener en cuenta la columna 4, que está
satisfecha.
Una vez ejecutado todo el algoritmo hasta asignar todas las casillas, obtenemos la
siguiente asignación básica y factible inicial.
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Fíjese que el número de variables básicas es: m+n-1=8
Solución básica factible no degenerada:
X15=40 ; X21=30 ; X23=20 ; X25=10 ; X32=40 ; X33=30 ; X44=40 ; X45=10
Z = 16(40) + 15(30) + 13(20) + 16(10) + 15(40) + 18(30) + 0(40) + 0(10) = 2.650
El criterio de la optimalidad
Hemos conseguido tres (3) soluciones básicas factibles no degeneradas por
medio de tres métodos: El de la esquina noroeste, el del costo mínimo y el de
Vogel. Pero ninguna de ellas nos garantiza que la solución encontrada es la
óptima. Para saberlo, debemos estar seguros que ninguna de las variables no
básicas pueda entrar a la base haciendo que la función objetivo disminuya. Para
discernir un método que nos evalúe el efecto de introducir una unidad de cada
variable no básica, recurrimos al método MODI.
Método MODI o UV
Consideremos la solución inicial hallada por el método de la Esquina N.O.
Paso 2: Se dibuja la matriz Zij que contiene los costos de la variable solución.
ai
17 20 13 12
50 20
15 21 26 25
40 50
15 14 15 17
20 95
bj
Z = $ 5305
90
115
50 60 70 95
D2 D3 D4
70O1
O2
O3
D1
17 20
21 26
15 17
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Paso 3: Se construye un conjunto de números vj y ui tal que la suma iguale a los
valores de la matriz Zij del paso 2 y se completa las celdas vacías con la suma de
los ui y vj la matriz Zij que contiene los costos de la variable solución.
Se tiene las siguientes ecuaciones de las celdas básicas:
U1 + v1 = 17 u2 + v3 = 26
U1 + v2 = 20 u3 + v3 = 15
U2 + v2 = 21 u3 + v4 = 17
Haciendo v1 = 0 se encuentra que: u1 = 17 ; v2 = 3 ; u2 = 18
V3 = 8 ; u3 = 7 ; v4 = 10
Paso 4: Se calcula Cij - Zij
vj
ui 0 3 8 10
17 17 20 25 27
18 18 21 26 28
7 7 10 15 17
17 20 13 12
15 21 26 25
15 14 15 17
vj
ui 0 3 8 10
17 17 20 25 27
18 18 21 26 28
7 7 10 15 17
0 0 -12 -15
-3 0 0 -3
8 4 0 0
Cij - Zij
-
=
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Se selecciona la casilla (1,4) que tiene el costo de entrada más pequeño, por
consiguiente debe entrar a la base la variable X14
El costo de la nueva solución es: Z1 = 5305 + (20)(-15) = 3005
A continuación probamos si esta solución es o no la óptima
Se calcula Cij - Zij
ai
- +50 20
+ -40 50
+ -20 95
bj
O3 115
50 60 70 95
O1 70
O2 90
D1 D2 D3 D4 ai
50 20
60 30
40 75
bj
O3 115
50 60 70 95
O1 70
O2 90
D1 D2 D3 D4
17 20 13 12
15 21 26 25
15 14 15 17
vj
ui 0 -12 -7 -5
17 17 5 10 12
33 33 21 26 28
22 22 10 15 17
0 15 3 0
-18 0 0 -3
-7 4 0 0
Cij - Zij
-
=
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Se selecciona la casilla (2,1) que tiene el costo de entrada más pequeño, por
consiguiente debe entrar a la base la variable X21
El costo de la nueva solución es: Z2 = 5005 + (30)(-18) = 4465
A continuación probamos si esta solución es o no la óptima
Se calcula Cij - Zij
Se selecciona la casilla (3,2) que tiene el costo de entrada más pequeño, por
consiguiente debe entrar a la base la variable X32
ai
- +50 20
+ -60 30
+ -40 75
115
50 60 70 95
70
90
D1 D2 D3 D4 ai
20 50
30 60
70 45115
50 60 70 95
70
90
D1 D2 D3 D4
17 20 13 12
15 21 26 25
15 14 15 17
vj
ui 0 -6 -7 -5
17 17 23 10 12
15 15 21 8 10
22 22 28 15 17
0 -3 3 0
0 0 18 15
-7 -14 0 0
Cij - Zij
ai
- +50 20
+ -60 30
+ -40 75
bj
O3 115
50 60 70 95
O1 70
O2 90
D1 D2 D3 D4ai
70
50 40
20 70 25
bj
O3 115
50 60 70 95
O1 70
O2 90
D1 D2 D3 D4
-
=
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
El costo de la nueva solución es: Z2 = 4465+ (20)(-14) = 4185
A continuación probamos si esta solución es o no la óptima
Se calcula Cij - Zij
Esta es la solución óptima
El algoritmo de mejoramiento de la solución
Dado que los métodos estudiados no garantizan una solución óptima, es
necesario verificar que no exista una ruta no utilizada que lo sea. De ser este el
caso, se determina esta nueva solución.
Se estudiarán 2 métodos para el mejoramiento de una solución básica factible
inicial:
a) Método de la Distribución Modificada
b) Método del Paso Secuencial
MÉTODO DEL PASO SECUENCIAL
1) Localizar una celda no básica, que no tenga costo marginal, y determinar
un circuito con el mínimo número de celdas básicas siguiendo trayectorias
horizontales y verticales solamente.
17 20 13 12
15 21 26 25
15 14 15 17
vj
ui 0 6 7 9
3 3 9 10 12
15 15 21 22 24
8 8 14 15 17
14 11 3 0
0 0 4 1
7 0 0 0
Cij - Zij
-
=
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
2) Asignar intercalando signos positivos “+” y negativos “-” al circuito
determinado en el paso 1, comenzando con la asignación “+” a la celda no
básica.
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
3) Determinar el costo marginal del circuito localizado, que consiste en el
costo de ingresar una unidad a la celda no básica utilizando los signos del
paso 2:
4) Si existen celdas no básicas sin costo marginal regresar al paso1.
5) Si todas las celdas no básicas tienen costo marginal no negativo la solución
actual es óptima. FIN.
6) Localizar la celda que tenga el costo marginal más negativo. Asignar a esta
celda xP, donde xP es el mínimo valor de las celdas del circuito que tienen signo
menos “-”:
xP = min (x1, x3, x5)
Reajuste el valor de las celdas básicas en xP conforme a los signos correspondientes:
x1 = x1 - xP
x2 = x2 + xP
x3 = x3 - xP
x4 = x4 + xP
x = x x
x5 x5 – xP
Z = Z + (Costo Marginal) x xP
7) Descarte los costos marginales de las celdas no básicas y regrese al paso 1.
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
MÉTODO DE LA DISTRIBUCIÓN MODIFICADA
1) Asignar a cada fila las variables:
ui , i = 1, 2, ..., m
Asignar a cada columna las variables:
vj , j = 1, 2, ..., n
2) Con cada celda básica se tiene:
cij = ui + vj
se asigna:
u1 = 0
determinar las restantes variable u y v.
3) Determinar el costo marginal de las celdas no básicas de la siguiente forma: Costo Marginal (k, m) = ckm – ( uk + vm ) 4) Si todas las celdas no básicas tienen costo marginal no negativo la solución actual es óptima.FIN. 5) Localizar la celda que tenga el costo marginal más negativo. Diseñar un circuito similar al método anterior para esta celda. Asignar a esta celda xP, donde xP es el mínimo valor de las celdas del circuito que tienen signo menos “-”: xP = min ( x1, x3, x5)
Reajuste el valor de las celdas básicas en xP conforme a los signos correspondientes:
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
6) Descarte los costos marginales de las celdas no básicas y regrese al paso 1.
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Introducción
Muchas de las situaciones en la vida exigen una de dos respuestas posibles: si o
no. Así Muchas de las situaciones en la vida exigen una de dos respuestas
posibles: si o no. Así es que podemos representar éstas posibilidades con los
valores 0 (no) y 1 (si), y aprovechar las matemáticas para que nos den una mano
ante decisiones difíciles; a esto es lo que solemos llamar -por obvias razones-
Programación Binaria.
Una de las muchísimas aplicaciones de la Programación Binaria, es el problema
de la Asignación. Este método analiza el problema de asignar un cierto número
de recursos a un determinado número de tareas, con base en algún tipo de
valoración para cada recurso. Cada recurso, podrá ser asignado a una sola tarea.
El PA consiste en asignar recursos a tareas en función de un objetivo ligado a la
eficiencia del sistema. Un ejemplo típico es el de asignación de personas a turnos
horarios, o el de asignar personas a máquinas.
El esquema tabular del PA es:
Planteamiento del problema
Minimizar el costo total de operación de modo que:
3.2 EL PROBLEMA DE ASIGNACION
M1 M2 ............... Mn ai
T1
c11 c12
...............c1n
1
T2
c12 c22
...............c2n
1
.........
.........
.........
...............
.........
.........
Tm
cm1 cm2
...............
cmn
1
bj 1 1 ................ 1
M A Q U I N A S
T A
R E
A S
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
• cada tarea se asigne a una y sólo una máquina
• cada máquina realice una y sólo una tarea
Algoritmo para determinar la asignación optima
La utilización del método SIMPLEX o los métodos del Problema de Transporte, no
resultan eficientes para resolver el Problema de Asignación, por lo cual se utiliza
otro método denominado METODO HÚNGARO.
El Método Húngaro se desarrolló por Kuhn, basado en un trabajo de Egerváry y
Konig. Fue Kuhn quien lo denominó: Método Húngaro.
Característica del Método Húngaro
El método a estudiar tiene la siguiente característica:
a) Se garantiza la solución óptima.
b) El procedimiento requiere que la matriz de costos sea no negativa.
c) La solución óptima se obtiene en una matriz de costos equivalente cuyo valor
óptimo es cero (0).
d) El problema planteado debe estar balanceado:
1,0
..1,1
..1,1
..
c
n
1j
m
1i
m
1i
n
1j
ij
ij
ij
ij
ij
x
mix
njx
as
xMin Xij: 1 si la tarea i se hace con la máquina j
cij: costo de realizar la tarea i con máquina j
n: tareas
m: máquinas
Si hay más máquinas que tareas se formula
con desigualdades, y se resuelve con tareas
ficticias
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
e) La solución óptima no varía si a la matriz original se le incrementa un valor k a
cada celda. Pero el valor Z se incrementa en nk.
f) La solución óptima no varía si a la matriz original se le incrementa un valor k a
una fila o columna. Pero el valor Z se incrementa en k.
Proceso del Método Húngaro
1) Reducción por filas
Determinar el mínimo valor de cada fila y restarlo a todas las celdas de su
correspondiente fila. Esto garantiza un cero en cada fila.
2) Reducción por columnas
Determinar el mínimo valor de cada columna y restarlo a todas las celdas de su
correspondiente columna. Esto garantiza un cero en cada columna.
3) Cubrimiento de ceros
Con el mínimo número de rectas cubrir los ceros de la matriz reducida.
Empezar por la fila o columna que tenga el mayor número de ceros.
Si el número de rectas resulta igual a n (número de tareas o equipos) se ha
llegado a la solución óptima Pasar al paso 5 de lo contrario pasar al óptima. 5,
paso 4.
4) Reducción posterior
Localizar la celda no cubierta de menor costo. Restar el valor determinado a las
celdas no cubiertas. Sumar el valor determinado a las celdas que se encuentren
en la intersección de las rectas. Regresar al paso 3.
5) Localización de la solución
Determinar las filas que tengan un único valor cero y asignarlos, eliminar las
columnas correspondientes. Determinar las columnas que tengan un único valor
cero y asignarlos, eliminar las filas correspondientes.
Repetir este procedimiento tantas veces sea necesario.
En caso de celdas con empates seleccionar arbitrariamente.
La asignación localizada de valor cero, implantarla en la matriz de costos original y
determinar el valor de Z.
Problema ejemplo
Existen 5 operarios (A, B, C, D y C) que tienen que llenar 5 cargos (I, II, III, IV y V).
La matriz de costos que caracteriza el problema de asignación es la siguiente:
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Determinar la asignación óptima
1- Se calcula C’ij= Cij – elemento más pequeño de cada columna
2. Se calcula C*ij = C’ij – elemento mas pequeño de cada fila
I II III IV V
A 5 3 7 3 4
B 5 6 12 7 8
C 2 8 3 4 5
D 9 6 10 5 6
E 3 2 1 4 5
I II III IV V
A 3 1 6 0 0
B 3 4 11 4 4
C 0 6 2 1 1
D 7 4 9 2 2
E 1 0 0 1 1
I II III IV V
A 3 1 6 0 0
B 0 1 8 1 1
C 0 6 2 1 1
D 5 2 7 0 0
E 1 0 0 1 1
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
3. Procederemos a encontrar el número mínimo de recta r que cubren todos los
ceros de la matriz C*
Vemos que r = 4 que es diferente de m=5, por consiguiente no se ha llegado al
óptimo
4. En este caso ⍬= 1 (elemento mínimo no cubierto por las rectas). Se resta ⍬ a
todos los elementos no cubiertos por las rectas- Se suma ⍬ a todos los elementos
en las intersecciones entre 2 rectas y se vuelve al paso 3. La matriz C* se
transforma en
Se observa que r = 5 = m =5, por consiguiente se ha llegado al óptimo
6. Determinamos la asignación óptima
I II III IV V
A 3 1 6 0 0 2
B 0 1 8 1 1 1
C 0 6 2 1 1 1
D 5 2 7 0 0 2
E 1 0 0 1 1 2
2 1 1 2 2
I II III IV V
A 3 0 5 0 0 3
B 0 0 7 1 1 2 1
C 0 5 1 1 1 1
D 5 1 6 0 0 2
E 2 0 0 2 2 2
2 3 1 2 2
2 1 1
1
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Hay dos soluciones óptimas:
A es asignado a IV
B es asignado a II
C es asignado a I
D es asignado a V
E es asignado a II
O bien:
A es asignado a V
B es asignado a II
C es asignado a I
D es asignado a IV
E es asignado a III
El costo total del programa en ambos casos es Z = $ 18
3.3 EL USO DE SOFTWARE
I II III IV V
A 3 0 5 0 0 3
B 0 0 7 1 1 2
C 0 5 1 1 1 1
D 5 1 6 0 0 2
E 2 0 0 2 2 2
2 3 1 2 2
0
0 0
0 0
0
0
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Software WinQsb
El WinQsb maneja el problema del transporte en su módulo de Modelos de Redes,
el cual en su inicio nos muestra la siguiente ventana, que se debe diligenciar así:
Fíjese que éste módulo también resuelve otros modelos de redes, que se
especifican en la parte izquierda de la ventana.
Los datos se pueden ingresar de dos formas: En una matriz ó tablero de doble
entrada ó de forma gráfica.
A continuación se ilustra el ingreso de datos en la tabla de doble entrada.
El modo de edición del menú principal permite cambiar los rótulos de las fuentes y
los destinos. No es necesario que la oferta sea igual a la demanda, el software se
encarga de agregar fuentes ó destinos de holgura, según sea la necesidad.
Para solucionar el problema, se da clic sobre el icono que aparece en la
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
parte superior y que se señala en la figura siguiente:
El WinQsb le ofrecerá entonces una ventana con la respuesta
óptima del problema, indicando cuántas unidades enviar desde cada una
de las ciudades de origen a cada una de las ciudades de destino, con su
costo por envío y el costo total de la operación.
Si se usa éste icono, el WinQsb nos ilustrará mediante una red la respectiva
respuesta óptima al problema.
Observe que en éste problema la oferta de los
Centros de distribución es igual a los
requerimientos de los detallistas, por lo tanto no
hubo necesidad de adicionar ni fuentes, ni
destinos ficticios y se trata de un problema de
mercado perfecto.
A continuación se ilustra el mismo problema; Pero
bajo el software del INVOP (Investigación de
Operaciones), Software creado por Beatriz Loubet y Sandra Segurade la Facultad
de Ciencias Económicas de la Universidad del Cuyo en Argentina; El software
está hecho en lenguaje Delphi y puede ser adquirido gratuitamente dela
siguientes direcciones en internet:
http//members.tripod.com/~operativa www.cui.edu.co/industrial/SOF01.html
Software INVOP
Este software maneja las siguientes aplicaciones: Asignaciones, Transporte,
Distancias en redes (Ruta más corta, Árbol de mínimo recorrido, Agente viajero),
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
Flujo de redes.
El invop está en Español y su metodología dirigido a la enseñanza, ofreciendo al
usuario tanto la parte teórica de fundamento matemático como la parte práctica de
solución de problemas con sus respectivos ejemplos.
El Invop presenta una ventana principal, en la que hace una breve, pero útil
reseña de sus aplicaciones, de ellas seleccionamos la de transporte, como se
muestra en la figura siguiente:
Al escoger la opción de transporte, el INVOP nos ofrece una ventana en donde
captura los datos del problema y en un recuadro situado en la parte inferior
derecha, donde nos ofrece la solución óptima. Colocando el cursor sobre algunos
sitios de interés de ésta ventana, se ofrece un rótulo en fondo amarillo con la
respectiva instrucción de ayuda.
En la parte inferior izquierda de la ventana se especifica el criterio de optimización
y la cantidad de fuentes y destinos, en la parte superior derecha se introducen los
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
costos por unidad a transportar y habilitando el cuadro de control, se editan
los encabezados de fila ycolumna, al igual que las ofertas y las demandas de
fuentes y destinos.
Cuando la información del problema está introducida, se procede a solucionar el
problema, haciendo clic sobre el icono del menú superior, que tiene la figura de
una calculadora,
Entonces se llena el cuadro en la parte inferior derecha con la solución óptima. En
la figura siguiente se ilustra ésta ventana.
Se recomienda al Usuario del Software leer la ayuda (Help), en la que se explica
toda la parte conceptual y matemática del algoritmo del transporte al igual que se
ilustran varios ejemplos de muy buena calidad.
RESOLUCIÓN DE UN PROBLEMA DE ASIGNACIÓN MEDIANTE WINQSB -
NETWORK MODELING
La facilidad de resolver un problema de asignación mediante WinQSB es aún
mayor a la que se incurre mediante programación lineal, y esta metodología
justifica el pensar en que el método húngaro es sumamente anacrónico
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
únicamente contemplado para fines históricos y académicos. En el módulo
NETWORK MODELING del paquete de herramientas WinQSB se puede resolver
el modelo tan solo traspasando los costos de una matriz n*m a otra que brinda el
módulo n*m.
INGRESANDO LOS DATOS A WINQSB - NETWORK MODELING
RESULTADOS OBTENIDOS MEDIANTE WINQSB - NETWORK MODELING
Por ende la asignación que representa el menor costo para la jornada de
mantenimiento preventivo determina que el Equipo 1 realice el mantenimiento de
la Máquina 1, el Equipo 2 realice el mantenimiento de la Máquina 3 y el Equipo 3
realice el mantenimiento de la Máquina 2, jornada que tendrá un costo total de 17
unidades monetarias.
De esta manera se hace evidente cual es la alternativa predilecta para resolver
problemas de asignación.
Bibliografía
1. Arbonas, M.E. Optimización Industrial (I): Distribución de los recursos.
Colección Productica No. 26. Marcombo S.A, 1989
2. Arbonas, M.E. Optimización Industrial (II): Programación de recursos.
Colección Productica No. 29. Marcombo S.A, 1989.
3. Anderson, D.R., Sweeney.J. , Williams,T.A. , Introducción a los Modelos
Cuantitativos para Administración. Grupo Editorial Iberoamérica. 1993.
Direcciones electrónicas:
http://www.monografias.com/trabajos6/proli/proli.shtml#Bibliograf%C3%ADa
ALGORITMOS ESPECIALES DE PROGRAMACION LINEAL UNIDAD 3
ANGEL RAMOS APARICIO
www.ditutor.com/programacion_lineal/programacion_lineal.html
www.programacionlineal.net/
www.vitutor.com/algebra/pl/a_1.htm
www.vitutor.com/algebra/pl/a_3.html