INDICE4.1 Definicion Problema de Transporte34.2 Metodo de
Aproximacion de Vogel54.3 Metodo de Modi84.4 Procedimiento de
Optimizacion94.5 Definicin Problema de Asignacin94.6 El Mtodo
Hngaro de Asignacin12Conclusin13Bibliografa13
Unidad 4 Transporte y asignacin 4.1 Definicion Problema de
TransporteProblema del transporte
Una empresa dedicada a la fabricacin de componentes de ordenador
tiene dos fbricas que producen, respectivamente, 800 y 1500 piezas
mensuales. Estas piezas han de ser transportadas a tres tiendas que
necesitan 1000, 700 y 600 piezas, respectivamente. Los costes de
transporte, en pesetas por pieza son los que aparecen en la tabla
adjunta. Cmo debe organizarse el transporte para que el coste sea
mnimo?Un problema particular que se resuelve con los procedimientos
de la programacin lineal es la situacin conocida como problema del
transporte o problema de la distribucin de mercancas.Se trata de
encontrar los caminos para trasladar mercanca, desde varias plantas
(orgenes) a diferentes centros de almacenamiento (destinos), de
manera que se minimice el costo del transporte.
Tienda ATienda BTienda C
Fbrica I371
Fbrica II226
Para que un problema pueda ser resuelto por el mtodo del
transporte debe cumplir:1) La funcin objetivo y las restricciones
deben ser lineales.
2) El total de unidades que salen en origen debe ser igual al
total de unidades que entran en destino.
En este tipo de problemas se exige que toda la produccin sea
distribuida a los centros de ventas en las cantidades que precisa
cada uno; por tanto, no pueden generarse inventario del producto ni
en las fbricas ni en los centros de ventas.En consecuencia, los 800
artculos producidos en la fbrica I deben distribuirse en las
cantidades x, y, z a A, B y C, de manera que x + y + z = 800. Pero,
adems, si desde I se envan x unidades a A, el resto, hasta las 1000
necesarias en A, deben ser enviadas desde la fbrica II; esto es,
1000 - x unidades sern enviadas desde II a A.Del mismo modo, si
desde I a B se envan y, el resto necesario, 700 - y, deben enviarse
desde II. Y lo mismo para C, que recibir z desde I y 600 - z desde
II.En la siguiente tabla de distribucin se resume lo dicho:Envosa
la tienda A (1000)a la tienda B (700)a la tienda C (600)
Desde la fbrica I ( 800)xy800 - x - y
Desde la fbrica II (1500)1000 - x700 - yx + y - 200
La ltima columna la hemos obtenido de la siguiente forma:Como x
+ y + z = 800 , se tiene que z = 800 - x - y, de donde, 600 - z =
600 - (800 - x - y) = x + y - 200.Ahora bien, todas las cantidades
anteriores deben ser mayores o iguales que cero. Por tanto, se
obtienen las siguientes desigualdades:x 0 ; 1000 - x 0 ; y 0; 700 -
y 0 ; 800 - x - y 0 ; x + y - 200 0 Simplificando las desigualdades
anteriores, se obtienen las siguientes inecuaciones:1000 x 0 ; 700
y 0 ; 800 x + y 0 Recordemos que nuestro objetivo es abaratar al
mximo los costes de transporte. Estos costes se hallan
multiplicando las cantidades enviadas a desde cada fbrica a cada
tienda por los respectivos costes de transporte unitario.Se
obtiene:Z = f(x,y) = 3x + 2(1000 - x) + 7y + 2(700 - y) + (800 - x
- y) + 6(x + y - 200) = 6x + 10y + 3000 En definitiva, el programa
lineal a resolver es :Minimizar: Z = 6x + 10y + 3000
sujeto a:1000 x 0
700 y 0
800 x + y 0
La regin factible se da en la imagen del margen.Sus vrtices son
A(200,0) ; B(800,0) ; C(100,700) ; D(0,700) y E(0,200).El coste, el
valor de Z en cada uno de esos puntos, es: en A, 4200 en B, 7800 en
C, 10600 en D, 10000 en E, 5000El mnimo se da en A , cuando x = 200
e y = 0.Luego, las cantidades a distribuir son:
Envosa la tienda A (1000)a la tienda B (700)a la tienda C
(600)
Desde la fbrica I ( 800)2000600
Desde la fbrica II (1500)800700 0
4.2 Metodo de Aproximacion de Vogel
Mtodo de Aproximacin de Vogel: para cada rengln y columna que
queda bajo consideracin, se calcula su diferencia, que se define
como la diferencia aritmtica entre el costo unitario ms pequeo
(cij) y el que le sigue, de los que quedan en ese rengln o columna.
(Si se tiene un empate para el costo ms pequeo de los restantes de
un rengln o columna, entonces la diferencia es 0). En el rengln o
columna que tiene la mayor diferencia se elige la variable que
tiene el menor costo unitario que queda. (Los empates para la mayor
de estas diferencias se pueden romper de manera arbitraria).Para
hacer ms concreta esta descripcin, se ilustrar el procedimiento
general, utilizando el mtodo de aproximacin de Vogel para resolver
el ejemplo presentado anteriormente y que fue resuelto por la regla
de la esquina noroeste:Iniciamos el mtodo calculando las primeras
diferencias para cada rengln y columna. De las diferencias que
obtuvimos nos fijamos en la mayor (Por qu?), que resulta ser para
la tercera columna. En esa columna encontramos el costo unitario
(cij) menor y en esa celda realizamos la primera asignacin:
RecursosDIF.
3647
51
24323
22 00
548
31
Demanda342 01 10 10
DIF.11 3 12
Nota: Marcaremos a la mayor de las diferencias seleccionada
encerrndola en un crculo y escribindole como superndice el nmero
que le corresponda en la secuencia de seleccin.
Observemos en la figura anterior que nicamente eliminamos el
segundo rengln ya que la tercera columna nos servir despus para
hacer la asignacin de una variable bsica degenerada. Continuando
con la aplicacin del mtodo, tenemos que calcular nuevamente las
diferencias de las columnas ya que hemos eliminado un rengln y sto
puede ocasionar que las diferencias aritmticas entre el costo
unitario ms pequeo y el que le sigue ya no sean las mismas:
RecursosDIF.
3647
51
24323
22 00
548
33 01
Demanda34 12 01 10 10
DIF.11 3 12
1 4 2 21
Como siguiente paso deberamos calcular las nuevas diferencias de
columnas, pero ya que solamente queda un rengln dentro de las
posibilidades (sto no significa que solamente un rengln quede bajo
consideracin ya que podemos observar que ninguna de las cuatro
columnas (destinos) ha sido eliminada y todas quedan todava bajo
consideracin), no es posible encontrar la diferencia aritmtica
entre el costo menor y el que le sigue, por lo tanto vamos tomando
una a una las celdas que quedan comenzando con la de menor costo
unitario hasta que todas hayan sido asignadas.
RecursosDIF.
3647
31015 2 1 01
24323
22 00
548
33 01
Demanda3 04 1 02 01 0 10 10
DIF.11 3 12
1 4 2 21
La solucin inicial bsica factible es x11=3, x12=1, x13=0
(variable bsica degenerada), x14=1, x23=2 y x32=3 y el costo total
de transporte asociado a esta primera Poltica de Transporte
factible es de:
x11c11x12c12x13c13x14c14x23c23x32c32
Costo =3(3)+1(7)+0(6)+1(4)+2(3)+3(3)= 35 unidades
Es necesario aclarar que sta puede o no ser la solucin final del
problema, es necesario aplicar a esta primera solucin factible la
prueba de optimalidad ya que puede existir una mejor poltica de
transporte que minimice todava ms el costo total.
4.3 Metodo de Modi
Este mtodo reproduce exactamente las mismas iteraciones del
mtodo de banquillo. La principal diferencia ocurre en la forma en
que las variables no bsicas se evalan en cada iteracin. Asociados a
cada rengln i de la tabla existen multiplicadores Ui similarmente
se asocia un multiplicador Vj a cada columna de la tabla j. Para
cada variable bsica Xij de la solucin actual, se escribe la ecuacin
Ui +Vj = Cij. Esas ecuaciones proporcionan m+n-1 relaciones con m+n
incgnitas.Los valores de los multiplicadores pueden ser
determinados a partir de las ecuaciones suponiendo un valor
arbitrario para cualquiera de los multiplicadores (usualmente se
establece U1=0) y resolviendo el sistema de ecuaciones para
encontrar los multiplicadores desconocidos. Una vez que se hace
esto, la evaluacin de cada variable no bsica X pq est dada como: El
criterio que se utiliza para seleccionar la variable que entra es
el mismo que el mtodo de banquillo (la mayor negativa).Ejemplo:Una
compaa est considerando una demanda de 5 clientes utilizando
artculos que tienen disponibles en 2 almacenes. Los almacenes
cuentan con 800 y 1000 unidades respectivamente. Los clientes
necesitan 200, 150, 200, 180 y 500 unidades respectivamente. Los
costos de embarque por artculo de los almacenes de los clientes
son:
Resuelva el modelo de transporte empleando.a) Una solucin
inicial por el mtodo de aproximacin de vogel.b) La solucin ptima
por el mtodo de multiplicadores.DESTINO FICTICIO = 570 ARTCULOS
4.4 Procedimiento de Optimizacion
Una solucin BF es optima si y solo si Cij-Ui-Vj=>0 para toda
(ij)tal que Xij es no basica. Es la reducion de costos. Pasos para
la optimizacion: 1.- se determina la variable basica entrante; se
elige la variable no basica Xij que tiene el valor negativo mas
grande(en terminos absolutos)para Cij-Ui-Vj. 2.- se determina la
varible basica que sale: se identifica la reaccion en cadena que se
necesita para conservar la factibilidad cuando aumenta el valor de
la variable basica entrante. Entre las celdas donadoras se
selecciona la variable basica que tiene el menor valor. 3.- se
determina la nueva solucion BF; se suma el valor de la variable
basica que sale a las asignaciones de las celdas receptoras y se
resta a las asignaciones de las celdas donadoras.
4.5 Definicin Problema de Asignacin
Definicin del problema.Sean un conjunto de fragmentos F = {F1,
F2, ..., Fn} y una red formada por el conjunto de sitios S = {S1,
S2, ..., Sm} en la cual un conjunto de aplicaciones Q = {q1, q2,
..., qq} se ejecutan. El problema de la asignacin implica encontrar
la distribucin ptima de F sobre S. Uno de los problemas ms
importantes que necesita discusin es el significado de distribucin
ptima. La distribucin ptima puede definirse con respecto a dos
medidas: 1. Coste mnimo. La funcin de coste consiste en el coste de
almacenamiento de cada Fi en un sitio Sj, el coste de practicar una
consulta en Fi en el sitio Sj, el coste de actualizar Fi en todos
los sitios donde se almacene y el coste de las comunicaciones de
datos. El problema de la asignacin, entonces, intenta encontrar un
esquema de asignacin tal que minimice esta funcin de coste
combinado.1. Rendimiento. La estrategia de asignacin se disea para
mantener una medida del rendimiento. Dos medidas habituales de este
rendimiento son el tiempo de respuesta y la salida del sistema en
cada sitio. Evidentemente, se debe intentar minimizar la primera y
maximizar la segunda.Se han propuesto modelos de asignacin que
enfocan el concepto de distribucin ptima desde diferentes puntos de
vista. Sin embargo, no resulta descabellado pensar en la inclusin,
tanto del rendimiento como de los factores de coste, dentro del
concepto. En otras palabras, deberamos buscar un esquema de
asignacin tal que, por ejemplo, la respuesta a las consultas de los
usuarios se realizase en el menor tiempo posible mientras que el
coste de procesamiento fuese mnimo. Una afirmacin similar podra
hacerse respecto a la maximizacin de la salida del sistema.
Consideremos ahora una formulacin del problema muy simple.
Definamos F y S como se hizo anteriormente. Por el momento,
consideraremos nicamente un fragmento sencillo, Fk. Daremos un
nmero de definiciones que nos permitan modelar el problema de la
asignacin. 1. Asumiremos que Q puede modificarse de tal manera que
sea posible identificar las consultas de actualizacin de las de
lectura, y definiremos lo siguiente para ese fragmento simple
Fk:
donde ti es el trfico de lectura que se genera en el sitio Si
para Fk, y
donde ui es el trfico de actualizacin que se genera en el sitio
Si para Fk.1. Asumiremos que el coste de comunicaciones entre un
par de sitios Si y Sj es fijo para una unidad de transmisin. Adems,
asumiremos que ste es diferente para actualizaciones y para
lecturas, por lo que definimos:
donde cij es el coste de la unidad de comunicacin para las
peticiones de lectura entre los sitios Si y Sj y c'ij es el coste
de la unidad de comunicacin para las peticiones de lectura entre
los sitios Si y Sj.1. Sea di el coste de almacenar el fragmento en
el sitio Si. Entonces definimos D = {d1, d2, ..., dm} como el coste
de almacenar Fk en todos los sitios. 1. Asumiremos que no existen
restricciones de capacidad en los sitios o en los enlaces de
comunicaciones. Entonces el problema de asignacin puede
especificarse como un problema de minimizacin de costes por el cual
se intenta encontrar el conjunto I S que especifique el lugar donde
han de ubicarse las copias de los fragmentos. La expresin matemtica
hace uso de la variable de decisin para la ubicacin xj es, xj = 1
si el fragmento Fk se asigna al sitio Sjxj = 0 en otro caso
entonces, definida xj,
El segundo trmino de la funcin calcula el coste total de
almacenar todas las copias duplicadas del fragmento. El primer
trmino corresponde al coste de transmisin de las actualizaciones a
todos los sitios que mantienen rplicas de un fragmento y al coste
de ejecucin de las peticiones de lectura en el sitio, lo cual
resultar un coste mnimo de transmisin de datos. Esta es una
formulacin muy simple que no es vlida para el diseo de bases de
datos distribuidas. Pero en el caso que lo fuera, existira un
problema. Para un gran nmero de fragmentos y de sitios, obtener
soluciones ptimas resultara probablemente totalmente inviable. Las
investigaciones, por tanto, deben girar en torno a la bsqueda de
buenos heursticos que proporciones soluciones parcialmente ptimas.
Hay un nmero de razones del porqu de formulaciones tan simples que
no sirven para el diseo de bases de datos distribuidas.
Generalmente, se heredan de los modelos de asignacin de archivos
para redes, pero 1. No se pueden tratar los fragmentos como
archivos individuales que se asignen aisladamente. La ubicacin de
un fragmento generalmente tiene influencia sobre las decisiones de
asignacin de los otros fragmentos, a los cuales se acceden a la
vez, puesto que el coste de acceso de los fragmentos restantes
puede variar. Por tanto, las relaciones entre fragmentos deben
tenerse en consideracin.1. El acceso de las aplicaciones a los
datos se modela muy sencillamente. Una peticin de usuario se
resuelve en un sitio y todos los datos necesarios se transfieren a
ese sitio. En los sistemas de bases de datos distribuidos, el
acceso a los datos es ms complicado que el simple acceso a archivos
remotos. Por tanto, la relacin entre la asignacin y el
procesamiento de consultas debera tambin tenerse en cuenta.1. Estos
modelos no tienen en cuenta el coste de mantenimiento de la
integridad, an localizando dos fragmentos implicados con las mismas
restricciones de integridad en dos sitios diferentes podra resultar
costoso dicho mantenimiento.1. Igualmente, el coste derivado del
control de concurrencia debera tenerse en cuenta.En resumen,
debemos distinguir entre el problema tradicional de asignacin de
archivos de la asignacin de fragmentos en los sistemas de bases de
datos distribuidos. No existen modelos heursticos generales que
tomen como entrada un conjunto de fragmentos y produzcan una
asignacin cercana a lo ptimo que adems est influenciada por los
tipos de restricciones descritas antes. Los modelos desarrollados
realizan una serie de simples suposiciones y pueden aplicarse a
ciertas formulaciones especficas. Por tanto, presentaremos un
modelo general y discutiremos una serie de posibles heursticos que
puedan emplearse para resolver el problema. Posteriormente,
describiremos un algoritmo concreto de asignacin. Informacin
necesaria.En esta etapa de la asignacin, necesitaremos datos
cuantitativos sobre la base de datos, las aplicaciones que
funcionan sobre ella, la red de comunicaciones, las caractersticas
de proceso, y el lmite de almacenamiento de cada sitio de la red.
Procederemos a discutirlos en detalle.Informacin de la base de
datos. Para desarrollar la fragmentacin horizontal, definimos la
selectividad de los mintrminos. Ahora, necesitamos extender esta
definicin a los fragmentos y definir la selectividad de un
fragmento Fj con respecto a una consulta qi. Es el nmero de tuplas
de Fj a las que se necesita acceder para procesar qi. Este valor lo
notaremos como seli(Fj). Otro elemento informativo de los
fragmentos de la base de datos es su tamao. El tamao de un
fragmento Fj viene dado por tamao(Fj) = card(Fj)*long(Fj), donde
long(Fj) es la longitud (en octetos) de una tupla del fragmento Fj.
Informacin de las aplicaciones. Mucha de la informacin relativa a
las aplicaciones se recoge durante el proceso de fragmentacin, pero
se necesita un poco ms para el modelo de asignacin. Las dos medidas
ms importantes son el nmero de accesos de lectura que una consulta
qi realiza sobre un fragmento Fj durante su ejecucin (llamada
RRij), y el nmero de accesos de actualizacin que una consulta qi
realiza sobre un fragmento Fj durante su ejecucin (llamada URij).
Tambin necesitamos definir dos matrices UM y RM, con elementos uij
y rij, respectivamente, que se especifican como sigue:uij = 1 si la
consulta qi actualiza el fragmento Fjuij = 0 en otro caso rij = 1
si la consulta qi lee del fragmento Fjrij = 0 en otro caso Tambin
debe definirse un vector O de valores o(i), donde o(i) especifica
el sitio origen de la consulta qi. Finalmente, especificaremos las
restricciones impuestas por el tiempo de respuesta, asignando a
cada aplicacin el mximo tiempo de respuesta permitido. Informacin
de los sitios. Sobre cada ordenador necesitamos conocer sus
capacidades de procesamiento y almacenamiento. Obviamente, estos
valores pueden calcularse a travs de funciones elaboradas o por
simples estimaciones. La unidad de coste de almacenar datos en el
sitio Sk ser denotada como UCAk. As mismo, especificaremos como
medida de coste UPTk al coste de procesar una unidad de trabajo en
el sitio Sk. La unidad de trabajo debera ser idntica a aquella
utilizada en las medidas RR y UR. Informacin sobre la red. En
nuestro modelo asumiremos la existencia de una red simple donde el
coste de comunicaciones se define respecto a una trama de datos.
Entonces gij nota el coste de comunicacin por trama entre los
sitios Si y Sj. Para permitir el clculo del nmero de mensajes,
usaremos ftamao como el tamao (en octetos) de una trama. Es
evidente que existen modelos de red mucho ms elaborados que toman
en cuenta las capacidades del canal, las distancias entre sitios,
las caractersticas del protocolo, etc. Sin embargo, se cree que la
derivacin de estas ecuaciones se sale fuera de este documento.
4.6 El Mtodo Hngaro de Asignacin
Este algoritmo se usa para resolver problemas de minimizacin, ya
que es ms eficaz que el empleado para resolver el problema del
transporte por el alto grado de degeneracin que pueden presentar
los problemas de asignacin. Las fases para la aplicacin del mtodo
Hngaro son: Paso 1: Encontrar primero el elemento ms pequeo en cada
fila de la matriz de costos m*m; se debe construir una nueva matriz
al restar de cada costo el costo mnimo de cada fila; encontrar para
esta nueva matriz, el costo mnimo en cada columna. A continuacin se
debe construir una nueva matriz (denominada matriz de costos
reducidos) al restar de cada costo el costo mnimo de su columna.
Paso 2: (En algunos pocos textos este paso se atribuye a Flood).
Consiste en trazar el nmero mnimo de lneas (horizontales o
verticales o ambas nicamente de esas maneras) que se requieren para
cubrir todos los ceros en la matriz de costos reducidos; si se
necesitan m lneas para cubrir todos los ceros, se tiene una solucin
ptima entre los ceros cubiertos de la matriz. Si se requieren menos
de m lneas para cubrir todos los ceros, se debe continuar con el
paso 3. El nmero de lneas para cubrir los ceros es igual a la
cantidad de asignaciones que hasta ese momento se pueden realizar.
Paso 3: Encontrar el menor elemento diferente de cero (llamado k)
en la matriz de costos reducidos, que no est cubierto por las lneas
dibujadas en el paso 2; a continuacin se debe restar k de cada
elemento no cubierto de la matriz de costos reducidos y sumar k a
cada elemento de la matriz de costos reducidos cubierto por dos
lneas (intersecciones). Por ltimo se debe regresar al paso 2.
Notas: 1. Para resolver un problema de asignacin en el cual la meta
es maximizar la funcin objetivo, se debe multiplicar la matriz de
ganancias por menos uno (1) y resolver el problema como uno de
minimizacin. 2. Si el nmero de filas y de columnas en la matriz de
costos son diferentes, el problema de asignacin est desbalanceado.
El mtodo Hngaro puede proporcionar una solucin incorrecta si el
problema no est balanceado; debido a lo anterior, se debe balancear
primero cualquier problema de asignacin (aadiendo filas o columnas
ficticias) antes de resolverlo mediante el mtodo Hngaro. 3. En un
problema grande, puede resultar difcil obtener el mnimo nmero de
filas necesarias para cubrir todos los ceros en la matriz de costos
actual. Se puede demostrar que si se necesitan j lneas para cubrir
todos los ceros, entonces se pueden asignar solamente j trabajos a
un costo cero en la matriz actual; esto explica porqu termina
cuando se necesitan m lneas. ConclusinMe ha parecido muy importante
el contenido de la materia ya que por supuesto que se aplicar en
nuestras labores en el momento en el que nos lleguemos a enfrentar
en algn problema en nuestra vida laboral y es importante saber cada
uno de los mtodos que existen ya que as sabremos que no solo hay
una sola manera de resolver el problema y entonces podremos escoger
la manera correcta o que sera la mejor forma para resolver nuestro
problema Bibliografa
http://www.sites.upiicsa.ipn.mx/polilibros/portal/Polilibros/P_terminados/InvOperChave/Documentos/Unidad1/UNIDAD112.htmhttps://www.academia.edu/6989381/Investigacion_de_operaciones
