\chapter{Conceitos básicos de otimização}
\label{cap:conceitos}

O principal objetivo deste trabalho é resolver um problema de otimização logística. Portanto, o que é otimizar? A matemática nos oferece diversas ferramentas para resolvermos questões práticas do nosso dia-a-dia e a otimização é mais uma delas. Muitas das vezes não nos damos conta do quanto a otimização nos envolve. Ela aparece desde os primeiros cálculos como nos exemplos clássicos de dimensionamento de uma caixa de papelão ou ao calcular a maior área de terreno possível a ser cercada com uma certa metragem de rede. Sem falar dos estudos na engenharia, na indústria, na roteirização, na escala de pessoal e em diversos outros campos.

No contexto da logística, a otimização influencia desde a localização dos centros de distribuição e de todas as unidades envolvidas até ao planejamento do sistema de transporte. Pode minimizar os custos com combustível e o desgaste das peças dos modais envolvidos na locomoção do material. Pode ainda, maximizar a agilidade nas entregas o que é muito importante, principalmente para as cargas perecíveis. Fica evidente que inúmeras variáveis influenciam, como o clima, a resistência do material de transporte e o transportado, os custos, o tempo, a disponibilidade do material humano, entre outros.

Para Saramago e Steffen Jr (2008), otimizar nada mais é do que buscar uma solução ou um conjunto de soluções ótimas para uma dada função ou um conjunto de soluções. Sendo assim, teremos que modelar a função objetivo de acordo com os nossos conhecimentos matemáticos, sabendo o que desejamos maximizar ou minimizar, para enfim, acharmos a solução ótima. Vamos então, esmiuçar os conceitos básicos de otimização.




\section{Definições e teoremas}

\begin{definicao}[Conjunto limitado] Seja $D$ um subconjunto de $\R^n$, caso $D$ esteja contido em uma bola aberta de centro na origem, então $A$ é um conjunto limitado.
\end{definicao}

\begin{definicao}[Conjunto fechado] Seja $D$ um subconjunto de $\R^n$, caso $D$ contenha todos os pontos de sua fronteira, então $D$ é um conjunto fechado.
\end{definicao}

\begin{definicao}[Conjunto Compacto] Seja $D$ um subconjunto de $\R^n$, caso $D$ seja um conjunto fechado e limitado, então $D$ é um conjunto compacto.
\end{definicao}

\begin{definicao}[Função contínua] Seja $f: D \subset \R^n \rightarrow \R$. Dizemos que $f$ é contínua em um ponto $\mathbf{p}=(a,b)$ de seu domínio~$D$, se para toda sequência $$\mathbf{x}_n=(x_n,y_n)\rightarrow(a,b)=\textbf{p}$$ no domínio, isto é, se para todo par de sequências numéricas $x_n \rightarrow a \textrm{ e } y_n \rightarrow b,$ com $(x_n,y_n) \in D$, tem-se $$f(x_n,y_n)\rightarrow f(a,b)$$ na imagem. Se $f$ é contínua em todos os pontos do seu domínio, então dizemos simplesmente que $f$ é contínua.
\end{definicao}



\begin{teorema}[Teorema de Weierstrass]
Toda função \mbox{$f: D\subset\R^n\rightarrow\R$} contínua, definida num conjunto compacto~$D$, possui pelo menos um máximo global e pelo menos um mínimo global em~$D$.
\end{teorema}

\begin{definicao}[Máximo e mínimo locais e globais] Sejam $f: D \subset \R^n \to \R$, $B\subset D$ uma bola aberta e $\mathbf{x}^*\in B$:
	\begin{enumerate}[label=(\roman*)]
		\item $\mathbf{x}^*$ é um \emph{ponto de máximo local} de $f$ em $D$ se  $f(\mathbf{x}^*) \geq f(\mathbf{x})$ para todo $\mathbf{x}\in B$;
		
		\item $\mathbf{x}^*$ é um \emph{ponto de mínimo local} de $f$ em $D$ se  $f(\mathbf{x}^*) \leq f(\mathbf{x})$ para todo $\mathbf{x}\in B$;
		
		\item $\mathbf{x}^*$ é um \emph{ponto de máximo global} de $f$ em $D$ se  $f(\mathbf{x}^*) \geq f(\mathbf{x})$ para todo $\mathbf{x}\in D$;
		
		\item $\mathbf{x}^*$ é um \emph{ponto de mínimo global} de $f$ em $D$ se  $f(\mathbf{x}^*) \leq f(\mathbf{x})$ para todo $\mathbf{x}\in D$;
	\end{enumerate}
