apostila

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 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Solução gráfica . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Respostas dos exercícios da seção 1.3 . . . . . . . . . . . .
1.5 O modelo geral da Programação Linear . . . . . . . . . . .
1.6 Variações do Modelo Geral . . . . . . . . . . . . . . . . . .
1.7 O que está implícito em qualquer modelo de P.Linear . . .
1.8 Exemplos de formulação de modelos de Programação Linear
1.9 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.10 Respostas dos exercícios da seção 1.9 . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

1
1
4
10
12
16
16
16
18
24
29

2 O Método Simplex
2.1 Definições básicas . . . . . . . . . . . . . . . . .
2.2 Um método não muito eficiente . . . . . . . . . .
2.3 Situações que podem acontecer no Método Simplex
2.3.1 Empate na escolha da variável entrante . .
2.3.2 Empate na escolha da variável sainte . . .
2.3.3 Não existência de variável sainte . . . . .
2.3.4 Múltiplas (infinitas) soluções ótimas . . . .
2.3.5 Modelos de