Aula 01: Introdução - Otimização Linear e Inteira...Introdução Exemplo de problema: Objetivo: encontrar o maior número primo. Restrição: com 3 casas decimais. Solução ótima:

Aula 01: IntroduçãoOtimização Linear e Inteira

Túlio A. M. Toffolohttp://www.toffolo.com.br

BCC464/PCC174 – 2018/2Slides baseados no material de Haroldo Gambini

http://www.toffolo.com.br

Aula de Hoje

1 Otimização

2 Pesquisa Operacional

3 Exemplo: O Problema da Dieta

4 Método Gráfico

1 / 26 Túlio Toffolo – Otimização Linear e Inteira – Aula 01: Introdução

Aula de Hoje

1 Otimização



4 Método Gráfico


Introdução

Selecionar a melhor entre um conjunto de alternativas

Ramo da matemática aplicada:

teoria;

algoritmos;

aplicações.


Introdução

Exemplo de problema:

Objetivo:

encontrar o maior número primo.

Restrição:

com 3 casas decimais.

Solução ótima:

997


Introdução

FormatoFunção objetivo:

f : Rn → R

Restrições que definem o conjunto de soluções válidas:S ⊆ Rn

(normalmente um conjunto de equações/desigualdades)

Resolvendo...

Encontrar x∗ ∈ S, uma solução ótima, que minimiza/maximiza o valorda função objetivo f


Otimização ...

Linearx1 + 3x2 . . .

Não Linearseno(x1) + 3x2 . . .

Contínuax ∈ Rn

Discretax ∈ Zn

Multicritério

...


Aula de Hoje

1 Otimização



4 Método Gráfico


Pesquisa Operacional

Ramo da Ciência que lida com a otimização do desempenho de sistemas.

Otimizar...

maximizar lucro;

maximizar satisfação;

minimizar custos;

minimizar riscos;

...


Pesquisa Operacional: Origens Históricas

Início formal: II Grande Guerra Mundial

Exército britânico:

Cerca de 1000 cientistas de Pesquisa Operacional.

Grupo altamente interdisciplinar.

Problemas resolvidos pelo grupo:

Localização de radares.

Determinação do tamanho de frotas de navios.

Detecção de submarinos.

Rapidamente implementado pelos países aliados.


Pesquisa Operacional: Definição

Pesquisa Operacional (PO) ou Ciência do Gerenciamento es-tuda as operações de uma organização e utiliza modelos matemá-ticos e/ou computacionais ou outras abordagens analíticas paraencontrar maneiras melhores de realizá-las.

The Science of Betterhttp://www.scienceofbetter.org/


http://www.scienceofbetter.org/

Construindo um Modelo

Interesse em modelar matematicamente o processo de decisão:

Parar com o:

E começar a formalizar:

x1 + x4 + x7 ≤ 10x3 − x5 ≥ 5. . .


O Modelo

Variáveis de Decisão

variáveis cujos valores serão escolhidos.

Exemplo

Planejamento de produção de combustíveis:

x1 quantidade em milhares de litros de gasolina que será produzida;

x2 quantidade em milhares de litros de diesel que será produzido.


O Modelo

Dados de Entrada

valores fixos (decididos a priori);

também chamadas variáveis não controladas.

Exemplo

Planejamento da Produção:

custos de matéria prima;

custos trabalhistas;

disponibilidade de matéria prima.


Programação Linear: breve histórico

George Dantzig

1939: teoria matemática por Kantorovich(lhe rendeu um Nobel)

1940: algoritmo Simplex (por Dantzig)

baseado em operações elementares sobre matrizes;

tedioso de resolver a mão.

felizmente: nascimento do computador eletrônicotambém nos anos 40!


Programação Linear

Utilização Pós-Guerra

Crescente utilização no comércio e indústria

Moscow, 1958: Planejamento do transporte de areia para construção:

10 pontos de origem

230 pontos de destino

10 dias de um computador Strena

11% de economia


Programação Linear

Utilização Pós-Guerra

Rijkswaterstaat da Noruega, 1986: definição da política degerenciamento de água

15 milhões economizados anualmente

Eletrobrás, CEPEL, 1986: alocação de recursos térmicos e hidráulicosno sistema nacional gerador de energia

43 milhões economizados anualmente


Programa Linear - Formato

Função Objetivo

Minimizar custo, tempo, risco, poluição, . . . ouMaximizar lucro, qualidade, segurança, . . . ouEncontrar qualquer solução viável

Restrições

