Universidade Federal do Amazonas

class: center, middle, inverse, title-slide

# Universidade Federal do Amazonas
## Instituto de Ciência Exatas e Tecnologia
### Prof. Dr. Hidelbrando Ferreira Rodrigues
### Pesquisa Operacional II - Aula 01
### Turma: Engenharia de Produção
### Ano civil: 2021 - Semestre letivo 2020/2
### 2021-08-16

---

## Programação Discreta

### Introdução
> A característica que distingue otimização discreta ou combinatória é que algumas das variáveis pertencem a um conjunto discreto, tipicamente, um subconjunto dos números inteiros.

--
Otimização discreta também é conhecida como programação **inteira** e **combinatória**.

--
Problemas de programação inteira aparecem em profusão na vida real e aplicações ocorrem nas mais diversas áreas, tais com:

> 
- energia 
--
- transportes 
--
- telecomunicações  
--
- circuitos eletrônicos 
--
- biologia molecular  
--
- medicina e saúde 
--
- criptografia 
--
- aviação 
--
- finanças

Uma grande variedade de aplicações é encontrada em engenharia de produção, compreendendo:
--

> 
- planejamento e programação da produção 
--
- projeto de *layout* de sistemas de produção  
--
- localização de instalações 
--
- distribuição de produtos

Variáveis discretas importantes nessas aplicações envolvem, por exemplo:
--

> 
- dicidir se um produto é fabricado ou não em um período 
--
- escolher a melhor sequência de itens a serem processados em uma máquina 
--
- escolher o melhor local, dentre vários candidatos, a intalar uma nova fábrica ou centro de distribuição
--
- determinar as melhores rotas de distribuição de produtos

---

### Introdução
--

> Um produto com variáveis inteiras e reais é denomiando de *Programação Linear Inteira Mista (PIM)*, quando tem a seguinte forma:

`$$z = max\quad \textbf{cx + dy}$$`
`$$\mathbf{Ax + Dy} \leq \mathbf{b}$$`
`$$x \in R_{+}^{n}, y \in Z_{+}^{p}$$`
> 
em que `$\mathbf{A}$`, uma matriz (mxn), `$\mathbf{D}$`, uma matriz (mxp), `$\mathbf{c}$`, um vetor  (1xn), `$\mathbf{d}$`, um vetor (1xp), e `$\mathbf{b}$`, um vetor (mx1), representam parâmetros do problema.

--
> 
Os vetores de variáveis são `$\mathbf{x}$` e `$\mathbf{y}$` com dimensões (nx1) e (px1).

--
> 
`$\mathbf{R_{+}^{n}}$` representa o espaço dos vetores com `$n$` componentes reais e `$\mathbf{Z_{+}^{p}}$` representa o espaço de vetores com *p* componestes inteiras não-negativas.

Quando todas as variáveis são inteiras, tem-se um problema de *programação (linear) inteira (PI)*,

`$$z = max\quad \textbf{cx}$$`

`$$\mathbf{Ax} \leq \mathbf{b}$$`
`$$x \in R_{+}^{n}$$`
---

### Introdução
--

e se todas as variáveis assumem valores 0 ou 1, tem-se um problema de programação 0-1 ou *binária (PB)*, escrita como

`$$z = max\quad \textbf{cx}$$`
`$$\mathbf{Ax} \leq \mathbf{b}$$`
`$$x \in B^{n}$$`
em que `$B^{n}$` representa o espaço de vetores com *n* componentes binárias.

Um outro tipo de problema é o problema de *otimização combinatória (OC)*, que pode ser definido da seguinte forma.

> 
É dado um conjunto finito `$N= {1, ..., n}$`, um conjunto de pesos `$c_{j}$` para cada `$j \in N$`, e uma família `$F$` de subconjuntos factíveis de `$N$`. O problema de otimização consiste em achar o subconjunto de peso mínimo de `$F$`, isto é:

`$$min\{\sum_{j \in s}c_{j}: S \in F \}$$`

De modo geral, um problema de *OC* pode ser como o problema de *PI* ou *PB*.

> 
Problemas de Programação Inteira e Combinatória são resolvidos por *métodos ótimo (exatos)*, que fornecem uma solução ótima;

--
> 
por algoritmos aproximados, que garantem a distância máxima entre a solução subótima encontrada e o valor ótima;

--
> 
ou por *métodos heurísticos*, que em geral, fornecem uma solução subótima, sem conhecimento da qualidade desta em relação a uma solução ótima.

