Download - Planificación de una explotación agraria
-
Universidad Complutense de Madrid
Facultad de Ciencias Matematicas
Trabajo de fin de Grado
Planificacion de una explotacion agraria
Autor:
Leonardo Torres Hansa
Directora:
Dra. M Teresa Ortuno Sanchez
Madrid, julio de 2012
-
Indice
Abstract 2
1. Introduccion 3
2. La programacion matematica y la agricultura 4
3. Planteamiento del problema 5
4. Modelizacion del problema determinista 7
4.1. Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.2. Funcion objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5. Resultados computacionales 11
6. Programacion estocastica 14
6.1. Problemas en dos etapas . . . . . . . . . . . . . . . . . . . . . . . 15
6.2. Formulacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.3. Modelizacion. Analisis de escenarios . . . . . . . . . . . . . . . . . 19
6.4. Representacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7. Modelizacion del problema estocastico 26
7.1. Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
7.2. Funcion objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
7.3. Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
8. Experiencia computacional con el problema estocastico 33
9. Conclusiones 34
Bibliografa 36
-
Abstract
Farmers have to face economic and environmental pressures. They have to
plan activities and optimize resources for an annual crop cycle. For this
purpose, an integer programming model is proposed.
In a first section, we present some problems, involving mathematics
and crop planning, several mathematicians have previously dealed with.
We focus on those solved with mathematical programming techniques and
we also mention problems in which a stochastic programming model was
necessary.
We have been asked to develop a model that considers optimal resource
allocation, as well as optimal task planning to minimize total costs, in order
to help farmers to plan activities and optimize resources for an annual crop
cycle. We propose two mathematical programming models.
In the first one, the decision variables represent when a task should
be started and how many new units of each kind of resources should be
taken on. For the second one, we consider the execution time for each task
a stochastic piece of data. We introduce uncertainty into the model with
scenario analysis, building a two-stage stochastic model, in which second-
stage variables represent whether the deadlines will be satisfied under each
scenario.
We also make an introduction to stochastic programming in which we
present the most important ways of acting against uncertainty on our
mathematical programming models, focused on two-stage ones.
Some of the final results are shown, as well. They have been obtained
with a program in GAMS, connected to the CPLEX optimizer.
-
1. Introduccion
Las matematicas han dado un modo de abstraer en la manera de lo posible lo
que la ciencia y el pensamiento queran explicar. Han servido para desarrollar
elementos que ninguna otra ciencia poda estudiar, elementos de un mundo de
ideas, en el sentido mas platonico de la palabra, que solo con las matematicas
hemos conseguido comprender.
No obstante, las herramientas matematicas llegaron mas lejos. No se quedaron
en estas abstractas ideas que estaban aparentemente poco presentes en el mundo
cotidiano, sino que, hoy en da, a menudo se opta por su utilizacion. No es raro
ver una ecuacion diferencial que describa el colapso de un puente, ni un modelo
de programacion matematica con el que se planifique la distribucion de la energa
electrica, o un programa informatico que calcule la probabilidad de ganar en un
casino, u otro que cifre mensajes mediante el calculo de logaritmos discretos, ni
una ecuacion con la que se trate de modelizar los mercados financieros. . . Lo que
vamos a ver es un ejemplo concreto de estas aplicaciones.
En agricultura las matematicas pueden jugar un papel decisivo en la planifi-
cacion del calendario anual. Las decisiones que se tienen que tomar al respecto
se realizan sobre gran cantidad de datos y variables. Es aqu cuando los metodos
matematicos permiten simplificar estas deciones o, incluso, dar una optima.
A partir de un conjunto de datos reales vamos a construir un modelo de
programacion entera que permitira secuenciar las tareas que se tengan que realizar
a lo largo del ano de manera optima, as como determinar las necesidades mnimas
relativas a la maquinaria.
A continuacion, tras una introduccion a la programacion estocastica lineal
bietapica propondremos un modelo de programacion estocastica lineal en dos
etapas para el mismo problema, del que supondremos desconocida parte de los
datos.
Mostraremos en paralelo algunos de los resultados computacionales obtenidos,
con el apoyo del citado conjunto de datos.
3
-
2. La programacion matematica y la agricultura
La produccion agrcola se ha visto siempre dificultada por las presiones economi-
cas y medioambientales. La cada de los precios de los productos fuerza a los
agricultores a bajar sus costes de produccion, por lo que para mantener una ren-
tabilidad necesitan encontrar alternativas para sus metodos de produccion de
cultivo. Es aqu cuando la planificacion de una explotacion agrcola adquiere un
papel crucial.
Las decisiones que se deben tomar para construir esta planificacion dependen
de dos tipos de factores. Unos, como las condiciones climaticas, las caractersti-
cas del terreno o la situacion economica del momento, no pueden ser modificados.
Para otros, como la maquinaria o el personal de los que dispone la granja, s se
puede considerar la posibilidad de sustituirlos, mejorarlos o mantenerlos como
esten. Las opciones que tiene el agricultor para llevar a cabo la explotacion de-
penden de estos factores. Podemos considerar un amplio rango de alternativas:
que se cultivara, que operaciones se ejecutaran, como y cuando, que maquina-
ria se empleara, que productos seran necesarios o cuantos empleados se deberan
contratar.
La toma de estas decisiones es lo que constituye la planificacion agrcola y la
programacion matematica es un metodo ampliamente utilizado para realizarla.
La importancia de su aplicacion se basa en su fortaleza para modelizar problemas
complejos y en la posibilidad que da a los usuarios para, posteriormente, resolver
los modelos construidos.
Es natural que en una explotacion agraria se espere maximizar los beneficios
finales. Si esta puede ser planificada, por que no buscar que la ganancia final es-
perada sea maxima? Incovenientes que podemos encontrarnos son, por ejemplo, el
riesgo relativo al tiempo atmosferico o al mercado, o restricciones medioambien-
tales que se impongan, como limitaciones en el uso de fertilizantes o pesticidas,
as como las penalizaciones acarreadas por el incumplimiento de aquellas. En [8]
podemos ver un modelo de programacion matematica multiobjetivo que, ademas
de maximizar el beneficio de la explotacion, busca minimizar el riesgo debido a
dichas restricciones medioambientales.
4
-
En [10] los autores realizan un planteamiento mediante un modelo de progra-
macion entera estocastica que merece ser mencionado. Sera posible mantener,
con alta probabilidad, el nivel de eficacia obtenido con un modelo previo pero
en una menor superficie de cultivo? Cuentan, ademas, con que factores como
los citados antes implican que las expectativas de produccion no se vean satis-
fechas. Finalmente la solucion permita disminuir el area requerida para el caso
que trataron.
Se ha trabajado tambien en problemas en los que se decide cual es la secuencia
ordenada optima de varios cultivos. Los autores de [6] construyen un modelo de
programacion lineal que permite encontrar dicha secuencia. Por otro lado, dada
una secuencia de cultivos no factible, muestran como hallar una subsecuencia de
esta que s lo sea, que permitira proceder con la planificacion agrcola correspon-
diente, pese a que la sucesion presentada en primer lugar no lo permitiera.
Tambien podemos tener en cuenta en un modelo de programacion matematica
las condiciones especiales que requieren ciertos tipos de cultivo, como el ecologico.
Un ejemplo de esto es [4], artculo en el que se desarrolla un modelo que no
solo tiene presente que el tiempo de almacenamiento maximo permitido puede
verse muy reducido (las cosechas, al fin y al cabo, son productos perecederos)
sino, ademas, la incertidumbre que envuelve a la demanda esperada, para lo que
proponen un modelo de programacion estocastica bietapico con recurso.
Otra restriccion que podemos considerar es el control sobre la superficie de
cultivo de las granjas de cara a reducir la deforestacion. Los autores de [1] presen-
tan un modelo de programacion lineal entera mixta sujeto a ello, cuyo objetivo es
disminuir la superficie de la explotacion agrcola pero satisfaciendo las necesidades
del agricultor.
3. Planteamiento del problema
Vamos a plantear un modelo matematico que permitira determinar una plani-
ficacion agrcola al principio del ano. Para ello debemos tener en cuenta todas
las tareas que se deben llevar a cabo as como cuales son los mnimos recursos
necesarios para cada una de ellas. Podemos ya dar algunas definiciones:
5
-
Tareas. Cada una de las actividades que tienen que realizarse para obtener fi-
nalmente una cosecha. Algunos conjuntos de tareas perseguiran un mismo
objetivo y otras tareas seran individuales e independientes. Cada tarea tiene
asignada una ventana de tiempo, relaciones de precedencia con otras tareas
y diferentes formas de ser realizada de acuerdo al empleo que haga de los
recursos.
Modos. Cada una de las diferentes maneras de las que se pueden realizar las
tareas. Vienen determinados por los recursos necesarios, por la duracion y
por el coste de la tarea realizada segun ese modo.
Recursos. Cuando hablamos de ellos nos referimos tanto a los materiales como a
los humanos. Tambien podemos distinguir los recursos que estan disponibles
en la granja y los que necesitamos comprar, alquilar o contratar.
Para la construccion del modelo suponemos que se ha determinado previamen-
te la secuencia de tareas que deben realizarse, a la que llamaremos itinerario
tecnico. Para poder emplearlo como dato del problema, el itinerario tecnico no
solo debe incluir las tareas que se deseen realizar sino ademas sus relaciones de
precedencia.
Tengamos en cuenta que consideraremos previa tambien una evaluacion de
costes de los recursos, de manera que sean estos datos del problema, as como su
disponibilidad. Recordemos que los modos de realizacion de las tareas dependen
de los recursos.
As pues, el problema que se plantea es el de decidir cuando se iniciara, con
que recursos y en cuanto tiempo cada una de las tareas que componen el itinerario
tecnico, con el objetivo de minimizar el coste total, que vendra dado por la suma
de los costes asociados a los modos seleccionados y del coste fijo de los recursos
que se usen. En el modelo deberan incluirse las restricciones a las que se vea sujeto
el objetivo, de forma que se respeten la ventana de tiempo de las actividades y
las relaciones de precedencia (si las hay).
Para la construccion del modelo emplearemos tecnicas de programacion ma-
tematica.
6
-
Un incoveniente que encontramos a la hora de recopilar los datos es que la
informacion sobre los costes, la duracion de las tareas o la disponibilidad de los
recursos puede no ser suficiente. Nos centraremos en el caso en que la duracion
pueda ser desconocida.
La idea es que a pesar de que contamos con diferentes modos de realizar una
misma tarea, su duracion puede variar, aun en un mismo modo, por factores aje-
nos a el, como las condiciones atmosfericas o el grado de disponibilidad de un
recurso. Para solventarlo, extenderemos nuestro modelo a uno estocastico, me-
diante un previo analisis de escenarios. De esta forma, aunque se deja de perseguir
el optimo del objetivo original, las perdidas acarreadas por la cada en escenarios
desfavorables se minimiza.
Presentaremos en primer lugar una modelizacion determinista. Se tratara de
un problema de secuenciacion y asignacion de recursos en el que todos los datos se
consideran conocidos. Las decisiones que se tomaran seran cuando se iniciaran las
tareas, de que modos y que recursos se contrataran al principio del ano agrcola.
A continuacion, construiremos el modelo estocastico va analisis de escenarios.
Como ya hemos dicho, la duracion de las tareas sera un dato variable. Pretende-
mos que en el modelo anterior se tenga en cuenta la variabilidad de la duracion de
una misma tarea, de forma que se minimice el riesgo dependiente de un escenario
u otro.
4. Modelizacion del problema determinista
Procedemos a construir el primer modelo de acuerdo con lo explicado ut supra.
La dimension del problema viene dada por los siguientes parametros:
tt : numero total de tareas
mti : numero total de modos para la tarea i
it : numero total de instantes
rt : numero total de tipos de recurso distintos.
Hemos tomado como unidad temporal de referencia el da. Por tanto, cuan-
do a lo largo del desarrollo del problema hablemos de instantes de tiempo nos
7
-
referiremos a das.
Los ndices que utilizaremos seran:
i : tarea, i = 1, . . . , tt
i : tarea, i = 1, . . . , tt
j : modo de realizar la tarea i, j = 1, . . . ,mti
m : modo de realizar la tarea i, m = 1, . . . ,mti
t : instante de tiempo, t = 1, . . . , it
: instante de tiempo, = 1, . . . , it
k : tipo de recurso, k = 1, . . . , rt.
Los datos que asumimos conocidos son:
pij : tiempo de proceso de la tarea i realizada segun el modo j (das)
ri : fecha de inicio mas temprana de la tarea i (da)
di : fecha maxima de la finalizacion de la tarea i (da)
k : unidades de recurso del tipo k que poseemos
ijk : unidades de recurso del tipo k que necesitamos por unidad de tiempo
para la tarea i en el modo j (unidades de recurso por da)
cij : coste de realizacion de la tarea i mediante el modo j (euros)
ck : coste de contrato de una unidad de recurso k (euros).
Recordemos que cada modo j especifica que recursos emplea. Por tanto, si un
recurso k tiene un cierto coste asociado por usarlo, se incluira en el coste cij.
La ventana de tiempo de cada tarea i quedara determinada por los parametros
di y ri y es independiente de los modos en que pueda realizarse la tarea. La idea
precisamente es decidir que modo se empleara para cada tarea de forma que su
ventana de tiempo se satisfaga.
El parametro pij es el que en la seccion 7 sera una variable aleatoria que
habra que introducir en el modelo.
8
-
4.1. Variables
Lo que se necesita es decidir de que modo se deben realizar las tareas, cuando se
deben iniciar y cuantas unidades de recurso de cada tipo se conseguiran nuevas1.
As pues, definiremos dos tipos de variables: uno relativo a las tareas y otro, a los
recursos.
Xijt =
1 si iniciamos i segun j en t0 en caso contrarioYk : unidades de recurso del tipo k que contratamos nuevas.
Las Xijt, para todo i, j, t, estan definidas como variables de impulso: no
decidimos cuando se esta realizando la tarea sino cuando se inicia. Asumiremos
que una tarea i en proceso no se vera interrumpida. Como conocemos su tiempo
de proceso pij, sabremos cuando acabara una vez se decida su instante de inicio t.
4.2. Funcion objetivo
Buscamos minimizar costes. Estos los tenemos agrupados en dos tipos: costes por
el contrato de nuevas unidades de recursos (ck,k = 1, . . . , rt) y costes intrnse-cos a la realizacion de una tarea i mediante alguno de sus modos i (cij,i =1, . . . , tt j = 1, . . . ,mti).
El primer tipo es independiente del tiempo que se use el recurso k; solo tiene
en cuenta si se contrata o no. Por otra parte, a un modo de realizar una tarea
lo determina, entre otras cosas, el tiempo de proceso de la tarea segun ese modo
(pij,i = 1, . . . , tt j = 1, . . . ,mti); por lo tanto, no haremos referencia a esetiempo en la funcion objetivo porque queda implcito en el parametro cij.
Podemos, entonces, expresar la funcion objetivo como:
1En el caso de que sean necesarios recursos que no se posean, se decidira contratarlos al
comienzo del ano agrcola, momento en que se implementa el presente modelo. Por lo tanto,
podemos tratar de forma equivalente a los recursos que se contratan, a los recursos que se
compran y a los recursos que se alquilan
9
-
mnrtk=1
ck Yk +tti=1
mtij=1
itt=1
cij Xijt (4.1)
4.3. Restricciones
El recinto donde esta definido el problema podemos verlo mediante las siguientes
expresiones:
mtij=1
itt=1
Xijt = 1 i (4.2)
ri1t=1
Xijt +it
t=dipij+1Xijt = 0 i j (4.3)
mtij=1
dipijt=ri
(t+ pij)Xijt mtij=1
dipijt=ri
tXijt si i precede a i (4.4)
tti=1
mtij=1
ijk
t=tpij+1
Xij k + Yk k t (4.5)
Xijt {0, 1} i j t (4.6)
Yk Z Yk 0 k (4.7)La restriccion (4.2) fuerza a que cada actividad se realice de un unico modo
y a que, ademas, se inicie una unica vez (o de forma equivalente, a que se realice
una unica vez).
La restriccion (4.3) obliga a que cada tarea, se realice del modo en que se
realice, satisfaga su ventana de tiempo. Lo que conseguimos con esta restriccion
es dar valor 0 a las variables Xijt siempre que iniciar la tarea i segun el modo j
en el instante t implique la violacion de la ventana de la tarea i.
La restriccion (4.4) delimita las relaciones de precedencia entre las actividades
(si las hay). Sean dos actividades, i, i, tales que i precede a i. El primer miembro
de la desigualdad sera el instante de finalizacion de la tarea i y el segundo, el
10
-
instante de inicio de la tarea i. Si se decide iniciar la tarea i en el modo j en el
instante t, esta restriccion hara que la tarea i no pueda iniciarse si la tarea i no
se ha concluido (como muy pronto sera en el instante t+ pij).
La restriccion (4.5) permite que el modelo tenga presente que una unidad
de recurso del tipo k, k, no puede estar en dos sitios distintos a la vez, i.e.,que en cada instante solo se usaran los recursos que esten disponibles. Lo que
hace la restriccion es obligar a que se disponga en cada instante t de todos los
recursos necesarios en ese instante. Para ello necesitamos saber cuales son las
tareas que se estan llevando a cabo en t (y de que modo), lo que viene dado por
la expresiontt
i=1
mtij=1
t=tpij+1Xij . Ahora se multiplica Xij por ijk y se
obtiene la cantidad de recurso del tipo k necesaria en ese instante.
Indicamos finalmente que las variables Xijt son binarias y que las Yk relativas
a las unidades de recurso del tipo k que adquiramos habran de ser enteras no
negativas.
5. Resultados computacionales
Hemos implementado el modelo anteriormente descrito en GAMS, junto con el
optimizador de CPLEX. Hemos empleado datos obtenidos del Instituto Tecnico
Agronomico Provincial de Albacete2 con los que hemos estudiado casos diferentes,
en funcion de los diferentes cultivos y tipos de recursos que considerabamos.
En la tabla 1 podemos ver las dimensiones del modelo y los resultados compu-
tacionales en cada uno de los casos resueltos, en funcion del numero de cultivos
considerados en cada uno. El parametro m representa el numero de restricciones
del modelo; n, el numero de variables continuas; n01 el numero de variables bi-
narias; z, el valor optimo de la funcion objetivo; y T , el tiempo computacional
requerido por el optimizador para resolver el modelo, en segundos.
Una primera observacion que se puede hacer es que, de acuerdo con el tiempo
2El ITAP es una empresa publica creada en 1986, en Albacete, Castilla-La Mancha, Espana.
Su ambito de actuacion es el sector agropecuario y agroalimentario. Algunas de sus funciones son
la investigacion agraria, la produccion y comercializacion de variedades de plantas, la gestion de
un laboratorio agropecuario, el desarrollo de programas provinciales de agricultura y ganadera
o el asesoramiento tecnico a los agricultores y ganaderos de la provincia.
11
-
Cultivos m n n01 Z T (seg.)
1 351 6 759 11733 0.515
2 771 7 1680 22931 1.903
3 1156 11 1680 39592 2.044
4 1401 14 6660 44978 3.325
5 1823 15 8127 57855 7.659
6 1984 15 8929 60523 11.825
7 2631 17 13498 84613 18.814
Tabla 1: Resultados computacionales
computacional T , es un problema sencillo. A la hora de planificar un ano agrcola
desde su comienzo, el problema supone un gran numero de decisiones y datos,
pero una vez expresado de forma matematica, a un ordenador no le cuesta mas
de unos segundos obtener la solucion optima.
Cabe destacar tambien la diferencia con trabajos previos sobre este mismo
problema. En [11] podemos ver una modelizacion alternativa, puesta en practica
con un conjunto de datos similar al empleado aqu. La mejora de las maquinas
en los ultimos anos ha permitido no solo una mas rapida resolucion de proble-
mas similares sino, ademas, la posibilidad de enfrentarnos a conjuntos de datos
mayores.
Mostramos finalmente la solucion optima obtenida para el caso de tres tipos
de cultivos. En la figura 1 vemos el diagrama de Gantt3 construido a partir de la
solucion obtenida en el caso citado.
Cabe destacar que no hemos pedido en el modelo que las tareas se inicien
lo antes posible, de forma que puede darse un margen inicial entre su posible
comienzo y la fecha exacta del mismo, independientemente del inevitable por las
relaciones de precedencia entre las tareas.
Mencion especial merece tambien la holgura de las ventanas de tiempo, que
3Un diagrama de Gantt es una herramienta grafica desarrollada por Henry Laurence Gantt,
ingeniero mecanico estadounidense, a comienzos del siglo XX. Su objetivo es mostrar el tiempo
de ejecucion que se preve dedicar a un conjunto de tareas a lo largo de una lnea temporal.
12
-
permiten a menudo un amplio margen entre cuando se concluye una tarea y hasta
cuando estara permitida su realizacion.
Figura 1: Diagrama de Gantt para los cultivos 1, 2 y 3
13
-
6. Programacion estocastica
En los problemas de decision esta involucrada en muchas ocasiones la incerti-
dumbre, es decir, alguno de los datos no se conoce con certeza. La programacion
estocastica es el estudio de procedimientos orientados a la resolucion de estos
problemas.
La Investigacion Operativa surge durante la Segunda Guerra Mundial y ya en
1955 el propio Dantzig4 introduce la incertidumbre en sus modelos de programa-
cion lineal.
Un problema de programacion lineal determinista de minimizacion5 se puede
plantear como:
mn z = cTx
s.a Ax = b (6.1)
x 0,
donde x es un vector de tamano n N y cuyas componentes son las variablesde decision y c, A y b son datos conocidos. Concretamente, c es un vector de
dimension n, b es un vector de dimension m N y A es una matriz de dimensionm n. z = cTx corresponde al valor de la funcion objetivo y el conjunto desoluciones factibles viene dado por F = {x | Ax = b,x 0}.
Definicion. Un optimo x para el problema lineal determinista 6.1 es una so-
lucion factible de F tal que cTx cTx para cualquier x F .
A los problemas de programacion matematica en los que alguno de los parame-
tros es desconocido los llamamos problemas de programacion estocastica. Lo que
4George B. Dantzig nace en Portland, Oregon, en 1914. Famoso por sus aportaciones a la
Investigacion Operativa y a la Estadstica, cabe destacar su desarrollo del algoritmo del smplex.
Doctor por la Universidad de Berkeley, California, en 1946, Doctor Honorario por la Universidad
de Maryland en 1976 y Profesor Emerito en la Universidad de Stanford, California, ciudad en
la que fallece en 2005.5Recordemos que una funcion f : Rn R (analogamente, f : Zn Z) verifica max {f(x)} =
mn {f(x)} x Rn (analogamente, x Zn).
14
-
se perseguira en estos casos es la representacion de estos parametros como varia-
bles aleatorias (asumiremos que su distribucion es conocida) para poder tratar
la incertidumbre en los datos como un dato mas del problema. Destacamos dos
procedimientos:
Programacion probabilstica. Se trata de un metodo con el que se busca el
optimo esperado de la funcion objetivo. Ademas se cuenta con restricciones
de tipo probabilstico, que se intentan satisfacer cumpliendo determinados
umbrales de probabilidad.
Analisis de escenarios. De las variables aleatorias presentes en el problema
se considera un conjunto finito de realizaciones futuras con sus respectivas
probabilidades. A continuacion se estudia el problema sobre estas posibles
realizaciones.
El primer procedimiento necesita que se conozcan con mucha precision las
distribuciones de las variables aleatorias. Por ello, emplearemos el segundo: el
analisis de escenarios.
6.1. Problemas en dos etapas
En un problema estocastico, la incertidumbre que envuelve a los datos descono-
cidos puede representarse mediante una variable aleatoria () que toma valores
en un subconjunto de Rn, n N, y que depende del resultado que se de tras elexperimento aleatorio que hace estocastico al problema.
Observacion. es el menor subconjunto de Rn tal que P () = 1.
Ejemplo. Supongamos que en cierto punto del planeta va a iniciarse un terre-
moto. Con la notacion anterior podemos ver como la intensidad en la escala de
Richter que tendra. Una vez concluya el evento, los danos que se han producido en
la zona vienen dados por la variable aleatoria (), que depende de la intensidad
que haya habido.
Pongamos otro ejemplo en torno a las apuestas en las ruletas. El suceso alea-
torio del que dependen las ganancias del jugador viene dado por ; estas
15
-
estan representadas por la variable aleatoria (), que pasa a ser conocida una
vez la bola cae sobre un numero (hecho que podemos representar por ).
Habitualmente las decisiones tendran que ser tomadas antes de que se haya
realizado dicho experimento y, consecuentemente, antes de conocer su resultado.
Habra ocasiones en las que otras puedan ser tomadas una vez que la incertidumbre
haya desaparecido. En este caso, diremos que el problema es de recursion y que
las decisiones del primer tipo son de primera etapa; las del segundo, de segunda
etapa.
Definicion. A los modelos para los que haya que considerar los dos tipos de
decisiones los llamaremos bietapicos.
Denotemos a las decisiones de primera etapa por el vector x y a las de segunda
etapa, por y(,x) o y(), donde es el resultado del experimento aleatorio.Sea () la realizacion de la variable aleatoria dependiente del resultado . El
esquema de la toma de decisiones que se tienen que realizar en un modelo bietapico
es
x () y(,x).Ilustremos estos terminos con un ejemplo. Pensemos en un comerciante que recibe
un producto cada da. Visita clientes a lo largo del da con la esperanza de poder
vender su mercanca. Vuelve a casa ora cuando encuentra un comprador, ora
cuando visita a todos los clientes, quienes deciden comprar o no el producto de
manera aleatoria (suponemos que la decision de un da no influye en la de los
venideros). Al comerciante le gustara encontrar el orden en que debe visitar a los
clientes de forma que pueda volver a casa lo antes posible. Tengamos en cuenta
que el tiempo que invierte en el recorrido comprende el tiempo de recorrido entre
un cliente y otro as como el que gasta cada vez que visita a un cliente.
Observacion. Para simplificar, asumiremos que una vez fijado el orden en que
visitara a los clientes, no lo cambiara de forma improvisada durante el recorrido.
En esta situacion, la primera etapa del problema consiste en decidir cual es la
secuencia de clientes que seguira y, ademas, llegar al primer cliente. La segunda
16
-
etapa tiene una duracion variable, ya que depende de si los clientes le compran el
producto o no. Pongamos un caso con solo dos clientes. Los tiempos de recorridos
(incluido el tiempo de servicio en la localizacion de los clientes) vienen dados en
la figura 2.
Origen
Cliente 2
Cliente 1
4h
3h
1,5h
Figura 2: Ejemplo del comerciante
Pongamos que el da comienza a las 8:00. Si primero va al cliente 1 y luego,
al 2, la primera etapa empezara a las 8:00 y terminara a las 9:30. La segunda
etapa comienza a esa misma hora y, si el cliente 1 compra el producto, termina a
las 11:00 (contamos con que el vendedor vuelve a casa); si 1 no compra, termina
a las 16:30. Si decide realizar la secuencia alternativa, la primera etapa acaba a
las 12:00 y la segunda, o bien a las 16:00 o bien a las 16:30. As, la primera etapa
de esta segunda opcion puede terminar incluso despues de la segunda etapa de la
primera alternativa si el cliente 1 compra el producto.
6.2. Formulacion
En 1955 Dantzig y Beale6 dieron la primera formulacion para problemas bietapi-
cos de programacion lineal estocastica con recursion.
6Martin Beale nace en 1928 y se educa en Cambridge. Se gradua en Matematicas en 1949 y
en 1955 aplica el algoritmo del Smplex de Dantzig a la minimizacion de una funcion cuadratica.
Miembro de varias asociaciones matematicas, llega a ser vicepresidente de la Royal Statistical
17
-
mn cTx + E
[mn q ()T y ()
]s. a Ax = b
T () x + Wy () = h () (6.2)x,y () 0
Observemos la distincion que se hace entre las decisiones de la primera etapa y
las de la segunda. Las decisiones de la primera vienen representadas por el vector
x de tamano n1. A Mm1n1 es la matriz correspondiente, b (tamano m1), elvector de terminos independientes y c (tamano n1), el vector de costes.
En la segunda etapa, para cada realizacion de la variable aleatoria (), con
, los datos de la segunda etapa q (), h () y T () quedan determinados.Respectivamente, las dimensiones son n2, m2 y m2n1. A W la llamamos matrizde recursion y, si es fija, diremos que el problema es de recursion fija7.
Como q, T y h dependen del resultado del experimento aleatorio, podemos
interpretarlos como vectores aleatorios. Denotemos por Ti() a la i-esima fila
de la matriz T(). Podemos ahora agrupar todas las componentes estocasticas
de los datos relativos a la segunda etapa y obtenemos as el vector T () =(q()T ,h()T ,T1(), . . . ,Tm2()
), que puede llegar a tener hasta N := n2 +
m2 +m2 n1 componentes.Cuando se concluye , se toman las decisiones de segunda etapa y(,x),
donde x son las decisiones relativas a la primera etapa.
Es cierto que tanto el vector de decisiones y como los parametros q, T o h
dependen del resultado que se de, pero conviene hacer notar que no lo hacen
de la misma manera. La idea es indicar que las decisiones y no tienen por que ser
las mismas bajo diferentes acontecimientos ; se escogen de forma que las res-
tricciones de (6.2) que dependan de se satisfagan casi seguro, i.e., para todo
salvo quiza para un subconjunto de probabilidad cero.Society de 1978 a 1980 y, posteriormente del Institute of Mathematics and its Applications, en
el Reino Unido.7Para el problema que vamos a tratar no es relevante el caso en el que la matriz W no es
fija.
18
-
El termino cTx de la funcion objetivo del modelo (6.2) es determinstico. Su
otro termino es la esperanza del objetivo de la segunda etapa, q ()T y (), sobre
la variable aleatoria , i.e, sobre todas las realizaciones posibles de . Por ello,
el calculo de dicha esperanza es costoso: y () se obtiene como solucion de un
modelo lineal, para cada . Existe una formulacion alternativa al modelo(6.2) que, precisamente, hace hincapie en ello. Dada una realizacion , sea
Q(x, ()) = mny
{q()Ty|Wy = h()T()x, y 0}
el valor de la funcion objetivo para la segunda etapa. Su esperanza bajo la variable
aleatoria es
Q(x) = E [Q (x, ())]y la llamaremos funcion de recurso. Con todo, podemos dar como problema
alternativo a (6.2):
mn z = cTx +Q(x)s.a Ax = b (6.3)
x 0,
al que llamaremos problema determinstico equivalente (DEP).
Esta formulacion permite ver claramente que la diferencia principal del proble-
ma estocastico frente a uno determinstico esta en el valor de la funcion objetivo
para la segunda etapa.
6.3. Modelizacion. Analisis de escenarios
Los problemas de programacion estocastica van acompanados de una costosa reso-
lucion, lo que ha llevado a que buena parte de los metodos que se han desarrollado
para afrontarlos consista en la simplificacion del modelo: si eliminamos la incer-
tidumbre presente en este, construimos modelos mucho mas sencillos de resolver.
Por ejemplo, podemos reemplazar todos las variables aleatorias presentes por sus
valores esperados. Supongamos, por otra parte, que del vector aleatorio que ha-
ce al problema estocastico tomamos un numero finito de realizaciones. Con cada
19
-
una construimos un problema determinstico distinto, de resolucion mas sencilla
que el estocastico original. Podemos despues combinar las diferentes soluciones
para obtener una solucion global.
Como podemos realizar esta combinacion de soluciones? Merece la pena
resolver el problema simplificado, a pesar de la informacion que se pueda perder?
Definicion. Tomemos un conjunto finito de realizaciones de la variable aleatoria
multidimensional . Cada una de estas realizaciones se corresponde con un estado
particular de la realidad; las llamaremos escenarios.
Observacion. En muchas ocasiones, incluso cuando una variable aleatoria puede
tomar infinitos valores, es decir, cuando existen infinitas realizaciones distintas,
estas pueden resumirse en un conjunto de realizaciones que son mas significativas
que otras8, por lo que resulta razonable el metodo de resolucion mediante un
analisis de escenarios.
Sea entonces () uno de estos escenarios, para algun resultado del eventoaleatorio . Consideremos el problema asociado:
mn z = cTx + mn{q()Ty|Wy = h()T()x, y 0}
s.a Ax = b (6.4)
x 0,
donde, igual que en (6.2), T () =(q()T ,h()T ,T1(), . . . ,Tm2()
). Asuma-
mos tambien la existencia de al menos una solucion factible para cada escenario,
i.e., , x tal que z(x, ) < . Consecuentemente estamos tambien supo-niendo la existencia de una solucion optima9. Denotemos por tanto por x()
a una solucion optima de (6.4). En el analisis de escenarios lo que nos interesa
es encontrar las soluciones x() del problema (6.4) para todos los escenarios,
as como los valores z(x(), ) de la funcion objetivo asociados.
8Metodologas como el metodo de simulacion de Monte Carlo, el analisis de conglomerados
o las redes neuronales son algunos ejemplos de tecnicas empleadas para tal proposito.9Porque una de ellas dara un menor valor para z.
20
-
Definicion. Llamaremos solucion wait-and-see10 a
WS = E [z(x(), )] = E [mn z (x, )] . (6.5)
Esta solucion se corresponde con la solucion media que cabra obtener si tu-
vieramos la habilidad de predecir el escenario que se va a dar, i.e., la realizacion
, antes de tomar la decision.
Definicion. Llamaremos solucion here-and-now11 a la del problema estocastico
general (6.2):
HN = mnxE [z(x, )] , (6.6)
cuya solucion optima habamos denotado por x.
Podemos ahora comparar ambas soluciones. En [3] se demuestra que WS HN . Lo que quiere decir el resultado es que la solucion que se dara si conociera-
mos () es mejor que la que se da antes de que se realice el experimento . Lo
que nos podemos plantear ahora es cuan mejor es la solucion wait-and-see frente
a la here-and-now.
Definicion. Llamaremos valor esperado de la informacion perfecta a la
diferencia entre ambas soluciones:
EV PI = HN WS12.
Observacion. Si el objetivo es la minimizacion de unos costes, el EV PI lo
podemos interpretar como la cantidad maxima que el decisor estara dispuesto a
pagar para poder acceder a la informacion completa del problema.
En la practica, encontrar la solucion wait-and-see seguira siendo difcil (im-
posible, de hecho, si no se puede conseguir la informacion perfecta en el sentido
citado anteriormente). Por lo tanto, se buscan maneras mas simples de afrontar un
problema estocastico, por ejemplo, la sustitucion de todas las variables aleatorias
10En espanol, espera-y-veras11En espanol, aqu y ahora12La siglas provienen del ingles expected value of perfect information
21
-
por sus valores esperados. Al problema determinstico resultante lo llamaremos
problema de valor esperado:
EV = mnxz(x, ), (6.7)
donde = E [].
Observacion. Si coincide con uno de los escenarios, (6.7) es un caso particular
de (6.4).
Sea x() una solucion optima de (6.7). El que sea una buena solucion del
problema estocastico dependera del escenario en el que nos encontremos pero,
en principio, no hay razon alguna para pensar que x() siquiera se acerca a la
solucion del problema (6.6). El valor de la solucion estocastica mide cuan buena
o mala es la decision x() respecto de la solucion (6.6). Necesitamos primero
conocer que se espera que ocurra si se usa la solucion (6.7):
EEV = E[z(x(), )
](6.8)
Definicion. Definiremos al valor de la solucion estocastica como
V SS = EEV HN. (6.9)
Concretamente, el valor de la solucion estocastica proporciona una medida de
la ventaja que ofrece la resolucion del problema (6.6) frente al problema del valor
esperado correspondiente. Cuanto mayor sea V SS, mas recomendable sera resol-
ver el problema (6.6).
Con todo, tras la toma de una decision nos podemos encontrar en diferentes
situaciones: los escenarios. De estos contamos con algo de informacion al inicio
de la nueva etapa. Un arbol como el de la figura 3 nos puede ayudar a visualizar
este planteamiento.
El nodo raz representa la primera etapa. Los demas nodos hacen referencia
a la segunda etapa de los diferentes escenarios que se puede llegar en funcion de
la decision que se tome en el nodo raz.
22
-
escenario 3
escenario 2
escenario 1
Figura 3: Arbol de escenarios
6.4. Representacion
El analisis de escenarios para el problema (6.2) da paso a diferentes maneras
de representarlo. Consecuentemente, se han construido metodos de resolucion
que aprovechan dichas representaciones. Para el problema que nos atane, nos
centraremos en el caso en que la variable aleatoria tiene soporte finito. Con
esta hipotesis el problema admite una formulacion lineal determinstica.
As pues, supongamos que () es finita con soporte = {1, 2, . . . , K}y sea pk la probabilidad de k, k = 1, . . . , K. Podemos entonces reescribir losterminos de (6.2) que dependen de de forma explcita, incluidas las variables
y() para cada una de los escenarios ().
Observacion. La esperanza de la funcion objetivo del problema (6.2) en el pre-
sente caso es una suma finita, por lo que la funcion objetivo en la representacion
que vamos a ver es lineal.
Sea, por tanto, () finita. Denominaremos forma extensiva del problema
a:
23
-
mn z = cTx +Kk=1
pkqTk yk
s.a Ax = b
Tkx + Wyk = hk k = 1, . . . , K (6.10)x 0,yk 0, k = 1, . . . , K.
Este problema se puede resolver con las tecnicas usuales de programacion
lineal, como el algoritmo del smplex. El inconveniente que se puede presentar
es la dimension (en terminos de variables y restricciones) que puede llegar a
tener. No obstante, existen metodos especficos para resolver el problema en tales
situaciones. La idea es aprovechar la estructura de la matriz de restricciones.
Observemos que esta tiene el siguiente esquema:
Ax = b
T1x + Wy1 = h1
T1x + Wy2 = h2...
. . ....
TKx + + WyK = hK
por lo que la matriz global es:
A
T1 W
T2 W...
. . .
TK W
La estructura de esta matriz permite aplicar metodos de descomposicion, como
el de Dantzig-Wolfe o el de Benders. La idea en la que se basan es que podemos
eliminar, en el problema dual, el primer bloque de restricciones; as, la matriz
del problema se reduce a una diagonal por bloques (concretamente, K bloques)
y la resolucion pasa a ser bloque a bloque. Si la solucion obtenida no satisface
24
-
esa primera restriccion eliminada, se introduce un corte (que impedira tener en
cuenta esta solucion) y se resuelve el problema resultante.
Existe una representacion alternativa que emplea variables para cada etapa
y para cada escenario; se denomina representacion en variables separadas. No
obstante, hay que tener presente que las decisiones de primera etapa son inde-
pendientes del escenario que se vaya a dar13. Una manera de verlo es que tienen
ser iguales para cualquier resultado del evento aleatorio. Por lo tanto, enel modelo hay que introducir restricciones que fuercen a dicha igualdad:
xk xk+1 = 0 k = 1, . . . , K,
donde definimos k + 1 = 1 cuando k = K.
As pues, la representacion con variables separadas en escenarios sujeta a las
restricciones de no anticipacion queda:
mn z =Kk=1
pk(cTxk + q
Tk yk)
s.a Axk = b k = 1, . . . , KTkxk + Wyk = hk k = 1, . . . , K (6.11)
xk xk+1 = 0 k = 1, . . . , Kxk 0,yk 0, k = 1, . . . , K.
Con esta representacion se obtiene un problema por cada escenario, relaciona-
dos los problemas tan solo por las condiciones de no anticipacion xk xk+1 = 0.El inconveniente que se nos plantea es el aumento de la dimension del problema
por el mayor numero de variables. No obstante, es posible aplicar metodos ma-
triciales especficos para matrices con formas especiales. La matriz global de la
representacion (6.11) sigue el esquema:
13A esta condicion la conocemos como Principio de no anticipacion.
25
-
A 0
T1 W
I IA
T2 W
I I. . .
. . . IA
TK W
Tecnicas usuales de descomposicion son la de Dantzig-Wolfe o la de Benders.
Lo que hacen es modificar la region factible. La primera trabaja sobre subregio-
nes de la factible hasta encontrar el optimo; la segunda, optimiza en una region
factible mayor y posteriormente aumenta las restricciones para buscar una apro-
ximacion al optimo en la region factible original. Otro metodo, la descomposicion
Lagrangiana, equivalente a la descomposion Dantzig-Wolfe, elimina las restriccio-
nes de no anticipacion y las penaliza en la funcion objetivo. Los coeficientes de
dicha penalizacion vienen dados por el vector de multiplicadores de Lagrange14.
7. Modelizacion del problema estocastico
Ya hemos comentado en las secciones 3 y 4 que la duracion de las tareas puede
verse sometida a cambios.
Al comienzo del ano, como estas variaciones no pueden ser conocidas, se pla-
neara el calendario de acuerdo a diferentes valores de la duracion pij. Estos de-
penderan de los diferentes resultados que se puedan dar tras un evento aleatorio
. Posteriormente, valoraremos la posibilidad de que una tarea cuyo comienzo se
14Una estimacion de los multiplicadores se puede obtener mediante el metodo del subgra-
diente.
26
-
haya retrasado pueda no satisfacer su ventana de tiempo. Por supuesto, penali-
zaremos este retraso.
Esa planificacion que haremos antes de que comience el ano se corresponde
con la primera etapa del modelo que vamos a construir. No emplearemos, no
obstante, cada uno de los pij sino que, con el objeto de reducir la dimension del
problema, nos apoyaremos en una unica medida que nos permita resumirlos; por
ejemplo, su media. Los retrasos acarreados por el hecho de que una tarea, en un
determinado escenario, no satisfaga su ventana de tiempo prevista constituiran
las variables de segunda etapa.
Los escenarios dependeran de los diferentes pij que se puedan dar a lo largo del
ano. A medida que pasen los das, que el ano este siendo bueno o no quedara de-
terminado y, consecuentemente, tambien lo haran las variables de segunda etapa.
As, la estructura de las decisiones seguira la de la figura 3, de forma que
en el nodo raz se decidira que recursos contratar y cuando se iniciaran, en un
principio las tareas, y en los demas nodos (dependientes de los escenarios), los
retrasos respecto de la ventana de tiempo quedaran determinados.
La dimension del problema estocastico sera mayor que la del determinista ya
que trabajaremos con un cierto numero de posibles escenarios. Recordemos que
esta vena dada por los siguientes valores:
tt : numero total de tareas
mti : numero total de modos para la tarea i
it : numero total de instantes
rt : numero total de tipos de recurso distintos.
Para el modelo estocastico tendremos que anadir:
et : numero total de escenarios.
El nuevo ndice que utilizaremos sera el que hemos estado empleando habi-
tualmente para referirnos a los escenarios:
: escenario, = 1, . . . , et.
27
-
Algunos de los datos de la seccion 4 los consideraremos conocidos tambien
para el caso estocastico:
ri : fecha de inicio mas temprana de la tarea i (da)
di : fecha maxima de la finalizacion de la tarea i (da)
k : unidades de recurso del tipo k que poseemos
ijk : unidades de recurso del tipo k que necesitamos por unidad de tiempo
para la tarea i en el modo j (unidades de recurso por da)
cij : coste de realizacion de la tarea i mediante el modo j por unidad de
tiempo (euros por da)
ck : coste de contrato de una unidad de recurso k (euros).
Una novedad es el coste cij, que en este caso lo definimos para cada unidad
de tiempo. Con las nuevas variables que vamos a emplear, tenerlo as definido
resultara mas practico.
Dependiente del escenario tenemos:
pij : duracion de la tarea i realizada en el modo j en el escenario .
y, en consecuencia, contamos tambien con:
pij : duracion media de la tarea i realizada en el modo j ponderada sobre
cada escenario.
Asumiremos que se ha realizado un analisis previo sobre todos estos parame-
tros, de forma que puedan ser tomados como datos del problema, incluidas las
probabilidades de cada escenario y las diferentes duraciones que puedan corres-
ponder a las tareas.
7.1. Variables
Una vez mas habremos de decidir el modo en que se realizaran las tareas, cuando
se deben iniciar y cuantas unidades de cada recurso k se contrataran. Las varia-
bles empleadas en el modelo determinista quedan igualmente definidas, y son las
variables de primera etapa del modelo estocastico:
28
-
Xijt =
1 si iniciamos i segun j en t0 en caso contrarioYk : unidades de recurso del tipo k que contratamos nuevas.
Veamos cuales son las variables relativas a la segunda fase del problema. Para
cada tarea i y cada escenario definiremos una variable que mida el retraso que
sufre con respecto a su ventana de tiempo, es decir, cuanto tiempo por encima
de su fecha lmite de finalizacion le lleva ser concluida. Necesitaremos tambien
variables auxiliares para la modelizacion:
RF i : retraso en la finalizacion de la tarea i, respecto de su ventana de
tiempo, en el escenario dado por .
RIi : retraso en el inicio previsto de la tarea i en el escenario dado .
Zijt =
1 si la tarea i segun j se lleva a cabo en t en el escenario 0 en caso contrario.it {0, 1}it {0, 1}
Supongamos que, mediante las variables de pimera etapaXijt, se tena previsto
iniciar la tarea i en un da t pero en determinado escenario las tareas que la
preceden sufren retrasos. Entonces i sufrira un retraso en su inicio y vendra dado
por la variable RIi . En funcion del margen que tuviera respecto de su ventana
de tiempo, cabe la posibilidad de que, por este retraso inicial, tambien se retrase
en su finalizacion, lo que vendra dado por RF i .
Con Zijt podremos ver los recursos que necesitamos en cada escenario y en
cada dat.
El uso de las variables it, it y ijt lo explicaremos en 7.3.
A la vista de las variables citadas podemos adelantar que nos hemos inclinado
por la representacion en forma extensiva (6.10).
29
-
7.2. Funcion objetivo
Igual que en el problema determinista nuestro objetivo ahora sera minimizar
los costes de realizacion de las tareas y de contratacion de recursos. Pero por las
nuevas definiciones que hemos hecho, las variables de primera etapa no apareceran
en la funcion objetivo de manera analoga al caso de la seccion 4.
Los costes cij no dependen de los escenarios, pero su definicion en esta sec-
cion permite que puedan acompanar a las variables de segunda etapa Zijt, que
s dependen del escenario. Queremos minimizar tambien el retraso en finalizar las
tareas RF i15.
mnrtk=1
ck Yk +et=1
p (
tti=1
mtij=1
itt=1
cij Zijt +
tti=1
RF i
), (7.1)
donde p, , es la probabilidad de que el resultado del evento aleatorio sea .
7.3. Restricciones
Las expresiones que definen el recinto de soluciones factibles para el problema
son:
itt=1
mtij=1
Xijt = 1 i (7.2)
ri1t=1
Xijt +it
t=dipij+1Xijt = 0 i j (7.3)
RIi +
mtij=1
dit=dipij+1
(t+ pij)Xijt di +RF i i (7.4)
RIi +
mtij=1
dipijt=ri
(t+ pij
)Xijt RIi +
mtij=1
dipijt=ri
tXijt si i precede a i (7.5)
15Si se desea, se pueden definir unos pesos que acompanen a estas variables en la funcion
objetivo, por ejemplo, en funcion de las tareas o de los escenarios, de forma que se le de mas o
menos importancia al retraso de determinadas tareas en determinados escenarios.
30
-
Para introducir las variables Zijt en el modelo necesitaremos escribir mediante
expresiones lineales la siguientes implicaciones, para cada i, t, :
RIi +
mtij=1
it=1
Xij > tmtij=1
t=1
Zijt 0 (7.6)
RIi +
mtij=1
it=1
( + pij
)Xij < t
mtij=1
it=t1
Zijt 0 (7.7)
Anadiremos tambien:
tti=1
mtij=1
ijk Zijt k + Yk k t (7.8)
itt=1
Zijt =itt=1
pijXijt i j (7.9)
Xijt {0, 1} i j t, Yk Z Yk 0 k (7.10)Zijt {0, 1} i j t
RIi , RFi Z RIi , RF i 0, i (7.11)
Las siguientes restricciones modelizan la implicacion (7.6):
RIi +
mtij=1
it=1
Xij t it (1 it) i t (7.12)
mtij=1
t=1
Zijt (
mtij=1
pij
) it i t (7.13)
y (7.7):
RIi +
mtij=1
it=1
( + pij
)Xij t (it) (1 it) i t (7.14)
31
-
mtij=1
it=t1
Zijt (
mtij=1
pij
) it i t (7.15)
it, it {0, 1} i t (7.16)
Recordemos que una variable Zijt indica si la tarea i se esta llevando a cabo
en el instante t, en el modo j, en el escenario . Por lo tanto, dado un instante t
y un escenario , si la actividad i se inicia en un instante posterior a t, sabemos
que las variables Zijt tomaran valor 0 en, al menos, todos los intantes anteriores
a t, relacion expresada con (7.6). Analogamente, y segun hemos expresado con
(7.7), vemos que toman valor 0 en todos los instantes posteriores a t si sabemos
que se concluye antes.
Ahora, por logica sabemos que, dadas dos proposiciones p y q, la implicacion
p q se modeliza de manera equivalente a la disyuncion p q. Si aplicamosesto a las implicaciones anteriores, junto con las variables it y
it, se llega a las
desigualdades (7.12)(7.15).Los valores it, it y mtij=1 pij actuan como cotas en (7.12), (7.14), (7.13) y
(7.15) y permiten los casos en que estas restricciones hayan de ser redundantes
para el modelo.
Por otra parte, las restricciones (7.2), (7.3), (7.5) y (7.8) cumplen funciones
analogas a las de sus homologas en el modelo determinista. Concretamente, (7.2)
fuerza a que cada tarea se realice una y solamente una vez y de un unico modo.
(7.3) sufre una variacion con respecto al caso determinista: verifica que el instante
en el que se inicie cada tarea permita que, en media, si todo sucede de acuerdo con
lo previsto, se satisfaga la ventana de tiempo, pero dejara abierta la posibilidad
de que en algunos escenarios no se satisfaga.
Con (7.4) conseguimos que si una tarea i se inicia con retraso en un escenario,
entonces ese retraso afecte tambien a su finalizacion y sea posible que i se concluya
mas tarde de su fecha de finalizacion mas tarda di.
La restriccion (7.5) garantiza que, en el caso de que la tarea i preceda a la tarea
i, i no pueda iniciarse si i aun no ha terminado. Tambien define las variables del
retraso inicial que pueden sufrir las tareas. El terminomti
j=1
dipijt=ri
(t+ pij
)Xijt
del primer miembro de la desigualdad represeta el instante en el que se tiene
32
-
previsto que finzalizara la tarea i; junto con RIi tenemos cuando finaliza la tarea
i. De manera similar el segundo miembro muestra cuando empezara la tarea
i.mti
j=1
dipijt=ri Xijt es el instante en que se decidio empezar la tarea i
en la
primera etapa; la variable RIi tomara su valor de forma que, si RIi > 0, el
segundo miembro sea el nuevo instante en el que se iniciara i, de forma que la
relacion de precedencia se siga respetando.
La restriccion (7.8) es con la que se consigue que la cantidad de recursos
disponibles sea suficiente para cubrir las necesidades de las tareas que se esten
llevando a cabo en el da t.
Necesitamos, finalmente, dos tipos mas de restricciones, que son las que rela-
cionan a las variables Xijt y Zijt, de forma que, una vez este resuelto el modelo,
no se contradigan sus resultados. Con (7.9) forzamos a que el modo j en que se
realice una tarea i coincida para las variables Xijt y Zijt.
Indicamos tambien que las variables Xijt y Zijt son binarias, as como las
it
y it; y que las relativas a los retrasos, RIi RF
i , son enteras no negativas, igual
que las Yk.
8. Experiencia computacional con el problema
estocastico
De nuevo, hemos implementado el modelo descrito en GAMS, junto con el optimi-
zador de CPLEX. Los datos que se emplearon en la seccion 5 han sido adaptados
a un caso estocastico para poder introducirlos en este nuevo modelo.
A diferencia de lo ocurrido con el caso determinista, la obtencion de resultados
ha sido mucho mas costosa y las herramientas disponibles no han sido suficien-
temente potentes para abordar el problema en su totalidad. Hemos trabajado
unicamente con grupos de uno y dos cultivos y, ademas, ha sido necesario reducir
el numero de periodos de tiempo: no hemos aplicado el modelo sobre todos los
das del ano sino sobre un subconjunto de ellos. Con ordenadores mas potentes
tambien se puede ampliar el numero de escenarios futuros, que en los casos que
hemos trabajado ha sido de tres: uno con las duraciones empleadas en la seccion 5
y otros dos con variaciones (siempre empeoramientos de las situaciones previstas)
33
-
sobre ellas.
Para ilustrarlo, podemos citar que, para un grupo con un unico cultivo, hemos
necesitado 8233 restricciones y 8502 variables binarias, una dimension mayor
incluso que la del problema determinista para los siete cultivos con cuyos datos
se contaba, aparte del tiempo computacional necesitado (23,806 segundos), que
tambien es mayor. La resolucion para un cultivo mas ha requerido un tiempo de
1007,314 segundos.
9. Conclusiones
En este trabajo hemos propuesto dos modelos de programacion lineal, uno deter-
minista y otro estocastico, que ayuden a la planificacion de un ano agrcola.
Tras una muestra de ejemplos de aplicaciones de la programacion matematica
que se han hecho recientemente en la agricultura, hemos presentado el problema
que se nos haba planteado: dar un calendario para la secuencia de tareas que
se tienen que llevar a cabo en una explotacion agraria, as como determinar las
necesidades de maquinaria y mano de obra, y con el proposito de que los gastos
y los retrasos en la finalizacion de las tareas sean mnimos.
Hemos presentado tambien algunos de los resultados obtenidos tras la im-
plementacion de los modelos. En este aspecto cabe resaltar la mejora de las
herramientas en los ultimos anos, de forma que ahora podemos enfrentarnos a
problemas que en su momento no pudieron abordarse en su totalidad, o en tiem-
pos de ejecucion mayores. Paralelamente, hemos podido ver que el planteamiento
estocastico requiere la definicion de mas variables que la version determinista del
mismo problema. Tanto es as que, con las herramientas de las que disponemos,
no hemos podido resolverlo en su totalidad y nos hemos visto obligados a reducir
los periodos de tiempo considerados y la cantidad de cultivos con la que se pen-
saba proceder en la explotacion. En futuro se podra retomar el modelo y, quiza,
con los futuros avances, se pueda resolver con mas escenarios, mayores grupos de
cultivos y considerando todos los das del ano.
Un modelo matematico no representa la realidad tal y como es. Es inevitable
prescindir de ciertos elementos que no se pueden expresar matematicamente o que
34
-
un ordenador no va a poder resolver. Un ejemplo es este modelo de programacion
estocastica, en el que hemos reducido el problema de que pasara en el futuro a un
conjunto de posibles resultados finales, ponderados por probabilidades que hemos
estimado previamente.
Otra consecuencia de esta diferencia entre los modelos y la realidad es que
planteamientos distintos de un mismo problema pueden dar lugar a modelos que
no sean iguales. Las soluciones finales no tienen por que ser notablemente diferen-
tes, pero el modo de llegar a ellas puede no compartir las mismas ideas esenciales.
Podemos ver en otros proyectos sobre este mismo problema la toma en conside-
racion de elementos que aqu hemos decidido no incluir en el modelo (como la
posibilidad de disponer de un recurso de forma parcial) o interpretaciones para-
lelas de los datos (podramos haber empleado una variable para cada recurso que
fuera necesario en la explotacion en lugar de variables asignadas a cada grupo de
recursos).
Las matematicas han ayudado a abordar problemas que tienen que ser re-
sueltos da a da, ano tras ano. Quiza, sin las herramientas con las que contamos,
algunos de ellos no habramos sido capaces de resolverlos, o incluso de plantearlos.
35
-
Bibliografa
[1] L. Alfandari el al.. A MIP flow model for crop-rotation planning in a context
of forest sustainable development. Annals of Operations Research, 2011. 190:
149-164.
[2] J. Alvarado Boirivant, El analisis post-optimal en programacion lineal
aplicada a la agricultura, 2011 [en lnea].
[27 de mayo de 2012]
[3] J. R. Birge, Francois Louveaux, Introduction to Stochastic Programming.
Springer, 1997. 2: 51-63, 3: 83-103, 4: 137-141, 5: 155-163.
[4] Alysson M. Costa et al.. Sustainable vegetable crop supply problem with
perishable stocks. Annals of Operations Research, 2011. doi: 10.1007/s10479-
010-0830-y.
[5] J. M Ferrer Caja, El problema estocastico lineal bietapico con recurso. Tra-bajo de investigacion, Universidad Complutense de Madrid. 1: 6-12, 4:57-62.
2004.
[6] W. K. Klein Haneveld, A. W. Stegeman. Crop succession requirements in
agricultural production planning, European Journal of Operational Research,
2005. 166: 406-429.
[7] M Teresa Ortuno. Introduccion a la Programacion Lineal Estocastica [Apun-tes de clase].
[8] M. Radulescu, C. Z. Radulescu, G. Zbaganu. A portfolio theory approach
to crop planning under environmental constraints. Annals of Operations Re-
search. 2011. doi: 10.1007/s10479-011-0902-7.
[9] A. Ramos et al., Modelos matematicos de optimizacion, 2010 [en lnea].
[25 de junio de 2012]
36
-
[10] B. Vizvari et al.. Stochastic programming and simulation based analysis of
the structure of production on the arable land. Annals of Operations Research,
2011. 190: 325-337. doi: 10.1007/s10479-009-0635-z.
[11] Begona Vitoriano et al. Two alternative models for farm management: discre-
te versus continuous time horizon. European Journal of Operational Research,
2003. 144: 613628.
[12] H. P. Williams, Model building in mathematical programming. John Wiley,
1993. 3:17-35, 12: 231-258, 13: 261-304.
[13] Wikipedia: George Dantzig [en lnea].
[8 de abril de 2012]
[14] Wikipedia: Martin Beale [en lnea].
[5 de mayo de 2012]
[15] Instituto Tecnico Agronomico Provincial, S.A. [en lnea].
[17 de junio de 2012]
37
AbstractIntroduccinLa programacin matemtica y la agriculturaPlanteamiento del problemaModelizacin del problema deterministaVariablesFuncin objetivoRestricciones
Resultados computacionalesProgramacin estocsticaProblemas en dos etapasFormulacinModelizacin. Anlisis de escenariosRepresentacin
Modelizacin del problema estocsticoVariablesFuncin objetivoRestricciones
Experiencia computacional con el problema estocsticoConclusionesBibliografa