Disponibilidade: recursos finitos, . . .Operacionais: horários de trabalho, tempo de máquina, . . .Limites: venda em escala, . . .


Aula de Hoje

1 Otimização



4 Método Gráfico


Exemplo: O Problema da Dieta

Para uma boa alimentação, o corpo necessita de vitaminas e proteínas.

A necessidade mínima de vitaminas é de 32 unidades por dia e a de proteínasde 36 unidades por dia.

Uma pessoa tem disponível carne e ovos para se alimentar. Cada unidade decarne contém 8 unidades de vitamina e 6 unidades de proteínas. Cada unidadede ovo contém 4 unidades de vitamina e 6 unidades de proteínas.

Cada unidade de carne custa 3 unidades monetárias e cada unidade de ovocusto 2,5 unidades monetárias.

Qual a quantidade diária de carne e ovos que deve ser consumida para suprir asnecessidades de vitaminas e proteínas com menor custo possível



Variáveis de Decisãox1 quantidade de carne

x2 quantidade de ovos

Custo de uma solução

Preço da carne: 3 unidades monetárias

Preço dos ovos: 2,5 unidades monetárias

Custo total = 3x1 + 2, 5x2



A solução tem que satisfazer os requerimentos nutricionais:

Nutriente Quantidade MínimaVitaminas 32Proteínas 36

Restrições

Carne OvosVitaminas 8x1 4x2 ≥ 32Proteínas 6x1 6x2 ≥ 36



Minimizar: 3x1+2, 5x2 (1)

Sujeito a: 8x1+ 4x2 ≥ 32 (2)

6x1+ 6x2 ≥ 36 (3)

x1 ≥ 0 (4)

x2 ≥ 0 (5)


Aula de Hoje

1 Otimização



4 Método Gráfico


O Método Gráfico

Trabalhando com 2 variáveis, podemos visualizar um Programa Linearno plano cartesiano:

Soluções representadas por pontos no gráfico.

Restrições indicadas por regiões do gráfico onde as soluções sãoválidas.


Método Gráfico - Restrições

x1

x2

1 2 3 4 5 6 7 8 9 10

1

2

3

4

5

6

1

Exemplo: considere a restrição x1 + 2x2 ≥ 10


Exemplo de Método Gráfico: A Roça

Um pequeno agricultor está decidindo quantos sacos de sementes irá plantar desoja e de milho.

Ele dispõe de 350 reais. O custo do saco de sementes de soja é 70 reais e ocusto do saco de sementes de milho é de 50 reais.

Para buscar as sementes o agricultor tem uma picape capaz de carregar 400 kilos.Cada saco de sementes de soja pesa 50 quilos e cada saco de sementes de milhopesa 80 kilos.

Consultando o vendedor, ele verificou que o vendedor dispõe de 4 sacos de sojae uma grande quantidade de sacos de milho.

O agricultor calculou que irá lucrar na época da colheita 300 reais por saco desoja e 280 reais por saco de milho plantados.

Quantos sacos de soja/milho ele deve plantar para maximizar o lucro?


O Gráfico

x1

x2

1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

300

600

900

1200

1500

18001720,4

Variáveis:x1: qtde de sojax2: qtde de milho

Restrições:Dinheiro (máx: 350)

soja: 70milho: 5070x1 + 50x2 ≤ 350

Peso (máx: 400)soja: 50milho: 8050x1 + 80x2 ≤ 400

Disponibilidadesoja: 4x1 ≤ 4

Lucro (Objetivo):

Max. 300x1 + 280x2


Espaço de Soluções

Exemplo 21 desenhe no gráfico a região factível (região de soluções) que satisfaz

as restrições abaixo:x1 + 3x2 ≤ 122x1 + x2 ≥ 16x1 ≥ 0 e x2 ≥ 0


/ 12Túlio Toffolo — Otimização Linear e Inteira: Apresentação

x1

x2

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1


x1+3x2 12 (6)2x1+ x2 � 16 (7)

x1, x2 � 0 (8)

29 / 31 Túlio Toffolo – Otimização Linear e Inteira: Aula 01



Exercício1 desenhe no gráfico a região factível (região de soluções) que satisfaz

as restrições abaixo:5x1 + 2x2 ≥ 254x1 − 3x2 ≥ −3x1 ≥ 0,x1 ≤ 2x2 ≥ 0


/ 12

Perguntas?

Documents

Aula 01: Introdução - Otimização Linear e Inteira...Introdução Exemplo de problema: Objetivo: encontrar o maior número primo. Restrição: com 3 casas decimais. Solução ótima: