articulo junaeb

REVISTA INGENIERA DE SISTEMAS VOLUMEN XV, NMERO 1, JUNIO 2001

13

Programacin Entera Mejora el Proceso deLicitacin de Raciones Alimenticias1

Rafael Epstein 2Lysette Henrquez 3

Jaime Cataln 4Gabriel Weintraub 5Cristin Martnez 6

Marzo, 2001

Resumen

En este trabajo se presenta la aplicacin exitosa del uso de un modelo matemticopara determinar la adjudicacin ptima en una licitacin de servicios de racionesalimenticias para colegios en Chile. El proceso involucra 180 millones de dlaresy la alimentacin de un milln trescientos mil nios aproximadamente, siendouna de las licitaciones estatales ms importantes en el pas. Para mejorar la cali-dad de la asignacin, se desarroll un modelo de programacin lineal entera quedecide la adjudicacin entre las distintas empresas concesionarias. El modelo cam-bi radicalmente la naturaleza del proceso en tres aspectos fundamentales. Prime-ro, dio transparencia y objetividad al proceso completo generando competenciaentre las empresas. Segundo, permiti a las firmas construir ofertas territorialmente

1 El artculo describe las experiencias realizadas en el proceso de licitacin de becas alimenticias de laJunta Nacional de Auxilio Escolar y Becas (JUNAEB) entre los aos 1997 y 2000, mientras los auto-res Epstein, Cataln y Weintraub eran consultores de JUNAEB y la institucin era dirigida por laSra. Lysette Henrquez primero y por el Sr. Ricardo Halab despus. Los autores agradecen a todo elequipo humano de JUNAEB involucrado en el proceso de licitacin, en especial a Rodolfo Aguayo yPablo Cspedes por el trabajo informtico y a Ana Mara Aburto y Germn Schultz por la constantecolaboracin. Las opiniones aqu expresadas son de los autores y no necesariamente representan aque-llas de JUNAEB.

2 Depto. de Ingeniera Industrial, Universidad de Chile. Repblica 701, Santiago [email protected]

3 Ex-Directora Nacional, Junta Nacional de Auxilio Escolar y Becas (JUNAEB),Chile. PNUD, [email protected].

4 Depto. de Ingeniera Industrial, Universidad de Chile. [email protected] Depto. de Ingeniera Industrial, Universidad de Chile. [email protected] Subdirector Depto. de Supervisin, JUNAEB, Chile. [email protected]

R. EPSTEIN, L. HENRQUEZ, J. CATALN, G. WEINTRAUB Y C. MARTNEZ PROGRAMACIN ENTERA MEJORA EL PROCEO DE LICITACIN DE RACIONES ALIMENTICIAS

14

flexibles para as incluir sus economas de escala, llevando a un uso eficiente delos recursos. Finalmente, el modelo encontr la solucin ptima, cuestin nada detrivial si se considera que el problema de asignacin es NP-completo y tiene alre-dedor de 5000 variables enteras. Esta nueva metodologa, enmarcada en un nuevoproceso de licitacin, mejor notablemente la razn precio-calidad de las racionesalimenticias, generando ahorros en tres aos de US$ 40 millones, equivalentes alcosto de alimentar 115.000 nios durante el mismo perodo.

1 Introduccin

Chile es un pas en vas de desarrollo cuyo sistema educacional est formado por14.000 colegios a lo largo de las 13 regiones geogrficas del pas. El 91 % de lacobertura escolar es financiada total o parcialmente por el Estado, encargndosede entregar la educacin a los nios provenientes de los sectores con menos recur-sos del pas. El 30 % de la poblacin menor a 18 aos vive bajo la lnea de pobreza.Un factor fundamental para hacer efectiva la igualdad de oportunidades es suplirlas carencias de los nios y jvenes provenientes de los sectores socioecon-micamente vulnerables, a travs de programas asistenciales orientados a otorgaralimentacin complementaria para reducir el ausentismo y desercin escolar ymejorar el rendimiento escolar, adems de programas de salud, vivienda estu-diantil y recreacin (Henrquez (1999)).

La Junta Nacional de Auxilio Escolar y Becas (JUNAEB), servicio pblicodel sector educacin, es la responsable de brindar estos programas asistenciales.En particular, su objetivo fundamental consiste en entregar la alimentacin a losalumnos durante su jornada escolar (desayuno, almuerzo, merienda y cena segncorresponda). sta se brinda en los diferentes colegios con cobertura nacional sincosto para los estudiantes. El presupuesto anual de JUNAEB para programas esde 150 millones de dlares (al ao 2000), de los cuales 138 se gastan en el Progra-ma de Alimentacin Escolar (PAE), entregando servicios alimenticios a un millndoscientos mil nios aproximadamente. Esto incluye el programa de alimenta-cin regular adems del programa de vacaciones y algunos programas dereforzamiento del Ministerio de Educacin.

En el ao 1980, JUNAEB externaliz los servicios alimenticios a empresasconcesionarias, licitando el servicio de raciones alimenticias de los diferentes cole-gios. En el ao 1980 slo participaron tres empresas, aumentando a treinta en ladcada del noventa y actualmente el nmero de empresas participantes es de 26.

JUNAEB tiene un importante poder de negociacin frente a las empresasconcesionarias debido a los enormes volmenes de alimentos que demanda. Ade-ms posee una vasta experiencia en el rubro, por lo cual tambin administra losprogramas de alimentacin de JUNJI e INTEGRA, instituciones sociales encar-gadas de la alimentacin de los jardines infantiles del pas. La cobertura de am-bas instituciones es de 126.000 nios y su presupuesto anual es de 46 millones de


