Aula 06: Dualidade (aula prática) · / 12/ 14 Túlio Toffolo — Otimização Linear e Inteira — Aula 06: Dualidade (aula prática) Exercício 1: max. s.a. Exemplo: O Problema

BCC464/PCC174 — 2018/2Departamento de Computação — UFOP

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

Otimização Linear e InteiraAula 06: Dualidade (aula prática)

Exercício 1

/ 12/ 14 Túlio Toffolo — Otimização Linear e Inteira — Aula 06: Dualidade (aula prática)

Exercício 1:

max.

s.a.

Exemplo: O Problema da Dieta

Minimizar: 32u1+36u2 (6)

Sujeito a: 8u1+ 6u2 3 (7)4u1+ 6u2 2, 5 (8)u1 � 0 (9)

u2 � 0 (10)

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

Exemplo: O Problema da Dieta

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

Sujeito a: 8x1+ 4x2 � 32 (2)6x1+ 6x2 � 36 (3)x1 � 0 (4)

x2 � 0 (5)

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

min.

s.a.

PL Primal PL Dual

�3

Exercício 2


Exercício 2: Carteira de Investimentos

Uma empresa gerencia recursos de terceiros através da escolha de carteiras de investimentos para diversos clientes, baseados em bonds de diversas empresas. Um de seus clientes exige que:

The football leagues grouping problem

Problem constraints:

Leagues must comprise between m� and m+ teams.At most 2 teams from the same club can be in a league.There is a limit on the level difference between teams inthe same league.There is a limit on the travel time/distance between teamsin the same league.

It’s a generalization of the clique partitioning problem withminimum clique size requirement.

7 / 25 Toffolo et al. – IP heuristics for nesting problems

Não mais de 25% do total aplicado deve ser investido em um único investimento;






Um valor superior ou igual a 50% do total aplicado deve ser investido em títulos de maturidade maiores que 10 anos;






O total aplicado em títulos de alto risco deve ser, no máximo, de 45% do total investido.

Considerando a tabela de retorno, risco e maturidade (próximo slide), determine a estratégia ótima para o investidor de forma que a rentabilidade de sua aplicação seja máxima.

�5



Título Retorno anual (%)

Maturidade (anos)

Risco

1 8,7 15 1 – Muito baixo

2 9,5 12 3 – Regular

3 12,0 8 4 – Alto4 9,0 7 2 – Baixo5 13,0 11 4 – Alto6 20,0 5 5 – Muito alto

�6



�7

Forma Padrão

max .X

j2Titulos

retornoj

100xj

s.a. xj 25 8j 2 TitulosX

j2Titulos|maturidadej�10

xj � 50

X

j2Titulos|riscoj�4

xj 45

X

j2Titulos

xj = 100

3 / 34 Túlio Toffolo – Otimização Linear e Inteira – Aula 03: Simplex e Modelagem



1. Qual o melhor retorno que se pode obter? Quanto se deve aplicar em cada título para que se tenha o retorno ótimo?

2. Em qual percentual aumentaria o retorno se fosse permitido aplicar 1% a mais no Título 2? Qual seria o retorno? Essa regra vale até quanto?

3. A partir de qual percentual a aplicação no Título 3 é vantajosa?

4. Se fosse imposto limitar a aplicação em cada título em 24% para um dentre os títulos 2, 4 e 6, em qual título deveria ser feita a diminuição de aplicação? Justifique.

5. Quanto é a influência da limitação de aplicação em título de alto risco? Qual seria o retorno se esta limitação fosse de 49%?

�8

Exercício 3


Exercício 3: Produção de automóveisThe football leagues grouping problem





Uma empresa deve produzir 1000 automóveis. Ela tem quatro fábricas, as quais, devido a diferenças na mão-de-obra e avanços tecnológicos, as plantas diferem no custo de produção de cada carro. Elas também utilizam diferentes quantidades de matéria-prima e mão-de-obra. A tabela abaixo resume essas informações:

Fábrica Custo (R$ mil) Mão-de-Obra Mat. Prima

1 15 2 32 10 3 43 9 4 54 7 5 6

�10


Exercício 3: Produção de automóveisThe football leagues grouping problem





Um acordo trabalhista requer que pelo menos 400 carros sejam produzidos na Fábrica 3. Existem 3300 horas de mão-de-obra e 4000 unidades de material que podem ser alocas às 4 fábricas:

åÎFabricasj

jj xcmin

åÎ

£Fabricasj

jj TotMObraxMObra

åÎ

£Fabricasj

jj x aTotMatPrimMatPrima

åÎ

=Fabricasj

jx Producao

0| ¹Î"³ jjj AcordoFabricasjAcordox

�11


Exercício 3: Produção de automóveis

1. Quais são as quantias ótimas de produção? Qual o custo da produção?

2. Quanto custa produzir mais um veículo? Quanto economizamos produzindo um veículo a menos?

3. Como mudaria a solução se custasse somente R$8.000,00 para produzir na fábrica 2? Como ficaria o custo?

4. Quanto o acordo está custando? Qual seria a variação no custo se o acordo fosse de 250 carros?

5. Até que custo ainda é vantajoso produzir na Fábrica 2?

�12

Exercício 4


Exercício 4Exercício

Exercício1 Resolva o PL abaixo e seu dual utilizando o método

Simplex:

min. x1+ x2

s.a. 2x1+ 5x2 � 105x1+ 3x2 � 4x1, x2 � 0

21 / 34 Túlio Toffolo – Otimização Linear e Inteira – Aula 03: Simplex e Modelagem�14

/ 12

Perguntas?

Documents

Aula 06: Dualidade (aula prática) · / 12/ 14 Túlio Toffolo — Otimização Linear e Inteira — Aula 06: Dualidade (aula prática) Exercício 1: max. s.a. Exemplo: O Problema