Rol£ R. Mantel Estimación de tablas de tras- acciones intersectoriales

Documento de Trabajo.

~igiembre de 1973.

Instituto Torcuato Di Tella Centro de

Inve~tigaciones EconÓmicas super$ 1502

Buenos Aires (26) Argentina

O. IWRDDUCCTON Y RESUMEN

En algunas aplfeacfones econ&nicas, en especial en las del modelo de

Inaumo-producto, es necesaria la estimación de los elementos de una tabla

ce transacciones intersectoriales, cuando no es f a c t i b l e alg6n proeedi-

miento estadfstleo directo. Ea tande d i sponib le una tabla anterf or , así

c.mo eatimcxeiones corrientes sobre 108 totales d e las f i l a s y las cofum-

naa , puede ser deseable construir una nueva tabla en haae a esa in£orma-

c16n, que sea consistente con los totalee dadoa y que en algún mentido

bien def in ido , se acerque lo mba paaible a l a estructura anterior, Este

b e r e el easo cuando ee neceeite una tabla de fnsuma - producto para un

año determinada, y de las cuentas nacionales de eee año e810 se eonoz-

can los niveles de producción total de cada sector. Otra CASO se pre-

genta cuando deben ea tablecerse Los flujos interre~j.anales de bienes y

servicias y sblo se han estimado l a s importaciones y expartaeicnes eoca-

les de cada regien, s i n tener a mano una infomaci6n detallada y actua-

I.lzcnda d e l origen y destino de dichas fmpsrtaclonees o r_.xpurraclanrra.

En el caso de tablas no negativas arbftrarias, se rnnrrren varias so-

l u c i o n e ~ a l problema, pero éstas no siempre exl~?i.citrin exiterios de op-

~imixaei6n para el ajuste (1). El presente trabajo anal5zsrZ algunoa d ~ ,

estos criterios : rnfnimas cuadrados, con o s i n psrnderaei6n de 105 toi a,.?:r m ,

con o s i n ransideraeión de le l ios ib i l idad de soliirioneu cmr , .L . . .OS nl;: - -

p.ativas; y fa mfnimizaeión del m5ximo error relativo. SE demostrará

(1) Ver loa trabajas de Bacharach (19651, Hatuaxewski, Pitts y Sdwyer (1963 y 1964) y Theil (1967).

que eete í i l t i m o criterio puede ser implementado eficientemente, redu-

ci6ndolo a un problema de progratuaci6n lineal, y reeolviéndolo p o r medio

de m algoritfio, basado en una modificación de los mEtodos de solucf6n

da problemas de transporte.

L. EL PROBLEMA Y SU SOLUCZQN 'CORRIENTE

El plantea del problema puede anunciarse de la siguiente manera: da-

da una matriz A de m fila8 y n columas, con elementos no negativos,

y dados un vactor positivo b de m elamentúm, de aumaa para las f i l m

y un vector poeitivo , de n elementoe, de sumas para lae columnas, ha-

llar una matriz D de igualee dimsnsimee que la tabla original. A que

satisfaga las condicionem

( 1) D e m b ; e D m c

donde e , el vector suma, as de dimentafbn apropiada y tiene todoe raue d e -

Entos iguales a l a unidad. Lae ecuaciones (1) expreean las condiciones

de coaeistancia de la nueva tabla con 1w 1ua0 marginales dadas. Por

otra parte esta tabla debe ~proximaree lo d a paaible a l a tabla original,

Bscharach (1965) p'rapuao como criterio da ajuete l a condición de que

la nueva matriz @ea biproporcianal a la tabla dada. Con sete término se

expreea l a candici6a de que axietan veataree pnei tivas r y S de dimen-

1 / siones eprapiadao t a b i que ee cumpla la ecuaciún -

de donde murga el nombri de 'kdtodo RhSm. Eeta autor demuestre que la oo-

lueibn puede calcularme por medio de un ,proceeo iterativo, en el cual ae

ajustan en cada etapa primero la8 filas, de manera que las aumae cmcuer-

den con las dad- manteniendo constants la estructura de cada f i l a , y h e -

I/ El acento circunflejo sobre un vector lo convierte en una matriz cua- - drada diagonal con lom elementoe d e l vector a lo largo de la diagonal principal,

go lu columu , da mlrllara que 1u wmam concu~rdm con l a i dadai mante-

niando eon8tuitm r i t r v r i Ii r i t w c t u r r da cada c o l w i , EL proceso coz

vmrgi m i y 8610 8% lu icuaciorir i (1) timan usa rolucibn D no nrgrti-

v i , m i diair , ii y ralo ii rr aump2m I r oondiol* da eoni~rt rnai i ,

( C) EI a i i t r u d. aouroioau (1) a i o ~ ~ ~ i i t i i i t a 0 0 . una io ludd. oon

b) prri toda prrtioidn da1 oonjunto bl as dos ruboonjunto8 axl

hmitfvoi y iraluyintii 1 r 1' y toda part ioibn d i 1 conju!~

t o l4 a ' doi ,iubeoaju~tor axhruitivor y rxoluymntai J y

J ' , i t Lo i~a t lor in to i r da i imtr i i A i e n a u l ~ m p a ~ a t0-

2/ M y # npraamtra i lo8 aoajuntor da 1~ p r b e o i m y n nduroi nrturrlri, zrrpiotiva~anta, La not~ ldr i C , por rj-lo, raA.1i l a ru- a a todo, la t i a ~ i n o g da ii f e n i imdio.ir. ooneiwactái d a ~ dolo dr #materia, pata iiiiorai d i E fndiar d i ihr ooatraidor rn a1 conjunto M, La dmortrraibn da l a propoi5cibn qur iQui purda rncontrirra, por i j r ~ r p l o , ai10 (19601,

Cc aguE en adelante se supondrd que se cumple l a condici6n de consis

t ~ r ~ c i a (C) 3 fin de garantizar la existencia de al menos una solución pa-

ra el sistema de ecuaciones (1) con coeficientes no negativos,

Para s hglificar l a notacidn se emplearán las siguiente8 definicio-

nes :

(3)

y se supondrá que la matriz ariginal A es no negativa, con sumas margi-

nales posilivaa . Se ~ssard revista muy brevemente a dist intos criterios basados en

cuadrados nlnimos, d t o d o que tiene a su favor La eimplic idad de su apl ic j ,

ción,