15

dlares. De esta manera, actualmente, JUNAEB totaliza compras al sector ali-mentos por 184 millones de dlares anuales, para brindar servicios a 1.326.000nios aproximadamente.

Cada ao se licitan los servicios de raciones alimenticias correspondientes aun tercio del pas por un perodo de tres aos. Los montos involucrados en lalicitacin son del orden de 180 millones de dlares, siendo una de las ms grandespara el estado chileno.

Esta es una licitacin de alimentacin escolar administrada por una insti-tucin (JUNAEB), pero que est dirigida a tres instituciones (JUNAEB, JUNJI eINTEGRA), por lo tanto en su adjudicacin requiere conciliar distintos puntos devista institucionales. Adems, entre sus complejidades, est que representa unservicio de alimentacin diario que se licita a tres aos, pero que puede verseafectado por diversos escenarios bastante cambiantes derivados del largo perodode contrato considerado. Por ejemplo, puede variar la cantidad de raciones ali-menticias que deben ser brindadas, como tambin la estructura alimentaria delas distintas raciones, debido a nuevos requerimientos nutricionales.

Los beneficiarios son muy diferentes (sus edades fluctan entre 2 y 24 aos),lo que implica que en la licitacin se debe incluir una gran variedad de raciones yservicios de alimentacin. De esta manera, el equipo de nutricionistas de JUNAEBha definido una variedad de productos que deben ser cotizados por las empresas.Por ejemplo, un almuerzo de 850 caloras para enseanza media, con sus requeri-mientos nutricionales definidos y la frecuencia de determinados alimentos comocarne, pescado y verduras; un desayuno de 350 caloras para enseanza bsica,etc.. As, una oferta de una empresa debe incluir el territorio geogrfico al cualpostula y un precio para cada uno de estos 168 productos. En una licitacin sepresentan alrededor de 4500 de estas ofertas, por lo cual el anlisis de todas lascombinaciones posibles es altamente complejo.

A pesar de la gran cantidad de dinero involucrado y de la complejidad delproblema, hasta el ao 1997, la asignacin se realizaba utilizando criterios subje-tivos, bastante rudimentarios. Bsicamente, se aplicaban una serie de filtros su-cesivos basados en criterios financieros y tcnicos, descartando posibles asigna-ciones. As, de manera iterativa se reduca el tamao del espacio factible hastaobtener una solucin, supuestamente de buena calidad. Dado el gran tamao dela licitacin, la solucin obtenida era claramente subptima y, ms an, fcilmen-te se generaban presiones indebidas sobre los funcionarios responsables deJUNAEB, de parte de las empresas. En este tipo de negociaciones es fundamentaladjudicar utilizando mtodos objetivos para dar transparencia al proceso. De estamanera, se reduce la posibilidad de que existan presiones ilcitas y se obliga a lasempresas a competir va calidad y precios (Milgrom (1989)).

Conocidos estos antecedentes, en el ao 1997, la direccin de JUNAEB leencarg a un equipo de ingenieros de la Universidad de Chile el diseo eimplementacin de un nuevo mecanismo de asignacin para la licitacin del ser-vicio de raciones alimenticias. En este trabajo se muestra el desarrollo eimplementacin de este nuevo mecanismo, en el cual se utiliza un modelo de pro-


16

gramacin lineal con variables binarias para asignar en forma ptima un procesode licitacin a las distintas empresas oferentes. Esta herramienta fue utilizadaexitosamente en la licitacin de alimentos escolares del ao 1997, repitindose laexperiencia en las licitaciones siguientes de los aos 1999 y 2000. En estas dosltimas licitaciones, la metodologa fue mejorada introduciendo mayor flexibili-dad. As, fue posible analizar posibles escenarios que podran darse a lo largo delperodo de contrato considerado (tres aos), pero cuyas definiciones deben seranuales, encontrando una solucin robusta frente a los distintos escenarios.JUNAEB pretende seguir utilizando esta metodologa en los futuros procesos delicitacin.

La introduccin de herramientas matemticas fue determinante para reali-zar un proceso de negociacin limpio y transparente, generando competencia en-tre las empresas. Adems, el modelo permiti capturar las economas de escalaexistentes para las firmas participantes. Finalmente el modelo llev a una asig-nacin ptima de los recursos. De esta manera, fue posible licitar el servicio deraciones alimenticias de la forma ms ventajosa posible, aspecto fundamental sise considera que en este proceso se compromete la calidad de la alimentacin dealrededor de un milln trescientos mil nios en Chile, muchos de los cuales basansu nutricin en la comida recibida en los colegios.

2 El Proceso de Licitacin

Para efectos de la licitacin el pas se divide aproximadamente en 90 unidadesterritoriales (desde ahora U.T.). Es decir, en promedio, cada una de las 13 regio-nes geogrficas del pas se divide en 7 U.T.. Se licita un tercio de ellas cada aopor un perodo de tres aos.

El proceso empieza con el llamado y registro de empresas, donde JUNAEBlas clasifica desde el punto de vista administrativo, tcnico y financiero. Estopermite, por una parte descartar empresas que no cumplen con los estndaresmnimos de confiabilidad y, por otra, clasificarlas de acuerdo a sus capacidades.Existen dos clasificaciones:

