Pesquisa Operacional

APOSTILA DO CURSO

PESQUISA

OPERACIONAL

Prof. Erico Fagundes Anicet Lisboa, M. Sc.

[e-mail]

Versão digital disponível na internet

http://www.ericolisboa.eng.br

RIO DE JANEIRO, RJ - BRASIL

FEVEREIRO DE 2002

ii

ÍNDICE

1. INTRODUÇÃO À PESQUISA OPERACIONAL _________________________ 1

1.1 O Desenvolvimento da Pesquisa Operacional _________________________________________ 1

1.2 Modelagem ___________________________________________________________________ 1

1.3 Estrutura de Modelos Matemáticos_________________________________________________ 2

1.4 Técnicas Matemáticas em Pesquisa Operacional_______________________________________ 2

1.5 Fases do Estudo de Pesquisa Operacional____________________________________________ 3

1.5.1 Definição do problema ___________________________________________________________________3

1.5.2 Construção do modelo ___________________________________________________________________3

1.5.3 Solução do modelo _____________________________________________________________________3

1.5.4 Validação do modelo ____________________________________________________________________3

1.5.5 Implementação da solução________________________________________________________________4

2. ÁLGEBRA LINEAR ______________________________________________ 5

2.1 Vetores ______________________________________________________________________ 5

2.1.1 Soma e subtração de vetores ______________________________________________________________5

2.1.2 Vetores LD e LI________________________________________________________________________5

2.2 Matrizes _____________________________________________________________________ 6

2.2.1 Soma e subtração de matrizes _____________________________________________________________6

2.2.2 Produto de matrizes _____________________________________________________________________7

2.2.3 Matrizes especiais ______________________________________________________________________8

2.2.4 A inversa de uma matriz _________________________________________________________________8

2.3 Sistemas de Equações Lineares____________________________________________________ 9

2.3.1 Método algébrico por adição _____________________________________________________________ 10

2.3.2 Método algébrico por substituição _________________________________________________________ 10

2.3.3 Método de Gauss-Jordan ________________________________________________________________ 11

3. PROGRAMAÇÃO LINEAR________________________________________ 12

3.1 Definição____________________________________________________________________ 12

3.2 Formulação de Modelos ________________________________________________________ 12

3.3 Exemplo ____________________________________________________________________ 13

3.4 Solução Gráfica_______________________________________________________________ 13

iii

4. O MÉTODO SIMPLEX ___________________________________________ 15

4.1 Exemplo de um Problema_______________________________________________________ 15

4.2 Desenvolvimento do Método Simplex ______________________________________________ 18

4.3 Procedimento do Método Simplex (Problemas de Maximização) _________________________ 21

4.4 Outro Exemplo _______________________________________________________________ 21

4.5 Aspectos Matemáticos Singulares _________________________________________________ 23

4.5.1 Minimização de uma função _____________________________________________________________ 23

4.5.2 Restrições de limite inferior (³) ___________________________________________________________ 23

4.5.3 Restrições de igualdade _________________________________________________________________ 23

4.5.4 Variável irrestrita em sinal_______________________________________________________________ 23

4.5 Método Simplex em Duas Fases __________________________________________________ 24

5. A FERRAMENTA SOLVER (EXCEL) _______________________________ 27

5.1 Definindo e Resolvendo um Problema______________________________________________ 27

5.2 Instalando o Solver____________________________________________________________ 30

6. O PROBLEMA DE TRANSPORTE__________________________________ 31

6.1 Um Exemplo de Problema de Transporte ___________________________________________ 31

6.2 Problema Clássico de Transporte _________________________________________________ 32

6.3 Método de Stepping-Stone ______________________________________________________ 33

6.3.1 Solução inicial________________________________________________________________________ 33

6.3.2 Processo iterativo______________________________________________________________________ 33

6.4 Dificuldades do Problema de Transporte ___________________________________________