\end{definicao}

Para nós, o Teorema de Weierstrass é de grande valia pois, trataremos de problemas de otimização em que a função objetivo~$f$ será contínua e nosso conjunto de restrições determinará um domínio compacto para essa função. Desta forma, o Teorema de Weierstrass nos garante a existência de pontos de máximo e mínimo globais de~$f$ dentro desse domínio.



\section{Alguns problemas de otimização}

Como já foi dito anteriormente, a otimização tem aplicações nas mais variadas áreas. Apresentaremos aqui alguns exemplos.

\subsection{Problemas de mistura}

Neste problema, queremos determinar o quanto é necessário de diferentes materiais para que, ao misturá-los, obtenhamos um produto com peculiaridades específicas. Como aconteceu, por exemplo, no caso real do responsável pela alimentação do Exército norte-americano. Ele queria descobrir a combinação de alimentos mínimos necessários para prover uma alimentação saudável e com os nutrientes indispensáveis para a tropa prosseguir no combate. Uma outra aplicação seria nas fundições, onde são utilizados diferentes insumos para que, após passarem por um forno de alta temperatura, formam uma liga metálica que precisa ter características específicas para ser aprovada pelas normas técnicas da metalurgia e, sempre, tendo o menor preço possível.

Mais uma situação, poderia ser em uma fábrica de suco concentrado de frutas. Suponhamos que, para produzir a bebida, a indústria precise utilizar substâncias para dar sabor, adoçar, aromatizar, etc. A ideia é obter uma mistura que contenha quantidades específicas de cada ingrediente e com o menor custo possível.

Seja $n$ o número de ingredientes que podem ser utilizados na produção da mistura e $ m $ o número de componentes relevantes para a mistura. Sejam ainda $ x_{j} $ a quantidade de ingrediente $ j $ que deve ser utilizada em uma unidade da mistura, $ a_{ij} $ a quantidade do componente $ i $ no ingrediente $ j $, $ b_{i} $ a quantidade do componente $ i $ na mistura, $ c_{j} $ o custo de uma unidade no ingrediente $ j $, onde $ i=1,2,\ldots,m $ e $ j=1,2,\ldots,n$.

Desta maneira, como queremos minimizar o custo, podemos expressar o problema da mistura da seguinte forma:


\begin{equation*}
\begin{aligned}[t]
\minimizar\: & f(x_1,x_2,\ldots,x_n) = c_{1}x_{1}+c_{2}x_{2}+\ldots+c_{n}x_{n} \\
\operatorname{s.a.}\: &
\begin{aligned}[t]
&a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} =  b_{1}\\
&a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} =  b_{2}\\
&\qquad\qquad\qquad\vdots\\
&a_{m1}x_{m} + a_{m2}x_{m} + \ldots + a_{mn}x_{n} =  b_{m}\\
&x_{1}+x_{2}+\ldots +x_{n}  = 1\\
&x_{1}\geq0, x_{2}\geq0,\ldots,x_{n} \geq 0
\end{aligned}
\end{aligned}
\end{equation*}


%$$
%\begin{aligned}[t]
%\minimizar\: & f(x_1,x_2,\ldots,x_n) = c_{1}x_{1}+c_{2}x_{2},\ldots,c_{n}x_{n} \\
%\operatorname{s.a.}\: &
%\begin{aligned}[t]
%a_{11}x_{1} +a_{12}x_{2}+\ldots+a_{1n}x_{n} &= b_{1}\\
%a_{21}x_{1}+a_{22}x_{2}+\ldots+a_{2n}x_{n} &= b_{2}\\
%&\vdots\\
%a_{m1}x_{m}+a_{m2}x_{m}+\ldots+a_{mn}x_{n} &= b_{m}\\
%x_{1}+x_{2}+\ldots +x_{n} &= 1\\
%x_{1}\geq0, x_{2}\geq0,\ldots,x_{n}&\geq 0
%\end{aligned}\\
%\end{aligned}
%$$