Segn su capacidad financiera y operativa, las empresas se clasifican encinco categoras distintas de acuerdo a la cantidad mxima de U.T. a las quepueden aspirar.

Segn las evaluaciones tcnicas realizadas, las empresas obtienen una cali-ficacin global de desempeo, la que puede utilizarse en el modelo de asig-nacin como se ver ms adelante.

Luego se realiza el llamado pblico a la licitacin y la venta de bases. Poste-riormente las empresas concesionarias (que son alrededor de 26) presentan susofertas. Lo hacen de manera electrnica, en diskette, el cual recibe una codifica-cin y la relacin nombre-cdigo de la empresa queda en Notara, por lo tanto noes conocido por los evaluadores hasta el momento de la adjudicacin.


17

Las ofertas de las empresas incluyen un proyecto tcnico y las ofertas eco-nmicas. El proyecto tcnico presentado por las empresas se basa en los requeri-mientos establecidos por JUNAEB, entre los cuales destacan:

Los nutricionales, en que las diferentes raciones deben cumplir con sus res-pectivas definiciones nutricionales.

Los de estructura alimentaria, donde se sealan los tipos de servicios (al-muerzo, desayuno, etc.) y la frecuencia o presencia mnima y mxima dedeterminados alimentos y los requisitos de variedad mnima en las prepa-raciones.

Los insumos y sus caractersticas mnimas de calidad.

Las condiciones de operacin: higiene, abastecimiento, manipulacin, su-pervisin, etc.

Los requisitos de infraestructura: mobiliario, equipo y vajilla, etc.

JUNAEB evala si cada empresa cumple o no con los requisitos solicitados.Las ofertas de las empresas que califican exitosamente las pruebas anterioressiguen participando en la licitacin y compiten va precios, a travs de las ofertaseconmicas. La forma de licitar cumple con las recomendaciones del Banco Mun-dial para dar garantas de transparencia: primero definir barreras tcnicas paraasegurar que los requerimientos mnimos sean satisfechos y luego adjudicar porprecio. La calidad de servicio se puede regular aumentando las barreras tcnicas.

Cada oferta econmica presentada por las empresas concesionarias incluyeun conjunto desde 1 a 8 U.T. a cubrir, resguardando el lmite mximo que le per-mite la clasificacin respectiva. Las empresas presentan tantas ofertas como quie-ran y cada oferta se acepta o rechaza por completo, es decir, no es posible aceptarfracciones de ofertas. Por ejemplo, si una empresa presenta una oferta que inclu-ye 5 U.T., el paquete completo se acepta o se rechaza, pero no es posible aceptar laoferta por slo 3 de las 5 U.T.. Si cierta oferta de una empresa es aceptada, signi-fica que la empresa debe brindar todos los servicios de raciones alimenticias enlas U.T. correspondientes a esa oferta.

Al permitir ofertas que sean paquetes de U.T. se busca aprovechar las eco-nomas de escala que puedan tener las empresas al brindar un mayor nmero deprestaciones. Es decir, el precio de una oferta que contiene las U.T. X e Y, proba-blemente ser inferior a la suma de los precios de ofertas separadas e individua-les por las mismas dos U.T.. Las economas de escala aparecen por varios moti-vos: infraestructura comn que utilizan U.T. cercanas, descuentos por volumenen la compra de insumos, transporte ms eficiente, mejor uso del personal, etc..

En general, las empresas presentan muchas ofertas, que van desde ofertaspequeas de una sola U.T. a ofertas ms abultadas las cuales incluyen variasU.T.. La presentacin de ofertas constituidas por paquetes de U.T. lleva a que elproblema de asignacin sea combinatorial y su solucin no trivial. En efecto, elproblema resultante contiene problemas combinatoriales clsicos tales como cu-brimiento, multi-knapsack y localizacin, todos ellos pertenecientes a la clase NP-completo (Nemhauser y Wolsey (1988)). El uso de herramientas matemticas per-


18

miti resolver ptimamente este difcil problema combinatorial, haciendo posibleaprovechar las economas de escala existentes para las firmas y reduciendo as, elcosto total de la asignacin.

En cada oferta las empresas deben cotizar 168 productos, correspondientesa diferentes productos definidos por el equipo de nutricionistas de JUNAEB y delas otras dos instituciones participantes. En primer lugar, dado los diferentesservicios brindados, existen treinta tipos de raciones alimenticias, en que cadauna establece el nmero de caloras a brindar y requerimientos nutricionales es-pecficos. Por ejemplo, la racin B350 es un desayuno para enseanza bsica de350 caloras; la racin M1000 es un almuerzo para enseanza media de 1000 ca-loras.

Para cada una de estas raciones, las nutricionistas han definido tres estruc-turas alimentarias referentes a diferentes combinaciones de alimentos posiblespara alcanzar el nmero de caloras determinado en cada racin. Las estructurasalimentarias son de distinta calidad, con lo cual JUNAEB puede cotizar una va-riedad de productos, unos mejores que otros. Por ejemplo en un almuerzo de 650caloras una estructura alimentaria establece diez veces carne al mes (vacuno,pollo, pavo, cerdo o cordero en distintas formas), dos veces legumbre y cuatroveces pescado al mes; mientras que otra alternativa de estructura alimentariaestablece catorce veces carne al mes, una vez legumbre y cuatro veces pescado almes. Es decir, cada producto es una racin alimenticia perfectamente definidapor el equipo de nutricionistas de JUNAEB, en que se establece el nmero decaloras a brindar, los requerimientos nutricionales y la frecuencia de alimentosrequeridos. En cada oferta, las empresas deben ofrecer un precio para cada unode estos productos.

