Mostrando postagens com marcador Pesquisa Operacional. Mostrar todas as postagens
Mostrando postagens com marcador Pesquisa Operacional. Mostrar todas as postagens

terça-feira, 1 de dezembro de 2015

Programação Dinâmica Determinística

A programação dinâmica (PD) determina a solução ótima de um problema de multivariáveis decompondo-o em estágios, sendo que cada estágio compreende um subproblema com uma única variável. A vantagem da decomposição é que o processo de otimização em cada estágio envolve apenas uma variável, uma tarefa mais simples em termos de cálculo do que lidar com todas as variáveis simultaneamente. Um modelo PD é basicamente uma equação recursiva que liga os diferentes estágios do problema de maneira que garante que a solução ótima viável de cada estágio também é ótima e viável para o problema inteiro.
            A notação e a estrutura conceitual da equação recursiva são diferentes de quaisquer outras que você tenha estudado até aqui. A experiência mostrou que a estrutura da equação recursiva pode não parecer lógica para um principiante. Se você já passou por experiência semelhante, sabe que o melhor procedimento é tentar implementar o que lhe pareça lógico e então executar os cálculos de acordo com isso. Você não tardará a descobrir que as definições apresentadas no livro são as corretas e, durante o processo, aprenderá como a PD funciona.
            Embora a equação recursiva seja uma estrutura comum para a formulação de modelos de PD, os detalhes da solução são diferentes. Somente pela exposição a diferentes formulações é que você conseguirá ganhar experiência em modelagem de PD e solução de PD.

Aplicação real – Otimização de corte transversal e alocação de toras na Weyerhaeuser
            Árvores antigas são cortadas e serradas em toras para fabricar diferentes produtos finais (como madeira para construção civil, compensado, placas ou papel). As especificações das toras (por exemplo, comprimento, diâmetros finais) são diferentes dependendo da serraria onde as toras serão usadas. Com árvores cortadas de até 35 metros de comprimento, o número de combinações de cortes transversais que atende aos requisitos da serraria pode ser grande, e a maneira como a árvore é desmembrada em toras pode afetar a receita. O objetivo é determinar as combinações de cortes transversais que maximizem a receita total. O estudo usa a programação dinâmica para otimizar o processo. O sistema proposto foi implementado pela primeira vez em 1978, resultando em um aumento anual do lucro de no mínimo $ 7 milhões.

NATUREZA RECURSIVA DOS CÁLCULOS EM PD

            Os cálculos em PD são feitos recursivamente, de modo que a solução ótima de um subproblema é usada como dado de entrada para o subproblema seguinte. Quando o último subproblema é resolvido, a solução ótima para o problema inteiro está à mão. O modo como os cálculos recursivos são executados depende de como decompomos o problema original. Em particular, os subproblemas normalmente estão ligados por restrições em comum. À medida que passamos de um subproblema para o seguinte, a viabilidade dessas restrições em comum deve ser mantida.

Fonte: Taha

quinta-feira, 12 de novembro de 2015

Exercício de PO (Programação Linear Inteira)

A mobileCo está destinando um orçamento de 15 milhões de dólares para a construção de até sete estações transmissoras para cobrir a máxima população possível em 15 comunidades geográficas contíguas. As comunidades cobertas por cada transmissora e os custos de construção previstos em orçamento são dados na Tabela J.

Tabela J:


A tabela K dá as populações das diferentes comunidades.

Quais das transmissoras propostas devem ser construídas?

Resolução:
-Binário:
xt= 1, caso a transmissora xi seja construída;
     0, caso contrario.

xc= 1, se a comunidade c dor abrangida;
      0, caso contrário.

-Variáveis de decisão:
ct=custo do transmissor t.
Sc=conjunto de transmissores que abrange a comunidade c.
Pj=população da comunidade j
t= 1, 2, 3, 4, 5, 6, 7, 8
c= 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

-Função objetivo:
Max z = P1c1 + P2c2 + P3c3 + P4c4 + P5c5 + P6c6 + P7c7 + P8c8 + P9c9 + P10c10 + P11c11 + P12c12 + P13c13 + P14c14 + P15c15
Sujeito a:      



Solução: construir transmissores 2,4,5,6 e 7. Todas as comunidades são abrangidas, exceto a comunidade 1.