a) :.íEnimos cuadrados siprples , s i n restriccioaea de no negatividad,

La soluci6n m á s sencilla de calcular e8 la que resulta de ninimizar

31 el s igu iente objetivo -

( 4 ) tr (D - Al (D - A) '

su j e t o a la condición de que la matriz D cumpla con las ecuaciones (1) . Formando la expresf án de Lagrarige

3/ El sfmbolo tr índica l a traza de la matriz que le s igue, es decir, la - suma de loa eiemen~oa d e la diagonal pr incipal de la matriz. El apóstxa- fe ' ind i ca transposición de la matriz que le antecede.

dondc p y q san vectores de multiplicadores de Lagrange, es ir.nediaca

la cb tencica de la^ coxidicionics necesarias p Erz un ~ f n i m ~ , anularira:: l a

derj-vada y a - c i a l L,, de L con res?ecta a 3, as decir

de donde pueden eliminarse los multiplicadorez car. La syuda be las zcuz-

C i C I i e ; (3 .3 >¿ra oLEen~+r la soluci6r, explfc5?x

(5: r = ( A - b C / S ) T* + h CIE

m &nde La, p3r e j ~ v p l ~ , 2s ;ia :n;itriz de c::¿sn n tnyclj 2:-crnatos ¿E Iri <=í - g m a l ,~iiic:~;aT so:: L~cales rt (ni-1) Jn: y :,os :'~:ligs.. of_a:r;;entus r : z l x

7 , y ? s: Jeflri,: ?e r.:crcrri s imi la r , ccii n rz,@npL,??z:.d:j L S*, n

El. ~ r S - r . e i p ~ 1 iiicon-~cnicnte 2c e s t e ?t"0c i : ' 5 -~ t~ : :C eL ? a ;3;3~51L1:.¿.

d~ 3L.e !.u z:.32ci.?i; c c a t e ~ g c h?Lrr.,entzs ~ a ~ z a t i - ! o c , 2 e r r puede sub~caz rcc

ccois.l:zr.~,a,!o 1s r,f!ii¿i:i-5r; dc que e s t a ~ i c ! cccl-ra, c r ? ~ . ~ sc PTO;IOEC En c.2. n?é - todo ~fguiecte.

9: se dese ?s.?.cttlar r:J n5;:imc Zp Ir. !.:!?ir. :TE: 1 4 ; r-:ijc!-i: E 1 + , - I-

ct?eer;cn~r: [1> y :! Ir, cor.dici6n t e que La so!.:;cf$r, ~ P F rz z ~ g a t i v z , ? n

e3 ;'cislb,Le: Fr.?nei.+ar la soluci6n cn fonna cerrz.?-z trc-r cr, ~ c u E c : ' ~ ~ : (5)

S i n e ~ h n r z e t t f l n v f n s e pue l e caLculxr 3 a ~ c ? l u c i 6 n can cie:: ts faci?+i ri.r.2 :

in:iliz~r.2? ~?;irrc ?e 1.03 rr.8tolcs ?.?~FI rzc: T w ? : prrb!.er.üe ,'e prcgrmar i6r .

cuzdrstica con re~triccfane~ lineales.

c) Mínimos cuadrados ponderados s i n restricciones de no negatividad

E' inccnvenfer-te cpe puede presentarse ea l o s mÉtctdoa anteriores e8

que 108 t é m i n o 6 ciel error no se panderai: d c ccuerdo con la importanciz

relativa d e l coeficiente. En particular, la acluciBn puede 2resetitar coe-

ficientes no nulo8 cuando los de la matriz or ig ina l lo son, situacibn en

que puede eer deseable imponer la restrfcci6n de que la solucián también

tenga nulos esos mismos coeficientes. La otra situación, algo menos ex-

trema, que puede presentarse ee que coeficientes pequeños sufran graridrs

correcciones, rnie~tras que los coeficlentet; myor~ls cst&& sujeto:: u

correcciones pequeñas , modif icaildo as2 aprcciab lemerito la estructura dc

l a matriz. Ea Ease a estas consideraciuries se arriba al objetivo a m h i -

donde w representa la importancia asignada al docvfo correspondiente i j

-un valor m& baja indica quc e1 desvfo absolutc debo 6er menor-. Sc l ~ ? p 3

ne que ectov ~ ~ k f i c i e n t e e de ponderacibn no non n c g a t i v ~ s , y que cul;i;dc

u.. es nula la solvcidn debe cumplir cün 13 igualdad d . . = u. .. CIEG eii 1 3 =J 13

E s t e caso AL cor,;zira dircctameiite un cosficiciite dcl la zciluci6ri c ~ i l uila

de l a tabla cr ig inal , es m& uiiportaiite q ~ c Ccs nisui~s G e a n cmpsrablcs,

es decir que 138 dos sumas B y u a e m & magnitud no muy disfmil. Es-

to puede lograrse iriultiplicandu la matriz original A p o r algGn número

pocitivo conveniente, si fuera necesaria.

Como en el caso descripto bajo a) : l a solución puede presentarse en

n o t a c i h matricial a f i n de calcularla directamente. Para ello se proce-

de minimizando el Lagrmgeano

L L = 1/2 zMxh' (dij - a. .) / w.. - p (D e - b) - ( e D - q 11 =J

obteniendo las condiciones nec,eaarias

equivalentes a la ecuación malricial

donde W e R la matriz de las ponderaciones w ij '

Definiendo W'e = v ,

e W m u, posmultiplicando la ecuación (7) por la columna e , y luego pra-

multiplicándola p o r l a f i l a e , recordando los s?mbolos para las sumas

de las filas y d e las columnas de las matrices A y D , se obtiece la

ecuaci6n

Esra ecuacíEn, puede resolverse p o r medio de una inversión de la ma-

triz d e l sistema, si se cumple un supuesto de interdependencia de 1.0s

4! coeficíentes 32 ponderacibn - . Si sc h p c n e la r a c ~ r t c c i á n adic ional

p e e q -que es admisible ya que e x t s t e un grad~ de l ibertad gara l a s

mult ipl icadarzs dc Lagrange en la s o P ~ c i 6 n - se llega a la C~rmulnci5a

4/ Ver el asEndice 1 para una fomulaci5r. ri-guxosa de esta condición de - interdependcncfú y Za demoetracibn de que la matriz de coeficientes d e l sistema es regular.

tos valores para l o s multiplicadores p y q permiten calcular la

matriz D en base a la ecuación (7) , quedando asE resuelto el problema.

El lector podra verificar que tamblgn por metodos l ineales se re-

suelven dos criterios relacionados con el aquf presentado. Uno de e l los

c d n s i ~ t e en elegir como objetivo la minhización de la expresi6n

mientras que el o t r o utiliza como objetivo la expresión

siendo de ambos casos variables l a s A , y tomaida como restriccioiic::

l a s ecuaciones (1). La expresión (9) p e r m i t e que el proceso de optimi-

zación e l i ja el nive l adecuado para l a m a t r i z o r i g i n a l A de transacei~

nes, determi~ando dicha n i v e l , indicado por l a variable h . La expre-

sión (10) permite más f l e x i b i l i d a d , al ajustar cada columna de la matriz

A endbgenamente. En este caco se supone que: es importante mantener la

estructura de las columnas, coma sucede en aplicaciones d e l modelo de

inaumo-producto. Un método que considere m$s importante mantener la es-

tructura de las f i l a s se obt iene intercambiando f i l a s y colunmas.

Podrfa pensarse en generalizar aún m á s el problema, permitiendo un

ajuste simult%noo de f i l a s y columnas, de manera que, por ejemplo, en

(10) se multiplica cada coeficiente de l a matriz A por una variable

cuyo fndice depende de l a f i l a , ademgs de l a variable cuyo fndice depende

de la c o l m a . Este criterio expresa el deseo de que la soluci6n se a-

cerque a una matriz b i p roporcional a la original, man teniendo s imulthea-

mente al. mfnimo Pos desvfos , En este caso l a solucí& no puede calcular-

se por vfa d e l álgebra l ineal Gnicamente, debiendo procederse de manera

parecida a la soluciÓn por el mgtodo RAS.

d) M bimos cuadrados ponderados, con res t r iccionea de no negatividad

La solución presentada para el método anterior puede contener ele-

mentos negativos. Si es importante excluir esta posibilidad, ser6 nece-

sario minimizar uno de los tres objetivos indicados por las expresiones

(6) , ( 9 ) o (10) , con consideración de las restricciones (1) y la consi-

deracidn adicional de laa restricciones de no negatividad de las varia-

bles. Como en el caso presentado bajo b ) , l a solucidn no puede obtener-