Los precios ofertados corresponden al nivel de demanda del 100 %, es decir,cuando se brinda el nmero de raciones alimenticias planificadas. Adems, lasempresas piden un precio ms alto por racin, si la demanda baja a un 80 % y unprecio an mayor si baja a un 60 %. As, se disminuye el riesgo al cual estnexpuestas las empresas debido a una menor cobertura (huelga de profesores, epi-demia de alguna enfermedad, etc.), llevando a una disminucin de los preciosofertados para la demanda base del 100 %, que es el escenario ms relevante yprobable. Por otro lado, las empresas pueden ofrecer un descuento si el nivel dedemanda supera un 104 %, en caso que aumente el nmero de alumnos o se ex-tienda la jornada escolar. Este descuento es un porcentaje parejo por racin.

De esta manera, una oferta econmica incluye:

Las U.T. a las cuales postula.

Los precios correspondientes a treinta tipos de raciones en que cada unaestablece un nmero de caloras a brindar. Para cada una de estas racionesse cotizan precios referentes a tres diferentes alternativas de estructurasalimentarias (escenarios tipo A). Adicionalmente, se incluyen la racionesbrindadas por JUNJI e INTEGRA.


19

Para cada combinacin racin-estructura alimentaria mencionada en lospuntos anteriores, se presentan tres precios distintos, uno para cada nivelde demanda. Adems se ofrece un descuento por racin si el nivel de deman-da crece (escenarios tipo B).

De esta manera, considerando las diferentes raciones, estructurasalimentarias y niveles de demanda se llega a 168 precios (algunas combinacionesno existen). En la Figura N1 se presenta una muestra de una parte del Formula-rio nico de Oferta Econmica que deben llenar las empresas por cada oferta quepresentan.

Figura 1: Muestra de parte del Formulario nico de Oferta Econmica. Por cada oferta que presentan,las empresas deben incluir el cdigo de las U.T. ofertadas, los precios correspondientes a cada racin

alimenticia (B250, B350, etc.) y a cada estructura alimentaria (1, 2 o 3),segn el tramo del nivel dedemanda correspondiente (100-80, 80-60 o < 60). Adicionalmente, se incluye el descuento por racin

si el nivel de demanda supera el 104 %.

El costo total de una oferta, dada una estructura alimentaria y nivel dedemanda, depende del nmero de raciones de cada tipo a brindar en cada U.T., elcual depende de la poblacin escolar. El equipo de nutricionistas de JUNAEBdetermin dos composiciones diferentes del nmero de raciones de cada tipo abrindar en cada U.T., llamadas Maestros (escenarios tipo C).

El Maestro 1 establece, por ejemplo, que en la U.T. X se brindan 20.000raciones diarias B250, 15.000 raciones diarias B700, etc.; mientras que el Maes-tro 2 establece que se deben brindar 20.000 raciones diarias B250, 15.000 racio-nes diarias B800, etc.. En general, el Maestro 2 considera raciones con un mayornmero de caloras que el Maestro 1, algunas de las cuales no se brindan en elactual Programa de Alimentacin. Por ejemplo, el Maestro 2 considera almuerzosde 1200 caloras para cierto segmento de estudiantes de enseanza media, mien-tras que el Maestro 1 considera almuerzos de 1000 caloras para el mismo seg-mento. Para un Maestro dado y conociendo los 168 precios de una oferta y las U.T.que cubre, se puede valorar el costo total de una oferta para una estructura


20

alimentaria y nivel de demanda determinados. Para ello, se deben multiplicar losprecios unitarios de cada producto por las cantidades establecida en el Maestro yrealizar la suma total.7

3 Modelo Matemtico de Asignacin

El objetivo es escoger una combinacin de ofertas (de un total de 4500 ofertasaproximadamente que son candidatas a ser aceptadas) para cubrir todas las U.T.a costo mnimo. La asignacin ptima se sensibiliza utilizando dos funciones ob-jetivo distintas: i) considerando slo el costo asociado a JUNAEB; ii) consideran-do el costo de las tres instituciones juntas (escenarios tipo D).

La calificacin global de desempeo obtenida por las empresas segn lasevaluaciones tcnicas (Seccin 2) puede ser considerada en la asignacin de lasiguiente manera. Los precios de las ofertas de las empresas con mejor califica-cin son reducidos por un factor, privilegindolas en la adjudicacin por sobre lasofertas de empresas con peor desempeo. Tambin se sensibilizan las asignacio-nes ptimas con y sin utilizar la correccin por el factor de desempeo (escena-rios tipo E).

Adems, se deben considerar las restricciones adicionales del problema, las

que se detallan a continuacin:

Para evitar una concentracin excesiva, que hace ms vulnerable el progra-ma, se limita el nmero mximo de U.T. que pueden ser asignadas a unaempresa. Cada empresa tiene un lmite distinto que depende de su capaci-dad financiera y operativa (Seccin 2).

En la misma lnea y para fomentar la diversificacin en el sistema, se limitael nmero de ofertas de una misma empresa que pueden ser aceptadas (res-tricciones tipo F).