segunda-feira, 9 de novembro de 2015

Exercício de PO (Programação Linear Inteira)

Uma universidade pretende formar um comitê para tratar das reclamações dos estudantes. A administração quer que o comitê seja composto por ao menos uma mulher, um homem, um estudante, um administrador e um membro da faculdade. Dez indivíduos (identificados, para simplificar, pelas letras A a J foram indicados. O mix desses indivíduos nas diferentes categorias é apresentado na tabela F.

Tabela F
Categoria
Indivíduos
Mulheres
a, b, c, d, e
Homens
f, g, h, i, j
Estudantes
a, b, c, j
Administradores
e, f
Membros da Faculdade
d, g, h i

A universidade em questão quer formar o menor comitê que tenha representação de cada uma das cinco categorias. Formule a questão como um problema de PLI e ache a solução ótima.
Solução:
Estudante e mulher: a
Administrador e homem: f
Membro da faculdade: d
O comitê tem como uma das soluções ótimas os indivíduos: a, d, f.

sexta-feira, 6 de novembro de 2015

Exercício de PO (Programação Linear Inteira)

A ABC é uma empresa de caminhões de transporte que entrega diariamente cargas menores do que a capacidade total dos caminhões a cinco clientes. A Tabela D apresenta os clientes associados com cada rota.

Tabela D:

Rota
Clientes atendidos na rota
1
1,2,3,4
2
4,3,5
3
1,2,5
4
2,3,5
5
1,4,2
6
1,3,5

Os segmentos de cada rota são ditados pela capacidade do caminhão que está fazendo as entregas. Por exemplo, na rota 1, a capacidade do caminhão é suficiente para entregar cargas apenas aos clientes 1,2,3 e 4. A Tabela E apresenta uma lista de distâncias (em milhas) entre o terminal de caminhões (ABC) e os clientes.
Tabela E:


O objetivo é determinar a menor distância necessária para fazer as entregas diárias aos cinco clientes. Embora a solução possa resultar no atendimento de um cliente por maus de uma rota, a fase de implementação usará somente uma dessas rotas. Formule a questão como um problema de PLI e ache a solução ótima.
  
Resolução:
-Binário:
xj: 1, se a rota j for selecionada;
      0, caso contrário.

Distância total da rora (ABC, 1, 2, 3, 4, ABC) = 10 + 32 + 14 + 15 + 9 = 80 milhas
Minimizar z = 80x1 + 50x2 + 70x3 + 52x4 +60x5 + 44x6
Sujeito a:
x1 + x3 + x5 + x5 >= 1
x1 + x3 + x4 + x5 >= 1
x1 + x2 + x4 + x6 >= 1
x1 + x2 + x5 >= 1
x2 + x3 + x4 + x6 >= 1
xj = (0,1) para todo j
Solução: selecione as rotas (1,4,2) e (1,3,5), z = 104
O Cliente 1 deve ser omitido em uma das duas rotas.

quinta-feira, 5 de novembro de 2015

Momento AMPL – (PLI)

A Figura 2 apresenta um modelo geral em AMPL para qualquer problema de cobertura. A formulação é direta, logo que a utilização de conjunto indexado seja entendida. O modelo define streetcomo um conjunto indexado corner {strret)define as esquinas como uma função de rua. Com esses dois conjuntos, as restrições do modelo podem ser formuladas diretamente. Os dados do modelo dão os elementos dos conjuntos indexados que são específicos para a situação do exercício resolvido na postagem anterior ( link da postagem anterior: http://adf.ly/1R834H ). Qualquer outra situação é tratada com a alteração dos dados do modelo.


Figura 2:



Problema de cobertura - Programação Linear Inteira (PLI)

Nessa classe de problemas, várias instalações oferecem serviços sobrepostos a várias localidades. O objetivo é determinar o número mínimo de instalações que cobrirão (isto é, satisfarão as necessidades) cada localidade. Por exemplo, estações de tratamento de água podem ser construídas em vários locais, sendo que cada uma atenderia a um conjunto diferente de cidades. A sobreposição surge quando uma dada cidade pode receber serviços de mais de uma estação.

Exemplo: Instalação de telefones de segurança
Para promover a segurança no campus, o Departamento de Segurança de uma universidade iniciou um processo de instalação de telefones de emergência em locais selecionados. O departamento quer instalar o número mínimo de telefones, contanto que cada uma das ruas principais do campus seja atendida por no mínimo um telefone. A Figura 1 mapeia as ruas principais (A a K) do campus.
É lógico colocar os telefones em cruzamentos de ruas, de modo que cada telefone atenda no mínimo duas ruas. A figura 1 mostra que o layout das ruas requer um máximo de oito localizações de telefones.

Figura 1


Resolução:
Defina-se
-Binário:
xj:  1, se um telefone for instalado no local j
      0, caso contrário

-Restrições
As restrições do problema requerem a instalação de no mínimo um telefone em cada uma das 11 ruas (A a K). Assim, o modelo se torna

Minimizar z= x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8
Sujeito a:
x1 + x2  >= 1 (Rua A)
x2 + x3 >= 1 (Rua B)
x4 + x5 >= 1 (Rua C)  
x7 + x8 >= 1 (Rua D)
x6 + x7 >= 1 (Rua E)
x2 + x6 >= 1 (Rua F)
x1 + x6 >= 1 (Rua G)
x4 + x7 >= 1 (Rua H)
x2 + x4 >= 1 (Rua I)
x5 + x8 >= 1 (Rua J)
x3 + x5 >= 1 (Rua k)

xj(0,1), j=1,2,3,4,5,6,7,8

A solução ótima do problema requer instalar quatro telefones nos cruzamento 1,2,5 e 7.
Comentários:Em sentido escrito, problemas de cobertura são caracterizados por:
1) as variáveis xj, j=1,2,...,n são binárias;
2) os coeficientes do lado esquerdo das restrições são 0 ou 1;
3) o lado direito de cada restrição é da forma (>=1);
4) a função objetivo minimiza c1x1 + c2x2 + ... + cnxn, em que cj>0 para todo j=1,2,...,n.
Neste exemplo, cj=1 para todo j. Se cj representar o custo de instalação no local j, então esses coeficientes podem assumir valores que não sejam 1.
Variações do problema de cobertura incluem condições adicionais de lado.
  