ae por medio de una f8rmula explfcita. Sin embargo se la podrd calcular,

con cierta f a c i l i d a d , utilizando algGn algoritmo para resolver problemas

de programación cuadratiea con restricciones lineales.

Corno comentario general a mfnimos cuadrados ponderados , debe tener--

se en cuenta que, si la matriz de ponderaciones W no tiene nulo8 los

cuef icientes que corresponden a los ceroe de la tabla de transacciones

original A, la soluci6n probablemente proporcionará coeficientes no nu-

los donde l a estructura original tenfa caef icientes nulos .

3 . CbLciaó DEL mfiii$G zRT,uk j.&Lks,'f*;:d i,'&ipiCi

En vez de minimizar un promedio de los desvfos cuadrbticos como en

los mEtodos de cuadradas rufnimos , se puede requerir la reducción a su mi-

n i m o d e l mayor desvfo relativo absoluto. En otras palabras, si se defi-

ne como desvfo relativo absoluto a la e x p r c s i h

este objetivo puede expresarse como e l de minimizar la expresign

suje to a las condiciones (1) y la no negatividad de la8 variables.

El problema asf planteado no es l i n e a l , ya que en la definicidn (11)

interviene un valor absoluto y un cociente para cada par de Indices.

Sin embargo, es pos ib l e transformarlo en un problema con objetivo l i nea l

y restricciones en forma de desigualdades, para l-iaLLar la solución por

medio de l o s ngtodos usuales de programaciS;? l i nea l . A f i n de demostrar

esta afirmación, nótese que las ecuaciones (11) y (12) pueden resumirse

en laa desigualdades

t > > - --(D + AA) D - AA - &(D + AA). i L

estas desigualdades se reducen a

P o r medio de las ecuacloncs (1) y sustituyendo las sumas de f i l a s y co-

lumnas de las matrices A y D por sus s h b o l o s , se l l ega a las condi-

ciones

Finalmente, como el numerador de la expresibn (11) nunca excede al deno-

minador -recuErdese que t:inguno de los sfmbolas ea negativa- 81 valor 6p-A

ttmo para 5/2 no excede a la unidad, de ~ a ~ e r 3 que la defii1ici6n de x

i ~ d i c a qee el mfnimo para </2 ze alcanza cuando r ec máximo. En cor,sc-

cuencia, el problema reformulado consiste en calcular el m k i m o d e x

suje to a las condicionee (13) y (14) , un probleiiia que es, evidentemente,

d e programación l inea l . h'o es neceeario tetier en cuenta en f ornia explg

cita la condición de no negatividad de loa coeficientes de la matriz D

ai de la variable X , ya que ésta se cumple auco~6ticamenre en la solu-

ción Gel problema derivado.

luede verse que las ecuaciones del problema de máximo, as5 plantea-

da , son siempre consistentes; basta para e l lo sustituir en (131 y (14) a

2, y , x por cero. En cambio, aunque este heclio no es muy probable, e-

xiste la p o s i b i l i d a d de quc la solucibn no esté acotada superiomeiite.

Como i a matriz 2 es:S crcctada por la matriz or ig ina l A -ver desigual - dades (13)- ufi ri5ximú in f í z i t o requiere que i a su:ras niarginalcr dados

para Ea matriz ajus::asia G sea= propcrcionoles a las silmas correspon-

d f c c t c ~ de la& filas p colunuias de la matriz h. Ccrr,o cero eo cviclciite

con m a ~ i m p l e inspeccisn Z E los dato^, este caso puede excluir~e por

poco interesante, ya que la so luc ibn consistirá cn una matriz cuyc; ele-

nientos son todos proporcionales a la matriz origifinl. Si de todos acdoo

sc Jesca i n c l u i r este c a 3 ~ en cl anális is , deber2 ut i l i zarse un algorit-

z o pare ia solución dsl írc>lma que, no ~ 6 1 0 iaiiiquc que cl z h j c t i v o nu

e ~ c S acotado sino quc, prcpcrcime la diraccibn en ,;tic la aoiuciBn puede

aumcntar el objetivo en foma i l imi tada -tales algoritwos han sido im-

piementadoo aunque no san tfpicos-.

Si bien ea posible calcular la solución por medic d e l mgtodo s i m p l e

i~kra programación l inea l o algún otro algoritmo general, la estructura

dc1 problema p e r m i t e seguir un método mucho m8s eficiente, Si se cono-

cen los valores de x e y , la matriz 2 se puede determinar par medio

de un algoritmo para la soiuci6n de problemas de transporte -ecuaciones

114)- con restricciones sobre la capacidad -desiguaidades (13)-. Como