Se impone un nmero mximo de empresas que pueden ser asignadas acada una de las regiones geogrficas del pas, de modo de facilitar la opera-cin de JUNAEB en relacin a los mecanismos de control y supervisin so-bre ellas (restricciones tipo G1).

Por otro lado, se restringe el nmero mnimo de empresas por regin parapoder controlar imprevistos. De esta manera, si alguna empresa falla poralgn motivo, sus servicios pueden ser suplantados temporalmente por otraempresa que est operando en la misma regin (restricciones tipo G2).

Slo se consideran las ofertas que caen dentro de una banda de precios pre-determinada, eliminando a-priori ofertas de muy bajo costo que sonirrealistas. Este sera el caso de empresas que probablemente han subesti-

7 El modelo matemtico descrito a continuacin, su posterior resolucin e implementacin y los resul-tados obtenidos corresponden a la licitacin del ao 1999.


21

mado sus costos y al presentar costos tan bajos resultaran ganadoras en lalicitacin. Ofertas de tan bajo costo llevaran a una reduccin de la calidad ya incumplimientos del contrato por parte de la empresa, problemas queJUNAEB prefiere prevenir (restricciones tipo H).

La adjudicacin ptima se sensibiliza incluyendo o sin incluir cada una delas restricciones anteriores (F, G y H), de modo de cuantificar el costo monetarioasociado a imponer cada una de ellas. Slo la restriccin referente a un nmeromximo de U.T. por empresa es impuesta siempre. Adems, se consideran losdistintos escenarios correspondientes a diferentes estructuras alimentarias (A),los niveles de demanda (B), los dos Maestros (C), las dos funciones objetivo (D) yel factor de desempeo (E). De esta manera, realizando el cruce entre todas lasvariaciones posibles (algunos no existan), se generaron 704 escenarios a anali-zar, los que se resumen en la Figura N 2.

Figura 2: Se analizaron diversos escenarios correspondientes a los siguientes cruces,lo que gener 704 instancias del modelo.

Para encontrar la asignacin ptima en cada uno de estos escenarios se for-mul un modelo de programacin lineal con variables binarias. Se define unavariable binaria por cada oferta, en que la decisin es si aceptar o no la oferta.Adems, se define un conjunto de variables binarias auxiliares utilizadas en lasrestricciones que limitan el nmero de empresas por regin. De esta manera, elmodelo incluye 4600 variables binarias.

El modelo contiene varios problemas combinatoriales clsicos como el pro-blema de cubrimiento, multi-knapsack y localizacin, todos ellos NP-completos.Es decir, nuestro problema de asignacin pertenece a la clase de problemascombinatoriales ms difciles de resolver.

La cantidad de instancias del modelo a resolver era 704 y dado los plazosexistentes el tiempo para hacerlo escaso, por lo cual era importante que la resolu-cin de cada instancia tomar un tiempo pequeo. Por ello, y dada la potencialcomplejidad del problema, se agregaron restricciones al modelo de modo de forta-lecer la relajacin lineal de la formulacin. En primer lugar, se agregaron planosde corte, conocidos como packing para robustecer la relajacin lineal del proble-ma entero.

Adicionalmente, para algunas instancias se desacopl un conjunto de res-


22

tricciones. Esta tcnica de fortalecimiento, frecuente en modelos de localizacinno capacitados, nos entreg un modelo expandido con mejor relajacin linealque el original, pero de mayor tamao. La idea consista en que la formulacinexpandida requera menos iteraciones en la etapa de ramificacin y acotamien-to pero cada iteracin era ms costosa en tiempo porque el modelo era mayor.Esta formulacin se utiliz en las instancias ms difciles con buenos resultados.

El modelo fue programado en FORTRAN 90 y fue resuelto utilizando el pro-grama computacional CPLEX en un computador Pentium III. Se resolvieron las704 instancias del modelo, cada una en menos de tres minutos, para lo cual fue-ron necesarios los cortes de packing, y en algunos casos, la formulacin expan-dida. En el Apndice se describe en detalle el modelo de programacin lineal ente-ra utilizado para encontrar la asignacin ptima de ofertas en cada una de lasinstancias del modelo analizadas.

4 Resolucin e Implementacin

Al resolver las diferentes instancias del modelo fue posible encontrar las solucio-nes ptimas para los distintos escenarios, lo que le permiti a la Comisin deAdjudicacin de JUNAEB evaluar diferentes escenarios, como tambin la calidady robustez de las soluciones.

Por ejemplo, se determin el costo total de aumentar la calidad de las racio-nes alimenticias. Para ello, se compar el valor de la funcin objetivo en el ptimopara los escenarios correspondientes a las diferentes alternativas de estructurasalimentarias (A). Tambin se encontr el costo asociado a brindar nuevos tipos deraciones con mayor peso calrico, para lo cual se analizaron las soluciones pti-mas de los dos Maestros (C).

Al comparar las soluciones ptimas considerando las dos funciones objetivo(slo JUNAEB o las tres instituciones) se encontr el costo que le significa aJUNAEB incluir a JUNJI e INTEGRA en la licitacin (D). Al mismo tiempo, sedetermin el costo de las soluciones ptimas asociado a JUNAEB y el costo aso-ciado a las otras dos instituciones. Estas cifras son de mucha importancia porquele permiten a las respectivas instituciones saber si estn dentro de su presupues-to y si deben exigir al gobierno un aumento del mismo.

Adems fue posible saber cunto vale realizar una asignacin menos riesgosacon empresas que tengan mejor calificacin de desempeo (E). Tambin se deter-min el aumento del costo de la solucin al limitar el nmero de ofertas por em-presa, de modo de diversificar la asignacin (F). Asimismo se obtuvo el costo aso-ciado a limitar el nmero de empresas por regin (G) y el asociado a descartar lasofertas que salen de la banda de precios (H).


23

Adicionalmente, el objetivo era implementar una solucin robusta para losdistintos escenarios bajo anlisis. Por ejemplo, se verific la consistencia en elcomportamiento de la solucin ptima para el escenario en el cual se considera el100 % de demanda y cuando el escenario efectivo es una demanda de solamente el80 % de lo presupuestado (B). Adems, es til saber que tan robusta es la solucincon respecto a las distintas alternativas de estructuras alimentarias, debido aque la asignacin puede realizarse considerando una estructura determinada y alao siguiente sta puede ser cambiada.

El anlisis recin mencionado fue llevado a cabo mediante la construccinde tablas con informacin estadstica considerando las soluciones de las diferen-tes instancias del modelo. Por ejemplo, se hicieron tablas que permitan analizarel desempeo de la solucin ptima de una instancia, si el escenario efectivo erauno distinto. Esta informacin fue estudiada por la Comisin de Adjudicacin deJUNAEB para realizar la asignacin de la licitacin.

En primer lugar, la Comisin decidi que la funcin objetivo a utilizar era laque inclua las tres instituciones participantes, ya que se deseaba maximizar elbeneficio social y no slo el de una institucin en particular. Luego se decidi anali-zar solamente las soluciones correspondientes al Maestro 1 y a dos alternativas deestructuras alimentarias, ya que el resto exceda notablemente el presupuesto delas instituciones. De esta manera quedaron 128 instancias a analizar. Despus secompararon estas dos alternativas de men decidiendo brindar la ms econmica,la cual era aproximadamente 2,5 millones de dlares ms barata por ao. La Comi-sin de Adjudicacin determin que la diferencia de costo era demasiado alta, con-siderando que los mens no diferan demasiado en cuanto a su calidad.

Luego se determin que la institucin estaba dispuesta a pagar por tenerempresas con mejor calificacin de desempeo. Un costo total slo un 4 % mayorentregaba una solucin con empresas, en promedio, 40 % mejor calificadas lo cualera altamente conveniente. Tambin se decidi exigir las restricciones de lmitede ofertas por empresa y lmite de empresas por regin. El costo extra total co-rrespondiente a estas dos exigencias era de 800 mil dlares anuales, costo que lainstitucin estuvo dispuesta a pagar por una asignacin ms robusta. Por ltimo,se decidi no considerar la restriccin de banda de precios, ya que slo dos ofertasquedaban fuera de la banda en la solucin escogida y el costo era aproximada-mente un milln de dlares menor que el correspondiente a la solucin conside-rando la banda de precios. As, se escogi una asignacin que incluye a nueveempresas, cada una con una oferta y que tiene un costo anual de 60 millones dedlares para el sistema total y de 45 millones para JUNAEB. La solucin obteni-da era la ptima para el nivel de demanda correspondiente al 100 %. Sin embar-go, se verific que era muy robusta en relacin a los otros niveles de demanda eincluso a otras estructuras alimentarias (estaba a menos del 0,1 % del ptimo enlos otros escenarios).

Todo este proceso, que incluye la evaluacin de cada escenario y la confec-cin de las estadsticas, se debi realizar en una semana debido a los plazos lega-les permitidos en el proceso.


24

5 Resultados Obtenidos y Conclusiones

La utilizacin de un modelo matemtico para realizar la asignacin en la licita-cin del servicio de raciones alimenticias, en conjunto con otras medidas destina-das a mejorar la gestin de JUNAEB, llevaron a una serie de notables mejoras. Alcomparar la licitacin del ao 1999 (asignada con modelo matemtico) con la re-emplazada, correspondiente al ao 1995 (asignada sin modelo), se observa unamejora sustancial de la calidad de los aportes nutricionales, de la estructuraalimentaria de las raciones, de la infraestructura de los servicios de alimentaciny de la condicin laboral de las manipuladoras en las escuelas. Una comparacindetallada de las caractersticas de las licitaciones de 1995 y 1999 se encuentra enla Figura N 3. Todas estas mejoras representan un incremento de costos de 24 %en relacin a 1995 (en trminos reales), sin embargo, el precio de la racin prome-dio slo se increment en un 0,76 %. Lo esperado, de acuerdo a la tendencia, hu-biera sido un incremento a lo menos de un 22 % en el precio. Si consideramos lostres aos que dura la licitacin, el ahorro asciende a aproximadamente 40 millo-nes de dlares en todo el perodo, lo que equivale a la alimentacin de 115.000

nios por tres aos.

La cobertura de JUNAEB aument desde 1995 hasta el ao 2000, de 870.000nios a 1.200.000 nios. Adems, segn varias encuestas realizadas, se observque la satisfaccin de los estudiantes con respecto a la calidad de la alimentacinse mantuvo en un alto nivel. Por ltimo, se debe notar que el ao 1997, en el cualse introdujo el modelo matemtico para realizar la asignacin, fue un punto deinflexin en el mejoramiento del proceso de licitacin. En efecto, a pesar de que elpresupuesto de JUNAEB decreci en un 1 % en relacin al ao 1996, la cobertura

aument en un 8% (Crdova (1999)).

La utilizacin del modelo matemtico para realizar la asignacin llev a