\subsection{Problemas de planejamento de produção}

Existem diversos tipos de problemas de planejamento de produção e muitos deles podem ser resolvidos por meio da otimização linear. Um desses tipos é o problema de \emph{mix} de produção (planejamento estático). Ele ocorre quando uma fábrica deseja produzir diferentes tipos de produtos em diferentes épocas do ano, com o objetivo de atender à demanda e tornar o lucro da empresa o maior possível. Para isto, é necessário levar em consideração as restrições das máquinas, do material humano, do estoque, do investimento, etc.

A ideia é utilizada quando se deseja produzir uma quantidade $ x_{j} $, $ j=1,\ldots,n $ de um produto em um certo período do planejamento. Sendo $ b_{i} $ a capacidade do recurso $ i $, $ i=1,\ldots,m $, disponível neste período. Consideremos que, para a produção de uma unidade do produto $ j $, a quantidade $ a_{ij} $ de recurso $ i $ é utilizada. Existe a quantidade mínima $ p_{j} $ de produto $ j $ a ser produzida, haja vista os pedidos já existentes e ao estoque mínimo que a gerência deseja manter. Enquanto isso, o departamento de vendas, baseado em tabelas de períodos anteriores, prevê uma quantidade máxima $ q_{j} $ de unidades a serem vendidas. Cada produto $ j $ vendido contribui $ l_{j} $ para o lucro da empresa. 

Desta maneira, como queremos maximizar o lucro, concluímos que o problema de \emph{mix} de produção (planejamento estático) é expresso da seguinte forma:


$$
\begin{aligned}[t]
\maximizar\: & f(x_{1},x_{2},\ldots,x_{n}) = \sum_{j=1}^{n} l_{j} x_{j}\\
\sa\: & 
\begin{aligned}[t]
\sum_{j=1}^{n} a_{ij} x_{j} \leq C_{i} &\quad i=1,2,\ldots,m\\
p_{j} \leq x_{j}\leq q_{j} & \quad  j=1,2,\ldots,n\\
\end{aligned}
\end{aligned}
$$


\subsection{Problemas de transporte}

Esse tipo de situação diz respeito ao transporte de diferentes tipos de materiais. Por exemplo, o transporte de itens de um centro de distribuição aos mercados consumidores. A situação consiste em atender à demanda, considerando os limites da oferta, de modo que o custo total do transporte seja o menor possível.

Um situação hipotética seria o transporte de aparelhos de televisão que possuem centros de distribuição e mercados consumidores, sendo estes os destinos e aqueles as origens. Temos então $ m $ origens e $ n $ destinos. Sabemos que o custo para que se transporte um aparelho da origem $ m $  para o destino $ j $ é $ c_{ij} $. Sabemos ainda que, na origem $ i $, a oferta de televisores é $ a_{i} $ e no destino $ j $, a demanda é $ b_{j} $.

Seja $ x_{ij} $ a quantidade transportada do produto da origem $ i $ ao destino $ j $. Como o caminhão não sai vazio, essas quantidades sempre serão positivas, isto é $ x_{ij}\geq0 $, $ i=1,\ldots,m $ e $j=1,\ldots,n$. Seja também $ c_{ij}x_{ij} $ o custo para que se transporte a quantidade $ x_{ij} $ da origem $ i $ ao destino $ j $ e então, o custo total de transporte é a soma dos custos de transporte de todas as quantidades transportadas de $ i $ até $ j $, isto é $ \sum_{i=1}^{j} \sum_{i=1}^{j} c_{ij}x_{ij} $, o qual deve ser o menor possível.

Claramente, que tudo aquilo que sai da origem $ i $ não pode ultrapassar a quantidade de produtos disponíveis em $ i $, ou seja, para $i=1,\ldots,m$ temos $ \sum_{j=1}^{n} x_{ij} \leq a_{ij} $ e ainda, as quantidades de produtos que chegam no destino $ j $ devem satisfazer a demanda requerida neste local, ou seja, para todo $j=1,\ldots,n$ temos $ \sum_{i=1}^{m}x_{ij} = b_{j} $.
