Problema de transport

Un problema de transport és, en matemàtiques i economia, un cas particular de problema de programació llineal en el qual es deu minimisar el cost de l'abastiment a una série de punts de demanda a partir d'un grup de punts d'oferta —possiblement de distint número—, tenint en conte els distints preus d'enviament de cada punt d'oferta a cada punt de demanda.

Plantejament

Es disponen $n\in \mathbb{N}$ punts d'oferta o factories en una producció determinada (representada per mig d'un vector, F) i $m\in \mathbb{N}$ punts de demanda o mercats de demanda determinada (vector M):

$F\in {ℝ}^n;F=(F_1,F_2,F_3,\cdots ,F_n)$

$M\in {ℝ}^m;M=(M_1,M_2,M_3,\cdots ,M_m)$

Ademés es dispon com a senya d'una matriu de preus, C, de manera que $C_{ij}$ és el preu d'enviament per unitat des de la factoria $F_i$ al mercat $M_j$:

$C\in {ℳ}_{n\times m}(ℝ)$

L'objectiu és calcular una nova matriu, X, de manera que $X_{ij}$ siga el número d'unitats que s'envien de la factoria $F_i$ al mercat $M_j$.

$X\in {ℳ}_{n\times m}(ℝ)$

En estes senyes podem formular les condicions que s'han de complir:

$\sum _{i=1}^n{X}_{ij}\ge M_j\mathrm{\forall }j\in \mathbb{N}/1\le j\le m$

$\sum _{j=1}^m{X}_{ij}\le F_i\mathrm{\forall }i\in \mathbb{N}/1\le i\le n$

$X_{ij}\ge 0(i,j\in \mathbb{N};1\le i\le n;1\le j\le m)$

El preu total a pagar pel transport, $C_T$, que s'ha de minimisar, es determinarà per la suma dels productes del preu de cada unitat pel cost d'enviament per unitat de cada fàbrica a cada mercat:

$C_T=\sum _{i=1}^n\sum _{j=1}^m{X}_{ij}\cdot C_{ij}$

$\min C_T$

Problemes equilibrats

Es diu que el problema està equilibrat quan es complix que:

$\sum _{i=1}^n{F}_i=\sum _{j=1}^m{M}_j$