estos sobresalientes progresos y ahorros debido a que:

1. Es un mtodo de decisin objetivo y transparente, reduciendo la posibilidadde que se generen presiones indebidas de parte de las empresas involucradas.En efecto, el mecanismo hace que las decisiones sean ms objetivas y losresultados obtenidos absolutamente replicables, pudiendo ser mostrados ala opinin pblica cuando sean requeridos.

2. Es un mecanismo de adjudicacin justo, imparcial y confiable, lo cual gene-ra competencia entre las empresas obligndolas a aumentar su eficiencia yproductividad. As, las empresas mejoraron la calidad del servicio entrega-do, a un menor precio y an as teniendo utilidades. En efecto, las utilida-des promedio sobre ventas de las empresas aumentaron desde un 3,2 % en1995 hasta 4,9 % en 1999. Las utilidades promedio sobre capital propio au-mentaron desde 28% en 1995 hasta 38 % en 1999, lo que demuestra el au-mento en la inversin realizada por las empresas.


25

Figura 3: Comparacin de las licitaciones de 1995 y 1999 en relacin a los aportes nutricionales,la estructura alimentaria, la infraestructura de los servicios de alimentacin y la condicin laboral de las

manipuladoras en las escuelas.

3. El modelo permiti formular y resolver de manera ptima el problemacombinatorial que se genera al permitir que las ofertas sean paquetes deU.T.. De esta manera, fue posible capturar y sacar provecho de las econo-mas de escala existentes para las empresas, tales como ahorros por trans-porte, descuentos por volumen, etc..

4. En cada escenario se obtiene la combinacin de ofertas que minimiza el cos-to, satisfaciendo todas las restricciones. Dada la gran cantidad de ofertas,esto sera imposible de realizar manualmente y en caso de hacerlo, proba-blemente se incurrira en prdidas considerables. En efecto, si se escogemanualmente una asignacin 2 % peor a la solucin ptima, lo que ocurrefcilmente si no se utiliza una herramienta de solucin adecuada, la prdi-da alcanzara los tres y medio millones de dlares, que equivale a las racio-nes alimenticias de treinta mil nios por un ao.

5. Utilizando el modelo matemtico, rpidamente se pueden obtener las solu-ciones ptimas para diferentes escenarios. En este sentido, creemos que las


26

tablas de informacin estadstica construidas a partir de las soluciones delas distintas instancias del modelo fueron de gran ayuda para encontrar lamejor solucin, sobretodo en la reunin de la Comisin de Adjudicacin deJUNAEB. Esta informacin permiti valorar los costos y beneficios de cadaescenario. As se pudo determinar el costo de las diferentes asignacionespara cada una de las instituciones participantes y el costo para JUNAEBcorrespondiente a incluir a JUNJI e INTEGRA en la licitacin. Tambin sedetermin el costo de imponer restricciones operacionales, de considerar unabanda de precios y de exigir empresas de mejor calidad. Se evalo el costode brindar mens con mejor estructura alimentaria y mayor peso calrico.Adems se verific la robustez de la solucin obtenida frente a distintasestructuras alimentarias y niveles de demanda.

De esta manera, la solucin asignada es ptima en la relacin precio-cali-dad y robusta frente a los posibles escenarios, lo cual es muy relevante en unproblema de esta complejidad y que involucra montos de dinero tan elevados.

En el aspecto del modelo y su implementacin se puede sealar que las dosformulaciones alternativas con los planos de corte fueron efectivas para resolvertodas las instancias del modelo. Debemos mencionar que sin los fortalecimientosque introdujimos, algunas instancias no se podan resolver en los plazos existen-tes. Esto no es de extraar si observamos que el problema es claramente NP-completo: contiene los problemas de cubrimiento, multi-knapsack y localizacin.

La evidencia ms clara del xito de esta aplicacin est en el hecho de queuna vez realizada en 1997, fue llevada a cabo nuevamente en los aos 1999 y2000. Adems, se seguir utilizando en los futuros procesos de licitacin. Un as-pecto fundamental a destacar es que en las experiencias realizadas se estableciuna metodologa a utilizar en cualquier licitacin futura, ya sea en este mbito oen otro similar. De hecho, la misma metodologa fue utilizada en dos licitacionesde lentes pticos realizada por JUNAEB por dos millones de dlares cada una.

Adicionalmente, el hecho de repetir el uso de la metodologa ha permitidomejorar y sofisticar el sistema. Es as como desde la licitacin del ao 1999 seampli el anlisis de escenarios. Tambin, en la licitacin del ao 2000 se cambila restriccin del mximo nmero de ofertas por empresa por una restriccin demnimo nmero de empresas en la asignacin. De esta manera, se introdujo almodelo en una forma ms conveniente (aprovechando la flexibilidad que entregala presentacin de mltiples ofertas) una restriccin que asegura la diversifica-cin en la adjudicacin.

Este es un ejemplo de una aplicacin exitosa de investigacin operativa en unmbito de gran impacto social. En los pases en vas de desarrollo, los programassociales realizados por el Estado representan una proporcin significativa del pre-supuesto de la Nacin. Sin embargo, con frecuencia, las decisiones involucradas ensu desarrollo se toman utilizando criterios muy precarios. Este caso muestra que esposible utilizar herramientas sofisticadas para la toma de decisiones en este tipode problemas, incluso en ambientes en que nunca se haban utilizado. Esto es fun-damental si se considera que reducciones de costos en algunos puntos porcentuales


