programação linear
146 pág.

programação linear


DisciplinaProgramação Linear141 materiais745 seguidores
Pré-visualização25 páginas
Programação Linear
Mauricio Pereira dos Santos
Departamento de Matemática Aplicada
Instituto de Matemática e Estatística
UNIVERSIDADE DO ESTADO DO RIO DE JANEIRO
ii
Copyright c©2.000 por Mauricio Pereira dos Santos
Editoração: O autor, criando arquivo texto no format LaTex.
Fluxos e figuras: Visio e Corel Paint, incluídos no texto como EPS (Encapsulated
Postscript File).
30072007
Conteúdo
1 Introdução 1
1.1 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Solução gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Respostas dos exercícios da seção 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 O modelo geral da Programação Linear . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6 Variações do Modelo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 O que está implícito em qualquer modelo de P.Linear . . . . . . . . . . . . . . . . . 16
1.8 Exemplos de formulação de modelos de Programação Linear . . . . . . . . . . . . . . 18
1.9 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.10 Respostas dos exercícios da seção 1.9 . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2 O Método Simplex 33
2.1 Definições básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Um método não muito eficiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Situações que podem acontecer no Método Simplex . . . . . . . . . . . . . . . . . . . 43
2.3.1 Empate na escolha da variável entrante . . . . . . . . . . . . . . . . . . . . . 43
2.3.2 Empate na escolha da variável sainte . . . . . . . . . . . . . . . . . . . . . . 44
2.3.3 Não existência de variável sainte . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.4 Múltiplas (infinitas) soluções ótimas . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.5 Modelos de Minimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.3.6 Modelos com variáveis irrestritas em sinal . . . . . . . . . . . . . . . . . . . 50
2.4 Outras formas de modelos - O Simplex de 2 fases . . . . . . . . . . . . . . . . . . . . 51
2.5 Novos algorítimos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.7 Respostas dos exercícios da seção 2.6 . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3 Análise depois do Ótimo 61
3.1 Análise de Sensibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Análise de Sensibilidade dos Coeficientes da Função Objetivo . . . . . . . . . . . . . 64
3.2.1 De variáveis não básicas na solução ótima . . . . . . . . . . . . . . . . . . . . 64
3.2.2 De variáveis básicas na solução ótima . . . . . . . . . . . . . . . . . . . . . . 65
3.3 Análise de Sensibilidade das constantes do lado direito . . . . . . . . . . . . . . . . 67
3.4 Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.1 Modelos Primal e Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.2 Teorema Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.3 Relação entre o Primal e o Dual . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.5 Valor ótimo das variáveis do Modelo Dual . . . . . . . . . . . . . . . . . . . . . . . . 72
3.6 Significado econômico dos valores ótimos das variáveis do Modelo Dual . . . . . . . . 74
3.7 Análise de Sensibilidade usando o Modelo Dual . . . . . . . . . . . . . . . . . . . . 75
3.7.1 Inclusão de uma nova variável . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.8 Análise de Sensibilidade dos coeficientes das restrições . . . . . . . . . . . . . . . . 77
3.8.1 De variável não básica na solução ótima . . . . . . . . . . . . . . . . . . . . . 77
3.8.2 De variável básica na solução ótima . . . . . . . . . . . . . . . . . . . . . . . 77
iv CONTEÚDO
3.9 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.10 Respostas dos exercícios da seção 3.9 . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4 Algorítimo dos Transportes 93
4.1 Um exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2 Formulação como um modelo clássico de P.Linear . . . . . . . . . . . . . . . . . . . 94
4.3 Quadro (tableau) usado no algorítimo dos transportes . . . . . . . . . . . . . . . . . 94
4.4 Fonte ou destino artificial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5 Impossibilidade de transporte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.6 Etapas do algorítimo dos transportes . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.7 Número de variáveis básicas nas soluções básicas . . . . . . . . . . . . . . . . . . . 96
4.8 Métodos para achar a solução básica inicial . . . . . . . . . . . . . . . . . . . . . . . 96
4.9 Esgotamento simultâneo de linha e coluna . . . . . . . . . . . . . . . . . . . . . . . 103
4.10 Teste para saber se uma solução básica é ótima . . . . . . . . . . . . . . . . . . . . . 105
4.11 Soluções básicas degeneradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.12 O Modelo da Baldeação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.13 Diferença entre Transporte e Baldeação . . . . . . . . . . . . . . . . . . . . . . . . 115
4.14 Adaptação do modelo da baldeação ao algorítimo do transporte . . . . . . . . . . . . 116
4.15 O Modelo da Atribuição ou da Designação . . . . . . . . . . . . . . . . . . . . . . . 118
4.16 Passos do Algorítimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.17 Impossibilidade de atribuição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.18 Fontes ou destinos artificiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.19 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.20 Respostas dos exercícios da seção 4.19 . . . . . . . . . . . . . . . . . . . . . . . . . 132
5 Bibliografia de Pesquisa Operacional 137
Capítulo 1
Introdução
Muitos colocam o desenvolvimento da Programação Linear (PL) como um dos avan-
ços científicos mais importantes do século XX. Seu impacto desde 1950 tem sido ex-
traordinário. Hoje em dia é uma ferramenta padrão que tem possibilitado grandes
ganhos para a maioria das companhias nos países industrializados, sendo que seu
uso em outros setores da sociedade vem crescendo rapidamente. Qual a natureza
desta ferramenta e que tipo de problemas ela resolve ? Neste capítulo aprende-
remos as respostas para estas 2 perguntas. Resumidamente, o tipo mais comum
de aplicação envolve o problema de distribuir recursos limitados entre atividades
que estão competindo por aquele recursos, da melhor maneira possível (isto é, da
maneira ótima). Programação Linear usa um modelo matemático para descrever
o problema . O termo linear significa que todas as funções matemáticas do mo-
delo são, obrigatoriamente, funções lineares. A palavra programação não se refere
a programação de computadores e deve ser vista como um sinônimo de planeja-
mento. Assim, podemos definir a programação linear como sendo o planejamento
de atividades para obter um resultado ótimo, isto é, um resultado que atenda, da
melhor forma possível, a um determinado objetivo. Embora alocação de recursos
para atividades seja o tipo mais comum, programação linear tem numerosos outros
tipos de aplicação. De fato, qualquer problema cujo modelo matemático se enqua-
dre na forma geral de um modelo de PL, é um problema de programação linear.
Um procedimento
Wesley
Wesley fez um comentário
4
0 aprovações
Carregar mais