oe sabe, estos mgtodos son más eficientes que e l mgtodo simplex, ya que

tcman en cuenta la estructura especial del problema, que permite calcu-

lar l a solución por medio de simples sumas y res tas , s i n necesidad de

efectuar multiplicaciones o divisiones. La estructura d e l presente pro-

blema es a l g o más compleja, pero es p o s i b l e utilizar el metodo de decam-

posicidn de Dantzig, usando 205 métodoa de deteminacibn de f lujos en

redes con limitaciones de capacidad, en uno de l o s subproblemas en que

5 / se descmpone el problema dado. -

En aplicacionea del modelo de insumo-producto, como y a ee ha hecho

notar, puede ser importante alterar lo menos posible la estructura de

l a s columnas de la matriz A, de modo que será deseable aplicar el cri-

t e r i o de Bptiuto a cada columna por separado, reemplazando la definicidn

(11) por

5 1 Ver el apgndice 2 . -

con una variable d i s t inta para cada una de 1- columnas que indique la

escala d e l eector correspandiente,

Como en el caso anterior, lee relaciones (15) y (12) pueden xees-

cribirse ahora como

> * > &

E(D+ A: ) = - - - < ( D + A l 1.

CI 2 Definiendo t E A / ( e X ) ; Z E D y - x A t; y ~ ( 1 -& ) / 46 (el);

2 x (1 - E ) / 46 ; estas desigualdades se reducen a

Utilizando las ecuaciones (1) como en el casa previo, se l lega a

A estas condiciones debe agregarse la ecuación

que es una consecuencia directa de la definicibn d e t.

Como se notará de Inmediato, el sistema resultante no e s l ineal , ya

que en las ecuáciones (17) aparece el producto de la variable x por el

vector t , ambas incógnitas d e l problema. La solución deberá determinar - se por medio de aproximaciones sucesivas, en base a vectores t: de

prueba, o, mejor aGn , por medio de alguno de los algowitmois d i s p o ~ i i b l e s

para l a deteminaci5n de la solución de crecimiento balanceado de l mode-

lo de von Neumaan, ya que, en el fondo, el presente problema es de le

familia de problemas generalizados de detenninaci6n de vectores caracte-

rfsticos de sistemas l ineales . No noa detendremos en g1.

Desde el punto de v i s t a práctico es quizá conveniente la primera

solucion de esta sección, que tiene l a ventaja de ser fbcilmente calcu-

lable.

DiaresiÓn sobre la euuivalencia de las soluciones obtenidas con d i s t i n -

t o s conceptos de error relativo.

Considérese l a siguiente definición de error relativo entre dos

matrices no negativas A y D

( 1) 5 = rnaxij / dij -1 a. . l / (t d . . + (1-tl A a - . ) 1 J 13 = J

donde X es un factor de escala calculado de manera de hacer el error re-

lativo 5 mfnirno, y t es un parhetro no negativo y no mayor que la uni-

dad. Se demostrará que el problema de programación l ineal , a que puede

ser reducido el problema def in ido en La sección 3 , d e l texto , es inde-

pendiente d e l valor d e l parhetro t. La función objetivo allf adoptada

corresponde al valor de t 112. Otros valores particulares de interes

son los correspondientes a L O -errores como porcentajes de la magni-

tud de loa elementos de l a matriz original A- y t 1 -errores como por-

centajes de la magnitud de los elementos de la matriz estimada D-.

La relaci6n (1) implica

(2) >

f (t D + (1-t) AA) m D - A A 2 -E (t D 4- (1-t) A 1 0

que se reduce a

(3) > >

A ' 2 = 9

si se define

Como relaciBn inversa a la primera definición de ( 4 ) puede tomarse

Ahora Lieli, la ~oluci611 Óptima del problema d e maximizar x sujeto

a las condiciones (31 y

( 4 ) Z e - b y + B x = = e Z - c y + $ x = O

d : ~ un valor no negativo (posiblemente infinito) para x , Para tales va-

lores de x la ecuación (5) indica que aumentos de x son equivalentes

z disminuciones de E , y , por lo tanto, el m%cimo d e x corresponderl a

un mfnimo de F . Esto es valida aun para l o s valores extremos de cero y

uno para t , en los cuales la ecuaci6n ( 5 ) deber5 interpretarse como cl

límite que toma esa expresih cuando t tiende al valor dado,

Para f inalizar ae proporci onarsn las fórmulas a que ae reduce (5) :

( 6 ) 5 m 1 / (1 + 2 X) para t O 6 1

E = 2 ( 1 + 2 x - 2J*)»') = 2 d z - ) 2 para t = 112.

Apéndice 1. - Existencia de una s ~ l u c i h Gnica en el caso de minlmos

cuadrados ponderados.

Eii el texto sr! iia afimado que 13 matriz, cuya inversa se indica en

la ecuacizn (81, ea regular -es decir, su inversa existe-, si se cumple

la condición.

(1) 'Lnterdependencia. - Loa coeficientes de la matriz de ponderaciones

W corresponden a un sistema interdependiente, si para dos

subconjuntos arbitrarios I y J de M y N, respectivaen-

t e , se cumple sieinpre la desigualdad estricta

{ J . . > o , ' I ~ J Wi j + 5 I'XJ 1,

donde 1' y J t representan los complmentos de I y J en

M y N , respectivamente.

Esta condición se d~ siempre en la práctica, si a coeficientes posi-

t ivas da la matriz A correspanden ponderaciones posi t ivas , pue8 la ma-

t r t z A cumple con esta condición cuando hay, al menos, un sector que

rcaliza trans~cciones en forma directa o indirecta con cada uno ¿e l o s

dcmzs. Si esta cundición no se cumple, el sistema econ&fco se divide

en dos partes completamente independientes entre sf , y entonces es posi-

ble analizar a cada una de ellos por separado,

Para demostrar que la matriz mencionada es regular, resulta suf i -

ciente demostrar que es pos i t iva def in ida . En otras palabras, si se la

pre- y posmultiplica por un vector arbitrario (x ,y) , debe d c ~ o ~ t r e r s e

que el resultado no es p o s i t i v o 8610 si este vector es nulc. Efactuan-

do dicho producto, se obtiene

- E w . . (xi + y . ) ' + ( e x - e y) 2 m 11 J

donde se ha uti l izado la definici6n de los.vectorss u y v. Como la s

ponderaciones no son negativas, este expreaian no puede eer negativa,

ya que ea una suma de términos no negativoe. Ademh, para que la expre-

sicri mulc es i:eccsilrio <;:? se 3nuL~:; t o d o s sus r;Z:.i.;iuos. Ec. : tc s i g -

>!,fFca, i3il ps3iier :.usar, anular cl ~ar2:itesiz 9ue si.gue a cada 1jciil-Jura.-

1 { i ! x, = :<,). J. c

7 ?l c o i i j ~ ~ ~ b o di:: coardcl:zdil:; C!C igu01es a la irrinera dc x con sig--

S i I no c o i n c i i l ~ can ti, o si. 3 no coincide con X , la condic izn (1)

i ad ica que

cs d e c i r , qzc existe, o bien a l g h par ( i , j ) con i i ~ , 1, j c .3' para cl

q ~ e la poiidcraciói; es p o s i ~ i v a y por lu t a i i t o 1. c: -x = --.* "*1 o I,-i.cin a,;.

' j i ., -

~ G i i par (i. ,j) cori i c i 1' , J a 3 para el q u c l a i ia~d~rac i6 i i es: l i c s i t ivs

- dcfinici5i1 de 5 , mientras quc an cl scgundo ijc contraciicc la defiilici5iz

de 1; por e l l o todos lou clcmentos dc x c y deben ser p x ~ p c r c i o n a l c ~ ,

es decir

x = c; y -1 2,

Cotiio tat:ibi$ii cl Ciltiiiio ~¿Qriiiii;o dc 12 c ~ ~ r c s i . 6 ~ ; :>ajo ~ 3 t u J i . 0 CICUC ;:.-

ririharsc?, ;?uec!c vcrSL dc iil;:iciliato que J. dc5e : . t i ~ nulr;, i;ie:~da iiaf.or cii

cordcecueiicia tanto s. coica y. Es to deniucciera la rifiazaci~ii hcchn al

u r k c i ~ i o dc C S L ~ ap6- L L G L C ~ . ' *

Apéndice 2 . - Algoritmo para minimizar e9 error relativo máximo.

Si bien es p o s i b l e determinar la solución d e l problema planteado en

la s e c c i h 3 d e l texto por medio d e l m&todo simplex, la estructura espe-

cial d e l sistema de restricciones sugiere la p o s i b i l i d a d de hallar algGn

mstodo m& eficiente que un algoritmo general, El algoritmo que se preeen--

tará a continuación toma en cuenta dos de las caracterfsticas del proble-

ma. La primera es evidente en las desigualdades en (13) del t e x t o , que

muestra que un número considerable de restricciones -exactamente n x m-

consisten Gnieamente de una cota superior a las variables ,ademh de la co-

ta inferior usual en l o s problemaa de programación lineal dada por les

condiciones de no negatividad, En lugar de incorporar estas cotas su-

periores explf citamente al problema, es más eficiente tratarlas de acuer-

do con el mgtodo ideado por Dantzig (1963) para cotas superiores, de

manera que las eeuaciones se reducen a las m -t. n en (14) del texto, A su

vez, estas Ú l t i m a s ecuaciones presentan la estructura especial de un pro-

blema de transporte, en lo que se refiere a %os coeficientee de las va-

riables incluidas en l a matriz 2. Esto no es cierto para l a s coef i-

cientes de Las variables x e y; por tal motivo no es p o s i b l e calcular

l a eolución por medio de un algoritmo para resolver problemaa de trane-

porte, Sin embargo, SI es pos ib l e descomponer el problema en dos, de

acuerdo con el mgtodo de descomposicilh de Dantzig (1963) aplicado al

problema duaP, o el de Beale aplicado al problema directo. Uno de

l o s subproblemas tendrá entonces la estructura adecuada para la aplica - ciÓn de un algoritmo de transporte. EP algoritmo detallado a continua-

eiÚn está inspirado en estas cmsideraciones, con una aimplif icaci6n

adic ional , permitida por el hecho de que las sucesivas tases son casi

triangulares, que p o s i b i l i t a hallar la solución exacta d e l problema,

A fin de poder describir la solución necesitamos formular el proble - ma y su dual. El problema directo o primal es

(P> m e x x sujeto a

c < Q = Z - A

Z e t b y + 8 x u O

e ~ - c y + 8 X = O

Por m d i o de una matriz M y dos vectorea p y q de dimensiones

apropiadas podemos escribir la función de Lagrauge , eumando las res tric-

ciones convenientemente multiplicadas:

t u x + t x (A-Z) - p (&-by+ Bx) f (e2-cy-1-$x) q

donde el sfrnbolo tr indica la traza -es decir la suma de l o s elementos

de la diagonal- de la matriz que fe s igue , mientras que el apóstrofe '

indica transposición . Los tihninos independientes de las variable8 del primal no8 dan la

funci6n objctivo d e l dual, mientras que las restricc5ones de éste se ob-

tienen calculando 1 s derivada6 d e l b~rangeano con respecto a las varia - bles d e l primal , tenZendo en cuenta las restricciones de no-negatividad.

21 resultado es el problema d u d

(DI min tr l!' A sujeto a

PB - = 1

p b - c q = 0

Lcs fines del aPgorit=io nos interesan en particular las relaciones

de cmplenentaxidad entre los dos problemas, (P) y (D), Estas se dedu-

cen conparsndo las primeras restricciones de (P) con las Últimas de ID) ,

y en forma explIcita s m

implica q j

Eliminado lcs coeficientes. de la matriz II con lz ayuda de las 61-

tf;?a.; r e ~ t x i c c i o n e s d e (DI se llega a la formulación equivalente

P . > q implica zij - O 3 j

Pi < q j implica 2.. = a.. 33 13

A fin de simplificar la exposici&, supondremos que no se presentan

problemas de coLuciones degeneradas. Si bien , debido a. la estructura es-

pecial del problema, ea muy p o s i b l e que en alguna de las iteraciones no

se produzca un aumentc en el valor de la función objetivo, en la práctica

Esto no ofrece problemas, pudiendo resolverse l o s casos en que hay varios

candidatos para abandonar la base, por medio de alguno de los procedi-

mientos conocidos -orden lexicogrgf ico , perturLac5Ói, selección al azar-,

A continuación se explicarán lag etapas principalea d e l algoritmo, d e j m-

da para el final un sencillo ejemplo num&rico.

Iniciacibn d e l algoritmo

El primer paso consiste en la determinación de una solucí611 básica

arbitraria a las restricciones de (P) , con e l agregado de que x sea

nula. Dada la condicián de consistencia (C) d e l texto, siempre existí-

rá una eoluci6n no negativa a l a s ecuaclone~

ta l que los elementos de la matriz Z correspandientea a elementos nulos

de la matriz no negativa A, son nulos. En base a teoremas del Qlgebra

elemental -véase, por ejemplo, Dantzig (1963)- existirg una soiucidn bá-

O sica que se denominar5 Z mientras que los elementos de evta matriz Y'

que es& en la base -en nGmero igual a mi-n-1 debido al supuesto de no

O degeneración- formar& el conjunto t5sico S . Para la deeermínaci5n de

e s t a base i n i c i a l podr6 utilizarse cualquiera de las mÉtodas pzra re8ol-

ver el problema de transporte con restricciones sobre las rutas, por lo

cuat no se presentar& 106 detalles.

A f i n de cumplir con les cotas superiores indicadas por la s primeras

res t r i cc ione~ de (P), es suf ic iente inulti.plicar la aoluciSn básica ini-

c ia l por un nGraero s o s i t i v o detcrmicado. Tomando el mayor número p o s i t i -

O vo , t a l que se cuui~lm. Isc cotas superiores, y denominhdolo y se ten-

drá que

satisfacen la8 restricciones de (P). Las varhbles idsicas formar& un

O o conjunto B , que se obtiene de S de la siguiente manera. Debido a la

O O definición de y habrá un elemento de Z igual a su cota superior. Esta

variable, p o r lo t a n t o , se excluirá de La base, debiendo ser considerada,

O como variable no b s i c a en su c o t a super ior . Por o t r a parte y es pos i -

t i v a , de manera que habrá que incluirla en la base. Esto significa que

3' es igual a SO s i n una de las variables en su cota superior pero iriclu-

O O yendo a y . EL conjunto S recibe el nombre de seudobase, y será de

Euma u t i l i d a d durante el cblculo,

El práximo paso consiste en in.troducir x en la base. Para simpli-

f icar la soluciSn, aprovechando la estructura d e l problema, es Útil des-

componer la matriz Z de acuerdo con la ecuación

Se supondrá que Z satisface las ecuacianes (2) y satisface Y

de manera que l a matriz Z def in ida en (3) satisface automáticamente

las ecuacioncs en (P). Para calcular las matrices 2 y Z se emplea- Y X

rá la seudobase ccrriente; los valores de x e y se determinarán de ma-

nera que las variables en la seudabase, que no son básicas, no se alte-

ren. Además su nivel debe ser tal que, a l i n t r o d u c i r una nueva variable

en la base, se elinine alguna de las anteriores.

Al iniciar el primer paso del algoritmo deberá entonces deter-

1 minarse 2 de manera de que se satisfaga la ecuación ( 2 ) por medio de la Y

O seudobase S .

Por supueato, la solucián será simplemente

1 Como la seudobase es triangular, el cálculo de Z es inmediato, ya

X

que sólo es necesario realizar restas en e l orden conveniente. Si el

elemento (k,h) de la matriz Z es no básico pero eaeá en l a seudo-base,

se calculará la matriz auxiliar

1 1 1 donde dyl = (X)kh ; dx = para que el elemento (k,h) de D' sea

L nulo . Podrá entonces calcularse el nueva valor Z para la matr iz Z en

base a la fórmula

1 debiendo t ser máximo h a j o la condiei6n de que se cumplan laa cotas su-

periores e Inferiores para La matriz 2 dadas en {P) , es decir , r debe

Si ( i , j ) son l o s subfndices de un elemento hss ico para el que una de las

desigualdades en la def inic icn ( 7 ) es una igualdad, o sea, el elemento

que mL=s restringe el incremento en t , se habrá hal lada la variahle que

debe abandonar: l a hase. Restimiendo:

Una vcz i n i c i a l a d o el ~ l g o r i t m o en l o forma descripta, re puede pro-

seguir con los pasos s iguientes . Como $SLOS son s i n i l a r e s , darezos l a

¿escril;ciÉn dcl cicLc gccgricc k, para IE = 1, 2, 7, . . . , que permite pa- i ~ k k k k

sür d 2 los datos c o n c c i d o ~ x , y , Z , 3 , S a los necesarios para el

ciclc s i g u i e ~ t e .

Ciclo k

C::i!a c ic lo se cmpoae d e varios pasos. El primero cofisiste en de-

termtr:,;. s i la soPuci& eorrrente es o no 6ptima. Si lo es, ei problema

sc ha l l a rcsuelt:~, mientras que si no lo es resulta necesario determinar

la nueva variable que debe ingresarse a la base. Es obvio que tanto x

como y siempre serán básicas, de modo que sólo habrá que analizar los

elementos de la m a t r i z 2. Finalmente será necesario modificar las va-

rcables bás i cas hasta que ar.a de gstas abandone la base, hallando así

l o s nuevos valores para las variables, la nueva base, y la nueva seudo-

base. Se describir5 a continuacibn cada uno de estos pasos.

a) Cálcula de las variables del d u a í , a f i n de detectar la soluciÓn 6p-

t i m a - Como surge d e l a n á l i s i s de l o s problemas de transporte, una base en

tales problemas es siempre triangular, es decir, el sistema de ecuaciones

para hallar loa valores de las variables bSisicas es triangular, permitfen - do calcular una a una en forma recureiva, s i n necesidad de resolver si#-

temas de ecuaciones eimuitheas, En el problema presente la hase consta,

como en l o s problemas de transporte, de rrir-n-1 variablee. Sin embargo,

no todas son elementos de l a matriz 2, y a que t a n t o x como y se ha-

l l a n siempre presentes. En cada ciclo, l a seudobase se mantiene trian-

gular, como sí fuera la base de un problema de transporte. Desde el pun-

to de vista de la teorla de las redes, l a sed cuyos nodos son 3.a~ f i l a s

y columnas de la matriz, y cuyas aristas son las variables básicas,

forma una arborescencia,-es decir, no contiene ciclos-. Ai pasar de la

seudobase a la base hay q ~ e eliminar dos mis tas -la base contiene dos

elementos menos que la matriz 2- y Estas neeeaariameate dividen a la

arborescencia en tres partes inconexas. Las condiciones en (1) implican

que si (i , j ) está en la base, entances p i = qj

, de modo que las cansi-

deraciones anteriores dan la clasificación de las filas y columnas en

tres clases, con precios -variables del d u d p y q-iguales para todas

las f i l a s y columas en una de las tres clases, Como no todas las ecua-

ciones son independientes -resultado conocido de los problemas de trans-

porte - será p o s i b l e asignar un valor arbitrario a los precios en una

de estas claaes, cera por s impl ic idad . Asignando el valor de r a los

precios cn otra de las clases y el valar de S a l o s de la tercera, e

intxoduciendn estos valores en las primeras dos ecucianes de (D), se

obtendrán dos ecuaciones en las dos incdgnites r y G que, una vez re-

sueltas, permitir& determinar todos los precios. Si con estos precios

se cumplen las condiciones (1) para las cmbinaclones d e subfndices r,c

Lasicas, se habrá l legado a la solución 6 p t i m a . En caso contrzrio será

necesario modificar los valores de las variables, efectuando l o s 2 ~ s c s

siguientes.

b) De terminación de la nueva variable 5ásica

Esta etapa es sencilla. Ai verificar las condiciones (1) se ha-

brán presentado casos en que éstm no se cumplen. Cualquiera de ellas

da una indicación da que la variable correspondieree p ~ e d e ser introdu-

cida c m provecho. E2 usva l introducir l a varia5le para la que el cri-

terio da la diferencia mayor, aunque esto no asegura llegar a la solu-

c ) !ktemi.naciÚn de la nueva s c u d o t a s ~

Las variables que s3n elementos de la matriz Z y que se hallan

1c en la base c c i r r i e ~ t ~ E' , jcnto ecn 12 Cueva variable deteminada en la

sección =teriapr, nc pueden formar una red qae contenga un ciclo, ya que

e l l o no era c i e r t o para dichas variables b%icas , y ej . la variable nueva

cerrara el c ic lo , ésta tendrfe que ocupar un lugar para el que p. E q j J.

1-, por lo tanto, nc padpta hzlier sido seleccionada pzrz cntrar en la La-

sa. A f i n de constrr i ie lo nueva seudobaso sk'l es suficieate completar

esta a r b o r ~ c c c n c i a de rnh-2 arista8 a una con una arista m&, elegida ar-

bitrariamente entre laa pos ib l e s variables que no cíerran un ciclo con

las anteriores. For brevedad, E s t a variable adicional recibir5 e l nora-

brrl d c la variabie seud~55s;ca, pero en real idad ns es la Gnica en

,tc+l kv¡-1-, -üurique lo r s cn 3 i3

d>;Cs?cula 6r los can;F,ios las variables básicas

k+l Conociendo la seudabsse S se calculan rápidameate, como en el pa-

so inicial, lüs mabriscs 2 y zk'l, que deben cumplir con las eiuacio- X Y

ncn (S ) y ( 2 ) , re~pectivancnte, Como en el paso i n i c i a l , también se

determinan dx k f l k4-3. ki-1 kl-1 )h ; d~ - '% )hu , donde (h,u) se

rcf iere a l a variable seudcb~sica, y

El valor d e l nivel ea <LE deben ser incrementadas l a s variablcs eocarlí

dado par

(91 ,k+l n a l t : - z k = t D ~ 3 - 1 k

" A - Z )

de manera que

cumpla con las cotas impuestas por las primeras relaciones de (P). Nue-

vamente habra un par de subfndices (i,j) para lo^ cuales l a s restriccio-

nes que definen a tH1 son e£ ectivas. La variable correspmdieote es la

k k-l-1 que debe eer eliminada de la base B para convertirla en B , incorpo-

rando por supuesto la variable bh ica nueva determinada en el paeo b) . Si z resulta ser la variable que se intentaba introducir en la base, ee

i j

tendrá B k-kl = Bk

Como antes, se calculan l o s valores

y se repite la secuencia de operaciones d e l c ic lo t í p i c o desde el cwiien-

z o , una vez incrementado el valor de k en una unidad.

El lector puede verificar, que la secuencia de soluciones básicas

ea la misma que ee obtendrá de una aplicaciBn directa d e l método s imple

al problema (P); por lo t a n t o queda asegurada l a terminacih del aigoxit-

mo en un nGmero f i n i t o de c i c l o s , si se trata debidamente el problema de

bases degeneradas. La terminacih puede darse al alcanzar el Sptimo ea

e l paso 3 o por obtener un tk'' so en el paeo d ) , indicando una solu-

ci& exacta, es decir con error relativo nulo, del problema -inicial, por

ser proporcionales las sumas marginales de la matriz A y las d e la ma-

t r i z D deseada, Si b - 6 p

c = s 'd

la nnluci6n ser$ obvimente

6 A

€ = O Ej mplo numérico

Suphgase dada La matriz

con sumas marginales

siendo las sumas marginales de l a matriz D buscada

b' = (64 ,105 ,76 ) ; c (39,93,113) ; S = 245

Se desea calcular la matriz D que presente el menor desvSo relativo 6-

xiruo pos ible .

Iniciación - Debida a que la matriz A es pos i t iva , la determinacibn de la base

inicial es muy senci l la . La matriz 2' Y

se ha calculado de la siguiente manera, En primer lugar s e anotaron en

loa márgenes los to ta les , es decir, los vectores b y c. Comenzando

por la primera f i l a , se inscribid en el. mayor valor consistente con loa

totales de los márgenes, de modo de no excederlos. Asf se continud haata

agotar la primera f i l a . Luego se continub con lz segunda f i l a , para fina-

l i zar con la tercera, Esto procedimiento siempre produce una soluci6n bá-

sica, como ae sabe por el análisis de sistemaa de transporte, Los elemen-

O tos de l a base in ic ia l S , son los elementos posit ivo8 de la matriz asf

hallada,

Para calcular el valor inicial de y es necesario d i v i d i r cada ele-

o mento de A por el correspondiente de 2 señalado con un asterisco, dan-

Y do un valor

Ciclo O

La matriz

se calculb anotando en primer lugar los totciles marginales dados por los

vectores B y f. Como los elementos de SO corresponden a una base, es

siempre pos ib le llenar los distintos espacios de una mancra Gnica, con-

sistente con las sumas marginales y la condicidn de que los elemento^ no

básicos aean nulos. En este caso se ve de inmediato que hay un s o l o ele-

mento en la primera columna, de modo que &te debe igualar la suma de di-

cha columna. Restando este niímero del total de la primera f i l a e igno-

rando la primera columna en lo sucesivo, puede notarme que e8 ahora l a

primera f i l a la que contiene un solo elemento bssico, procediéndose a

anotar el total nuevo de la f i l a en ese lugar. Estas paso8 siempre pue-

den ser cumplidos, puesto que la red asociada con la base es una arbores-

cencia, de modo que, al @liminar aristas, siempre queda alguna -al menos

dos- inc idente en un nodo que no está ligado a otra arista.

Ai calcular yo se determin6 que uno de los elementos eeudobásicos

será v2 ; por lo t a n t o se fendr3.

I Aplicando (7) para calcular t se obtiene

1 señalándose con un asterisco el elemento de la matriz D correspondiente

a Pa variable que d c j a la base, ñecordando las f 6mulas correspondientes ,

se t iene

Ndtese que todas las variables tienen denominador carnGn& = 17. El deno-

mixador de t1 era 425 = 25 x 17; el factor 25 era el denominador contGaín

d e las variables antes de comenzar el ciclo. Este I i l t imo factor pudo

ser s impl i f icado , pues 20s numeradores resul tantea, después de aplicadas

ias f6mulas para efectuar el cambio de los valores de las variables, son

mÚltiplos d e l mismo. Esta propiedad se mantiene constantemente, y es una

consecuencia de l a casi triangularidad de la base, que garantiza que las

variables tomen valores racionales con denominadores que son deteminan-

tes de orden 2 formados con sumas marginales de las dos matrices, es

decir, con elementos de los vectores b, c,#3 y 6. Por o t r a parte debe no-

k k tarse que las matrices Z y Z se calculan, en cada ciclo, por medio de x Y

sumas y r e s t e , s iendo, por lo tanto, enteros si los datos originales son

k enteroa, Tambign la matriz D estar6 en ese caso formada por elementos en-

teros, Esta propiedad puede ser empleada para calcular la solucidn racio-

nal exacta al problema, como se hará con el ejemplo,

Ciclo 1

a) Precios

Recugrdese la matriz 2 1

1 que ha sido multiplicada por el denominador comGn para mayor cmodi-

dad. Loa elementos bgsicos han s i d o inscriptos en un clrculo, y en los

mfrgenes se han anotado los precios. Como en la primera fila no hay ele-

mento básico alguno, e l precio r corresponde Gnicamence a esa fila.

Del mismo modo el precio 8 correeponde Gnicamente a la primera columna.

En cambio el tercer grupo de fila6 y columnas corresponde a las f i l a s 2

y 3 y a las columnas 2 y 3 , que esth relacionadas entre sf por ser

b ás ieos los elementos zZ2 , z2 j, y =33* Por lo tanto les corresponde el

mismo precio , que se iguala a cero por comodidad -recuérdese que uno de

l o s precios puede ser asignado arbitrariamente. A fin de calcular x y

s se ut i l i zan las dos primeras ecuaciones de (D), bastando con reempla-

zar la unidad de la primera ecuación. por un niímero positivo arbitrario,

gracias a l a homogeneidad del. sistema de ecuaciones. Se tiene asf

que puede ser simplificad^ a

7 r > 4 s

64 r u39 s ,

sistema que tiene una s o l u c i h r e 39; s u 64

Reemplazando w y s por sus valores en (121, es p o s i b l e verificar

el cumplimiento de las condiciones (1). Se verd entmcea que Estas no se

cumplen para las combinaciones de subhdices I 1 , 2 ) ,(2,1), y (3,1), ya que

las relaciones entre los precios indican que e deberfa ser nula, mien- le

tras que zZ1 y z31 deberfen ser iguales i sus cotas superiores. En con-

secuencia se ha señalado en (12) el hecho de que ea necesario reducir a l

1 valor de r1 y aumentar l o s valores de z y .zi1 con Elecliae indicando 12 21

la dirección del cambio.

b ) Nueva variable b&ica

, Se elige al azar una de las tres variables cuyos vitiores son h-

consistentes cm l o s precios. En este caso se e i i g i d z21, aeñaiándola can

ua asterisco en (12).

c) Nueva seudobaae