---

.left-column[
Exemplo 1.

`$$z = max\quad \textbf{10x1 + 6x2}$$`
`$$\mathbf{9x1 + 5x2} \leq \mathbf{45}$$`
`$$\mathbf{-4x1 + 5x2} \leq \mathbf{5}$$`
`$$\mathbf{x} \in \mathbf{Z}_{+}^{2}$$`
]

.right-column[

<div class="figure" style="text-align: center">
<img src="Imagens/PLI.png" alt="Figura 1" width="35%" />
<p class="caption">Figura 1</p>
</div>

Ao se mover ao longo da direção do gradiente da função ovjetivo `$(5,3)$`, observa-se que a solução órima é `$x= (5,0)$`, com valor `$z=50$`.

A figura mostra um conjunto de soluções factíveis que satisfazem as restrições do exemplo, que é dado por `$X={(0,0), (0,1), (1,0), (1,1), (2,0), (2,1), (2,2), (3,0), (3,1), (3,2), (3,3), (4,0), (4,1), (5,0)}$`

]

---
.left-column[

Exemplo 2.

`$$z = max\quad \textbf{2x1 + 3x2}$$`
`$$\mathbf{6x1 + 8x2} \leq \mathbf{10}$$`
`$$\mathbf{x} \in \mathbf{B}_{+}^{2}$$`

O conjunto de soluções factíveis do Exemplo 2 é dado por `$x = {(0,0), (1,0), (0,1)}$`. Calculando o valor de cada solução, tem-se que a solução ótima é `$\mathbf{x}=(0,1),$` com valor `$z=3$`

]

.right-column[

A seguinte modificação do Exemplo 1 ilustra um problema de programação inteira-mista:

Exemplo 3

`$$z = max\quad \textbf{10x1 + 6x2}$$`
`$$\mathbf{9x1 + 5x2} \leq \mathbf{45}$$`
`$$\mathbf{-4x1 + 5x2} \leq \mathbf{5}$$`
`$$\mathbf{x_{1}} \in \mathbf{R}_{+}^{1}, \mathbf{x_{2}} \in \mathbf{Z}_{+}^{1}$$`
A Figura 2 mostra que o conjunto de soluções factíveis consiste em quatro seguimentos de reta descrito por: `$X_{1}={(x_{1},0), \quad 0 \leq x_{1} \leq 5}$`, `$X_{2}={(x_{1},1), \quad 1\frac{1}{4} \leq x_{1} \leq 3\frac{8}{9}}$`, `$X_{3}={(x_{1},2), \quad 0 \leq x_{1} \leq 4\frac{4}{9}}$`, `$X_{4}={(x_{1},3), \quad 2\frac{1}{2} \leq x_{1} \leq 3\frac{1}{3}}$`.

<div class="figure" style="text-align: center">
<img src="Imagens/PLIM.png" alt="Figura 2" width="27%" />
<p class="caption">Figura 2</p>
</div>
]

---

## Programação não linear

Aqui, faremos uma breve introdução à programação não linear, mostrando suas diferenças com relação à programação linear. Salientaremos, ainda, a dificuldade dos algoritmos na resolução desses problemas e suas possíveis consequências.

■ Resolução gráfica de problemas de programação não linear.
--

■ Programação côncava, convexa e quadrática.
--

■ Programação não linear utilizando o Excel.
--

Como sabemos, um modelo é uma representação simplificada de uma situação real. 
--

O conceito de simplificação inerente aos modelos está relacionado, sobretudo, ao fato de que, dada a complexidade da realidade, é praticamente impossível e/ou economicamente inviável incluir na representação do problema todas as variáveis que podem interferir no resultado do fenômeno que estamos estudando, ou por seu grande número ou por desconhecimento. Assim, o modelo em geral abrange apenas as variáveis mais relevantes e que exercem maior impacto sobre o problema.

Ao trabalhar com um grupo restrito de aspectos, um modelo só será útil e adequado caso represente, da maneira mais fidedigna possível, o comportamento das variáveis selecionadas. Esse comportamento, no entanto, raramente se mostra tão simples de ser trabalhado como nos problemas de programação linear. Na realidade, a maioria dos modelos que tratam de problemas reais apresenta algum grau de não linearidade.

Problemas de mix de produtos, em que a margem de lucro por produto varia de acordo com a quantidade vendida, e problemas de transporte, com custos variáveis que dependem da quantidade enviada, são apenas alguns exemplos corriqueiros nos quais o comportamento das variáveis relevantes é não linear.

