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