(o, abreviadament, $\sum F=\sum M$, és dir, l'oferta total és igual a la demanda total).

En cas que $\sum F>\sum M$ (Oferta total siga major a la demanda total) s'incorporaria un centre de consum adicional al problema, el centre de consum artificial, $M_a$, de manera que la seua demanda siga l'excedent ( $M_a=\sum F-\sum M$) i el cost d'enviament a este mercat siga nul:

$C_{ia}=0\mathrm{\forall }i\in \mathbb{N}/1\le i\le n$.

En cas que $\sum F<\sum M$ (Demanda total major a l'oferta total) s'incorporaria una factoria adicional al problema, la factoria artificial, $M_b$, de manera que la seua oferta siga l'excedent ($M_b=\sum M-\sum F$ ) i el cost d'enviament d'esta factoria siga nul:

$C_{bj}=0\mathrm{\forall }j\in \mathbb{N}/1\le j\le m$.

Representació Gràfica del Problema de Transport

Es mostra la presentació gràfica del problema de transport a on:

Representació Gràfica del Problema de Transport

• Nodos: Factories i Mercats. A cada nodo se li associa una restricció en la seua oferta Fi i demanda Mj.
• Arcs: Ruta a seguir per a transportar les mercaderies. A cada arc se li associa una variable de decisió $X_{i,j}$.

Taula de Transport

L'estructura del problema de transport permet una representació compacta del problema utilisant el format de taula de transport com es mostra a continuació.

	Mercat 1	Mercat 2		Mercat j		Mercat m
Factoria 1	cost(1, 1)	cost(1, 2)	...	cost (1, j)	...	cost(1, m)	Oferix 1 ($F_1$)
Factoria 2	cost(2,1)	cost(2,2)	...	cost (2, j)	...	cost(2, m)	Oferix 2 ($F_2$)
...	...	...	...	...	...	...	...
Factoria i	cost (i,1)	cost (i,2)	...	cost(i,j)	...	cost(i,m)	Oferix i ($F_i$)
...	...	...	...	...	...	...	...
Factoria n	cost(n, 1)	cost(n,2)	...	...	...	cost(n, m)	Oferix n ($F_n$)
	Demanda 1 ($M_1$)	Demanda 2 ($M_2$)	...	Demanda j ($M_j$)		Demanda m ($M_m$)

cal mencionar que els costs deuen ser colocats en el cantó superior dret.

Comparació entre els plantejaments

Entre cada representació existix una equivalència que es menciona a continuació:

Model de Programació Llineal	Gràfica	Taula de Transport	Número
Restricció	Nodo	Rengló (oferta) o columna (demanda)	n+m
Variable $X_{i,j}$	Arc	Casella	nm

Solució del Problema de Transport

El problema de transport pot ser resolt de les següents formes:

• Método Simplex: El problema de transport pot ser resolt plantejant el model de programació llineal i utilisar ya siga el método de la gran M o el método de les dos fases (métodos variants del método simplex).
• Tècnica de Transport: Consta dels mateixos passos del método simplex no obstant és una tècnica específica de solució.

Per a que un problema de transport puga ser resolt a través de la tècnica de transport deu complir en les característiques:

• Ser un problema equilibrat (l'oferta total i la demanda total deuen ser igual).
• Contar en $n+m-1$ variables bàsiques, sent $n$ els punts de demanda i $m$ els punts d'oferta.

Tècnica de Transport

Per a aplicar la tècnica de transport s'utilisa la taula de transport equilibrada. Els passos són els mateixos del método simplex, els quals contemplen:

• Establir solució bàsica factible inicial:

Existixen varis métodos per a fer açò: Noreste i les seues variacions(Suroest, Suroest, etc), i Cost mínim o el método de Vogel: En qualsevol d'estos métodos es deu obtindre una solució que contemple $n+m-1$ variables bàsiques.

• Definir la variable d'entrada:

Per a trobar la variable d'entrada s'utilisarà els criteris ya establits del método simplex per a un cas minimisat. I es trobarà la variable utilisant el método de multiplicadors o método d'o-v. Dit método utilisa el model dual del model de programació llineal. El método calcula els valors de les variables duals $u_i$ i $v_j$ (cada rengló tindrà un $u_i$ i cada columna tindrà un $v_j$). Estos multiplicadors s'obtenen de les equacions: $u_i+v_j=c_{i,j}$ per a cada variable bàsica $x_{i,j}$

En total es tindran n+m-1 equacions i m+n multiplicadors. És necessari utilisar un valor arbitrari per a un d'ells i d'ahí trobar els demés valors dels multiplicadors.

Per a trobar el $z_j-c_j$ de les variables no bàsiques s'utilisa la relació:

Suponga que $x_{s,r}$ és la variable no bàsica, llavors es calcula en $u_s+v_r-c_{s,r}$.

Si en calcular estos valors algun és positiu, s'elegix al valor més gran de el $z_j-c_j$ com la variable d'entrada. En el cas de que tots siguen $z_j-c_j<0$, llavors la solució actual és l'òptima.

• Establir la variable d'eixida

Per a identificar la variable d'eixida serà necessari construir un circuit. Els circuits es construïxen a partir de la solució bàsica factible. Un circuit deu contindre únicament variables bàsiques en excepció de la variable d'entrada. Suponga un eixemple en la següent taula en 3 factories i 4 mercats, en este cas es tindran 6 variables bàsiques (3+4-1) i una possible solució inicial podria ser (es posa B per a indicar que és variable bàsica):

	Mercat 1	Mercat 2	Mercat 3	Mercat 4
Factoria 1	B	B
Factoria 2		B	B	B
Factoria 3				B

Suponga que la variable entrada és la casella (3,1), esta variable deurà prendre un valor de $+\nu$, açò ocasiona un reajustament de les demés caselles bàsiques, l'anàlisis es realisa per columna i per rengló, per tant el reajustament serà:

	Mercat 1	Mercat 2	Mercat 3	Mercat 4
Factoria 1	B$-\nu$	B$+\nu$
Factoria 2		B$-\nu$	B	B$+\nu$
Factoria 3	$+\nu$			B$-\nu$

Per a determinar el valor de la variable d'entrada $x_{i,j}$ i establir la variable d'eixida:

$x_{i,j}=min\{X_{p,q}/X_{p,q}-\nu X_{p,q}b\acute{a}sica\}$

En este cas el valor de la variable d'entrada $\nu$ es troba en els valors de les caselles (1,1), (2,2) i (3,4) d'estos s'elegix el valor més chicotet (esta casella serà la variable d'eixida). Una volta que es tinga el valor $\nu$ es fa les sumes i les restes de les demés caselles del circuit. Es retorna al pas de la variable d'entrada.

Vore també

• Problema del viajante
• Movilitat d'últim quilómetro

Bibliografia

• Hillier, F. S., Lieberman, G. J., & Elmer, M. M. (2006). Introducció a l'Investigació d'Operacions. Mèxic, D.F.: McGraw-Hill.
• Taha, H. A. (2011). Operations research: An introduction. Upper Saddle River, NJ: Prentice Hall.
• Winston, W. L., & Goldberg, J. B. (2004). Investigació d'Operacions: Aplicacions i algoritmes. Austràlia: Thomson.