Exercício de PO (Programação Linear Inteira)

(Graves et al., 1993) A Ulern University usa um modelo matemático que otimiza as preferências dos estudantes levando em consideração a limitação das salas de aula e dos recursos da faculdade. Para demonstrar a aplicação do modelo, considere o caso simplificado de dez estudantes que devem selecionar dos cursos eletivos entre os seis oferecidos. A tabela C apresenta contagens que representam a preferência de cada estudante para cursos individuais, sendo que a contagem 100 é a mais alta. Para simplificar, considera-se que a contagem de preferência para uma seleção de dois cursos e a soma das contagens individuais. A capacidade dos cursos é o número máximo de estudantes que poderão assistir às aulas.

Tabela C


Contagem de preferências por curso
Estudante
1
2
3
4
5
6
1
20
40
50
30
90
100
2
90
100
80
70
10
40
3
25
40
30
80
95
90
4
80
50
60
80
30
40
5
75
60
90
100
50
40
6
60
40
90
10
80
80
7
45
40
70
60
55
60
8
30
100
40
70
90
55
9
80
60
100
70
65
80
10
40
60
80
100
90
10
Capacidade
Do curso
6
8
5
5
6
5

Formule a questão como um problema de PLI e ache a solução ótima.
Resolução:
 -Binário:
xij= 1, se o estudante i selecionar o curso j
        0, caso contrário.
-Variáveis:
cij= contagem de preferência associada;
Cij= capacidade do curso j.
Maximizar z = (somatório i) vezes (somatório j) cij,xij
Sujeito a
(somatório de j)xij=2, i=1,2,...,10, (somatório de j)xij <= Cj, j=1,2,...,6

-Solução:
Curso 1: Estudantes: (2, 4, 9)
Curso 2: Estudantes: (2, 8)
Curso 3: Estudantes: (5, 6, 7, 9)
Curso 4: Estudantes: (4, 5, 7, 10)
Curso 5: Estudantes: (1, 3, 8, 10)
Curso 6: Estudantes: (1, 3)
Contagem total = 1775