Otimização linear aplicada ao plantio sustentável de vegetais · super agradáveis, roscas de goiabada e cuecas-viradas que levava para casa (que não se limitaram ao primeiro

Otimização linear aplicada ao plantio sustentável de vegetais

Rafael Martins Gomes

Otimização linear aplicada ao plantio sustentável de vegetais

Rafael Martins Gomes

Orientador: Prof. Dr. Marcos Nereu Arenales

Dissertação apresentada ao Instituto de Ciências Matemáticas e de Computação - ICMC-USP, como parte dos requisitos para obtenção do título de Mestre em Ciências - Ciências de Computação e Matemática Computacional. VERSÃO REVISADA.

USP – São Carlos agosto de 2011

SERVIÇO DE PÓS-GRADUAÇÃO DO ICMC-USP

Data de Depósito: 02.08.2011 Assinatura:________________________

Ficha catalográfica elaborada pela Biblioteca Prof. Achille Bassi e Seção Técnica de Informática, ICMC/USP,

com os dados fornecidos pelo(a) autor(a)

G633oGomes, Rafael Martins Otimização linear aplicada ao plantio sustentávelde vegetais / Rafael Martins Gomes; orientadorMarcos Nereu Arenales -- São Carlos, 2011. 88 p.

Dissertação (Mestrado - Programa de Pós-Graduação emCiências de Computação e Matemática Computacional) --Instituto de Ciências Matemáticas e de Computação,Universidade de São Paulo, 2011.

1. Rotação de culturas. 2. Otimização linear ediscreta. 3. Geração de colunas. 4. Agriculturasustentável. I. Arenales, Marcos Nereu, orient. II.Título.

AGRADECIMENTOS

Muitas pessoas estiveram envolvidas nessa fase de minha vida, e ajudaram a

torná-la em uma das experiências mais amadurecedoras e especiais que tive até hoje.

Espero conseguir mencionar todas essas pessoas, de alguma forma, sabendo que todas

foram especiais a seu modo.

Agradeço primeiramente a Deus, por me dar a vida e os dons que possuo,

permitindo que meus esforços e estudos me trouxessem a esse ponto.

Agradeço a minha mãe, Áurea Martins Gomes, por ser o pilar de sustentação da

minha vida, minha inspiração, minha heroína. Sem sua dedicação e seu carinho, eu

nunca me tornaria a pessoa que hoje sou. Lembrar dela sempre foi a forma que eu

encontrava para obter motivação em me dedicar a tudo que fiz e continuo fazendo. Não

há palavras que descrevam o quão especial é o amor de mãe. Desejo a ela toda a

felicidade do mundo, e estarei a seu lado para todo o sempre, fazendo de tudo que

estiver a meu alcance para que minha mãe tenha uma vida repleta de paz, felicidade e

harmonia. Amo-te mais que tudo neste mundo, mãe!

Agradeço à minha família, mas preciso deixar uma menção honrosa à minha avó

materna, Maria Boretti Martins, por preparar deliciosos almoços todos os sábados, entre

outras iguarias clássicas de avós que adoram engordar seus netos. Um exemplo de

disposição de dar inveja a muitos jovens, espero me tornar alguém tão inspirador como

minha avó um dia.

Agradeço ao meu melhor amigo, Gustavo Monteiro Dias, pela amizade

inabalável que nesta data passa dos 18 anos. A certeza de que encontraria um rosto

amigo em São Carlos foi uma das razões que tive coragem de encarar a mudança para

uma cidade desconhecida. Desejo ao Gustavo muito sucesso, mas não é como se ele não

soubesse o quanto eu torço por ele.

Agradeço aos professores que participaram das bancas de qualificação e defesa,

Alysson Machado Costa, Reinaldo Morabito e Vitória Pureza, por aceitarem o convite e

compartilharem de sugestões de melhorias. Certamente muitas das lições que aprendi

serão utilizadas no futuro em outras ocasiões, de alguma forma.

Agradeço ao meu orientador, Marcos Nereu Arenales, com quem aprendi muito,

principalmente a organizar minhas tarefas e responsabilidades. Não hesito em afirmar

que hoje sou uma pessoa muito mais capacitada e auto-didata, e devo isto ao apoio do

meu orientador. Saiba que seu último aluno adotado termina o mestrado mais

responsável e com mais maturidade graças a você.

Agradeço às funcionárias da secretaria de pós-graduação do ICMC da USP de

São Carlos, sempre muito atenciosas, pacientes e prestativas: sua ajuda por muitas vezes

tornou os processos burocráticos necessários e exigidos pela faculdade uma tarefa

menos árdua e de forma organizada. O agradecimento se estende aos funcionários de

toda a USP de São Carlos, pelos serviços oferecidos.

Agradeço aos professores e alunos do Laboratório de Otimização do ICMC da

USP de São Carlos, pela enorme amizade e apoio durante todo este tempo. Muitas

foram as risadas, papos de todas as naturezas, pizzadas, temakis às quartas-feiras,

jogatinas, almoços, jantares, amigo secreto, festas de aniversários com bolos da Maria

Doces... inúmeras memórias agradáveis que levo no meu coração e lembrarei com

muito carinho. Ver um grupo onde professores e alunos convivem e se socializam tão à

vontade me faz querer visitar e participar de eventos com a turma em novas

oportunidades. Desejo sucesso a todos!

Como alguém que encontrou no Kung Fu um estilo de vida, eu não poderia

deixar de agradecer pessoas que foram e estão sendo importantes nessa caminhada.

Seguindo a ordem cronológica, agradeço inicialmente ao meu niisan, meu irmão

adotivo mais novo, Luiz Paulo M. Tempester, por ser mais que um amigo, ser o irmão

que eu nunca tive. Seu apoio em uma fase crítica em minha vida foi fundamental para

que eu superasse as dificuldades, o que só foi possível por eu ter conhecido o Kung Fu

por intermédio dele. Por todo o apoio e reconhecimento do meu potencial em artes

marciais, agradeço meu niisan e lhe desejo muito sucesso, e ratifico que superá-lo-ei

como mestre em Kung Fu!

Agradeço ao Si Hing Rafael e Si Hing Juliano, instrutores da academia Tat

Wong de Campinas, onde meus treinamentos iniciaram, antes do início do meu

mestrado. Ambos perceberam em mim dedicação, empenho e potencial, e assim me

incentivaram e apoiaram durante os treinos. Lembro de lágrimas escorrerem após meu

último dia na academia. Sou grato a eles pela ajuda na fase inicial de meu treinamento,

que se estende até hoje!

Agradeço à Associação Fei Lung Sin de Kung Fu de São Carlos e ao Si Sok

Danilo Martins de Mello, por fornecer na faculdade treinos abertos e gratuitos, sempre

com seriedade e dedicação. Altruísmo como este do Danilo, se responsabilzando por

treinos sem exigir nada em troca enquanto se dedica à sua graduação, mostra o quão

especial este grupo é. Por mais que eu voltasse dolorido, com hematomas e cansado, os

treinos com o pessoal da AFLS eram a razão pela qual eu mal podia esperar pelo

anoitecer. Agradeço todos os colegas de treino destes dois anos e meio pelos ótimos

momentos juntos. Dentre os colegas deixo um agradecimento especial para o Sérgio

Aparecido Zanchetta Jr., conhecido entre os amigos como Zanka, por ter sido como um

padrinho de treino, também reconhecendo meu potencial e dedicação, e empenhando-se

em me ensinar. Graças ao pessoal da AFLS de São Carlos, ganhei uma maturidade nas

artes marciais que me ajudam em vários campos da vida até hoje.

Por fim, agradeço à União Long Fon Quan Kung Fu e Tai Chi Chuan de Mogi

Mirim (minha cidade natal) e ao Jo Sz Marcos Braga, onde comecei a treinar neste

último ano de mestrado e pretendo estabilizar. Desde que cheguei, pude ver que o Jo Sz

reconheceu minha maturidade em artes marciais. Se estou evoluindo tão rapidamente

dentro da LFQ, não posso negar que é devido ao empenho do pessoal da AFLS. Espero

atender as espectativas do Jo Sz Marcos e poder adquirir o título de mestre em artes

marciais com sua ajuda.

Na vivência em São Carlos, agradeço a Beth, funcionária da padaria que ficava

ao lado da kitnet que morei no primeiro ano, por muitos cafés da manhã com papos

super agradáveis, roscas de goiabada e cuecas-viradas que levava para casa (que não se

limitaram ao primeiro ano!), e por ser um exemplo de determinação e garra. E agradeço

também à Gisele Paladine Basílio Conquista, funcionária faz-tudo da temakeria que eu e

colegas sempre íamos desfrutar de culinária japonesa: assim como a Beth, tive papos

super agradáveis com a Gisele e pude conhecer mais uma pessoa que é exemplo de

força e amor. Desejo muito sucesso e felicidade às duas!

Agradeço também amigos distantes, mas com quem converso ocasionalmente e

me trazem memórias tão boas: Raquel Costa, Cristiane Gelatti e Ronaldo Campos,

amigos desde os tempos do ensino médio; Camila Kamarad, Sílvia Murata e Sidney

Abe, amigos da graduação; e Janaína Santos, Aline Miyuki, Juliana Moraes e Juliana

Otaviani, amigas do meu antigo trabalho. Saudades de tempos que não voltam mais,

mas que mostram o quão especial essas amizades são!

Agradeço ao professor de Educação Artística Avelino Francisco Dias Ferreira,

conhecido como Kiko, colega de trabalho de minha mãe. Além de ter se tornado um

grande amigo nosso, em um fim de semana de intensos testes na reta final do meu

mestrado o carregador de meu notebook queimou, e foi o empréstimo do carregador do

notebook do Kiko, que possuía um igual ao meu, que eu pude dar contuinidade e

finalizar meus experimentos (que ainda duraram semanas a fio). Obrigado, Kiko, muito

sucesso e felicidade!

Agradeço aos colegas das repúblicas que morei, Rep Capelinha e Rep 29, pelos

papos descontraídos e risadas diárias. Apesar de eu me considerar o paizão da turma,

por ser o único de pós-graduação, sempre me sentia à vontade com todos.

Agradeço ao CNPq pelo apoio financeiro fornecido durante meu mestrado,

permitindo que este estudo fosse concluído e todas as memórias boas e agradecimentos

aqui listados tenham se concretizado.

RESUMO

O planejamento de rotações de culturas é um tema de interesse em ascensão por permitir

uma redução significativa no uso de adubos industriais, agrotóxicos e outros produtos

químicos no cultivo, permitindo a auto-sustentação e qualidade das terras cultivadas.

Este trabalho centraliza em utilizar rotações para atender uma demanda periódica pré-

determinada, respeitando as restrições relativas a aspectos ecológicos que auxiliam na

estabilidade geral do solo para definir uma rotação de culturas factível. Modelos

matemáticos que consideram um tamanho mínimo de lote a ser usado por uma rotação e

métodos heurísticos, baseados em geração de colunas, são apresentados. Uma análise

detalhada do comportamento dos métodos perante variações em diferentes parâmetros e

critérios é realizada. A primeira heurística, denominada Algoritmo GC-BC, obteve

resultados de melhor qualidade e de forma mais rápida que a segunda heurística,

denominada Heurística Lote Fixo. Entretanto, combinando ambas heurísticas foi

possível obter os resultados mais satisfatórios, ou seja, soluções que respeitam a

condição de lote mínimo em um tempo computacional aceitável para um planejamento

anual, cujos valores são próximos a um limitante superior. A ideia subjacente de gerar

colunas adicionais para um problema mestre restrito produz soluções de qualidade, o

que pode vir a ser aplicado em outras áreas de pesquisa que necessitam da geração de

colunas para uma resolução em tempo computacional viável.

Palavras-chave: rotação de culturas, otimização linear e discreta, geração de colunas,

agricultura sustentável

ABSTRACT

The crop rotation planning is a rising topic for providing a significative reduction on the

usage of industrial fertilizers, pesticides and other chemical, allowing the soil to self-

sustain. This study focus on using rotations to meet a periodic and pre-defined demand

while ecologic restrictions, that help sustain the soil’s stability, define a valid crop

rotation. Mathematical models that consider a minimum size of a used lot associated

with a given rotation and heuristic resolution methods, based on column generation, are

presented. A detailed analysis of the methods behaviour before changes on parameters

and criteria is performed. The first heuristic, called GC-BC Algorithm, achieved better

and faster results compared to the second heuristic, called Fixed Lot Heuristic.

However, combining both heuristics produced even better results, that is, solutions that

respect the minimum lot sizing restrictions in good execution time for an annual

planning. The idea behind of generating additional columns to the restricted master

problem produces good quality solutions, which may be applicable in other research

areas that require column generation for their resolution with a reasonable execution

time.

Keywords: crop rotation, linear and combinatorial optimization, column generation,

sustainable agriculture

SUMÁRIO

Introdução 01 Revisão bibliográfica 05 Modelos matemáticos 09

Modelo base de rotação 11 Modelo de ot imização l inear com atendimento de demanda 19 Modelo de otimização inteira para o problema de atendimento de demanda e lote mínimo 23

Métodos heurísticos de resolução 27 Heuríst ica GC-BC 27

Heuríst ica Lote Fixo 30

Testes computacionais 35 Testes heuríst ica GC-BC 37

Testes prel iminares 37 Testes ponderação-α 43 Testes conjunto de restr ições (3.6) 47

Testes curva de ef iciência 50 Testes cri tér io de parada relaxado 53 Testes simetr ia 57

Testes lote mínimo 60 Testes heuríst ica Lote Fixo 63

Testes f ixa lote pequeno 63

Testes f ixa lotes grandes 67 Testes f ixa dois lotes 70 Testes f ixa maior demanda 72

Comparativo f inal 76

Conclusões e Perspectivas 81 Referências bibliográficas 85 Apêndice 87

1

1 INTRODUÇÃO

Uma prática comum na agricultura e altamente notável no Brasil, devido à sua

tradição histórica no cultivo de cana-de-açúcar, é a monocultura: com administração

relativamente fácil no constante plantio de uma única cultura, os custos totais dos

alimentos são reduzidos, embora seja alta a utilização de agrotóxicos e fertilizantes

sintéticos, entre outros produtos e recursos industriais que são poluentes e não

renováveis. Apesar de possuir um custo final menor, a monocultura acarreta em uma

perda gradativa das propriedades físicas e químicas do solo devido ao uso intensivo dos

produtos industriais, podendo até tornar-se improdutivo em caso de má administração.

Parte da poluição pode ser levada às águas locais, ao solo e alimentos, trazendo danos à

saúde humana e alterando as condições ambientais da região. Há um custo incalculável

que vem sendo desprezado. Surge neste contexto a necessidade de novas abordagens

para melhor sustentabilidade ambiental e financeira de pequenos e médios agricultores,

os quais não possuem capital para manutenção e investimentos com produtos industriais

e gerar produções mínimas para viabilidade econômica (Gliessman, 2000).

A consciência ambiental é, hoje em dia, mais difundida. Nota-se a preocupação

com o desenvolvimento sustentável entre a população e nos meios industrial, político e

governamental. Por exemplo, limites para a emissão de poluentes e demais cuidados

como tratamento e purificação, mesmo que acarretem em um investimento maior, são

implantados em indústrias, visando melhor cuidar do meio ambiente e de outras

questões sociais. Já no setor da agricultura, o acesso de pequenos produtores ao

mercado e cuidados ecológicos, como a redução do uso de pesticidas, ganham destaque

no ponto de vista econômico e sustentável. Neste contexto, uma medida que pode

atender estas expectativas no meio agrícola é a rotação de culturas.

A rotação de culturas traz diversidade vegetal na terra em que é aplicada:

diversidade esta, que foi mostrada em estudos ecológicos e agronômicos, capaz de

melhorar a exploração dos recursos produtivos do solo, além de auxiliar no controle de

pragas e pestes com uso reduzido de inseticidas e outros produtos industriais,

aumentando a estabilidade do solo defronte pressões ambientais e estendendo assim sua

vida útil (Altieri et al., 1995; Vandenmeer, 1992). Para os produtores, uma maior

variedade de produção ajuda a manter uma estabilidade econômica, reduzindo o

impacto causado por oscilações nos preços e no mercado de oferta e demanda, caso

2

estes venham a ocorrer. Vemos uma sustentabilidade não só agrícola e ecológica, mas

também econômica com o uso de rotações de culturas.

Porém, pequenos e médios produtores possuem uma área de plantio reduzida

disponível e sua produção tende a ser descontínua e heterogênea. Associações e

cooperativas atuam unindo estes produtores agrícolas para que haja uma produção

constante e uniforme: na região Sudeste do Brasil temos, por exemplo, associações

como Horta e Arte (SP) e Sítio do Moinho (RJ) (Campanhola e Valarini, 2001). Desta

forma, os gastos administrativos, desde planejamento de plantio e conexões de mercado

até empacotamento, deixam de ser uma tarefa individual e custosa, sendo feita em

conjunto e padronizada. A inclusão de pequenos agricultores no mercado é de

fundamental importância econômica, pois estimulam a compra e venda no comércio

local e aumentam o número de empregos (Ong’Wen e Wright, 2007).

Neste contexto, este trabalho propõe modelagens matemáticas e métodos de

solução que representem as decisões a serem tomadas por estas cooperativas, ou seja, o

quê, quando e quanto será produzido por cada membro da associação, de forma a

cumprir uma demanda de mercado periódico prevista ao longo do tempo. Com um

planejamento adequado, garante-se o atendimento da demanda exigida com o melhor

aproveitamento da terra, produzindo alimentos com redução no uso de fertilizantes e

afins, aumentando a qualidade da produção.

Um planejamento de rotação de culturas consiste em repetir uma sequência de

plantio após seu término. O período de tempo deste planejamento pode ser variado e,

inclusive, ser um fator característico dos cultivos a serem usados: plantações de laranja,

por exemplo, ocupam a terra por anos. Hortaliças, por sua vez, variam de algumas

semanas a alguns meses. Ao definir um rotação de culturas, as características das

plantações devem ser consideradas para um planejamento efetivo.

O devido planejamento do cultivo do solo pode ajudar a manter a fertilidade do

solo naturalmente, garantindo um uso contínuo viável econômica e ecologicamente. O

uso de uma adubação verde pelo plantio de uma leguminosa melhora a fertilidade e

protege o solo, assim como um período sem nenhum cultivo permite o controle

biológico de pragas e doenças e contribiu na reciclagem dos nutrientes da terra. (Altieri

et al., 1995; Gliessman, 2000). Por estas razões, fatores ecológicos e agronômicos são

considerados na maioria dos modelos matemáticos relacionados à rotação de culturas.

Quanto aos aspectos ecológicos, alguns a se levar em consideração no cultivo de

hortaliças são: o não cultivo de culturas de mesma família botânica em sequência em

3

um mesmo local, uma cultura para adubação verde (geralmente leguminosa) em algum

período da rotação para auxiliar na fixação de nitrogênio, assim como um período de

pousio (sem cultivo), para o descanso da terra. Estes critérios serão usados como

restrições para definir uma rotação de cultura factível para o problema abordado neste

estudo.

Na seção seguinte, é feita uma revisão bibliográfica sobre rotações de culturas,

apontando alguns trabalhos e mostrando o desenvolvimento nesta área desde os

primeiros trabalhos apresentados no final da década de 30. Um enfoque maior é dado

nos trabalhos e tese de doutorado de Santos (2007, 2008, 2009, 2010a, 2010b), os quais

serviram de base para este estudo e que utilizam critérios ecológicos como os

mencionados acima em seus modelos.

Na Seção 3, o modelo matemático que representa os critérios ecológicos e

definem uma rotação factível é apresentado. Junto a este, o modelo matemático

referente ao problema de atendimento de demanda é discutido e demonstramos como

ambos são unificados e caracterizados como um problema mestre e um subproblema. O

problema mestre, originalmente formado por variáveis de decisão lineares a respeito do

tamanho de lote a ser usado para cada rotação, é expandido com a inclusão de restrições

de lote mínimo para as variáveis de decisão, determinando o modelo final inteiro-misto

a ser estudado neste trabalho. O uso de um lote mínimo é interessante em aplicações

práticas, já que o manuseio e administração de espaços muito pequenos de terra podem

se tornar difíceis e até mesmo custosos, não justificando o uso destes lotes pequenos

conforme a solução ótima de um modelo linear.

A Seção 4 discute a dificuldade da resolução por métodos exatos do modelo

proposto da Seção 3, e detalha duas heurísticas criadas visando contornar tal

dificuldade: a primeira, denominada Algoritmo GC-BC, é uma alternativa ao branch-

and-price, método de resolução intuitivo a um problema de geração de colunas que

contém variáveis discretas, cuja ideia é realizar a geração de colunas e a resolução via

branch-and-cut separadamente; a segunda proposta, a Heurística Lote Fixo, resolve o

problema linear e define, pelo uso de algum critério de seleção, uma variável a ser

fixada em um valor que satisfaça a condição de lote mínimo.

A Seção 5 consiste dos testes computacionais realizados, com diferentes

enfoques de resolução e análise de comportamento do modelo perante mudanças de

parâmetros para o Algoritmo GC-BC, como ponderações entre o lucro e a criação de

lotes, diferentes valores de lote mínimo, entre outros. Para a Heurística Lote Fixo,

4

avalia-se quatro diferentes critérios de escolha de variáveis. Todos os métodos são

avaliados quanto ao tempo computacional e qualidade de solução em relação à

resolução linear do modelo relaxado.

Por fim, a Seção 6 consiste de um sumário das conclusões ao analisar os

resultados obtidos pelos testes realizados e descritos na Seção 5, e discute novas

possibilidades de estudos futuros e aplicação das técnicas propostas em outras linhas de

pesquisa.

5

2 REVISÃO BIBLIOGRÁFICA

O tema planejamento de plantio de culturas existe há tempos na literatura, desde

o trabalho pioneiro de Kantorovich (1939, traduzido do russo em 1960), o qual mostrou

este tema como sendo tratável com ferramentas matemáticas em um modelo de

otimização linear, com objetivo de maximizar a produção. Uma abordagem mais

profunda foi apresentada em Chicago no primeiro congresso em aplicações de

otimização linear, em 1949, por Hildreth e Reiter (artigo publicado em 1951), que

propuseram um modelo para particionar uma área de plantio utilizando-se de rotações

pré-definidas nessas partições, argumentando que assim os custos com manutenção

(irrigação, mão-de-obra, entre outros) e os riscos econômicos seriam reduzidos. Os

autores também argumentam sobre as vantagens das rotações de culturas em relação ao

aumento da produção e melhor uso dos recursos. Nesse modelo, as variáveis de decisão

eram o tamanho das áreas com cada rotação.

Rotações pré-definidas foram totalmente descartadas por El-Nazer e McCarl

(1986), em que um problema de rotação era solucionado com sequências de culturas

cultivadas uma após a outra anualmente, em áreas homogêneas. Um novo enfoque, com

múltiplos plantios anuais e áreas heterogêneas, foi considerado posteriormente por

Dogliotti et al. (2003), que desenvolveram uma ferramenta computacional capaz de

gerar as rotações factíveis de um dado grupo de culturas de uma região do Uruguai,

além de considerar restrições de plantio sequencial de uma mesma cultura na rotação.

El-Nazer e McCarl (1986) também consideram que a ordem das culturas

cultivadas é de grande importância, supondo que a produtividade de uma cultura está

diretamente relacionada à cultura precedente ao seu plantio no mesmo local, podendo

essa produtividade ser afetada pelo cultivo de até quatro anos anteriores. Já se inicia,

aqui, a possibilidade de proibir certas sequências previamente à resolução do modelo,

seja por motivos ecológicos, agronômicos ou qualquer outro. Restrições quanto ao

plantio são abordadas por Haneveld e Stegeman (2005), com as sequências de culturas

definidas fortemente segundo as restrições impostas sobre o plantio, que consideram

não apenas o que foi plantado nos últimos anos, mas também a duração de cada

plantação. Os autores trabalham também com restrições de pousio inclusos nas rotações

a serem definidas, dependendo do sequenciamento das culturas.

6

Detlefsen e Jensen (2007) tomam uma abordagem diferente, focando a formação

da seqüência de plantio conforme a quantidade de nitrogênio presente no solo utilizado

para o cultivo das culturas plantadas nos anos precedentes: no caso do modelo proposto

foram consideradas culturas anuais, referindo-se então ao cultivo dos últimos três anos.

Os autores assumem que o tamanho dos lotes de terra a serem utilizados para cada

cultivo é fixo e determinado previamente, o que permite que o problema seja resolvido

como um problema de transporte.

Pouco se tratou, até então, a respeito de épocas de cultivo favoráveis: as rotações

não consideravam o período do ano em que seriam aplicadas. Clarke (1989) trouxe tal

consideração à tona, incluindo épocas propícias para o cultivo. Seu modelo, entretanto,

não tratava de possíveis influências que uma cultura podia trazer aos cultivos seguintes.

Alfandari et al. (2009) consideram um problema aplicado em Madagascar,

visando reduzir o desmatamento da região. Para preparar as terras para o cultivo, utiliza-

se uma técnica que envolve a queimada da vegetação local, mas devido ao seu uso

exaustivo e planejamento de curto prazo, as terras se tornam improdutivas. Desta forma,

outros lotes de terra passam pelo mesmo processo para dar continuidade ao cultivo. Os

autores propuseram um modelo que representa um planejamento a longo prazo,

atendendo uma demanda e minimizando a área a ser cultivada, reduzindo assim o

desmatamento contínuo e mantendo a fertilidade da terra.

No primeiro trabalho de Santos et al. (2007), o modelo proposto visa maximizar

o uso de terra para cultivos respeitando restrições ecológicas juntamente de restrições de

adjacências: uma área de cultivo previamente dividida em lotes fixos, cujas divisões

podem ser representadas por um grafo de adjacência. Assim como duas culturas de

mesma família botânica não podem ser cultivadas em sequência em uma mesma área,

elas são proibidas de cultivo em lotes adjacentes em um mesmo período de tempo.

Em Santos et al. (2008), o problema de rotações de culturas com restrição de

adjacência é expandido e explorado por reformulações, utilizando decomposição de

Dantzig-Wolfe e geração de colunas em sua resolução. Neste trabalho, os autores

exploram características de algumas distribuições espaciais comuns, como divisão em

tabuleiro ou lado a lado. A partir dessas características, o modelo principal pode ser

simplificado e a solução ótima obtida em um tempo computacional menor.

Santos (2009), em sua tese de doutorado, organiza os trabalhos para o problema

de rotações de culturas com enfoque em adjacência dos trabalhos anteriores, e propõe

uma proposta de resolução por branch-and-price é desenvolvida. O modelo com

7

atendimento de demanda também é desenvolvido, e considerações são feitas sobre a

minimização de lotes usados para o atendimento da demanda, assim como penalizações

de demandas não atendidas e desconsideração de lotes muito pequenos.

Santos et al. (2010b) focam unicamente no modelo com atendimento de

demanda, organizando e detalhando os esforços aplicados no problema descritos na tese

de doutorado da autora. Em Costa et al. (2010), os autores expandem o modelo de

demanda com a adição de estoques de produção. Porém, devido às características

perecíveis de hortaliças, os estoques não podem exceder um determinado período, assim

como parte do estoque é perdido ao longo do tempo. Além do método de resolução por

geração de colunas, uma programação estocástica de dois estágios com recurso é

proposta.

Por fim, em Santos et al. (2010a), os trabalhos anteriores da autora são

organizados e sintetizados em um único artigo. A consideração de estoques para o

problema de demanda é incluída, mas a extensão com estoques perecíveis de Costa et

al. (2010) não é mencionada nesta síntese.

8

9

3 MODELOS MATEMÁTICOS

A rotação de culturas consiste em definir uma sequência de plantio para uma

dada área que se repetirá indefinidamente ao longo do tempo, ou seja, uma sequência de

decisões que se repetem após ser realizada. Este intervalo de tempo necessário para que

toda a sequência seja plantada é chamado de tamanho da rotação. Um exemplo simples

para visualizar o conceito de rotação, consideremos uma rotação com tamanho de 1 ano,

na qual uma cultura A é cultivada durante os 4 primeiros meses em toda a área de

cultivo, seguidos de 5 meses cultivando-se uma cultura B, e por fim 3 meses cultivando-

se uma cultura C: temos então o ciclo A-B-C e, após o cultivo de C, retoma-se o cultivo

da cultura A. Esta rotação é ilustrada na Figura 3.1 abaixo:

Figura 3.1: um exemplo de rotação das culturas A, B e C

O planejamento adequado do cultivo pode ajudar a manter a fertilidade do solo

naturalmente, garantindo um uso contínuo viável econômica e ecologicamente, e

também permite o controle biológico natural de pragas e doenças, minimizando o uso

de agrotóxicos ou quaisquer outros produtos químicos, gerando uma maior estabilidade

geral do solo e de suas características físicas, químicas e biológicas. Para isto, fatores

ecológicos e agronômicos são considerados na maioria dos modelos matemáticos

relacionados à rotação de culturas.

Dentre os aspectos ecológicos, três deles são considerados neste trabalho:

(a) culturas de mesma família botânica não são cultivadas em sequência em um

mesmo local, evitando assim a proliferação de pragas e doenças: ressaltemos que

organismos-pestes costumam atacar culturas de uma família botânica em

comum;

(b) um cultivo de uma cultura para adubação verde (comumente realizado pelo

plantio de leguminosas, sem colheita, visando estabilizar o nível de nitrogênio

do solo) deve ser incluído no planejamento da rotação;

10

(c) um tempo (de duração pré-determinada) chamado pousio, em que nada é

cultivado e a terra tem sua vegetação espontânea crescendo durante este tempo,

permitindo que o solo recupere sua estrutura (tanto física quanto biológica) e

ajudando inclusive no controle biológico de alguns insetos e ácaros, também

deve estar incluso no planejamento da rotação.

Os aspectos ecológicos listados acima são considerados no modelo proposto por

Santos et al. (2007), que será o modelo base considerado neste trabalho. Diferentes

considerações podem ser feitas ao determinar uma rotação: os critérios ecológicos (a)-

(c) listados acima aplicam-se bem à rotações de hortaliças, que são o objeto de estudo

deste trabalho.

As sub-seções a seguir explicitam os modelos matemáticos usados neste estudo:

primeiramente, define-se as restrições que caracterizam uma rotação, respeitando os

critérios ecológicos (a)-(c) e outros aspectos técnicos, tais como período adequado de

plantio e períodos de colheita. Na sequência, modela-se o problema abordado de

atendimento de demanda e, por fim, ambos os modelos são reformulados em problema

mestre e subproblema, para definir rotações para o cumprimento de demanda.

11

3.1 MODELO BASE DE ROTAÇÃO

Para simplificar a modelagem, discretizamos o tamanho da rotação em unidades

de tempo menores chamadas períodos, os quais definem os possíveis instantes para as

tomadas de decisão, bem como os dados do problema. Por exemplo, uma rotação de um

ano pode ser discretizada em 12 meses, de modo que as ações são do tipo: plante a

cultura A no mês 3, a qual deve ser cultivada durante 5 meses. As demandas e colheitas

são quantidades também descritas nesta discretização: por exemplo, a cultura A possui

demanda de 50 unidades (que podem ser em kg ou outro unidade adequada de medida)

no período 8.

Considere que o tamanho T da rotação seja dividida em M períodos. Por

exemplo, T=1 ano pode ser dividido em M=12 meses. Uma programação de rotação de

culturas de tamanho M é um calendário de plantio das culturas da rotação. Para tomar

esta decisão, os critérios ecológicos (a)-(c) apresentados na seção anterior são

considerados. Por simplicidade, relembramos de forma resumida estes critérios:

(a) Uma cultura não pode ser cultivada após uma outra de mesma família botânica;

(b) O plantio de uma cultura para a adubação verde deve ser incluída na rotação;

(c) Um pousio deve ser incluído na rotação, por um tempo pré-estabelecido.

Adicionalmente, há restrições técnicas que se deve levar em conta: a época de

plantio e ciclo de cada cultura é variante entre elas. Cada hortaliça possui suas épocas

específicas de plantio, além de requerer um respectivo tempo para que as colheitas sejas

feitas. Essas restrições, que serão incluídas no modelo, são descritas como:

i. Cada cultura possui um conjunto de períodos favoráveis para seu plantio, os

quais devem ser respeitados;

ii. O tempo entre plantio e as colheitas (ciclo) é variante entre as culturas.

Estes critérios e restrições técnicas definirão as restrições matemáticas do

modelo. É importante relembrar que, por enquanto, a rotação de um único lote está em

questão.

12

Um exemplo (Santos, 2009) para ilustrar este modelo: considere três culturas e

rotações de duração de 1 ano, divididas em períodos de 1 mês (totalizando assim 12

períodos). A cultura X, pertencente à família botânica 1, possui ciclo de 5 meses e deve

ser plantada de janeiro a julho (referente aos períodos 1 a 7); a cultura Y, também da

família botânica 1, possui um ciclo de 4 meses e pode ser plantada durante todo o ano;

por fim a cultura Z, de família botânica 2, é utilizada para adubação verde e, além de

poder ser cultivada em qualquer período, possui um ciclo de 2 meses. O pousio exigido

é de 1 mês (1 período). Uma programação factível para este exemplo pode ser

visualizada pela Figura 3.2

P X Z Y

Período 1 2 3 4 5 6 7 8 9 10 11 12

Figura 3.2. Uma programação de rotação de culturas (fonte: Santos L. M., 2009)

Vemos nesta figura que a cultura X é plantada no mês (período) 3, dentro de seu

período favorável de plantio, e durando até o mês (período) 7. A cultura Z, de outra

família botânica e utilizada para adubação verde, sucede o cultivo, ocupando os meses 8

e 9. A cultura Y começa seu cultivo no mês 10, e é concluído no mês 1 do ano seguinte,

havendo então um período de pousio durante o mês 2. Ao mês 3, a cultura X é plantada

novamente e o ciclo se repete. Respeitamos aqui a necessidade de pousio, adubação

verde e não temos culturas de mesma família botânica plantadas sucessivamente, como

também não há sobreposição de cultivos, isto é, duas culturas não são plantadas

simultaneamente neste mesmo lote.

Define-se, então, um modelo matemático para este problema, respeitando os

critérios ecológicos e as restrições técnicas listadas acima. Os parâmetros e dados

usados são:

Parâmetros e dados:

M número de períodos de uma rotação;

C conjunto de culturas que podem ser selecionadas para o plantio, excluindo as culturas

para adubação verde;

G conjunto de culturas para adubação verde;

N cardinalidade de ∪C G, ou seja, o número total de culturas;

N+1 cultura fictícia que representa o pousio obrigatório de ciclo pré–definido;

13

NF número de famílias botânicas;

F(p) conjunto de culturas da família botânica p, p = 1..NF;

it ciclo de cultivo da cultura i, incluindo os períodos estimados para preparo do solo e

colheita: ou seja, o tempo em períodos do plantio até a colheita;

iI conjunto de períodos em que a cultura i pode ser plantada. Para o pousio, adotamos

1NI + = {1, ..., M}.

É possível definir um período restrito para o pousio, porém usualmente isso não

se mostra necessário. Alternativamente pode-se obrigar o pousio após o cultivo de uma

certa cultura, o qual poderia ser implementado como um período a mais para a cultura

em questão ou com o uso de restrições adicionais. Nota-se que o modelo pode ser

facilmente expandido conforme necessário.

As variáveis de decisão são:

Variáveis:

=contráriocaso

jperíodonoplantadaéiculturaasexij ,0

,1

para i = 1..N+1 e j iI∈

Utilizando-se destes parâmetros, dados e variáveis de decisão, uma formulação

matemática que caracteriza uma rotação factível é dada por:

� � ��,��

��

��

�

��≤ 1, � = 1. . � (3.1)

� � ��,��

�

��∈��

≤ 1, � = 1. . ��, � = 1. . � (3.2)

� � ��∈��∈�

= 1 (3.3)

� � �,��

��= 1 (3.4)

�� ∈ �0,1!, " = 1. . � + 1, � ∈ $� (3.5)

Obs.: nas equações (3.1)–(3.2), j – r ≤ 0 é substituído por j – r + M.

14

As restrições em (3.1) nos garantem que apenas uma cultura pode ocupar a terra

em um dado período (incluindo o pousio, que é tratado como uma cultura pelo modelo).

As restrições (3.2) proíbem o cultivo de culturas de mesma família botânica em

seqüência, garantindo então que diferentes famílias sejam plantadas após a colheita de

uma dada cultura. As restrições (3.3) e (3.4), por sua vez, nos garantem a ocorrência de

um cultivo de uma cultura destinada à adubação verde e um pousio, respectivamente.

Por fim, (3.5) definem as variáveis de decisão como binárias. Para as restrições (3.1) e

(3.2), apenas as variáveis xi,j-r tal que j-r iI∈ são consideradas.

As restrições (3.1) e (3.2) podem ser de difícil visualização. Para melhor

compreendê-las, utilizemos como referência primeiramente a figura abaixo, para ilustrar

a restrição (3.1):

Figura 3.3. Exemplificação do funcionamento das restrições (3.1)

Por simplicidade, todas as culturas do exemplo acima, A, B, C, D e E, possuem

um ciclo de quatro períodos para sua colheita a partir de sua plantação. Seja A a cultura

que desejamos plantar em um período j, e queremos verificar quais (e quando)

hortaliças podem ser plantadas. Cada cultura terá seu período de plantio verificado

conforme sua alocação na figura acima. Com isso, não seria possível plantar a cultura E

no período j-3, uma vez que sua colheita ocorreria no período j, conflitando com o

plantio de A. A cultura D, a ser plantada no período j-4, seria colhida no período j-1¸

podendo assim o período j ser utilizado pela cultura A. B e C seriam colhidas antes do

plantio de A, nos períodos j-3 e j-2 respectivamente. Neste caso, uma entre as culturas

B, C e D poderiam ser cultivadas sem conflito com o plantio de A em j, enquanto E não

seria viável de cultivo.

Portanto, para o cultivo de uma cultura i qualquer em um dado período j, é

necessário que os tk-1 períodos anteriores ao período j não tenham sido ocupados por

outra cultura k. Evitamos, assim, a sobreposição dos plantios.

15

De forma análoga para a restrição (3.2), temos o mesmo conceito. Referenciando

a figura abaixo para exemplificar:


Assumamos que A, B e D pertençam à mesma família botânica, todas com ciclo

de 4 períodos. Mesmo que D seja plantada em j-4 e, portanto, sua colheita ocorre em j-

1, evitando a sobreposição, A será cultivada no período seguinte j, o que não é

permitido. Para que não haja cultivos em sequência de culturas de mesma família, o

plantio deveria ser feito em um período j-5 (ou anterior), como mostrado pela cultura B

da figura 3.4, resultando em uma colheita no período j-2 (ou anterior).

Portanto, para o cultivo de uma cultura i qualquer em um dado período j, é

necessário que os tk períodos anteriores a j não tenham sido ocupados por uma dada

cultura k de mesma família botânica. Evitamos assim o cultivo sequencial de hortaliças

de mesma família.

Vale ressaltar que o número de pousios e de culturas para a adubação verde

exigidos na rotação podem assumir valores diferentes de 1, caso necessário. Neste caso,

as restrições (3.3) e (3.4) sofreriam algumas alterações, além da necessidade da inclusão

de um par de restrição que garanta um intervalo mínimo entre as ocorrências. Santos

(2009) discute estas alterações. Neste trabalho, entretanto, o número de pousio e

adubação verde a serem incluídos na rotação não será modificado.

O modelo (3.1)-(3.5), proposto inicialmente por Santos et al. (2007), não impede

que em um dado período, nenhuma cultura seja cultivada: isso implica, na prática, em

uma ocorrência de pousio, além do que é exigido pela formulação. Porém, isso não

implica em infactibilidade.

Note que as restrições (3.2) podem, sem perda de generalidade, ser reescritas

como:

� ��,� + ��,��∈�(&)

≤ 1, � = 1. . ��, � = 1. . � (3.6)

16

Assim como (3.2), as restrições (3.6) evitam o plantio consecutivo de culturas de

mesma família botânica, já que a sobreposição já é evitada por (3.1). Para visualizar

isto, utilizemos novamente um exemplo simples ilustrado na figura abaixo:


Seja A e D culturas de mesma família, e D com ciclo de 4 períodos. Para A

plantada no período j, D irá sobrepô-la se seu cultivo ocorresse em j-3. Esta

sobreposição já é evitada pela restrição (3.1). O cultivo em j-4 acarretará no cultivo de A

ocorrendo logo após a colheita de D, o que deve ser evitado. O cultivo em j-5, por sua

vez, não viola os critérios ecológicos definidos. Com a sobreposição já impedida por

(3.1), a restrição (3.2) pode ser simplificada: para o plantio de uma cultura i qualquer

em um dado período j, é necessário que no período j-ti não tenha sido ocupado pelo

plantio de uma cultura qualquer de mesma família botânica.

Com o uso da restrição (3.6), a matriz de coeficientes do problema torna-se mais

esparsa, podendo ser mais bem explorada por pacotes de otimização e a resolução do

modelo torna-se mais eficiente. Testes computacionais foram realizados para comparar

o desempenho obtido utilizando-se cada conjunto de restrição, e estão descritos na seção

5.1.3.

O modelo final adotado neste trabalho que define uma rotação de culturas

factível para um lote, respeitando os critérios ecológicos (a)-(c), é portanto:

� � ��,��

��

��

�

��≤ 1, � = 1. . � (3.7)

� ��,� + ��,��∈�(&)

≤ 1, � = 1. . ��, � = 1. . � (3.8)

� � ��∈��∈�

= 1 (3.9)

17

� � �,��

��= 1 (3.10)

�� ∈ �0,1!, " = 1. . � + 1, � ∈ $� (3.11)

Obs.: nas equações (3.7)–(3.8), j – r ≤ 0 é substituído por j – r + M.

A formulação matemática (3.7)-(3.11) é de fundamental importância para o

desenvolvimento deste projeto, pois determina as programações de rotações de culturas

de um lote a serem utilizadas em um problema de otimização detalhado na seção

seguinte.

18

19

3.2 MODELO DE OTIMIZAÇÃO LINEAR DE ATENDIMENTO DE

DEMANDA

Devido à realidade dos pequenos agricultores, com áreas de plantio disponíveis

reduzidas e culturas passíveis de plantio dependentes do solo e clima local, sua

produção não é constante e, com isso, não há condições para um comércio ativo de

forma independente, que além de exigir um abastecimento contínuo também exige

investimentos de limpeza, empacotamento e entrega: ou seja, há custos de produção e

logística que um produtor pequeno não consegue suportar. Cresce então o surgimento

de cooperativas ou associações, em que pequenos agricultores de uma região (podendo

ser ampla) trabalham em conjunto para atender a uma certa demanda, visto que suas

diferentes propriedades comumente permitem o cultivo de diferentes culturas devido à

variação climática e terrena, podendo assim cumprir a produção necessária

conjuntamente, compartilhando os custos de produção e logística. É necessário então

decidir quando e quanto será produzido de cada cultura por cada membro da

cooperativa.

O modelo para a programação de rotação de culturas com demanda (PRC-D)

visa atender uma demanda conhecida ao longo do tempo, considerando áreas de

produção heterogêneas (isto é, permitem o cultivo de diferentes hortaliças com

diferentes produtividades, conforme as características do solo e do clima de cada região

de plantio), mas ainda respeitando os aspectos ecológicos e restrições técnicas

discutidos anteriormente, modelado pelas restrições (3.7)-(3.11).

Consideramos um conjunto de áreas A1,...,AL disponíveis para o cultivo de

diferentes culturas pertencentes a um conjunto C (além de um conjunto G para as

culturas destinadas à adubação verde), culturas estas com suas demandas conhecidas ao

longo do tempo (não há demanda para as culturas pertencentes a G). Como explicado

anteriormente, as áreas apresentam diferentes características e com isso as culturas

podem ser passíveis ou não de plantio em cada uma delas, assim como apresentar

diferente produtividade. Deseja-se definir então um plano de plantio de culturas para

cada uma das L áreas de forma a atender a demanda, podendo cada área ser dividida em

diferentes lotes, cada um seguindo uma programação de rotação independente.

Definimos então os parâmetros e dados usados pelo modelo:

20

L número de áreas de cultivo (hortas ou fazendas, independentes entre si);

kC conjunto de culturas que podem ser plantadas na área k, k = 1..L;

kS conjunto das possíveis programações de produção para a área k, isto é,

todas as soluções do sistema (3.7) – (3.11);

I i conjunto de possíveis períodos de colheita para a cultura i;

dij

demanda da cultura i no período j (dependendo da cultura, este dado

pode ser unidade, peso ou volume).

Por simplicidade de notação, escrevemos ks S∈ para nos referirmos à s-ésima

programação para a área k. Para cada área k, as restrições (3.7)-(3.11) devem ser

satisfeitas com os dados correspondentes.

As variáveis de decisão são:

λks Tamanho em m² do lote reservado na área k a ser cultivado

conforme a programação ks S∈

Para cada programação ( ∈ )*, seja sijka a quantidade colhida por unidade de

área da cultura " ∈ +* no período � ∈ $�, na área de cultivo k.

Com estes dados é possível escrever então o modelo do PRC-D como:

,-./�0 = 12� � � 3*45*44∈67

8

*� (3.12)

s.a. � � 2��*4 5*44∈67

8

*�≥ :�� , � ∈ $�, " ∈ +* (3.13)

� 5*44∈67

≤ ;< , = = 1. . > (3.14)

5*4 ≥ 0, ( ∈ )*, = = 1. . > (3.15)

Sendo o parâmetroksc o retorno obtido por unidade de área k utilizando-se da

programação s. Notamos aqui que as restrições de adjacência de cultivo de culturas de

mesma família botânica aplicam-se apenas de forma temporal dentro de cada

programação de rotação: não há restrições de adjacência física entre os lotes. Restrições

21

de adjacência são abordadas nos diversos trabalhos de Santos, conforme descrito na

revisão bibliográfica.

A função objetivo (3.12) do modelo busca maximizar o retorno obtido pelas

áreas utilizadas de cada programação de produção. As restrições (3.13) nos garantem

que, ao somar as produções realizadas por cada programação de todas as áreas, a

demanda de cada cultura em cada período é atendida. As restrições (3.14), por sua vez,

nos asseguram que não será utilizada uma área total maior que a disponível em cada

uma das k = 1,...,L áreas, enquanto (3.15) garantem a não-negatividade das variáveis de

decisão.

Santos (2009) considera também a ocorrência de colheitas parciais, por ser um

aspecto prático de relevância. Para isso, o modelo (3.12)-(3.15) é reformulado,

adicionando então os seguintes dados:

?� número de períodos entre o plantio e a primeira colheita da cultura " ∈ +;

��*� quantidade obtida na r–ésima colheita da cultura " ∈ +* por unidade de área k,

para @ = 1, . . . , A� − ?� − 1

A partir da primeira colheita parcial, todo período subsequente passa a ter uma

colheita parcial disponível (indicada por pikr), até o último período do ciclo da cultura

em questão.

Assim, os dados no modelo (3.12)-(3.15) são alterados. Podemos reescrever o

retorno cks em função do planejamento de rotação correspondente. Seja �C��*4 a s-ésima

rotação da área k que satisfaz as restrições (3.7)-(3.11), que equivale a 1 se a cultura i é

cultivada no período j, e 0 caso contrário. Temos que o retorno obtido por unidade de

área de uma dada cultura i, no período j, desta programação é dado por

∑ ∑ ��*��C��*4��E��∈� .

Assim, se r i é o retorno unitário da cultura i, o retorno total por unidade de área

cks da rotação s para a área k é dado por:

3*4 = � @� � � ��*��C��*4��E�

��∈��∈/7

(iii)

22

Com o uso dos dados de produção, podemos também reescrever sijka , e definir a

quantidade obtida pela r-ésima colheita por unidade de área da cultura " ∈ +* no

período � ∈ $�, referente à área de cultivo k, como:

2��*4 = ��*��C�,��E��,*4 (iv)

Ou seja, a quantidade colhida por unidade de área no período j é definida pela

produção da r-ésima colheita, cujo plantio ocorreu no período j-oi-r.

Desta forma, o modelo (3.12)-(3.15) utilizando-se das reformulações (iii)-(iv) é

reescrito como:

,-./�0 = max � � � @� � � ��*��C��*4 5*4

��E�

��∈��∈/74∈67

8

*� (3.16)

s.a. � � � ��*��C�,��E��,*4 5*4

��E�

��4∈67

8

*�≥ :�� , � ∈ $�, " ∈ +* (3.17)

� 5*44∈67

≤ ;< , = = 1. . > (3.18)

5*4 ≥ 0, ( ∈ )*, = = 1. . > (3.19)

A função objetivo (3.16) utiliza a reformulação (iii) para definir o retorno total

obtido em uma única unidade (tipicamente monetária), e a restrição (3.17) é

reformulada conforme (iv) para definir que toda a produção atenda a demanda definida,

utilizando-se das colheitas parciais.

23

3.3 MODELO DE OTIMIZAÇÃO INTEIRA PARA O PROBLEMA

DE ATENDIMENTO DE DEMANDA E LOTE MÍNIMO

O modelo (3.12)-(3.15) e sua re-escrita (3.16)-(3.19) apenas definem que as

variáveis λks sejam não negativas: uma solução ótima pode incluir valores de λ

considerados muito pequenos, além de possivelmente possuírem grande diversidade de

rotações, ou seja, diferentes lotes. Isto é impraticável em uma situação real, visto que há

uma manutenção não contabilizada pelo modelo quanto à divisão dos lotes, e portanto

deve ser evitado. Faz-se necessário, então, o tratamento do número e tamanho dos lotes,

para evitar que um resultado indesejado ocorra. Santos (2009) propõe um modelo

simples para reduzir o número de lotes e algumas heurísticas simples para lidar com esta

dificuldade.

Neste trabalho, para lidar com a ocorrência de lotes muito pequenos exigimos

um tamanho de lote mínimo. Para isto, faz-se necessário incluir variáveis binárias yks,

referentes a cada variável λks. Seja:

=contráriocaso

káreanautilizadaésoprogramaçãaseyks ,0

,1

Seja λmin o valor que define o tamanho mínimo de um lote. As restrições

adicionais são então definidas:

5*4 ≥ 5I�JK*4

5*4 ≤ ;*K*4

O modelo (3.16)-(3.19), acrescido das restrições de lote-mínimo é, portanto:

,-./�0 = max � � � @� � � ��*��C��*4 5*4

��E�

��∈��∈/74∈67

8

*� (3.20)

s.a. � � � ��*��C�,��E��,*4 5*4

��E�

��4∈67

8

*�≥ :�� , � ∈ $�, " ∈ +* (3.21)

24

� 5*44∈67

≤ ;< , = = 1. . > (3.22)

5*4 ≥ 5I�JK*4, ( ∈ )*, = = 1. . > (3.23)

5*4 ≤ ;*K*4 , ( ∈ )*, = = 1. . > (3.24)

K*4 ∈ �0,1!, 5*4 ≥ 0, ( ∈ )*, = = 1. . > (3.25)

Além de garantir o tamanho mínimo desejado para um lote, as variáveis binárias

permitem trabalhar de forma mais eficaz com o total de lotes usados, como minimizar

este total. Porém, o modelo final torna-se bem mais complexo ao incluirmos tais

restrições e variáveis para lidar com a ocorrência de lotes muito pequenos, pois as

variáveis binárias tornam o problema em inteiro-misto. Métodos híbridos e heurísticas

para resolver este problema adaptado são o foco principal deste projeto.

Conforme descrito na seção anterior, o modelo matemático (3.20)-(3.25) será o

modelo-chave deste estudo. Devido ao enorme número de rotações factíveis para uma

dada área (ou seja, a cardinalidade de Sk é muito grande), e apenas uma parte delas deve

compor uma solução ótima, um método de geração de colunas mostra-se atrativo. É

preciso, entretanto, definir uma ligação entre o modelo (3.20)-(3.25) e as restrições

(3.7)-(3.11), que definem uma rotação factível.

Considerando o modelo linear de atendimento demanda PRC-D representado por

(3.16)-(3.19) (isto é, sem restrições referentes ao tamanho do lote) como o problema

mestre, denotamos as variáveis duais (π,α) relativas às restrições (3.17) e (3.18),

respectivamente. Para o subproblema, o custo relativo é definido como uma função

objetivo a se maximizar, sujeita às restrições (3.7)-(3.11), que caracterizam uma rotação

factível.

O custo relativo de uma variável é dado pelo seu custo na função objetivo

decrementado do produto de seus coeficientes pelas variáveis duais de cada restrição.

Pelo modelo (3.16)-(3.19), temos que o custo de uma variável 5*4 na função objetivo

(3.16) é dado por ∑ @� ∑ ∑ ��*��C��*4��E��∈��∈/7 . Pelas restrições (3.17) temos os

coeficientes ��*��C�,��E��,*4 . Para as restrições (3.18), o coeficiente é 1. Sendo xijk as

variáveis de decisão do subproblema referente à área k, definido pelas restrições (3.7)-

(3.11), temos que a função objetivo do subproblema, que é encontrar o maior custo

relativo para a área k, é escrita como:

25

3̂* = max � � � (@� − M�,��)��*��*

��E�

��∈��∈/7

− N* (3.26)

A função objetivo (3.26), sujeita às restrições (3.7)-(3.11), retorna o maior lucro

relativo para as variáveis duais fornecidas, e a solução �C��* determina a respectiva

rotação. Com os dados da rotação, podemos calcular os coeficientes da nova variável λks

(ou seja, uma coluna do problema mestre), conforme estabelecido por (i) e (ii) na seção

anterior.

Os métodos de resolução propostos consideram o modelo (3.16)-(3.19) na

resolução inicial, e o subproblema é definido com a maximização de (3.26) restrito às

restrições de rotação (3.7)-(3.11), que gerará colunas ao problema mestre. O modelo

(3.20)-(3.25) é utilizado posteriormente. A seção seguinte detalha, além dos métodos de

resolução propostos, estas e outras considerações.

26

27

4 MÉTODOS HEURÍSTICOS DE RESOLUÇÃO

Esta seção descreve as duas heurísticas de resolução propostas para o problema

de atendimento de demanda com restrição de lote mínimo. Estes métodos foram

desenvolvidos como alternativas ao branch-and-price. Embora o método branch-and-

price pareça ser atrativo para resolver este problema de forma ótima, ele traz consigo

dificuldades intrínsecas: a primeira dificuldade diz respeito à resolução da relaxação

linear do problema mestre, uma vez que as restrições (3.23)-(3.24) não estão disponíveis

de antemão e, portanto, a construção dos custos relativos (que dependem das variáveis

duais associadas a estas restrições) não podem ser calculados explicitamente. Uma outra

dificuldade é associada à ramificação: como repassar a informação ao subproblema?

Uma estratégia típica seria obter uma formulação compacta, em que o modelo (3.20)-

(3.25) seria uma reformulação. Esta tarefa não é trivial e não traz necessariamente

garantia de êxito na aplicação do método branch-and-price. Para contornar estas

dificuldades, métodos heurísticos são apresentados.

De forma geral, ambos os métodos propostos partem da resolução linear do

modelo sem a utilização das restrições de lotes mínimos, portanto uma relaxação do

problema. A partir desta solução, diferentes estratégias para construção de soluções

factíveis, respeitando as restrições de lote mínimo, são propostas.

4.1 HEURÍSTICA GC-BC

A primeira heurística proposta é denominada GC-BC: Geração de Colunas –

Branch and Cut.

Utilizamos a solução do modelo linear (3.16)-(3.19), o qual é resolvido por

geração de colunas, para adicionar as variáveis binárias e restrições para cada coluna

gerada, obtendo o modelo (3.20)-(3.25) restrito (ou seja, com apenas um conjunto de

todas as colunas), que é resolvido de forma exata por um branch-and-cut. A heurística

GC-BC possui, portanto, duas fases bem definidas: a geração de colunas usando o

modelo (3.16)-(3.19), e a resolução do modelo (3.20)-(3.25) restrito às colunas geradas

na primeira fase.

Para a geração de colunas do modelo (3.16)-(3.19), entretanto, é necessário que

um conjunto inicial de variáveis esteja definido. Uma opção é definir um conjunto

28

inicial de rotações factíveis para o problema. Porém, por simplicidade e praticidade,

optou-se pelo uso de variáveis artificiais para as restrições (3.17), as quais funcionam

como indicadores de demanda não atendida, possuindo um custo elevado e negativo na

função objetivo: desta forma, na otimalidade seus valores tendem a zero, caracterizando

o atendimento da demanda. Se valores não-nulos para as variáveis artificiais ocorrem na

solução ótima, então a demanda original não é possível ser atendida com os dados

disponíveis. Esta situação, embora indesejável, pode ser real e aceitável na prática, isto

é, um plano de plantios e colheitas que não atende toda a demanda.

O algoritmo que define a heurística é descrito como:

Algoritmo: Heurística GC-BC para o problema PRC-D

Fase I

1. Inicie o problema mestre restrito (3.16)-(3.19) (PMR) com variáveis artificiais

associadas às restrições (3.17), com custo elevado e negativo.

2. Solucione o PMR e obtenha as variáveis duais ( ),π α referentes às restrições

(3.17) e (3.18), respectivamente.

3. Para cada área k = 1.. L, resolva um subproblema Pk restrito por (3.7)-(3.11) de

modo a maximizar (3.26), e obtenha os lucros relativos 3̂* e as colunas aks

correspondente, se 3̂* > 0.

4. Se 3̂* ≤ 0, para todo k = 1.. L, finalize a Fase I e vá para o passo 5 (Fase II).

Caso contrário, insira no PMR as colunas aks para os respectivos custos relativos

3̂* > 0, e retorne ao passo 2.

Fase II

5. Para cada coluna adicionada na Fase I, inclua no PMR o par de restrições

(3.23)-(3.24) correspondente, As variáveis artificiais são mantidas para garantir

a factibilidade do novo modelo.

6. Resolva o PMR (3.20)-(3.25) obtido no Passo 5 via branch-and-cut.

As variáveis artificiais são mantidas mesmo durante a Fase II, permitindo que o

não-atendimento da demanda ocorra, já que as novas restrições de tamanhos mínimos

aos lotes podem acarretar infactibilidade do problema. Porém, devido ao alto custo

29

associado às variáveis, a demanda deixará de ser atendida apenas na impossibilidade de

cumpri-la com a área máxima permitida com as colunas geradas na Fase I.

A partir do algoritmo e modelo apresentados, diferentes parâmetros foram

alterados e analisados: apresentamos a seguir um sumário deles, e descrevemos na seção

5.1 os resultados dos testes realizados a partir deste modelo.

Uma variação da função objetivo permite que a Fase II busque o atendimento da

demanda visando reduzir o número de lotes necessários:

12� � � � @� � � ��*��C��*4 5*4

��E�

��∈��∈/74∈67

8

*�− , � � K*4

4∈67

8

*� (4.1)

Incluímos as variáveis binárias yks na função objetivo com um custo

representado pelo coeficiente z, que refere-se à penalidade ou custo financeiro associado

à utilização/criação de um lote. Poder-se-ia utilizar penalidades diferentes para cada

área de cultivo ou mesmo diferentes rotações, porém optou-se por manter o custo

constante entre elas, sem perda de generalidade. A somatória é incluída com o sinal

negativo, denominando a perda referente. A rigor, temos dois objetivos que compõem

(4.1): maximizar o retorno (f(λ)), na primeira parte, e minimizar o número de lotes que a

área é dividida (g(y)), segunda parte. Podemos escrever como:

)(min

)(max

yg

f λ (4.2)

Se considerarmos apenas f(λ) temos o problema (3.20)-(3.25) descrito pelo

algoritmo acima. Ao considerarmos apenas g(y), temos o problema de atendimento de

demanda com minimização de lotes. Um balanço entre as duas funções pode ser feito e

remete a um dos conjuntos de testes computacionais realizados e descritos na seção

5.1.2 (Gomes e Arenales, 2010). Uma curva de eficiência (curva de Paretto) pode ser

gerada, de modo que não se tem uma solução ótima mas um conjunto de soluções

eficientes para auxiliar o tomador de decisões, que saberá o quanto deve abrir mão do

retorno para diminuir o número de lotes.

Os testes são apresentados na seção subseqüente 5.1.3 foram realizados para

comprovar a melhoria obtida pela reescrita do segundo conjunto de restrições definida

em (3.6), como mencionado na seção 3.1.

30

(Definimos os valores loteg e lotef como sendo a somatória das variáveis yks das

soluções obtidas ao se minimizar g(y) e ao se maximizar f(λ), respectivamente. Ou seja,

estes valores representam o total de lotes utilizados em cada objetivo. Pode-se definir

então uma curva de Paretto ao fixar o número de lotes usados em diferentes valores do

intervalo [loteg, lotef] ao se maximizar f(λ). Diferente dos testes descritos na seção 5.1.2,

que considera um balanço entre o lucro e penalidades associadas ao uso de cada lote, a

seção 5.1.4 descreve a geração de uma curva de Paretto com os valores de f(λ) obtidos

ao variar o valor máximo de lotes usados dentro do intervalo descrito acima.

Visando alternativas para melhorar o desempenho computacional do algoritmo,

por tratar-se de geração de colunas, foi avaliado o uso de um valor cmin > 0, para a

verificação da condição de parada da Fase I do algoritmo. O propósito de um valor

maior que 0 seria evitar que o algoritmo ficasse, por muitas iterações, gerando colunas

com custos relativos muito baixos, aumentando o tempo computacional necessário para

uma melhora não significativa no retorno obtido. Os testes computacionais referentes ao

uso de custos alternativos são discutidos na seção 5.1.5.

Uma análise de situações de simetria no problema, ocorrência que surgiu durante

testes preliminares e estudada em mais detalhes, é feita na seção 5.1.6.

Na seção 5.1.7, avaliamos como a dificuldade de resolução do algoritmo varia

conforme mudamos o valor de λmin utilizado, visto que o tamanho mínimo definido a um

lote pode variar de acordo com a necessidade ou disponibilidade dos agricultores.

Observe que a Fase II do algoritmo é, por si só, resolvida de forma exata, porém

não é a solução exata do problema (3.20)-(3.25) como um todo, já que apenas um

pequeno conjunto de todas as colunas possíveis são consideradas. Por isso, o

procedimento GC-BC é considerado heurístico.

4.2 HEURÍSTICA LOTE FIXO

A segunda heurística proposta utiliza apenas o modelo linear (3.16)-(3.19) e, por

meio de avaliações das coordenadas na solução, fixa o valor de algumas variáveis no

tamanho mínimo desejado para um lote. Após a fixação, o modelo tem a demanda

atualizada, considerando o atendimento cumprido pelas variáveis fixadas, como também

a área disponível é atualizada, e um problema residual, análogo ao inicial, é resolvido. O

processo é repetido até que algum critério de parada seja satisfeito.

31

Devido à atualização do modelo em cada iteração, mais colunas tendem a ser

geradas na nova resolução, abrindo mais possibilidades de solução.

Para caracterizar o algoritmo, faremos uso de dois grupos V e F: o grupo V

contém as variáveis candidatas a serem fixadas em uma iteração, e o grupo F contém as

variáveis que já foram fixadas pelo algoritmo. Sabendo disso, o algoritmo que descreve

a heurística Lote Fixo é definida como:

Algoritmo: Heurística Lote Fixo para o problema PRC-D

1. Resolva (3.16)-(3.19) por geração de colunas. Faça P = ∅ e � = ∅.

2. Faça t = 0.

3. Se 5*4 ≥ 5I�J, ∀5*4 > 0, PARE: a solução é ótima para o problema (3.20)-

(3.25) se t = 0, heurística se t > 0.

4. Caso contrário, seja P = �(=, () | 5*4 < 5I�J U (=, () ∉ �! o conjunto das

variáveis cujo valor viola a restrição de lote mínimo. Avalie as condições de

parada.

5. Determine (=, () ∈ P segundo um critério de seleção pré-definido.

6. Para todo (=, () selecionado, faça 5*4 = 5I�J e atualize as informações

referentes (faça � ← � ∪ �(=, ()! e atualize o total de fixações de (=, ()).

7. Atualize as demandas :�� = :�� − 2��*4 5*4, para todo i e j, conforme as

variáveis 5*4 selecionadas no passo 6.

a. Se :�� < 0, faça :�� = 0.

8. Atualize a área restante disponível ;* = ;* − 5I�J, para cada 5*4 selecionado.

9. Resolva (3.16)-(3.19) (agora com dij e Ak atualizados) por geração de colunas.

10. Faça t = t + 1, e retorne para 3.

As condições de parada podem diversificar, e por questões de simplicidade de

leitura, não foram incluídas no algoritmo acima. O algoritmo implementado utilizou as

seguintes condições de parada:

32

Condições de parada para a Heurística Lote Fixo para o problema PRC-D

1. Se, ∀= = 1, … , >, a área total disponível Ak < n*λmin, PARE. (utilizou-se n =

1,5).

2. Se, para todo k’ = 1,...,L, ∑ 5*4*4∈Z | *�*[ < 5I�J , PARE.

3. Calcule as perdas associadas: seja λ’ a solução obtida ao se considerar 5*4 = 0

para todo (=, () ∈ P:

a. Calcule: f(λ’) = f(λ) - ∑ 3*45*4*4∈Z

b. Calcule demanda não atendida:

dij ’ = ∑ ∑ 2��*4 5*44∈678*� − ∑ 2��*4 5*4*4∈Z

c. Se dij ’ ≥ dij , faça dij ’ = 0 (a demanda é atendida); caso contrário, faça dij ’

= dij - dij ’.

d. Se f(λ’) ≤ tol_f e dij ’ ≤ tol_d para todo i,j, PARE.

A primeira condição de parada proposta assume que, se a área restante de todas

as hortas tratadas em uma dada iteração é menor ou igual a um certo múltiplo do

tamanho mínimo de lote definido, não há área restante suficiente que compense um

replanejamento. Esta verificação é mais bem aplicada no passo 8 do algoritmo, antes da

resolução do modelo.

Uma idéia similar é utilizada na segunda condição, que considera que se todos

os lotes pequenos forem somados e ainda não formarem uma área maior ou igual a um

lote mínimo, são de pouca contribuição para a solução e poderiam ser desprezados sem

perdas significativas.

A terceira condição, por sua vez, avalia se a perda (na função objetivo e não-

atendimento de demanda) associada à desconsideração dos lotes pequenos é menor que

uma tolerância pré-determinada. Esta perda pode ser avaliada em valores brutos

(conforme descrito nas condições acima) ou proporcionalmente aos valores originais. A

perda proporcional foi escolhida para ser verificada no algoritmo implementado.

A consideração feita por se anular valores menores que um valor estipulado

(neste caso, λmin), é inspirada pela heurística α-lote apresentada em Santos (2009): neste

trabalho, a autora desconsiderou lotes menores que um dado valor α. Calculou-se a

perda percentual desta consideração, e avaliações foram feitas sobre sua eficácia. A

autora usou α = 1 para seus testes, um valor que julgamos ser muito baixo perante os

33

resultados obtidos: assumimos então uma abordagem mais ousada, adaptando um dos

critérios de parada para uma análise similar à α-heurística com α = λmin.

Para o passo 5, o critério de seleção de variáveis a ser fixada também é sujeito a

mudanças. Este critério é crucial e suas variações serão o foco do desenvolvimento da

heurística. O primeiro critério escolhido para a fixação das variáveis foi:

Critério 1 de seleção de variável a ser fixada para a Heurística Lote Fixo

1. Seja P = �(=, () | 5*4 < 5I�J U (=, () ∉ �!. 2. Determine (k,s)∈ P tal que 5̅*4 = �2� �5*4 | (=, () ∈ P!.

Outros padrões de escolha de variáveis a serem fixadas em cada iteração são

propostos. Mais detalhes são fornecidos juntamente dos testes computacionais

correspondentes, descritos nas seções 5.2.2, 5.2.3 e 5.2.4. Uma mistura dos conceitos

das Heurísticas Lote Fixo com GC-BC é apresentada, discutida e testada para cada

diferente critério de escolha em sua respectiva seção. Por fim, a seção 5.2.5 compara o

desempenho computacional entre os critérios.

34

35

5 TESTES COMPUTACIONAIS

Todos os testes computacionais foram realizados em uma máquina Pentium

Dual CPU com 2.16/2.17 GHz e 2.0 GB de memória RAM, sob o sistema operacional

Windows Vista. Os modelos são iniciados com variáveis artificiais, as quais são

mantidas no modelo como representantes de demanda não-atendida.

Os dados de culturas utilizados foram os mesmos de Santos (2009), obtidos em

uma horta da cidade de Barbacena – MG, que consistem de 23 culturas divididas em 9

famílias botânicas. O Apêndice A contém todos os detalhes referentes às 23 culturas

utilizadas. Em alguns testes, grupos menores de culturas foram usados, como 12

culturas divididas em 6 famílias botânicas, 16 culturas em 7 famílias, e 20 culturas em 8

famílias. Nos grupos menores, pequenas alterações nos períodos favoráveis de plantio

das adubações verdes foram feitas para garantir que não ocorresse falta de atendimento

de demanda em razão à impossibilidade de plantio, já que as adubações verdes são

obrigatórias nas rotações: estas alterações são meras extensões dos períodos factíveis de

plantio e foram feitas unicamente devido à redução da amostra, pois uma situação

prática não seria tão limitada, e com isso garantindo a factibilidade das instâncias.

A menos que explicitado o contrário, todos os testes utilizam a re-escrita (3.6) de

restrições e assumem lote mínimo λmin = 100, além da disponibilidade de 20.000 m² de

área total para cultivo dividida em k = 1, k = 3 e k = 5 hortas distintas. Nos casos de

múltiplas hortas, a produtividade das hortaliças foi variada entre elas, além da inclusão

de algumas proibições de plantio e totais de área para cada horta variando em um

intervalo ;* ∈ [3000, 7500], porém a somatória de todas as áreas mantém o total

estipulado de 20.000 m².

O tempo de execução foi limitado em 3600 segundos (1 hora) para todo o

processo de geração de colunas, e também em 3600 segundos para a resolução do

problema inteiro-misto.

Os códigos foram implementados na linguagem C++ utilizando o software

Microsoft Visual C++ 2008 Express Edition, e o solver IBM CPLEX 12.1 foi usado

como ferramenta de solução dos modelos matemáticos.

36

37

5.1 TESTES HEURÍSTICA GC-BC

Os testes referentes à Heurística GC-BC são apresentados a seguir. Inicialmente,

avaliamos os testes preliminares, baseados no algoritmo descrito na seção 4.1 e, a seguir

tratamos algumas análises de parâmetros como discutidos anteriormente.

Os testes usualmente consistem de 12 classes de problemas (referente às

combinações do número de culturas e hortas consideradas), para as quais foram

utilizados os dados de 5 diferentes cenários de demanda). As áreas disponíveis para

plantio são variadas, assim como a produtividade de cada cultura, além de algumas

proibições relativas a cada área de plantio, como mencionado anteriormente. A menos

que expresso o contrário, o valor de lote mínimo utilizado foi λmin = 100, e a área

máxima disponível, considerando todas as regiões de cultivo, é sempre igual a

20.000m².

5.1.1 TESTES PRELIMINARES

O primeiro conjunto de testes realizados consiste em resolver o modelo (3.16)-

(3.19) (caracterizado pela maximização do retorno financeiro sem restrições de tamanho

de lote), obtendo um valor para a função objetivo e o número de lotes usados (Fase I do

algoritmo). Após adaptar o modelo para (3.20)-(3.25) (caracterizado pela maximização

do lucro com restrições de lote mínimo), o modelo inteiro-misto é resolvido e um novo

valor de função objetivo e total de lotes usados é obtido (Fase II do algoritmo, usando

f(λ) como objetivo, isto é, maximizando o lucro). Por fim, as instâncias foram rodadas

novamente, com a Fase II adaptada para que a função objetivo seja composta apenas de

g(y), isto é, minimizando o número de lotes. Desta forma, comparamos o valor do lucro

obtido (ou seja, f(λ)) e o total de lotes usados nas três situações: sem restrição de lote

mínimo, com restrição de lote mínimo, e com restrição de lote mínimo visando

minimizar o total de lotes usados.

As tabelas abaixo apresentam os resultados obtidos para cinco cenários de

demanda, cada cenário aplicado a 12 classes de problema relativas ao número de

culturas e hortas. A colunas f1(λ) e y1 apresentam respectivamente o valor de função

objetivo e número de lotes obtidos na Fase I do algoritmo. Para melhor visualização e

compreensão, as colunas seguintes são exibidas em valores percentuais em relação às

38

anteriores: as colunas f2(λ) e y2 fornecem a redução dos resultados obtidos pela Fase II

do algoritmo em relação à Fase I, e de forma análoga as colunas fmin(λ) e ymin referem-se

aos valores obtidos na Fase II ao minimizarmos g(y).

Tabela 5.1: resultados dos testes preliminares para o cenário de demanda 1

hortas cult. f1(λ) f2(λ) fmin(λ) y1 y2 ymin

1

12 2676582,78 -0,97% -90,80% 39 -10,26% -51,28%

16 2575102,28 -1,35% -75,17% 53 -18,87% -52,83%

20 2016602,28 -1,51% -78,15% 76 -10,53% -56,58%

23 1366246,73 -3,96% -65,63% 83 -20,48% -50,60%

3

12 2302470,56 -0,91% -90,48% 43 -23,26% -55,81%

16 2389692,38 -1,07% -81,23% 53 -16,98% -52,83%

20 2155522,00 -1,18% -80,39% 80 -22,50% -58,75%

23 1271723,57 -4,43% -69,82% 104 -14,42% -61,54%

5

12 2986404,85 -0,17% -93,71% 41 -17,07% -53,66%

16 2978234,81 -1,46% -89,92% 59 -20,34% -57,63%

20 2692998,10 -1,43% -71,77% 80 -12,50% -60,00%

23 2100988,03 -2,21% -79,61% 94 -10,64% -60,64%



1

12 3620969,21 -3,90% -96,27% 56 -44,64% -53,57%

16 3806712,14 -4,18% -10,55% 65 -43,08% -53,85%

20 3258701,03 -5,64% -84,49% 77 -40,26% -54,55%

23 3031934,37 -5,92% -81,18% 86 -33,72% -54,65%

3

12 2928602,19 -2,90% -83,91% 53 -41,51% -50,94%

16 3034318,92 -3,67% -87,38% 68 -36,76% -54,41%

20 2800574,81 -3,13% -60,58% 78 -33,33% -55,13%

23 2502294,27 -3,36% -80,14% 100 -35,00% -60,00%

5

12 3167395,36 -0,93% -69,28% 59 -44,07% -57,63%

16 3717112,01 -5,65% -88,15% 80 -45,00% -60,00%

20 3465639,85 -5,49% -93,76% 90 -42,22% -63,33%

23 3207488,54 -5,75% -91,40% 110 -43,64% -65,45%

39



1

12 3753049,21 -4,11% -7,22% 55 -47,27% -54,55%

16 3943085,22 -4,72% -83,78% 73 -47,95% -57,53%

20 3781761,33 -5,66% -84,83% 86 -41,86% -59,30%

23 3562613,13 -6,81% -90,88% 97 -46,39% -58,76%

3

12 2996466,15 -3,09% -53,55% 56 -44,64% -55,36%

16 3120223,20 -3,81% -86,25% 71 -47,89% -54,93%

20 2924227,10 -3,18% -83,45% 85 -43,53% -58,82%

23 2690223,49 -3,77% -82,24% 120 -47,50% -65,00%

5

12 3162745,25 -0,61% -90,79% 66 -50,00% -60,61%

16 3781033,31 -5,94% -82,65% 93 -53,76% -64,52%

20 3802939,82 -6,23% -89,41% 99 -48,48% -64,65%

23 3504055,11 -5,57% -53,77% 121 -46,28% -64,46%



1

12 3515827,43 -7,02% -92,59% 90 -56,67% -56,67%

16 3691871,00 -7,54% -78,41% 101 -51,49% -58,42%

20 3512078,85 -8,35% -64,56% 113 -48,67% -56,64%

23 3360192,06 -9,93% -85,82% 148 -53,38% -62,84%

3

12 2971776,10 -4,17% -82,21% 96 -57,29% -60,42%

16 2792967,07 -8,04% -88,63% 107 -54,21% -60,75%

20 2767989,41 -4,18% -83,20% 122 -49,18% -57,38%

23 2550466,96 -8,73% -79,48% 174 -50,57% -67,82%

5

12 3141466,78 -1,79% -62,94% 90 -50,00% -58,89%

16 3717125,05 -9,98% -79,84% 111 -52,25% -59,46%

20 3752085,15 -9,61% -89,06% 127 -53,54% -62,20%

23 3422370,78 -8,41% -82,24% 163 -49,69% -65,64%

40



1

12 3620818,17 -5,63% -93,89% 51 -41,18% -43,14%

16 3828331,51 -5,37% -65,16% 54 -40,74% -42,59%

20 3735951,29 -5,67% -64,46% 73 -45,21% -54,79%

23 3619333,91 -6,03% -82,84% 79 -46,84% -54,43%

3

12 2978193,64 -3,26% -35,53% 54 -40,74% -46,30%

16 2951827,95 -4,27% -75,75% 58 -41,38% -48,28%

20 2903786,52 -4,42% -54,20% 75 -36,00% -53,33%

23 2690167,63 -2,69% -85,09% 91 -47,25% -60,44%

5

12 3171795,08 -1,37% -91,69% 51 -31,37% -45,10%

16 3772279,13 -6,65% -66,61% 75 -49,33% -60,00%

20 3879189,84 -5,90% -86,94% 84 -50,00% -61,90%

23 3544769,74 -2,80% -86,38% 85 -48,24% -60,00%

Observamos nas tabelas que para os 5 cenários o número de lotes usados na

solução fornecida pela Fase II é significativamente menor que a solução linear da Fase

I. Apenas esta redução é capaz de simplificar consideravelmente a administração física

dos lotes: em alguns casos obtemos mais de 50% de redução, uma ocorrência freqüente

no cenário 4. Há, entretanto, reduções menores e de pouco impacto, como notamos nos

testes referentes ao cenário de demanda 1.

Ao focarmos os esforços em minimizar os lotes, o valor obtido nem sempre se

mostrou muito menor que o número de lotes gerado pela Fase II convencional, mas há

ocorrências de reduções grandes, algo que podemos observar mais facilmente nos

resultados do cenário 1. Por sua vez, este é o cenário que obteve a menor redução de

lotes usados ao maximizar o lucro, indicando que a redução do número de lotes impacta

bastante o lucro.

É possível que parte desta alta redução no lucro se deva ao fato de que o modelo

é resolvido em função das variáveis yks, e como as respectivas variáveis λks satisfazem a

demanda final, não há utilização da área restante para produção extra e, com isso,

aumento do lucro. Porém, veremos adiante nos testes da seção 5.1.4 que estes baixos

valores não estão distantes da realidade da solução ótima referente ao problema com o

mínimo de lotes necessários para garantir o cumprimento da demanda.

Observamos agora o tempo computacional necessário para a resolução dos

problemas, agrupados por fase: Fase I (geração de colunas), Fase II (branch-and-cut

41

com as restrições de lote mínimo) e Minimização de lotes (Fase II com função objetivo

de minimizar lotes usados).

Figura 5.1: Tempo computacional da geração de colunas para 5 cenários de demanda

Observamos na Figura 5.1 que o tempo necessário para a geração de colunas

(referente à Fase I do algoritmo) cresce de forma significativa conforme cresce o

número de culturas do problema. O número de áreas utilizadas tem pouco impacto no

tempo de resolução; embora a tendência seja haver um pequeno aumento, notamos que

isso nem sempre ocorre: vemos no cenário 4 que o problema com 1 área e 23 culturas

requereu mais tempo que os problemas com 3 e 5 áreas para o mesmo número de

culturas.

O aumento do tempo computacional observado nos problemas com mais

culturas é natural, uma vez que o número de culturas define em grande parte o número

de restrições do modelo: as restrições de demanda (3.17) são da ordem de O(M.N),

sendo M o número de períodos e N o número de culturas. Cada área a mais, por sua vez,

acrescenta uma única restrição ao conjunto de restrições (3.18), que é da ordem de

O(L), sendo L o número de áreas consideradas.

0,00

50,00

100,00

150,00

200,00

250,00

300,00

350,00

400,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)

Parâmetros (nº fazendas x nº culturas)

Tempo resolução Geração de Colunas

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

42

Figura 5.2: Tempo computacional do branch-and-cut para 5 cenários de demanda

Para a Fase II do algoritmo, que consiste da solução do problema inteiro-misto

com restrições de lote mínimo via branch-and-cut, o tempo computacional foi bem

abaixo do esperado, como observado na Figura 5.2: poucas instâncias passaram da

marca de 2 minutos em sua resolução. O pacote de otimização mostrou-se eficiente em

resolver um problema inteiro-misto que possui apenas variáveis binárias e que não

possuem simetria em sua semântica.

Figura 5.3: Tempo computacional da minimização de lotes para 5 cenários de demanda

0,00

20,00

40,00

60,00

80,00

100,00

120,00

140,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)


Tempo de resolução Branch-and-Cut

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

0,00

20,00

40,00

60,00

80,00

100,00

120,00

140,00

160,00

180,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)


Tempo resolução Minimização de Lotes

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

43

Se a Fase II é alterada de forma que o objetivo é obter a solução com o menor

número de lotes possível, o tempo computacional necessário também se mostrou baixo:

a Figura 5.3 mostra que a grande maioria dos problemas foi resolvida em menos de 20

segundos. Mesmo em instâncias mais demoradas, não mais que 3 minutos foram

necessários para a comprovação da otimalidade do problema.

Uma única exceção foi observada e não incluída no gráfico acima: o problema

com 3 hortas e 23 culturas, para o cenário de demanda 1, não foi capaz de provar a

otimalidade dentro do tempo limite de 3600 segundos. Devido a este alto valor, a

solução não foi inclusa no gráfico para evitar que o gráfico ficasse desconfigurado, com

todos os valores concentrados e impossibilitando qualquer distinção entre eles.

Curiosamente tal dificuldade não ocorreu no problema de 5 áreas e 23 culturas, que

esperava-se ser computacionalmente mais difícil de resolver, o que sugere que a classe

de problemas com 3 áreas pode apresentar simetria em sua divisão.

Notamos nos três gráficos que o tempo computacional necessário para a solução

do problema proposto é baixo, independente do objetivo final (maximizar lucro ou

minimizar lotes). Não é possível comparar este tempo com os resultados de Santos,

visto que os problemas abordados são distintos. A perda de lucro comparando-se com o

resultado obtido na Fase I é baixa na média, enquanto o número total de lotes usados

decresce consideravelmente: a facilidade de administração deste número reduzido de

lotes deve ser capaz de compensar o investimento que é perdido considerando-se a

solução que desconsidera um tamanho mínimo para os lotes.

5.1.2 TESTES PONDERAÇÃO-α

As funções objetivos descritas na seção 4.2, que são maximizar o lucro obtido e

minimizar o total de lotes utilizados enquanto cumpre-se o atendimento de demanda,

são conflitantes. Minimizar o número de lotes necessários enquanto garante-se o

atendimento da demanda tende a reduzir drasticamente o lucro das rotações. Por outro

lado, o lucro máximo pode requerer uma vasta distribuição de lotes, o que torna a

administração inaceitável na prática. É fácil ver, portanto, que um balanço entre os

objetivos pode trazer resultados mais satisfatórios na prática.

44

Em Gomes e Arenales (2010), esta consideração foi tratada e avaliada.

Descreveremos aqui os pontos mais importantes e resultados obtidos de forma

resumida.

Uma das técnicas mais clássicas para obter soluções de problemas

multiobjetivos é fornecer pesos a cada um dos deles e uni-los em uma única função

mono-objetivo. Desta forma, objetivos conflitantes são trabalhados simultaneamente e o

problema pode ser abordado de diferentes maneiras conforme os pesos utilizados. Não

existe, então, uma solução ótima para o problema, apenas uma solução ótima para um

determinado conjunto de coeficientes de peso. Um conjunto de soluções pode ser obtido

utilizando diferentes coeficientes, os quais são variados conforme os interesses do

usuário. Porém, não é uma tarefa trivial determinar quais coeficientes são adequados

(Cohon, 1978).

Para balancear os dois objetivos desejados conforme descritos em (4.2), eles

foram unidos em uma função mono-objetivo, sendo que cada objetivo foi então

multiplicado por um fator. Podemos escrevê-los, sem perda de generalidade, da seguinte

forma:

)().1()(.max ygf αλα −− (5.1)

Utilizando valores para α, 0 ≤ α ≤ 1, dá-se menor ou maior peso a um ou outro

objetivo. É fácil observar que, para α = 1, temos apenas a maximização de f(λ),

enquanto para α = 0 nosso objetivo se resume a minimizar g(y). Qualquer valor

intermediário busca soluções de compromisso entre um objetivo e outro.

Vale ressaltar que o valor retornado por (5.1) considera os lucros e a penalidade

pelo número de lotes ao mesmo tempo, portanto uma análise individual de f(λ) e g(y)

deve ser considerada.

O método de resolução é a Heurística GC-BC, conforme descrito no algoritmo

presente na seção 4.1. A única diferença, entretanto, é que a função objetivo é definida

conforme (5.1), com a penalização z de g(y) fixada em 1000 e 3000.

Os testes realizados consistiram em utilizar valores de α = 0, 0.1,..., 1, testados

em 3 diferentes classes de problemas, para um mesmo cenário de demanda.

As tabelas abaixo apresentam os resultados obtidos na Fase II do algoritmo GC-

BC (e, portanto, satisfaz as condições de lote mínimo) para um cenário de demanda com

23 culturas em três instâncias: com 1, 3 e 5 áreas de cultivo diferentes. Cada coluna é

45

identificada pelo valor de α. As informações “%Redução_Lucro” e “%Redução_Lote”

comparam os valores da f(λ) e total de lotes usados na solução obtida (listados acima na

tabela) pela Fase II com a Fase I do algoritmo.

Tabela 5.6: resultados computacionais para a Fase II com k = 1 área

Valores de α 0.0 0.1 0.2 0.3 0.4 0.5 Lucro (f(λ)) 364140,00 774333,33 834416,67 850743,33 852743,33 852743,67 Nº de lotes 42 61 71 77 78 78 %Redução_lucro 59,25 13,35 6,63 4,80 4,58 4,58 %Redução_lote 56,25 36,46 26,04 19,79 18,75 18,75 Valores de α 0.6 0.7 0.8 0.9 1.0 Média Lucro (f(λ)) 853543,33 853543,33 853543,33 854260,00 854260,00 795298,48 Nº de lotes 79 79 79 83 83 72,09 %Redução_lucro 4,49 4,49 4,49 4,41 4,41 10,50 %Redução_lote 17,71 17,71 17,71 13,54 13,54 23,30

A Fase I do algoritmo forneceu f(λ) = 893636,59 com 96 lotes na primeira

instância, reduzindo para pelo menos 83 lotes quando maximizamos o lucro na Fase II.

Para valores de α de 0,3 a 0,8, o número de lotes usados pouco variou, como

observamos na Tabela 5.6. Para α = 0, vemos uma redução significativa no lucro obtido,

mostrando claramente como os objetivos são conflitantes. O tempo médio da geração de

colunas (Fase I) foi de 395 segundos, com a Fase II requerendo uma média de 76

segundos, com menção especial ao caso de α = 0, que necessitou de 394 segundos,

provavelmente devido às múltiplas soluções ótimas do problema quando o foco é

apenas a minimização dos lotes.

Tabela 5.7: resultados computacionais para a Fase II com k = 3 áreas

Valores de α 0.0 0.1 0.2 0.3 0.4 0.5

Lucro (f(λ)) 360045,56 786765,95 932660,83 1059655,83 1078824,17 1093736,67

Nº de lotes 39 45 53 66 69 73

%Redução_lucro 68,48 31,12 18,34 7,22 5,55 4,24

%Redução_lote 60,61 54,55 46,46 33,33 30,30 26,26

Valores de α 0.6 0.7 0.8 0.9 1.0 Média

Lucro (f(λ)) 1096228,33 1096228,33 1096228,33 1096228,33 1096634,52 981203,35

Nº de lotes 74 74 74 74 79 65,45

%Redução_lucro 4,02 4,02 4,02 4,02 3,99 14,09

%Redução_lote 25,25 25,25 25,25 25,25 20,20 33,88

46

Para 3 áreas de plantio diferentes, foi obtido f(λ) = 1142178,05 com o uso de 99

lotes na Fase I. A Tabela 5.7 mostra que o comportamento foi similar à primeira

instância quanto ao número de lotes: valores intermediários de α pouco variaram a

redução de lotes usados. Mesmo no extremo de maximização de lucro, os lotes

necessários foram reduzidos para pelo menos 79, representando quase 20% de redução.

Porém, a Fase II apresentou dificuldades, com tempo médio de execução de 2329

segundos e não-prova da otimalidade para valores baixos de α (0.1 a 0.5), ou seja o

algoritmo foi interrompido por limite de tempo.

Tabela 5.8: resultados computacionais para a Fase II com cinco áreas

Valores de α 0.0 0.1 0.2 0.3 0.4 0.5

Lucro (f(λ)) 447661,19 1491990,67 1548892,50 1680122,44 1684605,56 1710453,64

Nº de lotes 39 47 50 64 65 72

%Redução_lucro 74,98 16,60 13,42 6,08 5,83 4,39

%Redução_lote 61,00 53,00 50,00 36,00 35,00 28,00

Valores de α 0.6 0.7 0.8 0.9 1.0 Média

Lucro (f(λ)) 1717604,92 1719167,44 1719967,44 1722121,33 1722301,33 1560444,41

Nº de lotes 75 76 77 81 83 66,27

%Redução_lucro 3,99 3,90 3,85 3,73 3,72 12,77

%Redução_lote 25,00 24,00 23,00 19,00 17,00 33,73

A terceira instância forneceu com 100 lotes na Fase I um valor de f(λ) =

1788897,15. A Fase II não conseguiu provar a otimalidade na maioria dos valores de α,

embora o valor do gap fosse usualmente menor que 1%. Na Tabela 5.8 vemos que o

número de lotes reduzidos, por sua vez, não se mostrou constante para valores

intermediários de α como nas outras instâncias, e sim um comportamento de mudança

mais contínua.

Em todos os casos, é fácil observar como a redução de lotes é significativa

quando ela é o único objetivo considerado, e como esta redução traz um impacto grande

no lucro obtido. Estes resultados indicam que uma aproximação de uma curva de

Paretto (curva de eficiência) com os diferentes valores de lotes pode ser uma ferramenta

de grande auxílio na tomada de decisão. Testes dedicados à geração desta curva foram

realizados e são descritos na seção 5.1.4.

Os tempos computacionais altos na resolução do problema nas instâncias com 3

e 5 áreas indicam simetria no problema. Testes foram realizados para avaliar o impacto

que a simetria do problema pode trazer ao modelo e são apresentados na seção 5.1.6.

47

5.1.3 TESTES CONJUNTO DE RESTRIÇÕES (3.6)

Conforme discutido na seção 3.1, as restrições que descrevem o subproblema

que determina uma rotação factível poderiam ser simplificadas sem perda de

generalidade, substituindo o conjunto de restrições (3.2) por (3.6). Esta substituição

torna a matriz de coeficientes mais esparsa, potencialmente facilitando sua resolução

por pacotes de otimização que exploram esta característica. Nesta seção descreveremos

os testes computacionais realizados que verificam o desempenho obtido com esta

mudança:

Os testes realizados consistiram em executar o algoritmo GC-BC utilizando o

conjunto de restrições (3.1)-(3.5), e na sequência analisar as mesmas instâncias

utilizando o conjunto de restrições (3.7)-(3.11). Foram resolvidas 60 instâncias,

seguindo o mesmo padrão de 5 cenários de demanda para 12 classes de problema dos

testes anteriores.

Os gráficos abaixo mostram o tempo computacional necessário para a resolução

da Fase I do algoritmo, que consiste na geração de colunas. As linhas contínuas

representam o tempo necessário utilizando-se as restrições (3.1)-(3.5), enquanto as

linhas com marcadores indicam o tempo computacional referente à resolução pelas

restrições (3.7)-(3.11). Para melhor visualização dividimos os gráficos de forma que

cada um apresenta os resultados referentes a um cenário de demanda. Cada ponto do

eixo horizontal representa uma classe de problema, definidas pela combinação do

número de hortas e culturas utilizadas, mantendo o padrão já utilizado em gráficos

anteriores.

Figura 5.4: Comparativo de tempo para a geração de colunas para cenário de demanda 1

0

50

100

150

200

250

300

350

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o g

era

ção

de

co

lun

as

(s)

Parâmetros (nº hortas x nº culturas)

Comparativo de restrições - cenário 1

Restrição antiga 1

Restrição nova 1

48




0

50

100

150

200

250

300

350

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o g

era

ção

de

co

lun

as

(s)




Restrição nova 2

0

50

100

150

200

250

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o g

era

ção

de

co

lun

as

(s)



Restricao antiga 3

Restrição nova 3

0

100

200

300

400

500

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o g

era

ção

de

co

lun

as

(s)




Restrição nova 4

49


Observamos que, de forma geral, a redução no tempo é presente e, embora não

tão significativo, pode chegar a representar até 60% de redução em uma das instâncias.

As variações tendem a ser mais notáveis nas instâncias com mais culturas e que, por sua

vez, requereram um tempo computacional total maior: em instâncias com baixo tempo

de execução, a redução não aparenta ser tão significativa.

Houve, entretanto, ocorrências em que o segundo conjunto de restrições

requereu mais tempo que o primeiro. Essas ocorrências não representam a maioria e, em

geral, o tempo extra utilizado não foi de grande impacto. O quarto cenário de demanda,

por sua vez, obteve ganhos e perdas de formas equilibradas (nenhum conjunto de

restrição prevaleceu sobre o outro).

Vale ressaltar que em todas as instâncias o valor obtido para a função objetivo

na Fase I não se alterava perante a mudança do modelo utilizado, o que comprova que

ambos de fato representam o mesmo problema e, portanto, possuem a mesma solução

ótima para o problema linear.

Vemos que, em geral, o conjunto de restrições (3.6) substituindo as restrições

(3.2) manteve a generalidade do problema e permitiu uma resolução mais rápida do

modelo, comprovando que a matriz de coeficientes mais esparsa pôde ser mais bem

trabalhada pelo pacote de otimização, mantendo a garantia de otimalidade da geração de

colunas. Embora o ganho seja relativamente pequeno nos testes realizados, para

instâncias ainda maiores e difíceis, ou métodos que exijam ainda mais iterações, esse

ganho pode atingir proporções de grande valia.

Perante o resultado satisfatório obtido, o conjunto de restrições (3.7)-(3.11) foi

adotado para todos os testes realizados neste trabalho.

0

50

100

150

200

250

300

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o g

era

ção

de

co

lun

as

(s)




Restrição nova 5

50

5.1.4 TESTES CURVA DE EFICIÊNCIA

Os resultados descritos na seção 5.1.2 permitem observar o conflito dos

objetivos: para obter mais lucro, é necessária a criação de mais lotes, o que por sua vez

torna a administração muito mais complexa. Conforme diferentes pesos eram atribuídos

a cada objetivo, o número de lotes variava gradativamente. Mostra-se interessante,

como instrumento de apoio à tomada de decisão, a curva de Paretto, a que relaciona o

lucro e o número de lotes.

Os testes computacionais realizados para definir uma aproximação da curva de

Paretto consistiram em inicialmente resolver uma instância utilizando-se, na Fase II do

algoritmo GC-BC, apenas um dos dois objetivos: denotamos ]?AU^ o número de lotes

obtidos com a maximização de f(λ), e ]?AU_ o número de lotes obtidos com a

minimização de g(y). Com os dois extremos em mãos, escolhemos o parâmetro

]?AUI`a ∈ []?AU_, ]?AU^], e assim podemos obter soluções não-dominadas pela

resolução do modelo (3.20)-(3.25) com a inclusão da restrição:

� � K*4 ≤ lotehij4∈67

8

*� (5.2)

Com o objetivo de maximizar f(λ) na Fase II do algoritmo, a adição da restrição

(5.2) ao modelo (3.20)-(3.25) nos fornecerá o maior lucro possível para o número de

lotemax estipulado. As soluções de uma instância com lotemax no intervalo estipulado

anteriormente, definem uma curva de Paretto para o problema com os resultados obtidos

para cada valor de lotemax. A curva será entretanto aproximada, pois as soluções não são

necessariamente ótimas, visto que nem todas as colunas são utilizadas.

Devido ao grande número de resoluções necessárias (para cada valor de lotemax

no intervalo definido), utilizou-se apenas o cenário de demanda 1 para as diferentes

combinações de áreas e culturas, resultando em 12 curvas de Paretto. Os gráficos abaixo

representam o valor obtido para a função objetivo para cada valor de lotemax utilizado.

Para os intervalos maiores, o valor de lotemax foi variado em duas unidades entre um

teste e outro. Devido à proximidade dos resultados e para simplicidade de apresentação,

os gráficos que exibem as curvas foram divididos conforme o número de culturas de

cada instância. O eixo horizontal representa o valor atribuído a lotemax, enquanto o eixo

51

vertical fornece o valor da função objetivo obtido ao resolver o modelo utilizando o

respectivo valor de lotemax na restrição adicional (5.2).

Figura 5.9: Curva de Paretto aproximada para classes de problemas com 12 culturas


1000000,00

1500000,00

2000000,00

2500000,00

3000000,00

3500000,00

15 20 25 30 35

Fu

nçã

o O

bje

tiv

o

Total de lotes permitido

Curvas de Paretto - 12 culturas

1 fazenda

3 fazendas

5 fazendas

1200000,00

1400000,00

1600000,00

1800000,00

2000000,00

2200000,00

2400000,00

2600000,00

2800000,00

25 30 35 40 45 50

Fu

nçã

o O

bje

tiv

o



1 fazenda

3 fazendas

5 fazendas

52



Em todos os casos representados pelas Figuras 5.9-5.12, reparamos que valores

próximos do mínimo necessário para o cumprimento de demanda resultam em valores

muito baixos de lucro: essa discrepância tende a ser mais acentuada conforme o número

de áreas de cultivo aumenta. Ainda assim, a queda significativa na função objetivo

tende a ocorrer só para valores de lote próximos do mínimo possível, indicando que é

possível reduzir ainda mais o número de lotes obtidos pela Fase II do algoritmo

convencional (que não busca a reduão do número de lotes) e ainda manter o lucro

obtido em bons níveis.

450000,00

650000,00

850000,00

1050000,00

1250000,00

1450000,00

1650000,00

1850000,00

2050000,00

2250000,00

2450000,00

30 40 50 60 70

Fu

nçã

o O

bje

tiv

o



1 fazendas

3 fazendas

5 fazendas

380000,00

580000,00

780000,00

980000,00

1180000,00

1380000,00

1580000,00

1780000,00

35 45 55 65 75 85 95

Fu

nçã

o O

bje

tiv

o



1 fazenda

3 fazendas

5 fazendas

53

O tempo computacional de resolução, entretanto, mostrou-se irregular: em geral,

o tempo necessário para os valores extremos (próximos do mínimo e máximo) de lote

foi baixo, enquanto valores intermediários comumente não conseguiam comprovar a

otimalidade dentro do limite estipulado de 3600 segundos. Embora tal limite foi

atingido com frequência principalmente nas classes com 20 e 23 culturas, observou-se

variações bruscas e intermitentes no tempo computacional.

Concluímos que as curvas de Paretto podem ser de grande auxílio na tomada de

decisão, pois é possível reduzir o total de lotes sem grandes perdas no lucro, resultando

em uma administração mais fácil e barata. Porém, o intervalo de possíveis soluções

pode ser extenso e o custo computacional intermitente em sua resolução pode requerer

um tempo muito maior de que se está disposto a investir. Uma alternativa seria definir

números de lotes estratégicos para a geração da curva de Paretto, diminuindo o custo

computacional total.

5.1.5 TESTES CRITÉRIO DE PARADA RELAXADO

Como uma alternativa para agilizar o processo de resolução do algoritmo sem

perdas significativas no retorno, usamos uma tolerância 3I�J > 0 como critério de

parada para a geração de colunas (Fase I da heurística GC-BC): ou seja, o algoritmo

para quando os custos relativos 3* ≤ 3I�J, para todo k = 1,...,L.

Esta abordagem é feita para avaliar se, em uma ocorrência frequente de valores

baixos de ck ao final do algoritmo, obtém-se pouco retorno para a função objetivo. Para

evitar que o algoritmo perca muito tempo gerando colunas de baixo retorno, paramos

precocemente o processo.

Esta ideia foi aplicada inicialmente por Gilmore e Gomory (1963): no problema

de cortes, os autores observaram que em um conjunto de instâncias gerava-se muitos

padrões com pouco ganho após um certo tempo. O critério de parada utilizado,

entretanto, não foi o custo relativo bruto, e sim a ocorrência consecutiva de 10 gerações

que não reduziam o desperdício dos cortes em pelo menos 0,1%. Os resultados obtidos

pelos autores foram satisfatórios para o conjunto de instâncias resolvido.

Os testes descritos abaixo foram realizados utilizando-se 3 classes de problemas:

para 1, 3 e 5 áreas de plantio, todas com 23 culturas disponíveis. Para cada classe de

54

problema aplicou-se 5 cenários de demanda. Em cada teste, o valor de cmin foi variado

em 0 (que caracteriza a otimalidade), 1, 10 e 50.

As comparações foram feitas em relação ao tempo e valor de função objetivo

f(λ) obtido pela Fase I do algoritmo para cmin = 0. Desta forma podemos avaliar o ganho

de tempo e quanto isso impacta o lucro.

As tabelas abaixo são compostas pelas colunas Tempo(s), f1(λ) e f2(λ), que

indicam respectivamente o tempo computacional necessário para a conclusão da

geração de colunas (Fase I), o valor de função objetivo obtido na Fase I e o valor de

função objetivo obtido na Fase II. As linhas que representam cmin = 0 correspondem à

otimalidade. Por facilidade de visualização, as linhas subseqüentes que representam

outros valores de cmin possuem os valores representados porcentualmente em relação à

linha de cmin = 0 correspondente.

Tabela 5.9: resultados computacionais para diferentes cmin para o cenário de demanda 1

hortas cmin Tempo(s) f1(λ) f2(λ)

1

0 292,00 1156875,67 1120579,75

1 -23,63% 0,00% 0,00%

10 -27,40% -0,41% -1,91%

50 -39,38% -3,40% -13,45%

3

0 147,00 1047989,23 977276,44

1 -19,73% 0,00% 0,00%

10 -28,57% -0,29% -0,80%

50 -47,62% -4,87% -7,65%

5

0 213,00 1932003,46 1883068,76

1 -6,10% -0,08% -0,15%

10 -33,80% -0,50% -1,23%

50 -49,30% -3,30% -5,23%



1

0 134,00 2904871,77 2710312,33

1 -1,49% 0,00% 0,00%

10 -19,40% -0,13% -0,11%

50 -27,61% -0,28% -1,15%

3

0 106,00 2444687,87 2361846,42

1 -3,77% 0,00% -0,22%

10 -20,75% -0,44% -0,73%

50 -55,66% -4,18% -4,82%

55

5

0 252,00 3077396,00 2865280,42

1 -15,87% -0,01% -0,09%

10 -48,81% -0,12% -0,24%

50 -66,67% -2,23% -2,98%



1

0 170,00 3410402,34 3203864,68

1 -4,12% 0,00% 0,00%

10 -17,06% -0,07% -0,26%

50 -23,53% -0,24% -0,96%

3

0 112,00 2616609,67 2518966,17

1 -10,71% 0,00% 0,00%

10 -24,11% -0,74% -0,64%

50 -65,18% -2,31% -2,53%

5

0 155,00 3398311,09 3217143,29

1 -25,16% 0,00% 0,00%

10 -31,61% -0,10% -0,39%

50 -70,32% -0,98% -2,81%



1

0 349,00 3273730,05 2921705,53

1 -0,57% 0,00% 0,00%

10 -17,48% -0,04% -0,63%

50 -41,26% -0,24% -1,27%

3

0 208,00 2504727,03 2272860,89

1 -3,37% 0,00% 0,00%

10 -28,37% -0,71% -1,11%

50 -65,87% -1,87% -3,53%

5

0 302,00 3383372,66 3062461,18

1 -4,64% 0,00% 0,16%

10 -46,03% -0,12% -0,59%

50 -64,90% -0,74% -2,25%

56



1

0 84,00 3561636,11 3363829,00

1 -13,10% 0,00% 0,00%

10 -8,33% -0,01% -0,01%

50 -34,52% -0,11% -0,48%

3

0 73,00 2673615,83 2605837,23

1 -13,70% 0,00% 0,00%

10 -34,25% -0,48% -0,56%

50 -60,27% -3,28% -3,46%

5

0 142,00 3520000,31 3369548,30

1 -17,61% 0,00% 0,03%

10 -46,48% -0,04% -0,09%

50 -52,82% -0,85% -1,74%

Não avaliamos aqui o tempo necessário para a resolução da Fase II, pois a

redução obtida é sempre proporcional à redução referente à Fase I, além de o tempo

computacional necessário ser, em sua maioria, muito baixo, de forma que a redução não

é significativa. Em nenhuma instância houve não-atendimento de demanda devido ao

término precoce da geração de colunas.

Em todos os testes, a redução do lucro na Fase II é sempre maior que na Fase I.

Podemos observar que para valores de cmin = 1, há uma pequena redução no tempo,

porém o lucro obtido manteve-se o mesmo na maior parte das instâncias testadas. Isso

indica que raramente colunas geradas com custos menores que 1 são utilizadas na

solução final. O mesmo pode ser dito para os testes de cmin = 10, havendo uma redução

mais significativa no tempo de execução da geração de colunas, mas com reduções de

lucro usualmente menores que 1% mesmo para a Fase II.

Nos testes referentes a cmin = 50, a redução de tempo foi grande, chegando até a

70% em uma das instâncias. Porém, este valor mais alto de cmin acarretou em uma

redução mais acentuada nos lucros, principalmente na Fase II. Embora a redução fique

em torno dos 3%, os valores altos de função objetivo são significativos em valores

absolutos.

Embora a redução porcentual de tempo perante redução de lucro seja atrativa,

vale lembrar que mesmo sem estas considerações o tempo computacional é baixo em

todas as instâncias, tratando-se de um planejamento anual. A análise necessária para

avaliar se a redução obtida é compensada provavelmente não justificaria tal

57

simplificação. Entretanto, se tais proporções forem mantidas em instâncias muito

maiores e de difícil resolução, a redução de tempo pode ser útil, especialmente se forem

necessárias múltiplas resoluções.

5.1.6 TESTES SIMETRIA

Durante os testes da seção 5.1.2, observou-se a ocorrência de simetria nas

instâncias verificadas, o que ocasionava em aumento do tempo computacional de

resolução do modelo. Para melhor avaliar este impacto, propomos um conjunto de testes

que abordasse este ponto, comparando instâncias normais com suas versões com

simetria imposta.

Os testes realizados consistiram em rodar um conjunto de 5 cenários de

demanda, dividido em 8 classes de problema: combinações de 3 ou 5 áreas de plantio

com os diferentes produtividades para as culturas usados nos testes anteriores (as

classes de problema que consideram uma única horta não possuem simetria). Na

sequência repetem-se os testes, de forma que todas as áreas possuam a mesma

produtividade da primeira para todas as culturas, além de remover qualquer proibição de

plantio: desta forma, todas as áreas de plantio da instância testada possuem as mesmas

características, impondo simetria ao problema.

Os gráficos abaixo mostram o tempo computacional necessário para cada

cenário de demanda, tanto para a geração de colunas referente à Fase I (Tempo GC)

como para a resolução do problema inteiro-misto referente à Fase II (Tempo BC). As

curvas acrescidas de “Sim.” referem-se às respectivas fases com simetria forçada.

Figura 5.13: Tempo computacional com simetria imposta para cenário de demanda 1

0,00

1000,00

2000,00

3000,00

4000,00

3 12 3 16 3 20 3 23 5 12 5 16 5 20 5 23

Tem

po

(s)


Teste Simetria - cenário 1

Tempo GC 1

Tempo BC 1

Tempo GC Sim. 1

Tempo BC Sim. 1

58




0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

3500,00

4000,00

3 12 3 16 3 20 3 23 5 12 5 16 5 20 5 23

Tem

po

(s)



Tempo GC 2

Tempo BC 2

Tempo GC Sim. 2

Tempo BC Sim. 2

0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

3500,00

4000,00

3 12 3 16 3 20 3 23 5 12 5 16 5 20 5 23

Tem

po

(s)



Tempo GC 3

Tempo BC 3

Tempo GC Sim. 3

Tempo BC Sim. 3

0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

3500,00

4000,00

3 12 3 16 3 20 3 23 5 12 5 16 5 20 5 23

Tem

po

(s)



Tempo GC 4

Tempo BC 4

Tempo GC Sim. 4

Tempo BC Sim. 4

59


Notamos em todos os gráficos que o aumento do número de culturas leva o

tempo computacional de execução do branch-and-cut ao limite de 3600 segundos

facilmente. O cenário de demanda 5 representado pela Figura 5.17, por sua vez, possui

uma única combinação de dados que não chegou neste limite. O cenário 4, entretanto,

apresentou dificuldades apenas na última classe, como observado na Figura 5.16. Nos

casos em que o limite não era atingido, a resolução foi rápida, com poucos casos de

tempo médio de execução (entre 1000 e 1500 segundos). Nos cenários 1, 2 e 3 o limite

sempre foi alcançado nas classes de problemas com mais de 20 culturas, eventualmente

atingindo este limite também nas classes de 12 e 16 culturas.

Em contrapartida, o cenário 4 mostrou mais explicitamente o aumento do tempo

computacional necessário para a geração de colunas: houve classes de problemas para

as quais o tempo foi até 5 vezes maior. Embora a visualização não seja tão clara,

podemos observar que o aumento de tempo na geração de colunas ocorre em todos os

testes e tende a ser proporcional ao número de áreas de cultivo consideradas.

De forma geral, o problema inteiro misto para as instâncias com simetria forçada

ainda é resolvido rapidamente nas instâncias menores, mas sua dificuldade aumenta

exponencialmente nas instâncias médias e grandes, atingindo facilmente o limite de

3600 segundos para a sua execução na Fase II do algoritmo.

A simetria também pôde ser observada pelo número de colunas geradas, que em

todos os casos o total de colunas era sempre maior que o total obtido pelas respectivas

instâncias para uma única área de cultivo, seguindo novamente a proporção do número

de hortas do problema. Isso é reflexo de os subproblemas obterem as mesmas

0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

3500,00

4000,00

3 12 3 16 3 20 3 23 5 12 5 16 5 20 5 23

Tem

po

(s)



Tempo GC 5

Tempo BC 5

Tempo GC Sim. 5

Tempo BC Sim. 5

60

informações para cada fazenda durante o processo de geração de colunas em cada

iteração, resultando em colunas idênticas.

É importante ressaltar que os valores obtidos na geração de colunas para a

função objetivo das instâncias com simetria forçada foram sempre iguais aos valores

obtidos ao se rodar as respectivas instâncias com uma única área de plantio: ou seja, o

valor de f(λ) para um cenário de demanda aplicado a uma classe de problema com 1 área

de cultivo e 20 culturas e aplicado a uma classe com 3 áreas de cultivo e 20 culturas

eram iguais. Tal resultado era esperado, visto que as áreas de cultivo são idênticas e a

área total é a mesma, o que também comprova que é possível tratar áreas com as

mesmas características como uma única região, evitando a simetria e toda a dificuldade

computacional envolvida, agilizando de forma significativa o processo de resolução e

adquirindo o mesmo resultado.

5.1.7 TESTES LOTE MÍNIMO

Um parâmetro de importância no modelo utilizado, que refletirá diretamente nos

resultados práticos obtidos, é o tamanho mínimo que um lote deverá assumir na solução

final, representado por λmin. Este valor traduz diretamente a mão-de-obra envolvida com

a separação da área de cultivo de cada horta e, portanto, deve ser avaliado com cautela

antes de ser definido.

No modelo utilizado neste trabalho, o valor de λmin é o mesmo para todas as

áreas de plantio. Pode-se definir diferentes valores para cada área, respeitando as

condições de cada agricultor, porém manteremos um valor igual para todas as áreas nos

testes realizados nesta seção.

Os testes realizados previamente consideram λmin = 100. Para analisar os

impactos causados pela mudança deste valor, verificamos 3 classes de problemas, que

variam em número de áreas de cultivo (1, 3 e 5 áreas), todas com 23 culturas

disponíveis para plantio, para cada qual verificamos os valores λmin = 50, 100, 150 e

200. Para estas 12 classes de problemas, aplicamos 5 cenários de demanda diferentes.

O gráfico abaixo representa a redução porcentual de lucro que ocorre na Fase II

do algoritmo GC-BC em relação à Fase I, a qual não possui restrições de lote mínimo.

O eixo horizontal representa as 12 classes de problemas resolvidos, e cada curva

representa um cenário de demanda diferente.

61

Figura 5.18: Redução de lucro para diferentes valores de lote mínimo

Observamos que, independente do cenário de demanda, o comportamento é o

mesmo e notamos que é dependente apenas do valor de λmin, e o número de áreas de

cultivo não trouxe nenhuma mudança significativa nos valores obtidos. A perda de lucro

para λmin = 50 não é muito menor que o perda que ocorre no valor padrão λmin = 100 que

foi utilizado previamente. Para λmin = 150, entretanto, essa porcentagem é claramente

maior, representando mais que o dobro na maioria dos casos. Com o valor ainda maior

de λmin = 200, a perda atinge grandes escalas, entre 30% e 40%. Nenhuma classe

verificada, por sua vez, tornou-se infactível com o aumento de λmin, o que caracteriza

que a área de cultivo disponível era suficiente para um valor alto de lote mínimo.

O gráfico abaixo representa o tempo computacional referente à Fase II do

algoritmo GC-BC para as instâncias verificadas.

Figura 5.19: tempo computacional para diferentes valores de lote mínimo

-50,00%

-40,00%

-30,00%

-20,00%

-10,00%

0,00%

1

50

1

100

1

150

1

200

3

50

3

100

3

150

3

200

5

50

5

100

5

150

5

200

Po

rce

ntu

al d

e r

ed

uçã

o

Parâmetros (nº hortas x tamanho lote mínimo)

Redução de lucro

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

0,00500,00

1000,001500,002000,002500,003000,003500,004000,00

1

50

1

100

1

150

1

200

3

50

3

100

3

150

3

200

5

50

5

100

5

150

5

200

Te

mp

o (

s)

Parâmetros (nº hortas x tamanho lote Mínimo)

Tempo Computacional

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

62

O tempo computacional foi baixo na grande maioria dos casos verificados.

Apenas o cenário de demanda 1 teve uma dificuldade constante, excedendo o limite de

execução de 3600 segundos em quatro instâncias, cujos gaps foram 0,93%, 2,64%,

11,91% e 1,11%.

Com exceção do primeiro cenário de demanda, as classes de problemas com λmin

= 50 foram as que apresentaram um pequeno aumento no tempo computacional de

resolução. Embora esse aumento só se mostrou significativo no cenário de demanda 4, é

possível observá-lo nos demais cenários.

Concluimos que o aumento de λmin só resulta em dificuldades significativas se a

área total de cultivo disponível não oferecer uma “folga” suficiente para trabalhar com

esta mudança. O valor padrão de 100 usado em todos os testes mostra-se adequado para

aplicações práticas, visto que as hortas pertencem a pequenos agricultores, com área de

cultivo limitada. Os resultados indicam que valores diferentes de λmin para cada horta

provavelmente podem ser utilizados sem perda de generalidade nem comprometer a

capacidade de resolução geral do modelo.

63

5.2 TESTES HEURÍSTICA LOTE FIXO

Os testes referentes à Heurística Lote Fixo são apresentados a seguir. A princípio

descrevemos os resultados obtidos para o algoritmo com o critério 1 de seleção de

variável apresentados na Seção 4.2 e na sequência discutimos e avaliamos mudanças

neste critério de escolha aplicado em cada iteração.

Nos testes realizados, são consideradas tolerâncias relativas aos valores

proporcionais de perda (conforme discutido na Seção 4.2). Ambas as tolerâncias na

função objetivo e não-atendimento de demanda foram fixadas em 0,1%.

Ratificando, o algoritmo consiste em selecionar variáveis que assumirão um

valor igual a λmin e a demanda atendida por esta seleção é atualizada. O modelo é

resolvido novamente com a demanda e área residuais. O critério de escolha de variável

a ser fixada a cada iteração é um fator decisivo e os testes realizados avaliam diferentes

critérios.

Para posterior comparação entre os processos de fixação de variáveis, todos os

testes realizados utilizam 12 classes de problemas com os mesmos 5 cenários de

demanda. Desta forma podemos comparar os resultados obtidos para cada método.

Os diferentes processos de seleção de fixação das variáveis são detalhados em

cada seção.

5.2.1 TESTES FIXA LOTE PEQUENO

Os primeiros testes realizados para a Heurística Lote Fixo consideram o critério

1 de seleção de variável a ser fixada. Por facilidade de leitura, repetimos este critério:


1. Seja P = �(=, () | 5*4 < 5I�J U (=, () ∉ �!. 2. Determine (k,s)∈ P tal que 5̅*4 = �2� �5*4 |(=, () ∈ P!.

O conjunto V é o conjunto das variáveis candidatas em cada iteração e F é o

conjunto das variáveis que já foram fixadas em alguma iteração prévia do algoritmo. A

cada iteração, todas as variáveis menores que λmin e que ainda não foram selecionadas

são candidatas. Deste conjunto, aquela que possuir o maior valor (portanto, o valor mais

64

próximo de λmin) será selecionada. A demanda e área disponível são atualizadas

conforme esta seleção.

Variáveis que pertencem ao conjunto F não são mais candidatas a serem fixadas

em λmin, pois estas assumem um valor maior que λmin na solução do problema. Por

exemplo, seja λmin = 100 e uma variável qualquer λ = 50 em uma dada iteração, se 5 ∈ �

a solução respectiva seria λ = λmin + 50 = 150. Isso implica que toda variável pertencente

ao conjunto F possuirá um valor maior ou igual a λmin, e portanto não é passível de

escolha para fixação em uma iteração posterior.

O conceito por trás deste critério de seleção é aproximar para λmin as variáveis

mais próximas deste valor, presumindo que esta aproximação não deve acarretar em

grandes variações nas áreas das outras rotações e em iterações posteriores possam

compensar a produção de outros lotes pequenos, gerando uma solução apenas com lotes

maiores, de mais fácil administração e manuseio.

Os testes realizados consistem da execução da Fase I e Fase II do algoritmo GC-

BC, seguidos da execução do algoritmo Lote Fixo, o qual é iniciado com as colunas

geradas previamente e, finalmente, o modelo é resolvido por um branch-and-cut com

todas as colunas obtidas até então: desta forma uma comparação completa pode ser

feita. Como o algoritmo Lote Fixo atualiza a demanda a ser atendida e a área disponível

iterativamente, estes valores são redefinidos em seus valores iniciais quando o modelo é

resolvido por branch-and-cut na última etapa. O objetivo é avaliar o comportamento da

resolução exata do modelo com as colunas adicionais obtidas pelo algoritmo Lote Fixo,

tanto em tempo computacional como valor de função objetivo.

O gráfico abaixo informa o tempo computacional total de execução do modelo

(algoritmo GC-BC, algoritmo Lote Fixo com as colunas geradas pelo primeiro, e

resolução exata com todas as colunas obtidas por ambos os algoritmos), considerando o

primeiro critério de escolha de variável para o algoritmo Lote Fixo.

65

Figura 5.20: tempo computacional total com o critério 1 do algoritmo Lote Fixo

Observamos que o tempo computacional total manteve-se suficientemente baixo,

com exceção da classe de problema com 3 áreas de cultivo e 23 culturas para o primeiro

cenário de demanda, o qual atingiu o tempo limite de execução de 3600 segundos

durante a solução exata após o algoritmo Lote Fixo. Tirando esta ocorrência e o último

teste para o cenário de demanda 4, todos os testes requeriram menos que 1500 segundos

ao todo, o que é plenamente viável para um planejamento anual.

Para efeito de comparação, o gráfico abaixo apresenta a redução de lucro obtida

na Fase II em relação à solução relaxada da Fase I do algoritmo GC-BC inicial. Este

gráfico representa o resultado dos 5 cenários de demanda utilizados para as 12 classes

de problemas em todos os testes e servirá de referência para comparações posteriores.

Figura 5.21: Redução de lucro da solução exata obtida na Fase II do algoritmo GC-BC

0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

3500,00

4000,00

4500,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)


Tempo Computacional Total

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC


Comparação Fase II GC - Fase I GC

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

66

O gráfico seguinte mostra o quanto a solução obtida pelo algoritmo Lote Fixo é

menor em relação à solução relaxada obtida pela Fase I do algoritmo GC-BC.

Figura 5.22: Redução de lucro do algoritmo Lote Fixo com o critério 1 de seleção

Os resultados obtidos não são muito distantes da média obtida pelo algoritmo

GC-BC tradicional, havendo ocorrências de melhorias e pioras. A porcentagem também

não apresenta um comportamento estável, embora a tendência mais comumente

observada é da qualidade da solução reduzir conforme o número de culturas utilizadas

cresce. O número de áreas de cultivo não mostra influência na qualidade da solução

obtida, porém as classes de problemas de uma única área surpreendentemente possuem

a maior redução porcentual de lucro, de forma mais acentuada que o algoritmo GC-BC.

A seguir, apresentamos a comparação do resultado obtido pela solução exata do

problema mestre restrito às colunas geradas após a execução do algoritmo Lote Fixo

com a primeira solução relaxada obtida na Fase I do algoritmo GC-BC.

Figura 5.23: Redução de lucro da solução exata após Lote Fixo com o critério 1 de seleção

-16,00%-14,00%-12,00%-10,00%

-8,00%-6,00%-4,00%-2,00%0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23Po

rce

nta

ge

m r

ela

tiv

a à

GC


Comparação Lote Fixo - Fase I GC

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23Po

rce

nta

ge

m r

ela

tiv

a à

GC


Comparação Lote Fixo BC - Fase I GC

Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

67

Podemos notar que o comportamento das curvas é similar à solução exata do

problema mestre restrito obtida pelo algoritmo GC-BC, havendo instâncias de pequenas

melhorias na qualidade da solução e outras de ganhos próximos a 2%. Não houve

situações de piora, o que era esperado, visto que o modelo possui as novas colunas

geradas pelo algoritmo Lote Fixo além das anteriores, logo, em pior caso, a solução

ótima obtida é igual à anterior.

Observa-se também que o algoritmo Lote Fixo (figura 5.22) parece gerar

soluções de melhor qualidade que as soluções exatas (figuras 5.21 e 5.23), o que não é

de todo correto: devido aos diversos critérios de parada possíveis para o algoritmo Lote

Fixo, a solução final obtida não necessariamente respeita a condição de lote mínimo

para todas as variáveis, com isso sua solução pode gerar valores “melhores” que a

solução exata gerada com todas as colunas obtida: esta solução é heurística e

potencialmente relaxada.

Concluimos que o algoritmo Lote Fixo com o critério 1 de seleção de variáveis,

por si só, não garante soluções de qualidade, porém as colunas extras obtidas podem

fornecer melhorias na solução exata do problema, com custo computacional aceitável.

5.2.2 TESTES FIXA LOTES GRANDES

Considerando o enfoque do primeiro critério de seleção apenas nas variáveis

pequenas, alteramos este critério para focar também nos lotes maiores. O segundo

critério de seleção avaliado é descrito como:


1. Seja P = �(=, () | 5*4 < 5I�J U (=, () ∉ �! e P′ = �(=, () | 5*4 ≥ 5I�J!. 2. Determine um conjunto de pares ordenados (k,s) que satisfaçam 5̅*4 =

�2� �5*4 |(=, () ∈ P! e todos os pares (=, () ∈ P′.

Desta forma, todas as variáveis maiores que 5I�J e uma variável menor que este

valor são fixadas. Este critério é uma extensão do primeiro, pois fixa a mesma variável

menor que 5I�J além de todas as maiores. Com isso, a atualização de demanda atendida

é feita de forma mais agressiva.

68

O tempo computacional, observado no gráfico abaixo, não é muito diferente do

observado para o critério 1:


Novamente, apenas a classe de problema com 3 hortas e 23 culturas, aplicado ao

primeiro cenário de demanda, excedeu o tempo limite de execução de 3600 na resolução

exata via branch-and-cut após a execução do algoritmo Lote Fixo. O critério 2 obteve

tempo total de execução um pouco menor que o critério 1, mas o comportamento é o

mesmo. Essa pequena redução ocorre devido à atualização de atendimento de demanda

relativo às variáveis de maior valor que são fixadas em cada iteração, acelerando a

redução e consequentemente solução do modelo.

Abaixo, avaliamos a qualidade das soluções obtidas pelo algoritmo Lote Fixo

com o critério 2 de seleção de variável em relação à solução relaxada obtida na Fase I:


0,00

1000,00

2000,00

3000,00

4000,00

5000,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)



Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



Cenário 2

Cenário 3

Cenário 4

Cenário 5

69

O gráfico nos mostra que o critério 2 gera soluções, no geral, levemente

melhores que as obtidas pelo critério 1, quando consideramos apenas o resultado

retornado pela heurística Lote Fixo. Observamos, entretanto, um comportamento

errático nos valores perante a variação de classes de problemas, assim como no primeiro

critério. Um detalhe importante é que o resultado heurístico obtido com este critério

para as classes de problemas 1-20, 1-23 e 3-23 para o cenário de demanda 1 não foi

capaz de atender a demanda imposta: isso resultou no uso das variáveis de não-

atendimento, com custo altamente negativo. Para evitar que estes valores distorcessem o

gráfico, o cenário 1 não foi incluído, porém as demais classes com demanda atendida

tiveram resultados favoráveis, com redução média de 0,84%.

Porém, novamente esta solução é heurística e não garante que a condição de lote

mínimo seja totalmente respeitada na solução final, devido a outras condições de parada

como tolerância de redução na função objetivo ao desconsiderar os lotes pequenos.

Resolvendo o modelo por branch-and-cut após a geração de novas colunas pelo

algoritmo Lote Fixo, obtemos:


Ao comparar estes resultados com os demonstrados na Figura 5.21, notamos que

as diferenças são mínimas, mantendo o mesmo comportamento e média que o critério 1

de seleção.

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

70

Notamos que o critério 2 de seleção de variáveis não gera soluções melhores

para a resolução exata mas a solução heurística e o tempo computacional total são

levemente melhores que o primeiro critério.

5.2.3 TESTES FIXA DOIS LOTES

Visando mixar as idéias de ambos os critérios anteriores, propomos um terceiro

critério de seleção de variáveis, que não foca apenas nas variáveis pequenas nem foca

demais nas variáveis grandes. Definimos o terceiro critério como:


1. Seja P = �(=, () | 5*4 < 5I�J U (=, () ∉ �! e P′ = �(=, () | 5*4 ≥ 5I�J !. 2. Determine dois pares ordenados (k,s) que satisfaçam 5̅*4 = �2� �5*4 |(=, () ∈

P! e 5′*4 = �"l �5*4 |(=, () ∈ P′! .

O critério 3 também pode ser visto como uma extensão do critério 1: além de

selecionar a variável mais próxima de 5I�J do grupo de variáveis menores que este

valor, também considera a variável mais próxima deste valor do grupo das maiores que

o lote mínimo. Desta forma, duas variáveis são escolhidas por iteração do algoritmo.

Usando este terceiro critério de seleção de variáveis para o algoritmo Lote Fixo,

o tempo total de execução obtido é descrito no gráfico abaixo:


0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)



Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

71

Notamos que, embora o comportamento geral é bem próximo do obtido pelos

critérios anteriores, a classe de problema com 3 áreas de cultivo e 23 culturas não

excedeu o tempo de execução de 3600 segundos como previamente. Houve entretanto

um aumento significativo no tempo na última classe de problema para o cenário de

demanda 5.

Os resultados computacionais referentes à função objetivo obtida pela heurística

Lote Fixo quando comparada à obtida pela geração de colunas inicial seguem:


Podemos observar que a solução heurística tende a ter qualidade levemente pior

quando comparada aos critérios anteriores. Além disso, o cenário de demanda 1 para a

classe 1-23 terminou sua execução com demanda-não atendida, resultando em valores

negativo para a função objetivo, portanto sua curva não foi considerada no gráfico

acima: a redução média das demais classes ficou em 2,5%. Novamente, não há garantia

de que a solução fornecida pela heurística respeite todas as restrições de lote mínimo.

O interesse maior encontra-se na solução exata obtida com as colunas extras

geradas pela heurística Lote Fixo. Ao utilizar o critério 3 de seleção, os resultados

obtidos foram:

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



Cenário 2

Cenário 3

Cenário 4

Cenário 5

72


Os resultados obtidos variaram minimamente quando comparados com os

demais critérios. Isso indica que a fixação de uma ou múltiplas variáveis maiores que o

valor definido de lote mínimo não afeta o desempenho do algoritmo durante a geração

de colunas extras após a atualização da demanda atendida.

O terceiro critério de seleção mostrou-se de qualidade igual ao segundo, com

soluções quase idênticas e com o tempo computacional médio próximo.

5.2.3 TESTES FIXA MAIOR DEMANDA

Com o intuito de gerar uma abordagem diferente das anteriores, criamos um

critério que, ao invés de focar as atenções nos valores das variáveis, foca nas demandas

ainda não atendidas.

Várias formulações foram testadas: após definir qual a maior demanda ainda não

atendida, é preciso selecionar qual variável capaz de atender tal demanda será

selecionada para ser fixada em λmin. Após diferentes combinações, o critério final

utilizado foi:

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

73


1. Seja(", �) tal que :̅�� = �2� �:��| " = 1. . �, � = 1. . �!. Em caso de mais de um

candidato, o desempate é feito baseado na ordem lexicográfica das demandas.

2. Dentre as variáveis λks, selecione todas as (k,s) tal que seu respectivo coeficiente

2��*4 = �2� m2��*4 n= = 1. . >, ( = 1. . |)*|! para i e j definidos no Passo 1.

3. Caso mais de uma variável seja selecionada, selecione todas as (k,s) que tenham

sido fixadas previamente o menor número de vezes.

4. Em caso de um novo empate, escolha (k,s) tal que |5*4 − 5I�J| = �"l �|5*4 − 5I�J|} para todas as variáveis selecionadas no Passo 3.

5. Na ocorrência de mais um empate, escolha (k,s) seguindo uma ordem

lexicográfica.

De forma resumida, dentre as variáveis capazes de atender a maior demanda

ainda pendente, aquela que possuir o maior rendimento (caracterizado pelo maior

coeficiente) e foi fixada menos vezes e estiver mais próxima do valor de λmin, será

selecionada. Para o Passo 4, uma faixa de tolerância de 30 foi utilizada, permitindo que

variáveis dentro da menor diferença obtida, acrescida ou subtraída desta tolerância,

fossem candidatas. Os diversos critérios de desempate são necessários para tentar evitar

vícios e ciclos no processo de escolha. Desta forma, atendemos parte da maior demanda

ainda não-atendida usando a rotação de maior produção e que tenha sido menos

utilizada, aumentando a variedade da solução.

O tempo computacional descrito abaixo, assim como nos critérios anteriores,

envolvem todo o processo, desde a primeira geração de colunas até a resolução exata do

problema inteiro após a heurística Lote Fixo.

74


Notamos que o tempo médio de execução é levemente maior que os outros

critérios, porém a instância particular da classe de problemas 3-23 para o cenário de

demanda 1 não estourou o tempo de resolução do problema inteiro final como nos dois

primeiros critérios. Isso sugere que as colunas extras geradas pela heurística Lote Fixo

com o critério de seleção baseado em demanda foram de melhor qualidade.

A seguir, analisamos a qualidade da solução retornada pela heurística:


0,00

500,00

1000,00

1500,00

2000,00

2500,00

3000,00

3500,00

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Te

mp

o (

s)



Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

-35,00%

-30,00%

-25,00%

-20,00%

-15,00%

-10,00%

-5,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



Cenário 2

Cenário 3

Cenário 4

Cenário 5

75

Notamos que a heurística por si só gerou soluções de má qualidade: além de

duas ocorrências de não-atendimento de demanda observados no cenário 1 para as

classes 1-23 e 3-23 (cuja curva foi novamente excluída do gráfico, com redução média

de 27,65% para as classes resolvidas), o resultado obtido chega a ser pior em até 40%.

Com uma perda em torno de 20% entre todas as instâncias, este critério deixou a desejar

comparado com os demais, caso limite-se à solução heurística.

Por outro lado, ao usar-se as colunas extras obtidas na resolução exata do

modelo inicial, o quadro se inverte, como podemos observar no gráfico abaixo:


A solução exata foi de melhor qualidade que os critérios anteriores em boa parte

dos casos, havendo poucas situações piores. Embora o comportamento ainda seja

similar, há leves oscilações favoráveis em relação aos anteriores.

O critério de seleção baseado em demanda, apesar de gerar soluções heurísticas

de má qualidade mesmo com diversos critérios de desempate impostos, permitiu uma

abordagem diferenciada ao gerar novas colunas, que pôde trazer melhorias na solução

final obtida por um método exato.

-12,00%

-10,00%

-8,00%

-6,00%

-4,00%

-2,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



Cenário 1

Cenário 2

Cenário 3

Cenário 4

Cenário 5

76

5.2.5 COMPARATIVO FINAL

A heurística Lote Fixo proposta, embora gere soluções usualmente piores que a

solução exata obtida apenas com as colunas iniciais do algoritmo GC-BC, possui um

bom tempo de execução. Todavia, em instâncias mais difíceis, nem sempre foi capaz de

gerar soluções que atendessem completamente a demanda, mesmo havendo condições

plenas para tal.

Notamos que a principal contribuição da heurística Lote Fixo está justamente na

criação de novas colunas para o problema mestre, permitindo refinar ainda mais a

solução final, ainda dentro de um tempo computacional aceitável. Para melhor

visualizar esta contribuição, juntamos para cada cenário de demanda os resultados da

solução exata obtida para o primeiro conjunto de rotações obtido pelo algoritmo GC-

BC, além da solução exata obtida após a criação de novas colunas para cada critério de

seleção da heurística Lote Fixo.

Figura 5.33: Redução de lucro da solução exata aplicado ao cenário de demanda 1

-5,00%

-4,50%

-4,00%

-3,50%

-3,00%

-2,50%

-2,00%

-1,50%

-1,00%

-0,50%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC


Comparação GC - cenário 1

GC-BC original

Lote Fixo Critério 1




77



Os cenários de demanda 4 e 5 não ofereceram resultados significativos,

mantendo as soluções muito próximas e variações muito pequenas com pouquíssimas

exceções, então foram omitidos para evitar redundância.

Devido aos valores próximos, algumas regiões dos gráficos são de difícil

comparação. Para visualizar em mais detalhes, listamos a seguir as tabelas com os

resultados obtidos. Por questão de facilidade de leitura, o critério com o melhor solução

para cada classe de problema possui seu valor destacado nas tabelas abaixo.

-7,00%

-6,00%

-5,00%

-4,00%

-3,00%

-2,00%

-1,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



GC-BC original





-8,00%

-7,00%

-6,00%

-5,00%

-4,00%

-3,00%

-2,00%

-1,00%

0,00%

1

12

1

16

1

20

1

23

3

12

3

16

3

20

3

23

5

12

5

16

5

20

5

23

Po

rce

nta

ge

m r

ela

tiv

a à

GC



GC-BC original





78

Tabela 5.14: redução de lucro de cada critério para o cenário de demanda 1

hortas cult. GC-BC Critério 1 Critério 2 Critério 3 Critério 4

1

12 -0,97% -0,60% -0,74% -0,72% -0,42%

16 -1,35% -0,69% -0,68% -0,65% -0,70%

20 -1,51% -1,25% -1,05% -1,25% -1,41%

23 -3,96% -1,32% -1,18% -1,15% -1,88%

3

12 -0,91% -0,50% -0,49% -0,49% -0,30%

16 -1,07% -1,07% -1,07% -1,07% -0,98%

20 -1,18% -0,97% -0,97% -1,01% -1,05%

23 -4,43% -3,98% -3,95% -3,82% -3,88%

5

12 -0,17% -0,16% -0,16% -0,16% -0,16%

16 -1,46% -1,46% -1,46% -1,46% -1,46%

20 -1,43% -1,37% -1,38% -1,37% -1,20%

23 -2,21% -2,19% -2,17% -2,18% -1,95%



1

12 -3,90% -3,71% -3,70% -3,70% -3,72%

16 -4,18% -3,73% -3,73% -3,75% -3,89%

20 -5,64% -4,40% -4,67% -4,71% -4,61%

23 -5,92% -4,95% -5,09% -5,08% -5,31%

3

12 -2,90% -2,22% -2,10% -2,26% -1,99%

16 -3,67% -3,60% -3,60% -3,60% -3,59%

20 -3,13% -3,07% -3,10% -3,13% -3,07%

23 -3,36% -3,25% -3,25% -3,25% -3,18%

5

12 -0,93% -0,93% -0,93% -0,93% -0,92%

16 -5,65% -5,41% -5,65% -5,40% -5,29%

20 -5,49% -5,49% -5,46% -5,49% -5,45%

23 -5,75% -5,54% -5,67% -5,67% -5,36%



1

12 -4,11% -3,64% -3,79% -3,79% -3,65%

16 -4,72% -4,43% -4,51% -4,43% -4,36%

20 -5,66% -4,72% -4,82% -4,84% -5,22%

23 -6,81% -5,44% -5,45% -4,92% -5,12%

3

12 -3,09% -2,56% -2,56% -2,95% -2,51%

16 -3,81% -3,81% -3,81% -3,81% -3,81%

20 -3,18% -3,12% -3,12% -3,10% -3,09%

23 -3,77% -3,54% -3,55% -3,49% -3,49%

79

5

12 -0,61% -0,60% -0,60% -0,59% -0,56%

16 -5,94% -5,87% -5,87% -5,87% -5,91%

20 -6,23% -6,16% -6,09% -6,09% -5,81%

23 -5,57% -5,32% -5,17% -5,20% -4,91%

Observamos nos gráficos que o algoritmo GC-BC original sempre possui as

soluções mais distantes em relação ao problema relaxado, enquanto a heurística Lote

Fixo gera algumas melhorias nestas soluções. Isto é esperado, pois a heurística gera

colunas adicionais ao problema restrito, portanto a nova solução é sempre melhor ou

igual que a obtida pelo algoritmo GC-BC. Uma comparação entre os critérios se tornae

difícil devido aos resultados próximos, portanto analisamos os valores discretizados nas

tabelas 5.14-16 para tirarmos conclusões.

Em algumas classes de problemas esta melhoria é ínfima, porém há casos de

ganhos mais significativos. Os quatro critérios de seleção de variável demonstram

comportamento bem similar, porém o critério 4 (baseado em demanda) mostrou-se mais

errático, podendo acarretar em mudanças mais notáveis, tanto gerando soluções finais

de melhor qualidade em relação aos outros critérios (ocorrência mais comum nas classes

de problemas com 3 e 5 áreas de cultivo) quanto de pior qualidade (observado mais

frequentemente nas classes de problemas com 1 área de cultivo). De fato, apenas duas

instâncias com 1 área de cultivo obteve o melhor resultado com o uso do critério

baseado em demanda, como visto nas tabelas 5.14 e 5.16.

Em geral, o uso da heurística Lote Fixo para gerar colunas adicionais ao

problema mestre restrito traz melhorias relativamente baixas comparadas ao resultado

prévio do algoritmo GC-BC, e entre os critérios as diferenças são ínfimas, não oscilando

mais que 0,5%. Porém, considerando-se o baixo custo computacional envolvido nas

instâncias verificadas este esforço adicional mostra-se válido, podendo trazer soluções

de melhor qualidade para um planejamento a longo prazo, com um tempo de execução

levemente maior mas sem impacto.

80

81

6 CONCLUSÕES E PERSPECTIVAS

Este trabalho abordou o problema de planejamento de rotações de culturas, mais

especificamente hortaliças, com atendimento de demanda periódica. Este problema é

aplicado a cooperativas e associações que reúnem pequenos e médios agricultores que

precisam definir o tamanho de cada produção de cada agricultor visando cumprir uma

demanda conhecida, porém cada produtor isoladamente possui limitações como pouca

área de plantio que levam a dificuldades de planejamento e logística associadas à

produção reduzida

As hortaliças possuem a característica de ciclos curtos de cultivo, além de

colheitas parciais. Diferente de cultivos extensivos como cana e laranja, o plantio e a

produção são variados ao longo de um período (por exemplo, um ano). Focando nos

critérios ecológicos que reduzem o uso de fertilizantes e agrotóxicos, este trabalho

utilizou o modelo matemático proposto inicialmente em Santos et al. (2007), cuja base

se manteve nos trabalhos subsequentes da autora, mas com uma abordagem de

atendimento de demanda.

Embora uma abordagem inicial para o problema de demanda tenha sido estudada

na tese de doutorado de Santos (2009), a dificuldade prática decorrente deste modelo foi

a obtenção de soluções que utilizam lotes de plantio muito pequenos. Indepedente dos

recursos disponíveis a um agricultor, o manuseio e administração de um lote muito

pequeno tornam a solução ótima do modelo não aplicável na prática. Os estudos aqui

realizados visaram obter formas de refinar esta solução, incluindo-se restrições

adicionais de lote mínimo para as variáveis de decisão. Tais restrições, entretanto, não

estão disponíveis ao problema mestre restrito, pois dependem das colunas geradas que,

por sua vez, dependem das restrições de lote mínimo. Esta interdependência foi

contornada com heurísticas que geram colunas em uma primeira fase, e incluem as

restrições de lote mínimo em uma segunda fase. As restrições de lote mínimo

modificam o problema, de forma que os resultados aqui obtidos não são passíveis de

comparação com outros trabalhos, inclusive o de Santos: apesar de similares, os

problemas abordados são distintos.

Os testes realizados utilizaram um modelo mestre, que caracteriza o problema de

demanda, e um subproblema responsável por gerar rotações factíveis perante os critérios

impostos, traduzidos em colunas para o problema mestre. O subproblema teve parte do

82

conjunto de restrições simplificada sem perda de generalidade, além de resultar em um

desempenho computacional levemente melhor, conforme descrito na Seção 5.1.3.

Para impor a condição de lote mínimo, foi proposto um par de restrições

adicionais para cada variável de decisão. Este par de restrições requer a inclusão de uma

variável de decisão binária referente a cada variável original, representado o uso ou não

da variável em questão. Esta inclusão torna o modelo linear em um modelo inteiro-

misto, o que aumenta a complexidade de resolução do problema.

Devido à natureza do problema relaxado original, um método de geração de

colunas mostra-se atrativo. Porém, tal método é aplicado apenas a problemas lineares, e

as restrições adicionais de lote mínimo possuem variáveis binárias. Um método branch-

and-price, embora intuitivo perante a uma situação de geração de colunas com variáveis

discretas, possui dificuldades intrínsecas de implementação que incentivam uma

abordagem heurística. Como a geração de todas as colunas possíveis é

computacionalmente inviável, propomos o algoritmo GC-BC, que consiste em adicionar

as restrições de lote mínimo apenas para as colunas geradas pelo problema linear, e

então resolver o novo modelo inteiro-misto por um método de branch-and-cut

tradicional, para o qual foi utilizado o pacote de otimização IBM CPLEX 12.1.

A seção 5.1.1 descreve uma visão panorâmica dos resultados obtidos pelo

algoritmo GC-BC. A resolução do problema inteiro-misto, entretanto, pode adquirir

níveis de complexidade maiores caso características de simetria surjam nas colunas

geradas. Isso pode ocorrer mais facilmente caso múltiplas áreas de cultivo possuam

características similares. Caso as características sejam idênticas ou uma leve relaxação

do problema seja aceitável, áreas similares podem ser tratadas como uma única área de

cultivo para remover a simetria, o que acelera em muito a resolução do problema,

conforme descrito na Seção 5.1.6.

Além da utilização de um tamanho mínimo ao lote, pode ser de interesse aos

produtores reduzir o total de lotes utilizados. Por ser um interesse conflitante com o

objetivo de maximizar o lucro obtido, uma ponderação entre eles ou a criação de uma

curva de Paretto podem auxiliar na tomada de decisão de quantos lotes utilizar. As

seções 5.1.2 e 5.1.4 descrevem a construção dessas ferramentas, e fica claro que uma

redução significativa no número de lotes criados pode ser obtida sem grandes perdas no

lucro, porém o custo computacional envolvido é alto devido às várias resoluções

necessárias e dificuldade de resolução associada à inclusão de novas restrições para a

obtenção das informações desejadas.

83

Utilizar um valor de custo mínimo maior que zero para definir a parada precoce

da geração de colunas, apesar de reduzir o tempo de execução, não mostrou ser uma

abordagem capaz de trazer resultados interessantes ao problema tratado. Descrevemos

na Seção 5.1.5 como o tempo computacional reduzido com esta mudança não justifica

sua aplicação.

Com o enfoque deste trabalho em tratar a condição de lote mínimo, analisamos

na Seção 5.1.7 o comportamento do modelo com diferentes valores de lote mínimo.

Observamos que este valor apenas resulta em dificuldades significativas caso a área de

cultivo disponível seja suficientemente limitada, o que sugere que valores diferentes de

lote mínimo para cada área de cultivo podem ser aplicados sem perda de generalidade e

sem agravar a complexidade do problema.

Considerando a possibilidade de problemas com dimensões que os tornem

impraticáveis para uma resolução exata, propomos a Heurística Lote Fixo para simular a

utilização de lotes mínimos a partir de um modelo linear. Seu conceito é definir qual

variável fixar ao valor mínimo estipulado, e resolver novamente o modelo com sua

demanda e área disponível atualizadas, considerando a fixação realizada,

potencialmente gerando novas colunas. Esse processo é repetido até que algum critério

de parada seja satisfeito, com o ideal sendo parada por atendimento de demanda ou

todas as variáveis não-nulas possuírem valor maior que o lote mínimo desejado: além de

factível, tal solução seria também um limitante inferior para o problema mestre.

A heurística Lote Fixo tem o critério de seleção de variável a ser fixada como o

ponto chave: diversos critérios podem ser definidos, podendo gerar soluções de

diferentes qualidades. Foram propostos quatro diferentes critérios, com os focos

voltados aos lotes menores, aos lotes maiores, um balanço entre os dois e às demandas

não-atendidas. Os detalhes da heurística e dos diferentes critérios de escolha foram

definidos ao longo da Seção 5.2

Apesar da inexistência de trabalhos na literatura que tratem o mesmo problema

para efeitos comparativos, é plausível afirmar que o algoritmo GC-BC mostrou-se um

procedimento efetivo. O tempo computacional de resolução manteve médias baixas, e a

qualidade da solução obtida não esteve muito abaixo do problema linear original.

Concluímos também que os resultados obtidos pela heurística Lote Fixo são

similares para todos os critérios de seleção com exceção do critério com enfoque na

demanda pendente, que gerou soluções de má qualidade. Ainda assim, as soluções

heurísticas geradas não se mostraram muito melhor que as obtidas pelo algoritmo GC-

84

BC. Porém, considerando o tempo computacional de execução baixo, a heurística se

mostrou útil em gerar novas colunas para o problema mestre restrito, permitindo refinar

ainda mais as soluções iniciais pela resolução exata do modelo mestre restrito.

Um método exato, que garanta a obtenção da solução ótima considerando as

restrições de lote mínimo, do tipo branch-and-price, é ainda um desafio para pesquisas

futuras. Estratégias para a construção de métodos tipo branch-and-price consistem em

escrever uma formulação compacta para auxiliar nas ramificações da árvore branch-

and-bound, ou passar informações para os subproblemas relativas às restrições de lote

mínimo, as quais não são explicitamente conhecidas. Ambas as estratégias não são,

aparentemente, triviais.

As abordagens propostas neste trabalho podem ser estendidas a outros estudos

que envolvam restrições de lote mínimo como as únicas restrições com variáveis

discretas, como em problemas de corte que exigem que um número mínimo de placas

de metal sejam cortadas conforme um padrão de corte. O algoritmo GC-BC por si só

mostrou-se uma estratégia razoável para um branch-and-price e auxiliado pela

heurística Lote Fixo permite um refinamento ainda maior da solução obtida. Para

problemas simétricos, a heurística Lote Fixo pode fornecer limitantes inferiores de

qualidade com tempo de execução reduzido.

85

Referências Bibliográficas

[1] ALFANDARI, L.; LEMALADE, J.; NAGIH, A.; PLATEAU, G. A mip flow

model for crop-rotation planning in a context of forest sustainable

development. Annals of Operations Research, v. DOI: 10.1007/s10479-009-

0553-0, 2009.

[2] ALTIERI, M. A.; FARRELL, J. G.; HECHT, S. B.; LIEBMAN, M.;

MAGDOFF, F.; MURPHY, W.; NORGAARD, R. B.; SIKOR, T. O.

Agroecology: the science of sustainable agriculture. 1995.

[3] CAMPANHOLA, C.; VALARINI, P. J. A agricultura orgânica e seu potencial

para o pequeno agricultor. Caderno de Ciência e Tecnologia, v. 18, n.3, p. 69 -

101, 2001.

[4] CLARKE, H. Combinatorial aspects of cropping pattern selection in

agriculture. European Journal of Operational Research, v. 40, p. 70 - 77, 1989.

[5] COSTA, A. M.; DOS SANTOS, L. M. R.; ALEM, D. J.; SANTOS, R. H. S.

Sustainable vegetable crop supply problem with perishable stocks. Annals of

Operation Research, v. DOI: 10.1007/s10479-010-0830-y, 2011.

[6] DETLEFSEN, N.; JENSEN, A. Modelling optimal crop sequences using

network flows. Agricultural Systems, v. 94, p. 566 - 572, 2007.

[7] DOGLIOTTI, S.; ROSSING, W.; ITTERSUM, M. V. Rotat, a tool for

systematically generating crop rotations. European Journal of Agronomy, v.

19, p. 239 - 250, 2003.

[8] EL-NAZER, T.; MCCARL, B. The choice of crop rotation: A modeling

approach and case study. American Journal of Agricultural Economics, v.

68(1), p. 127 - 136, 1986.

[9] GLIESSMAN, S. R. Agroecology: ecological processes in sustainable

agriculture. 2000.

[10] GOMES, R.M.; ARENALES, M.N. Otimização linear aplicada ao plantio

sustentável de vegetais. Anais do XLII Simpósio Brasileiro de Pesquisa

Operacional, p. 331 – 342, 2010.

[11] HANEVELD, W.; STEGEMAN, A. Crop succession requirements in

agricultural production planning. European Journal of Operations Research, v.

166, p. 406 - 429, 2005.

86

[12] HILDRETH, C.; REITER, S. On the choice of a crop rotation plan. TC

Koopmans, p. 177 - 188, 1951. Proceedings of the Conference on Linear

Programming held in Chicago in 1949.

[13] KANTOROVICH, L. Mathematical methods of organizing and planning

production (traduzido do original em russo, datado 1939). Management

Science, v. 6, p. 366 - 422, 1960.

[14] ONG'WEN, O.; WRIGHT, S. Small farmers and the future of sustainable

agriculture. Ecofair Trade Dialogue, Discussion Paper, v. 7, 2007.

[15] SANTOS, L. M. R.; SANTOS, R. H.; ARENALES, M. N.; RAGGI, L. A. Um

modelo para a programação de rotações de culturas. Pesquisa Operacional, v.

27, p. 535 - 547, 2007.

[16] SANTOS, L. M. R.; MICHELON, P.; ARENALES, M. N.; SANTOS, R. H. S.

Crop rotation scheduling with adjacency constraints. Annals of Operations

Research, v. DOI: 10.1007/s10479-008-0478-z, 2008.

[17] SANTOS, L. M. R. Programação de rotação de culturas modelos e métodos de

solução. 2009. (Tese de Doutorado) - Universidade de São Paulo - campus São

Carlos, 2009.

[18] SANTOS, L. M. R.; ARENALES, M. N.; COSTA, A. M.; SANTOS, R. H. A

linear optimization approach for increasing sustainability in vegetable crop

production. Computational Methods for Agricultural Research: Advances and

Applications (Editores: Dr. Prado, Dr. Barreto Luiz e Dr. Chaib Filho), v. 1, p.

234 - 265, 2010a.

[19] SANTOS, L. M. R.; COSTA, A. M.; ARENALES, M. N.; SANTOS, R. H. S.

Sustainable vegetable crop supply problem. European Journal of Operational

Research, v. 204, p. 639 - 647, 2010b.

[20] VANDERMEER, J. H. The ecology of intercropping. Cambridge University

Press, 1992.

87

Apêndice A Para os experimentos computacionais realizados neste trabalho foram selecionadas 23 culturas cultivadas em uma horta orgânica em Barbacena – MG. As culturas 20 a 23 são leguminosas para adubação verde. Os dados de plantio produtividade das culturas são apresentadas nas tabelas a seguir. A unidade de tempo utilizada para definir os ciclos é de uma semana. O ciclo de cultivo de cada cultura inclui o tempo estimado para plantio e colheita.

Tabela A.1 – Dados de plantio e ciclo de 23 culturas

CULTURA FAMILIA ÉPOCA PLANTIO

CICLO Início Fim

1 Alface americana 1 Compositae ano todo 7 2 Alface mimosa 1 Compositae ano todo 7 3 Alface lisa 1 Compositae ano todo 7 4 Almeirão 1 Compositae ano todo 7 5 Couve 2 Brassicaceae fevereiro setembro 32 6 Brócolis 2 Brassicaceae fevereiro outubro 20 7 Couve-Flor 2 Brassicaceae março outubro 18 8 Beterraba 3 Chenopodiaceae fevereiro setembro 11 9 Espinafre 3 Chenopodiaceae fevereiro setembro 20 10 Abobrinha 4 Cucurbitaceae outubro fevereiro 14 11 Moranga 4 Cucurbitaceae novembro janeiro 19 12 Pepino 4 Cucurbitaceae setembro março 13 13 Alho 5 Liliaceae março abril 24 14 Cebola 5 Liliaceae março julho 24 15 Alho porró 5 Liliaceae abril abril 12 16 Quiabo 6 Malvaceae novembro janeiro 27 17 Tomate 7 Solanaceae ano todo 24 18 Cenoura 8 Umbelliferae ano todo 16 19 Salsinha 8 Umbelliferae outubro fevereiro 21 20 Mucuna preta 9 Leguminosae outubro janeiro 16 21 Feijão-de-porco 9 Leguminosae outubro fevereiro 12 22 Tremoço 9 Leguminosae março julho 18 23 Ervilha Peluda 9 Leguminosae março julho 20

88

Tabela A.2. Dados sobre colheitas parciais de 19 culturas: nome,unidade de medida, número de períodos de 1 semana até a primeira colheita (representada por oi, e produção esperada nos sucessivos períodos de colheita.

CULTURA unidade

de medida COLHEITA

io 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 Alface americano Unidade 5 9 3 2 Alface mimosa Unidade 5 9 3

3 Alface lisa Unidade 5 9 3

4 Almeirão Unidade 5 9 3

5 Couve Maço 12 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 6 Brócolis Maço 10 1 1 2 2 3 3 3 2 2 1

7 Couve-Flor Unidade 16 1 3 8 Beterraba Kg 8 1 2 1

9 Espinafre Maço 5 3 4 4 4 4 4 4 4 4 4 4 4 3 3 2

10 Abobrinha Kg 9 0,2 0,3 0,3 0,3 0,2

11 Moranga Kg 16 0,5 0,5 0,5

12 Pepino Kg 8 1 2 2 1 1

13 Alho Kg 23 0,3 14 Cebola Kg 23 3

15 Alho porró Kg 8 3 3 3 3

16 Quiabo Kg 14 0,2 0,3 0,3 0,4 0,4 0,4 0,4 0,4 0,4 0,4 0,2 0,2 0,2 17 Tomate Kg 15 0,8 0,8 1 1 1,2 1,2 1 0,8 0,2

18 Cenoura Kg 13 1,5 2 1,5 19 Salsinha Maço 8 14 16 16 16 16 16 16 16 16 16 16 14 10

Documents

Otimização linear aplicada ao plantio sustentável de vegetais · super agradáveis, roscas de goiabada e cuecas-viradas que levava para casa (que não se limitaram ao primeiro