LivroPL MAFM

Programa¸c˜ao Linear
Marco Antonio Figueiredo Menezes
Departamento de Computa¸c˜ao da
Universidade Cat´olica de Goi´as (UCG)
Endere¸co Eletrˆonico: [e-mail]
Setembro/2006

0

Este texto est´ a em elabora¸c˜ao. A primeira vers˜ao deste texto foi revisada pelo Professor Cl´ ovis Gonzaga. Uma segunda vers˜ao foi revisada pelo Professor Hilton Machado. Esta
´ importante lembrar que desde o in´ıcio, a partir de 1999, o texto foi
´e a terceira vers˜ ao. E utilizado e corrigido em minicursos (IV e V Encontro de Matem´atica e Estat´ıstica da UFG,
III UCGComp e V UCGComp e IV Encontro de Matem´atica da UEG-Unidade An´apolis), pelos meus alunos de Inicia¸c˜ao Cient´ıfica (1999-2004), no Semin´arios de Otimiza¸c˜ao que coordenamos aqui no Departamento de Computa¸c˜ao da UCG desde 1999 e na disciplina
An´
alise Aplicada Computacional (CMP4132) nas turmas de Ciˆencia da Computa¸c˜ao e
Engenharia de Computa¸c˜ ao da UCG (1999/2-2005/1).

Sum´ ario 1 Um Pouco da Hist´ oria 5

2 O Problema
9
2.1 O problema no formato padr˜ao . . . . . . . . . . . . . . . . . 9
2.2 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Sobre a Modelagem
3.1 Um problema da dieta
3.1.1 O problema . .
3.1.2 O modelo . . .
3.2 Exerc´ıcios . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

17
18
18
19
20

4 Poliedros e o Conjunto Vi´ avel 23
4.1 Poliedros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5 Caracteriza¸c˜ ao do Conjunto
5.1 Solu¸c˜ao b´asica vi´avel . . .
5.2 A caracteriza¸c˜ao de X . .
5.3 Exerc´ıcios . . . . . . . . .

Vi´ avel . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .

31
31
35
38

´
6 Caracteriza¸c˜ ao do Conjunto de Solu¸ c˜ oes