Optimización y reparto de costes en problemas de inventario centralizados

Traballo Fin de Grao Optimización y reparto de costes en problemas de inventario centralizados Martín Brañas Rey 2020/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Optimización y reparto de costes en problemas de inventario centralizados Martín Brañas Rey 2020/2021 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Estadística e Investigación Operativa Título: Optimización y reparto de costes en problemas de inventario centralizados Breve descrición do contido Este traballo n de grao consiste nunha revisión bibliográca das principais situacións de cooperación multi-axente en problemas de inventario centralizados. A análise desta clase de problemas considera dous obxectivos como fundamentais. Tras a formulación do modelo matemático axeitado, identifícase a política óptima de inventario a seguir e que minimiza os costes conxuntos da cooperación para os posibles grupos de individuos. Unha vez determinada, cómpre repartir os costes resultantes desa colaboración entre os axentes involucrados no problema, usando para este n resultados propios da teoría de xogos Recomendacións Outras observacións iii Índice general Resumen vii Introducción ix 1. Los juegos de inventario 1 1.1. Introducción.................................... 1 1.2. El modelo básico de inventario . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Costedepedido.................................. 4 1.4. Coste de almacenaje y pedido . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2. Los sistemas de inventario y transporte 17 2.1. Introducción.................................... 17 2.2. Sistemas de transporte de inventario . . . . . . . . . . . . . . . . . . . . . . 18 2.3. Una regla de asignación de costes . . . . . . . . . . . . . . . . . . . . . . . . 22 3. Los problemas de inventario multi-producto 27 3.1. Introducción.................................... 27 3.2. Problemas EOQ multi-item de inventario . . . . . . . . . . . . . . . . . . . . 28 3.3. Problemas EOQ multi-item de inventario bajo cooperación . . . . . . . . . . 30 3.4. Juegos de inventario multi-item . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.5. Compartir los costes de pedidos conjuntos . . . . . . . . . . . . . . . . . . . 35 3.6. Estructura de coaliciones de pedido beneciosas . . . . . . . . . . . . . . . . 37 4. Conclusión 39 Bibliografía 41 v Resumen Este trabajo de n de grado es una revisión bibliográca de las principales situaciones de cooperación multi-agente en problemas de inventario centralizados. El análisis de esta clase de problemas tiene dos objetivos fundamentales. Tras la formulación del modelo matemático adecuado, se identica la política óptima de inventario a seguir y que minimiza los costes conjuntos da cooperación para los posibles grupos de individuos. Una vez determinada, se deben repartir los costes resultantes de esa colaboración entre los agentes involucrados en el problema, usando para este n resultados propios de la teoría de juegos. Abstract This thesis is a literature review of the main situations multi-agent cooperation in centralized inventory problems. The analysis of this kind of problems has two fundamental objectives. After the formulation of the appropriate mathematical model, the optimal inventory policy, that minimizes the joint costs of cooperation for the possible groups of individuals, is identied. Once determined, the costs resulting from that cooperationtion have to be allocated among the agents involved in the problem, using for this purpose results from game theory. vii 4 CAPÍTULO 1. LOS JUEGOS DE INVENTARIO Comparando esto con la media del coste por unidad de tiempo de una empresa individualmente adi/Qi+hiQi/2 . Expresando este coste como una función de Q1 unicamente, tenemos: ad1 Q1 +Q1 2d1X i∈N hidi. Minimizando respecto de Q1 da como resultado la cantidad óptima de los pedidos de la empresa i , c Qi : c Qi=v u u t2ad2 i P j∈N hjdj . La longitud óptima del ciclo es : c Qi di =v u u t2a P j∈N hjdj ,∀i∈N. Por lo tanto, el número óptimo de pedidos que la empresa debe realizar es : mN=di c Qi =v u u tP j∈N hjdj 2a=sX j∈N m2 j. Aquí mi=di/˙ Qi=pdihi/(2a) representa el número de pedidos que una empresa i debería hacer para minimizar costes. El coste medio mínimo es igual a 2amN . Como en el caso de una única empresa, el coste de pedido y de almacenaje son iguales ambos a amN . Es relevante recalcar que el mínimo del coste depende unicamente de a , que es información pública, y de mN , que depende de mi . Por lo tanto, para calcular el coste mínimo, es suciente con que cada empresa revele el número óptimo de pedidos que haría si trabajara individualmente, mi . Las empresas no tendrán que revelar sus costes de almacenaje ni su demanda, no es necesario la revelación total de la información. Aunque es posible, que la cantidad de información revelada inuya el almacenaje conjunto de la mercancía. En las siguientes secciones discutiremos diferentes resoluciones a este problema. 1.3. Coste de pedido En esta sección consideraremos situaciones en las cuales cada empresa revela unicamente el número óptimo de pedidos por unidad de tiempo si trabajara de manera individual, mi . Por lo tanto, se mantendrá como información privada di , hi y ˙ Qi . Hemos visto que cuando todas las empresas trabajan de manera conjunta, el número óptimo de pedidos para la empresa i∈N es c Qi=di/mN . Esta cantidad es menor que 1.3. COSTE DE PEDIDO 5 la cantidad óptima individual de pedidos, ˙ Qi=di/mi , dado que, mN=rP j∈N m2 j> mi para todo i∈N . Entonces, el nivel de inventario medio sera menor para cada rma: c Qi/2<˙ Qi/2 . Todas las empresas ahorran en costes de almacenaje. Como el coste de almacenaje es información privada ,no podemos considerar como dividir el coste total de almacenaje entre las empresas. Por lo tanto, asumimos que cada empresa paga sus costes de almacenaje. El tamaño óptimo de los pedidos de la empresa i es c Qi=di/mN , el cual es información privada ya que di es información privada. Para que exista la posibilidad de hacer un pedido conjunto sin revelar información privada necesitamos un intermediario que haga todos los pedidos. Cada empresa le comunica al intermediario su tamaño óptimo de pedido c Qi , y el intermediario hará un pedido de tamaño P i∈Nc Qi . El intermediario conoce mi pero el proveedor no, por lo tanto, el proveedor solo conoce P i∈Nc Qi . Es mas, el intermediario no revelará de una empresa a otra empresa, asegurándose así de que toda la información privada permanece privada. Solo nos interesa el coste óptimo de pedido amN , el cual esta descrito por la 3-tupla {N, a, {mi}iN } . Si una coalición S de empresas coopera entonces el coste óptimo de pedido es asX i∈S m2 i. (1.1) Consecuentemente, se puede denir el juego del coste de pedido correspondiente (N, co) como sigue. Para todas las coaliciones S⊂N , el coste co(S) es igual al coste óptimo anterior y co(∅) = 0 . co(S) = arP i∈S m2 i y co(∅) = 0 . Consideremos algunas propiedades de los juegos de coste de pedido. Un juego de coste (N, c) es cóncavo si para todo i∈N y para todo S⊂T⊂N\{i} tenemos que c(S∪{i})− c(S)≥c(T∪{i})−c(T) y es monótono si para todo S⊂T⊂N se tiene que c(S)≤c(T) . La siguiente proposición prueba las propiedades de monotonía y la concavidad del juego de coste asociado Proposición 1.1. Sea {N, a, {mi}iN } una situación de costes de pedidos y sea (N, co) el juego de coste de pedidos asociado. Entonces el juego (N, co) es cóncavo y monótono. Demostración : Sea (N, co) el juego de coste de pedidos correspondiente. Como P i∈S m2 i es creciente en el numero de elementos de S y como √x es una función monotonamente creciente y cóncava, tenemos que (N, co) es monótono y cóncavo.  6 CAPÍTULO 1. LOS JUEGOS DE INVENTARIO Uno de los mayores problemas de la teoría de juegos cooperativos es como dividir los benecios de la cooperación si la coalición N se ha formado. Una forma de compartir estos benecios es siguiendo una asignación en el núcleo. El núcleo del juego de costes (N, c) es el conjunto C(c) = x∈RN|P i∈N xi=c(N),P i∈S xi≤c(S)∀S⊂N, S 6=∅ . Cuando un elemento del núcleo x∈C(c) se propone como distribución del coste total c(N) , donde la empresa i tiene que pagar xi , entonces una coalición S de empresas pagará como máximo su propio coste ya que P i∈S xi< c(S) . Por lo tanto, ninguna coalición tiene incentivos para abandonar la coalición grande. Un juego esta balanceado si su núcleo es no vacío, y es totalmente balanceado si para cada subjuego (S, cS) esta balanceado, donde cS(T) := c(T) para todo T⊂S . Otra propiedad de los juegos de coste de pedidos es que un múltiplo no negativo de dicho juego es otro juego de coste de pedidos. Sea λ un número no negativo, para toda coalición S de empresas en N se tiene que: λco(S) = arP i∈S (λmi)2 , y esto describe el valor de la coalición S en el juego de coste de pedidos correspondiente a la situación {N, a, {λmi}iN } . Dicha situación se da cuando todos las demandas individuales y los costes de almacenaje aumenta en λ unidades. Por lo tanto, (N, λco) es un juego de coste de pedidos. Sin embargo, la suma de dos juegos de coste de pedido no tiene porque ser otro juego de coste de pedido. Los juegos de coste de pedidos son una clase especial de juegos de producción, como introdujeron Shapley y Shubik (1967). Un juego de producción es un juego cooperativo con un conjunto de jugadores N y el valor de una coalición de jugadores es g(b(S)) , siendo g una función de producción (cóncava) y b(S) = P i∈S bi los recursos de la coalición S . En el caso especico del juego de coste de pedidos jamos co(S) = g(b(S)) con g(x) = a√xyb(S) = P i∈S m2 i . Si cada unidad de producción cuesta una unidad monetaria entonces g(b(S)) no denota unicamente cuanto produce la coalición si no que también denota el coste de los bienes producidos. La cantidad de recursos retenida por la empresa i es b({i}) = m2 i . Una solución interesante para estos juegos es la regla proporcional. Deniremos la regla proporcional π(co) como la regla que divide el coste total co(N) proporcionalmente a los recursos individuales. Esto implica que la empresa i∈N tiene que pagar πi(co) = b({i}) P j∈N b({j})=m2 i P j∈N m2 j co(N) = am2 i rP j∈N m2 j (1.2) donde la ultima igualdad se sigue de (1.1) para S=N . Otra interpretación de esta regla 1.3. COSTE DE PEDIDO 7 proporcional se sigue de que co({i}) = ami para todas las empresas i∈N . Si dividimos el coste total co(N) por la raíz cuadrada del coste individual proporcionalmente entonces la empresa i tiene que pagar : c2 o({i}) P j∈N c2 o({j})co(N) = a2m2 i P j∈N a2m2 j co(N) = m2 i P j∈N m2 j co(N) acabando con la misma regla proporcional. Esta regla tiene algunas propiedades interesantes que veremos a continuación. Primero, para todos los juegos de coste de pedidos (N, co) se tiene que π(co) es un elemento del núcleo C(co) . Esto es fácil de probar, por (1.2) se sigue que P i∈N π(co) = co(N) y para todas las coaliciones no vacías S⊆N tenemos que: X i∈S πi(co) = X i∈S am2 i rP j∈N m2 j≤X i∈S am2 i rP j∈S m2 j =asX j∈S m2 j=co(S). A esta regla proporcional se puede llegar a través de un esquema monótono de asignación de población (PMAS). Estos esquemas fueron introducidos en Sprumont (1990) y se denen como sigue. Un vector y={yiS}, i∈S, S ⊂N, S 6=∅ es un esquema monótono de asignación de población del juego de costes (N, c) sí y solo sí, satisface las dos condiciones siguientes: P i∈S yiS =c(S) , para todas las coaliciones no vacías S de N . para todas las coaliciones no vacías S, T ⊆N y para todo i∈S se tiene que cumplir que S⊂T=⇒yiS ≥yiT . También se tiene que, como cada juego de coste de pedidos (N, co) es cóncavo y como π(co)∈C(co) existe un PMAS y={yiS}, i∈S, S ⊂N, S 6=∅ del juego (N, co) tal que yiN =πi(co) para todo i∈N . Denimos para todo i∈S, S ⊂N, S 6=∅ yiS =am2 i rP j∈S m2 j . Entonces para todo S⊂N, S 6=∅ X i∈S yiS =X i∈S am2 i rP j∈S m2 j =asX j∈S m2 j=co(S) y para todos S, U ⊂N;S, U 6=∅ tales que S⊂U y para todo i∈S 8 CAPÍTULO 1. LOS JUEGOS DE INVENTARIO yiS =am2 i rP j∈S m2 j≥am2 i rP j∈U m2 j =yiU . Finalmente, se tiene que yiN =πi(co) para todo i∈N . Por lo tanto, se puede llegar a la regla π(co) a través del PMAS y . Ahora introduciremos una propiedad de la monotonía de las reglas de solución de la clase de los juegos de coste de pedidos, la cual se parece a la monotonía fuerte de Young (1985). Sea f una regla de solución de la clase de los juegos de coste de pedidos. Entonces fi(co)∈R denota el coste asignado al jugador i∈N según esta regla en el juego c0y f(co)=(fi(co))i∈N∈RN . Sea (N, co) y (N, ¯co) dos juegos de coste de pedidos. La regla f satisface la eciencia si P i∈N fi(co) = co(N) y satisface la monotonía si para todo i∈N tal que co({i})≥¯co({i}) se tiene que co(N)fi(co)≥¯co(N)fi(¯co) . Esta propiedad de la monotonía empieza por la siguiente suposición: si co({i})≥ ¯co({i}) y co(N) = ¯co(N) entonces fi(co)≥fi(¯co) , sin embargo, queremos llegar más lejos, si co({i})≥¯co({i}) y co(N)6= ¯co(N) entonces exijimos que se mantenga la desigualdad anterior y por lo tanto fi(co)≥fi(¯co) exceptuando una corrección en relación a otros jugadores. Juntando eciencia y monotonía se caracteriza la regla proporcional de la clase de los juegos de coste de pedidos, como muestra el siguiente teorema. Teorema 1.2. Existe una única regla que satisfaga la monotonía y la eciencia de la clase de los juegos de coste de pedidos, y es la regla proporcional. Demostración : Es trivial que la regla proporcional satisface la eciencia y la monotonía. Para probar el inverso, tomamos la regla f de la clase de los juegos de coste de pedidos que satisface monotonía y eciencia. Debemos tener en cuenta que la monotonía implica que para todos los juegos de coste de pedidos (N, c0 o) y (N, c00 o) se tiene que: c0 o({i}) = c00 o({i})⇒c0 o(N)fi(c0 o) = c00 o(N)fi(c00 o). (1.3) Deniendo el juego de coste de pedidos (N, c0 o) como c0 o(S) = 0 para todo S⊂N y tomando un juego de coste de pedidos (N, co) . Si para algún i∈N se tiene que co({i}) = 0 entonces co({i}) = c0 o({i}) . De (1.3) se sigue que c0 o(N)fi(c0 o) = c0 o(N)fi(c0 o)=0 y por lo tanto: co({i}) = 0 ⇒fi(co)=0. (1.4) Deniendo el número I(co) como el número de jugadores i∈N con co({i})>0 . Tenemos que fi(co) = πi(co) para todo i∈N aplicando inducción en I(co) tenemos que: Si I(co) = 0 entonces por (1.4), fi(co) = 0 para todo i∈N . 1.3. COSTE DE PEDIDO 9 Si I(co)=1 entonces existe un único jugador k∈N con co({k})>0 . Para todo i∈N\{k}, co({i})=0 , por (1.4), fi(co) = 0 = πi(co) . Por la eciencia se sigue que fk(co) = co(N)−P i6=k fi(co) = co(N)−P i6=k πi(co) = πk(co) . Asumiendo ahora que f(co) = π(co) para todos los juegos de coste de pedidos (N, co) con I(co)≤I, I ≤n−1 . Considerando un juego de coste de pedidos (N, ¯co) correspondiente a N, ¯a, {¯mi}i∈N con I(¯co) = I+ 1 . Podemos asumir sin perdida de generalidad que co({i})>0 para los jugadores i = 1, 2,..., I + 1 . Deniendo el juego (N, co) para ser correspondiente con N, a, {mi}i∈N donde a= ¯a, mj= ¯mj para todo j∈N\{I+ 1} y mI+1 = 0 . Entonces I(co) = I y f(co) = π(co) . Como co({k}) = ¯co({i})>0 para todo k=1, 2,...,I se sigue por (1.3) que ¯co(N)fk(¯co) = co(N)fk(co) = co(N)πk(co) . Por lo tanto, πk(co) = am2 ksX j∈N m2 j=c2 o({k}) co(N) entonces, usando inducción se tiene que: ¯co(N)fk(¯co) = co(N)πk(co) = co(N)c2 o({k}) co(N)=c2 o({k}) = ¯c2 o({k}). Se sigue que fk(¯co) = ¯c2 o({k}) ¯co(N)=πk(¯co) , también se tiene que co({j}) = ¯co({j}) = 0 para todo j = I+2,..., n-1, n por lo tanto por (1.4) fj(co)=0=πj(co) . Finalmente, la eciencia implica que: fI+1(¯co) = ¯co(N)−P j6=I+1 fk(¯co) = ¯co(N)−P j6=I+1 πk(¯co) = πI+1(¯co) . Lo cual concluye la demostración.  El coste mínimo de la coalición N , incluyendo coste de almacenaje, es igual a 2amN= 2arP i∈N m2 i . Denimos el juego de coste de inventario correspondiente (N, cv) para que sea el juego con el coste de la coalición S igual al mínimo coste que puedo obtener por si mismo, esto es, cv(S) = 2arP i∈S m2 iy cv(∅)=0 . Entonces, cv= 2co . Las propiedades de los juegos de coste de pedidos se mantienen en los juegos de coste de inventario, así que, estos juegos son cóncavos. Es más, basándonos en la regla proporcional para los juegos de coste de pedidos podemos encontrar una asignación del núcleo del juego de coste de inventario. En el juego de coste de pedidos, la regla proporcional divide el coste total de los pedidos de la coalición mayor entre los jugadores. En un juego de coste de inventario, tenemos que dividir coste de pedido y almacenaje. Denimos la regla de distribución r(cv) como sigue. La empresa i tiene que pagar el coste de pedido siguiendo la regla proporcional y sus costes de almacenaje privados, por lo tanto, ri(cv) = πi(co) + hib Qi/2 , donde b Qi es el tamaño óptimo de pedido para la empresa i cuando coopera con el resto de empresas. 10 CAPÍTULO 1. LOS JUEGOS DE INVENTARIO Teorema 1.3. Si (N, cv) es un juego de coste de inventario, entonces r(cv)∈C(cv) y se puede llegar a r(cv) a través de un PMAS. Demostración : Sea (N, cv) un juego de coste de inventario. Primero, tenemos que ver que πi(co) = hib Qi/2 . Resolviendo el problema de minimización del coste para la coalición N , tenemos que b Qi=di mN =2am2 i himN =2am2 i hirP j∈N m2 j . Entonces, el coste de almacenaje para la empresa i es hic Qi 2=hi 2 2am2 i hirP j∈N m2 j =am2 i rP j∈N m2 j =πi(co) para todo i∈N . Después tenemos que ver que r( cv ) es un elemento del núcleo. De la primera parte de esta demostración se sigue que, ri(cv) = 2πi(co) para todo i∈N . Es más, se tiene que: P i∈N 2πi(co)=2P i∈N πi(co)=2co(N) = cv(N) y para todo S⊂N, S 6=∅ , se tiene que: P i∈S 2πi(co) = 2P i∈S πi(co)≤2co(S) = cv(S) entonces, r(cv)∈C(cv) . Igual que en el caso de los juegos de coste de pedidos, se puede ver que es posible llegar a la regla r(cv) a través de un PMAS de la forma 2y donde y esta denido como se denió anteriormente.  1.4. Coste de almacenaje y pedido En esta sección consideraremos situaciones en las que la revelación de la información es total. Cada empresa i∈N revela su demanda di , su coste de almacenamiento hi , su numero óptimo de pedidos individuales mi y su tamaño de pedido individual óptimo ˙ Qi . Si asumimos que no existen limites en la capacidad de almacenamiento, el coste del transporte es 0 y el tiempo del transporte es determinista, entonces podemos considerar coordinación en los costes de almacenamiento. Si el miembro de una coalición tiene unos costes de almacenaje muy bajos, entonces la coalición puede reducir sus costes si guarda su inventario en el almacén de este miembro. 1.4. COSTE DE ALMACENAJE Y PEDIDO 11 El coste medio por unidad de tiempo de una coalición es la suma de los costes de almacenamiento y pedido. Igual que antes, el coste total se minimiza si todos los ciclos tienen la misma longitud, por lo tanto se tiene que Qi/di=Qj/dj para todo i, j ∈S . Sin pérdida de generalidad asumimos que la empresa 1 es miembro de la coalición S . Ahora podemos expresar Qi como función de Q1 para todo i∈S:Qi=diQ1/d1 . En cada ciclo la coalición realiza un pedido conjunto a un coste a , entonces el coste de pedido medio por unidad de tiempo es ad1/Q1 . Todos los bienes serán guardados en el almacén de la empresa con menor coste de almacenamiento. Denimos hS:= min i∈Shi . El nivel medio de inventario de la empresa i∈S es Qi/2 por unidad de tiempo y hSQi/2 denota el coste medio de almacenamiento por unidad de tiempo. Tenemos entonces que el coste medio por unidad de tiempo para las empresas en S es: ad1 Q1 +X i∈S hS Qi 2. Substituyendo Qi=diQ1/d1 se expresa el coste como una función de Q1 y tenemos: ad1 Q1 +X i∈S hS diQ1 2d1 . El mínimo del coste se alcanzará si: Q1=v u u t2ad2 1 hSP j∈S dj por lo tanto, Qi=di d1 Q1=v u u t2ad2 i hSP j∈S dj para todo i∈S . El coste mínimo por unidad de tiempo de la coalición S es s2ahSX i∈S di. Una situación de coste de almacenamiento esta descrita por la tupla N, a, {hi, di}i∈N . Dada una situación de coste de almacenaje, podemos denir el correspondiente juego de coste de almacenaje (N, ch) como el juego que asigna a la coalición su coste mínimo S⊂ N y ch(∅)=0 . Estos juegos son subaditivos, i.e., para todas las coaliciones S, T ⊆N tales que S∩T=∅ se tiene que ch(S) + ch(T)≥ch(S+T) . 12 CAPÍTULO 1. LOS JUEGOS DE INVENTARIO Como en el caso de los juegos de coste de almacenaje, podemos denir una regla para asignar el coste a la coalición mayor. La regla p(ch) divide el coste de la coalición mayor proporcionalmente a las demandas. Esto signica que para i∈N , pi(ch) = di P j∈N dj ch(N) = di P j∈N djs2ahNX j∈N dj. Teorema 1.4. Sea N, a, {hi, di}i∈N una situación de coste de almacenaje. Entonces la regla proporcional p(ch) es una asignación del núcleo del correspondiente juego de coste de almacenaje y se puede llegar a ella a través de un PMAS. Demostración : Por denición de la regla p(ch) tenemos que P i∈N pi(ch) = ch(N) . También se tiene que X i∈S pi(ch) = P i∈S di P j∈N djs2ahNX j∈N dj=X i∈S div u u t2ahN P j∈N dj ≤X i∈S div u u t2ahN P j∈S dj =s2ahNX j∈S dj≤s2ahSX j∈S dj=ch(S). Por lo tanto, p(ch)∈C(ch) . De forma similar a como hicimos en el párrafo anterior podemos denir un PMAS y tal que yiN =pi(ch) para todo i∈N .  Si un juego de coste es cóncavo entonces todos sus vectores marginales pertenecen al núcleo. Como los juegos de costes de almacenaje no son necesariamente cóncavos, podría haber vectores marginales que no están en el núcleo. Sin embargo, veremos que los juegos de coste de almacenaje son permutacionalmente cóncavos, lo que implica que al menos un vector marginal esta en el núcleo. Para demostrar la implicación anterior antes debemos denir el siguiente concepto, que fue introducido en Granot y Huberman(1982) y estudiado en Driessen(1988). Sea Π(N) un conjunto de permutaciones del conjunto de jugadores N . Para todo σ∈Π(N), σ(i) denota la posición del jugador i∈N en el pedido σ . Sea Pσ i el conjunto de jugadores que van antes que el jugador i con respecto al pedido σ . El conjunto ¯ Pσ i se obtiene de Pσ i al añadir el jugador i . Por lo tanto Pσ i={j∈N|σ(j)< σ(i)} y ¯ Pσ i={j∈N|σ(j)≤σ(i)}= Pσ i∪{i} . Deniendo para todo σ∈Π(N), σ(0) = 0 y Pσ 0=∅ . Se dice que un juego de coste (N, c) es permutacionalmente cóncavo respecto de un pedido σ∈Π(N) si satisface c¯ (Pσ i∪R)−c(¯ Pσ i)≥c(¯ Pσ j∪R)−c(¯ Pσ j) para todo i, j ∈N∪{0} y todo R⊂ N tal que σ(i)≤σ(j) y R⊂N\¯ Pσ j . Un juego se dice que es permutacionalmente cóncavo si existe un pedido σ∈Π(N) tal que el juego es permutacionlmente cóncavo respecto del pedido σ . El vector marginal xσ(c)∈RN respecto del pedido σ en 1.4. COSTE DE ALMACENAJE Y PEDIDO 13 el juego de coste (N, c) viene dado por xσ i(c) = c(¯ Pσ i)−c(Pσ i) para todo i∈N . Granot y Huberman(1982) mostraron que si el juego (N, c) es permutacionalmente cóncavo con respecto al pedido σ∈Π(N) entonces xσ(c)∈C(c) . En el siguiente teorema veremos que los juegos de coste de almacenaje son permtacionalmente cóncavos entonces a partir de este resultado, sabremos que existe al menos un vector marginal en el núcleo. Teorema 1.5. Los juegos de coste de almacenaje son permutacionalmente cóncavos. Demostración : Sea (N, ch) un juego de coste de almacenaje. Sin perdida de generalidad enumeramos los jugadores desde 1 hasta n , N={1,2, ..., n} ,de modo que el coste de almacenaje por unidad de tiempo de todos los jugadores forma una secuencia no decreciente, i.e., h1≤h2≤... ≤hn . Tomemos σ∈Π(N) tal que σ(i) = i para todo i∈N . Mostraremos que (N, ch) es permutacionalmente cóncavo respecto de este pedido y por lo tanto (N, ch) es permutacionalmente cóncavo. Sea i, j ∈N∪{0}, σ(i)≤σ(j)y R ⊂N\¯ Pσ j . Entonces i≤j ya que σ(k) = k para todo k∈N∪{0} . El juego (N, ¯c) donde ¯c(S) = rP j∈S dj para todo S⊂N , es un juego cóncavo, es decir, ¯c(S∪U)−¯c(S)≥¯c(T∪U)−¯c(T) para todo S⊂T⊂N y para todo U⊂N\T . Tomamos S=¯ Pσ i, T =¯ Pσ j, U =R . Entonces tenemos que S⊂T como σ(i)≤σ(j), U ⊂N\T y sX k∈¯ Pσ i∪R dk−sX k∈¯ Pσ i dk≥v u u tX k∈¯ Pσ j∪R dk−v u u tX k∈¯ Pσ j dk. (1.5) Tenemos que ver que ch¯ (Pσ i∪R)−ch(¯ Pσ i)≥ch(¯ Pσ j∪R)−ch(¯ Pσ j) . Distinguimos tres casos: Caso 1 : i=0 , j=0 entonces ¯ Pσ i=¯ Pσ j=∅ y ch¯ (Pσ i∪R)−ch(¯ Pσ i) = ch(R)−ch(∅) = ch(¯ Pσ j∪R)−ch(¯ Pσ j). Caso 2 : i=0 , j>0 entonces ¯ Pσ i=∅ y ¯ Pσ j={1,2, ..., j} . Como 1∈¯ Pσ j y 1/∈R tenemos que h¯ Pσ j=h¯ Pσ j∪R=h1y hR≥h1 . Multiplicando ambos lados de (1.5) por √2ahR tenemos s2ahRX k∈R dk≥v u u t2ahRX k∈¯ Pσ j∪R dk−v u u t2ahRX k∈¯ Pσ j dk ≥v u u t2ah1X k∈¯ Pσ j∪R dk−v u u t2ah1X k∈¯ Pσ j dk y esto es igual a ch(R)−ch(∅)≥ch(¯ Pσ j∪R)−ch(¯ Pσ j) . 20 CAPÍTULO 2. LOS SISTEMAS DE INVENTARIO Y TRANSPORTE C(S, Qi) = (a+aS)di Qi +X j∈S hj Qj 2 =(a+aS)di Qi +Qi 2diX j∈S hjdj. El tamaño óptimo del pedido del agente i∈S es ˆ Qi=v u u t2(a+aS)d2 i P j∈S hjdj . El número óptimo de pedidos por unidad de timepo es ˆms=di Qi =v u u tP j∈S hjdj 2(a+aS), y el coste total medio óptimo por unidad de tiempo es C(S, ˆ Qi) = s2(a+aS)X j∈S hjdj= 2(a+aS) ˆms. Estos cálculos nos permiten asociar un juego de costes a cada sistema de transporte de inventario. Tenemos que para cada coalición S⊆N , c(S) es el coste mínimo de coste del proyecto que cubre las necesidades de los agentes de S . Para un sistema de transporte de inventarios (N, I) = N, a, {ai, di, hi}i∈N , se puede construir el juego de costes (N, c) que viene dado por: c(S) := C(S, ˆ Qi) = r2(a+aS)P j∈S hjdj= 2(a+aS) ˆms . Entonces se dice que el juego de costes (N, c) es un juego de transporte de inventario si existe un sistema de transporte de inventario (N, I) cuyo juego de coste asociado es (N, c) . Un juego de inventario es cualquier juego de coste (N, c) que satisfaga que para todo S⊂N , c(S)≥0 y , además, c(S)2=P i∈S c(i)2 . Un juego de coste es subaditivo si nunca es benecioso que una coalición se divida en varias coaliciones más pequeñas. Formalmente, para cada S, T ⊂N tal que S∩T=∅ , se tiene que c(S) + c(T)≥c(S∪T) . Este concepto nos ayudara a responder a la primera de las preguntas que nos planteábamos ya que cuando el juego de coste correspondiente sea subaditivo será razonable que se forme la gran coalición N . El siguiente teorema proporciona una condición necesaria y suciente para la subaditividad de un juego de transporte de inventario. 2.2. SISTEMAS DE TRANSPORTE DE INVENTARIO 21 Teorema 2.1. Consideremos un juego de transporte de inventario (N, c) asociado a un sistema de transporte de inventario (N, I) = N, a, {ai, di, hi}i∈N . (N, c) es subaditivo sí y solo sí ˆmt≥1 2 aT−aS a+aT ˆmS para todo S, T ⊂N tal que S∩T=∅ y aS≤aT . Demostración : Sea S, T ⊂N tal que S∩T=∅ y aS≤aT . Tenemos que probar que c(S) + c(T)≥c(S∪T)⇐⇒ ˆmt≥1 2 aT−aS a+aT ˆmS. Como c(S)≥0 , c(S) + c(T)≥c(S∪T)⇐⇒ c(S)2+c(T)2+ 2c(S)c(T)≥c(S∪T)2 ⇐⇒ 2c(S)c(T)≥c(S∪T)2−c(S)2−c(T)2. Pero, c(S∪T)2−c(S)2−c(T)2= 2(a+aS∪T)X j∈S∪T hjdj−2(a+aS)X j∈S hjdj−2(a+aT)X j∈T hjdj = 2(a+aT)X j∈T hjdj−2(a+aS)X j∈S hjdj = 2(aT−aS)X j∈S hjdj. Entonces, c(S) + c(T)≥c(S∪T)⇐⇒ c(S)c(T)≥(aT−aS)P j∈S hjdj . Reescribiendo el lado derecho de la equivalencia tenemos que 4(a+aS)(a+aT) ˆmsˆmT≥(aT−aS)2(a+aS) ˆm2 s⇐⇒ ˆmt≥1 2 aT−aS a+aT ˆmS.  Más o menos, esta condición quiere decir que la cooperación es beneciosa cuando los agentes remotos no son clientes raros en el sentido de que sus números óptimos de pedidos individuales no son muy pequeños en comparación con el numero óptimo de pedidos individuales de otros agentes. En la siguiente sección responderemos a la segunda cuestión: si tenemos un sistema de transporte de inventarios cuyo juego asociado (N, c) es subaditivo, i.e., un sistema de transporte de inventario en el cual es razonable que los agentes de N formen una coalición, ¾Como debería asignarse c(N) entre los miembros de N ? 22 CAPÍTULO 2. LOS SISTEMAS DE INVENTARIO Y TRANSPORTE 2.3. Una regla de asignación de costes Empezaremos esta sección con un resultado del núcleo de un juego de transporte de inventario. Tomemos un juego de transporte de inventario (N, c) y asumamos que los agentes de N forman una coalición para los pedidos. Al igual que con los juegos de coste de pedidos, queremos asignar c(N) a los miembros de N sería conveniente que la asignación pertenezca al núcleo de (N, c) que como ya hemos visto para juegos de coste de pedidos viene dado por: C(N, c) = x∈RN|P i∈N xi=c(N),Pxi i∈S≤c(S)∀S⊂N . Para realizar la demostración del siguiente resultado relacionado con el carácter no vacío de juegos de inventario subaditivos, es necesario introducir algunos conceptos previamente. Sea (N, c) un juego de transporte de inventario subaditivo asociado a un sistema de transporte de inventarios (N, I) = N, a, {ai, di, hi}i∈N . Diremos que i∈N es un agente extremo de (N, I) si ai=aN , i.e., si la distancia al proveedor es mayor o igual que la distancia del proveedor al resto de agentes. Denotaremos a Π(N) un conjunto de permutaciones del conjunto de jugadores N . Para todo σ∈Π(N) , σ(i) denota la posición del jugador i∈N en el pedido σ . Sea Pσ i el conjunto de jugadores que van antes que el jugador i con respecto al pedido σ , es decir, Pσ i={j∈N|σ(j)< σ(i)} . Denotaremos por σ−1 la inversa de σ . El vector marginal respecto del pedido σ en el juego de coste (N, c) viene dado por mσ(N, c) = (mσ i(N, c))i∈N donde mσ i(N, c) = c(Pσ i∪ {i})−c(Pσ i) para todo i∈N . Para cada vector marginal mσ(N, c) se tiene que P i∈N mσ i(N, c) = c(N) . Entonces cada vector marginal de (N, c) es una asignación de c(N) que asigna a cada i su contribución a su predecesor siguiendo un orden particular. Teorema 2.2. Consideremos un juego de transporte de inventario subaditivo (N, c) . Entonces (N, c) es no vacío. Demostración Esta demostración consiste en probar que mσ(N, c) es un vector marginal y su orden σ satisface que σ−1 (1) es un agente extremo de (N, I) , y por lo tanto mσ(N, c) pertenece al núcleo de (N, c) . Tomemos un juego de transporte de inventario (N, c) asociado a un sistema de transporte de inventarios (N, I) = N, a, {ai, di, hi}i∈N . Tomemos ahora un vector marginal mσ(N, c) tal que σ satisface que σ−1 (1) es un agente extremo de (N, I) . Tenemos que probar que mσ(N, c) pertenece al núcleo de (N, c) . Para hacer esto, es suciente ver que para cada coalición no vacía S⊂N , se tiene que P i∈S mσ i(N, c)≤c(S) . Distinguiremos dos casos : (a) S contiene al agente extremo σ−1 (1). Entonces 2.3. UNA REGLA DE ASIGNACIÓN DE COSTES 23 X i∈S mσ i(N, c) = c(σ−1(1)) + X j∈S\{σ−1(1)} c(Pσ j∪{j})−c(Pσ j) =c(σ−1(1)) + X j∈S\{σ−1(1)} s2(a+aN)X i∈Pσ j∪{j} hidi−s2(a+aN)X i∈Pσ j hidi  =X j∈Sp2(a+aN) sX i∈Pσ j∪{j} hidi−sX i∈Pσ j hidi  ≤X j∈Sp2(a+aN) sX i∈(Pσ j∪{j})∩S hidi−sX i∈Pσ j∩S hidi =c(S) donde la desigualdad implica que √x+y−√x es decreciente en x para todo y∈[0,∞) (b) S no contiene al agente extremo σ−1 (1). En este caso denotaremos ¯ S=S∪σ−1(1) .Usando el mismo razonamiento que en (a), tenemos que P i∈¯ S mσ i(N, c)≤c(¯ S) . Ahora teniendo en cuenta que mσ σ−1(1)(N, c) = c(σ−1(1)) y que c es subaditivo, se tiene que P i∈S mσ i(N, c) + c(σ−1(1)) = P i∈¯ S mσ i(N, c)≤c(¯ S)≤c(S) + c(σ−1(1)) lo que implica que P i∈S mσ i(N, c)≤c(S). Por la demostración anterior sabemos que todos los vectores marginales son asignaciones en el núcleo, usaremos esto para denir nuestra regla de asignación. Primero, veamos a lo que nos referimos por regla de asignación. Nuestro objetivo es proponer para cada sistema de transporte de inventario cuyo juego asociado (N, c) es subaditivo una asignación de c(N) a través de los agentes de N . Una regla de asignación es un mecanismo con el que logramos dicho objetivo. Formalmente, una regla de asignación para un sistema de transporte de inventarios es una aplicación Φ que se asocia a cada sistema de transporte de inventario (N, I) , con un juego de costes asociado (N, c) un vector Φ(N, I) = (Φi(N, I))i∈N que satisface que P i∈N Φi(N, I) = c(N) . Ahora deniremos una regla de asignación que propone siempre asignaciones en el núcleo del correspondiente juego de transporte de inventario cuando este es subaditivo. Tomemos un sistema de transporte de inventario (N, I) y consideremos todos los pedidos σ∈Π(N) que inviertan el orden dado por las distancias de los agentes al proveedor, i.e., todos los pedidos σ∈Π(N) tales 24 CAPÍTULO 2. LOS SISTEMAS DE INVENTARIO Y TRANSPORTE que σ(i)≤σ(j) implica que ai es mayor o igual que ai (siendo ai , aj las distancias de i, j al proveedor respectivamente) para todo i, j ∈N . Denotamos por Π(N, I) al conjuntos de estos pedidos en (N, I) . Deniremos nuestra regla de asignación como la regla que propone para cada sistema de transporte de inventario (N, I) la media de los vectores marginales asociados a los pedidos de Π(N, I) . A esta regla la llamaremos la regla de la línea y su denición formal es: La regla de la línea es la regla de asignación que asocia a cada sistema de transporte de inventarios (N, I) , con juego de costes asociado (N, c) , la asignación L(N, I) = (Li(N, I)i∈N) dada por Li(N, I) = 1 Π(N, I)X σ∈Π(N,I) mσ i(N, c) (2.1) para todo i∈N . Obsérvese que todos los pedidos σ∈Π(N, I) satisfacen que σ−1(1) es un agente extremo de (N, I) , y entonces mσ(N, c)∈C(N, c) cuando (N, c) es un juego subaditivo. Como C(N, c) es un conjunto convexo, entonces L(N, I)∈C(N, c) cuando (N, c) es subaditivo. Ahora veremos dos propiedades que están relacionas con la regla de la línea, en el sentido de que la caracterizan dentro del conjunto de posibles reglas para sistema de transporte de inventarios. Las dos propiedades se reeren a las distancias entre los agentes y el proveedor. Estas distancias son la característica que distingue a este modelo de otros modelos de inventario centralizado. La primera propiedad de equidad que dice que si dos agentes están a la misma distancia del proveedor entonces tiene que ser tratados de la misma manera. Tratamiento equilibrado para agentes igualmente distantes (BT) . Una regla de asignación φ para sistemas de transporte de inventario satisface BT si se verica lo siguiente. Sea (N, I) = N, a, {ai, di, hi}i∈N un sistema de transporte de inventario y sean j, k ∈N con aj=ak . Para cada l∈N , denotemos por (N\{l}, I) el sistema de transporte de inventario N\{l}, a, {ai, di, hi}i∈N\{l} . Entonces: φj(N, I)−φj(N\{k}, I) = φk(N, I)−φk(N\{j}, I) . La segunda propiedad, Participación Gratuita de Agentes Sin Coste (FP), dice que si se ha formado un grupo y un conjunto de nuevos agentes entra al grupo, esta incorporación no afectara la asignación de los agentes en el grupo original si los nuevos agentes están más cerca del proveedor que todos los demás agentes. La idea bajo esta propiedad es que estos nuevos agentes se pueden considerar como agentes con coste cero, porque no producen ningún cambio ni al grupo original o ni a ningún subgrupo de esta, en el sentido de que la ruta de transporte se mantiene sin variación después de su incorporación. Procedemos a dar una denición más rigurosa de la propiedad. 2.3. UNA REGLA DE ASIGNACIÓN DE COSTES 25 Participación Gratuita de Agentes Sin Coste (FP). Una regla de asignación φ para un sistema de transporte de inventario satisface FP si se verica la siguiente condición. Sea (N∪N0, IN∪N0) = N∪N0, a, {ai, di, hi}i∈N∪N0 un sistema de transporte de inventario tal que N∩N0=∅ y aN0< ai para todo i∈N . Denotemos por (N, I) el sistema de transporte de inventario N, a, {ai, di, hi}i∈N . Entonces: φj(N∪N0, IN∪N0) = φj(N, I) (2.2) para todo j∈N Estas dos propiedades caracterizan a la regla de la línea. Como dice el siguiente teorema: Teorema 2.3. La regla de la linea es la unica regla para sistemas de transporte de inventario que satisface BF y FP Demostración: Para más detalles, ver el Apéndice en Fiestras-Janeiro et al. (2011). 26 CAPÍTULO 2. LOS SISTEMAS DE INVENTARIO Y TRANSPORTE Capítulo 3 Los problemas de inventario multi-producto 3.1. Introducción El análisis del comportamiento cooperativo en situaciones de inventario ha sido estudiado durante los últimos años. Formalmente, el inventario es la cantidad de bienes almacenados por una empresa en un instante de tiempo. En términos económicos, representa una inversión para la compra y mantenimiento del producto en stock. Cada empresa debe tener el nivel de inventario adecuado de producto para satisfacer las necesidades de sus clientes y, por lo tanto, debe manejarse de manera óptima. Los modelos de problemas de inventario se aplican con el objetivo de mantener el nivel de inventario óptimo y así reducir los costes. Los modelos más básicos de problemas de inventario, la cantidad económica de pedido (EOQ) y el lote económico de producción (EPQ) aparecen en Meca et al. (2003). Sin embargo, cuando se consideran los costes de transporte de los pedidos surgen nuevos sistemas de inventario. Por ejemplo en Dror et al. (1985) usan líneas de transporte comunes y en Fiestras-Janeiro et al. (2011) se incluyen los costes de transporte por pedido nuevo en un modelo básico EOQ. En este capítulo se exponen los resultados que aparecen en SaavedraNieves (2020) que expanden el modelo descrito en Fiestras-Janeiro et al. (2011) a una situación con varios artículos. En el capítulo anterior describimos sistemas de inventario en los cuales múltiples agentes realizan un pedido conjunto de un único articulo usando una política EOQ. En ese caso el coste jo de pedido se divide en dos partes, una que es común para todos los agentes involucrados y otra que depende de la distancia del proveedor al agente. Una suposición principal en el capítulo anterior era que los agentes están situados 27 28 CAPÍTULO 3. LOS PROBLEMAS DE INVENTARIO MULTI-PRODUCTO a lo largo de una ruta lineal. Sin embargo, esta suposición no es realista para la mayoría de las situaciones en el mundo real. Para rutas circulares o cuando los agentes y el proveedor están situados siguiendo un gráco irregular, la idea de linealidad de la ruta introducida en el capítulo anterior no tiene sentido. En particular, consideraremos la existencia de una función general para determinar el coste de transporte de un nuevo pedido. En este capítulo trataremos una variación del problema presentado en el capítulo anterior. Primero, abandonamos el enfoque de la variación de los costes de transporte en pedidos nuevos. Cada agente tiene una demanda determinista, un almacén con costes de almacenaje, los agentes no se pueden quedar sin inventario y el tiempo de espera es constante. Ahora analizaremos una situación en la cual los costes de transporte vienen dados por una función general. Por otro lado, parece natural que los agentes tengan un único proveedor para todos sus artículos. Esto no cambia substancialmente el análisis de este tipo de problemas, aunque abre la puerta a la generalización de modelos de inventario previamente mencionados bajo este nuevo enfoque. El capítulo se estructura como sigue. La segunda sección describe el sistema EOQ multiitem con coste de transporte generales. La tercera sección establece la política óptima de inventario cuando los agentes cooperan. Estudiamos los costes asociados a este problema en la cuarta sección. Las secciones quinta se centra en como se comparten los costes en este escenario y en la sexta analizaremos los escenarios en los cuales se debe formar una coalición. 3.2. Problemas EOQ multi-item de inventario Un sistema EOQ multi-item con costes de transporte generales es un modelo multiagente de inventario donde cada agente enfrenta un problema de revisión continua de inventario que también involucra los siguientes supuestos: Cada agente tiene una demanda determinista y lineal de varios artículos. Los pedidos se realizan cuando el nivel de inventario es cero, y quedarse sin inventario no está permitido. Cada agente guarda sus pedidos en un almacén de capacidad ilimitada con un coste extra. Todos los agentes están ubicados en una ruta que no es necesariamente lineal. De hecho, el coste por realizar un nuevo pedido tiene dos componentes: una ja y otra variable, que depende de la distancia del agente al proveedor. 3.2. PROBLEMAS EOQ MULTI-ITEM DE INVENTARIO 29 Cada agente tiene que satisfacer la demanda de un conjunto M=1,...,m de m artículos diferentes. Con este objetivo los pedidos nuevos están compuestos de varios artículos que tienen un único proveedor. Asumimos como en los capítulos anteriores que el tiempo de espera es constante (o incluso cero). Denotamos al conjunto nito de agentes por N . Adicionalmente asociamos los siguientes parámetros a cada agente i∈N : a > 0 , el coste jo de realizar un pedido. hi>0 , el coste de almacenaje por artículo almacenado. dki >0 , la demanda del artículo k∈M que necesita el agente i . pki >0 , el coste por unidad del artículo k∈M para el agente i . Diferenciaremos dos componentes en los costes de pedido cuando un nuevo pedido se realiza. Además de considerar un coste jo a > 0 por cada pedido, también debemos incluir una segunda componente que se reera a un coste variable. El proveedor cobra una tarifa igual a a+A(S) cuando una coalición S⊂N realiza un pedido. Como en Saavedra-Nieves et al. (2018) asumimos también la existencia de una aplicación A, de 2N a R . Esta aplicación asigna a cada S⊆N el coste A(S)≥0 . Denotamos a esta clase de problemas de inventario por la tupla nN, M, a, A, {hi}i∈N,{dki}k∈M,i∈N,{pki}k∈M,i∈No . Cada agente i∈N tiene que satisfacer las demandas de los artículos a tiempo. Con este objetivo, el agente i almacena pedidos por valor de Qi>0 . Utilizando el precio de una unidad k para el agente i , consideramos: dki >0 , el valor de la demanda del producto k∈M para el agente i . Di>0 , el valor total de la demanda para el agente i . Qki >0 , el valor del producto k∈M para el agente i . Qi>0 , el valor total del pedido para el agente i . Analizaremos esta clase de problemas en términos del valor de la cantidad de cada artículo en un pedido óptimo. Análogamente a como se hizo en el modelo EOQ básico, denimos un ciclo como el intervalo de tiempo entre dos pedidos consecutivos, i.e. Qi/Di . Además, el valor de mi= Di/Qi=dki/Qki denota el número de pedidos óptimo por unidad de tiempo. Entonces, el coste medido de pedido por unidad de tiempo viene dado por Di/Qi(a+A(i)) . Ya que el nivel medio de inventario es Qi/2 , el coste medio de almacenaje es hiQi/2 . Por lo tanto, el coste medio por unidad de tiempo para el agente i es: 36 CAPÍTULO 3. LOS PROBLEMAS DE INVENTARIO MULTI-PRODUCTO Esta condición es equivalente a a( ˆmNPj∈Sλj Pj∈Nλj−ˆmS) + A(N)Pj∈Sλj Pj∈Nλj−A(S) ˆmS≤0. Esta desigualdad se satisface siempre que A sea monótona y como ˆmN ˆmS≤ˆmN ˆmS A(N) A(S)≤Pj∈Nλj Pj∈Sλj para todo S⊆N se tiene que ˆmN ˆmS A(N) A(S)≤Pj∈Nλj Pj∈Sλj .  El siguiente ejemplo ilustra el comportamiento de RPλ(l) en un sistema particular l . Ejemplo 3.5. Sea l=nN, M, a, A, {hi}i∈N,{dki}k∈M,i∈N,{pki}k∈M,i∈No un problema EOQ multi-item con costes de transporte generales dado por: N={1,2,3} , M={1,2,3} , a= 0.013 y la función de coste A viene dada en la tabla 3.3. D =(1.351, 1.387, 2.385) y h=(0.011, 0.138, 0.239). S {1} {2} {3} {1,2} {1,3} {2,3} N A(S) 1.6 1.6 1.7 1.8 1.7 1.7 2.0 Tabla 3.3: Función A. S {1} {2} {3} {1,2} {1,3} {2,3} N cl(S) 0.219 0.786 1.397 0.865 1.416 1.615 1.768 Tabla 3.4: El juego de costes (N, cl) . El juego de costes (N, cl) asociado a l está en la Tabla 3.4. La condición del teorema anterior se cumple para l y, por ejemplo, para λ∈RN tal que λi =cl({i}) para todo i∈N . Se comprueba fácilmente que RPλ(l) = (0.161, 0.578, 1.028). 3.6. ESTRUCTURA DE COALICIONES DE PEDIDO BENEFICIOSAS 37 3.6. Estructura de coaliciones de pedido beneciosas Aunque normalmente analicemos la formación de la coalición N , es fácil comprobar que no siempre es beneciosa la cooperación. Por lo tanto, nos surge una nueva pregunta, ¾qué coaliciones se deben formar en un problema como los anteriores? Para dar una respuesta usaremos las ideas de Elomri et al. (2012) para problemas EOQ básicos con costes de transporte aditivos. Dado un juego de costes general (N, c) , la noción de benecio de una coalición S⊆N se redene en términos del cociente c(S) Pi∈Sc(i) . En este sentido, se dice que una coalición es la coalición de pedido más beneciosa si minimiza el ratio anterior en el conjunto de posibles coaliciones de N . La tarea principal consistirá en determinar una estructura de pedido, i.e. una partición de N compuesta por las coaliciones de pedido más beneciosas. Sea l=nN, M, a, A, {hi}i∈N,{dki}k∈M,i∈N,{pki}k∈M,i∈No y (N, cl) un problema EOQ multi-item con costes de transporte generales y sea P una estructura de pedido para N . Entonces RPλ(l) con λ∈RN y λi=cl(i) para todo i∈N se dene formalmente, para cada i∈Sk∈P , por RPλ(l) = cl(i) Pj∈Skcl(j)cl(Sk). (3.2) Esta regla es fácil de obtener y tiene una interpretación muy natural. En Elomri et al. (2012) se demuestra que la restricción de RPλ(l) a cada subjuego inducido por Sk∈P pertenece al núcleo si λi=cl(i) . Adaptamos el procedimiento de Elomri et al. (2012) para obtener una estructura de pedido como la ya mencionada. Escoge de forma iterativa, la coalición de pedido más beneciosa de los agentes no asignados a ninguna clase anteriormente. Algoritmo 3.6. Sea l=nN, M, a, A, {hi}i∈N,{dki}k∈M,i∈N,{pki}k∈M,i∈No un problema EOQ multi-item con costes de transporte generales. Sea (N, cl) el juego de costes asociado: 1. k= 0, P =∅ . 2. k=k+ 1 . 3. determinar Sk⊆N\S S∈P S tal que cl(Sk) Pi∈Skcl(i) =min T⊆N\S S∈P Scl(T) Pi∈Tcl(i). Si Sk=N\S S∈P S este procedimiento termina, de lo contrario, se obtiene Sk⊆ N\S S∈C S y entonces tomamos P=P∪Sk . 38 CAPÍTULO 3. LOS PROBLEMAS DE INVENTARIO MULTI-PRODUCTO 4. ir al paso 2 a no ser que N\S S∈P S=∅ . El algoritmo que acabamos de describir identica una estructura de pedidos P para el problema de inventario multi-item del primer ejemplo de esta sección: Ejemplo 3.7. Consideramos el problema EOQ multi-item con costes de transporte generales del primer ejemplo de esta sección. Tabla 3.5 describe el juego de costes correspondiente (N, cl) y los ratios asociados a cada posible coalición. Entonces, P={S1, S2}={{1,2},{3}} aplicando el algoritmo que acabamos de denir. La propuesta de la regla RPλ para l con λ∈RN y λi=cl({i}) para todo i∈N , es RPλ(l) =(2.283, 2.512, 11.177). S {1} {2} {3} {1,2} {1,3} {2,3} N cl(S) 2.285 2.515 11.177 4.795 13.496 13.720 16.029 Ratio 1 1 1 0.999 1.003 1.002 1.003 Tabla 3.5: El juego de costes (N, cl) . Aunque RPλ(l) nos proporciona asignaciones estables para cada S∈P no es eciente para N ya que cl({1,2}) + cl({3}) = 4.795 +11.177 <16.029 =cl(N) . Mas aún, aseguramos benecios cuando los jugadores en N cooperan siguiendo P en este problema. Capítulo 4 Conclusión El modelo introducido en el primer capítulo se conoce como modelo básico de inventario ya que forma la base de una gran variedad de modelos de inventario diferentes. El modelo básico de inventario es un modelo simple y algunas extensiones harían que fuera más realista. Algunas posibles extensiones ya tratadas en la literatura considerarían la inclusión del coste de compra por cada unidad del bien, un tiempo de entrega estocástico, una cantidad nita para los pedidos, costes de pedido individuales, permitir que las empresas se queden sin stock, descuentos por cantidades mayores en los pedidos. Discutiremos brevemente algunas de estas extensiones. Un coste de compra c por unidad del bien implica que las empresas deberían pagar a parte del coste jo por pedido un coste variable cQ por un pedido de Q unidades. Por unidad de tiempo esto implica un coste extra cQ ·d/Q =cd , un coste constante, que no inuenciara a la cantidad óptima de pedido ni a la longitud óptima del ciclo. Solo aumentará el coste, por lo tanto, no es realmente una extensión. Los descuentos por cantidad se pueden denir de dos maneras. Primero podemos pensar en descuentos por cantidad para todas las unidades compradas, la otra forma de verlo es descuentos por cantidad crecientes, por ejemplo, las primeras 100 unidades cuestan 20 ¿ y las siguientes 100 cuestan 15 ¿ . En el caso de una demanda no determinista podremos pensar que D es la demanda estocástica de la empresa. Los juegos que surjan de esta situación pueden que estén dentro de la clase de juegos de inventario centralizados, donde se consideran valores esperados. De lo contrario estarán dentro de la clase de los juegos cooperativos TU con pagos estocásticos. El segundo capítulo proporciona una nueva contribución a los problemas de inventario centralizados. Examina un problema de asignación de costes en un sistema de transporte de inventario con un único artículo, un único proveedor y múltiples agentes que realizan un pedido conjunto usando una política EOQ con una estructura de coste especica. El 39 40 CAPÍTULO 4. CONCLUSIÓN coste de pedido conjunto es la suma de un coste jo y un coste de transporte que es el máximo de los costes de transporte individuales. Este problema corresponde con la situación en la que todos los agentes están ubicados en la misma ruta de la línea. Para estos sistemas de transporte de inventarios, la cooperación no es siempre razonable, pero si imponemos una condición simple que compara el numero óptimo de pedidos para cada par disjunto de coaliciones, podemos asegurar que la cooperación es razonable. Es más, cuando la coalición es razonable, hemos probado que siempre podemos encontrar asignaciones estables. Finalmente, hemos introducido la regla de la línea, una regla de asignación que proporciona asignaciones estables cuando la coalición es razonable. En el siguiente capítulo abordaremos el problema de asignación de costes que surge de un sistema de inventario con múltiples artículos y varios agentes que hacen pedidos conjuntos siguiendo una política EOQ. El tercer capítulo describe un problema EOQ multi-item con costes de transporte generales. Se introduce como generalización del modelo EOQ del segundo capítulo y de Fiestras-Janeiro et al. (2011). Analizamos un problema de asignación de costes en un sistema de inventario con múltiples artículos y costes de transporte generales, un único proveedor y varios agentes que realizan pedidos conjuntos siguiendo una política EOQ. La principal novedad con respecto al modelo del capítulo anterior es la consideración de una estructura particular para los costes, compuesta de dos componentes. La primera de las cuales es un coste jo por cada pedido y la segunda es una variable que viene dada por una función general. En particular, asumimos que la segunda componente está relacionada con los costes de transporte de cada nuevo pedido desde el proveedor. Para justicar esta hipótesis hemos lidiado con situaciones en las cuales los agentes no están todos situados necesariamente en una ruta lineal. Hemos comprobado que la cooperación de los agentes de N no es necesariamente beneciosa en esta clase de problemas, pero impusimos unas condiciones básicas bajo las cuales la cooperación es razonable. Desde un enfoque basado en la teoría de juegos, somos capaces de proporcionar algunas condiciones bajo las cuales el núcleo del correspondiente juego es no vacío. En particular, introducimos la regla λ -proporcional, una asignación que proporciona asignaciones estables bajo algunas condiciones. Todos estos resultados se pueden aplicar en muchas situaciones de inventario en el mundo real como, entre muchas otras, en operaciones de franquicias. Bibliografía [1] Driessen, Th. (1988). On cores of subconvex games and permutationally convex games. Methods of Operations Research. 60(1988), 313323. [2] Dror, M., Ball, M. & Golden, B. (1985). A computational comparison of algorithms for the inventory routing problem. Ann. Oper. Res.. 4(1), 123 [3] Elomri, A., Ghaari, A., Jemai, Z. & Dallery, Y. (2012). Coalition formation and cost allocation for joint replenishment systems. Prod. Oper. Manage., 21(6), 10151027. [4] Fiestras-Janeiro, M.G., García-Jurado, I., Meca-Martinez, A. & Mosquera, M.A. (2011). Cost allocation in inventory transportation systems. Sociedad de Estadística e Investigación Operativa 2011. [5] Granot, D. & Huberman, G. (1982). The relationship between convex games and minimum cost spanning tree games: a case for permutationally convex games. SIAM Journal of Algebra and Discrete Methods, 3(1982), 288292. [6] Hadley, G. & Whitin, T.M. (1963). Analysis of inventory systems, Prentice-Hall, Englewood clis, N.J. [7] Meca-Martinez, A., García-Jurado, I. & Borm, P. (2003). Cooperation and competition in inventory games. Math. Methods Oper. Res., 57(3), 481493. [8] Meca, A., Timmer, J., García-Jurado, I., & Borm, P. (2004). Inventory games. European Journal of Operational Research, 156(1), 127-139. [9] Saavedra-Nieves, A. (2020). A multi-agent inventory problem with general transportation costs. Operations Research Letters, 48(1), 86-92. [10] Saavedra-Nieves, A., García-Jurado, I. & Fiestras-Janeiro, M.G. (2018). Placing joint orders when holding costs are negligible and shortages are not allowed in: D. Mueller, R. Trost (Eds.). Game theory in management accounting. Contributions to Management Science. Springer, 2018, 349360. 41 42 BIBLIOGRAFÍA [11] Shapley, L.S. & Shubik, M. (1967). Ownership and the production function. Journal of Economics, 8 (1967), 88111. [12] Sprumont, Y. (1990). Population monotonic allocation schemes for cooperative games with transferable utility. Games and Economic Behavior, 2 (1990), 378394. [13] Young, H.P. (1985). Monotonic solutions of cooperative games. International Journal of Game Theory, 14 (1985), 6572. [14] Zipkin, P. (2000). Foundations of inventory management. McGraw Hill, New York.