Tres son las candidatas para la seudoba~e, 51,212, y z13, ya que

la^ otras dos variables no básicas, =31 Y 232' e s t h situadas de manera

de formar, con algunas de laa básicas, los vértices de un rect&gulo, in-

dicando la presencia de un ciclo en la red asociada. Arbitrariamente se

elige como seudobdsica a z13, de modo que

La variable aeudob~slca r lJ se ha inscr ipto en un cuadrado en (12).

d) Cambio de base

A continuaci6n se omiten l o s comentarios, por ser la secuencia de

las operaciones similar a las ya efectuadas.

. .

Ciclo 2 .' .

,Nota: igual base significa iguales precios

Ciclo 5

Nota: igual baae a ignif iea iguales precios que en el ciclo anterior,

Aquf todaa las condiciones (1) sobre las relaciones entre precios y valo-

res de lae variables se cumplen. Por lo tanto l a solucidn corriente es la

6 p t h a . El error relativo máximo es

y la matriz ajustada D es

D m (I/Y) (2 + X A)

mientras que el factor de escala es

REFERENCIAS BIBLIOGRAFICAS

Bacharach , M. O .L. "Estimating matrices f rwr marginal data" en Interna- t i o n a l Economic Review vol. 6 , nr, 3 , setiembre

Dantzig, G,B. Linear Programiw and extensions; Princeton Univer- sity , Press Princetun, 1963

Gale , D, The theory of Linear Ecoaomic Kodels, Mc-Graw - H i l l New York, 1960

P f t t s , P,R. ccef f icients l! en Ccinadim .Joumnb of-~eonomies and Sawyer, J.A. Political Science 30, 1964'pags.'203-210,

"L'ajustement periodique des sistemee de relatious interindustriellee, en ''Econometrica 32 (1963) p a e , 90-110.