---

## Programação não linear

Problemas de otimização em que a função-objetivo e/ou pelo menos uma das restrições envolvidas não são funções lineares das variáveis de decisão são denominados problemas de programação não linear (PNL ou nonlinear programming, em inglês). Neste capítulo, abordaremos as principais características desse tipo de problema, bem como apresentaremos diversas técnicas para resolvê-los com o auxílio de uma planilha eletrônica.

Um problema de programação não linear pode ser genericamente representado da seguinte forma:

Otimizar: `$Z = f(X_{1}, X_{2}, ..., X_{n})$`
sujeito a restrições:

<img src="Imagens/pnl.png" width="35%" style="display: block; margin: auto;" />
em que pelo menos uma das funções `$f$` ou `$g_{i}$` é não linear.

Percebemos que essa representação é ampla demais para que haja um único algoritmo capaz de resolver todos os problemas que podem ser incluídos nesse formato.

---

Os Problemas 1, 2 e 3 a seguir, por exemplo, são extremamente diferentes entre si; contudo, são todos de programação não linear.

---
## Programação não linear

Para entendermos claramente as diferenças entre problemas de programação linear e problemas de programação não linear, desenvolveremos alguns exemplos. Iniciaremos com o Problema 4, a seguir, de programação linear (PL).

Problema 4: Max Z = 2x1 + 8x2

--
                      s.r.

x1 ≤ 5

2x2 ≤ 14

3x1 + 2x2 ≤ 17

x1, x2 ≥ 0
                      
---
O conjunto de soluções viáveis do Problema 4 está representado na Figura 3 e sua solução gráfica está representada na Figura 4.

Resolver problemas lineares como esse é relativamente simples. Precisamos apenas:

1. definir a região viável delimitada pelas restrições;

2. identificar o extremo (no caso de solução ótima única) da região viável em que a função-objetivo apresenta o maior valor, para um problema de maximização, ou o menor valor, para um problema de minimização.

No Problema 4, a solução ótima está no ponto extremo formado por x1 = 1 e x2 = 7, pois apresenta o maior valor possível para a função-objetivo (Z = 58).

<img src="Imagens/fig3.png" width="35%" style="display: block; margin: auto;" />
---
## Programação não linear

Agora modificaremos o Problema 4. Manteremos a função-objetivo, porém trocaremos as restrições lineares 2x2 ≤ 14 e 3x1 + 2x2 ≤ 17 pela restrição não linear 4x12 + 9x22 ≤ 144. Portanto, temos agora o Problema 5, dado a seguir:

Problema 5: Max Z = 2x1 + 8x2
  
  
                      s.r.
  
  
                      x1 ≤ 5
                      
                      
                      4x12 + 9x22 ≤ 144
                      
                      
                      x1, x2 ≥ 0

Essa modificação introduz a não linearidade no problema, modificando as fronteiras do conjunto de soluções viáveis de apenas retas para retas e curvas. Nesse caso, o conjunto de soluções viáveis (Figura 3) tem uma fronteira delimitada por uma elipse (lugar geométrico representado pela restrição introduzida)1 e por diversas retas.

---

Nesse caso, a função-objetivo é uma reta e a metodologia para se encontrar a solução ótima é a mesma do problema de programação linear, isto é, ir incrementando o valor de Z até que nenhum ponto da reta pertença ao conjunto de soluções viáveis (Figura 4).

Conforme podemos perceber, a solução ótima ainda se situa na fronteira do conjunto de soluções viáveis. No entanto, nesse segundo problema, a solução ótima não é mais um extremo do conjunto de soluções viáveis. Essa constatação reflete uma das características dos problemas de programação não linear, que é a possibilidade de a solução ótima assumir qualquer valor do conjunto de soluções viáveis, não havendo a simplificação existente nos problemas de programação linear.
---
## Programação não linear

.left-column[
Suponha agora o Problema 6, de otimização não linear, em que todas as restrições são lineares (as mesmas do Problema 4) e apenas a função-objetivo é não linear

Problema 6: Max Z = 784x1 – 49x21 + 576x2 – 36x22

s.r.

x1 ≤ 5

2x2 ≤ 14

3x1 + 2x2 ≤ 17

x1, x2 ≥ 0

]
--
.right-column[
<img src="Imagens/fig5.png" width="50%" style="display: block; margin: auto;" /><img src="Imagens/fig6.png" width="50%" style="display: block; margin: auto;" />
]