27

por optimizacin pueden ser substanciales en valor. Creemos que los profesionalesde investigacin operativa pueden ser fundamentales en esta direccin, para locual es primordial difundir la potencialidad de las herramientas matemticas en latoma de decisiones dentro de los ejecutivos de este tipo de instituciones.

6 Apndice: Modelo Matemtico

Parmetros

R: conjunto de regiones geogrficas del pas.

I: conjunto de unidades territoriales.

K: conjunto de empresas participantes.

J: conjunto de ofertas presentadas.

cj(estralim, niveldda, maestro, F.O.): costo de la oferta j para estructuraalimentaria, nivel de demanda y Maestro dados, dependiendo de la funcinobjetivo utilizada (JUNAEB o tres instituciones).

cjbanda(estralim, niveldda, maestro, F.O.) : costo correspondiente a la banda de pre-

cios de la oferta j para estructura alimentaria, nivel de demanda y Maestrodados, dependiendo de la funcin objetivo utilizada.

PONDk: ponderador de la empresa k, de acuerdo a su calificacin global de desem-peo. Si la evaluacin se realiza sin considerar la calificacin, el ponderadorser uno.

e(j): empresa que presenta oferta j.

u(j): conjunto de unidades territoriales incluidas en oferta j.

oer(k,r) : conjunto de ofertas presentadas por la empresa k que incluyen U.T. per-tenecientes a la regin r.

MAXuniemp(k): lmite mximo de U.T. aceptables para la empresa k. Lmite de-pende del tamao de la empresa y toma valores entre 1 y 8.

MAXofeemp(k): lmite mximo de ofertas aceptables para la empresa k. Lmite sefija igual a uno.

MINempreg(r): lmite mnimo de empresas aceptables en regin r. Lmite depen-de de la regin pero en general es cercano a 2.

MAXempreg(r): lmite mximo de empresas aceptables en regin r. Lmite depen-de de la regin pero en general es cercano a 4.


28

Variables

Funcin Objetivo

Minimizar el costo total de la asignacin para estructura alimentaria, nivel dedemanda y Maestro dados, dependiendo de la funcin objetivo utilizada (JUNAEBo tres instituciones) y de si se considera o no la calificacin global de desempeoen la asignacin.

Restricciones

(1) Todas las unidades territoriales deben ser cubiertas.

(2) Lmite de unidades territoriales asignadas a cada empresa.

(3a) Clculo de variables Ykr.

(3b) Clculo de variables Ykr.


29

(4) Lmite de ofertas por empresa (opcional).

(5) Lmite de empresas por regin (opcional).

(6) Descartar ofertas que salen de la banda de precios (opcional).

Xj = 0 si

(7) Integrabilidad de las variables.

Las restricciones (1) definen un clsico problema de cubrimiento, donde lasU.T. son los elementos a cubrir y las ofertas los elementos cubridores. Las restric-ciones (2) constituyen un multi-knapsack. Las restricciones (3) obligan a activarlas variables Y slo cuando se han activado las correspondientes variables X. Lasrestricciones (4) y (5) son cotas generalizadas para las variables X e Y respectiva-mente. El nmero de variables binarias es aproximadamente 4600. El modelo ensu conjunto es la combinacin de clsicos problemas combinatoriales, cada uno deellos NP-completo.

Como se dijo en la Seccin 3, la cantidad de instancias del modelo a resolvereran 704 y el tiempo para hacerlo escaso, por lo cual era importante que la resolu-cin de cada instancia tomar un tiempo pequeo. Por ello, y dada la potencialcomplejidad del problema, se agregaron restricciones al modelo de modo de forta-lecer la relajacin lineal de la formulacin. En primer lugar, se agregaron lossiguientes planos de corte, redundantes con el conjunto de restricciones (2) delmodelo, pero que robustecen la relajacin lineal del problema entero:

Estas restricciones que tienen una validez evidente, se conocen comopacking y son muy utilizadas para formular problemas de knapsack o de establemximo (Nemhauser y Wolsey (1988)).


30

Adicionalmente, para algunas instancias se desacoplaron las restricciones(3b) de la siguiente forma:

Esta tcnica de fortalecimiento, frecuente en modelos de localizacin no ca-pacitados, nos entreg un modelo expandido con mejor relajacin lineal que eloriginal, pero de mayor tamao. La idea consista en que la formulacin expan-dida requera menos iteraciones en la etapa de ramificacin y acotamiento perocada iteracin era ms costosa en tiempo porque el modelo era mayor. Esta for-mulacin se utiliz en las instancias ms difciles con buenos resultados.

Referencias bibliogrficas

[1] Crdova, S. (1999), Impacto del Uso de Mtodos de Optimizacin en la Adjudicacinde Grandes Licitaciones y Su Aplicacin a la Junta Nacional de Auxilio Escolar yBecas (JUNAEB), Estudio de Caso, MBA, Universidad de Chile.

[2] Henrquez, L. (1999), JUNAEB, Red Nacional de Apoyo al Estudiante, EncuentroSudamericano Sobre Alimentacin Escolar.

[3] Milgrom, P. (1989), Auctions and Bidding: A Primer, The Journal of EconomicPerspectives, Vol. 3, No. 3.

[4] Nemhauser, G. y L. Wolsey (1988), Integer and Combinatorial Optimization, John

Wiley & Sons, Inc.

Documents

articulo junaeb